Marcus Rossel

Marcus Rossel

Auto-generated profile, based on publicly available information

Marcus Rossel

Barkhausen Institut, Dresden, Germany

Research Focus & Metrics

Academic Career Length

3Years (2024-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
10 June 2025 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
RSRudi Schneider
Rudi Schneider
MRMarcus Rossel
Marcus Rossel
ASAmir Shaikhha
Amir Shaikhha
AGAndrés Goens
Andrés Goens
TKThomas Kœhler
Thomas Kœhler
MSMichel Steuwer
Michel Steuwer
Equality saturation has gained significant interest as a powerful optimization and reasoning technique. At its heart is the e-graph data structure, that space-efficiently represents equal sub-terms uniquely. An important open problem in this context is extending this efficient representation to languages featuring (bound) variables. Independent of how we represent variables in e-graphs, either as names or nameless (using de Bruijn indices), sharing is broken as sub-terms that differ only in the names of their variables are represented separately. This results in aggressive e-graph growth, bad performance, as well as reduced expressiveness. In this paper, we present a novel approach to representing bound variables in e-graphs by making them a first-class built-in feature of the data structure. Our slotted e-graph represents terms that differ only by (bound or free) variable names uniquely. To do so, e-classes that represent equivalent terms via e-nodes are parameterized by slots , abstracting over free variables of the represented terms. Referring to an e-class from an e-node now requires relating the variables from its context to the slots of the e-class. Our evaluation of slotted e-graph uses two case studies from compiler optimization and theorem proving to show that performing equality saturation for languages with bound variables is greatly simplified and that we can solve practically relevant problems that cannot be solved with e-graphs using de Bruijn indices.

27 July 2024
Verified
Book Chapter
Closed access
PDF file
MRMarcus Rossel
Marcus Rossel
SLShaokai Lin
Shaokai Lin
MLMarten Lohstroh
Marten Lohstroh
JCJeronimo Castrillon
Jeronimo Castrillon
AGAndrés Goens
Andrés Goens

8 January 2026 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MRMarcus Rossel
Marcus Rossel
RSRudi Schneider
Rudi Schneider
TKThomas Kœhler
Thomas Kœhler
MSMichel Steuwer
Michel Steuwer
AGAndrés Goens
Andrés Goens
Equations are ubiquitous in mathematical reasoning. Often, however, they only hold under certain conditions. As these conditions are usually clear from context, mathematicians regularly omit them when performing equational reasoning on paper. In contrast, interactive theorem provers pedantically insist on every detail to be convinced that a theorem holds, hindering equational reasoning at the more abstract level of pen-and-paper mathematics. In this paper, we address this issue by raising the level of equational reasoning to enable pen-and-paper style in interactive theorem provers. We achieve this by interpreting theorems as conditional rewrite rules, and use equality saturation to automatically derive equational proofs. Conditions that cannot be automatically proven may be surfaced as proof obligations. Concretely, we present how to interpret theorems as conditional rewrite rules for a significant class of theorems. Handling these theorems goes beyond simple syntactic rewriting, and deals with aspects like propositional conditions and type classes. We evaluate our approach by implementing it as a tactic in Lean, using the egg library for equality saturation with e-graphs. We show four use cases demonstrating the efficacy of this higher level of abstraction for equational reasoning.

16 May 2024 in arXiv
Verified
Preprint
Open access
PDF file
MRMarcus Rossel
Marcus Rossel
AGAndrés Goens
Andrés Goens
Interactive theorem provers, like Isabelle/HOL, Coq and Lean, have expressive languages that allow the formalization of general mathematical objects and proofs. In this context, an important goal is to reduce the time and effort needed to prove theorems. A significant means of achieving this is by improving proof automation. We have implemented an early prototype of proof automation for equational reasoning in Lean by using equality saturation. To achieve this, we need to bridge the gap between Lean's expression semantics and the syntactically driven e-graphs in equality saturation. This involves handling bound variables, implicit typing, as well as Lean's definitional equality, which is more general than syntactic equality and involves notions like $α$-equivalence, $β$-reduction, and $η$-reduction. In this extended abstract, we highlight how we attempt to bridge this gap, and which challenges remain to be solved. Notably, while our techniques are partially unsound, the resulting proof automation remains sound by virtue of Lean's proof checking.