Automatic Checking of Compiler Correctness with E-Graphs MIT CSAIL researchers, led by first author Dustin Jamner with undergraduate Tilek Askerbekov and Prof. Adam Chlipala, have developed an e-graph-based proof-automation tool that automatically verifies compiler correctness for previously unseen programming languages without extra theorem-proving annotations. The work, described as the first general tool of its kind, is set to appear at POPL 2027 and is detailed in Jamner's PhD dissertation. It targets compilers for functional languages built in the System F to Typed Assembly Language tradition, where each intermediate form is checked by a sound type system. 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. I’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. I’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. What Kind of Compilers? First 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. To avoid gratuitous dependencies on functional-programming lore, I’ll use an example program from Python