{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T17:24:19Z","timestamp":1778520259056,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3428193","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Fixpoints for the masses: programming with first-class Datalog constraints"],"prefix":"10.1145","volume":"4","author":[{"given":"Magnus","family":"Madsen","sequence":"first","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ond\u0159ej","family":"Lhot\u00e1k","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proc. Conference on Innovative Data Systems (CIDR).","author":"Alvaro Peter","year":"2011"},{"key":"e_1_2_2_2_1","volume-title":"Dedalus: Datalog in time and space. In International Datalog 2.0 Workshop.","author":"Alvaro Peter","year":"2010"},{"key":"e_1_2_2_3_1","volume-title":"Proc. of ACM on Programming Languages Principles of Programming Languages (POPL) ( 2019 ).","author":"Arntzenius Michael","year":"2019"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951948"},{"key":"e_1_2_2_5_1","volume-title":"Proc. European Conference on Object-Oriented Programming (ECOOP 2016 ).","author":"Avgustinov Pavel","year":"2016"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/6012.15399"},{"key":"e_1_2_2_7_1","volume-title":"FormuLog: Datalog for static analysis involving logical formulae. arXiv preprint arXiv","author":"Bembenek Aaron","year":"1809"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.43410"},{"key":"e_1_2_2_10_1","volume-title":"Logic programming and databases","author":"Ceri Stefano"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/79204.79209"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/582153.582176"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9"},{"key":"e_1_2_2_15_1","volume-title":"Robert Bruce Findler, and Matthew Flatt","author":"Felleisen Matthias","year":"2009"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00330-3"},{"key":"e_1_2_2_17_1","volume-title":"Proc. International Conference on Logic Programming (ICLP\/SLP).","author":"Gelfond Michael","year":"1988"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_2_20_1","volume-title":"Parallel Logic Programming in PARLOG: The Language and its Implementation","author":"Gregory Steve"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785477_2"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594530"},{"key":"e_1_2_2_23_1","unstructured":"Fergus Henderson Thomas Conway Zoltan Somogyi David Jefery Peter Schachte Simon Taylor Chris Speirs Tyson Dowd Ralph Becket and Mark Brown. 1996. The Mercury language reference manual. ( 1996 ).  Fergus Henderson Thomas Conway Zoltan Somogyi David Jefery Peter Schachte Simon Taylor Chris Speirs Tyson Dowd Ralph Becket and Mark Brown. 1996. The Mercury language reference manual. ( 1996 )."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989456"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41635"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90033-7"},{"key":"e_1_2_2_27_1","volume-title":"Soufl\u00e9: On Synthesis of Program Analyzers. In International Conference on Computer Aided Verification.","author":"Jordan Herbert","year":"2016"},{"key":"e_1_2_2_28_1","volume-title":"Proc. Symposium on Principles and Practice of Parallel Programming.","author":"Jordan Herbert","year":"2018"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462191"},{"key":"e_1_2_2_30_1","unstructured":"Ross D King. 2004. Applying Inductive Logic Programming to Predicting Gene Function. AI Magazine ( 2004 ).  Ross D King. 2004. Applying Inductive Logic Programming to Predicting Gene Function. AI Magazine ( 2004 )."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(87)90007-0"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065169"},{"key":"e_1_2_2_33_1","unstructured":"Daan Leijen. 2005. Extensible records with scoped labels. Trends in Functional Programming ( 2005 ).  Daan Leijen. 2005. Extensible records with scoped labels. Trends in Functional Programming ( 2005 )."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36388-2_6"},{"key":"e_1_2_2_35_1","unstructured":"Boon Thau Loo Tyson Condie Minos Garofalakis David E Gay Joseph M Hellerstein Petros Maniatis Raghu Ramakrishnan Timothy Roscoe and Ion Stoica. 2009. Declarative networking. Commun. ACM ( 2009 ).  Boon Thau Loo Tyson Condie Minos Garofalakis David E Gay Joseph M Hellerstein Petros Maniatis Raghu Ramakrishnan Timothy Roscoe and Ion Stoica. 2009. Declarative networking. Commun. ACM ( 2009 )."},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Magnus Madsen Ming-Ho Yee and Ond\u0159ej Lhot\u00e1k. 2016. From Datalog to Flix: A Declarative Language for Fixed Points on Lattices. In Programming Language Design and Implementation (PLDI).  Magnus Madsen Ming-Ho Yee and Ond\u0159ej Lhot\u00e1k. 2016. From Datalog to Flix: A Declarative Language for Fixed Points on Lattices. In Programming Language Design and Implementation (PLDI).","DOI":"10.1145\/2908080.2908096"},{"key":"e_1_2_2_38_1","unstructured":"Jack Minker. 1988. Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann.  Jack Minker. 1988. Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann."},{"key":"e_1_2_2_39_1","volume-title":"Inductive Logic Programming for Natural Language Processing. In International Conference on Inductive Logic Programming.","author":"Mooney Raymond J","year":"1996"},{"key":"e_1_2_2_40_1","unstructured":"Christos H. Papadimitriou. 1985. A note the expressive power of Prolog. Bulletin of the European Association for Theoretical Computer Science (EATCS) ( 1985 ).  Christos H. Papadimitriou. 1985. A note the expressive power of Prolog. Bulletin of the European Association for Theoretical Computer Science (EATCS) ( 1985 )."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00072-2"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706317"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892226"},{"key":"e_1_2_2_45_1","volume-title":"International Conference Data Engineering (ICDE).","author":"Seo Jiwon","year":"2013"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509524"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926390"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594320"},{"key":"e_1_2_2_51_1","doi-asserted-by":"crossref","unstructured":"Zoltan Somogyi Fergus Henderson and Thomas Conway. 1996. The Execution Algorithm of Mercury an Eficient Purely Declarative Logic Programming Language. The Journal of Logic Programming ( 1996 ).  Zoltan Somogyi Fergus Henderson and Thomas Conway. 1996. The Execution Algorithm of Mercury an Eficient Purely Declarative Logic Programming Language. The Journal of Logic Programming ( 1996 ).","DOI":"10.1016\/S0743-1066(96)00068-4"},{"key":"e_1_2_2_52_1","unstructured":"Zoltan Somogyi Fergus J Henderson and Thomas Charles Conway. 1995. Mercury an eficient purely declarative logic programming language. Australian Computer Science Communications ( 1995 ).  Zoltan Somogyi Fergus J Henderson and Thomas Charles Conway. 1995. Mercury an eficient purely declarative logic programming language. Australian Computer Science Communications ( 1995 )."},{"key":"e_1_2_2_53_1","volume-title":"https:\/\/soufle-lang.github.io\/ [Online","author":"Authors Soufle","year":"2018"},{"key":"e_1_2_2_54_1","doi-asserted-by":"crossref","unstructured":"Pavle Subotic Herbert Jordan Lijun Chang Alan Fekete and Bernhard Scholz. 2018. Automatic Index Selection for Large-Scale Datalog Computation. ( 2018 ).  Pavle Subotic Herbert Jordan Lijun Chang Alan Fekete and Bernhard Scholz. 2018. Automatic Index Selection for Large-Scale Datalog Computation. ( 2018 ).","DOI":"10.14778\/3282495.3282500"},{"key":"e_1_2_2_55_1","unstructured":"Jefrey D Ullman. 1984. Principles of Database Systems. Galgotia publications.  Jefrey D Ullman. 1984. Principles of Database Systems. Galgotia publications."},{"key":"e_1_2_2_56_1","unstructured":"Jefrey D. Ullman. 1988. Principles of Database and Knowledge-Base Systems.  Jefrey D. Ullman. 1988. Principles of Database and Knowledge-Base Systems."},{"key":"e_1_2_2_57_1","unstructured":"Todd L Veldhuizen. 2012. Leapfrog Triejoin: a worst-case optimal join algorithm. arXiv preprint arXiv:1210.0481 ( 2012 ).  Todd L Veldhuizen. 2012. Leapfrog Triejoin: a worst-case optimal join algorithm. arXiv preprint arXiv:1210.0481 ( 2012 )."},{"key":"e_1_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Andrew K Wright and Matthias Felleisen. 1994. A Syntactic Approach to Type Soundness. Information and computation ( 1994 ).  Andrew K Wright and Matthias Felleisen. 1994. A Syntactic Approach to Type Soundness. Information and computation ( 1994 ).","DOI":"10.1006\/inco.1994.1093"},{"key":"e_1_2_2_59_1","volume-title":"International Symposium on Practical Aspects of Declarative Languages (PADL).","author":"Zook David","year":"2009"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428193","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:56Z","timestamp":1750197776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":58,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428193"],"URL":"https:\/\/doi.org\/10.1145\/3428193","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}