License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2023.31
URN: urn:nbn:de:0030-drops-182244
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18224/
Starup, Jonathan Lindegaard ;
Madsen, Magnus ;
Lhoták, Ondřej
Breaking the Negative Cycle: Exploring the Design Space of Stratification for First-Class Datalog Constraints
Abstract
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.
BibTeX - Entry
@InProceedings{starup_et_al:LIPIcs.ECOOP.2023.31,
author = {Starup, Jonathan Lindegaard and Madsen, Magnus and Lhot\'{a}k, Ond\v{r}ej},
title = {{Breaking the Negative Cycle: Exploring the Design Space of Stratification for First-Class Datalog Constraints}},
booktitle = {37th European Conference on Object-Oriented Programming (ECOOP 2023)},
pages = {31:1--31:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-281-5},
ISSN = {1868-8969},
year = {2023},
volume = {263},
editor = {Ali, Karim and Salvaneschi, Guido},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18224},
URN = {urn:nbn:de:0030-drops-182244},
doi = {10.4230/LIPIcs.ECOOP.2023.31},
annote = {Keywords: Datalog, first-class Datalog constraints, negation, stratified negation, type system, row polymorphism, the Flix programming language}
}
|
Keywords: |
|
Datalog, first-class Datalog constraints, negation, stratified negation, type system, row polymorphism, the Flix programming language |
|
Collection: |
|
37th European Conference on Object-Oriented Programming (ECOOP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
11.07.2023 |
