Pure Prolog

Pure Prolog: We are now ready to deal with (pure) Prolog, the major Logic Programming Language. It is obtained from a variation of the backward chaining algorithm that allows Horn clauses with the following rules and conventions:

• The Selection Rule is to select the leftmost literals in the goal.
• The Search Rule is to consider the clauses in the order they appear in the current list of clauses, from top to bottom.
• Negation as Failure, that is, Prolog assumes that a literal L is proven if if it is unable to prove (NOT L)
• Terms can be set equal to variables but not in general to other terms. For example, we can say that x=A and x=F(B) but we cannot say that A=F(B).
• Resolvents are added to the bottom of the list of available clauses.

These rules make for very rapid processing. Unfortunately: The Pure Prolog Inference Procedure is Sound but not Complete This can be seen by example. Given

• P(A,B)
• P(C,B)
• P(y,x) < = P(x,y)
• P(x,z) < = P(x,y),P(y,z)

we are unable to derive in Prolog that P(A,C) because we get caught in an ever deepening depth-first search. A Prolog "program" is a knowledge base Gamma. The program is invoked by posing a query Phi. The value returned is the bindings of the variables in Phi, if the query succeeds, or failure. The interpreter returns one answer at a time; the user has the option to request it to continue and to return further answers.

The derivation mechanism of Pure Prolog has a very simple form that can be described by the following flow chart.

Interpreter for Pure Prolog Notational conventions:

• i: used to index literals in a goal
• Ki: indexes the clauses in the given program (i.e. set of clauses) P
• Max: the number of clauses in P
• h(G): the first literal of the goal G
• t(G): the rest of goal G, i.e. G without its first literal
• clause(Ki): the kith clause of the program

Real Prolog: Real Prolog systems differ from pure Prolog for a number of reasons. Many of which have to do with the ability in Prolog to modify the control (search) strategy so as to achieve efficient programs. In fact there is a dictum due to Kowalski:
Logic Control = Algorithm
But the reason that is important to us now is that Prolog uses a Unification procedure which does not enforce the Occur Test. This has an unfortunate consequence that, while Prolog may give origin to efficient programs, but
Prolog is not Sound
Actual Prolog differs from pure Prolog in three major respects:

• There are additional functionalities besides theorem proving, such as functions to assert statements, functions to do arithmetic, functions to do I/O.
• The "cut" operator allows the user to prune branches of the search tree.
• The unification routine is not quite correct, in that it does not check for circular bindings e.g. X -> Y, Y -> f(X).)

Notation: The clause "~p V ~q V r" is written in Prolog in the form "r :- p,q."