PLDA Homework 4: Prolog interpreter

Write an interpreter for a Prolog subset.

A Prolog program is composed of several clauses. Clauses can be facts or rules. A rule has the form

Head :- Body .
where Head is a predicate, and Body is a list of one or more predicates separated by commas. A fact has the form
Predicate .
and is equivalent with the rule Predicate :- true . Predicates are written over terms, which are constants, variables, or functions of terms. Variables start with uppercase and constants with lowercase letters.

The meaning of a clause is that the clause head is true if all the predicates in the body are true.
Evaluation of a goal is done by unifying it with the head of a rule, and then evaluating the subgoals in the rule attempting to make them true.

Before unification, the variables in the rule head and body have to be renamed to fresh variables.

Define a term as

type term = Var of string | Fun of string * term list
and consider constants to be zero-arity functions.

It suffices for your functions to handle ML representations; if you prefer, a parser to interface with will be provided.


Marius Minea
Last modified: Tue Nov 15 8:30:00 EET 2011