Logic & Constraint Programming — Tier 3 Index
Logic & Constraint Programming — Tier 3 Index
- Type: Family index
- Family: Logic programming, constraint programming, answer-set programming, rewriting logic
- Languages catalogued: ~14
- Last updated: 2026-05-07
Family overview
Logic programming asks the programmer to state what is true rather than how to compute it. A program is a set of facts and rules, and execution is a search for assignments to variables that make a query true. Prolog (1972) is the canonical member of the family and has its own deep note; this index covers everything else — the dialects, the constraint extensions, the answer-set sub-family, the rewriting-logic branch, and the pure-relational embeddings.
The family splits into four working camps in 2026:
-
Datalog & friends — a deliberately weakened logic language (no function symbols, no negation in the head) that is decidable, terminates, and can be evaluated bottom-up in polynomial time. After two decades of academic neglect, Datalog has had a startling revival as the engine behind modern static analysis (Soufflé, Doop, CodeQL’s predecessor), program reasoning (Datafrog, Differential Datalog), and graph-style query systems (LogicBlox, Datomic’s query language). If you’ve used a modern type-checker or security scanner, you’ve probably executed Datalog without knowing it.
-
Extended Prolog & constraint logic programming (CLP) — Ciao, B-Prolog, ECLiPSe, SWI-Prolog (covered separately) extend Prolog with assertions, tabling, and constraint solvers (CLP(FD), CLP(R), CLP(Q)). The killer app is scheduling, planning, and combinatorial search: airline crew rostering, factory scheduling, satellite control. ECLiPSe was the dominant industrial CLP system for two decades.
-
Answer Set Programming (ASP) — AnsProlog, DLV, Clingo. ASP changes the semantics: instead of computing one answer top-down (Prolog), an ASP solver finds all stable models of a logic program. This is unbeaten for declarative combinatorial problems: graph colouring, planning under uncertainty, biomedical reasoning. The Potsdam group’s Clingo / gringo / clasp toolchain is the de-facto modern implementation and powers research in robotics planning, knowledge representation, and computational biology.
-
Higher-order, dependent, and rewriting logic — λProlog, Twelf, Maude. These extend logic programming into the world of proofs and program verification: λProlog and Twelf use higher-order unification to encode logical frameworks; Maude uses rewriting logic for protocol verification, model checking, and formal-methods research.
A fifth, smaller camp lives outside dedicated logic languages: miniKanren (a relational DSL embedded in Scheme/Clojure/Racket) and CHR (Constraint Handling Rules, usually embedded in Prolog or Java/Python). These are influential out of proportion to their LoC count: miniKanren spawned core.logic (Clojure), cKanren, and a healthy “relational programming” research thread.
The state of the family in 2026 is quietly indispensable: Datalog inside static analysers is mainstream, ASP runs serious industrial planning, miniKanren teaches a generation of functional programmers what unification and search feel like, and Maude continues to be the reference rewriting-logic system. None of these are mainstream day-job languages, but they show up everywhere in their respective niches.
In our deep library
- prolog — the canonical logic language; covers SWI-Prolog and the Edinburgh family
- ml-and-fp — Mercury and Curry are arguably ML-family with logic features; cross-listed
- lisp-and-scheme — miniKanren is implemented as Scheme/Racket macros; core.logic is Clojure
- haskell — for the dependent-types-and-types-as-proofs lineage Twelf belongs to
Tier 3 — the family
| Language | First release | Status 2026 | Niche | Why it matters | Source URL |
|---|---|---|---|---|---|
| Datalog | 1977 (Chandra & Harel) | Revival / active | Static analysis, graph queries, deductive DB | Decidable subset of Prolog; basis for Soufflé, Datomic, Differential Datalog | https://en.wikipedia.org/wiki/Datalog |
| Soufflé | 2016 | Active | High-performance Datalog for static analysis | Compiles Datalog to parallel C++; used in Doop, security tools | https://souffle-lang.github.io/ |
| miniKanren | 2005 (Friedman, Byrd, Kiselyov) | Active | Relational programming embedded in host langs | Influential teaching language; “The Reasoned Schemer” book; core.logic in Clojure | http://minikanren.org/ |
| Picat | 2013 | Active | Logic + functional + constraint multi-paradigm | ”Pattern, Inference, Constraint, Action, Tabling”; used in puzzle solving, planning | http://picat-lang.org/ |
| Mercury | 1995 | Active | Pure logic + types + modes | Statically typed, mode-checked Prolog; faster than Prolog by 10-100x | https://mercurylang.org/ |
| Curry | 1996 | Active (research) | Haskell + logic programming | Functional-logic; demand-driven evaluation; multiple implementations (PAKCS, KiCS2) | https://www.curry-lang.org/ |
| Mozart/Oz | 1995 | Mostly dormant | Multi-paradigm research lang | Constraint + logic + FP + OO; basis for “Concepts, Techniques, and Models of Computer Programming” (CTM) | https://mozart.github.io/ |
| Ciao Prolog | 1995 | Active | Extended Prolog with assertions + safety analysis | Modules, assertion language, abstract interpretation; used in EU research | https://ciao-lang.org/ |
| B-Prolog | 1994 | Commercial / dormant | Tabling + constraint Prolog | Pioneered tabled execution and CLP(FD) action rules; superseded by Picat from same author | https://en.wikipedia.org/wiki/B-Prolog |
| ECLiPSe | 1993 | Open-source maintained | Industrial CLP (constraint logic programming) | Dominant CLP system 1995-2015 (airline rostering, scheduling); now community-maintained | https://eclipseclp.org/ |
| AnsProlog (ASP) | ~1999 (Gelfond & Lifschitz semantics) | Active formalism | Declarative logic via stable models | Defines the answer-set semantics that ASP solvers implement | https://en.wikipedia.org/wiki/Answer_set_programming |
| DLV | 1997 | Active | ASP solver + language | One of the two canonical ASP systems; disjunctive logic programs | https://www.dlvsystem.it/ |
| Clingo / gringo | 2008 | Active | Modern ASP toolchain (Potsdam) | De facto modern ASP; powers planning/robotics research | https://potassco.org/clingo/ |
| CHR (Constraint Handling Rules) | 1991 | Active embedded | Constraint propagation language | Usually embedded in Prolog/Java/Python; rewriting-rule constraint solver | https://chr.informatik.uni-ulm.de/ |
| λProlog (Lambda Prolog) | 1988 | Research active | Higher-order logic programming | Higher-order unification; encodes binding/scoping naturally | https://www.lix.polytechnique.fr/~dale/lProlog/ |
| Twelf | 1999 | Niche research | Logical-framework metalanguage | Encoding deductive systems and proofs; used in PL research | http://twelf.org/ |
| Maude | 1999 | Active | Rewriting-logic verification | Model checking, protocol verification, formal-methods research | http://maude.cs.illinois.edu/ |
Notable threads
- The Datalog renaissance. From ~2010 onward Datalog became the engine of choice for whole-program static analysis (Doop for Java points-to analysis, Soufflé as the modern compiler), incremental computation (Differential Datalog from VMware), and reactive query systems (Datomic, LogicBlox, Materialise’s Differential Dataflow). The reason: Datalog is decidable, terminating, and bottom-up evaluable in polynomial time — Prolog’s combinatorial wildness is exactly what static-analysis writers don’t want.
- ASP for planning. When the problem is combinatorial and declarative — pack these blocks, schedule these jobs, find a stable molecular configuration — ASP solvers (Clingo) regularly beat hand-written search code. The Potsdam group has been the centre of gravity for two decades.
- miniKanren’s outsized influence. A relational language that fits in a single Scheme file (30-100 lines depending on the variant) became the teaching tool of choice for “logic programming for functional programmers” via The Reasoned Schemer (Friedman, Byrd, Kiselyov). It directly inspired Clojure’s core.logic, Racket’s
racket/logic, and a healthy thread of relational-interpreter research (Byrd’s relational miniKanren can run programs backwards to generate quines). - Functional-logic merger keeps trying to happen. Mercury, Curry, and Mozart/Oz all attempt to unify logic and functional programming under one roof. None broke through to the mainstream, but each demonstrated useful ideas: Mercury’s mode system, Curry’s needed narrowing, Oz’s dataflow concurrency. The lessons fed into Haskell type-class research and into modern dependent-type languages.
- Why logic programming stays niche. For a typical “build this CRUD app” problem, declarative search is overkill and the unpredictable performance is a liability. Logic programming wins decisively when the problem is search/inference (constraints, planning, static analysis) — which describes <5% of working programmer time but ≥50% of compilers, schedulers, and reasoning systems.
Citations
- Alain Colmerauer & Philippe Roussel, “The birth of Prolog” (1992, HOPL II) — https://dl.acm.org/doi/10.1145/154766.155362
- Stefano Ceri, Georg Gottlob & Letizia Tanca, “What you Always Wanted to Know About Datalog” (1989) — https://dl.acm.org/doi/10.1109/69.43410
- Daniel P. Friedman, William E. Byrd & Oleg Kiselyov, The Reasoned Schemer (2nd ed. 2018, MIT Press) — https://mitpress.mit.edu/9780262535519/the-reasoned-schemer/
- Bernardo Subercaseaux & Marijn Heule, “Sufficient conditions for the unique readability of answer-set programs” — https://potassco.org/
- Michael Gelfond & Vladimir Lifschitz, “The stable model semantics for logic programming” (1988) — http://www.cs.utexas.edu/users/vl/papers/stable.pdf
- Z. Somogyi, F. Henderson & T. Conway, “The execution algorithm of Mercury” (1996) — https://mercurylang.org/documentation/papers/concepts.pdf
- Sergio Antoy & Michael Hanus, “Functional logic programming” (CACM 2010) — https://dl.acm.org/doi/10.1145/1721654.1721675
- Peter Van Roy & Seif Haridi, Concepts, Techniques, and Models of Computer Programming (CTM, MIT 2004) — https://www.info.ucl.ac.be/~pvr/book.html
- Bernhard Scholz et al., “On Fast Large-Scale Program Analysis in Datalog” (CC 2016, Soufflé) — https://souffle-lang.github.io/pdf/cc.pdf