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

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

  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)

  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)

  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.