Assignment 3. Due January 24.


Total points: 40
----------------------------------------------------------

1. (4 points)

Let insert(Number, List1, List2) be a ternary predicate that succeeds if and 
only if its third argument, a sorted list of numbers 'List2' is obtained from 
its second argument, also a sorted list of numbers 'List1', by inserting 'Number' 
in the proper place. (The lists are sorted in ascending order.) 
   
Assume it is implemented as follows:

   insert(X, [H|T1], [H|T2]) :- 
       X>H, 
       !, 
       insert(X, T1, T2).
   insert(X, L, [X|L]).

a. Provide an appropriate query to show that this program is incorrect with
   respect to the given specification.
b. Change the program so that it works correctly.
 
======================

2. (4 points)

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

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

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

(d) Which of the following terms is more general than the others? 
      f(g(x),g(y)), f(g(x),y), f(g(y),x), f(g(x),g(x))

    Justify your answer by showing the corresponding substitutions.
    
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.

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

3. (4 points)

Sketch the steps of the unification algorithm discussed in the class on the pairs 
of terms below:

   a) f(a,x,g(y)) and f(z,y,x)
   b) f(x,y,z,w) and f(f(u,u),f(x,x),f(y,y),f(z,z))

Here f,g,a,b,c,d are function symbols, x,y,z,u,w are variables.

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

4. (6 points)

Implement the predicate occurs(Var, Term) that succeeds if the Prolog variable Var 
occurs in the Prolog term Term, and fails otherwise.

Hint 1. You can use var(term) to check whether term is a Prolog variable.  
Hint 2. You can use var1 == var2 to check whether 'var1' and 'var2' are identical.

Sample runs:
  ?- occurs(X, f(X)).
  true.

  ?- occurs(X, f(Y)).
  false.

  ?- occurs(X, f(a,g(b,h(X,c),d))).
  true.

  ?- occurs(X, X).
  true.

  ?- occurs(x, f(x)).
  false.

  ?- occurs(x, x).
  false.

  ?- occurs(x, f(X)).
  false.
  
==========================

5. (6 points)

Generate all triples (X,Y,Z) that satisfy the conditions that all three 
components are different integers between 0 and 9 (both included), and that 
(10*X+Y)/(10*Y+Z) equals X/Z.

The output of your program should be to the screen, and be in
the form:

    3 5 9 	
    3 1 6

if (3, 5, 9) and (3, 1, 6) happen to be the solutions.

(Usage of the 'findall' predicate is permitted.)

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

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

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

7. (4 points)

Define a predicate divisors(number, list) which suceeds of 'list' is the list of
the divisors of the natural number 'number'. If 'number' is not a natural number,
the program should print an error message and fail.

Sample runs:

?- divisors(1, Divisors).
Divisors = [1].

?- divisors(2, Divisors).
Divisors = [1, 2].

?- divisors(3, Divisors).
Divisors = [1, 3].

?- divisors(4, Divisors).
Divisors = [1, 2, 4].

?- divisors(9, Divisors).
Divisors = [1, 3, 9].

?- divisors(12, Divisors).
Divisors = [1, 2, 3, 4, 6, 12].

?- divisors(100, Divisors).
Divisors = [1, 2, 4, 5, 10, 20, 25, 50, 100].

?- divisors(101, Divisors).
Divisors = [1, 101].

?- divisors(10.1, Divisors).
10.1 is not a positive integer. 
false.

?- divisors(-101, Divisors).
-101 is not a positive integer. 
false.

?- 
?- divisors(30, X).
X = [1, 2, 3, 5, 6, 10, 15, 30]
Yes

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

8. (4 points)

  (a) Write a DCG that generates the language consisting of all the strings of
      length 5 built from the letters a, b, and c. Write also the Prolog program 
      that corresponds to this DCG.

  (b) Write a DCG that generates the language consisting of all the strings of 
      the form a^nb^n, n>0, i.e., the language consisting of the string 
      ab, aabb, aaabbb, aaaabbbb,.... Write also the Prolog program that 
      corresponds to this DCG.

  (c) Let a^n b^2n, n>=0 be the formal language which contains all strings of the 
      following form: the empty string, abb, aabbbb, aaabbbbbb, ... Write a DCG 
      that generates this language. Write also the Prolog program that 
      corresponds to this DCG.
      
  (d) Write a DCG that defines a parametrised nonterminal star(X) such that,
      for any atom a, star(a) accepts the regular language a∗. Write also the 
      Prolog program that corresponds to this DCG.