Exercise Set 5

1. Why is it usually important to use cuts in logic programs?
   1. Because it makes the logic of programs easier to understand.
   2. Because it greatly reduces the memory utilization.
   3. Because cuts tend to make predicates run in many modes.
   4. Because cuts are necessary to achieve backtracking.

2. Unification is a form of pattern matching. Which of the following is {\it not\/} a characteristic of unification?
   1. Unification involves backtracking; if one branch does not succeed, the unification algorithm tries another branch.
   2. Unification is permanent; once a unification is done, it cannot be undone by a later unification.
   3. Unification is symmetric; unifying A with B has exactly the same effect as unifying B with A.
   4. Unification is active; it can modify the data structures that are involved in the unification, making later unifications impossible.

3. In Prolog, predicates can run in many modes. What does that mean?
   1. A predicate can have more than one meaning.
   2. A predicate can perform cuts, which limit the size of search trees.
   3. A predicate can employ backtracking, which allows it to search for many different solutions.
   4. A predicate can treat different parameters as inputs or outputs, depending on the context in which it is used.

4. Prolog data structures can contain variables. A variable in a data structure represents
   1. a lazy part of a structure, which is computed when needed by a predicates stored with the variable.
   2. a box whose contents can be changed over time, and that can take on many different values during the course of a single successful branch of a computation.
   3. an unknown part of a structure, which will be typically be filled in later when more information is obtained.
   4. a part of the structure that will never be known, and will always represent all possible data structures.

5. In a Prolog goal (or query), unbound variables are
   1. implicitly existentially quantified, with the system asked to find their values.
   2. implicitly universally quantified, with the system asked to prove the goal for all values of the variables.
   3. not allowed.
   4. allowed only if the programmer has declared them.

6. In Prolog, it is not possible to write a function that performs computation. All computation is performed by predicates. In general, how can computation of a function be simulated, using a predicate?

7. Show the Prolog search tree for goal (X = [1,2], member(a,X)). Note that a is a constant, not a variable. The definition of the member predicate is as follows. Notation [A|B] is Prolog's way of writing A::B. :- is Prolog's way of writing <=.

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

8. Show the Prolog search tree for goal append([1,2], X, [1,2,5,4]), using the following definition of append.

         append([], X, X).
         append(H::T, X, H::Y) :- append(T, X, Y).
     

9. Suppose that you know a list Y. Using only the append predicate, write a goal that is satisfied just when list Y has the form X ++ X, for some list X. (Here, ++ means concatenation of lists.) For example, if Y = [2,4,5,2,4,5], the goal would succeed, but if Y = [2,4,3,4,6], the goal would fail.

10. Suppose that you have a value N and a list X. Using only the append predicate and notation [A|B] for the list A::B, write a goal that is true just when N is a member of list X.

11. The Scheme function assoc can be mimicked by a predicate in Prolog. Write a Prolog definition of predicate assoc such that assoc(K,V,X) is true if X is a list of the form [...,(K,V),...]. For example, assoc(4, 7, [(3,6),(4,7),(9,2)]) is true, but assoc(4, 7, [(3,6),(4,8),(9,2)]) is false. You assoc predicate should be capable of running in a mode where it tells the value of V, given the values of K and X.