← back to research residency

🥚 (egg)

Mar 11 2025 Exploring e-graphs

ell's egg recipe:

step 1: do rewrite stuff

*(a +(b c))
original rewrite code

step 2: do egg stuff

Followed along with this awesome egg presentation and its associated paper to make my own egg in JS.
image source: egg: e-graphs good website

step 3: evaluate the egg

builtins
demo

I used parser combinators to create a lisp-y parser (with array and block literals), then did post processing on the lisp-y AST to add statements to the AST. I put the AST into an e-graph, saturated it, and then "evaluated" the e-graph (using a method similar to e-class analysis from the egg paper)

With time?

I may tune my egg implementation to be efficient enough to solve algebra problems at some point. Regardless, I will use rewriting based ideas going forward.