next up previous contents
Next: Parallelism in Logic Programming Up: Parallel Logic Programming Previous: Parallel Logic Programming

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 tex2html_wrap_inline966 and execution is driven by a query (or goal) of the form tex2html_wrap_inline968 .

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

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 tex2html_wrap_inline984 such that tex2html_wrap_inline986 .

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


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

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:

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 extends pure Horn clause logic with some additional features, aimed at making Prolog a ``complete'' programming language. The most relevant extensions are:

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

next up previous contents
Next: Parallelism in Logic Programming Up: Parallel Logic Programming Previous: Parallel Logic Programming

Tue Mar 19 14:37:09 MST 1996