CS计算机代考程序代写 scheme prolog database algorithm CSE240

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= Pivot, split(Pivot,T,Le,Gt). % and put it into Gt

‹#›
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= Pivot, split(Pivot,T,Le,Gt).
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