CSE 341 -- Assignment 7 -- Prolog Warmup

November 6, 1995
Due in quiz sections November 21, 1995

  1. Define the append relation as shown in the lecture notes. Now try append on the following. In each case reject the answers to see what happens when Prolog backtracks.
     ?- append([a,b,c],[w,x,y,z],L).
     ?- append([a,b],Y,[a,b,c,d]).
     ?- append([a,c],Y,[a,b,c,d]).
     ?- append(X,Y,[a,b,c,d]).
     ?- append(X,Y,Z).
    
    You don't have to hand in anything for this question.

  2. Extend the "likes" program shown in the lecture notes with some additional facts about liking things. You should include at least two additional facts and one additional rule. This program is also available on ~borning/341/likes.pl on mscc.ms. Demonstrate your rules operating correctly. (You get to decide what kinds of facts or rules you put in. )

    /* What you like should go here */
    

  3. Write and test a set of Prolog rules that define the next_color relation. (This is just a Prolog version of the Lisp function you wrote for Question 5 in Assignment 1.) The next_color relation has two arguments -- it should succeed if both arguments are atoms representing stoplight colors, and if the second argument is the color that follows the first argument. Otherwise it should fail. Examples:

    next_color(green,N) should succeed with N=yellow next_color(yellow,N) should succeed with N=red next_color(red,N) should succeed with N=green next_color(purple,N) should fail next_color(A,B), next_color(B,red) should succeed with A=green, B=yellow next_color(A,yellow) should succeed with A=green In each case try backtracking and see if there are any more answers. (There shouldn't be.) Finally, try the following goal and see which answers are produced by backtracking: next_color(A,B).

    next_color(green,yellow).
    next_color(yellow,red).
    next_color(red,green).
    

  4. Write a twice rule that takes two arguments. (This is also a Prolog version of a previous Lisp question.) A call to twice succeeds if both arguments are lists of the same length. Each element in the second list should itself be a list of length two, with the original element repeated. Examples: twice([x,y,z],S) succeeds with S=[[x,x],[y,y],[z,z]] twice([fred],S) succeeds with S=[[fred,fred]] twice([],S) succeeds with S=[] twice([A],S) succeeds with S=[[A,A]] twice(A,[[2,2],[10,10]]) succeeds with A=[2,10] twice(A,[[2,3],[10,10]]) fails (Note that A is still a variable in the result for twice([A],S).) Again, try backtracking in each case and see if there are more answers. Then try the following goal and see what is produced upon backtracking: twice(A,B)

    twice([],[]).
    twice([X|Xs],[[X,X]|Ys]) :- 
      twice(Xs,Ys).
    

  5. Write a variation of twice, called flat_twice, that succeeds if the second list is twice as long as the first, with each element of the first list repeated. Examples: flat_twice([x,y,z],S) succeeds with S=[x,x,y,y,z,z] flat_twice([],S) succeeds with S=[] flat_twice([1,X],[A,B,C,100]) succeeds with A=B=1, C=X=100 flat_twice(S,[1,2,3,4]) fails As usual, try backtracking in each case and see if there are more answers. Then try the following goal and see what is produced upon backtracking: flat_twice(A,B)

    flat_twice([],[]).
    flat_twice([X|Xs],[X,X|Ys]) :- 
      flat_twice(Xs,Ys).
    

  6. The file ~borning/341/deriv.pl contains the ever-popular symbolic differentiation program, this time in Prolog. The goal go1(X) will try the first example, and similarly for go2(X) and so forth.

    The simplification rules contain a number of cuts (the "!" symbol). Why are these there? Try backtracking on the goals with the program as given. Now remove the cuts and try backtracking again. Explain the resulting behavior.

    With the cuts, the program produces the correct answers, and if one tries to backtrack on any of the sample goals, it fails. Without the cuts, the first answers returned will be the same as for the original program. However, one can backtrack and get alternate answers. These alternate answers will still be correct but won't be in the simplest form. (For example, for go1(N), one gets N=1+0 in addition to the correct answer of N=1.)

    The reason for this is that in the rules for plus_simplify and times_simplify, there are a series of simplifications -- for example, for adding 0 to anything -- and after these there is a catch-all rule that doesn't simplify at all. With the cuts, the catchall rule is encountered only if none of the previous simplications can be performed -- otherwise the cuts remove this rule as a possibility. Without the cuts, the catchall rule will be encountered on backtracking, and answers not in the simplest form may be returned.