CS661 Artifical Intelligence
Lecture 8 - more PROLOG
- the cut
- succeeds immediately but is never resatisfied
- as side effect - commits to all before it
- so cut stops backtracking
- genesis family example
is_father(X) :- father(X,_).
abraham ; abraham
in order to get the result only once ...
is_father :- father(X,_), !.
the cut is like a fence
use of !, fail.
- foo :- a, b, c, !, d, e, f.
- a, b, c backtrack, but once c succeeds we never try a or b or c again
- d, e, f can later backtrack
average_taxpayer(X) :- non_citizen(X), fail.
average_taxpayer(X) :- income<100000.
this is wrong since may resatisfy later !
so use ...
average_taxpayer(X) :- non_citizen(X), !, fail.
average_taxpayer(X) :- income<100000.
let's sum from 1 to N (assume N>=1)
sum(1,1) :- !.
sum(N,R) :- N1 is N-1, sum(N1,R), R is R+N.
need the cut since if had
can replace cut with use of not( ) predicate
- go :- sum(1,X), foo(Y).
- and foo(Y) fails, PROLOG will try to reinstantiate sum(1,X).
- sum(1,1). sum(N,R) :- not(N=<1), N1 is N-1, sum(N1,R), R is R+N.
- LISP language has list as its only data structure
- which is why it is a list processing language
- PROLOG has list a one possible data structure
- a list is a set with order
- by placing lists inside lists we can make tree structures
- [ ] the empty list
- [a, b, c, d] a list with four elements
- [a, [b,c], d] a list with three elements, the second of which is a list
- one manipulation of lists is to separate head from tail
- head is the first elements in the list, the tail is the rest of the list (a list!)
- [ head | tail ]
- there are potential problems with this notation, e.g. [A|B] = [X,Y]
- ?- [H, T] = [a, b, c, d]. H=a T=[b,c,d]
- ?- [H,T] = [a]. H=a, T=[ ]
- ?- [H,T] = [ ]. no
- dot notation - binary tree interpretation
- [a] == .(a,)
- [a,b,c] == .(a,.(b,.(c,)))
- some LISP-like predicates (most with 2 uninstantiated variables)
- ?- append([a,b,c], [1,2,3], [a,b,c,1,2,3]). yes
- ?- append([a,b], [c,d], X). X=[a,b,c,d]
- ?- append(X, [b,c,d], [a,b,c,d]). X=[a]
- how is append defined ?
append([ ], L, L).
append([H | L1], L2, [H | L3]) :- append(L1, L2, L3).
- tells if instantiated variable is a list
- note that not all [A|B] are lists - only if B is a list !
- how is is_list defined ?
is_list( [A | B] ) :- is_list(B).
meaningless for uninstantiated variable
- 1) use var predicate
- 2) use weaker test, e.g. is_list(). is_list([_,_]). (but some non-lists will pass)
- defined in the following way:
- this is better than defining
- member(X, [Y | _ ] :- X=Y.
- member(X, [_ | Y]) :- member(X,Y).
last(X,[_|Y) :- last(X,Y).
append can often be used instead
- last(L,List) := append(_,[L],List).
- member(M,List) :- append(_,[M|_], List).
- basic tools in AI languages such as PROLOG and LISP
- need to ensure termination (easy for lists and the cut)
- first example
- is_integer: is_integer(0).
- is_integer(X) :- is_integer(Y), X is Y+1.
- answers are 0; 1; 2; 3 ...
- classic exmaple of recursion is factorial
factorial(N,R) :- N>1, N1 is N-1, factorial(N1,Tmp), R is N*Tmp.
need N>1 to terminate the recursion
more elegant with cut
factorial(1,1) :- !.
factorial(N,R) :- N1 is N-1, factorial(N1,Tmp), R is N*Tmp.
Hanoi rings puzzle
hanoi(N) :- move(N,left,center,right).
move(0,_,_,_) :- !.
move(N,A,B,C) :- M is N-1, move(M,A,C,B), print(‘move a disc from ‘, A, ‘ to ‘, B), nl, move(M,C,B,A).
recursion is often used with lists
printlist([H|T]) :- print(H),printlist(T).
parent(X,Y) :- child(Y,X).
child(A,B) :- parent(B,A).
left recursion (fix by reversing order in rule)
person(X) :- person(Y), parent(Y,X).
some particularly useful recursions
Wumpus world in Prolog (agent part, need simulator also)
- defined as repeat :- repeat.
- e.g. get0(C) :- repeat, get(X), X>32, !.
can_enter(X,Y) :- not_wumpus(X,Y), not_pit(X,Y).
not_wumpus(X,Y) :- not(stench(X1,Y1)), adjacent(X,Y,X1,Y1). and same for not_pit
adjacent(X,Y,X1,Y1) :- X1is X-1, Y1 is Y.
adjacent(X,Y,X1,Y1) :- X1 is X+1, Y1 is Y. etc.
pickup_gold(X,Y) :- glitter(X,Y).
climb_out(X,Y) :- X=1, Y=1, have_gold.
forward(X,Y) :- angle=0, X is X=1, update(X,Y). update is simulator function