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:
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
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:
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:
Notation: The clause "~p V ~q V r" is written in Prolog in the form "r :- p,q."