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

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

• in order to get the result only once ...

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

• the cut is like a fence
• 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
• use of !, fail.

       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
• go :- sum(1,X), foo(Y).
• and foo(Y) fails, PROLOG will try to reinstantiate sum(1,X).
• can replace cut with use of not( ) predicate
• sum(1,1). sum(N,R) :- not(N=<1), N1 is N-1, sum(N1,R), R is R+N.
• PROLOG lists
• 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).
    

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

• meaningless for uninstantiated variable
• 1) use var predicate
• 2) use weaker test, e.g. is_list([]). is_list([_,_]). (but some non-lists will pass)
• member
• 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

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

• append can often be used instead
• last(L,List) := append(_,[L],List).
• member(M,List) :- append(_,[M|_], List).
• recursion
• 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.
   

• 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([]).
    printlist([H|T]) :- print(H),printlist(T).
  

• bad recursions
• infinite recursion

       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).  
        person(adam).  
   

• some particularly useful recursions
• repeat
• defined as repeat :- repeat.
• e.g. get0(C) :- repeat, get(X), X>32, !.
• Wumpus world in Prolog (agent part, need simulator also)

   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
 

---