{"article":{"slug":"automatic-checking-of-compiler-correctness-with-e-graphs","title":"Automatic Checking of Compiler Correctness with E-Graphs","subtitle":null,"summary":"MIT professor Adam Chlipala describes CSAIL research on using e-graphs to automatically check that compiler optimizations are correct, as part of his series on building correct, efficient programs from proven rewrite rules.","content_type":"research","language":"en","canonical_url":"https://stng.substack.com/p/automatic-checking-of-compiler-correctness","author":{"name":"Adam Chlipala","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Structure and Guarantees","url":"https://stng.substack.com/","listing_slug":null,"listing":null},"topics":[{"name":"compilers","slug":"compilers","url":"https://listedarticles.com/topics/compilers"},{"name":"research","slug":"research","url":"https://listedarticles.com/topics/research"},{"name":"programming-languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":2942,"reading_minutes":13,"published_at":"2026-11-17T13:23:47.000Z","added_at":"2026-11-17T19:53:05.916Z","updated_at":"2026-11-17T19:53:05.916Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/automatic-checking-of-compiler-correctness-with-e-graphs","markdown_url":"https://listedarticles.com/articles/automatic-checking-of-compiler-correctness-with-e-graphs.md","example":false,"citation":"Adam Chlipala, Structure and Guarantees. \"Automatic Checking of Compiler Correctness with E-Graphs.\" 17 Nov 2026. https://stng.substack.com/p/automatic-checking-of-compiler-correctness (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://stng.substack.com/p/automatic-checking-of-compiler-correctness"},"body_markdown":"*This article is crossposted between Prof. Adam Chlipala’s blog* [Structure and Guarantees](https://stng.substack.com/) *and [the blog of CSAIL](https://csailmit.substack.com/), the MIT lab where the research being discussed took place.*\n\nI’m in the home stretch of a series of articles on [constructing correct and efficient programs step-by-step using proven rewrite rules](https://stng.substack.com/p/correct-by-construction-code-via), which I argue is an important alternative to the ways AI coding agents are being used widely today. Previous examples have included [tensor programs](https://stng.substack.com/p/high-level-algebra-for-low-level), [digital hardware](https://stng.substack.com/p/deriving-efficient-hardware-in-the), and [low-level cryptographic software](https://stng.substack.com/p/random-search-and-guaranteed-correctness). [The last article](https://stng.substack.com/p/exploring-exponentially-many-programs) introduced e-graphs, a data structure and set of related algorithms for efficiently exploring many alternative ways to write algebraic expressions. That technology has proven very useful for both program verification and program optimization.\n\nThanks for reading Structure and Guarantees! Subscribe for free to receive new posts and support my work.\n\nI’m going to give an example now of this approach in action, in hot-off-the-presses research. [Our paper](https://adam.chlipala.net/papers/EgraphsPOPL27/) to appear at [POPL 2027](https://popl27.sigplan.org/) in January in Mexico City uses e-graphs to automate formal verification of compilers. It seems to be the first example of a general proof-automation tool that can take in a [compiler](https://en.wikipedia.org/wiki/Compiler) definition for a new programming language the tool has never seen before, with no extra annotations meant just to guide theorem proving, and prove it correct automatically. (There are past examples that applied to fixed programming languages, as in [Cobalt](https://web.cs.ucla.edu/~todd/research/pub.php?id=pldi03) and [Rhodium](https://www.cs.cornell.edu/~lerner/papers/rhodium-popl2005.pdf).) The final version of the paper isn’t quite posted as of this writing, but you can find the details in first author [Dustin Jamner](https://jamner.net/)’s [PhD dissertation](https://adam.chlipala.net/theses/dijamner.pdf). Undergraduate [Tilek Askerbekov](https://www.linkedin.com/in/tilek-askerbekov-36a844207/) also contributed to this paper.\n\n# What Kind of Compilers?\n\nFirst I need to level with you about what kind of compiler we are talking about. It’s not one that looks especially like [GCC](https://en.wikipedia.org/wiki/GNU_Compiler_Collection) or [Clang](https://en.wikipedia.org/wiki/Clang), the canonical ways to resolve that word in industry. Instead, let me welcome you to the mathematically intriguing parallel universe of compilers for [functional programming languages](https://en.wikipedia.org/wiki/Functional_programming). The compilers our research project deals with follow in the tradition of classic research paper [“From System F to Typed Assembly Language”](https://www.cs.princeton.edu/~dpw/papers/tal-toplas.pdf). I’m not exactly an unbiased evaluator of this set of ideas, having done a postdoc with faculty author of the paper [Greg Morrisett](https://tech.cornell.edu/people/greg-morrisett/) and undergraduate research with *his* former PhD advisor [Bob Harper](https://www.cs.cmu.edu/~rwh/). Let’s take a quick look, though, at how this kind of compiler works. The idea is that compilation is broken into stages, and every intermediate form of a program is checked in a sound type system that guarantees lack of crashes, which is very different from classic compilers that quickly drop down to intermediate languages where all safety bets are off.\n\nTo avoid gratuitous dependencies on functional-programming lore, I’ll use an example program from [Python](https://en.wikipedia.org/wiki/Python_(programming_language)), which we want to compile, gradually, until it becomes sufficiently like [assembly language](https://en.wikipedia.org/wiki/Assembly_language). Our starting program is a nice simple one.\n\n```\ndef square(x):\n    return x * x\n\ndef compute(x):\n    return square(x + 1) + 3\n\nprint(compute(4))\n```\n\nProgrammers generally take for granted the ability for one function to call another, which calls another, and so on. This freedom is usually implemented behind the scenes with a [call stack](https://en.wikipedia.org/wiki/Call_stack). Our first compiler transformation will make the call stack explicit. In fact, the call stack will manifest as a chain of [first-class functions](https://en.wikipedia.org/wiki/First-class_function), with each calling the function for the next lower level of the stack. This transformation is conversion to [continuation-passing style](https://en.wikipedia.org/wiki/Continuation-passing_style), where we use “continuation” to refer to the functions we are introducing.\n\n```\ndef square(x, k):\n    k(x * x)\n\ndef compute(x, k):\n    def after_square(y):\n        k(y + 3)\n\n    square(x + 1, after_square)\n\ncompute(4, print)\n```\n\nNotice what happened: each function now takes a continuation `k` as an explicit argument. Where a function would have returned, it instead calls its continuation with the result. Now no function (beyond certain primitives) ever returns, which lines up well with how hardware execution actually works. The call stack was just an opt-in fiction that feels natural to us because our brains evolved to understand natural language with similar structure (a soap box I’ll climb back onto in a future article or two, to explain some downsides for practical programming of giving this fiction too much special status). This example also depends somewhat on [tail-call optimization](https://en.wikipedia.org/wiki/Tail_call) for its reasonableness, which Python doesn’t actually provide, but let’s imagine that it did.\n\nWhat about this code is still too distant from what hardware can support directly? The function definition of `after_square` casually mentions a variable `k` *from the enclosing scope*. The term of art is that `after_square` is a *lexical [closure](https://en.wikipedia.org/wiki/Closure_(computer_programming)) that captures variable* `k`. This kind of mechanism is rather remote from what is natural to implement in hardware, so we also want a *closure conversion* compiler phase that removes use of captured variables, instead changing those variables into explicit function arguments, packaged up in first-class *environments*. The result for our running example is:\n\n```\ndef invoke(closure, value):\n    code, env = closure\n    code(env, value)\n\ndef square(env, x, k):\n    invoke(k, x * x)\n\ndef after_square(env, y):\n    k = env[\"k\"]\n    invoke(k, y + 3)\n\ndef compute(env, x, k):\n    continuation = (after_square, {\"k\": k})\n    square({}, x + 1, continuation)\n\ndef print_result(env, value):\n    print(value)\n\ninitial_continuation = (print_result, {})\ncompute({}, 4, initial_continuation)\n```\n\nEvery place a first-class function value appeared before, we now see an explicit *closure*, a pair of a function reference and an environment dictionary that packages up all of the captured variables that function is allowed to access. A useful property of this code is that all [control flow](https://en.wikipedia.org/wiki/Control_flow), or code that determines which other code should run, now uses features that map fairly directly to assembly language. In contrast, program features like nested function definitions with variable capture wind up looking rather different in assembly. The generated code still uses data structures like tuples and dictionaries, so further compilation phases are needed to explain those features with more-primitive constructs, but I’ll cut off the example here.\n\nThe paper I cited earlier in this section associates such programs and transformations with [static types](https://en.wikipedia.org/wiki/Type_system#STATIC), which can be checked to ensure absence of crashes and other problems. It would be too much of a digression for me to review the type-system features needed to handle everything we’ve just seen in code, but the types are also a central part of our new verification flow.\n\n# Languages and Compilers, Modularly\n\nThis kind of compiler is already hard enough to get right, but our new result is based on the framework from the first half of Dustin’s PhD thesis, [Pyrosome](https://adam.chlipala.net/papers/PyrosomeOOPSLA25/), which shows how to define programming languages and their formally verified compilers *modularly*. That is, with Pyrosome, we can define *language-feature modules* that explain features worth adding to programming languages, tagged with snippets of compiler code that should be used to implement those features. More importantly, a module can be formally verified in isolation. The upshot is that any set of modules compatible in a certain syntactic sense can be *linked together* to form a full programming language with its compiler ready to go, getting a correctness theorem for that compiler “for free.”\n\nThe challenge of this setting is to allow verifying snippets of compilers in a way that guarantees correct behavior when they are linked together with arbitrary other snippets, up to the framework-level rules we set about what makes a valid feature module and when linking is permitted.\n\nPyrosome is organized in a way very compatible with [the worldview of rewrite rules and logical guarantees](https://stng.substack.com/p/correct-by-construction-code-via) that I’ve been pushing. Here is the basic anatomy of a language-feature module. (I will take some liberties simplifying syntax and other aspects for this article.)\n\nThe most fundamental thing a module does is extend a grammar of syntactic language features, which I’ll write here using syntax inspired by [Backus-Naur form](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form). Here is how a module introducing length-two tuples would extend a grammar of expressions.\n\n```\nexp ::= ... | (exp, exp) | exp.1 | exp.2\n```\n\nWe should also introduce a new shape of type for tuples and give typing rules for tuple expressions, where I write `e : t` for the fact that expression `e` has type `t`. Rules are considered to quantify implicitly over all of the variables they mention.\n\n```\ntype ::= ... | type * type\n\nrule: e1 : t1 && e2 : t2 -> (e1, e2) : t1 * t2\n\nrule: e : t1 * t2 -> e.1 : t1\n\nrule: e : t1 * t2 -> e.2 : t2\n```\n\nThe next two ingredients are the most interesting for how compiler correctness is formulated in Pyrosome. First, a module declares *equational rules* that explain how expressions evaluate. Providing these rules is, in some sense, extra work to help the automated theorem prover, but the rules also feed into the definition of correctness for a compiler. We would need them just to make clear what the theorem statement is. Here a `v` variable enforces that a subterm is a *value*, e.g. a constant of some primitive type. This restriction is important to keep the following equations from dropping subterms that produce important side effects; even if the language-feature module we are writing involves no direct use of side effects, it might be linked later with one that does.\n\n```\nrule: (v1, v2).1 = v1\n\nrule: (v1, v2).2 = v2\n```\n\nSecond, a module gives the cases of compiler phases for its language features. Here is a sample for conversion to continuation-passing style, where we assume some variable `k` is available in the generated program, to stand for the continuation argument of the current function. (Things start to get muddled here around different kinds of variables [program variables vs. *[metavariables](https://en.wikipedia.org/wiki/Metavariable)* of our logical reasoning], but see the research papers for a full formal disentanglement.) I write `e1[x |-> e2]` for substituting expression `e2` for occurrences of variable `x` in expression `e1`, a notation used here for plugging in particular values for the ambient continuation `k`. We also have `fun x => ...` syntax for an anonymous function (like `lambda` in Python).\n\n```\ncps_conv((e1, e2)) = cps_conv(e1)[k |-> fun x1 => cps_conv(e2)[k |-> fun x2 => k((x1, x2))]]\n```\n\nThis somewhat-tricky expansion of a tupling expression evaluates each component expression in sequence, assigning names `x1` and `x2` to the results, where we then combine those values into a tuple to pass off to the current continuation.\n\nHow does Pyrosome formulate correctness of a language-feature module? It is tempting to assume that we should generate one proof obligation per snippet of compiler code. Pyrosome instead does something less obvious: we get one proof obligation *per equational rule explaining a feature of the compiler’s source language*. What does this proof obligation say? It says that, given source-language expressions matching the two sides of the rule, *the compilations of those two expressions are provably equal in the target language*, using the equations declared for that target language. There is some subtlety to why this formulation is appealingly modular, but it really does allow defining language features and their compiler code separately, with easy linking into full languages and their compilers. See the dissertation for an explanation of why this notion of correctness maps well onto prior formulations of compiler correctness, but for instance it covers showing that a source program that returns a particular integer is compiled into a target program that returns the same integer. This conclusion applies even for Turing-complete languages where the compiler has no hope of figuring out universally in advance which integer a program evaluates to.\n\nFor our first example equational rule above, we get the obligation `cps_conv((v1, v2).1) = cps_conv(v1)`. The lefthand side of this equation can be simplified using the definition of `cps_conv`, for cases like the one for tuple construction shown above and one for projecting the first element of a tuple that I haven’t shown. Then we must apply equational rules of the target language to complete the proof. Our original paper on Pyrosome presented some proof automation that is able to discharge *most* of the obligations, in a case study inspired by “From System F to Typed Assembly Language.” However, a fair number of manual proof cases remained.\n\n# Using E-Graphs to Automate Proof of Compiler Correctness Obligations\n\nThe original automation kept hitting a proof obligation with the equational rules of all the language-feature modules involved, in a [greedy](https://en.wikipedia.org/wiki/Greedy_algorithm) approach with no backtracking. [As we covered in the last article](https://stng.substack.com/p/exploring-exponentially-many-programs), this appealingly simple approach can get stuck in local optima, where the two sides of an equation to be proved don’t actually rewrite into the same form, even though a rewrite sequence does exist to make them match. A concrete class of example from this project is proofs that require use of *[eta laws](https://en.wikipedia.org/wiki/Lambda_calculus_definition#%CE%B7-reduction)*, which are sometimes used to expand expressions, rather than simplifying them, as in asserting `f = fun x => f(x)` for any value `f` of function type. Our new solution is exactly the one from the prior article: use of an automated theorem prover based on e-graphs. We will explore many possible rewritings of an expression, representing the set of possibilities compactly and using fast operations to search for new rewrite opportunities.\n\nOur e-graph engine is inspired by [egglog](https://github.com/egraphs-good/egglog), a popular tool that reduces e-graph operations to the [Datalog](https://en.wikipedia.org/wiki/Datalog) database query language. Dustin reimplemented the core of egglog inside the logic of [the Rocq Prover](https://en.wikipedia.org/wiki/Rocq). That is, this implementation is a [purely functional](https://en.wikipedia.org/wiki/Purely_functional_programming) program in the native language that Rocq likes to reason about, which raised some new implementation challenges that were different from those that showed up in egglog’s original implementation in an [imperative](https://en.wikipedia.org/wiki/Imperative_programming) language. Thanks to using Rocq’s native language, Dustin was able to prove soundness of the engine without dealing with vagaries of any popular imperative language that could have been used instead to implement the engine. There are also engine features specific to Pyrosome and how to encode its proof obligations as egglog-style queries; these features are proved, too.\n\nThe end result is a function inside Rocq that takes in the code of a language-feature module and delivers a verdict on its correctness: either “proved correct” or “failed to prove correctness.” This function is itself proved correct, so no further human effort is needed in applying it within a Rocq development. This design choice contrasts with the other common one of having such an engine output a proof justifying its conclusion for any individual run, which imposes a continuing performance cost for generation of proofs.\n\nNow, sometimes verification fails, whether because of an actual compiler bug or because of an incompleteness in the e-graph engine. Such incompleteness is inevitable, because exploring all possible rewrite sequences from some starting point can generate too many term variants to store, even using a clever data structure with sharing, so a numeric cutoff on number of rounds of search is typically employed. It is important to give useful feedback to the programmer when verification fails. We want to explain to the programmer which equality couldn’t be established, in the simplest possible terms. Partly to that end, this new engine includes an *extraction* feature of the kind we discussed last time, to produce the *shortest* term found so far to represent some value.\n\nThe last post sketched an extraction approach that works on e-graphs structured as trees. Following egg, our new engine can handle extraction from general e-graphs, with a somewhat-flexible notion of *additive* cost functions, which give the metrics we optimize in finding best encodings of values. The trick is to plan ahead: all nodes of e-graphs are always annotated with their values according to chosen cost functions, and any e-graph modification requires fixing up these values. Then a simple linear-time graph traversal can extract the lowest-cost representation for any node (though that representation may be represented as a graph with sharing, so that naive printing as a tree takes more than linear time).\n\n[![](https://substackcdn.com/image/fetch/$s_!unq7!,w_1456,c_limit,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fdfd4a574-0d9b-4516-be10-96787b7bac23_1536x1024.png)](https://substackcdn.com/image/fetch/$s_!unq7!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fdfd4a574-0d9b-4516-be10-96787b7bac23_1536x1024.png)\n\nThe evaluation from our paper shows that this engine automates proof of every obligation associated with the compiler inspired by “From System F to Typed Assembly Language,” when we restrict to avoid [polymorphism](https://en.wikipedia.org/wiki/Parametric_polymorphism) in the source language. We have a few other case studies (including adding in that polymorphism) that generate a handful of lingering obligations with manual proofs (about 5 out of about 200 obligations across all the case studies). The full implementation includes using the e-graph for [type inference](https://en.wikipedia.org/wiki/Type_inference) as well, which is applied to fill in missing type annotations within rules written in convenient surface syntax.\n\n# Conclusion\n\nThis new functionality allows rapid experimentation with new programming-language features and their compiler code, since we have an oracle that checks correctness automatically. We can imagine AI coding agents appealing to that check via tool calls, delivering formally verified compilers after experimenting for a while with language and compiler design. The catch is that the check is implemented as a sequential functional program, and it can effectively time out or run out of memory on goals that only seem moderately complex. We would really rather have something more like the traditional low-level, performance-optimized implementations of Datalog, but still formally verified. The more parallel the implementation, the better, most likely. I’ll be returning in later articles to this theme, along with more detail of how a Datalog implementation works and how to reduce to Datalog various queries in theorem proving and program optimization.\n\nThere is one more example I want to give of gradually deriving a correct program with logically sound steps, this time for fairly open-ended C programming. Before I go there two weeks from now, I’ll use next week to weigh in on the increasing use of AI agents to enforce correctness on other AI agents, the inherent trust weaknesses of that style, and how deterministic approaches like formal methods can come to the rescue, demonstrated with a new benchmark suite from my startup [Nectry](https://nectry.com/).\n","body_html":"<p><em>This article is crossposted between Prof. Adam Chlipala’s blog</em> <a href=\"https://stng.substack.com/\" rel=\"nofollow ugc noopener\">Structure and Guarantees</a> <em>and <a href=\"https://csailmit.substack.com/\" rel=\"nofollow ugc noopener\">the blog of CSAIL</a>, the MIT lab where the research being discussed took place.</em></p>\n<p>I’m in the home stretch of a series of articles on <a href=\"https://stng.substack.com/p/correct-by-construction-code-via\" rel=\"nofollow ugc noopener\">constructing correct and efficient programs step-by-step using proven rewrite rules</a>, which I argue is an important alternative to the ways AI coding agents are being used widely today. Previous examples have included <a href=\"https://stng.substack.com/p/high-level-algebra-for-low-level\" rel=\"nofollow ugc noopener\">tensor programs</a>, <a href=\"https://stng.substack.com/p/deriving-efficient-hardware-in-the\" rel=\"nofollow ugc noopener\">digital hardware</a>, and <a href=\"https://stng.substack.com/p/random-search-and-guaranteed-correctness\" rel=\"nofollow ugc noopener\">low-level cryptographic software</a>. <a href=\"https://stng.substack.com/p/exploring-exponentially-many-programs\" rel=\"nofollow ugc noopener\">The last article</a> introduced e-graphs, a data structure and set of related algorithms for efficiently exploring many alternative ways to write algebraic expressions. That technology has proven very useful for both program verification and program optimization.</p>\n<p>Thanks for reading Structure and Guarantees! Subscribe for free to receive new posts and support my work.</p>\n<p>I’m going to give an example now of this approach in action, in hot-off-the-presses research. <a href=\"https://adam.chlipala.net/papers/EgraphsPOPL27/\" rel=\"nofollow ugc noopener\">Our paper</a> to appear at <a href=\"https://popl27.sigplan.org/\" rel=\"nofollow ugc noopener\">POPL 2027</a> in January in Mexico City uses e-graphs to automate formal verification of compilers. It seems to be the first example of a general proof-automation tool that can take in a <a href=\"https://en.wikipedia.org/wiki/Compiler\" rel=\"nofollow ugc noopener\">compiler</a> definition for a new programming language the tool has never seen before, with no extra annotations meant just to guide theorem proving, and prove it correct automatically. (There are past examples that applied to fixed programming languages, as in <a href=\"https://web.cs.ucla.edu/~todd/research/pub.php?id=pldi03\" rel=\"nofollow ugc noopener\">Cobalt</a> and <a href=\"https://www.cs.cornell.edu/~lerner/papers/rhodium-popl2005.pdf\" rel=\"nofollow ugc noopener\">Rhodium</a>.) The final version of the paper isn’t quite posted as of this writing, but you can find the details in first author <a href=\"https://jamner.net/\" rel=\"nofollow ugc noopener\">Dustin Jamner</a>’s <a href=\"https://adam.chlipala.net/theses/dijamner.pdf\" rel=\"nofollow ugc noopener\">PhD dissertation</a>. Undergraduate <a href=\"https://www.linkedin.com/in/tilek-askerbekov-36a844207/\" rel=\"nofollow ugc noopener\">Tilek Askerbekov</a> also contributed to this paper.</p>\n<h1 id=\"what-kind-of-compilers\">What Kind of Compilers?</h1>\n<p>First I need to level with you about what kind of compiler we are talking about. It’s not one that looks especially like <a href=\"https://en.wikipedia.org/wiki/GNU_Compiler_Collection\" rel=\"nofollow ugc noopener\">GCC</a> or <a href=\"https://en.wikipedia.org/wiki/Clang\" rel=\"nofollow ugc noopener\">Clang</a>, the canonical ways to resolve that word in industry. Instead, let me welcome you to the mathematically intriguing parallel universe of compilers for <a href=\"https://en.wikipedia.org/wiki/Functional_programming\" rel=\"nofollow ugc noopener\">functional programming languages</a>. The compilers our research project deals with follow in the tradition of classic research paper <a href=\"https://www.cs.princeton.edu/~dpw/papers/tal-toplas.pdf\" rel=\"nofollow ugc noopener\">“From System F to Typed Assembly Language”</a>. I’m not exactly an unbiased evaluator of this set of ideas, having done a postdoc with faculty author of the paper <a href=\"https://tech.cornell.edu/people/greg-morrisett/\" rel=\"nofollow ugc noopener\">Greg Morrisett</a> and undergraduate research with <em>his</em> former PhD advisor <a href=\"https://www.cs.cmu.edu/~rwh/\" rel=\"nofollow ugc noopener\">Bob Harper</a>. Let’s take a quick look, though, at how this kind of compiler works. The idea is that compilation is broken into stages, and every intermediate form of a program is checked in a sound type system that guarantees lack of crashes, which is very different from classic compilers that quickly drop down to intermediate languages where all safety bets are off.</p>\n<p>To avoid gratuitous dependencies on functional-programming lore, I’ll use an example program from <a href=\"https://en.wikipedia.org/wiki/Python_(programming_language)\" rel=\"nofollow ugc noopener\">Python</a>, which we want to compile, gradually, until it becomes sufficiently like <a href=\"https://en.wikipedia.org/wiki/Assembly_language\" rel=\"nofollow ugc noopener\">assembly language</a>. Our starting program is a nice simple one.</p>\n<pre><code>def square(x):\n    return x * x\n\ndef compute(x):\n    return square(x + 1) + 3\n\nprint(compute(4))</code></pre>\n<p>Programmers generally take for granted the ability for one function to call another, which calls another, and so on. This freedom is usually implemented behind the scenes with a <a href=\"https://en.wikipedia.org/wiki/Call_stack\" rel=\"nofollow ugc noopener\">call stack</a>. Our first compiler transformation will make the call stack explicit. In fact, the call stack will manifest as a chain of <a href=\"https://en.wikipedia.org/wiki/First-class_function\" rel=\"nofollow ugc noopener\">first-class functions</a>, with each calling the function for the next lower level of the stack. This transformation is conversion to <a href=\"https://en.wikipedia.org/wiki/Continuation-passing_style\" rel=\"nofollow ugc noopener\">continuation-passing style</a>, where we use “continuation” to refer to the functions we are introducing.</p>\n<pre><code>def square(x, k):\n    k(x * x)\n\ndef compute(x, k):\n    def after_square(y):\n        k(y + 3)\n\n    square(x + 1, after_square)\n\ncompute(4, print)</code></pre>\n<p>Notice what happened: each function now takes a continuation <code>k</code> as an explicit argument. Where a function would have returned, it instead calls its continuation with the result. Now no function (beyond certain primitives) ever returns, which lines up well with how hardware execution actually works. The call stack was just an opt-in fiction that feels natural to us because our brains evolved to understand natural language with similar structure (a soap box I’ll climb back onto in a future article or two, to explain some downsides for practical programming of giving this fiction too much special status). This example also depends somewhat on <a href=\"https://en.wikipedia.org/wiki/Tail_call\" rel=\"nofollow ugc noopener\">tail-call optimization</a> for its reasonableness, which Python doesn’t actually provide, but let’s imagine that it did.</p>\n<p>What about this code is still too distant from what hardware can support directly? The function definition of <code>after_square</code> casually mentions a variable <code>k</code> <em>from the enclosing scope</em>. The term of art is that <code>after_square</code> is a <em>lexical <a href=\"https://en.wikipedia.org/wiki/Closure_(computer_programming)\" rel=\"nofollow ugc noopener\">closure</a> that captures variable</em> <code>k</code>. This kind of mechanism is rather remote from what is natural to implement in hardware, so we also want a <em>closure conversion</em> compiler phase that removes use of captured variables, instead changing those variables into explicit function arguments, packaged up in first-class <em>environments</em>. The result for our running example is:</p>\n<pre><code>def invoke(closure, value):\n    code, env = closure\n    code(env, value)\n\ndef square(env, x, k):\n    invoke(k, x * x)\n\ndef after_square(env, y):\n    k = env[&quot;k&quot;]\n    invoke(k, y + 3)\n\ndef compute(env, x, k):\n    continuation = (after_square, {&quot;k&quot;: k})\n    square({}, x + 1, continuation)\n\ndef print_result(env, value):\n    print(value)\n\ninitial_continuation = (print_result, {})\ncompute({}, 4, initial_continuation)</code></pre>\n<p>Every place a first-class function value appeared before, we now see an explicit <em>closure</em>, a pair of a function reference and an environment dictionary that packages up all of the captured variables that function is allowed to access. A useful property of this code is that all <a href=\"https://en.wikipedia.org/wiki/Control_flow\" rel=\"nofollow ugc noopener\">control flow</a>, or code that determines which other code should run, now uses features that map fairly directly to assembly language. In contrast, program features like nested function definitions with variable capture wind up looking rather different in assembly. The generated code still uses data structures like tuples and dictionaries, so further compilation phases are needed to explain those features with more-primitive constructs, but I’ll cut off the example here.</p>\n<p>The paper I cited earlier in this section associates such programs and transformations with <a href=\"https://en.wikipedia.org/wiki/Type_system#STATIC\" rel=\"nofollow ugc noopener\">static types</a>, which can be checked to ensure absence of crashes and other problems. It would be too much of a digression for me to review the type-system features needed to handle everything we’ve just seen in code, but the types are also a central part of our new verification flow.</p>\n<h1 id=\"languages-and-compilers-modularly\">Languages and Compilers, Modularly</h1>\n<p>This kind of compiler is already hard enough to get right, but our new result is based on the framework from the first half of Dustin’s PhD thesis, <a href=\"https://adam.chlipala.net/papers/PyrosomeOOPSLA25/\" rel=\"nofollow ugc noopener\">Pyrosome</a>, which shows how to define programming languages and their formally verified compilers <em>modularly</em>. That is, with Pyrosome, we can define <em>language-feature modules</em> that explain features worth adding to programming languages, tagged with snippets of compiler code that should be used to implement those features. More importantly, a module can be formally verified in isolation. The upshot is that any set of modules compatible in a certain syntactic sense can be <em>linked together</em> to form a full programming language with its compiler ready to go, getting a correctness theorem for that compiler “for free.”</p>\n<p>The challenge of this setting is to allow verifying snippets of compilers in a way that guarantees correct behavior when they are linked together with arbitrary other snippets, up to the framework-level rules we set about what makes a valid feature module and when linking is permitted.</p>\n<p>Pyrosome is organized in a way very compatible with <a href=\"https://stng.substack.com/p/correct-by-construction-code-via\" rel=\"nofollow ugc noopener\">the worldview of rewrite rules and logical guarantees</a> that I’ve been pushing. Here is the basic anatomy of a language-feature module. (I will take some liberties simplifying syntax and other aspects for this article.)</p>\n<p>The most fundamental thing a module does is extend a grammar of syntactic language features, which I’ll write here using syntax inspired by <a href=\"https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form\" rel=\"nofollow ugc noopener\">Backus-Naur form</a>. Here is how a module introducing length-two tuples would extend a grammar of expressions.</p>\n<pre><code>exp ::= ... | (exp, exp) | exp.1 | exp.2</code></pre>\n<p>We should also introduce a new shape of type for tuples and give typing rules for tuple expressions, where I write <code>e : t</code> for the fact that expression <code>e</code> has type <code>t</code>. Rules are considered to quantify implicitly over all of the variables they mention.</p>\n<pre><code>type ::= ... | type * type\n\nrule: e1 : t1 &amp;&amp; e2 : t2 -&gt; (e1, e2) : t1 * t2\n\nrule: e : t1 * t2 -&gt; e.1 : t1\n\nrule: e : t1 * t2 -&gt; e.2 : t2</code></pre>\n<p>The next two ingredients are the most interesting for how compiler correctness is formulated in Pyrosome. First, a module declares <em>equational rules</em> that explain how expressions evaluate. Providing these rules is, in some sense, extra work to help the automated theorem prover, but the rules also feed into the definition of correctness for a compiler. We would need them just to make clear what the theorem statement is. Here a <code>v</code> variable enforces that a subterm is a <em>value</em>, e.g. a constant of some primitive type. This restriction is important to keep the following equations from dropping subterms that produce important side effects; even if the language-feature module we are writing involves no direct use of side effects, it might be linked later with one that does.</p>\n<pre><code>rule: (v1, v2).1 = v1\n\nrule: (v1, v2).2 = v2</code></pre>\n<p>Second, a module gives the cases of compiler phases for its language features. Here is a sample for conversion to continuation-passing style, where we assume some variable <code>k</code> is available in the generated program, to stand for the continuation argument of the current function. (Things start to get muddled here around different kinds of variables [program variables vs. <em><a href=\"https://en.wikipedia.org/wiki/Metavariable\" rel=\"nofollow ugc noopener\">metavariables</a></em> of our logical reasoning], but see the research papers for a full formal disentanglement.) I write <code>e1[x |-&gt; e2]</code> for substituting expression <code>e2</code> for occurrences of variable <code>x</code> in expression <code>e1</code>, a notation used here for plugging in particular values for the ambient continuation <code>k</code>. We also have <code>fun x =&gt; ...</code> syntax for an anonymous function (like <code>lambda</code> in Python).</p>\n<pre><code>cps_conv((e1, e2)) = cps_conv(e1)[k |-&gt; fun x1 =&gt; cps_conv(e2)[k |-&gt; fun x2 =&gt; k((x1, x2))]]</code></pre>\n<p>This somewhat-tricky expansion of a tupling expression evaluates each component expression in sequence, assigning names <code>x1</code> and <code>x2</code> to the results, where we then combine those values into a tuple to pass off to the current continuation.</p>\n<p>How does Pyrosome formulate correctness of a language-feature module? It is tempting to assume that we should generate one proof obligation per snippet of compiler code. Pyrosome instead does something less obvious: we get one proof obligation <em>per equational rule explaining a feature of the compiler’s source language</em>. What does this proof obligation say? It says that, given source-language expressions matching the two sides of the rule, <em>the compilations of those two expressions are provably equal in the target language</em>, using the equations declared for that target language. There is some subtlety to why this formulation is appealingly modular, but it really does allow defining language features and their compiler code separately, with easy linking into full languages and their compilers. See the dissertation for an explanation of why this notion of correctness maps well onto prior formulations of compiler correctness, but for instance it covers showing that a source program that returns a particular integer is compiled into a target program that returns the same integer. This conclusion applies even for Turing-complete languages where the compiler has no hope of figuring out universally in advance which integer a program evaluates to.</p>\n<p>For our first example equational rule above, we get the obligation <code>cps_conv((v1, v2).1) = cps_conv(v1)</code>. The lefthand side of this equation can be simplified using the definition of <code>cps_conv</code>, for cases like the one for tuple construction shown above and one for projecting the first element of a tuple that I haven’t shown. Then we must apply equational rules of the target language to complete the proof. Our original paper on Pyrosome presented some proof automation that is able to discharge <em>most</em> of the obligations, in a case study inspired by “From System F to Typed Assembly Language.” However, a fair number of manual proof cases remained.</p>\n<h1 id=\"using-e-graphs-to-automate-proof-of-compiler-correctness-obligat\">Using E-Graphs to Automate Proof of Compiler Correctness Obligations</h1>\n<p>The original automation kept hitting a proof obligation with the equational rules of all the language-feature modules involved, in a <a href=\"https://en.wikipedia.org/wiki/Greedy_algorithm\" rel=\"nofollow ugc noopener\">greedy</a> approach with no backtracking. <a href=\"https://stng.substack.com/p/exploring-exponentially-many-programs\" rel=\"nofollow ugc noopener\">As we covered in the last article</a>, this appealingly simple approach can get stuck in local optima, where the two sides of an equation to be proved don’t actually rewrite into the same form, even though a rewrite sequence does exist to make them match. A concrete class of example from this project is proofs that require use of <em><a href=\"https://en.wikipedia.org/wiki/Lambda_calculus_definition#%CE%B7-reduction\" rel=\"nofollow ugc noopener\">eta laws</a></em>, which are sometimes used to expand expressions, rather than simplifying them, as in asserting <code>f = fun x =&gt; f(x)</code> for any value <code>f</code> of function type. Our new solution is exactly the one from the prior article: use of an automated theorem prover based on e-graphs. We will explore many possible rewritings of an expression, representing the set of possibilities compactly and using fast operations to search for new rewrite opportunities.</p>\n<p>Our e-graph engine is inspired by <a href=\"https://github.com/egraphs-good/egglog\" rel=\"nofollow ugc noopener\">egglog</a>, a popular tool that reduces e-graph operations to the <a href=\"https://en.wikipedia.org/wiki/Datalog\" rel=\"nofollow ugc noopener\">Datalog</a> database query language. Dustin reimplemented the core of egglog inside the logic of <a href=\"https://en.wikipedia.org/wiki/Rocq\" rel=\"nofollow ugc noopener\">the Rocq Prover</a>. That is, this implementation is a <a href=\"https://en.wikipedia.org/wiki/Purely_functional_programming\" rel=\"nofollow ugc noopener\">purely functional</a> program in the native language that Rocq likes to reason about, which raised some new implementation challenges that were different from those that showed up in egglog’s original implementation in an <a href=\"https://en.wikipedia.org/wiki/Imperative_programming\" rel=\"nofollow ugc noopener\">imperative</a> language. Thanks to using Rocq’s native language, Dustin was able to prove soundness of the engine without dealing with vagaries of any popular imperative language that could have been used instead to implement the engine. There are also engine features specific to Pyrosome and how to encode its proof obligations as egglog-style queries; these features are proved, too.</p>\n<p>The end result is a function inside Rocq that takes in the code of a language-feature module and delivers a verdict on its correctness: either “proved correct” or “failed to prove correctness.” This function is itself proved correct, so no further human effort is needed in applying it within a Rocq development. This design choice contrasts with the other common one of having such an engine output a proof justifying its conclusion for any individual run, which imposes a continuing performance cost for generation of proofs.</p>\n<p>Now, sometimes verification fails, whether because of an actual compiler bug or because of an incompleteness in the e-graph engine. Such incompleteness is inevitable, because exploring all possible rewrite sequences from some starting point can generate too many term variants to store, even using a clever data structure with sharing, so a numeric cutoff on number of rounds of search is typically employed. It is important to give useful feedback to the programmer when verification fails. We want to explain to the programmer which equality couldn’t be established, in the simplest possible terms. Partly to that end, this new engine includes an <em>extraction</em> feature of the kind we discussed last time, to produce the <em>shortest</em> term found so far to represent some value.</p>\n<p>The last post sketched an extraction approach that works on e-graphs structured as trees. Following egg, our new engine can handle extraction from general e-graphs, with a somewhat-flexible notion of <em>additive</em> cost functions, which give the metrics we optimize in finding best encodings of values. The trick is to plan ahead: all nodes of e-graphs are always annotated with their values according to chosen cost functions, and any e-graph modification requires fixing up these values. Then a simple linear-time graph traversal can extract the lowest-cost representation for any node (though that representation may be represented as a graph with sharing, so that naive printing as a tree takes more than linear time).</p>\n<p><a href=\"https://substackcdn.com/image/fetch/$s_!unq7!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fdfd4a574-0d9b-4516-be10-96787b7bac23_1536x1024.png\" rel=\"nofollow ugc noopener\"><img src=\"https://substackcdn.com/image/fetch/$s_!unq7!,w_1456,c_limit,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fdfd4a574-0d9b-4516-be10-96787b7bac23_1536x1024.png\" alt=\"\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></a></p>\n<p>The evaluation from our paper shows that this engine automates proof of every obligation associated with the compiler inspired by “From System F to Typed Assembly Language,” when we restrict to avoid <a href=\"https://en.wikipedia.org/wiki/Parametric_polymorphism\" rel=\"nofollow ugc noopener\">polymorphism</a> in the source language. We have a few other case studies (including adding in that polymorphism) that generate a handful of lingering obligations with manual proofs (about 5 out of about 200 obligations across all the case studies). The full implementation includes using the e-graph for <a href=\"https://en.wikipedia.org/wiki/Type_inference\" rel=\"nofollow ugc noopener\">type inference</a> as well, which is applied to fill in missing type annotations within rules written in convenient surface syntax.</p>\n<h1 id=\"conclusion\">Conclusion</h1>\n<p>This new functionality allows rapid experimentation with new programming-language features and their compiler code, since we have an oracle that checks correctness automatically. We can imagine AI coding agents appealing to that check via tool calls, delivering formally verified compilers after experimenting for a while with language and compiler design. The catch is that the check is implemented as a sequential functional program, and it can effectively time out or run out of memory on goals that only seem moderately complex. We would really rather have something more like the traditional low-level, performance-optimized implementations of Datalog, but still formally verified. The more parallel the implementation, the better, most likely. I’ll be returning in later articles to this theme, along with more detail of how a Datalog implementation works and how to reduce to Datalog various queries in theorem proving and program optimization.</p>\n<p>There is one more example I want to give of gradually deriving a correct program with logically sound steps, this time for fairly open-ended C programming. Before I go there two weeks from now, I’ll use next week to weigh in on the increasing use of AI agents to enforce correctness on other AI agents, the inherent trust weaknesses of that style, and how deterministic approaches like formal methods can come to the rescue, demonstrated with a new benchmark suite from my startup <a href=\"https://nectry.com/\" rel=\"nofollow ugc noopener\">Nectry</a>.</p>","headings":[{"level":1,"text":"What Kind of Compilers?","id":"what-kind-of-compilers"},{"level":1,"text":"Languages and Compilers, Modularly","id":"languages-and-compilers-modularly"},{"level":1,"text":"Using E-Graphs to Automate Proof of Compiler Correctness Obligations","id":"using-e-graphs-to-automate-proof-of-compiler-correctness-obligat"},{"level":1,"text":"Conclusion","id":"conclusion"}]}}