Prepare chapter 2, namely sections 2.1 till 2.5
 

        Question 1:
            Indicate all the Prolog terms in the following lines of Prolog code:

             move(state(P, onfloor, P, H), climb, state(P, onbox, 3.5, H)).
             move(state(P, <--->, P, H),' onbox ',final).
             haschild(barry) :- parent(barry, small('Caroline')).
 

       Question 2:
            2a) What is the role of the syntax in the context of programming languages?
            2b) Can a Prolog sentence be ambiguous?

       Question 3:
            Did you have a previous course using GIL (Guided Independent Learning)? What were your experiences?
         
            or Do you understand the concept of GIL? More questions?

Week 2 (for  14/10/2011)

        Prepare chapter 2, namely sections 2.6 and 2.7
                chapter 3, namely sections 3.1 upto 3.2.2  (lists in Prolog) 

        Question 1:
            Consider again the family database of figure 1.8 and the following clauses for predecessor/2.
            (Note the position of the parent/2 goal in the recursive clause!!)

            (1)   predecessor(X,Y) :- parent(X,Y).
            (2)   predecessor(X,Y) :- predecessor(Z,Y), parent(X,Z).

            (3)   parent(pam,bob).
            (4)   parent(tom,bob).
            (5)   parent(tom,liz).
            (6)   parent(bob,ann).
            (7)   parent(bob,pat).
            (8)   parent(pat,jim).

            Note that you can use the numbers between () in the execution trace to refer to the clauses.
 

            a) Give the execution trace for
                     ?- predecessor(P,bob).

            b) Why do you need renaming?
                 Suppose you do not rename the clauses.  Would queries have the same answers? or more? or less?
 

Week 3 (for  21/10/2011)
 

         Prepare  the remaining part of chapter 3
                                more lists, operators and arithmetic
 

        Question 1:
                Given the defintion of conc/3 on page 65, indicate whether the following queries succeed (and give the bindings of the variables)
                or fail (explain why).

                a)  ?- conc( [X], [1,2,3],L).
                                 Is this the appropriate way to add an element to the beginning of a list???
                                 (do you know a more straightforward way???)
                b)  ?- conc( [1,2,3],  [X], L).
                                 Is L the same list as K in the query ?-   K = [  1,2,3 | X ].
                c)  ?- conc(L1,L2,[a,b,c]).
                      (Give all the possible answers!!!) 

        Question 2:
                Consider the following queries. 
                Indicate whether they succeed (and give the bindings of the variables)
                                or fail (explain why).

Week 4 (for  28/10/2011)
 

         Prepare  sections 4.1 till 4.4.
                  sections 5.1 and 5.2.
                  (Note that the remaining parts of these sections will be studied later).

         Question 1:
                   A. Consider the total/2 predicate (p.91) and the patterns in the slides about recursion.
                   Does total/2 fit into a pattern?  Explain why (not).

                   B. Extend the predecessor predicate so that it actually gives the list of predecessors when it succeeds.

         Question 2:
                  a) Consider the flight route planner of Figure 4.5.  Note that / is a predefined operator that
                     is used in a non-arithmetic context.  What is its role?

                  b) As this flight route program has to search for a solution, it will have a number of
                     backtrack points. 
                     Indicate where they are : give the calls in the program where backtracking occurs.

                  c) This program contains an example of a selector (as defined on p.93): where is it?

                  d) Would it make sense to add cuts to the timetable/3 predicate?
                     or to the member/2 predicate?
                     Explain your answer.

         Question 3:
                  a) Write the predicate reverse(L,R) which is true if the list R is the reversal of list L .

                  b) How many calls (to Prolog predicates) do you have to execute for reversing a list of N elements?
                       (In other words on p. 45 Figure 2.11 how many times will you call match(Goal,H',MatchOk, Instant)? )

         Question 4:
                   Consider the following clauses for length:

                         length([],0).
                         length([X], 1).
                         length( [H | T] , L) :-
                                            length(T,L1),
                                            L is L1 +1 .

                     a) What is wrong with this predicate??? 

                     b) Now, change the second clause into 
                                  length([X],1) :- !.

Week 5 (for  4/11/2011)
 

         We have some pending ones from Week 4 (see later)
 

          Prepare  section 4.5 ( The eight queens problem)
          Prepare sections 5.3 (Negation as failure)  and  5.4 (Problems with cut and negation)

          Question 5.1:
                   The program in Figure 4.7 ( Program 1 for 8-queens) gives a generate and test solution for the queens problem.

                   1a) Which call in the program is doing the generate? and which the test?

                   1b) What are the arguments of noattack(X/Y, Others) during the  execution of the query
                                                ?- template(S), solutions(S).
                           when noattack/2 is called for the first and the second time?
 

          Question 5.2:  Consider the following "yet another" version of canget/3.
                   move(s1,m1,s2).
                   move(s1,m2,s3).
                   move(s2,m3,s1).
                   move(s2,m7,s4).
                   move(s3,m4,s2).
                   move(s3,m5,s4).
                   move(s4,m6,f).

                   final(f).

                  canget(S,_,[]) :- final(S).
                  canget(S1,VisStates,[M|Rms]) :-
                          move(S1,M,S2),
                          valid(S2,VisStates),
                          canget(S2,[S2|VisStates],Rms).

                  valid(S2,VisStates) :-
                                  member(S2,VisStates), !, fail.
                  valid(_,_).
          

                (a) run the query ?- canget(s1,[s1],Mvs).
                      What are the answers for Mvs?

                (b) rewrite the recursive clause of canget/3 using negation as failure (namely \+/1 ).

          Question 5.3:
                   The "closed world assumption" is not only used in the context of negation as
                     failure.  Give one other context where it is used.

PENDING from Week 4 (for  28/10/2011)


         Question 3:
                  a) Write the predicate reverse(L,R) which is true if the list R is the reversal of list L .

                  b) How many calls (to Prolog predicates) do you have to execute for reversing a list of N elements?
                       (In other words on p. 45 Figure 2.11 how many times will you call match(Goal,H',MatchOk, Instant)? )

         Question 4:
                   Consider the following clauses for length:

                         length([],0).
                         length([X], 1).
                         length( [H | T] , L) :-
                                            length(T,L1),
                                            L is L1 +1 .

                     a) What is wrong with this predicate??? 

                     b) Now, change     the second clause into 
                                  length([X],1) :- !.

Week 6 (for 18/11/2011)

        Question 6.1
           Write the predicate nodoubles(L,R)  which succeeds if for a given list L , R is the corresponding list
           which contains all the elements of L but no doubles (any more).
           You may assume that you have to construct R.

           Hint: you must decide how you will detect the doubles. 
                    If you want, you can represent R by an accumulator (see last slides in recursion_patterns )!!!

        Question 6.3:
           In section 9 trees are introduced as data structures.  Do the following unifications
           succeed or fail (in case of success give the bindings of the variables).

  
      Question 7.1

               Write a predicate height(T,H) which is true if H is the height of tree T, where the
               height of a tree (or the depth of a tree) is the maximal distance of any leaf
               from the root of the tree.

Prepare section 6  Input and Output

Prepare section 8  Programming Style and Technique
                                (but not yet section 8.5.3, namely  the part related to difference lists)
                                The  "coding Guidelines for Prolog" paper mentioned on the homepage of this course contains more related information!

              
      Question 7.2
               Consider the sumlist versions presented in section 8.5.4

               Consider a predicate that for a given list of elements computes the length of a list.
               Give for this lengthlist(List,Length) predicate also the two versions, namely
               a simple version that is not tail recursive and a tail recursive version.


      Question 7.3
               Consider the quicksort predicate on p. 200.  Give a version of this predicate that does not use
               conc/3 anymore: it should use an accumulator.  (see 8.5.4  p. 187).

     Question 7.4
               a. Consider Prolog predicates that deal with ordered binary trees. Can you still apply "last call optimization"? and "accumulators"?

               b. Write a predicate sumtree(Tree,Sum) that computes the sum of all the elements in the binary tree T (assume that the tree contains integers).

Prepare sections 7.1, 7.2 and 7.5
                 sections 9.4 and 9.5

                ( at this point we actually have seen chapters 6, 7, 8 and 9 completely,
                  except for the notion of difference lists which we will study when we are dealing
                  with the grammar rules in chapter 21).
 

            Question 7.5
                    Consider Figure 7.2, in particular the definition of del_var/3.
                    a) Could we put a cut in the second clause of del_var/3?   Why (not)?
                    b) Explain why the first clause of del_var is needed?
                    c) Consider the sum1/7 predicate.  Could we change the order of the calls in
                       the recursive clause? Why (not)????

             Question 7.6

Week 8 (for  2/12/2011)    
 

       Question 8.1

                    Consider the maplist/2 builtin of SWI.  (You can consult the manual by the query ?- apropos(maplist).)
                    Example queries are :

       Optional question (for those who want to test their understanding of Prolog programs)
                    Consider the 2 programs in Fig. 9.22 and 9.23.  They find a spanning tree for a graph.
                    Can you identify the sources of inefficiency in the program of 9.23?

       Question 8.2
             Time for your questions on the material studied so far.  You can mail them to me in advance!!!
           PLEASE TAKE THIS OPPORTUNITY.

            Prepare  the following  sections of chapter 14 about Constraint Logic Programming (CLP).
                    section 14.1: a general introduction
                    section 14.2: introduction to CLP(R)

                  
            For CLP, you could use SICStus Prolog.  You should put the following directive into your file to tell SICStus
            to use the library for CLP:
                   :- use_module(library(clpr)).                       % for CLP(R)
             or
                   :- use_module(library(clpfd)).                       % for CLP(FD) from 14.5


            Note that SWI Prolog has some (partial) support for CLP(FD) too. Use the directive          :- use_module(library('clp/bounds')).

            Question 8.3:
                   Consider the sumlist versions presented in section 8.5.4:

                    sumlist([],0).
                    sumlist([First| Rest] , Sum) :-
                                sumlist(Rest,Sum0),
                                 Sum is First + Sum0 .

                   Formulate a CLP(R) version.
                   What does it answers for ?- sumlist([1,2,3], R). and ?-sumlist([X,2,Y],6).   

Week 9 (for  9/12/2011)             

 
Question 9.1:
                    Consider the following CLP(R) program.                        
                        fac(N,F) :- { N = 0, F = 1 }.
                        fac(N,F) :-
                                { 1 =< N, N1 = N - 1, F = N * F1,
                                  N =< F},                           % redundant constraint
                                fac(N1,F1).

                    Give an execution trace for the call ?- fac(K,3.0).
                    What is the role of the so-called redundant constraint N =< F???

Prepare section 14.3 and 14.4: more CLP(R).

Question 9.2:
                    Consider the scheduling program at p. 333 (Fig. 14.4) (a CLP(R) scheduling program for problems with precedence and resource constraints).
                    What is the role of the call to "fail" in the predicate  definition  for schedule/2 (where does it backtrack to???)

                    This program implements the "branch-and-bound" method (make sure you understand this method!).

Prepare section 14.5 :  CLP(FD)  with finite domains.

Question 9.3:
                    Consider the SEND+MORE = MONEY problem.
                    Give a CLP(FD) solution.

Question 9.4:
 Consider again the 5 houses puzzle (also known as the zebra puzzle). 
 We have solved it in Prolog: zebra.pl

 Solve it using CLP(FD) (see above for info about the Prolog systems).

Week 10 (for  16/12/2010) 

Question 10.1:
   Use reification to write the predicate occur_ntimes(X,L,N) which is true if the element X occurs exactly N times in the list L.

   Hint: think about reifying "X being the head of the non-empty list [H|T]" and then you have to sum the number of times "X being the head of the non-empty list [H|T]" is true.

Extra:    You can use occurs_ntimes/3 to solve the following problem.     

    A magic serie of length N is a sequence x0, x1, ..., x(N-1) such that each xi is the  number of occurences of the number  i in the serie.

   For example for N =4, there are 2 magic series 1,2,1,0   and  2,0,2,0.
   For N being equal to 1,2,3, and 6 there does not exist a magic serie.

Question 10.2:
             Have a look at the example of an earlier PLPM exam.

Prepare  
    Reconsider the section 8.5.3 about difference lists.
                              
Question 1:
     Do the following queries succeed? (if so, what are the values of the variables? )
                            a .  ?-  [H | T] = [1,2,3,5 |L].
                            b.   ?- L1 = [ 1,2 | T ], L2 = [3,4 | L1 ].
                            c.   ?- L1 = [ 1,2 | T ],  L2 = [3,4 | L1 ], T = [].
                            d.   ?- L1 = [ 1,2 | T ],  T = [3, 4 | L2 ].

   
Question 2              
     Define a predicate  flatten(List,ListofAtoms)  where List can contain lists, and lists of lists,
     and so on, and ListOfAtoms is a list containing all the atomic members, except the empty list,
     of those lists.
                 [ [ a, b], [c, d, [e, f], g], a, [i, [k] ] ]
                        flattens to [a, b, c, d, e, f, g, a, i, k]

     In case you have a version of flatten using append/3 (also known as conc/3), consider another
     version making use of difference lists.