PR2 Solution Guide:

% Total: 40 points


Ex2.1 [B]  10 points: 1 per part
(a) variable
(b) atom: a constant
(c) quoted string: an atom: a constant
(d) variable
(e) quoted string: an atom: a constant
(f) a structure (a term that is not a simple object)
(g) a number: a constant
(h) incorrect, because the principal functor of a structor must be
an atom, and 5, which is a number, is not an atom
(i) a structure; note that + is an atom
(l) incorrect, because Black( Cats)) is not a structure, since the
principal functor of a structure must be an atom, and Black,
which is a variable, is not an atom

Ex2.2 [B] 3 points: 1 per part
(a) rectangle(point(X1,Y1),point(X2,Y2),point(X3,Y3),point(X4,Y4)).
(b) square(point(X1,Y1),point(X2,Y2),point(X3,Y3),point(X4,Y4)).
(c) circle(point(X,Y),Radius).
% Constraints on points in (a) and (b) are introduced through matching

Ex2.3 [B] 5 points: 1 per part
(a) A=1 B=2
(b) fails
(c) fails
(d) E=2 D=2
(e) P1=point(-1,0) P2=point(1,0), P3=point(0,Y)  The instantiation
describes a particular class of isosceles triangles

Ex2.4 [B] 2 points
seg(point(5,X),point(5,Y)).

Ex2.5 [B] 3 points
regular(rectangle(P(X1,Y1),P(X1,Y2),P(X2,Y2),P(X1,Y2))).
% Assumes vertices are listed clockwise, starting from bottom left
 
Ex2.6 [B] 4 points: one per part
(a) A=2
(b) No
(c) C=1
(d) D=s(s(1)) ; D=s(s(s(s(s(1))))) ; etc. (adding three s each time)  

Ex2.7 [B] 1 point
relatives( X,Y) :-
  predecessor( X,Y)
  ;
  predecessor( Y,Z) 
  ;
  predecessor( Z,X), 
  predecessor( Z,Y) 
  ;
  predecessor( X,Z), 
  predecessor( Y,Z).

Ex2.8 [B] 1 point
translate( 1,one).
translate( 2,two).
translate( 3,three).

Ex2.9 [B] 5 points
Question: 
?- big(X), dark(X).

Execution trace:

(1) initial goal list: big(X), dark(X).
(2) scan the program from top to bottom looking for a clause whose head
matches the first goal, big(X).  Clause 1 found: big(bear).  This clause
has no body, so the goal list, properly instantiated, shrinks to:
dark(bear).
(3) scan the program for the goal dark(bear).  
Clause 7 found: dark(bear) :- black(bear).
Replace the first (only) goal by the instantiated body of clause 7,
obtaining a new goal list:
black(bear).
(4) scan the program for the goal black(bear).  No clause found.
Therefore, backtrack to step (3) and continue scanning below clause 7.
Clause 8 is found: dark(bear) :- brown(bear).
Replace the first (only) goal by the instantiated body of clause 8,
obtaining a new goal list:
brown(bear).
(5) scan the program for the goal brown(bear).  Find it (clause 4).
Clause 4 has no body, so the goal list shrinks to empty.  This
indicates successful termination, and the corresponding variable
instantiation is:
X = bear

Prolog does more work in the case of Figure 2.10.

Ex 2.10 [B] 6 points
SWI-Prolog responds as indicated in the text.  This is because it does not
perform the occurs check.  In detail, Prolog replaces X with f(X) in both
terms; this leads to an attempt to match f(X) with f(f(X)); Prolog
replaces X with f(X) in both terms; this leads to an attempt to match
f(X) with f(f(X)); Prolog replaces X with f(X) in both terms; this
leads to an attempt to match f(f(X)) with f(f(f(X))), and so on forever.
The composed substitution for X is X = f(f(f(....))), as indicated in
the text.  
SWI-Prolog also provides sound unification, through the predicate
unify_with_occurs_check/2.
Note that f(f(f(...))) represents a cyclic term; cyclic terms are useful
to describe recursive data structures (e.g., linked lists) in
static analysis of programs, as you may study in your compilers course.
Some Prolog authors (including the inventor of Prolog, Alain Colmerauer)
use this observation to make the case that the occurs check is not
needed; most Prolog authors disagree with Colmerauer, and view the lack
of the occurs check as a compromise dictated by efficiency considerations.

Monkey and banana exercise
The following partial trace shows that an infinite loop has been entered:
the goals canget(state(_G673,...)) and canget(state(_G681,...)) are
equal except for variable names, and success of a goal does not depend
on the names of variables.
[trace] 1 ?- canget( state( atdoor,onfloor,atwindow,hasnot)).
   Call: (6) canget(state(atdoor, onfloor, atwindow, hasnot)) ? creep
   Call: (7) move(state(atdoor, onfloor, atwindow, hasnot), _G677, _G678) ? creep
   Exit: (7) move(state(atdoor, onfloor, atwindow, hasnot), walk(atdoor, _G673), state(_G673, onfloor, atwindow, hasnot)) ? creep
   Call: (7) canget(state(_G673, onfloor, atwindow, hasnot)) ? creep
   Call: (8) move(state(_G673, onfloor, atwindow, hasnot), _G685, _G686) ? creep
   Exit: (8) move(state(_G673, onfloor, atwindow, hasnot), walk(_G673, _G681), state(_G681, onfloor, atwindow, hasnot)) ? creep
   Call: (8) canget(state(_G681, onfloor, atwindow, hasnot)) ? creep