Prolog

Prolog (PROgramming in LOGic) was created in 1972 by Alain Colmerauer and Robert Kowalski. A program is not a list of steps but a set of facts and rules, and running it means asking a question. The system finds the answers by unification and backtracking.

Paradigm: Logic Programming

What Makes Prolog Special

  • Facts, rules and queries. A fact is parent(tom, bob)., a rule is ancestor(X, Y) :- parent(X, Y). (read :- as "if"), and a query starts with ?-.
  • Variables start with a capital letter. Who or X are unknowns to be found. A lowercase word such as tom is a constant (an atom).
  • Relations run in every direction. The same ancestor rule answers "who are the descendants of tom?" and "who are the ancestors of ann?". There is no fixed input or output.
  • Backtracking search is built in. When a choice leads nowhere, the engine undoes it and tries the next one. Pressing ; asks for another answer.
  • Lists and recursion. Data is built from lists and terms, and recursion over [Head|Tail] replaces loops. Prolog is homoiconic: programs are terms it can inspect.

Example: A family tree that can be queried both ways

parent(tom, bob).
parent(bob, ann).
parent(bob, pat).

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

?- ancestor(tom, Who).
%  Who = bob ;
%  Who = ann ;
%  Who = pat.

?- ancestor(Who, ann).
%  Who = bob ;
%  Who = tom.

How It Works

  • Three facts describe the family. Nothing says how to search them.
  • Two rules define ancestor: a parent is an ancestor, and an ancestor of a parent's child is also an ancestor. The second rule is recursive, with no loop.
  • In the first query, the engine unifies X with tom and tries each way to prove the goal, giving bob, then ann and pat on backtracking.
  • The second query runs the same rules backwards to find who is an ancestor of ann. This reversibility is unique to logic programming.

History and Where It Is Used

Prolog is used in natural-language processing, expert systems, scheduling and planning, theorem proving, and compilers (Erlang was first written in Prolog). SWI-Prolog is the most popular free implementation and has libraries for constraints, web services and databases. The ideas also appear in Datalog engines and rule systems.

Learn More