CSE 505 - Autumn 2001 - Assignment 1

1. Use the unify algorithm to determine whether each of the following constraints is satisfiable.
   1. X=Y
   2. cons(1,A)=cons(B,cons(2,nil))
   3. point(X,10)=point(Y,Y)
   4. point(5,10)=point(Y,Y)
   5. f(X)=X
2. Try each of the constraints from Question 1 as a goal in CLP(R), and check whether the answer from the system is the same as yours. Is it? You will get strange behavior for one of the cases, because CLP(R) doesn't implement the occurs check. Try executing "unify" by hand for the bad case, but omitting the occurs check. What happens?
3. Try each of these constraints as a goal in CLP(R). What happens?
   1. X=Y+3, 2*X=3*Y+8
   2. X<=10, X>20
   3. X<=10, X<=20
   4. X*X=2
4. Write rules defining a predicate abs(A,B) that holds if B is the absolute value of A. Demonstrate your absolute value rule with the following goals:

     ?- abs(-2,Y).
     ?- abs(Y,5). 
     ?- abs(Y,-5).  
     ?- abs(Y,5), Y<0.
     ?- abs(Y,Y).
   

   If there are multiple solutions have CLP(R) find them all.
5. The following program computes the sum of the numbers from 0 to N.

     sum(0,0).
     sum(N,S+N) :- N>0, sum(N-1,S).
   

   Give the derivation tree and simplified derivation tree for the goal sum(2,A).

   What would happen if we changed the program to the following?

     sum(0,0).
     sum(N,S+N) :- sum(N-1,S).