University of Toronto
Faculty of Arts and Science

CSC324 -- Principles of Programming Languages
Spring 1998


Assignment 2:
Logic Programming with Prolog

      Due Dates
          Part A:  6:10pm Tuesday, March 3, 1998
          Part B:  6:10pm Tuesday, March 17, 1998

This assignment counts for 15% of the final grade


All programs should be written in Prolog and should be well documented and
thoroughly tested. Make sure you use good logic programming style; marks will
be deducted for programs that look like translated Lisp,  Turing or C.

Assignments should be handed in electronicaly, using the 'submit' command
available  on CDF machines.


Part B [100 marks]

8. [English to Logic; 5 marks] Write down  formulas in First Order Logic for
each of the following statements:

There exists a student who likes every course that he is enrolled in.
Every student  likes at least one course that she takes
If a student  is enrolled in a course, she has completed each prerequisite  or
has permission from the instructor.


9. [Logic to Prolog; 5 marks] Convert each of the formulas of problem #8 into
a collection of one or more Horn clauses, or show that this is not possible.


10. [Puzzles; 20 marks] Write down a sequence of  Prolog clauses which
represents the following facts:

Just before the end of the term, four students are discussing their
expectations in terms of letter grades for CSC324S.

Jack: We'll all get different grades;  if I get an A, Lucy will get a D.
Jean: If Lucy gets a C, Jack will get a D;  Jack will get a better grade  than
Paul.
Lucy: If Jean doesn't  get an A, then Jack will get a C;  if I get a B, then
Paul won't get a D.
Paul: If Lucy gets an A then I will get a B; if Jean doesn't get a B, then I
won't either.

When grades were announced, the students found, much to their surprise, that
all their expectations were in fact fulfilled! What letter grades did they
get? Is there more than one solution? Explain. 


11. [The Blocks World; 40 marks] Consider a world consisting of a tabletop
with several objects (blocks) of type brick, ball or pyramid.  The world also
includes a hand (robotic, naturally) that can move to any location on the
table, grasp any block (but only one at a time), or release a block it is
holding.  The hand may release a block only onto the table or the top of a
brick.



Write a Prolog program that can perform two operations:

      pickup(block)
      puton(block,support)

The first has the hand pick up a block after clearing off anything on top of
it, if necessary). The second has the hand place a block on a brick after
clearing the brick's top, if necessary.  For each input operation, your
program will produce the sequence of actions the arm must carry  out.

For example, assuming that block r is on block y, and we want y on block b,
for the operation puton(y,b) the program might generate the following sequence
of  actions:


    moveto(t1):		t1 is the location of y and r
    grasp(r)		   r is a block at t1 with nothing on top.
    moveto(t2)		     t2 is an empty location
    ungrasp(r)			r is now at t2, on the table.
    moveto(t1)			  back to t1
    grasp(y)			       that's a block, also at t1
    moveto(t3)				      brick b is located at t3
    ungrasp(y)					    now y is on b


Your program will have to represent the current state of the world, e.g.,
facts like these:

      "y is a block"	"p is a ball"
      "t1 is a location"   "b is at t3"
      "r is on y"	      "b is on table"
      "hand  is empty"	      "t2 is empty"....

Here are some operations that will probably be useful for your program:

move-hand:    Moves hand to a given location.
get-rid-of:   Gets hold of a given block whose top is clear and places it on
the table.
clear-top:	Clears all blocks on top of a given brick by getting rid of
them.
make-space:	Finds an empty location on the table or generates one.
		      (Assume there is always more empty space on table.)
grasp:			      Hand grasps a block with a clear top.
ungrasp:		      Releases block currently held.

Note that all these operations will need to change the representation of the
state of the world by asserting and erasing clauses.

Your program should enforce constraints such as:
"An object  can't be placed in a location where there is already a ball"
"Hand can only hold one object  at a time", 
etc.


12. [Recognizing Animals: 30 marks] Write a program which identifies animals
on the basis of clues (expressed in terms of Prolog clauses)that state facts
such as the following:

     ``The animal has feathers.''
     ``The animal has teeth.''
     ``The animal has long legs and a long neck.''

The identification is carried out by deduction with respect to a set of facts
about different biological classes of animals.  Some of the facts that your
program would use are listed below:

(a) If the animal has hair, then it is a mammal.
(b) If the animal gives milk, then it is a mammal.
(c) If the animal has feathers, it is a bird.
(d) If the animal flies and lays eggs, it is a bird.
(e) If the animal is a mammal and eats meat, it is a carnivore.
(f) If the animal is a mammal, has teeth, and its eyes point forward, then it
is a carnivore.
(g) If the animal is a mammal and has hoofs, then it is an ungulate.
(h) If the animal is a mammal and chews cud, then it is an ungulate and it is
even-toed.
(i) If the animal is a carnivore, has a tawny colour, and has dark spots, then
it is a cheetah.
(j) If the animal is a carnivore, has a tawny colour, and has dark stripes,
then it is a tiger.
(k) If the animal is an ungulate, has long legs, a long neck, a tawny colour,
and dark spots, then it is a giraffe.
(l) If the animal is an ungulate, has white colour, and has black stripes,
then it is a zebra.
(m) If the animal is a bird, does not fly, has long legs and neck, and is
black and white, then it is an ostrich.
(n) If the animal is a bird, swims, does not fly, and is black and white, then
it is a penguin.
(o) If the animal is a bird and it flies, then it is an albatross.


[Bonus (10 marks): Have your program ask questions  for missing clues.]