4 ms·

This is the advancement of egg[0]. Egg (and the e-graph theory behind it) has recently been put into use in some databases (e.g. cube[1]) and compilers (e.g. c

This is the advancement of egg[0]. Egg (and the e-graph theory behind it) has recently been put into use in some databases (e.g. cube[1]) and compilers (e.g. cranelift[2]). It lends itself well to the use-case of optimizing query planers and compilers, as it at the core avoids the optimization pass ordering problem (where an earlier optimization pass may destroy information that could be useful for a later one). [0]: https://github.com/egraphs-good/egg https://github.com/egraphs-good/egg [1]: https://github.com/cube-js/cube https://github.com/cube-js/cube [2]: https://github.com/bytecodealliance/rfcs/blob/main/accepted/cranelift-egraph.md https://github.com/bytecodealliance/rfcs/blob/main/accepted/...

philzook 4y ago
A more direct link to a list of applications of egraphs is https://egraphs-good.github.io/ https://egraphs-good.github.io/ Largely optimizing rewrites in compilers/synthesizers/query optimizer and theorem proving applications. The egglog repo is here https://github.com/mwillsey/egg-smol https://github.com/mwillsey/egg-smol with a wasm compiled web demo with examples here https://www.mwillsey.com/egg-smol/ https://www.mwillsey.com/egg-smol/ It is still in pre-release, so there are no guarantees of stability and not necessarily ready for people to pile in. This system is related to ones Yihong Zhang and I gave separate talks on at last year EGRAPHS 2022 workshop https://effect.systems/doc/pldi-2022-egraphs/abstract.pdf https://effect.systems/doc/pldi-2022-egraphs/abstract.pdf http://www.philipzucker.com/egglog/ http://www.philipzucker.com/egglog/
- YeGoblynQueenne 4y ago
  Thanks both for all the links!
- thaliaarchi 4y ago
  How does egglog compare to bddbddb, a Datalog engine powered by BDDs? They use BDDs in Datalog to solve previously unsolved problems like context-sensitive pointer analysis for large programs and show that analyses implemented with it are faster than hand-tuned implementations and use dramatically fewer lines of code. https://people.csail.mit.edu/mcarbin/papers/aplas05.pdf https://people.csail.mit.edu/mcarbin/papers/aplas05.pdf
cfallin 4y ago
A small correction re: Cranelift -- I had originally prototyped with egg, but we're currently using a variant of egraphs I invented called "acyclic egraphs" after working through performance and productionization issues, with our own implementation. Egg is great for what it is; a production compiler is just a really particular and demanding environment. I'll be giving a talk about it at EGRAPHS 2023 (in the meantime there are details in the RFC you linked). E-graphs are cool! :-)
felixyz 4y ago
Related to equality-constrained tree automata[1], which (as far as I understand) can "pick" an implementation/realization out of a huge latent space of possibilities. [1]: https://www.jameskoppel.com/publication/ecta/ https://www.jameskoppel.com/publication/ecta/

philzook 4y ago

A more direct link to a list of applications of egraphs is https://egraphs-good.github.io/ https://egraphs-good.github.io/ Largely optimizing rewrites in compilers/synthesizers/query optimizer and theorem proving applications. The egglog repo is here https://github.com/mwillsey/egg-smol https://github.com/mwillsey/egg-smol with a wasm compiled web demo with examples here https://www.mwillsey.com/egg-smol/ https://www.mwillsey.com/egg-smol/ It is still in pre-release, so there are no guarantees of stability and not necessarily ready for people to pile in. This system is related to ones Yihong Zhang and I gave separate talks on at last year EGRAPHS 2022 workshop https://effect.systems/doc/pldi-2022-egraphs/abstract.pdf https://effect.systems/doc/pldi-2022-egraphs/abstract.pdf http://www.philipzucker.com/egglog/ http://www.philipzucker.com/egglog/

YeGoblynQueenne 4y ago
Thanks both for all the links!
thaliaarchi 4y ago
How does egglog compare to bddbddb, a Datalog engine powered by BDDs? They use BDDs in Datalog to solve previously unsolved problems like context-sensitive pointer analysis for large programs and show that analyses implemented with it are faster than hand-tuned implementations and use dramatically fewer lines of code. https://people.csail.mit.edu/mcarbin/papers/aplas05.pdf https://people.csail.mit.edu/mcarbin/papers/aplas05.pdf

cfallin 4y ago

A small correction re: Cranelift -- I had originally prototyped with egg, but we're currently using a variant of egraphs I invented called "acyclic egraphs" after working through performance and productionization issues, with our own implementation. Egg is great for what it is; a production compiler is just a really particular and demanding environment. I'll be giving a talk about it at EGRAPHS 2023 (in the meantime there are details in the RFC you linked). E-graphs are cool! :-)

felixyz 4y ago

Related to equality-constrained tree automata[1], which (as far as I understand) can "pick" an implementation/realization out of a huge latent space of possibilities. [1]: https://www.jameskoppel.com/publication/ecta/ https://www.jameskoppel.com/publication/ecta/