PROLOG is based on a proof procedure known as resolution theorem proving, which was developed in 1965 by J. A. Robinson. It is covered in Chapter 15 of the Luger text.
PROLOG uses a declarative programming approach. Rather than describing how to do something, as is done in a procedural programming language (such as C), a PROLOG program describes what to do. For example, the following PROLOG program implements a stack (see Luger p. 655):
empty_stack([]). /* An empty list ([]) is an empty stack. */ stack(Top, Stack, [Top|Stack]). /* These are the push and pop operators. */
The first predicate describes what an empty stack looks like. The second describes what it means to push or pop the Top element of an existing Stack.
What makes it possible to describe a stack in such a cryptic way is that the PROLOG interpreter does a lot of the "how to" work for us. For example, for the second predicate, the interpreter will take different actions depending on how the parameters (Top, Stack) are bound to arguments. We'll get to the details shortly.
There are four parts to this topic: