Aarhus University Seal

Breaking the Negative Cycle: Exploring the Design Space of Stratification for First-Class Datalog Constraints

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

The λDat calculus brings together the power of functional and declarative logic programming in one language. In λDat, Datalog constraints are first-class values that can be constructed, passed around as arguments, returned, composed with other constraints, and solved. A significant part of the expressive power of Datalog comes from the use of negation. Stratified negation is a particularly simple and practical form of negation accessible to ordinary programmers. Stratification requires that Datalog programs must not use recursion through negation. For a Datalog program, this requirement is straightforward to check, but for a λDat program, it is not so simple: A λDat program constructs, composes, and solves Datalog programs at runtime. Hence stratification cannot readily be determined at compile-time. In this paper, we explore the design space of stratification for λDat. We investigate strategies to ensure, at compile-time, that programs constructed at runtime are guaranteed to be stratified, and we argue that previous design choices in the Flix programming language have been suboptimal.

Original languageEnglish
Title of host publication37th European Conference on Object-Oriented Programming, ECOOP 2023
EditorsKarim Ali, Guido Salvaneschi
PublisherDagstuhl Publishing
Publication yearJul 2023
Article number31
ISBN (electronic)9783959772815
Publication statusPublished - Jul 2023
Event37th European Conference on Object-Oriented Programming, ECOOP 2023 - Seattle, United States
Duration: 17 Jul 202321 Jul 2023


Conference37th European Conference on Object-Oriented Programming, ECOOP 2023
LandUnited States
SeriesLeibniz International Proceedings in Informatics, LIPIcs

Bibliographical note

Publisher Copyright:
© Jonathan Lindegaard Starup, Magnus Madsen, and Ondřej Lhoták;

    Research areas

  • Datalog, first-class Datalog constraints, negation, row polymorphism, stratified negation, the Flix programming language, type system

See relations at Aarhus University Citationformats

ID: 341391426