Description
Consider the following further simplified version of Prolog we have discussed in class:
• Axioms as given in Horn clause form.
• Variables in head are universally quantified.
• Variables in body only are existentially quantified.
• A query is a clause without a head.
• A fact is a clause without a body.
• A prolog program is composed of a list of clauses and one or more queries.
• There are no functions. Note that lack of functions will render this language very weak since
useful arithmetic and many other things cannot be done without functions.
A BNF for this simplified version Prolog is given below:
::= |
::= |
::= . | :- .
::= | , ::= | ( )
::= | ,
::= | |
::= ?- .
::= | ““
::= |
::= |
::= a | b | c | … | x | y | z
::= A | B | C | … | X | Y | Z
::= … integer numbers …
::= … all characters …
::= |
Assume that someone has written a lexer and a parser that can take a program in this language and
generate a data structure in Common Lisp.
• The outcome of the parser is a list of horn clauses.
• Each horn clause is a list of two entries, namely head and body.
• Head part is itself a list.
o If the clause is a query, head will be nil.
o Otherwise, it will be a predicate.
• Body is also a list with zero more entries.
o If the clause is a fact, the body will be nil.
o Otherwize, it will be a list of predicates.
• A predicate is a list with two entries: (predicate_name list_of_parameters)
o The first entry is a string indicating the name of the predicate.
o The second is a list of (possibly empty) parameters.
o The list of parameters can have string or numeric entries. String entries starting with
capital letters indicate that the parameter is a variable. String entries starting with
lowercase letters indicate name of objects (NOTE: object names cannot start with
caps). Numeric entries are treated as Common Lisp integers.
For example, the following code:
legs(X,2) :- mammal(X), arms(X,2).
legs(X,4) :- mammal(X), arms(X,0).
mammal(horse).
arms(horse,0).
?- legs(horse,4).
will generate the following list:
(
( (“legs” (“X” 2)) ( (“mammal” (“X”)) (“arms” (“X” 2)) ) )
( (“legs” (“X” 4)) ( (“mammal” (“X”)) (“arms” (“X” 0)) ) )
( (“mammal” (“horse”)) () )
( (“arms” (“horse” 0)) () )
( () (“legs” (“horse” 4)) )
)
Write a Common Lisp function such that when a parsed list of Horn clauses is given (as defined above)
as input, it will answer all the queries in this list of clauses. You will use resolution and unification
methods discussed in class to prove the queries and return the list of values for all variables for which
the query is true. An empty list on return means that the query is false. Make sure that your query
answer function halts.
