This article is crossposted between Prof. Adam Chlipala’s blog Structure and Guarantees and the blog of CSAIL, 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, which I argue is an important alternative to the ways AI coding agents are being used widely today. Previous examples have included tensor programs, digital hardware, and low-level cryptographic software. The last article 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.