University of Toronto
Faculty of Arts and Science

CSC324 -- Principles of Programming Languages
Spring 1998

Department:		Computer Science
Instructor:			 John Mylopoulos
Date:					February 10, 1998


Assignment 2:
Logic Programming with Prolog

      Due Dates
	  Part A:  6:10pm Tuesday, February 24, 1998
	       Part B:  6:10pm Tuesday, March 10, 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. Here is how to use it for assignment 2A.

	   submit -N  a2  csc324h  a2a.prlg

where	   'submit'   is the command to submit your assignment electronically,
	   '-N  a2'   indicates that you wish to create a subdirectory 'a2' in
		      your submit directory  containing  that assignment,
		      'csc324h'	  is this course,
and		      'a2a.prlg'  is the file with your submitted assignment.

If, for some reason, you decide later that you want to overwrite your earlier
submission (you cannot "unsubmit"), you must explicitly tell submit to do so
with the '-f'  switch:

     submit  -N  a2  -f  csc324h  a2a.prlg

For more information on how to use submit, type 'man submit' to access manual
documentation.

 Part A [50 marks]

1. [5 marks] Write a BNF grammar  that generates Lisp s-expressions.

2. [5 marks] For each of the following pairs say whether or not they will
unify, and if so, what the mgu will be. For any that do not, explain at what
point the unification algorithm fails:

(a) f(g(a),g(a),g(a))		and    f(X,Y,Z)
(b) f(g(a,b),a,g(b,a))		and    f(g(X,Y),X,g(X,Y))
(c) f(g(X),h(Y,Z),r(Y,a))	and    f(g(a),h(r(b,c),X),h(r(b,U),X)
(d) f(g(X),h(Y,X),r(Y,a))	and    f(g(a),h(r(b,c),U),h(r(b,U),U)
(e) f(X,g(Y,Y))			and    f(g(Y,Y),Y)

3. [10 marks] Consider the grammar  G = ({S,A,B},{a,b},P,S), where the
rule set P includes  the following rules:
     S ::= a B   A ::= b A A
     S ::= b A   B ::= b
     A ::= a	 B ::= b S
     A ::= a S   B ::= a B B

What language is generated by  this grammar? Prove your claim by using
mathematical induction on the length of the generated string.

4. [5 marks] Suppose you have a list L of atoms. Write a program that  outputs
the elements of the list as a sequence of words so that  the first letter of
each word is capitalized and words are separated by a comma except for the
last two which are separated by  "and".  For example:

     ?-output1([john,mary,james]).	 
     John, Mary and James.
     Yes
     
     ?-output1([this,makes,no,sense]).
     This, Makes, No and Sense.

5. [5 marks] Write a program that translates a list of English words into
French. Assume the following dictionary:

dict(the,le).  dict(dog,chien).	dict(blue,bleu).
dict(chases,chasse).		dict(cat,chat).	dict(green,vert).
dict(five,cinq).		dict(north,nord).	dict(south,sud).

				?- translate([the,dog],X).
				X = [le,chien]
				Yes
				
				?- translate([blue,cat,green,dog],X).
				X = [bleu,chat,vert,chien]
				Yes

6. [10 marks] Write a program  that parses  sentences according to the rules
of the  following BNF grammar:

   S   ::= NP VP
   NP  ::= [ Determiner ]  PNP
   PNP ::= [ Adjective ] Noun
   VP  ::= Verb [ NP ] | ToBe [ Adjective ]

Non-terminal symbols S, NP, VP and PNP correspond respectively to
English sentences, noun phrases, verb phrases and proper  noun phrases. To
test your program, you may assume the following vocabulary: 

Determiners:	   the, a, this, my, his, her, their.
Adjectives:	   good, bad, lazy, big, old, nasty, green, blue, late,
perfect, black, white, late.
Nouns:	 dog, cat, school, bank, assignment, assignments, penalty,
students, class, course, courses, beer, door.
Verbs:	  go, play, like, chase, chases, get, pass, enter, enters,	close,
drink, drinks.
ToBe:	is,are,was,were.

Your program must define a predicate sentence(List) that returns Yes if the
given list is a sentence according to the above grammar. For example, 

      ?-sentence([the,dog]).
      No

      ?-sentence([the,dog,chases,the,cat]).
      Yes

Test your program with the following  sentences: "this is a big class", "good
students pass their courses", "her assignment was perfect", "late assignments
get a penalty", "his cat is black".

7. [10 marks] Now combine programs from questions #5 and  #6 so that your
translation program works only  for correct sentences according to the grammar
given in question #6.  In addition, your translated sentences should respect
French grammar gender rules between determiners and nouns. That is, the gender
of a noun and its associated determiner must match, so "the door" is translate
to "la port", not "le port".  To accomplish this, your  program must look
ahead of any  determiner it comes across, find the associated noun, figure out
the gender of the corresponding French noun, and translate appropriately. You
may assume that French words in your dictionary possess gender information,
i.e., 

dict(the,le,m).		dict(the,la,f).		dict(door,porte, f).	
dict(nasty,miserable,_). dict(is,est,_).	dict(lazy,paresseux,_).	
dict(beer,bier,f).	 dict(green,vert,_). dict(blue,bleu,_).		
dict(dog,chien, m).	 dict(cat,chat, m).  dict(bank,banque,f)
dict(drinks,boit,_).	 dict(enters,'entre dans',_).	

Translate the following  sentences: "the nasty dog chases the cat", "the cat
is lazy", "the dog drinks beer", "the door is green", "the black cat  enters
the green door", "the bank is closed".