Lune

OOPSLA2020Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Fast and Efficient Boolean Unification for Hindley-Milner-Style Type and Effect Systems cites Relational nullable types with Boolean unification
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers9

  1. Relational nullable types with Boolean unificationMagnus Madsen, Jaco van de PolOOPSLA 2021 · 9 citations
  2. On-the-Fly Static Analysis via Dynamic Bidirected Dyck ReachabilityShankaranarayanan Krishna, Aniket Lal, Andreas Pavlogiannis, Omkar TuppePOPL 2024 · 7 citations
  3. Fast and Efficient Boolean Unification for Hindley-Milner-Style Type and Effect SystemsMagnus Madsen, Jaco van de Pol, Troels HenriksenOOPSLA 2023 · 5 citations
  4. IncIDFA: An Efficient and Generic Algorithm for Incremental Iterative Dataflow AnalysisAman Nougrahiya, V. Krishna NandivadaOOPSLA 2025 · 4 citations
  5. Finite-Choice Logic ProgrammingChris Martens, Robert J. Simmons, Michael ArntzeniusPOPL 2025 · 3 citations

Builds on1

  1. Seminaïve evaluation for a higher-order functional languageMichael Arntzenius, Neel KrishnaswamiPOPL 2020 · 15 citations

Related papers

  1. Datalog with First-Class FactsThomas Gilray, Arash Sahebolamri, Yihao Sun, Sowmith Kunapaneni et al.VLDB 2025 · 3 citations
  2. Flix: A Design for Language-Integrated DatalogMagnus Madsen, Ondrej LhotákOOPSLA 2025
  3. Flan: An Expressive and Efficient Datalog Compiler for Program AnalysisSupun Abeysinghe, Anxhelo Xhebraj, Tiark RompfPOPL 2024 · 9 citations
  4. Metamorphic testing of Datalog enginesMuhammad Numair Mansur, Maria Christakis, Valentin WüstholzFSE 2021 · 25 citations
  5. Polymorphic types and effects with Boolean unificationMagnus Madsen, Jaco van de PolOOPSLA 2020 · 18 citations
Dusk over the sea between two cliffs drawn in fine vertical lines