Logic Programming and Prolog

In the rest of this section we assume all the traditional definitions of mathematical logic [33].

Logic Programming [73] is a well-known programming paradigm based on a subset of First Order Logic--named Horn Clause Logic. A program is composed by a set of clauses (i.e., implications) of the form and execution is driven by a query (or goal) of the form .

Given a program P and a query , the purpose of an execution is to verify under which conditions the conjunction is a logical consequence of the program P--i.e., .

The computation process is based on two basic mechanisms, mainly due to Robinson [89], namely Resolution and Unification. Unification of two atoms A and B is the process of computing a substitution such that .

During resolution, given a query , a literal is selected, and a clause such that H and unify is used to produce a new query (named resolvent)

where is the (most general) unifier of H and .

In general, no restrictions are imposed on the order in which the subgoals and the clauses to be used are selected--i.e., they are non-deterministic operations. In particular:

• since, in absence of failure, each subgoal in the query will be eventually selected, the non-determinism in the subgoal selection is indicated as don't care non-determinism;
• since selecting different clauses will possibly lead to different solutions, the non-determinism in the clause selection is indicated as don't know non-determinism;

Different languages and different semantics can be obtained by playing on the definition of these two selection operations (i.e. subgoal selection and clause selection).

Prolog [100] is the most popular logic programming language. Prolog is based on Horn Clause Logic and its semantics are based on the previously described resolution + unification mechanisms. Prolog's operational semantics define the two select operations as follows:

• Prolog treats the query as a list of atoms and always selects the leftmost atom in the list;
• Prolog treats the program as a sequence of clauses and selects them in the order in which they are stored.

Prolog extends pure Horn clause logic with some additional features, aimed at making Prolog a ``complete'' programming language. The most relevant extensions are:

• Meta-logical Predicates: which are used to manipulate terms and to query the state of the proof (e.g., instantiation state of the variables).
• Cut: it represents the only non-logical operator in Prolog which affects the control of the execution. The cut allows to prune parts of the search space explored by the clause selection process.
• Extra-logical Predicates: they are used to perform I/O and to dynamically modify the structure of the program (e.g., dynamically adding new clauses to the program).

The semantics of Prolog are heavily based on the ordering adopted by the two selection functions--which is fundamental for the correct behaviour of the various extra-logical features of the language. From now on, whenever we talk about Prolog semantics we refer to this ordering of exploration of the search space. Because of this, we will often refer to those extra-logical predicates whose behaviour depends on their order of execution as order-sensitive predicates.

Web Tour

• The Logic Programming World
• Logic Programming Archive