CSE240
Chapter 5
Logic Language Prolog
Lecture 26
Structure, Recursion, Pair and List
Reading: Textbook Sections 5.4 and 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
Pairs, lists and more operations
Flow Control
Chapter 5 Outline
‹#›
Ch 5
CSE240
11/19/2002
Scope of Prolog Variables
The scope of a Prolog variable is just within the fact, rule, or query (question) that contains the variable. For example:
likes(Person, prolog) :-
likes(Person, programming),
likes(Person, logic).
The scope of Person is the entire rule (3 appearances). If
?- likes(john, prolog).
john will be instantiated to 3 appearances of Person.
?- likes(Who, prolog).
Who will be instantiated to all people who likes prolog.
‹#›
Ch 5
CSE240
11/19/2002
Scope Example
mother_of(elaine, gloria).
mother_of(gloria, sarah).
mother_of(mary_lou, bubba).
father_of(mike, gloria).
father_of(bubba, sarah).
father_of(bill_bobb, bubba).
parent(Parent, Child) :- mother_of(Parent, Child).
parent(Parent, Child) :- father_of(Parent, Child).
grandpa(X, Y) :- parent(X, G1), parent(G1, Y).
greatgrandpa(X, Y) :- parent(X, G1), parent(G1, G2), parent(G2, Y).
greatgreatgrandpa(X, Y) :- parent(X, G1), parent(G1, G2), parent(G2, G3), parent(G3, Y).
generation(G, X, Y) :- parent(X, Y), G is 1.
generation(G, X, Y) :- grandpa (X, Y), G is 2.
generation(G, X, Y) :- greatgrandpa(X, Y), G is 3.
generation(G, X, Y) :- greatgreatgrandpa(X, Y), G is 4.
rules
facts
‹#›
Ch 5
CSE240
11/19/2002
Recursion and Recursive Rules
Let’s consider the family database:
mother_of(elaine, gloria).
mother_of(gloria, sarah).
mother_of(mary_lou, bubba).
mother_of(elizabeth, elaine).
father_of(mike, gloria).
father_of(bubba, sarah).
father_of(bill_bobb, bubba).
father_of(herman, elaine).
parent(Parent, Child) :- mother_of(Parent, Child). parent(Parent, Child) :- father_of(Parent, Child).
‹#›
Ch 5
CSE240
11/19/2002
Recursion and Recursive Rules (contd.)
grandparent(A, D) :-
parent(A, Person),
parent(Person, D).
Deeper relationships:
greatgrandparent(A, D) :-
parent(A, Person), grandparent(Person, D).
‹#›
Ch 5
CSE240
11/19/2002
Recursion and Recursive Rules (contd.)
A rule is recursive, if a clause in the condition matches the conclusion: they have the same predicate and arity.
ancestor(A, D) :-
ancestor (A, P),
ancestor(P, D).
A
P
D
Ancestor
Ancestor
ancestor(A, D) :-
parent(A, P),
ancestor(P, D).
A
P
D
Ancestor
Parent
ancestor(A, D) :-
parent(A, D).
Size n
Size m
Size m
Stopping condition
Size n-1
Size n
‹#›
Ch 5
CSE240
11/19/2002
Tracing Recursive Rules
?- ancestor(mike, sarah)
Try the 1st ancestor rule with mike and sarah.
?- ancestor(mike, sarah).
?- parent(mike, sarah).
?- mother_of(mike, sarah). fail
?- father_of(mike, sarah). fail
Try the 2nd ancestor rule with mike and Person.
?- ancestor(mike, Person).
?- parent(mike, Person).
?- mother_of(mike, Person). fail
?- father_of(mike, Person). succeed
mother_of(elaine, gloria).
mother_of(gloria, sarah).
mother_of(mary_lou, bubba).
mother_of(elizabeth, elaine).
father_of(mike, gloria).
father_of(bubba, sarah).
father_of(bill_bobb, bubba).
father_of(herman, elaine).
parent(Parent, Child) :-
mother_of(Parent, Child).
parent(Parent, Child) :-
father_of(Parent, Child).
ancestor(A, D) :-
parent(A, D).
ancestor(A, D) :-
parent(A, P),
ancestor(P, D).
‹#›
Ch 5
CSE240
11/19/2002
Tracing Recursive Rules (contd.)
?- father_of(mike, Person). succeed
Person = gloria but not sarah
Try the recursive rule with gloria and sarah.
The 3rd rule will call the 1st ancestor rule.
?- ancestor(gloria, sarah).
?- parent(gloria, sarah).
?- mother_of(gloria, sarah). succeed
“yes”
mother_of(elaine, gloria).
mother_of(gloria, sarah).
mother_of(mary_lou, bubba).
mother_of(elizabeth, elaine).
father_of(mike, gloria).
father_of(bubba, sarah).
father_of(bill_bobb, bubba).
father_of(herman, elaine).
parent(Parent, Child) :-
mother_of(Parent, Child).
parent(Parent, Child) :-
father_of(Parent, Child).
ancestor(A, D) :-
parent(A, D).
ancestor(A, D) :-
parent(A, P),
ancestor(P, D).
You can also use the auto tracing tool:
| ?- trace.
| ?- ancestor(mike, sarah).
| ?- notrace.
‹#›
Ch 5
CSE240
11/19/2002
Representing a Graph
Let’s consider another example with a recursive rule:
/* the list of edges in a directed graph: */
edge(a,b).
edge(a,c).
edge(b,d).
edge(c,d).
edge(c,f).
edge(d,e).
edge(f,g).
edge(g, h).
edge(i,j). edge(j, k). edge(k, i).
a
b
c
d
e
f
g
h
i
j
k
‹#›
Ch 5
CSE240
11/19/2002
Representing “connected” relation
Let’s consider whether we can reach a certain node from a given node.
Definition: connected (Node1, Node2) iff we can travel from Node1, following the direction of the edges to Node2.
connected(Node1, Node2) :-
edge(Node1, Node2), !.
connected(Node1, Node2) :-
edge(Node1, X),
connected(X, Node2).
a
b
c
d
e
f
g
h
i
j
Exclamation mark
is called a “cut”. It removes all existing backtrack points.
‹#›
Ch 5
CSE240
11/19/2002
Adding and Removing Backtrack Points
/*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).
Prolog runtime searches iteratively, not recursively. Add a backtrack point to mark the return point.
A cut (!) removes all existing backtrack points.
‹#›
Ch 5
CSE240
11/19/2002
Representing an Undirected Graph
edge(a,b).
edge(a,c).
edge(b,d).
edge(c,d).
edge(c,f).
edge(d,e).
edge(f,g).
edge(g, h).
edge(i,j).
a
b
c
d
e
f
g
h
i
j
edge(b, a).
edge(c, a).
edge(d, b).
edge(d, c).
edge(f, c).
edge(e, d). edge(g, f). edge(h, g). edge(j, i).
edge(X, Y) :- edge(Y, X).
Problem? Try
?- edge(a, d)
‹#›
Ch 5
CSE240
11/19/2002
Circular Definition of Rules
A circular definition in a fact-rule base may cause dead looping.
edge(X, Y) :- edge(Y, X).
is a circular definition. Another example is:
parent(X, Y) :- child(Y, X).
child(X, Y) :- parent(Y, X).
It is fine for the questions that have a “yes” answer, but …
‹#›
Ch 5
CSE240
11/19/2002
Connected Undirected Graph
adjacent(X, Y) :- adjacent(X, Y) :-
edge(X, Y); edge(X, Y).
edge(Y, X). adjacent(X, Y) :-
edge(Y, X).
a
b
c
d
e
f
g
h
i
j
connected(Node1, Node2) :-
adjacent(Node1, Node2).
connected(Node1, Node2) :-
adjacent(Node1, X),
connected(X, Node2).
Is this a proper definition of a recursive rule?
=
‹#›
Ch 5
CSE240
11/19/2002
AI Application: Map Coloring
Neighboring states must use different colors
Graph model: Node = State and edge(X,Y) if they are adjacent
Washington
Oregon
California
Nevada
Arizona
Utah
Wyoming
Idaho
az
ca
or
ne
id
ut
wy
‹#›
Ch 5
CSE240
11/19/2002
Factbase and rulebase
edge(az, ca).
edge(az, ne).
edge(az, ut).
edge(ca, ne).
edge(ca, or).
edge(ne, ut).
edge(ne, or).
edge(ne, id).
edge(ut, id).
edge(ut, wy).
edge(id, wy).
edge(or, id).
adjacent(X, Y) :-
edge(X, Y); edge(Y, X).
az
ca
or
ne
id
ut
wy
Neighboring States must use different colors
color(az, orange).
color(ca, yellow).
color(ne, red).
color(ut, yellow).
color(or, orange).
color(id, yellow).
color(wy, red).
az
ca
or
ne
id
ut
wy
‹#›
Ch 5
CSE240
11/19/2002
Detecting the coloring error automatically
edge(az, ca).
edge(az, ne).
edge(az, ut).
edge(ca, ne).
edge(ca, or).
edge(ne, ut).
edge(ne, or).
edge(ne, id).
edge(ut, id).
edge(ut, wy).
edge(id, wy).
edge(or, id).
color(az, orange).
color(ca, yellow).
color(ne, red).
color(ut, yellow).
color(or, orange).
color(id, yellow).
color(wy, red).
adjacent(X, Y) :-
edge(X, Y); edge(Y, X).
miscolor(S1, S2, Color1) :-
adjacent(S1, S2),
color(S1, Color2),
color(S2, Color3).
az
ca
or
ne
id
ut
wy
| ?- miscolor(S1, S2, C).
C = yellow
S1 = ut
S2 = id ? ;
C = yellow
S1 = id
S2 = ut ? ;
no
| ?- miscolor(S1, S2, C).
no
Fix the coloring error
ut
color(ut, green).
Should
Color1 = Color2 = Color3?
Yes
1
1
Is it recursive?
‹#›
Ch 5
CSE240
11/19/2002
except display
Summary of Parameter Passing: What are Allowed?
C/C++ Java Scheme Prolog
Call- always primitive always always
by-value
Call-
by-reference/ always object never always
by address
Return yes & yes & always true or false
value no (void) no
Function as first not always not always always never
class object
except display
never other
‹#›
Ch 5
CSE240
11/19/2002
Writing Recursive Rules in Prolog
Using the Four-Step Abstract Approach
Identify size-n problem;
Find the stopping condition and the return value at the stopping condition;
Place the stopping rule before the recursive rule.
Identify size-m (e.g., m = n-1) problem and assume it will return the solution;
Construct the size-n problem solution based on the assumed size-m solution.
‹#›
Ch 5
CSE240
11/19/2002
Recursion Example: Factorial
factorial(0,1) :- !, /* This cut “!” has nothing to do with factorial */
/* It removes backtrack points and reduce search options*/
write(‘Completed’).
factorial(N,F) :-
N>0,
N1 is N-1,
factorial(N1,F1),
F is N * F1.
?- factorial(3, 6).
yes
yes
Algorithm: F = 1*2*3*…*N
factorial(N-1,F1)
‹#›
Ch 5
CSE240
11/19/2002
Arithmetic Goals vs. Logical Goals
What will be returned?
?- factorial(3, F).
?- factorial(3, 5).
?- factorial(3, 6).
?- factorial(X, 6).
F = 6
no
yes
X = 3? or no?
instantiation_error!
foo(X, Y) :- Y is 2*X.
?- foo(4, Y). Y = 8
?- foo(X, 8). error
foo(X, Y) :- Y is 2*X; X is Y/2.
?- foo(4, Y). Y = 8
?- foo(X, 8). X = 4? error
For arithmetic operations, logic specification do not work. We still follow imperative ways.
‹#›
Ch 5
CSE240
11/19/2002
Recursion with Dead Loop
/* other facts and rules */
factorial(N,F) :-
N1 is N-1,
factorial(N1,F1),
F is N * F1.
factorial(0,1).
/* other facts and rules */
?- factorial(2, Fac).
The following program tries to calculate F = n!
‹#›
Ch 5
CSE240
11/19/2002
Recursion vs. While Loop in C++
void factorial(int N, int *F) {
int P = 1, N1 = N;
while (N1 > 0) {
P = P*N1;
N1 = N1 – 1;
}
*F = P;
}
void factorial(int N, int *F) {
int F1;
if (N == 1)
*F = 1;
else {
factorial(N-1, &F1);
*F= N * F1;
}
}
void main() {
int F;
factorial(4, &F);
printf(“F = %d\n”, F);
}
Do you recall the uses of * and &
Do you recall the uses of * and &
‹#›
Ch 5
CSE240
11/19/2002
Factorial with Tail Recursion
A tail-recursive function is structurally easier to understand.
It is a special case of (less powerful than) recursion: loop!
But it may be more difficult conceptually to understand.
factorial(int N, int *F) {
int P = 1, N1 = N;
while (N1 > 0) {
P = P*N1;
N1 = N1 – 1;
}
*F = P;
}
fac(N, F) :- factorial(N, 1 ,F).
factorial(0, P, P) :- !.
factorial(N, P, F) :-
N > 0,
P1 is P*N,
N1 is N – 1,
factorial(N1, P1, F).
Prolog
C++
‹#›
Ch 5
CSE240
11/19/2002
Factorial with Tail Recursion
| ?- trace.
| ?- fac(3, F).
Call: fac(3,_15) ?
Call: factorial(3,1,_15) ?
Call: factorial(2,3,_15) ?
Call: factorial(1,6,_15) ?
Call: factorial(0,6,_15) ?
Exit: factorial(0,6,6) ?
Exit: factorial(1,6,6) ?
Exit: factorial(2,3,6) ?
Exit: factorial(3,1,6) ?
Exit: fac(3,6) ?
F = 6
| ?- notrace.
‹#›
Ch 5
CSE240
11/19/2002
Another Tail-Recursion Example (while-loop)
table_head :-
write(‘Name’),
tabulate(5), write(‘Address’),
tabulate(10), write(‘Phone’),nl.
tabulate(N) :- % print N spaces
N>0, % stopping condition
write(‘ ‘),
M is N – 1, % size-N solution
tabulate(M). % Assume size-M solution
| ?- table_head.
Name Address Phone
‹#›
Ch 5
CSE240
11/19/2002