CSE240
Chapter 5
Logic Language Prolog
Lecture 28
More List Operations and
Flow Control
Reading: Textbook Section 5.5
Dr. Yinong Chen
CSE240
Introduction to Programming Languages
‹#›
Ch 5
CSE240
11/19/2002
Introduction
Logic programming paradigm
Prolog programs: facts, rules, and goals
Factbase
Goals (Questions)
Rulebase
Compound questions
Arithmetic operations and rules
Recursion and graph operations
Parameter Passing
More recursive programs
Structures of facts and rules
More lists operations
Flow Control
Chapter 5 Outline
‹#›
Ch 5
CSE240
11/19/2002
Quicksort Idea: Sort people by their ages
age
25
people
age =< 25
people
age > 25
age
20
people
age =< 20
age
27
people
age > 27
people
age > 20
people
age =< 27
pivot
pivot
pivot
‹#›
Ch 5
CSE240
11/19/2002
Quick Sort Code in Prolog
qsort([],[]) :- !. % empty list is already sorted
qsort([Pivot|Tail],Sorted):- % Take first number as pivot
split(Pivot, Tail, L1, L2),
qsort(L1,Sorted1), % sort first part
qsort(L2,Sorted2), % sort second part
append(Sorted1,[Pivot|Sorted2], Sorted).
split(_,[],[],[]). % stopping condition
split(Pivot,[X|T],[X|Le],Gt):- % take first from Tail
X=
‹#›
Ch 5
CSE240
11/19/2002
Quick Sort Code Testing
| ?- [quicksort].
compiling /afs/asu.edu/users/y/c/h/ychen/Prolog/quicksort.pl for byte code…
/afs/asu.edu/users/y/c/h/ychen/Prolog/quicksort.pl compiled, 12 lines read – 2002 bytes written, 11 ms
Yes
| ?- qsort([8, 3, 4, 12, 25, 4, 6, 1, 9, 22, 6], Sorted).
Sorted = [1,3,4,4,6,6,8,9,12,22,25] ?
yes
| ?-
‹#›
Ch 5
CSE240
11/19/2002
void Quicksort (A, L, R) {
if R == L then return; else {
k = split(A, L, R);
Quicksort (A, L, k-1);
Quicksort (A, k+1, R);
} }
int split(A, L, R) {
int pivot = A[R]; i = L; j = R;
while i < j do {
while (A[i] < pivot) do i = i+1;
while ((j > i) && (A[j] >= pivot)) do j = j – 1;
if (i < j) then
swap(A[i], A[j]); // swap the values
}
swap(A[i], A[R]);
return i;
}
Quicksort in Imperative Algorithm
A
L
k
R
i
j
How do you write Prolog code by taking the right-most element as the pivot?
‹#›
Ch 5
CSE240
11/19/2002
Complexity of Sorting Algorithms
Sorting Algorithm Worse-case Average
Insertion Sort O(n2) Slow
Selection Sort O(n2) Slow
Mergesort O(nlog2n) Fast
Quicksort O(n2) Fastest
‹#›
Ch 5
CSE240
11/19/2002
How do you write Prolog code to remove the last element of a list?
Find Elements in Specific Positions
first(X, [X | _ ]).
car(X, [X | _ ]).
?- first(First, [a, b, c, d]). First = a
?- car(First, [a, b, c, d]). First = a
second(X, [ _, X | _ ]). second(X, [ _ | [X | _ ]]).
cadr(X, [ _, X | _]).
?- second(Second, [a, b, c, d]) . Second = b
?- cadr (Second, [a, b, c, d]). Second = b
last(X, [X]). % stopping condition
last(X, [ _ | Tail]) :- last(X, Tail). % recursive
Remove the head repeatedly until there is only one left
first(X, [X | T ]).
Singleton warning
‹#›
Ch 5
CSE240
11/19/2002
Singleton
Counting List Elements
count([ ], 0) :- !. % cut, stop checking other rules
count([ _ | Tail], S) :-
count(Tail, S2),
S is 1+S2.
Remove the first element,
Find the count of the reduced list,
The Num of original list is one more than the reduced list.
There is a built-in predicate: length(List, Len).
sum_list([ ], 0). % stopping condition
sum_list([Head|Tail], Sum) :-
sum_list(Tail, Sum2),
Sum is Head+Sum2.
count([X | Tail], S) :-
count(Tail, S2),
S is 1+S2.
‹#›
Ch 5
CSE240
11/19/2002
Forming New Lists
Insert a new element to the head position:
addhead(List, Element, [Element | List]). % cons
?- addhead([a, b, c, d], x, Newlist).
Newlist = [x, a, b, c, d]
?- addhead(Oldlist, a, [a, b, c, d]).
Oldlist = [b, c, d]
?- addhead([b, c, d], X, [a, b, c, d]).
X = a
Example of appending two lists:
?- append([a, b, c, d], [x, y, z], Newlist).
Newlist = [a, b, c, d, x, y, z]
How do you implement this function?
‹#›
Ch 5
CSE240
11/19/2002
Forming New Lists (contd.)
Append Two Lists: % build-in predicate
append([ ], X, X). % stopping condition
append([X | Y], Z, [X | W]) :- % size-n problem & constr
append(Y, Z, W). % size-(n-1) problem
If Y appends Z W, then, [X | Y] appends Z [X | W]
?- append([a, b, c], [d, f, g], X) X = [a, b, c, d, f, g]
?- append(H, [d, f, g], [x, a, b, c, d, f, g])
H = [x, a, b, c]
Reverse a List:
reverse([ ],[ ]). % Stopping condition
reverse([X | L],Rev) :- % size-n problem
reverse(L, RL), % size-(n-1) problem append(RL, [X], Rev). % construction
How do you do it in Scheme?
‹#›
Ch 5
CSE240
11/19/2002
Duplicate-Removal from a List (drm)
[7, 1, 3, 2, 3, 4, 2, 1, 3] [7, 4, 2, 1, 3]
drm(InputList, NewList).
| ?- drm([7, 1, 3, 2, 3, 4, 2, 1, 3], NL).
NL = [7, 4, 2, 1, 3]
‹#›
Ch 5
CSE240
11/19/2002
Duplicates Removal from a List (drm)
drm([], []):- !.
drm([Head | Tail], NL):- member(Head, Tail), write('removed member = '), write(Head), nl, drm(Tail, NL), !.
drm([H1 | T1], [H1 | NL2]):- drm(T1, NL2).
| ?- drm([7, 1, 3, 2, 3, 4, 2, 1, 3], NL).
removed member = 1
removed member = 3
removed member = 2
removed member = 3
NL = [7, 4, 2, 1, 3]
If member(Head, Tail) is true, it will not be executed. Otherwise, it will be executed, because cut will not be executed
‹#›
Ch 5
CSE240
11/19/2002
Duplicates Removal Trace
drm([], []):- !.
drm([Head | Tail], NL):- member(Head, Tail),
write('removed member = '), write(Head), nl,
drm(Tail, NL), !.
drm([H1 | T1], [H1 | NL2]):- drm(T1, NL2).
7 3 Call: drm([4,2,3],_58) ?
8 4 Call: member(4,[2,3]) ?
8 4 Fail: member(4,[2,3]) ?
8 4 Call: drm([2,3],_203) ?
9 5 Call: member(2,[3]) ?
9 5 Fail: member(2,[3]) ?
9 5 Call: drm([3],_229) ?
10 6 Call: member(3,[]) ?
10 6 Fail: member(3,[]) ?
10 6 Call: drm([],_255) ?
10 6 Exit: drm([],[]) ?
9 5 Exit: drm([3],[3]) ?
8 4 Exit: drm([2,3],[2,3]) ?
7 3 Exit: drm([4,2,3],[4,2,3]) ?
2 2 Exit: drm([3,4,2,3],[4,2,3]) ?
1 1 Exit: drm([7,3,4,2,3],[7,4,2,3]) ?
NL = [7,4,2,3]
| ?- drm([7, 3, 4, 2, 3], NL).
1 1 Call: drm([7,3,4,2,3],_26) ?
2 2 Call: member(7,[3,4,2,3]) ?
2 2 Fail: member(7,[3,4,2,3]) ?
2 2 Call: drm([3,4,2,3],_58) ?
3 3 Call: member(3,[4,2,3]) ?
3 3 Exit: member(3,[4,2,3]) ?
4 3 Call: write('removed member = ') ?
removed member =
4 3 Exit: write('removed member = ') ?
5 3 Call: write(3) ?
3
5 3 Exit: write(3) ?
6 3 Call: nl ?
6 3 Exit: nl ?
Cut executed
Recursive continues
7 added into list _58
4 added into list _203
2 added into list _229
3 added into list _255
‹#›
Ch 5
CSE240
11/19/2002
Quicksort In-Class Exercise
split(_,[],[],[]).
split(Pivot,[X|T],[X|Le],Gt):-
X=
Q1: What are the size-n problems?
[ ] Line 1 [ ] Line 2
[ ] Line 3 [ ] Line 4
[ ] Line 5
1
2
3
4
5
Q2: What is the stopping condition?
Line 1 (B) Line 2
(C) Line 3 (D) Line 4
(E) Line 5
Q3: At Line 1, what will happen if we write split(P,[],[],[]).?
Compilation error
Singleton warning
Execution exception
(D) Completely equivalent
Q4: What is the size of size-m problem?
n (B) n-1
(C) n-2 (D) n-3
(E) < n-3
Q5: Which lines need to be changed if we want to sort by descending order?
[ ] Line 1 [ ] Line 2
[ ] Line 3 [ ] Line 4
[ ] Line 5
‹#›
Ch 5
CSE240
11/19/2002
Flow Control: Cut (!) and Repeat
There are several built-in predicates that can be used to change order of searching the database.
Cut (!) is a special control facility enabling programmers to restrict the backtracking options. factorial(0, 1) :- !.
Cut will succeed (return true) when it is met (executed) for the first time, but will fail in any subsequent visits. (?)
Cut removes all existing backtracking points, but new backtracking points can be added later.
It may cut off valid options and thus the system cannot find all answers when you enter the semi-colon.
Use cut if you are sure there are no more answers or you don’t want to have more answers.
‹#›
Ch 5
CSE240
11/19/2002
Backtracking Points
A backtracking point is a point from which the Prolog runtime will re-start its search, if
- the current search fails, or
- the current search succeeds but a semi-colon is entered thereafter.
‹#›
Ch 5
CSE240
11/19/2002
What is a backtracking point?
/*Facts
mother_of(jane, elaine).
mother_of(jane, mike).
father_of(mike, andrew).
father_of(andrew, conrad).
/*Rules
grandmother_of(X, Z) :-
mother_of(X, Y),
(mother_of(Y, Z);
father_of(Y, Z)).
?-grandmother_of(jane, conrad).
grandmother_of(jane, conrad).
mother_of(jane, Y).
mother_of(jane, elaine).
mother_of(elaine, conrad).
father_of(elaine, conrad).
mother_of(jane, mike).
No
mother_of(mike, conrad).
father_of(mike, conrad).
backtracking point
‹#›
Ch 5
CSE240
11/19/2002
Adding and removing backtracking points
! cut
‹#›
Ch 5
CSE240
11/19/2002
Cut (!) Example
warm_blooded(cat).
warm_blooded(dog).
warm_blooded(chicken).
four_legs(cat).
four_legs(dog).
two_legs(chicken).
mammal(M) :-
warm_blooded(M), four_legs(M), !.
|?- mammal(X).
--> X = cat;
no (X = dog is cut off)
This example shows that a cut reduces possible answers
backtracking point
What is the impact?
‹#›
Ch 5
CSE240
11/19/2002
Understanding Cut (!)
mammal0(M) :-
warm_blooded(M), four_legs(M).
mammal1(M) :-
!, warm_blooded(M), four_legs(M).
mammal3(M) :-
warm_blooded(M), four_legs(M), !.
mammal2(M) :-
warm_blooded(M), !, four_legs(M).
|?- mammal0(X). |?- mammal1(X).
|?- mammal2(X). |?- mammal3(X).
What are the differences among the four rules?
‹#›
Ch 5
CSE240
11/19/2002
Will cut (!) stop recursion?
Consider the program:
factorial(0,1) :- !.
factorial(N,F) :- N>0, N1 is N-1,
factorial(N1,F1),
F is N * F1.
?- factorial(2, F).
factorial(1, F).
factiorial(0, F).
!.
F=1.
Will this cut remove the “backtracking points” and result in F = 1, instead of F = 2?
Exit: F=2*1.
Exit: F=2.
‹#›
Ch 5
CSE240
11/19/2002
recursive call
part 2
part 1
1
2
n
1
2
n
recursive call
part 2
part 1
1
2
n
1
2
n
A backtracking point is NOT a recursive exit point, from which the part 2 of the code (code after the recursive call) must be completed.
Recursive exit points may not be removed by cut (!).
Will cut (!) stop recursion?
recursive exit point
‹#›
Ch 5
CSE240
11/19/2002
Using Cut (!) for Functionality
Not Only for Efficiency
‹#›
Ch 5
CSE240
11/19/2002
Define not-operator using Cut
not(X) :- X, !, fail. % what happen if ! is not used?
not(_).
If X is true, cut will be executed (returns true), and then fail will be executed too, which will fail.
If X is false, cut and fail will not be executed, and thus, the next not(_) clause will be executed. As it has no condition. It always succeed.
Anonymous variable is used to prevent a “singleton” variable warning.
fail is a clause that always fails.
‹#›
Ch 5
CSE240
11/19/2002
Example of Using not-Operator
female(elaine).
female(jane).
female(sarah).
male(conrad).
male(joe).
married(luke).
married(mike).
father_of(andrew, conrad).
father_of(luke, mike).
father_of(mike, andrew).
mother_of(elaine, sarah).
mother_of(jane, edith).
mother_of(jane, mike).
/* Rules */
not(P) :- P, !, fail.
not(_).
is_male(X) :- father_of(X, _); male(X).
is_female(X) :- mother_of(X, _); female(X).
bachelor(X) :- is_male(X), not(married(X)).
grandmother_of(X, Z) :- mother_of(X, Y),
(mother_of(Y, Z); father_of(Y, Z)).
familyquestions :-
grandmother_of(X, andrew),
write(‘The grandmother of andrew is ‘),
write(X), nl,
father_of(Y, mike),
write(Y), write(‘ is the father of mike’), nl,
bachelor(Z), write(Z), write(‘ is a bachelor’),nl.
| ?- familyquestions.
The grandmother of andrew is jane
luke is the father of mike
andrew is a bachelor
true ? ;
conrad is a bachelor
true ? ;
joe is a bachelor
What is the stored program concept?
What is the stored program concept?
‹#›
Ch 5
CSE240
11/19/2002
Duplicate-Removal from a List (drm)
[7, 1, 3, 2, 3, 4, 2, 1, 3] [7, 4, 2, 1, 3]
drm(InputList, NewList).
| ?- drm([7, 1, 3, 2, 3, 4, 2, 1, 3], NL).
NL = [7, 4, 2, 1, 3]
‹#›
Ch 5
CSE240
11/19/2002
Duplicates Removal from a List (drm)
drm([], []):- !.
drm([Head | Tail], NL):- member(Head, Tail), write(‘removed member = ‘), write(Head), nl, drm(Tail, NL), !.
drm([H1 | T1], [H1 | NL2]):- drm(T1, NL2).
| ?- drm([7, 1, 3, 2, 3, 4, 2, 1, 3], NL).
removed member = 1
removed member = 3
removed member = 2
removed member = 3
NL = [7, 4, 2, 1, 3]
If member(Head, Tail) is true, it will not be executed. Otherwise, it will be executed, because cut will not be executed
‹#›
Ch 5
CSE240
11/19/2002
Duplicates Removal Trace
drm([], []):- !.
drm([Head | Tail], NL):- member(Head, Tail),
write(‘removed member = ‘), write(Head), nl,
drm(Tail, NL), !.
drm([H1 | T1], [H1 | NL2]):- drm(T1, NL2).
7 3 Call: drm([4,2,3],_58) ?
8 4 Call: member(4,[2,3]) ?
8 4 Fail: member(4,[2,3]) ?
8 4 Call: drm([2,3],_203) ?
9 5 Call: member(2,[3]) ?
9 5 Fail: member(2,[3]) ?
9 5 Call: drm([3],_229) ?
10 6 Call: member(3,[]) ?
10 6 Fail: member(3,[]) ?
10 6 Call: drm([],_255) ?
10 6 Exit: drm([],[]) ?
9 5 Exit: drm([3],[3]) ?
8 4 Exit: drm([2,3],[2,3]) ?
7 3 Exit: drm([4,2,3],[4,2,3]) ?
2 2 Exit: drm([3,4,2,3],[4,2,3]) ?
1 1 Exit: drm([7,3,4,2,3],[7,4,2,3]) ?
NL = [7,4,2,3]
| ?- drm([7, 3, 4, 2, 3], NL).
1 1 Call: drm([7,3,4,2,3],_26) ?
2 2 Call: member(7,[3,4,2,3]) ?
2 2 Fail: member(7,[3,4,2,3]) ?
2 2 Call: drm([3,4,2,3],_58) ?
3 3 Call: member(3,[4,2,3]) ?
3 3 Exit: member(3,[4,2,3]) ?
4 3 Call: write(‘removed member = ‘) ?
removed member =
4 3 Exit: write(‘removed member = ‘) ?
5 3 Call: write(3) ?
3
5 3 Exit: write(3) ?
6 3 Call: nl ?
6 3 Exit: nl ?
Cut executed
Recursive continues
7 added into list _58
4 added into list _203
2 added into list _229
3 added into list _255
‹#›
Ch 5
CSE240
11/19/2002