Prolog

• 1. Introduction

  ›

  Prolog asks a strange question of any programmer who encounters it for the first time: what if, instead of telling a computer how to do something, you simply told it what is true? That question sits at the heart of a language born in 1972 at the Faculty of Sciences of Luminy, part of Aix-Marseille II University in France. Alain Colmerauer and Philippe Roussel built Prolog not as a conventional tool for writing step-by-step instructions, but as a way to encode facts, rules, and relations, then let the machine figure out how to reason through them.

  The name itself was Philippe Roussel's invention, chosen at the suggestion of his wife. Programmation en logique: programming in logic. That phrase captured something genuinely different. Most languages of the era told a machine what to do, in what order, by what means. Prolog told it what was true, and trusted it to find the answer.

  Where did this idea come from, and why did it split the computing world along national lines? How does a language built on logical inference end up inside Watson, the IBM system that defeated human champions on Jeopardy? And what does it mean that Prolog remains, more than half a century after its creation, the most popular logic programming language in existence?

• 2. Origins in Logic

  ›

  Robert Kowalski supplied the theoretical backbone that made Prolog possible. His procedural interpretation of Horn clauses gave Colmerauer and Roussel the bridge between formal logic and executable computation. A Horn clause of the form H :- B1, ..., Bn reads as a procedure: to prove H, prove B1 and then B2 and so on through Bn. That simple reading transformed a mathematical formalism into something a computer could act on.

  The first working Prolog system was implemented in 1972. Gerard Battani and Henri Meloni wrote the original interpreter in Fortran. David H. D. Warren then carried that interpreter to the University of Edinburgh, where he built a new front-end that defined the Edinburgh Prolog syntax still used by most implementations today. Warren also created the first Prolog compiler, the DEC-10 Prolog, in collaboration with Fernando Pereira. His later work generalised those ideas into the Warren Abstract Machine, a design that went on to influence how Prolog code is compiled across many subsequent systems.

  Prolog's early history was not purely academic. It grew partly from a desire to reconcile two competing philosophies of knowledge representation. In North America during the late 1960s and early 1970s, the dominant approach treated knowledge procedurally. Prolog's creators wanted to show that a declarative approach, grounded in logic, could do the same work. That tension between the two camps never fully resolved, and it would soon play out on a geopolitical stage.

• 3. The Continental Divide

  ›

  European AI researchers threw their weight behind Prolog. American researchers favored Lisp. The rivalry reportedly generated something the source describes as many nationalistic debates on the merits of the two languages. Behind those debates lay a genuine philosophical disagreement about what a program should be: a set of instructions, or a body of knowledge.

  The debate found its most concrete expression in Japan. The Fifth Generation Computer Systems project, known as FGCS, chose a Prolog variant called Kernel Language as the foundation of its first operating system. The project aimed at ambitious performance targets: machines operating at between 0.1 and 1 GLIPS, or giga logical inferences per second. In 1982, the benchmark for conventional machines sat at between 10,000 and 100,000 logical inferences per second, so the targets represented a leap of several orders of magnitude. The Institute for New Generation Computer Technology estimated that one logical inference required roughly 100 operations on a conventional machine. The plan was to end the project in 1992 with a machine running 1,000 processors and achieving 1 GLIPS in total, which meant at least 1 MLIPS per processor.

  The FGCS also prompted much of the modern development of Prolog, injecting energy and resources into the language at a moment when it might otherwise have remained a research curiosity. Sega, meanwhile, took the language in a different direction entirely. In 1986, the company released the Sega AI Computer for the Japanese market, using Prolog to parse natural language input in Japanese via a touch pad.

• 4. How Prolog Reasons

  ›

  At runtime, execution begins with a single goal posted by the user, called the query. The Prolog engine then tries to find a resolution refutation of the negated query using a method called SLD resolution. If the negated query can be refuted, the original query is a logical consequence of the program, and the engine reports all generated variable bindings to the user.

  When multiple clause heads can match a given call, the system creates a choice-point, tries the first alternative, and continues. If any goal fails during execution, the engine discards all variable bindings made since the most recent choice-point and tries the next alternative. This strategy is called chronological backtracking, and it gives Prolog programs a distinctive quality: the ability to run, in a sense, both forwards and backwards across the relations they define.

  Negation works through a mechanism called negation as failure. The built-in predicate \+/1 attempts to prove a goal and succeeds precisely when that proof cannot be found. This allows non-monotonic reasoning but comes with a limitation: the approach is sound only when the argument contains no unbound variables. An unbound variable opens the door to incompleteness in a way that can surprise programmers accustomed to conventional logic.

  Iterative algorithms are expressed through recursive predicates rather than loops. An ancestor relation, for instance, can be defined in two clauses: X is an ancestor of Y if X is a parent of Y, or if X is a parent of some Z who is itself an ancestor of Y. The second clause calls the predicate it is defining, making it recursive, and the engine handles the rest.

• 5. Reach and Limits

  ›

  Prolog has been used for theorem proving, expert systems, term rewriting, type systems, automated planning, question answering, and natural language processing. That breadth has not translated into widespread adoption across the software industry. Most Prolog applications are small by industrial standards, with few exceeding 100,000 lines of code.

  Two structural problems explain the gap. First, not all Prolog compilers support modules, and the module systems that do exist are mutually incompatible. Virtually no implementation adheres to the modules section of the ISO standard. Most have instead adopted the Quintus/SICStus module system as a de facto standard, but even that convergence leaves subtle differences in semantics between implementations. Portability within what the source calls the Edinburgh/Quintus derived family of implementations improved meaningfully after 2007, allowing portable real-world applications to be maintained, but the problem has never been fully solved.

  Second, Prolog carries a performance penalty compared to conventional languages. Its non-deterministic evaluation strategy creates friction when a computation is intrinsically deterministic. Programmers frequently reach for the cut operator and other extralogical constructs to recover performance, but those constructs require a procedural reading of the program to understand correctly. They also destroy one of Prolog's central attractions: the ability to run programs backwards and forwards across a relation. Pure Prolog is not actually pure in practice; the order of clauses matters, execution depends on it, and many real programs are written to conform to Prolog's depth-first search order rather than as genuinely declarative logic.

• 6. Watson and the Graph Database

  ›

  IBM's Watson system, which drew wide public attention for its question-answering performance, was written in several languages including Prolog. The system ran on SUSE Linux Enterprise Server 11 using the Apache Hadoop framework for distributed computing, with IBM's DeepQA software and the Apache UIMA framework handling unstructured information management. Prolog's specific role was pattern matching over natural language parse trees.

  The Watson developers stated their reasoning directly: they needed a language for conveniently expressing pattern matching rules over parse trees and other annotations such as named entity recognition results, along with a technology that could execute those rules efficiently. They found Prolog to be the ideal choice for the language due to its simplicity and expressiveness.

  Open source graph database TerminusDB is also implemented in Prolog, designed for collaboratively building and curating knowledge graphs. Prolog is additionally used in the low-code development platform GeneXus. These deployments illustrate a consistent pattern in Prolog's industrial footprint: it tends to appear not as the primary language of a system but as the layer handling the most linguistically complex or relationally intricate part of the work, the piece where pattern matching over structured symbolic data is the binding constraint.

• 7. A Language Still Evolving

  ›

  ISO standardisation gave Prolog a more stable footing than it had in its first two decades. ISO/IEC 13211-1 was published in 1995, aiming to standardise the practices already in use across the many existing implementations. Three corrigenda followed: Cor.1:2007, Cor.2:2012, and Cor.3:2017. ISO/IEC 13211-2, published in 2000, added module support to the standard. The most recent addition to the standard family, 13211-3, was published in 2025.

  Higher-order programming extended the language beyond the boundaries of first-order logic. ISO Prolog now includes built-in higher-order predicates such as call/1 through call/3, findall/3, setof/3, and bagof/3. Higher-order programming style in Prolog was pioneered in HiLog and in the language known as lambda Prolog. Tabling, a memoisation technique implemented in systems including B-Prolog, XSB, SWI-Prolog, YAP, and Ciao, reduces execution time by storing intermediate results in a table and reusing them rather than re-running resolution each time a subgoal is re-encountered.

  Constraint logic programming, which extends Prolog with concepts from constraint satisfaction, has proven particularly useful for large-scale combinatorial optimisation problems and for applications in industrial settings such as automated time-tabling and production scheduling. Most Prolog systems ship with at least one constraint solver for finite domains, and many include solvers for rational numbers as well. The Janus interface, initially developed for XSB by Anderson and Swift and since adopted as a joint initiative by the XSB, Ciao, and SWI-Prolog teams, provides a bi-directional bridge between Prolog and Python, opening a path into the data science ecosystem that Prolog's original architects could not have anticipated.