Design

Prolog Implementation in OCaml

An example of a Prolog program

mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

?- sibling(sally, erica).

Declarations

There are 3 types of declarations:

Declaration	Pseudo-code
Rules	Head :- Body.
Facts	Head.
Query	?- Head.

The fact Head. is syntactic sugar for the rule Head :- true.

Expressions

In the above example, this line:

parent_child(X, Y) :- father_child(X, Y).

can be modeled as:

Clause (
    TermExp (
        "parent_child",
	[
            VarExp "X",
            VarExp "Y"
        ]
    ),
    TermExp (
        "father_child",
        [
            VarExp "X",
            VarExp "Y"
        ]
    )
)

Similarly, this line:

mother_child(trude, sally).

can be modeled as:

Clause (
    TermExp (
        "mother_child",
        [
            TermExp ("trude", []),
            TermExp ("sally", [])
        ]
    ),
    ConstExp (BoolConst true)
)

A more complicated line like:

sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y).

would be modeled as:

Clause(
    TermExp (
        "sibling",
        [
            VarExp "X",
            VarExp "Y"
        ]
    ),
    ConjunctionExp (
        TermExp (
            "parent_child",
            [
                VarExp "Z",
                VarExp "X"
            ]
        ),
        TermExp (
            "parent_child",
            [
                VarExp "Z",
                VarExp "Y"
            ]
        )
    )
)