Prolog
Last reviewed
May 4, 2026
Sources
18 citations
Review status
Source-backed
Revision
v1 · 4,003 words
Improve this article
Add missing citations, update stale details, or suggest a clearer explanation.
Suggest edit
CtrlK
Last reviewed
May 4, 2026
Sources
18 citations
Review status
Source-backed
Revision
v1 · 4,003 words
Add missing citations, update stale details, or suggest a clearer explanation.
Prolog (a contraction of the French PROgrammation en LOGique) is a logic programming language strongly associated with artificial intelligence research, computational linguistics, and automated reasoning. A Prolog program is not a sequence of imperative steps but a collection of facts and rules, which the system uses to answer queries by attempting to prove goals through search and unification. The name was coined by Philippe Roussel in 1972 at the Université d'Aix-Marseille, where Alain Colmerauer's group built the first interpreter as part of a larger effort on French-language man-machine dialogue.
Prolog grew out of two converging research programmes of the early 1970s: natural language processing in France and theorem proving in Britain. The theoretical core, that a useful subset of first-order logic called Horn clauses could be executed as a programming language, was articulated by Robert Kowalski at the University of Edinburgh, while the practical realisation came from Colmerauer and Philippe Roussel in Marseille. Within a decade Prolog had spread across European AI laboratories, become the implementation language of choice for expert systems and natural language interfaces, and been chosen as the substrate of Japan's Fifth Generation Computer Systems project.
Though commercial visibility receded after the 1990s, Prolog remains the canonical introduction to the declarative paradigm in undergraduate AI courses, the basis of industrial constraint solvers, and a building block of recent neuro-symbolic systems such as DeepProbLog. Its descendants, including Erlang, Mercury, and Datalog, have spread its ideas to telecommunications, formal verification, and database query systems.
| Field | Detail |
|---|---|
| Paradigm | Logic programming, declarative |
| Family | First-order logic; Horn clause subset |
| Designed by | Alain Colmerauer and Philippe Roussel; theoretical foundation by Robert Kowalski |
| First appeared | 1972, at the Université d'Aix-Marseille (Luminy) |
| Stable standard | ISO/IEC 13211-1:1995 (General Core); ISO/IEC 13211-2:2000 (Modules); subsequent technical corrigenda |
| Typing discipline | Dynamic, untyped (typed extensions exist in dialects such as Mercury and Visual Prolog) |
| Common file extensions | .pl, .pro, .P |
| Influenced by | Resolution theorem proving, Planner, predicate logic |
| Influenced | Erlang, Mercury, Datalog, Visual Prolog, Curry, Picat, Twelf |
| Major implementations | SWI-Prolog, GNU Prolog, SICStus Prolog, YAP, ECLiPSe, Tau Prolog, Trealla Prolog, Scryer Prolog, Visual Prolog |
| License | Varies by implementation: BSD-2 (SWI-Prolog), LGPL/GPL (GNU Prolog), MIT (Tau Prolog), commercial (SICStus, Visual Prolog) |
Prolog's roots lie in the meeting of two research traditions. In Edinburgh, a group around Bernard Meltzer was working on automated theorem proving following John Alan Robinson's 1965 paper introducing the resolution principle and the unification algorithm. Within that group, Robert Kowalski developed the procedural interpretation of Horn clauses: the observation that an implication H :- B1, ..., Bn can be read either as a logical statement or as a procedure call. This reading, refined together with the SL-resolution theorem prover developed by Kowalski and Donald Kuehner in 1971, made it plausible that a fragment of predicate logic could serve directly as a programming language.
At the University of Montreal in the late 1960s, Alain Colmerauer had built a linguistic formalism called Q-Systems used in the TAUM-METEO machine translation prototype. After moving to the Université d'Aix-Marseille in Luminy in 1970, he assembled a team aiming to let users converse with a computer in French. The team needed an inference engine, and after a one-week visit by Kowalski to Marseille in 1971, Colmerauer's student Philippe Roussel implemented a first interpreter in 1972, written in Algol-W on an IBM 360/67. Roussel coined the name Prolog as a contraction of PROgrammation en LOGique. Kowalski returned for two months in 1972 to collaborate on the design. A more efficient Fortran interpreter, completed by Battani and Meloni in 1973, became the basis of "Marseille Prolog" as most users encountered it. The Marseille system already contained the ingredients that later became standard: Horn-clause structure, depth-first search with chronological backtracking, and a unification algorithm.
Through the mid 1970s Prolog spread across European AI laboratories, particularly Edinburgh, Lisbon, and Budapest. The key practical advance was DEC-10 Prolog, written by David H. D. Warren with Fernando Pereira and Luis Pereira at Edinburgh. Warren completed his PhD on it in 1977 under Robert Kowalski and Donald Michie. DEC-10 Prolog was the first Prolog compiler (earlier systems were interpreters) and produced code competitive with imperative languages of the period. The syntactic conventions it introduced (operators, the :- clause separator, [Head|Tail] list notation) became the de facto Prolog syntax, known as Edinburgh syntax, and carried into the ISO standard.
In 1983 Warren designed an abstract machine, presented at U.C. Berkeley that October, decomposing Prolog execution into a small instruction set over a specific memory architecture. The Warren Abstract Machine, or WAM, became the de facto compilation target for nearly every serious Prolog implementation that followed. SICStus, SWI-Prolog, GNU Prolog, YAP, and Scryer Prolog all run a WAM or close descendant. Hassan Ait-Kaci's 1991 monograph Warren's Abstract Machine: A Tutorial Reconstruction is the standard reference.
In 1982 Japan's Ministry of International Trade and Industry launched the Fifth Generation Computer Systems (FGCS) project, a ten-year initiative to build massively parallel "inference machines" running logic programs. MITI established the Institute for New Generation Computer Technology (ICOT) with the major Japanese computer companies, with a budget of roughly 57 billion yen (around US$320 million). The choice of Prolog and logic programming as the software substrate raised the language's international visibility and triggered defensive funding in the United States (DARPA's Strategic Computing Initiative) and Europe (ESPRIT, Alvey).
Under Ehud Shapiro's influence after his 1982 visit to ICOT, FGCS pivoted from parallel Prolog toward concurrent logic programming. Kazunori Ueda's Guarded Horn Clauses became the basis for KL1, the kernel language used on the project's parallel inference machines. FGCS produced significant research on parallel logic programming and constraint solving but never produced commercially competitive hardware. Its end in 1992 (with a transitional period to 1994) coincided with the decline of expert systems and the broader retreat from symbolic AI characterising the second AI winter.
A decade of work in ISO/IEC JTC1/SC22/WG17 produced ISO/IEC 13211-1:1995, the first international standard for Prolog, covering syntax, semantics, built-in predicates, and conformance requirements for what the standard calls a "general core" Prolog processor. A second part, ISO/IEC 13211-2:2000, added a module system. In practice no major implementation conforms exactly to either part; almost every system extends the standard with implementation-specific built-ins. Scryer Prolog and Trealla Prolog are modern systems that explicitly target strict ISO conformance.
A Prolog program consists of a database of clauses (facts and rules) plus queries posed against it. The system answers a query by searching for a proof of the goal, using SLD resolution (Selective Linear resolution for Definite clauses) as its inference rule and Robinson-style unification to instantiate variables. The defining features follow from this model.
A fact asserts that some relation holds: parent(tom, bob). A rule is a Horn clause with a single positive head and zero or more body literals: grandparent(X, Y) :- parent(X, Z), parent(Z, Y). A program is read as a conjunction of clauses, each universally quantified over its variables. Variables begin with a capital letter or underscore; constants and predicate names start with a lowercase letter.
A query is a goal posed against the database, typically introduced at the top level with ?-. The system attempts to prove the goal by repeatedly selecting a literal, finding a clause whose head unifies with that literal, and replacing the literal with the clause body. This is SLD resolution; the linear restriction (always resolving against the current goal) is what makes implementation feasible. Prolog uses depth-first search with chronological backtracking, and the order of clauses and goals is significant.
Unification is the operation of finding a most general substitution that makes two terms syntactically identical. John Alan Robinson introduced it along with the resolution principle in his 1965 paper; Prolog uses it as a core primitive via the operator =. Standard implementations omit the occurs check by default for performance, so X = f(X) succeeds with a cyclic term rather than failing as the formal algorithm requires. Sound unification is available as unify_with_occurs_check/2.
When a unification or subgoal fails, Prolog backtracks to the most recent choice point and tries the next alternative. The cut, written !, is a meta-operator that commits to all choices made between itself and the head of the clause, pruning the search tree. It is controversial because it breaks the declarative reading of clauses, but it is essential to writing efficient Prolog. The combination of cut with negation gives negation as failure, written \+ Goal: a goal succeeds if Prolog cannot prove its negand.
Lists in Prolog are recursive structures built from a cons-style constructor and the empty-list constant []. The Edinburgh syntax [Head|Tail] introduced by Warren is universal. Pattern matching by unification means most list-processing predicates are written by case analysis on [] versus [H|T]. The same predicate often runs in multiple modes: append(?, ?, +X), for example, enumerates all decompositions of a given list into prefix and suffix.
Programs can manipulate the database at runtime through assertz/1, asserta/1, and retract/1. Meta-predicates such as findall/3, bagof/3, and setof/3 collect all solutions to a goal into a list. call/1 turns a term into an executable goal, giving Prolog higher-order programming on top of its first-order core.
Definite Clause Grammars (DCGs), introduced by Pereira and Warren in 1980, are syntactic sugar for context-free and context-sensitive grammars expressed as Prolog rules. A DCG rule s --> np, vp. is rewritten into a regular clause that threads an input list through the body. DCGs were one of Prolog's earliest practical wins in natural language parsing.
Constraint Logic Programming (CLP) generalises unification to constraint solving over specific domains. The CLP scheme of Jaffar and Lassez (1987) parameterises Prolog by a constraint domain. Standard instantiations include CLP(FD) for finite-domain integers, CLP(R) and CLP(Q) for real and rational arithmetic, and CLP(B) for Boolean constraints. Modern systems ship mature CLP libraries used in industrial scheduling, planning, and verification.
Tabling, or memoisation, caches subgoal evaluations to avoid recomputation and to give terminating semantics to programs that would loop under standard SLD resolution. XSB introduced tabling as a core feature; YAP, B-Prolog, SWI-Prolog, and Ciao followed. Tabled Prolog provides a clean implementation of bottom-up Datalog and underlies the well-founded semantics for negation.
The canonical introduction to Prolog is a small genealogy database, a shape of code that appears in nearly every Prolog textbook.
% Facts
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
% Rules
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
Querying the program at the top level returns either true (with bindings) or false:
?- grandparent(tom, X).
X = ann ;
X = pat.
?- ancestor(tom, jim).
true.
The semicolon asks for the next solution. List operations follow the same recursive pattern:
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
append([], L, L).
append([H|T], L, [H|R]) :- append(T, L, R).
reverse(L, R) :- reverse(L, [], R).
reverse([], Acc, Acc).
reverse([H|T], Acc, R) :- reverse(T, [H|Acc], R).
A Definite Clause Grammar parses a small fragment of English and builds a parse tree:
sentence(s(NP, VP)) --> noun_phrase(NP), verb_phrase(VP).
noun_phrase(np(D, N)) --> determiner(D), noun(N).
verb_phrase(vp(V, NP)) --> verb(V), noun_phrase(NP).
determiner(d(the)) --> [the].
noun(n(dog)) --> [dog].
noun(n(cat)) --> [cat].
verb(v(sees)) --> [sees].
?- phrase(sentence(Tree), [the, dog, sees, the, cat]).
Tree = s(np(d(the), n(dog)), vp(v(sees), np(d(the), n(cat)))).
A short CLP(FD) example finds distinct integers between 1 and 9 that sum to a target:
:- use_module(library(clpfd)).
solve(Vars, Target) :-
Vars ins 1..9,
all_distinct(Vars),
sum(Vars, #=, Target),
label(Vars).
Dozens of Prolog implementations have appeared since 1972. The table lists active systems with representative commercial and open source offerings.
| Implementation | Principal author or vendor | First release | License | Notes |
|---|---|---|---|---|
| SWI-Prolog | Jan Wielemaker (University of Amsterdam, later VU and CWI) | 1987 | BSD-2 | Largest open source community; web, C, and Java integration; CLP libraries |
| SICStus Prolog | RISE Research Institutes of Sweden (formerly SICS) | 1986 | Commercial | ISO-conformant; widely used in industry; strong CLP(FD) |
| GNU Prolog | Daniel Diaz | 1999 | LGPL or GPL (dual) | Native code compiler; built-in CLP(FD); FSF GNU project |
| YAP | Vitor Santos Costa, Luis Damas, Ricardo Rocha and others | mid-1980s | Artistic / LGPL | High-performance WAM with tabling and parallelism |
| ECLiPSe | IC-Parc, then Cisco; now community | 1990s | Mozilla Public License | Constraint logic programming platform |
| Tau Prolog | Jose Riquelme | 2017 | MIT | Pure JavaScript implementation; runs in browser and Node.js |
| Trealla Prolog | Andrew Davison | 2020 | MIT | Compact ISO-targeted interpreter in C |
| Scryer Prolog | Mark Thom and contributors | 2017 | BSD-3 | Rust-based; aims for full ISO conformance |
| XSB | David S. Warren and others (Stony Brook) | early 1990s | LGPL | Pioneered tabling; deductive database focus |
| Ciao | UPM CLIP group | 1995 onward | LGPL | Modular, multi-paradigm, strong assertion language |
| B-Prolog | Neng-Fa Zhou | 1994 | Free for non-commercial | Action rules and matching trees |
| Visual Prolog | Prolog Development Center (PDC), Denmark | 1996 (preceded by PDC Prolog 1986 / Turbo Prolog) | Commercial; free Personal Edition | Strongly typed, object-oriented dialect for Windows |
SWI-Prolog and SICStus together account for the majority of contemporary academic and industrial use. Tau Prolog, Trealla, and Scryer represent recent open source efforts to bring Prolog into modern deployment environments.
Prolog has been used across many domains. The most influential are summarised below.
Natural language was Prolog's first application and remains its most natural fit. Definite Clause Grammars allow context-free and mildly context-sensitive grammars to be expressed directly as Prolog rules, with parsing falling out as ordinary goal evaluation. Through the 1980s and 1990s most academic work in computational linguistics either used Prolog directly or used a logic-programming formalism implemented on top of it. The connection to NLP persists in grammar engineering systems such as the LKB and ALE.
IBM's Watson question answering system, which won the Jeopardy! Man vs. Machine Challenge in February 2011, used Prolog for parts of its question and passage analysis pipeline. The 2011 paper Natural Language Processing With Prolog in the IBM Watson System by Adam Lally and colleagues describes Watson's use of Prolog for pattern matching against parse trees produced by the ESG parser. Prolog's depth-first search, backtracking, and recursive rules over reachability in parse trees suited the rule-driven detection of question focus, lexical answer types, and entity relations within the broader Java and C++ system. (IBM Watson)
In the 1980s Prolog was a standard platform for expert systems, particularly in Europe. Expert system shells written in Prolog used its built-in pattern matching and backtracking to implement forward and backward chaining rule engines. Mycin-style diagnostic systems, configuration tools, and legal-reasoning prototypes appeared in volume. Although the expert-system industry collapsed with the 1990s AI winter, Prolog persists as a substrate for formal ontologies, particularly in biomedical informatics.
Constraint logic programming put Prolog into industrial scheduling, planning, transport, and verification work. SICStus Prolog and ECLiPSe ship industrial-grade CLP(FD) solvers used in airline crew scheduling, telecommunications planning, and timetabling.
The close relationship between Prolog and resolution theorem proving made the language an obvious vehicle for proof assistants and analysis tools. The Soufflé Datalog engine, used in static analysis of Java by tools such as Doop, descends from the deductive-database tradition that grew out of Prolog. (Automated reasoning)
Prolog has been used to build and query large biomedical knowledge bases, particularly in the OBO Foundry of biological ontologies. The Blip and Thea-OWL libraries built on SWI-Prolog provide ontology editing and querying environments used by curators.
Prolog's ideas about pattern matching, immutable variables, and rule-based computation have spread across the broader programming language ecosystem.
| Language | Relationship to Prolog |
|---|---|
| Erlang | Joe Armstrong, Robert Virding, and Mike Williams built the first prototype of Erlang in Prolog at Ericsson between 1986 and 1988, after Roger Skagervall pointed out that Armstrong's telephony notation already had Prolog-like structure. The Prolog prototype proved too slow for production and was reimplemented in C by 1989, but Erlang's syntax (clauses, pattern matching, atoms) clearly inherits from Prolog. |
| Mercury | A pure logic and functional language designed at the University of Melbourne by Zoltan Somogyi and Fergus Henderson, first released in 1995. Mercury keeps Prolog's clausal syntax but adds strong static typing, mode declarations, determinism categories, and a module system. |
| Datalog | A subset of Prolog without compound terms or function symbols and with stratified negation, designed for decidable bottom-up evaluation. Datalog underlies modern systems such as Soufflé, LogicBlox, and the recursion features of SQL. |
| Curry | A functional logic language by Michael Hanus and others, combining Haskell-style syntax and types with Prolog-style nondeterminism and unification. |
| Picat | A multi-paradigm language by Neng-Fa Zhou and Jonathan Fruhman that grew out of B-Prolog, blending logic, functional, constraint, and imperative programming. |
| Twelf | A metalogical framework for deductive systems, implemented in Standard ML but operating on a logic-programming core with higher-order unification. |
| Oz | A multiparadigm research language at UCL Louvain combining constraint and logic programming with concurrency and functional features. |
| KL1 | The kernel language of Japan's Fifth Generation project, derived from Guarded Horn Clauses. |
Indirect influence runs further. Pattern matching with destructuring binding in Clojure, Scala, Rust, and Python's match statements all draw on the unification idea Prolog made commonplace.
The canonical Prolog textbooks have shaped how generations of students encountered both the language and the broader subject of logic programming. The three most influential are still in print.
| Book | Authors | First edition | Notes |
|---|---|---|---|
| Programming in Prolog | William F. Clocksin and Christopher S. Mellish | Springer-Verlag, 1981 | First textbook on Prolog. Editions in 1984, 1987, 1994, and a fifth (Using the ISO Standard) in 2003. |
| The Art of Prolog | Leon Sterling and Ehud Shapiro | MIT Press, 1986 (2nd ed. 1994) | Advanced techniques including meta-interpreters and incremental development. |
| Prolog Programming for Artificial Intelligence | Ivan Bratko | Addison-Wesley, 1986 (4th ed. 2012) | The standard textbook for AI applications: search, expert systems, planning, machine learning, NLP. |
Other frequently cited works include Richard O'Keefe's The Craft of Prolog (MIT Press, 1990) and Learn Prolog Now! by Patrick Blackburn, Johan Bos, and Kristina Striegnitz (College Publications, 2006). Kowalski's Logic for Problem Solving (North-Holland, 1979) remains the standard introduction to the underlying view of computation.
Prolog's commercial visibility peaked in the late 1980s alongside the expert-systems boom and the publicity around Japan's Fifth Generation project. The retreat that followed had overlapping causes. Expert systems proved fragile when knowledge bases were incomplete; dedicated AI hardware lost on cost and performance to general-purpose workstations; and the rise of statistical and connectionist methods in the 1990s, which culminated in the deep learning revolution after 2012, redirected attention away from symbolic logic programming. Borland (Turbo Prolog) and Quintus exited or were absorbed, and the vendor ecosystem consolidated around SICStus, ECLiPSe, Visual Prolog, and the academic open source projects.
Prolog nonetheless remained the natural language for several niches. Constraint logic programming continued to grow with applications in scheduling, verification, and combinatorial optimisation. Educational use as the first declarative language in undergraduate AI courses persisted, particularly in Europe. SWI-Prolog has been continuously developed since 1987 and now anchors a substantial international community.
The 2020s brought a new wave of interest under the heading of neuro-symbolic artificial intelligence. Deep learning systems excel at perception but struggle with multi-step deductive reasoning, calibrated uncertainty over discrete structures, and verifiable knowledge. DeepProbLog, introduced by Robin Manhaeve and colleagues at KU Leuven in 2018 and extended through 2021, integrates ProbLog (a probabilistic Prolog) with neural networks via neural predicates: probabilistic facts whose probabilities are computed by neural network outputs, with gradients flowing through probabilistic inference back to the network parameters for end-to-end training. IBM's Logical Neural Networks pursue a related goal by embedding weighted first-order rules in differentiable network structures. Recent systems also combine large language models with Prolog as a back-end reasoner, using the LLM to translate natural language queries into Prolog clauses solved by a standard engine. The Prolog tradition of declarative knowledge representation and sound inference is again supplying capabilities that purely neural systems lack.