User:Eugene M. Izhikevich/Proposed/PROLOG programming language

From Scholarpedia
Jump to: navigation, search

PROLOG is a declarative programming language based logic. It is declarative in the sense that rather than defining procedures to solve the problem, in PROLOG the user defines the problem, and the computer automatically searches for solutions. It is widely used to implement symbolic inferences in the context of artificial intelligence.


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>0 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>0 is already computed.


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:


and the computer gives the answer:


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


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.


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 publications were internal reports:

  • 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.
  • Philippe Roussel, Prolog, manuel de référence et d'utilisation, Groupe d'Intelligence Artificielle, UER Marseille-Luminy, September 1975.

The work was influenced by Robert Kowalski who was in Edinburgh. More than ten years later David Warren, also in Edinburgh, created the WAM machine for his Prolog compiler.


Recommended reading

External links

Personal tools

Focal areas