Prolog

Prolog — from the French programmation en logique — was created in 1972 by Alain Colmerauer and Philippe Roussel in Marseille, on a theoretical footing laid by Robert Kowalski in Edinburgh. It is the great practical embodiment of Logic Programming: you do not write steps, you write facts and rules, and ask questions.

How it thinks

A Prolog program is a set of logical clauses. To answer a query the engine uses two ideas working together:

• Unification — pattern-matching that binds variables to make two terms equal.
• Backtracking — when a path fails, quietly undo and try the next clause.

Kowalski put the whole philosophy in one equation: algorithm = logic + control. You supply the logic; the engine supplies the control.

Its moment, and its legacy

Prolog became the language of AI, expert systems and natural-language work in the 1970s and 80s. Japan’s Fifth Generation Computer Systems project (1982) bet its future on it. David H. D. Warren’s WAM — the Warren Abstract Machine — made it genuinely fast and remains the standard compilation target.

The branch that matters most in this encyclopedia: Erlang was first prototyped in Prolog. Joe Armstrong’s earliest experiments in fault-tolerant telecom programming were Prolog meta-interpreters, and Erlang still wears the inheritance — the clause syntax, the trailing ., and pattern matching are all Prolog’s fingerprints.

The people

Prolog began as a conversation across a continent. In Marseille, Alain Colmerauer wanted a machine you could address in ordinary French; in Edinburgh, Robert Kowalski had shown that a slice of formal logic could be run, not merely checked. Put the linguist’s need beside the logician’s theory and you get Prolog: state what is true, and let the machine do the searching.

• Alain Colmerauer came to computing through linguistics: he wanted machines that could hold a conversation in French. Prolog was his tool for reasoning about language, and that origin explains its declarative, grammar-like feel. He kept returning to natural language and constraints for the rest of his career.
• Philippe Roussel was Colmerauer’s collaborator in Marseille and wrote the first Prolog interpreter in 1972, turning the idea into a working system.
• Robert Kowalski, in Edinburgh, supplied the theory: that a subset of logic (Horn clauses) could be read procedurally and executed. His slogan — algorithm = logic + control — is the whole philosophy in four words.
• David H. D. Warren later built the Warren Abstract Machine (WAM), which made Prolog fast enough to be taken seriously.

What set them apart: they were willing to give up telling the computer how, and to trust a search engine to find the how from a statement of what. Almost nobody else was prepared to surrender that much control.

Landmark open-source projects

• SWI-Prolog — the batteries- included implementation the playground uses.
• GNU Prolog — a compact, standards-focused system.
• Logtalk — objects on top of Prolog. Datalog, its restricted cousin, powers modern query engines.

Try it

%% A family tree of languages. Ask who descends from algol.
parent(algol, c).
parent(algol, prolog).
parent(prolog, erlang).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
main :- forall(ancestor(algol, W), format("~w descends from algol~n", [W])).

Sources

• Colmerauer & Roussel, “The Birth of Prolog” (1992) — the creators on the Marseille origins.
• Kowalski, “Logic Programming” (overview) — the theory, from the man who supplied it.

See also: Logic Programming, Erlang, Lisp.