Logic Programming
Logic programming is a paradigm in which a program is a set of logical statements, typically facts and if-then rules, and computation is the act of proving a query from them, so that the programmer states what is true about a problem and a built-in inference engine works out how to find answers. It separates logic from control. Robert Kowalski summarized the idea in his slogan "algorithm = logic + control": the logic component declares the knowledge, the control component decides the search strategy, and in the ideal case the first can be changed without touching the second.
Prolog, created in 1972 at the University of Marseille by Alain Colmerauer and Philippe Roussel, working in dialogue with Robert Kowalski, was the first practical logic programming language. Colmerauer's group built it for natural-language processing, and its name abbreviates "programmation en logique." The theoretical bridge was Kowalski's 1974 paper "Predicate logic as programming language," which showed that Horn clauses, rules with a single conclusion, can be read both as logical implications and as procedures, and that Robinson's 1965 resolution principle gives them an execution mechanism. Prolog's search is SLD resolution: it tries clauses top to bottom, unifies the goal with each head, and backtracks on failure. David H. D. Warren's 1983 Warren Abstract Machine gave it an efficient compilation target that most later implementations followed.
Prolog is powerful but not purely declarative, and this gap is the source of its best-known pitfalls. Because clauses and goals are tried in a fixed order, a left-recursive rule can send the interpreter into an infinite loop even though the logic is perfectly sound, and the cut operator, which prunes the search, has no logical meaning at all. Negation is "negation as failure," formalized by Keith Clark in 1978: a goal is treated as false when it cannot be proved, which is a closed-world assumption rather than true logical negation. A frequent misconception is that Prolog is simply a slow general-purpose language. It is better understood as a specialized engine for search, constraint solving, and symbolic manipulation, as in parsing, theorem proving, scheduling, and rule-based expert systems.
Datalog is the restricted, database-flavored descendant that trades Prolog's expressive power for guaranteed termination. It keeps facts and rules but forbids function symbols and uses bottom-up evaluation, so that every query over a finite database terminates and the answer does not depend on rule order. This makes recursion, such as computing transitive closure over a graph, easy and optimizable, and the language arose from the deductive database research of the late 1970s and the 1980s. Datalog has found a second life in static program analysis tools such as Soufflé, in security policy languages, and in query engines for graph and knowledge-base systems.
Answer set programming, grounded in the stable model semantics of Michael Gelfond and Vladimir Lifschitz in 1988, takes the declarative idea further by dropping Prolog's execution model entirely. A program describes constraints, and a solver such as clingo from the Potassco group at the University of Potsdam enumerates the stable models, each a consistent set of conclusions satisfying the rules. It handles negation by default, choice rules, and optimization, and is well suited to combinatorial problems like timetabling, configuration, and planning. The cost is that solving is a search over a possibly exponential space, so problem encoding matters.
Logic programming's visibility peaked with Japan's Fifth Generation Computer Systems project, launched in 1982, which chose it as a foundation and is usually remembered as overambitious. Even so, its ideas persist in rule engines, verification, and neurosymbolic work, where a neural network proposes and a logic program checks or explains. Language models can now write Prolog or ASP programs as an intermediate form, using the solver for the part where exactness matters.
Read logic programming as programming by assertion: the programmer supplies true statements and a question, the engine searches for proofs, and the three descendants differ in how much they give up for guarantees, with Prolog keeping full power, Datalog ensuring termination, and answer set programming ensuring declarative solutions.