Tutorial notes for week 9

Introductory Prolog problems, including list manipulation and arithmetic
operations.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1. List Manipulation

a. A predicate to compute the third element of a list (fails if the list
has less elements).

?- third([a,b,c,d],X).
X = c 
yes

?- third([a,b],X).
No

Solution:
  third([_,_,X|_],X).


b. Remove duplicate occurrences of an element

   rm-dups(L1,L2) -- L2 is the same as L1 with the second and
      succeeding immediately adjacent duplicates removed.

   For example:

?- rm-dups([a,b,a,a,a,c,c],[a,b,a,c]).
Yes
?- rm-dups([a,b,a,a,a,c,c],X).
X = [a, b, a, c] ;
No
?- rm-dups([a,b,a,a,a,c,c],[a,b,c]).
No

Solution:   Pre-req: L1 is fully instantiated, L1 and L2 are lists.
 
   rm-dups([],[]).
   rm-dups([X],[X]).
   rm-dups([X,X|Rest],Rest2) :- rm-dups([X|Rest],Rest2).
   rm-dups([X,Y|Rest],[X|Rest2]) :- X \= Y, rm-dups([Y|Rest],Rest2).

Note: If we don't add X\=Y to the last clause, we get the correct
solution, but when we ask for more solutions we get some (and we
shouldn't).


c. Count element occurrences.

    count(L,E,N) holds if the list L contains E N times.
    Precondition: L and E are instantiated. L is a non-nested list.

?- count([1,2,1,1],1,3).
Yes
?- count([1,2,1,1],1,N).
N = 3 ;
No~
?- count([1,2,1,1],1,2).
No
?- count([1,2,[1,2],1],[1,2],N).
N = 1 ;
No

    Solution:
    count([],_,0).
    count([E|Rest],E,N) :- count(Rest,E,N1), N is N1 + 1.
    count([X|Rest],E,N) :- X \= E, count(Rest, E, N).

Note: that N1 has to be instantiated when we compute N.
      X\=E means X does not unify with E.


d.  Count element occurrences.
    countAll(L,E,N) holds if the list L contains E N times on any level.
    Precondition: L and E are instantiated. L is a possibly nested list.

?- countAll([1,2,1,[2,[1]],3],1,N).
N = 3 ;
No
?- countAll([1,2,1,[2,[1]],3],1,3).
Yes
?- countAll([1,2,1,[2,[1]],3],1,2).
No

countAll([],_,0).
countAll([E|Rest],E,N) :- countAll(Rest,E,N1), N is N1 + 1.
countAll([X|Rest],E,N) :- X \= E, is_list(X),
                          countAll(X, E, N1),
                          countAll(Rest, E, N2), N is N1+N2.
countAll([X|Rest],E,N) :- X \= E, not(is_list(X)), countAll(Rest, E, N).

Note: is_list holds if the argument is a list.
      The predicate works if we skip X \= E and not(is_list(X)). We get
the first solution ok. But when we ask for more solutions, we get some
more, and we shouldn't. 


3. Debugging in Prolog.
------------------------

Highlights of tracing:  trace and spy points. 

Here are a few specifics:

Traces: those let you see every call one by one.
    Turning trace on:
        trace.
    Turning trace off:
        notrace.
    Note: in SWI Prolog, the trace stays on only for the next predicate
you run.

Spy point: those let you enter trace mode when a particular predicate is
called.
    Adding a spy point for predicate pred with arity n (i.e., pred takes n
    arguments):
        spy(pred/n).
    Adding a spy point for predicate pred, tracing every instance of the
    predicate, regardless of arity:
        spy(pred).
    Removing a spy point:
        nospy(pred/n).
        nospy(pred).

Useful commands while in trace mode:
    <enter>: move one step forward
    l: leap causes the program to resume (i.e., to leave trace mode) until
       the next spy point, or until the program is done.
    s: skip the current subprogram:  the current subprogram is executed
       with trace off, and the trace resumes when that subprogram is done.
       Useful to quickly go through long subprograms that you've already
       debugged and you don't need to go through the details.

Note that the behaviour of these commands may not be intuitively obvious
when you work with them, so you should first get accustomed to them with
simple programs.

Dealing with misbehaving code:
    If your code gets into infinite recursion, you can hit Ctrl-C to stop
    it.  The interpreter will put you in break mode, which you can leave
    by typing "a" (from "abort"). 



3. Trip Planning (if time allows).

Define a new kind of database to deal with "trips".

plane(to, ny).
plane(ny, london).
plane(london, bombay).
plane(london, oslo).
plane(bombay, katmandu).
boat(oslo, stockholm).
boat(stockholm, bombay).
boat(bombay, maldives).
...

Develop the following predicates.

a) cruise(X,Y) -- there is a possible boat journey from X to Y.

b) trip(X,Y) -- there is a possible journey (using plane or boat)
     from X to Y.

Note: In developing trip, get them to see that it's a good idea to have
    a "helper" predicate, call it "leg" for leg of a journey, that is
    true for either mode of transport (see the solution below).
    Note that an advantage of using "leg" is that it makes it easier
    to extend the knowledge base to have other modes of transport.

c) stopover(X,Y,S) -- there is a trip from X to Y with a stop in S.
   Assume that neither X nor Y can equal S. 

d) plane_cruise(X,Y) -- there is a trip from X to Y that has at least
     one plane leg, and at least one boat leg.
Note: "leg" will come in handy here.