Prolog Programming Project

Due Monday, December 4


You are welcome to choose a project in Prolog. Below are a few suggestions, but if you have a more interesting idea that will  demonstrate your knowledge of Prolog, that's fine.


Suggestion 1.


Write a toy, syntax-driven translator, either from one language to another (e.g. English to French, Italian to German, etc.)  or within a single language, translating sentences to different sentences with the same meaning.

Sentences will be represented as lists of words. The translator should be able to handle simple sentence constructions, such as [jack, runs], subject-verb-object [jack, hits, susan], subject-verb-prepositional phrase [jack, went, to, the, school].  The translation should maintain the correct verb tense and conjugation.

You should create a database of translations of words (using facts, of course) and clauses showing grammatical rules. These facts and clauses might look like:

englishpropernoun(jack).
englishverb(run).
   ...
englishpast(run,ran)
   ...
frenchverb(courir).
frenchconjugation(courir,je, cours).
frenchconjugation(courir,il, court).
   ...
translation(he,il).
translation(i,je).
   ...
pastparticiple(courir,couru).
   ...
auxiliary(courir,avoir).
   ...
frenchpast(Subject,Infinitive,[Aux,Participle]) :-
      pastparticiple(Infinitive,Participle),auxiliary(Infinitive,AuxInf),
      frenchconjugation(AuxInf,Subject,Aux).
   ...
You can imagine how [he,ran] gets translated to [il,a,couru] using the
clauses above. Try to write the translator so that it works in both directions.


Suggestion 2


It is a relatively simple matter to write a program to perform symbolic differentiation on algebraic expressions. Consider:

d(U+V,X,DU+DV) :- d(U,X,DU), d(V,X,DV).
d(U-V,X,DU-DV) :- d(U,X,DU), d(V,X,DV).
d(U*V,X,U*DV+V*DU) :- d(U,X,DU), d(V,X,DV).
d(X,X,1).
and so on (see Sterling&Shapiro, pp. 79 ff.) These rules describe the derivatives of algebraic expressions in terms of the derivatives of their subexpressions. The symmetry between input and output in these clauses means that they can be used to integrate as well. Investigate this fact, by extending the rules given above with a few more (powers,
quotients, some elementary functions, constants, etc.) and then test them as an integrating device. In order to be usable, such a system will require a few rules for algebraic simplification, multiplication by zero and one, constant folding of simple arithmetic expressions, etc. Be creative and have fun!

Note that +,*, and - are infix operators (that are identical to their prefix counterparts, i.e. X+Y is the same as +(X,Y)).