I’ve somehow not heard of e-graphs, interesting! The end of the POPL 2021 presentation mentioned projects using egg that involved “Java testing” and “educational problems”, does anyone know what these are?
Author here: those projects are a little old, I should update the list. The java testing was a course project and the education problems was a project that I don’t think went anywhere ultimately (I was not involved in either directly).
Is anybody using this to implement the optimizer for a more-or-less general purpose programming language? (Instead of the standard approach of multiple different passes that must be ordered by hand.)
Cammy has trivial alpha- and eta-equivalence, and no lambda-abstractions. In fact, my jelly optimizer doesn’t know whether an atom refers to a builtin function or a composite. This was essential to getting equational reasoning which doesn’t need to manage scopes or shadowing. Also, Cammy is total and pure, so optimizations don’t have to speculate or otherwise be conditional on a context. Finally, Cammy’s textual syntax is a flavor of S-expressions which is parseable by Scheme, OCaml, and egg’s builtin SymbolLang, so I did not have to write a new AST type in Rust.
I’ve somehow not heard of e-graphs, interesting! The end of the POPL 2021 presentation mentioned projects using egg that involved “Java testing” and “educational problems”, does anyone know what these are?
Author here: those projects are a little old, I should update the list. The java testing was a course project and the education problems was a project that I don’t think went anywhere ultimately (I was not involved in either directly).
Is anybody using this to implement the optimizer for a more-or-less general purpose programming language? (Instead of the standard approach of multiple different passes that must be ordered by hand.)
The cranelift folks are exploring using an e-graph (based on egg) in their compiler: https://github.com/bytecodealliance/rfcs/pull/27
Thanks for that reference. I’m looking forward to finding out how well this works in practice, for both code simplicity, and for performance.
I hadn’t seen that; very exciting!
I use egg in my implementation of Cammy. It is a short single-file optimizer with little magic.
The library and approach are fine, but the language needs to be intentionally designed for it.
Thanks, I’ll take a look. In what sense does the language need to be intentionally designed for it?
Cammy has trivial alpha- and eta-equivalence, and no lambda-abstractions. In fact, my jelly optimizer doesn’t know whether an atom refers to a builtin function or a composite. This was essential to getting equational reasoning which doesn’t need to manage scopes or shadowing. Also, Cammy is total and pure, so optimizations don’t have to speculate or otherwise be conditional on a context. Finally, Cammy’s textual syntax is a flavor of S-expressions which is parseable by Scheme, OCaml, and egg’s builtin
SymbolLang, so I did not have to write a new AST type in Rust.