Prolog and Logic Programming: When AI Spoke in Clauses

Zusammenfassung

Prolog — PROgramming in LOGique — was born in Marseille in 1972 as a tool for natural language processing, built on the mathematical foundations of first-order logic and automated theorem proving. It embodied a radical vision: instead of telling a computer how to compute something, you describe what is true and let the machine figure out the how. Prolog achieved brief worldwide fame when Japan chose it as the foundation of its ambitious Fifth Generation Computer project in 1982. It never conquered mainstream programming, but it demonstrated the viability of declarative computation and influenced languages and systems from Erlang to IBM’s Watson. For broader context on AI, see The Rise of Artificial Intelligence.

The Logic of Programs

There is a way of thinking about programming that sits outside the mainstream. Most programming languages — C, Python, Java, FORTRAN — are imperative: you specify the sequence of steps the computer must execute, how variables change, which branches to take, when to loop. The programmer thinks like a machine, specifying the process that produces the result.

Declarative programming inverts this. Instead of specifying how to compute, you specify what is true. The runtime system — the interpreter or compiler — figures out the mechanism. SQL is the most widely used declarative language today: you write SELECT name FROM employees WHERE salary > 100000, and the database engine decides how to execute that query. You declare what you want; the system handles the how.

Logic programming takes this vision to its logical limit. If you express your problem as a set of logical statements — facts and rules — and the system can perform logical inference, then programming is simply the act of describing reality, and computation is automated deduction.

This was not just an abstract philosophical position. It was a practical research program, and by the early 1970s, several threads of theoretical work had converged to make it feasible.

Robert Kowalski and the Theoretical Foundation

Robert Kowalski at Edinburgh University was working on automated theorem proving — the problem of using a computer to verify mathematical proofs. Theorem proving required a search procedure that could apply logical inference rules to find a proof of a target statement from a set of axioms. The key challenge was making this search efficient enough to be practical.

Kowalski’s contribution, developed in the early 1970s, was to show that a subset of first-order logic — Horn clauses — was both expressive enough to describe many interesting problems and restricted enough to support a highly efficient inference procedure. Horn clauses are logical statements with at most one positive literal: things like “IF A is true AND B is true THEN C is true.” This restriction eliminated the combinatorial explosion that made general first-order theorem proving intractable.

Kowalski’s theoretical framework — later called SLD-resolution (Selective Linear Definite clause resolution) — gave Horn clause inference a depth-first, left-to-right search strategy that was predictable, efficient, and implementable. He published the key paper, “Predicate Logic as a Programming Language,” in 1974, but the practical implementation that embodied these ideas had already appeared two years earlier in Marseille.

Alain Colmerauer and the Birth of Prolog

Alain Colmerauer was a computer scientist at the Université d’Aix-Marseille whose research interest in the early 1970s was natural language processing — specifically, building computer systems that could understand and generate French. His problem was that natural language required complex relational reasoning: understanding a sentence like “The man that the woman saw left” requires tracking who saw whom and who left, using the kind of relational inference that conventional procedural programs expressed awkwardly.

In 1971–72, Colmerauer spent a research visit at Edinburgh working with Kowalski, absorbed the theoretical framework of SLD-resolution, and returned to Marseille determined to implement it. Working with Phillippe Roussel, he built the first Prolog interpreter in 1972 — writing it in FORTRAN on a CDC 6400.

The name combined “programmation” and “logique.” The language expressed programs as collections of clauses in three forms:

Facts: parent(tom, bob). — Tom is a parent of Bob.
Rules: grandparent(X, Z) :- parent(X, Y), parent(Y, Z). — X is a grandparent of Z if X is a parent of Y and Y is a parent of Z.
Queries: ?- grandparent(tom, Who). — Who are Tom’s grandchildren?

The Prolog interpreter would answer the query by searching through the facts and rules, trying to satisfy each subgoal in the query by matching it against available clauses. The search was automatic. The programmer specified the relationships; the interpreter found the answers.

For natural language parsing, this was genuinely elegant. A grammar rule like “A sentence is a noun phrase followed by a verb phrase” translated almost directly into a Prolog clause. Colmerauer and his colleagues used Prolog to build French-language question-answering systems in the mid-1970s — among the first successful natural language processing applications in any language.

Edinburgh Prolog and the WAM

Colmerauer’s Prolog spread quickly through the logic programming research community, but for several years it remained slow — too slow for practical applications beyond small demonstrations. The bottleneck was the interpretation overhead of unification (the pattern-matching mechanism Prolog uses to match clauses) and the backtracking search.

David Warren at Edinburgh solved the performance problem. In 1977, he built the first Prolog compiler — a system that translated Prolog programs to machine code rather than interpreting them — and demonstrated performance improvements of over an order of magnitude. His more influential contribution came in 1983: the Warren Abstract Machine (WAM), a virtual machine architecture specifically designed for Prolog execution.

The WAM defined a set of abstract instructions optimized for Prolog’s execution model — unification, choice points, deterministic execution — and provided an intermediate compilation target that could be efficiently translated to real machine code on any architecture. The WAM became the standard compilation target for Prolog implementations; virtually every production Prolog system built since 1983 uses the WAM or a direct descendant.

Edinburgh Prolog, developed by Warren and colleagues, was the standard from which most other Prolog implementations derived. The language specification evolved into ISO Prolog (1995), the formal standard. SWI-Prolog, developed by Jan Wielemaker at the University of Amsterdam from 1987 and still actively developed today, became the most widely used open-source implementation.

Unification: Prolog’s Core Mechanism

Prolog’s execution model is built on unification — the process of finding variable assignments that make two terms identical. When Prolog tries to match the query grandparent(tom, Who) against the rule grandparent(X, Z) :- parent(X, Y), parent(Y, Z), it unifies X with tom and Z with Who. This variable binding is carried forward into the subgoals. If the search succeeds, Who gets bound to a specific value; if it fails, Prolog backtracks and tries other clauses. Unification is more powerful than simple pattern matching — it can match structures of arbitrary complexity in a single operation — and it is what gives Prolog its distinctive character.

The Fifth Generation Project: Prolog’s Moment in the Sun

In 1982, Japan’s Ministry of International Trade and Industry (MITI) announced the Fifth Generation Computer Systems project — a ten-year, $400 million initiative to build computers fundamentally more powerful than anything then existing, capable of natural language understanding, knowledge-based reasoning, and automatic theorem proving. The project would deploy a massively parallel hardware architecture designed from the ground up to execute logic programs efficiently.

The language chosen as the Fifth Generation’s software foundation was a variant of Prolog called KL1 (Kernel Language 1), which added parallel execution constructs to standard Prolog. The Fifth Generation project gave Prolog enormous international visibility. In the US and Europe, governments and corporations responded with their own AI research funding programs — partly motivated by fear that Japan would achieve an insurmountable lead in artificial intelligence.

Research into Prolog implementations, parallel logic programming, and logic-based databases accelerated dramatically. Academic AI courses in the mid-1980s frequently taught Prolog as the language of AI. The language was used for expert systems, natural language interfaces, and program analysis tools.

The Fifth Generation project did not deliver on its ambitions. The parallel Prolog execution it depended on was far harder to achieve than anticipated. KL1 programs were difficult to write and often ran no faster on the parallel hardware than sequential Prolog on conventional machines. By the early 1990s, the project had produced valuable research but not the AI computers that MITI had promised. It was wound down in 1992.

The project’s failure — and the broader disappointment of the AI Winter of the late 1980s and early 1990s — hit Prolog’s commercial ecosystem hard. Companies that had built products on Prolog found their markets shrinking as AI enthusiasm cooled. Expert system shells built on Prolog were superseded by cheaper and more practical software tools.

What Prolog Did and Did Not Achieve

Despite its commercial disappointments, Prolog left real marks on computing.

IBM’s Watson, the Jeopardy!-playing AI system, used Prolog components for certain reasoning and natural language analysis tasks alongside statistical machine learning. Watson’s DeepQA architecture incorporated multiple specialized reasoning modules, and Prolog’s efficiency for certain types of inference made it a natural choice for some of them.

Erlang (1986), developed at Ericsson for telecommunications systems, was designed by Joe Armstrong who cited Prolog as a major influence. Erlang’s pattern matching on function clauses — the ability to define different behavior for different argument patterns — is a direct descendant of Prolog’s clause matching. Erlang went on to become an influential systems language for highly concurrent applications.

Answer Set Programming (ASP), developed in the 1990s and 2000s, extended Prolog’s declarative approach with more powerful semantics for negation and non-monotonic reasoning. ASP is used for scheduling, configuration, and constraint satisfaction problems where its declarative style provides genuine advantages over procedural approaches.

Prolog is still used — for database query optimization, theorem proving, parsing, and in academic settings. SWI-Prolog is actively maintained and handles programs of significant complexity. The Logtalk object-oriented extension to Prolog supports modern software engineering practices while preserving the declarative core.

Why Logic Programming Didn’t Rule the World

Prolog’s failure to dominate programming had several causes beyond poor timing and the AI Winter.

Performance was a genuine obstacle. Even with the WAM, Prolog programs in the 1980s were typically slower than equivalent C programs by a factor of ten to a hundred. For the performance-critical applications of the era — database query engines, operating systems, scientific computation — this was disqualifying.

More fundamentally, most programming problems are not naturally expressed as constraint satisfaction over logical relations. A program that renders graphics, sorts a large dataset, or processes network packets has a clear procedural structure: do this step, then that step, transform this buffer, send that packet. Forcing such programs into a declarative framework produces awkward code and poor performance. Prolog excels at problems with complex relational structure and multiple constraints — combinatorial scheduling, natural language parsing, program verification — but these are a minority of the programming tasks that need to be done.

The absence of a strong standard library and ecosystem also mattered. Programs needed I/O, network access, GUI toolkits, database connections. Prolog’s I/O facilities were minimal and non-standard; building practical applications required mixing Prolog with other languages, which undermined the purity of the declarative approach.

Yet the vision Prolog embodied — that programs should describe what is true rather than how to compute — has never disappeared. It resurfaces in SQL, in functional programming’s emphasis on pure functions, in modern constraint programming systems. Every time a programmer writes a declarative specification and lets a system figure out the execution, they are working in the tradition Colmerauer and Kowalski established in the early 1970s.