Prolog and Logic Programming: Computing by Stating Relations
Prolog turned logical relations and inference into a programming model, emerging from collaboration between Alain Colmerauer's Marseille group and Robert Kowalski's work on the procedural interpretation of logic.
Prolog grew from attempts to make logic operational
In the late 1960s and early 1970s, artificial-intelligence researchers were exploring theorem proving, natural-language processing and formal logic. Alain Colmerauer’s Marseille group had experience with parsing and language transformation, while Robert Kowalski was developing a procedural interpretation of logical clauses.
The Computer History Museum’s Prolog preservation archive describes the interaction between the Marseille and Edinburgh traditions and identifies Colmerauer’s natural-language work, Robinson’s resolution method and Kowalski’s logic-programming ideas as important ingredients.[1]
The language was created through collaboration, not one isolated invention
Prolog’s history is best understood as a synthesis. Colmerauer and Philippe Roussel built the early language and interpreter in Marseille, while Kowalski supplied theoretical ideas that clarified how logical clauses could act like executable procedures.
Programs were expressed as facts and rules
Instead of writing a sequence of imperative commands, a Prolog programmer states relations. Facts describe what is known; rules describe how one relation follows from others. A query asks whether a goal can be satisfied under those declarations.
This changes the programmer’s perspective. The program describes a logical problem space, while the Prolog engine performs a search for substitutions and rule applications that make the goal succeed.
Unification connects symbolic structures
Unification finds substitutions that make symbolic terms match. It gives variables in Prolog a role very different from mutable storage locations in imperative languages. A variable can stand for an unknown term whose value is constrained by relationships.
Resolution gave the language an inference mechanism
Kowalski’s retrospective on the early years of logic programming describes how resolution and Horn-clause reasoning were interpreted procedurally, creating a bridge between logic as a specification formalism and logic as a way to execute computations.[2]
The interpreter searches clauses whose heads can unify with the current goal, replaces the goal with the rule’s body and continues recursively. Backtracking allows the system to explore alternative choices when one path fails.
Search order became part of practical semantics
Pure logic suggests that equivalent clause sets should describe the same relation, but an actual Prolog implementation must choose which rule and subgoal to try first. Clause order and goal order therefore affect termination and performance.
The first Prolog emerged in Marseille around 1972
Historical sources generally date the first Prolog to 1972 and credit Alain Colmerauer and Philippe Roussel with the Marseille implementation. The DTAI history of Prolog also recounts how Marseille code spread to other European groups through punched-card copies and later interpreters.[3]
The name came from programmation en logique, emphasizing that the language was intended to turn logical formulation into a programming practice.
Natural-language processing was an early application
The Marseille group used logic programming for language-analysis problems, where symbolic structures, grammars and alternatives made unification and backtracking especially natural.
Prolog separated declarative meaning from procedural behavior imperfectly but productively
A Prolog rule can often be read declaratively as a statement about a relation, while the same rule also drives a concrete search procedure. This duality became one of logic programming’s great attractions.
It also created practical pitfalls. A logically correct program can loop because of goal ordering, and control devices such as the cut operator deliberately affect search without changing the logical vocabulary. Prolog therefore never eliminated algorithmic reasoning; it relocated much of it into rule structure and search control.
Edinburgh became a major center for Prolog implementation and language style
The Software Preservation Group’s archive documents the later Edinburgh lineage, including implementations and historical materials that helped standardize a style of Prolog programming.[1] Different implementations developed distinct features, but the Edinburgh tradition strongly influenced later standards and teaching.
The language spread through AI research because symbolic representation and search were built into the programming model.
Prolog became central to the logic-programming boom of the 1980s
Japan’s Fifth Generation Computer Systems project and European AI programs elevated logic programming into a major research direction. Prolog systems were developed for expert systems, natural-language processing, databases and symbolic reasoning.
The Leuven history records the rapid spread of interpreters and compilers across research groups and the continuing evolution of Prolog implementations.[3]
Why Prolog belongs in the core history of programming languages
Prolog demonstrated a radically different answer to the question “what is a program?” Instead of primarily specifying a sequence of state-changing commands, the programmer could state relationships and allow an inference engine to search for solutions.[4][5]
The language never replaced imperative programming, but it permanently broadened the field. Logic variables, unification, rule-based execution and backtracking became foundational ideas in AI, constraint programming and symbolic systems.
Logic programming also influenced database query languages and constraint systems because relations can be viewed as both logical propositions and computable structures. Prolog’s particular search strategy is only one implementation choice, but the language made declarative relational programming concrete enough for generations of programmers to experiment with it directly.
Prolog also made nondeterminism feel ordinary. A program could describe several possible solutions and rely on the runtime to explore them, turning search from an explicit algorithmic framework into a built-in language behavior.
Prolog also made program execution visibly dependent on a search strategy. In an imperative language, the programmer usually writes the control order directly. In Prolog, a declarative set of clauses is paired with an engine that chooses goals, unifies terms and backtracks through alternatives. That separation encouraged researchers to ask which parts of a program express the problem itself and which parts merely guide the search for a solution. Constraint-logic languages later extended this idea by allowing variables to accumulate restrictions that specialized solvers propagate before a concrete value is chosen. The same intellectual lineage appears in rule engines, deductive databases and symbolic reasoning systems. Prolog’s practical quirks prevented logic programming from replacing conventional languages, but its model permanently expanded the design space of programming languages by treating inference as an execution mechanism rather than only as a tool for proving properties about programs.
Works Cited
- 01
- 02Robert Kowalski — The Early Years of Logic Programming researchgate.net
- 03KU Leuven DTAI — History of PROLOG dtai.cs.kuleuven.be
- 04Colmerauer and Roussel — The Birth of Prolog, historical archive softwarepreservation.org
- 05SWI-Prolog — The Prolog Language and Environment swi-prolog.org
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead