Prolog Language Born
Alain Colmerauer develops Prolog at University of Marseille, pioneering the logic programming paradigm.
Overview
Around 1970, Alain Colmerauer and Philippe Roussel at the University of Marseille developed Prolog (PROgrammation en LOGique). Prolog is based on Horn clauses from first-order logic, adopting a declarative programming style: programmers describe facts and rules about problems rather than specific computation steps. Prolog's execution engine automatically finds solutions to queries through backtracking search and unification algorithms. This logic programming paradigm has wide applications in natural language processing, expert systems, and knowledge reasoning, especially suitable for symbolic reasoning and knowledge representation tasks. Prolog, along with LISP, became an important tool language for AI research.
Study Notes
Background, mechanics, impact, and key takeaways in one read
Background & Context
In the early 1970s, Alain Colmerauer's team at the Université d'Aix-Marseille wanted computers to converse in French, while Robert Kowalski in Edinburgh was developing the "procedural interpretation of Horn clauses." The two lines met when Kowalski visited Marseille in 1971: they realized that the clausal form of first-order logic could both represent grammar and execute as a program. In 1972, Colmerauer and his student Philippe Roussel built the first interpreter, and Roussel coined the name Prolog (PROgrammation en LOGique). It turned "logic as program" into reality, becoming an AI language rivaling LISP and later a favorite of Japan's Fifth Generation project.
Key Points
- 1Alain Colmerauer and his student Philippe Roussel built the first working Prolog interpreter at Marseille in 1972.
- 2Prolog's theoretical foundation rests on Robert Kowalski's Edinburgh insight, the "procedural interpretation of Horn clauses."
- 3A Prolog program is a set of facts and rules (Horn clauses), driven by queries that prove goals.
- 4Its two core mechanisms are the unification of terms and depth-first search with chronological backtracking to find proofs.
- 5The very first Prolog program was a French question-answering system, born directly from natural-language motives.
- 6Japan's Fifth Generation project adopted Prolog as a base language, and Europe embraced it over Lisp.
How It Works
Prolog writes programs as "facts plus rules," e.g., parent(X,Y) :- father(X,Y). means "if X is Y's father, then X is Y's parent." A rule H :- B1, B2. reads both as a logical proposition and as a procedure call: to prove H, prove B1 and B2. On a query, the system uses unification to match variables against known facts or rule heads, then proves subgoals recursively; if a path fails, it backtracks up the call stack to the nearest choice point and tries another—chronological backtracking. Because search is depth-first by default, you declare "what is true" rather than "do this then that." The analogy: you state the puzzle's constraints and the machine searches backward for an assignment satisfying all of them, like solving Sudoku rather than writing a flowchart.
Impact & Legacy
Prolog brought declarative logic programming to the mainstream, becoming key for expert systems, NLP, and automated reasoning, and rose to fame via Japan's Fifth Generation project. Its limits: depth-first backtracking can be very slow on large spaces, and control constructs like cut undermine pure declarativeness; industrial use stayed small. Yet it endures in constraint logic programming, database querying (Datalog), and recent neuro-symbolic systems such as DeepProbLog, proving "logic as program" has lasting life. Its influence also reaches SQL-like query languages and verification tooling in industry.
Key Takeaways
- Declaring "what is true" often captures a problem's essence better than writing "how to do it."
- Unification and backtracking are the two pillars of a logic-programming engine.
- Control constructs like cut trade pure declarativeness for efficiency—a common engineering trade-off.
Glossary
A clause with at most one positive literal, H :- B1,...,Bn; both a logical proposition and a procedure.
Finding a variable assignment that makes two logical expressions equal; the core of Prolog matching.
When a proof path fails, rewinding up the call stack to the nearest choice point to try an alternative.