Computer Science 3675
Summer 2002
Solutions to practice questions for quiz 5

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

   4. Negation (the not predicate) in Prolog is mathematically correct negation, and goal not(X = 5) binds variable X to some value that is not equal to 5. F

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. Are backtracking and exception handling the same thing? For example, can you use the exception handling mechanism of Java to do backtracking?

   No, they are not the same, and exception handling cannot be used as a substitute for backtracking. A backtracking control frame remains active even after the function that created it has returned. An exception-handling control frame is removed when the context that created the frame is exited.

4. What is one important motivation for including exception handling in a programming language?

   Some acceptable answers include the following.

   1. Exception handling makes it possible to move error handling code out of the flow of the main program logic.
   2. Exception handling makes recovery from errors easier, thus making programmers more likely to put in the effort to do it.
   3. Exception handling makes it possible to recover from errors in parts of the program that do not perform any error checking, and might be written in an unreliable way.

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

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

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