- the cut
- succeeds immediately but is never resatisfied
- as side effect - commits to all before it
- so cut stops backtracking
- genesis family example

father(abraham,ishmael). father(abraham,isaac). is_father(X) :- father(X,_). ?-is_father(X). abraham ; abraham

father(abraham,ishmael). father(abraham,isaac). is_father :- father(X,_), !. ?-is_father(X). abraham

- 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.

average_taxpayer(X) :- non_citizen(X), !, fail. average_taxpayer(X) :- income<100000.

sum(1,1) :- !. sum(N,R) :- N1 is N-1, sum(N1,R), R is R+N.

- 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
- examples:
- [ ] 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
- ?- 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([]). is_list( [A | B] ) :- is_list(B).

- 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:
- member(X, [X | _ ]).
- this is better than defining
- member(X, [Y | _ ] :- X=Y.
- member(X, [_ | Y]) :- member(X,Y).

last(X,[X]). last(X,[_|Y) :- last(X,Y).

- 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(1,1). factorial(N,R) :- N>1, N1 is N-1, factorial(N1,Tmp), R is N*Tmp.

factorial(1,1) :- !. factorial(N,R) :- N1 is N-1, factorial(N1,Tmp), R is N*Tmp.

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).

printlist([]). printlist([H|T]) :- print(H),printlist(T).

- infinite recursion

parent(X,Y) :- child(Y,X). child(A,B) :- parent(B,A).

person(X) :- person(Y), parent(Y,X). person(adam).

- repeat
- 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_pitadjacent(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