Fixpoints for the masses: programming with first-class Datalog constraints
Magnus Madsen, Ondrej Lhoták
Abstract
Datalog is a declarative logic programming language that has been used in a variety of applications, including big-data analytics, language processing, networking and distributed systems, and program analysis.
In this paper, we propose first-class Datalog constraints as a mechanism to construct, compose, and solve Datalog programs at run time. The benefits are twofold: We gain the full power of a functional programming language to operate on Datalog constraints-as-values, while simultaneously we can use Datalog where it really shines: to declaratively express and solve fixpoint problems.
We present an extension of the lambda calculus with first-class Datalog constraints, including its semantics and a type system with row polymorphism based on Hindley-Milner. We prove soundness of the type system and implement it as an extension of the Flix programming language.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
9 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers9
- Relational nullable types with Boolean unificationMagnus Madsen, Jaco van de PolOOPSLA 2021 · 9 citations
- On-the-Fly Static Analysis via Dynamic Bidirected Dyck ReachabilityShankaranarayanan Krishna, Aniket Lal, Andreas Pavlogiannis, Omkar TuppePOPL 2024 · 7 citations
- Fast and Efficient Boolean Unification for Hindley-Milner-Style Type and Effect SystemsMagnus Madsen, Jaco van de Pol, Troels HenriksenOOPSLA 2023 · 5 citations
- IncIDFA: An Efficient and Generic Algorithm for Incremental Iterative Dataflow AnalysisAman Nougrahiya, V. Krishna NandivadaOOPSLA 2025 · 4 citations
- Finite-Choice Logic ProgrammingChris Martens, Robert J. Simmons, Michael ArntzeniusPOPL 2025 · 3 citations
Builds on1
Related papers
- Datalog with First-Class FactsThomas Gilray, Arash Sahebolamri, Yihao Sun, Sowmith Kunapaneni et al.VLDB 2025 · 3 citations
- Flix: A Design for Language-Integrated DatalogMagnus Madsen, Ondrej LhotákOOPSLA 2025
- Flan: An Expressive and Efficient Datalog Compiler for Program AnalysisSupun Abeysinghe, Anxhelo Xhebraj, Tiark RompfPOPL 2024 · 9 citations
- Metamorphic testing of Datalog enginesMuhammad Numair Mansur, Maria Christakis, Valentin WüstholzFSE 2021 · 25 citations
- Polymorphic types and effects with Boolean unificationMagnus Madsen, Jaco van de PolOOPSLA 2020 · 18 citations
