Computer Science 3675
Summer 2003
Solutions to practice questions for quiz 4

1. True or false.

   1. When a variable occurs in a logic programming goal, the interpreter is being asked whether that goal holds for all values of the variable. F

   2. In logic programming, a variable in an axiom might be used as an input variable sometimes, and as an output variable at other times, when computation uses that axiom. T

   3. Cuts are used to reduce memory requirements and to speed up computation. T

2. Unification is a form of pattern matching. Which of the following is not a characteristic of unification?

   1. Unification never changes the binding of a bound variable.
   2. Unification is symmetric; unifying A with B has exactly the same effect as unifying B with A.
   3. Unification is very slow, and is only used rarely during computations of logic programs.
   4. Unification can bind unbound variables.

3. In a logic programming style, write axioms for computing predicate samelength(X,Y), which is true just when X and Y are lists that have the same length.

        samelength([],[]).
        samelength([A|B], [C|D]) :- samelength(B,D).
     

4. In a logic programming style, write axioms for computing predicate allsame(X), which is true just when all members of list X are the same. For example, allsame([5,5,5]) is true, as is allsame([a,a]), but allsame([2,4,4]) is false. Note that allsame([]) is true, and allsame([b]) is true.

     allsame([]).
     allsame([X]).
     allsame([X,X|Z]) :- allsame([X|Z])
   

5. Show the logic programming search tree for goal (member(X,[3,4,5]), member(X,[4])), up to the point where a success is found. The definition of the member predicate is as follows, written in Prolog syntax.

         member(M, [M|X]).
         member(M, [X|T]) :- member(M, T).
     

                member(X,[3,4,5]), member(X,[4])
               /                               \
               | X = 3                      member(X,[4,5]), member(X,[4])
               |                           /                              \
           member(3,[4])                   | X = 4
          /             \                  |
        fail      member(3,[])             |
                 /            \            |
               fail          fail     member(4,[4])
                                     /             \
                                  success
   

6. Using backtracking, write an Astarte program fragment that will print all solutions (x,y) to equation xy - 2x² + y = 10, where x and y are both integers in the range 0,...,100. Do not use a loop or recursion. Your program fragment can fail when it is done.

       Let x = each(0 _upto_ 100).
       Let y = each(0 _upto_ 100).
       {x*y - 2*x^2 + y == 10}
       Writeln[$(x,y)].
       {false}