Search Results

Documents authored by Erdweg, Sebastian

Artifact
Software
DOI: 10.4230/artifacts.23600
Mono Types – First-Class Containers for Datalog

Authors: Runqing Xu, David Klopp, and Sebastian Erdweg

Abstract
Cite as

Runqing Xu, David Klopp, Sebastian Erdweg. Mono Types – First-Class Containers for Datalog (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23600,
   title = {{Mono Types – First-Class Containers for Datalog}}, 
   author = {Xu, Runqing and Klopp, David and Erdweg, Sebastian},
   note = {Software (visited on 2025-06-25)},
   url = {https://gitlab.rlp.net/plmz/artifacts/mono-types-ecoop25},
   doi = {10.4230/artifacts.23600},
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.20
Incremental Computing by Differential Execution

Authors: Prashant Kumar, André Pacak, and Sebastian Erdweg

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
Incremental computing offers the potential for significant performance gains by efficiently updating computations in response to changing data. However, traditional approaches are either problem-specific or use an inefficient all-or-nothing strategy of rerunning affected computations entirely. This paper presents differential semantics, a novel approach that directly embeds the propagation of changes into the semantics of a general-purpose programming language. Given a precise description of input changes, differential semantics rules define how these changes are tracked and propagated through core language constructs like assignments, conditionals, and loops to produce corresponding output changes. We formalize differential semantics and verify key properties, including correctness, using the Rocq proof assistant. We also develop and formally prove a set of optimizations, particularly for loop handling, that enable asymptotic performance improvements. An implementation of the semantics as a differential interpreter achieves order-of-magnitude speedups over recomputation on the Bellman-Ford shortest path algorithm.
Cite as

Prashant Kumar, André Pacak, and Sebastian Erdweg. Incremental Computing by Differential Execution. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 20:1-20:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.ECOOP.2025.20,
  author =	{Kumar, Prashant and Pacak, Andr\'{e} and Erdweg, Sebastian},
  title =	{{Incremental Computing by Differential Execution}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{20:1--20:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.20},
  URN =		{urn:nbn:de:0030-drops-233137},
  doi =		{10.4230/LIPIcs.ECOOP.2025.20},
  annote =	{Keywords: Incremental computing, differential semantics, programming language design, formal verification, big-step semantics}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.33
Mono Types - First-Class Containers for Datalog

Authors: Runqing Xu, David Klopp, and Sebastian Erdweg

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
We propose mono types, a new abstraction for programming Datalog. Mono types behave like first-class containers that can be stored in relations and to which elements can be added decentrally. But, mono types are more than just containers: They provide a read operation that can yield any result as long as it monotonically grows with each added element and is independent of the order in which elements are added to the container. This design permits a wide range of mono types (e.g., sets, maps, and aggregations), yet guarantees mono types can be integrated into Datalog without jeopardizing Datalog’s least fixed-point semantics. We develop a theory for mono types, which includes constructions for complex mono types, equivalence relation for mono types, and properties about semantics-preserving mono-type transformations. This theory ensures sound Datalog integration and justifies crucial compiler optimizations for mono types. Together, these techniques demonstrate that mono types provide abstraction without regret: We demonstrate in two case studies that programs become easier to write with mono types, while their performance also improves drastically.
Cite as

Runqing Xu, David Klopp, and Sebastian Erdweg. Mono Types - First-Class Containers for Datalog. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 33:1-33:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.ECOOP.2025.33,
  author =	{Xu, Runqing and Klopp, David and Erdweg, Sebastian},
  title =	{{Mono Types - First-Class Containers for Datalog}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{33:1--33:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.33},
  URN =		{urn:nbn:de:0030-drops-233250},
  doi =		{10.4230/LIPIcs.ECOOP.2025.33},
  annote =	{Keywords: Datalog, compiler optimization}
}
Document
Artifact
DOI: 10.4230/DARTS.11.2.13
Incremental Computing by Differential Execution (Artifact)

Authors: Prashant Kumar, André Pacak, and Sebastian Erdweg

Published in: DARTS, Volume 11, Issue 2, Special Issue of the 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
This artifact supports the paper titled "Incremental Computing by Differential Execution" accepted at ECOOP 2025. It provides a mechanized formalization in Rocq of the differential semantics and optimizations presented in the paper, along with a reference implementation of the differential interpreter in Scala. The artifact includes the Bellman-Ford benchmark used for the performance evaluation in Section 7. Both components are packaged as Docker images for ease of use and reproducibility, enabling verification of all claims made in the paper.
Cite as

Prashant Kumar, André Pacak, and Sebastian Erdweg. Incremental Computing by Differential Execution (Artifact). In Special Issue of the 39th European Conference on Object-Oriented Programming (ECOOP 2025). Dagstuhl Artifacts Series (DARTS), Volume 11, Issue 2, pp. 13:1-13:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{kumar_et_al:DARTS.11.2.13,
  author =	{Kumar, Prashant and Pacak, Andr\'{e} and Erdweg, Sebastian},
  title =	{{Incremental Computing by Differential Execution (Artifact)}},
  pages =	{13:1--13:8},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2025},
  volume =	{11},
  number =	{2},
  editor =	{Kumar, Prashant and Pacak, Andr\'{e} and Erdweg, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.11.2.13},
  URN =		{urn:nbn:de:0030-drops-233564},
  doi =		{10.4230/DARTS.11.2.13},
  annote =	{Keywords: Incremental computing, differential semantics, programming language design, formal verification, big-step semantics}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2023.5
Modular Abstract Definitional Interpreters for WebAssembly

Authors: Katharina Brandl, Sebastian Erdweg, Sven Keidel, and Nils Hansen

Published in: LIPIcs, Volume 263, 37th European Conference on Object-Oriented Programming (ECOOP 2023)

Abstract
Even though static analyses can improve performance and secure programs against vulnerabilities, no static whole-program analyses exist for WebAssembly (Wasm) to date. Part of the reason is that Wasm has many complex language concerns, and it is not obvious how to adopt existing analysis frameworks for these features. This paper explores how abstract definitional interpretation can be used to develop sophisticated analyses for Wasm and other complex languages efficiently. In particular, we show that the semantics of Wasm can be decomposed into 19 language-independent components that abstract different aspects of Wasm. We have written a highly configurable definitional interpreter for full Wasm 1.0 in 1628 LOC against these components. Analysis developers can instantiate this interpreter with different value and effect abstractions to obtain abstract definitional interpreters that compute inter-procedural control and data-flow information. This way, we develop the first whole-program dead code, constant propagation, and taint analyses for Wasm, each in less than 210 LOC. We evaluate our analyses on 1458 Wasm binaries collected by others in the wild. Our implementation is based on a novel framework for definitional abstract interpretation in Scala that eliminates scalability issues of prior work.
Cite as

Katharina Brandl, Sebastian Erdweg, Sven Keidel, and Nils Hansen. Modular Abstract Definitional Interpreters for WebAssembly. In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 5:1-5:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brandl_et_al:LIPIcs.ECOOP.2023.5,
  author =	{Brandl, Katharina and Erdweg, Sebastian and Keidel, Sven and Hansen, Nils},
  title =	{{Modular Abstract Definitional Interpreters for WebAssembly}},
  booktitle =	{37th European Conference on Object-Oriented Programming (ECOOP 2023)},
  pages =	{5:1--5: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/entities/document/10.4230/LIPIcs.ECOOP.2023.5},
  URN =		{urn:nbn:de:0030-drops-181982},
  doi =		{10.4230/LIPIcs.ECOOP.2023.5},
  annote =	{Keywords: Static Analysis, WebAssembly}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.10
On Solving Solved Problems

Authors: Sebastian Erdweg

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
Some problems are considered solved by the research community. But are they really and does that mean we should stop investigating them? In this essay, I argue that "solved" problems often only appear solved on the surface, while fundamental open research problems lurk below the surface. It requires dedicated researchers to discover those open problems by applying the existing solutions and putting them to the test.
Cite as

Sebastian Erdweg. On Solving Solved Problems. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 10:1-10:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{erdweg:OASIcs.EVCS.2023.10,
  author =	{Erdweg, Sebastian},
  title =	{{On Solving Solved Problems}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{10:1--10:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.10},
  URN =		{urn:nbn:de:0030-drops-177800},
  doi =		{10.4230/OASIcs.EVCS.2023.10},
  annote =	{Keywords: Research Methodology, Parsing, Type Checking}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2022.7
Functional Programming with Datalog

Authors: André Pacak and Sebastian Erdweg

Published in: LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022)

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.
Cite as

André Pacak and Sebastian Erdweg. Functional Programming with Datalog. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 7:1-7:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ECOOP.2022.7},
  URN =		{urn:nbn:de:0030-drops-162354},
  doi =		{10.4230/LIPIcs.ECOOP.2022.7},
  annote =	{Keywords: Datalog, functional programming, demand transformation}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2017.18
A Co-contextual Type Checker for Featherweight Java

Authors: Edlira Kuci, Sebastian Erdweg, Oliver Bracevac, Andi Bejleri, and Mira Mezini

Published in: LIPIcs, Volume 74, 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract
This paper addresses compositional and incremental type checking for object-oriented programming languages. Recent work achieved incremental type checking for structurally typed functional languages through co-contextual typing rules, a constraint-based formulation that removes any context dependency for expression typings. However, that work does not cover key features of object-oriented languages: Subtype polymorphism, nominal typing, and implementation inheritance. Type checkers encode these features in the form of class tables, an additional form of typing context inhibiting incrementalization. In the present work, we demonstrate that an appropriate co-contextual notion to class tables exists, paving the way to efficient incremental type checkers for object-oriented languages. This yields a novel formulation of Igarashi et al.'s Featherweight Java (FJ) type system, where we replace class tables by the dual concept of class table requirements and class table operations by dual operations on class table requirements. We prove the equivalence of FJ's type system and our co-contextual formulation. Based on our formulation, we implemented an incremental FJ type checker and compared its performance against javac on a number of realistic example programs.
Cite as

Edlira Kuci, Sebastian Erdweg, Oliver Bracevac, Andi Bejleri, and Mira Mezini. A Co-contextual Type Checker for Featherweight Java. In 31st European Conference on Object-Oriented Programming (ECOOP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 74, pp. 18:1-18:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kuci_et_al:LIPIcs.ECOOP.2017.18,
  author =	{Kuci, Edlira and Erdweg, Sebastian and Bracevac, Oliver and Bejleri, Andi and Mezini, Mira},
  title =	{{A Co-contextual Type Checker for Featherweight Java}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{18:1--18:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{M\"{u}ller, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.18},
  URN =		{urn:nbn:de:0030-drops-72628},
  doi =		{10.4230/LIPIcs.ECOOP.2017.18},
  annote =	{Keywords: type checking, co-contextual, constraints, class table, Featherweight Java}
}
Document
DOI: 10.4230/DagRep.6.10.1
Programming Language Techniques for Incremental and Reactive Computing (Dagstuhl Seminar 16402)

Authors: Camil Demetrescu, Sebastian Erdweg, Matthew A. Hammer, and Shriram Krishnamurthi

Published in: Dagstuhl Reports, Volume 6, Issue 10 (2017)

Abstract
Incremental computations are those that process input changes faster than naive computation that runs from scratch, and reactive computations consist of interactive behavior that varies over time. Due to the importance and prevalence of incremental, reactive systems, ad hoc variants of incremental and reactive computation are ubiquitous in modern software systems. In response to this reality, the PL research community has worked for several decades to advance new languages for systems that interface with a dynamically-changing environment. In this space, researchers propose new general-purpose languages and algorithms to express and implement efficient, dynamic behavior, in the form of incremental and reactive language systems. While these research lines continue to develop successfully, this work lacks a shared community that synthesizes a collective discussion about common motivations, alternative techniques, current results and future challenges. To overcome this lack of community, this seminar will work towards building one, by strengthening existing research connections and by forging new ones. Developing a shared culture is critical to the future advancement of incremental and reactive computing in modern PL research, and in turn, this PL research is critical to developing the efficient, understandable interactive systems of the future.
Cite as

Camil Demetrescu, Sebastian Erdweg, Matthew A. Hammer, and Shriram Krishnamurthi. Programming Language Techniques for Incremental and Reactive Computing (Dagstuhl Seminar 16402). In Dagstuhl Reports, Volume 6, Issue 10, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{demetrescu_et_al:DagRep.6.10.1,
  author =	{Demetrescu, Camil and Erdweg, Sebastian and Hammer, Matthew A. and Krishnamurthi, Shriram},
  title =	{{Programming Language Techniques for Incremental and Reactive Computing (Dagstuhl Seminar 16402)}},
  pages =	{1--12},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{10},
  editor =	{Demetrescu, Camil and Erdweg, Sebastian and Hammer, Matthew A. and Krishnamurthi, Shriram},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.10.1},
  URN =		{urn:nbn:de:0030-drops-69491},
  doi =		{10.4230/DagRep.6.10.1},
  annote =	{Keywords: Incremental computing, reactive programming, memoization, change propagation, dynamic dependency graph, dataflow programming, live programming}
}
Document
DOI: 10.4230/DagRep.5.2.26
Domain-Specific Languages (Dagstuhl Seminar 15062)

Authors: Sebastian Erdweg, Martin Erwig, Richard F. Paige, and Eelco Visser

Published in: Dagstuhl Reports, Volume 5, Issue 2 (2015)

Abstract
This report documents the program and outcomes of Dagstuhl Seminar 15062 “Domain-Specific Languages”, which took place February 1-6, 2015. The seminar was motivated on the one hand by the high interest in domain-specific languages in academia and industry and on the other hand by the observation that the community is divided into largely disconnected subdisciplines (e.g., internal, external, visual, model-driven). The seminar included participants across these subdisciplines and included overview talks, technical talks, demos, discussion groups, and an industrial panel. This report collects the abstracts of talks and other activities at the seminar and summarizes the outcomes of the seminar.
Cite as

Sebastian Erdweg, Martin Erwig, Richard F. Paige, and Eelco Visser. Domain-Specific Languages (Dagstuhl Seminar 15062). In Dagstuhl Reports, Volume 5, Issue 2, pp. 26-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{erdweg_et_al:DagRep.5.2.26,
  author =	{Erdweg, Sebastian and Erwig, Martin and Paige, Richard F. and Visser, Eelco},
  title =	{{Domain-Specific Languages (Dagstuhl Seminar 15062)}},
  pages =	{26--43},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{2},
  editor =	{Erdweg, Sebastian and Erwig, Martin and Paige, Richard F. and Visser, Eelco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.2.26},
  URN =		{urn:nbn:de:0030-drops-50434},
  doi =		{10.4230/DagRep.5.2.26},
  annote =	{Keywords: Internal DSLs, External DSLs, Domain-specific modeling, Extensible languages, Language workbenches, Textual/graph-based/visual languages, Language design, Language implementation techniques}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact