ASSIGNMENT 3. Due January 17.
=============================

Total points: 40
  
==============================================================

1. 4 points.

(a) Compute E\theta, where E=f(x, g(a,y), g(a,z)) and 
    \theta= {x -> y, y -> g(a,z), z -> x\}.

(b) Compute \theta\sigma, where \theta={x -> f(x,x), y -> z, z -> g(y,x)} and 
    \sigma= {x -> y, z -> y,  y -> g(y,y), u -> a}.

(c) Compute \theta\theta, where \theta={x -> f(x,x), y -> z, z -> g(y,x)}.

(d) Which of the following statements are true?
      d1: f(g(x),g(y)) is more general than f(g(x),g(x)).  
      d2: f(g(x),y) is more general than f(g(y),x).
      d3: f(g(y),x) is more general than f(g(x),y).
      d4: f(g(x),g(x)) is more general than f(g(x),g(y)).

    Justify your positive answers by showing the corresponding substitutions.

    (x,y,z,u are variables.)
    
REMARK. A term t is more general than a term s if s is an instance of t, i.e.,
if there is a substitution \theta such that t\theta = s.

==============================================================================

2. 6 points.

   Implement a ternary predicate flatten_term(Term, Function_symbol, Flattened_term)
   that succeeds if Flattened_term is obtained from Term by flattening out all
   nested occurrences of Function_symbol. It is assumed that Term contains no 
   Prolog variables and no lists (you don't have to check this).

   (You may want to use the univ predicate =.. to represent a term as a list.)

   Sample runs:

   ?- flatten_term(f(f(x)), f, Flattened_term).
   Flattened_term = f(x).

   ?- flatten_term(f(x), f, Flattened_term).
   Flattened_term = f(x).

   ?- flatten_term(a, f, Flattened_term).
   Flattened_term = a.

   ?- flatten_term(g(f(x)), f, Flattened_term).
   Flattened_term = g(f(x)).

   ?- flatten_term(g(f(f(x))), f, Flattened_term).
   Flattened_term = g(f(x)).

   ?- flatten_term(f(g(f(x))), f, Flattened_term).
   Flattened_term = f(g(f(x))).

   ?- flatten_term(f(f(f,g(f(y)))), f, Flattened_term).
   Flattened_term = f(g(f(y))).

===========================================================================

3. 4 points.

   Implement mergesort using the merge predicate defined
   in the previous assignment.

===========================================================================

4.  4 points.

    Write a predicate list_less(L1, L2) that is true if the list
    L1 is less than the list L2 with respect to the ordering
    defined below:

    list_less(L1, L2) iff
     Let L1' := complement(L1,L2), L2' := complement(L2,L1)
      (complement(L1,L2) contains those elements of L1
       that are not in L2)
     Let m1 := max(L1'), m2 := max(L2')
      (max(L) gives the maximal element of L with respect to
       the standard order @<)
     m1 @< m2.

   The behavior of the program on the sample queries should be the following:

   ?- list_less([3,4],[3,3,4,0]).
   true.

   ?- list_less([3,2,2,1,1,1,4,0],[3,3,4,0]).
   true.

   ?- list_less([3,3,3,3,2,2],[3,3,4,0]).
   true.

   ?- list_less([a,b,X,Y,[X|Y],2], [[X,X|Y]]).
   true.

   ?- list_less([a,b,X,Y,[X|Y],2], [X,b,b]).
   false.

===========================================================================

5. 3 points.

   Is the predicate p defined below tail recursive? Justify your answer.

   p([H|T]):-
       q,
       p(T).
   p([]).
   q.

===========================================================================

6. 5 points.

   Write a ternary predicate delete_nth(List_In, N, List_Out) that succeeds if
   'List_Out' is obtained from 'List_In' by deleting every N'th element.

   Sample runs:

   ?- delete_nth([a,b,c,d,e,f], 2, L).
   L = [a, c, e].

   ?- delete_nth([a,b,c,d,e,f], 1, L).
   L = [].

   ?- delete_nth([a,b,c,d,e,f], 0, L).
   false.

   ?- delete_nth([a,b,c,d,e,f], 10, L).
   L = [a, b, c, d, e, f].

   ?- delete_nth([a,b,c,d,e,f], 3, L).
   L = [a, b, d, e].

   ?- delete_nth([a,b,c,d,e,f], -1, L).
   false.

   ?- delete_nth([a,b,c,d,e,f], 1.5, L).
   false.

   ?- delete_nth([], 0, L).
   false.

   ?- delete_nth([], 1, L).
   L = [].

   ?- delete_nth([], 10, L).
   L = [].

===========================================================================

7. 6 points

  Write a predicate matrix_multiplication(M1, M2, M3), which is true if

  - M1, M2, and M3 are matrices, each represented as a list of lists (matrix rows), and
  - M3 = M1 * M2, where * stands for matrix multiplication.

Sample runs:
  
?- matrix_multiplication([[1,2],[3,4]], [[5,6],[7,8]], M).
M = [[19, 22], [43, 50]].

?- matrix_multiplication([[1,2],[3,4], [1,1]], [[5,6],[7,8]], M).
M = [[19, 22], [43, 50], [12, 14]].

?- matrix_multiplication([[1,2,1],[3,4,1]], [[5,6],[7,8]], M).
false.

?- matrix_multiplication([[1,0,0],[0,1,0],[0,0,1]], [[1,2,3],[4,5,6],[7,8,9]], M).
M = [[1, 2, 3], [4, 5, 6], [7, 8, 9]].

?- matrix_multiplication([[1,0,0],[0,1,0]], [[1,2,3],[4,5,6],[7,8,9]], M).
M = [[1, 2, 3], [4, 5, 6]].

===========================================================================

8. 8 points.

Implement the predicate unify(term1, term2, mgu) that succeeds if 'mgu' is a 
most general unifier of 'term1' and 'term2'. Use the algorithm discussed 
in the class.

Requirements:
   
   - term1 and term2 do not contain Prolog variables. If they do, your program 
     should print:
        Error: The input terms should not contain Prolog variables.
     and fail.
     (You can use var(term) to decide whether 'term' is a Prolog variable.)
     
   - The variables in term1 and term2 are Prolog atoms that start with x, y, or z. 
     (You can use the built-in atom_chars predicate to decide whether an atom 
     starts with x, y, or z)
      
   - mgu is a list of the form [v1 --> t1, ... , vn --> tn] where v1, ..., vn 
     are variables that occur in term1 or term2 and t1, ..., tn are terms. 
     Use the 'op' declaration to be able to write --> as an infix operator. 
     (Consult Section 5.5, Declaring Operators, from the book or the system
     manual for explanations how to declare operators in the program.)

Sample runs (the order of elements in the output Mgu list does not matter):

   ?- unify(f(x,g(a)), f(b,g(y)), Mgu).
   Mgu = [y --> a, x --> b].

   ?- unify(f(X,g(a)), f(b,g(y)), Mgu).
   Error: The input terms should not contain Prolog variables.
   false.

   ?- unify(f(x,g(a)), f(b,g(x)), Mgu).
   false.

   ?- unify(f(x), f(g(x)), Mgu).
   false.

   ?- unify(f(x), g(a), Mgu).
   false.

   ?- unify(f(x,x), f(y,g(y)), Mgu).
   false.

   ?- unify(f(x,x), f(y,g(z)), Mgu).
   Mgu = [y --> g(z)), x --> g(z))].

   ?- unify(f(x1,x2,x3,g(y0,y0),g(y1,y1),g(y2,y2),y3), f(g(x0,x0),g(x1,x1),g(x2,x2),y1,y2,y3,x3), Mgu).
   Mgu = [y0 --> x0, y2 --> g(g(x0, x0), g(x0, x0)), x3 --> g(g(g(x0, x0), g(x0, x0)), g(g(x0, x0), g(x0, x0)))), x1 --> g(x0, x0), x2 --> g(g(x0, x0), g(x0, x0)), y1 --> g(x0, x0), y3 --> g(g(g(x0, x0), g(x0, x0)), g(g(x0, x0), g(x0, x0)))].

===========================================================================