Dr. Alain Colmerauer

Revision as of 09:53, 31 March 2008

What is it?

A Prolog program is made of a set of rules. A rule is of the following form:

  <assertion>0  \(\leftarrow\) <assertion>1  , ... , <assertion>n . 

It states:

  <assertion>0 holds if <assertion>1,...,<assertion>n all hold.

In particular, when n=0, it states: <assertion>₀ holds. This is the declarative meaning. For the procedural meaning the rule states:

  to compute <assertion>0, compute <assertion>1,...,<assertion>n.

In this case, when n=0, it states: <assertion>₀ is already computed.

Example

We would like to concatenate b l to u e to obtain b l u e. Given the data structure of Prolog, we will concatenate dot(b,dot(l,nil)) to dot(u,dot(e,nil)) to obtain dot(b,dot(l,dot(u,dot(e,nil)))). Let us suppose that conc(X,Y,Z) means the concatenation of X with Y is Z and that list(X) means X is a list. Here is the program:

  conc(nil,X,X) :- list(X).
  conc(dot(A,X),Y,dot(A,Z)) :- conc(X,Y,Z).
  
  list(nil) :- .
  list(dot(A,X)) :- list(X).

The double sign :-  denotes \(\leftarrow\). What is more important, capital letters are used for variables. Their scope is just valid for each rule, and their value is unique but partially known. To run the program we ask a query:

  conc(dot(b,dot(l,nil)),dot(u,dot(e,nil)),Z).

and the computer gives the answer:

  Z=dot(b,dot(l,dot(u,dot(e,nil)))).

But because we have defined conc to be a ternary relation and not a binary function, we can ask:

  conc(X,Y,dot(b,dot(l,dot(u,dot(e,nil))))).

and obtain several answers:

  X=nil, Y=dot(b,dot(l,dot(u,dot(e,nil)))).
  X=dot(b,nil), Y=dot(l,dot(u,dot(e,nil))).
  X=dot(b,dot(l,nil)), Y=dot(u,dot(e,nil)).
  X=dot(b,dot(l,dot(u,nil))), Y=dot(e,nil).
  X=dot(b,dot(l,dot(u,dot(e,nil)))), Y=nil.

History

Prolog was invented in 1972, at Marseilles, by Alain Colmerauer and Philippe Roussel. The name Prolog stands for Progammation en Logique in French and was coined by Philippe Roussel. At that time, the only publication was an internal report:

Alain Colmerauer, Henry Kanoui, Robert Pasero et Philippe Roussel, Un système de communication en français, preliminary report for IRIA, Groupe d'Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, October 1972.

The work was influenced by Robert Kowalski who was in Edimburgh. More then ten years later David Warren, also in Edimburgh, created the WAM machine together with his Prolog compiler.

Usefull links

[site of Alain Colmerauer] [Association for Logic Programming ] [site of Robert Kowalski] Warren abstract machine