Lambda MicroEgg
philipzucker.com
philipzucker.com
Incidentally, I recently vibe coded an e-graph library in Clojure and a CAS system on top of it. I am not very familiar with the theory and my background on symbolic algebra systems was mostly coming from SICP. My motivation was just to play with ideas and "see some things actually happen" also. My library doesn't have any binding support but does do some of the semiring completion stuff mentioned in the post.
It was cool to see the numbers for the AC-10 benchmark match exactly. My lib is much slower, so this is motivating me to optimize it a bit. Anyway, I appreciate the post as well as the down to earth writing style.
Many applications are naturally expressed using bound variables (lambdas, summation expressions, einstein indices, integrals, loops) but the basic e-graph doesn't really support the concept. One can instead model using combinators (SKI combinators, relation algebra, categorical combinators, other) but this tends to be not entirely natural and tends to explodes in the search space of different ways to encode the same concept using combinators.
Lifting e-graphs are a variant of sorts of slotted e-graphs, which are techniques to supports binders in egraphs. It's more subtle to do so than one might think. Lambda microegg also adds a surface syntax to play around more easily.
At which point it felt like having jumped into the deep sea, at night, and sharks are all around. I have no formal education in CS, and a lot of this stuff is way above my pay grade. Though it made me wonder why none of this stuff has hit mainstream; modern compilers are still very crude, it seems like such an obvious idea to model compilation as transformation of one graph into another. Is this just fringe academic research that hasn’t yet trickled down to the masses of us code monkeys?
I still have a soft-spot for this niche of computer science, but I need to find 5 years and 20 IQ points to understand how it all fits together.
Basically all optimizing compilers have a simplifier or rewriter in them. I don't see it as a requirement or even necessarily a priori desirable to frame their discussion or formulation in terms of high barrier mathematical language. Do so if it is fun or useful. Sometimes it is. It is to my subjective taste to do so. Compiler writers are a pretty clever group by and large and are aware of a decent amount of useful math.
There is also a tendency to underestimate where 10 years of study and effort applied to a subject can bring you and attribute it totally to some intrinsic intelligence.
Term rewriting _is_ really neat. Realizing and remembering what you find neat and exciting is important. I like equations.