程序代写代做代考 C Logic Programming and Prolog

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