Logic programming is a paradigm of computer programming based on formal logic, where programs consist of sets of logical assertions and inference rules used to derive conclusions. Instead of specifying step‑by‑step instructions, the programmer declares facts and relationships (e.g., Horn clauses), and the system uses automated theorem proving—typically via resolution and unification—to answer queries. Originating from work in artificial intelligence and automated reasoning, logic programming is embodied most notably in the language Prolog, and has found applications in databases, natural language processing, and knowledge‑based systems. It belongs to the declarative programming family, emphasizing *what* to compute rather than *how*.
1.1 Early influences: formal logic and resolution
The roots of logic programming lie in the development of first‑order logic and automated theorem proving. In the 1960s, researchers such as Jacques Herbrand, Alan Robinson, and Melvin Fitting laid the groundwork. Robinson’s 1965 invention of the resolution principle provided a mechanical procedure for proving logical theorems. This method, combined with unification, allowed a computer to derive conclusions from a set of logical clauses. The idea of using resolution as a computational model was independently proposed by several researchers, including John McCarthy and J. A. Robinson.
1.2 Development of Prolog (1970s)
The first practical logic programming language, Prolog (from *Programmation en Logique*), was created in 1972 by Alain Colmerauer and Philippe Roussel at the University of Aix‑Marseille. Their work was influenced by Robi Robinson’s resolution and the formalism of Horn clauses. The early interpreter demonstrated the feasibility of using logical deduction to perform computations. In 1977, David H. D. Warren implemented the first efficient compiler for Prolog, known as the “Warren Abstract Machine” (WAM), which became the basis for many subsequent implementations.
1.3 Growth and standardization (1980s–1990s)
Throughout the 1980s, Prolog gained popularity in artificial intelligence research, especially in Europe and Japan. The Japanese Fifth‑Generation Computer Project (FGCS) adopted Prolog as a core language. Meanwhile, multiple dialects appeared. To unify these, the International Organization for Standardization (ISO) released the ISO Prolog standard in 1995 (ISO/IEC 13211‑1). This standardized syntax, control flow, and core predicates, improving portability across implementations.
2.1 Horn clauses and definite clauses
A Horn clause is a logical clause with at most one positive literal. In logic programming, programs are composed of *definite clauses* — Horn clauses with exactly one positive literal (the head) and zero or more negative literals (the body). This restricted form guarantees that resolution remains efficient and that every program has a unique minimal model. Clauses with no body (only a head) are called *facts*; those with a body are *rules*. For example, grandparent(X,Y) :- parent(X,Z), parent(Z,Y). is a definite clause.
2.2 Unification
Unification is the process of making two logical expressions identical by substituting variables with terms. In logic programming, unification is used to match a query clause against the head of a program clause. It is a symmetric, most‑general operation; the result is a *unifier* that, when applied, makes the two expressions equal. Unification is a central inference step in resolution and determines how variables are bound during query execution.
2.3 Resolution and SLD resolution
Resolution is a rule of inference that derives new clauses from existing ones by cancelling complementary literals. In logic programming, the operational semantics is given by SLD resolution (Selective Linear Definite clause resolution). SLD resolution selects a literal from the current goal, unifies it with the head of a program clause, replaces the literal with the clause’s body, and repeats until the goal is empty (success) or no clause matches (failure).
2.3.1 SLD derivations
An SLD derivation is a sequence of goals where each step applies SLD resolution. A derivation that ends with the empty goal is called a refutation and corresponds to a successful query. The sequence of substitutions produced along the derivation forms the computed answer. If a derivation does not terminate or reaches a dead end, the query fails. In Prolog, the search is performed depth‑first with backtracking (see 2.4.1).
2.3.2 SLDNF (negation as failure)
Standard SLD resolution handles only positive literals. To incorporate negation, logic programming uses negation as failure (NAF): a negative literal not P succeeds if all possible attempts to prove P fail (i.e., the goal P finitely fails). This is a non‑monotonic form of negation. SLD with negation as failure is abbreviated SLDNF. The semantics of NAF require careful treatment to avoid unsoundness, leading to concepts like stratification and well‑founded semantics (see 4.3).
2.4 Backtracking and search strategies
When multiple clauses can unify with a selected literal, the system must choose one. If the chosen branch later leads to failure, the system backtracks to the most recent choice point and tries an alternative clause. The order in which clauses are tried defines the search strategy.
2.4.1 Depth‑first search in Prolog
Prolog traditionally uses depth‑first search (DFS) with chronological backtracking. Clauses are tried in the order they appear in the program, and literals within a goal are processed left‑to‑right. DFS is simple to implement and memory‑efficient, but it can lead to infinite loops if the search space contains cycles. Programmers must order clauses and goals carefully to avoid non‑termination.
2.4.2 Cut operator and control
Prolog provides the cut operator (!) to prune the search space. A cut commits the system to the choices made since the parent goal was invoked, discarding remaining alternatives. This can improve efficiency and prevent unnecessary backtracking, but misuse can break the declarative reading of a program. Cuts are used for controlling behavior (e.g., implementing if‑then‑else) or optimising deterministic clauses.
3.1 Prolog
Prolog is the archetypal logic programming language. Its syntax uses Horn clauses, with :- separating head and body, and , for conjunction. Variables begin with an uppercase letter. Prolog implementations typically include built‑in predicates for input/output, arithmetic, and list manipulation.
3.1.1 Edinburgh Prolog vs. ISO Prolog
Early Prolog dialects varied. Edinburgh Prolog, developed at the University of Edinburgh, became a de facto standard in the 1980s, thanks to the widely used DEC‑10 compiler. The ISO standard (1995) later formalised the language, defining syntax, built‑ins, and module systems. Most modern Prolog systems conform to ISO Prolog while retaining Edinburgh‑compatible extensions.
3.1.2 Modern implementations (SWI‑Prolog, GNU Prolog)
SWI‑Prolog is a mature, open‑source implementation known for its extensive libraries, support for web programming, and development environment (SWISH). GNU Prolog is another popular compiler that generates native code via the WAM; it also implements constraint logic programming over finite domains (CLP(FD)). Other notable systems include SICStus Prolog, YAP, and Ciao.
3.2 Datalog
Datalog is a subset of logic programming designed for database querying. It omits complex terms (only variables and constants), function symbols, and the cut operator. Datalog programs are always terminating and are evaluated bottom‑up.
3.2.1 Syntax and restrictions
Datalog rules have the form head :- body where body is a conjunction of literals. No negation or recursion through arithmetics is allowed in pure Datalog. Extensions (e.g., stratified negation, constraints) are common. Datalog’s simplicity enables efficient set‑oriented evaluation using techniques like semi‑naïve evaluation.
3.2.2 Use in deductive databases
Datalog is the core language of deductive databases, which extend relational databases with recursive queries. Systems like DLV, Soufflé, and RDFox implement Datalog for data integration, ontology reasoning, and graph analytics. It is also used in program analysis and static code checking.
3.3 Constraint logic programming (CLP)
Constraint logic programming merges logic programming with constraint solving. Instead of pure unification, variables can be constrained by domains (e.g., integer intervals, real numbers). The inference engine interleaves logical deduction with constraint propagation and satisfaction.
3.3.1 CLP(R), CLP(FD)
CLP(R) handles constraints over real numbers using Simplex‑like algorithms. CLP(FD) reasons over finite domains of integers, using consistency techniques such as arc consistency. Both are available as libraries in Prolog systems (e.g., SWI‑Prolog’s clpfd).
3.3.2 Applications in combinatorial optimization
CLP is widely used for solving scheduling, resource allocation, and puzzle‑solving problems (e.g., Sudoku). The declarative nature allows programmers to state constraints directly without writing search algorithms. CLP solvers can also support global constraints (e.g., alldifferent) for more efficient pruning.
4.1 Model theory and least Herbrand model
The Herbrand universe is the set of all ground terms (variable‑free terms) that can be built from the program’s constants and functors. A Herbrand interpretation assigns truth values to ground atoms. For a definite logic program, there is a unique minimal Herbrand model — called the least Herbrand model — which contains exactly the ground atoms that are logical consequences of the program. This model serves as the declarative semantics of the program.
4.2 Proof theory and SLD resolution
The proof‑theoretic semantics is captured by SLD resolution. Soundness and completeness results show that any atom that is true in the least Herbrand model can be derived by an SLD refutation, and any derived atom is true in that model (for definite programs). This correspondence underlies the correctness of logic programming implementations.
4.3 Semantics of negation
Negation as failure introduces non‑monotonicity; the meaning of the program depends on the choice of which literals to treat as finitely failing. Several formal semantics have been developed.
4.3.1 Stratified negation
A program is stratified if clauses can be partitioned into layers such that negative literals refer only to lower layers. For stratified programs, the least model can be computed layer by layer using completion or iterated fixed‑point methods. Stratification ensures a clear, deterministic meaning.
4.3.2 Well‑founded semantics
The well‑founded semantics (WFS) provides a three‑valued model (true, false, undefined) for programs that are not stratified. It is considered the standard canonical semantics for (normal) logic programs with negation as failure. WFS handles recursion through negation elegantly and always exists.
4.4 Fixed‑point semantics and immediate consequence operator
The immediate consequence operator (TP) maps a set of ground atoms to the set of atoms that can be derived in one step of resolution. For definite programs, TP is monotonic, and its least fixed‑point (the smallest set closed under TP) equals the least Herbrand model. Iterating TP from the empty set yields a bottom‑up evaluation strategy.
5.1 Artificial intelligence and expert systems
Logic programming’s declarative nature makes it suitable for encoding knowledge and inferring new facts.
5.1.1 Rule‑based reasoning
Expert systems like MYCIN and XCON used rule‑based inference similar to Prolog’s Horn clauses. Logic programming allows the expression of if‑then rules, chaining them to deduce conclusions. Modern applications include legal reasoning and configuration systems.
5.1.2 Natural language parsing
Definite clause grammars (DCGs), a syntactic extension of Prolog, allow writing context‑free grammars with logical variables for feature‑based parsing. Prolog’s built‑in DCG support facilitates development of parsers for natural and formal languages.
5.2 Database querying and deductive databases
Datalog and full Prolog are used to express recursive queries that are difficult or impossible in SQL. Deductive database systems allow complex queries over large datasets with logic rules.
5.2.1 Datalog for data integration
Datalog is employed in data integration frameworks, such as the Datalog Educational System (DES) and Vadalog, for querying across heterogeneous databases. Its ability to express recursion and constraints suits data cleaning and ontology mediation.
5.3 Automated planning and scheduling
Logic programming languages like Prolog and answer set programming (ASP) are used for planning tasks. For example, the Planning Domain Definition Language (PDDL) can be translated into logic programs, and solvers use model‑finding to generate plans.
5.4 Bioinformatics and computational linguistics
In bioinformatics, logic programming is used for gene prediction, protein structure analysis, and pathway reasoning. Ciao Prolog and SWI‑Prolog have libraries for biological sequence analysis. In computational linguistics, DCGs and feature‑unification grammars (e.g., HPSG) are implemented in logic programming frameworks.
6.1 Inductive logic programming (ILP)
ILP combines logic programming with machine learning. Given background knowledge and examples, ILP systems (e.g., Progol, Aleph) induce a logic program that explains the positive examples and excludes the negative ones. ILP has been used for drug design, game playing, and relational data mining.
6.2 Answer set programming (ASP)
ASP is a declarative paradigm based on the stable‑model semantics. Programs consist of rules with negation, and the answer sets correspond to the intended models. ASP solvers (e.g., clasp, DLV, smodels) use sophisticated search heuristics.
6.2.1 Stable model semantics
A set of ground atoms is a stable model if every rule’s body is satisfied and no atom can be removed. A program may have zero, one, or multiple stable models. ASP handles default negation and disjunction, making it suitable for representing knowledge with defaults.
6.2.2 Applications in configuration
ASP is used for product configuration, scheduling, and robotics. Its ability to express complex constraints and generate all models (or a single optimal one) suits industrial configuration problems.
6.3 Concurrent and parallel logic programming
Extensions that exploit concurrency for performance or reactive systems.
6.3.1 Concurrent Prolog and Parlog
Developed in the 1980s, Concurrent Prolog and Parlog add guarded rules and committed choice. Processes communicate via shared logical variables, supporting parallel execution. These languages influenced the design of the Erlang concurrency model.
6.4 Probabilistic logic programming
This extension combines logic programming with probabilities. Systems like ProbLog, PRISM, and BLOG allow the encoding of uncertain knowledge. Queries return the probability of a goal being true, leveraging techniques from weighted model counting and knowledge compilation.
7.1 Imperative vs. declarative
Imperative languages (e.g., C, Java) specify *how* to compute by controlling state and mutable variables. Logic programming is declarative: the programmer states *what* is true, and the system finds a proof. This difference often leads to more concise programs for problems involving search and constraints.
7.2 Functional vs. logic programming
Both are declarative, but functional programming (e.g., Haskell, ML) is based on functions and bindings, while logic programming is relational.
7.2.1 Relational vs. functional composition
In logic programming, predicates define relations rather than functions. A relation can be evaluated in multiple directions (e.g., “append” can split a list or concatenate two lists). Functional programming requires explicit recursion or higher‑order combinators.
7.2.2 Choice and backtracking
Logic programming inherently supports nondeterminism through backtracking; functional programming requires monads or explicit list comprehensions to achieve similar effects. However, functional languages typically offer stronger type systems and referential transparency.
7.3 Object‑oriented logic programming (e.g., Logtalk)
Logtalk extends Prolog with object‑oriented concepts: objects, classes, protocols, and inheritance. It compiles to Prolog and integrates seamlessly with the host language. Other hybrid approaches include Visual Prolog and Ciao Prolog with OOP features.
8.1 Teaching logic with Prolog
Prolog’s declarative style makes it suitable for teaching logic, proof theory, and AI concepts in introductory courses. Its short syntax and immediate feedback (interactive queries) help students understand relationships and constraints.
8.2 Visual environments and tracing tools
Tools like SWISH (SWI‑Prolog for SHaring) provide a web‑based, visual interface with a step‑through debugger. Tau Prolog and Ciao’s “pir” environment support visualisation of resolution trees. These aids help students grasp backtracking and unification.
9.1 Efficiency and scalability issues
Pure logic programming can be slower than imperative code due to unification overhead and backtracking. For large‑scale problems, sophisticated compilation techniques (e.g., WAM, tabling) are necessary but still may not match hand‑optimised imperative solutions in number‑crunching tasks.
9.2 Limitations of negation as failure
Negation as failure is non‑monotonic and can lead to unsound conclusions if applied incorrectly (e.g., in non‑stratified programs). Its operational definition depends on the search strategy, causing results to vary between implementations.
9.3 Debugging challenges
The implicit control flow (backtracking, cut) makes debugging difficult. Standard trace‑based tools can become overwhelming. Declarative debugging (algorithmic debugging) is available in some systems but requires understanding of the intended behaviour.
10.1 Integration with machine learning
Logic programming is being combined with neural networks to create neural‑symbolic systems. Frameworks like DeepProbLog and NeuralProlog embed neural networks inside logical rules, enabling learning from noisy data while maintaining deductive reasoning. This hybrid approach holds promise for explainable AI.
10.2 Web‑scale reasoning and distributed logic programming
Efforts to scale logic programming to large‑scale data include distributed Datalog (e.g., BigDatalog on Spark) and WebProlog for reasoning over Linked Data. Cloud‑based reasoning services and parallel execution models aim to make logic programming viable for semantic web and big‑data applications.