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.2022.7
URN: urn:nbn:de:0030-drops-162354
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16235/
Go to the corresponding LIPIcs Volume Portal

Pacak, André ; Erdweg, Sebastian

Functional Programming with Datalog

pdf-format:
LIPIcs-ECOOP-2022-7.pdf (0.8 MB)

Abstract

Datalog is a carefully restricted logic programming language. What makes Datalog attractive is its declarative fixpoint semantics: Datalog queries consist of simple Horn clauses, yet Datalog solvers efficiently compute all derivable tuples even for recursive queries. However, as we argue in this paper, Datalog is ill-suited as a programming language and Datalog programs are hard to write and maintain. We propose a "new" frontend for Datalog: functional programming with sets called functional IncA. While programmers write recursive functions over algebraic data types and sets, we transparently translate all code to Datalog relations. However, we retain Datalog’s strengths: Functions that generate sets can encode arbitrary relations and mutually recursive functions have fixpoint semantics. We also ensure that the generated Datalog program terminates whenever the original functional program terminates, so that we can apply off-the-shelve bottom-up Datalog solvers. We demonstrate the versatility and ease of use of functional IncA by implementing a type checker, a program transformation, an interpreter of the untyped lambda calculus, two data-flow analyses, and clone detection of Java bytecode.

BibTeX - Entry

@InProceedings{pacak_et_al:LIPIcs.ECOOP.2022.7,
  author =	{Pacak, Andr\'{e} and Erdweg, Sebastian},
  title =	{{Functional Programming with Datalog}},
  booktitle =	{36th European Conference on Object-Oriented Programming (ECOOP 2022)},
  pages =	{7:1--7:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-225-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{222},
  editor =	{Ali, Karim and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16235},
  URN =		{urn:nbn:de:0030-drops-162354},
  doi =		{10.4230/LIPIcs.ECOOP.2022.7},
  annote =	{Keywords: Datalog, functional programming, demand transformation}
}

Keywords: Datalog, functional programming, demand transformation
Collection: 36th European Conference on Object-Oriented Programming (ECOOP 2022)
Issue Date: 2022
Date of publication: 23.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI