Assigned: 19 Nov.2001
Due: 10 Dec 2001 /

CS536 Written Assignment

Project No.4

Write a program to interpret a subset of Prolog. Prolog is a logical language. Prolog encourages the use of a single uniform database. Because it is based on the idea of a database, Prolog is relational. A relationship in Prolog is a logicalpredicate (a predicate in first order predicate logic), with several arguments, relationship that may be true or false. Prolog provides logical variables instead of ordinary variables. A logical variable is bound by unification rather than by assignment. Once bound, a logical variable can never change in the same context. Prolog provides automatic backtracking; every query leads to a search for relations in the database that satisfy the query. If there are several such relations, they are considered one at a time.

Prolog assertions are called clauses and they are divided into two types: facts, which state a relationship that holds between some objects, and rules, which are used to deduce new facts based on existing ones (based on conditions).

The following examples use a (suggested) syntax that is not exactly the one of Prolog. The syntax is such that it allows the Prolog interpreter to be embedded in Lisp or Scheme.

We will use <- to mark facts and rules.

Examples of facts

(<- (likes kim lee))

(<- (likes john kim))

(<- (likes robin dogs))

(<- (likes john dogs))

(<- (nice robin))

<fact> ::= (<- (<predicate> {<argument>}*))

Examples of rules

(<- (likes kim robin) (likes robin dogs) (nice robin))

which is to be read: “Kim likes Robin if Robin likes dogs and Robin is nice”

(<- (likes kim ?x) (likes ?x dogs) (likes ?x kim))

which is to be read: “Kim likes everyone who likes dogs and likes Kim”

(or “For any x, Kim likes x if x likes dogs and x likes kim”)

?x marks a logical variable.

<rule> ::= (<- <head> <body>)

<head> ::= (<predicate> {<argument>}*)

<body> ::= {<condition>}*

< condition > ::= (<predicate> {<argument>}*)

<argument> ::= <constant> | ?<identifier>

Querying the database

Consider the database with the facts and rules above.

(<- (likes kim lee))

(<- (likes john kim))

(<- (likes robin dogs))

(<- (likes john dogs))

(<- (nice robin))

(<- (likes kim robin) (likes robin dogs) (nice robin))

(<- (likes kim ?x) (likes ?x dogs) (likes ?x kim))

A query of the database should look like this:

(?- (likes kim lee))

Yes(this is the answer provided by the interpreter)

(?- (likes kim tom))

No

(?- (likes ?x dogs) (nice ?x))

?x = robin(the only answer for a person who both likes dogs and is nice)

(?- (likes kim ?x))

?x = lee(this is the first possible answer for ?x)

(If the user enters CR then no more solutions are sought.)

(?- (likes kim ?x))

?x = lee;(first answer for ?x, because of the first fact in the database)

?x = robin;(second answer for ?x, because of the first rule and existing facts)

?x = john;(third answer for ?x, because of the second rule and existing facts)

No(which means no more solutions)

<query> ::= (?- {<head>}*)

A query is also called a goal that the Prolog interpreter tries to prove.

The interpreter you are going to write should be able to process and give adequate answers to such examples. The interpreter should function by matching goals to facts and rule heads, perform variable unifications when necessary, and return the first solution if any (either Yes or variable values that make the goal true) or No if no solution. If other solutions are required, the interpreter backtracks (automatic backtracking) and searches for another match.

The interpreter should have a function unify (you may define the function, arguments, and return value the way it fits your implementation) that will behave in the following manner:

(unify ‘a ‘a)  (T . T)

(unify ‘a ‘b)  NIL

(unify ‘(?x ?y) ‘(a a))  ((?X . A) (?Y . A))

(unify ‘(?x ?y a) ‘(?y ?x ?x))  ((?Y . A) (?X . ?Y))

(unify ‘(?x a b) ‘(?y ?x ?x))  NIL

You should also:

  • Comment your code
  • Explain how your program works and each main function
  • Give input and associated output on relevant examples (at least the ones mentioned above but include also your own)
  • Include a trace facility that may be turned on and off, to trace facts and rules that are tried for matching and give the trace for an example that includes at least 2 rules and backtracking
  • Demonstrate separately your unify function on the examples above – as stated previously, you may make your own design decisions for unify, therefore the demo may not look exactly (at the syntactic level) as the examples above.

Note that you will be graded also on clarity of explanations, and programming style. Please provide both hard and soft copies for this project.

The language you use is at your choice. You should not copy code from books, web or colleagues. The code must be entirely yours.

Reading Chapter 8, Sections 8.1-8.4 from the PLC book will help you understand Prolog. Logical programming and Prolog will be covered on 26 Nov. and 3 Dec. in class. Prolog documentation indicated on the Web page of the course may also help.