Logic Programming and Prolog
Keep reading: Scott, Chapter 12
1
Lecture Outline
n Prolog n Lists
n Programming with lists n Arithmetic
Programming Languages CSCI 4430, A. Milanova 2
Lists
list head
[a,b,c] a
[X,[cat],Y] X
[a,[b,c],d] a
[X|Y] X
tail
[b,c]
a b
c
[[cat],Y]
[[b,c],d]
Y a
[]
Programming Languages CSCI 4430, A. Milanova
3
b c[]
[]
d
Lists: Unification
n [ H1 | T1 ] = [ H2 | T2 ]
n Head H1 unifies with H2, possibly recursively n Tail T1 unifies with T2, possibly recursively
n E.g.,[a|[b,c]]=[X|Y] n X=a
n Y=[b,c]
n NOTE: In Prolog, = denotes unification, not
assignment!
Programming Languages CSCI 4430, A. Milanova 4
Question
n [X,Y,Z] = [john, likes, fish] n X=john,Y=likes,Z=fish
n [cat] = [X | Y] n X=cat,Y=[]
n [[the, Y]|Z] = [[X, hare]|[is,here]] n X=the,Y=hare,Z=[is,here]
Programming Languages CSCI 4430, A. Milanova 5
Lists: Unification
n Sequence of comma separated terms, or n [ first term | rest_of_list ]
[[the|Y]|Z] =[[X,hare]|[is,here]]
Z
Y
is
here [ ]
hare []
the
Programming Languages CSCI 4430, A. Milanova
6
X
Lists Unification
n Look at the trees to see how this works! [ a, b, c ] = [ X | Y ]
X = a, Y = [b,c].
[a | Z ] =? [ X | Y ]
X = a, Y = Z.
Programming Languages CSCI 4430, A. Milanova 7
Improper and Proper Lists
[1 | 2] versus [1, 2]
12
1 2[]
Programming Languages CSCI 4430, A. Milanova
8
Question. Can we unify these lists?
[abc,Y] =? [abc|Y]
abc Y[]
abc
Y
Answer: No. There is no value binding for Y that makes these two trees
isomorphic
9
Aside: The Occurs check
Programming Languages CSCI 4430, A Milanova 10
Lecture Outline
n Prolog n Lists
n Programming with lists n Arithmetic
Programming Languages CSCI 4430, A. Milanova 11
Member_of
?- member(a,[a,b]). true.
?- member(a,[b,c]).
false.
?- member(X,[a,b,c]). X=a;
X=b; X=c; false.
1. member(A, [A | B]).
2. member(A, [B | C]) :- member(A, C).
Programming Languages CSCI 4430, A. Milanova 12
Member_of
?- member(a,[a,b]). true.
?- member(a,[b,c]).
false.
?- member(X,[a,b,c]). X=a;
X=b;
X = c.
?- member(a,[b,c,X]).
X=a; false.
1. member(A, [A | B]).
2. member(A, [B | C]) :- member (A, C).
Programming Languages CSCI 4430, A. Milanova 13
Prolog Search Tree (OR levels only)
member(X,[a,b,c])
A=X=a,B=[b,c]
X=a
success
A’=X=b,B’=[c]
A=X,B=a,C=[b,c]
member(X,[b,c])
success
X=c B”=c, C”=[] success member(X,[])
fail fail
A’=X,B’=b,C’=[c] member(X,[c])
X=b A”=X=c,B”=[] A”=X
1. member(A, [A | B]).
2. member(A, [B | C]) :- member (A, C).
14
Member_of
member(A, [A|B]).
member(A, [B|C]) :- member(A,C).
logical semantics: For every A,B and C member(A,[B|C]) if member(A,C);
procedural semantics: Head of clause is procedure entry. Tail of clause is procedure body; subgoals correspond to calls.
Programming Languages CSCI 4430, A. Milanova 15
“Procedural” Interpretation member(A, [A|B]).
member(A, [B|C]) :- member(A,C). member is a recursive “procedure”
member(A, [A|B]). is the base case. “Procedure” exits with true if the element we are
looking for, A, is the first element in the list. It exits with false if we have reached the end of the list
member(A, [B|C]) :- member(A,C). is the recursive case. If element A is not the first element in the list, call member recursively with arguments A
and tail C
Programming Languages CSCI 4430, A. Milanova 16
Question
1. member(A, [A | B]).
2. member(A, [B | C]) :- member(A, C).
Give all answers to the following query:
?- member(a,[b, a, X]).
Answer:
true ; X=a; false.
Programming Languages CSCI 4430, A. Milanova 17
Question
1. member(A, [A | B]).
2. member(A, [B | C]) :- member(A, C).
Give all answers to the following query:
?- member(a, [b | a]). Answer:
false.
Programming Languages CSCI 4430, A. Milanova 18
Append
append([ ], A, A).
append([A|B], C, [A|D]) :- append(B,C,D).
n Build a list:
?- append([a,b,c],[d,e],Y).
Y = [a,b,c,d,e]
n Break a list into constituent parts:
?- append(X,Y,[a,b]).
X = [], Y = [a,b]; X = [a], Y = [b]; X = [a,b], Y = []; false.
Programming Languages CSCI 4430, A. Milanova 19
More Append
append([ ], A, A).
append([A|B], C, [A|D]) :- append(B,C,D).
n Break a list into constituent parts ?- append(X,[b],[a,b]). X=[a]
?- append([a],Y,[a,b]). Y=[b]
Programming Languages CSCI 4430, A. Milanova 20
More Append
? – append(X,Y,[a,b]). X=[]
Y = [a,b] ;
X = [a]
Y=[b] ; X = [a,b] Y=[] ; false.
Programming Languages CSCI 4430, A. Milanova 21
Unbounded Arguments
n Generating an unbounded number of lists
?- append(X,[b],Y).
X=[]
Y = [b] ;
X = [ _G604] Y=[_G604,b] ;
X = [ _G604, _G610]
Y = [ _G604, _G610, b] ; Etc.
n Be careful when using append with 2 unbounded arguments!
22
An underscore, “don’t care” variable. Unifies with anything.
E.g., bad(Dog) :- bites(Dog,_).
Question
n What does this “procedure” do: p([],[]).
p([A|B],[[A]|Rest]) :- p(B,Rest).
?- p([a,b,c],Y).
Y = [ [a],[b],[c] ]
n Can also “flatten” a list: ?- p(X,[[a],[b],[c]]). X = [ a,b,c ]
Programming Languages CSCI 4430, A. Milanova 23
Common Structure
n “Processing” a list:
proc([],[]).
proc([H|T],[H1|T1]) :- f(H,H1),proc(T,T1).
n Base case: we have reached the end of list. In our case, the result for[ ]is[ ].
n Recursive case: result is [H1|T1]. H1 was obtained by calling f(H,H1) — processes element H into result H1. T1 is the result of
recursive call of proc on T.
Programming Languages CSCI 4430, A. Milanova 24
Lecture Outline
n Prolog n Lists
n Programming with lists n Arithmetic
Programming Languages CSCI 4430, A. Milanova 25
Arithmetic
n Prolog has all arithmetic operators n Built-in predicate is
n is(X, 1+3) or more commonly we write n X is 1+3
is forces evaluation of 1+3: ?- X is 1+3
X=4
n = is unification not assignment!
?- X = 4-1.
X = 4-1 % unifies X with 4-1!!!
Programming Languages CSCI 4430, A. Milanova 26
Arithmetic: Pitfalls
n is is not invertible! That is, arguments on
the right cannot be unbound!
n 3 is 3 – X.
ERROR: is/2: Arguments are not
sufficiently instantiated
n This doesn’t work either: ?- X is 4, X = X+1. false.
Why? What’s going on here?
Programming Languages CSCI 4430, A. Milanova 27
Exercise
n Write sum, which takes a list of integers and computes the sum of the integers. E.g.,
sum([1,2,3],R).
?- R = 6.
n How about if the integers are arbitrarily nested? E.g.,
sum([[1],[[[2]],3]],R).
?- R = 6.
Programming Languages CSCI 4430, A. Milanova 28
Exercise
Programming Languages CSCI 4430, A Milanova 29
Exercise
n Write plus10, which takes a list of integers
and computes another list, where all integers are shifted +10. E.g.,
plus10([1,2,3],R).
?- R = [11,12,13].
n Write len, which takes a list and computes the length of the list. E.g.,
len([1,[2],3],R).
?- R = 3.
Programming Languages CSCI 4430, A. Milanova 30
Exercise
n Write atoms, which takes a list and computes the number of atoms in the list.
E.g.,
atoms([a,[b,[[c]]]],R).
?- R = 3.
n Hint: built-in predicate atom(X) yields true if X is an atom (i.e., symbolic constant such as x, abc, tom).
Programming Languages CSCI 4430, A. Milanova 31
The End
Programming Languages CSCI 4430, A. Milanova 32