anon_zene said in #3095 3w ago:
https://www.cole-k.com/2023/07/24/e-graphs-primer/
About 10 years ago I was very interested in term rewriting as a basis for exotic programming languages and even AI. One of the big problems in term rewriting is that without a canonical deterministic ordering, you rapidly end up with an uncontrollable number of possibilities. You need ways to compress down the redundancy in some way. This e-graph ("equivalence-graph") technique is a good way to do at least part of that.
One thing this reminds me of is the interaction combinator system that supposedly gets optimal evaluation of lambda terms using heavy duty term sharing. (The LC is after all a term rewriting system). That guy Victor Taelin in twitter is working on GPU-accelerating these rewrite systems as an AI technique with his Higher Order Computing Company stuff (Bend, etc). Another thing it reminds me of is a paper I read many years ago about something like "complete laziness" or "total laziness" as a technique for evaluating lambda terms that had very interesting properties like crushing the time penalty of a tower of interpreters down to a constant offset: O(n) in the height of the tower, but O(1) in runtime (!!!). There's some very cool stuff in this area and some day it's going to lead to a big breakthrough paradigm.
About 10 years ago I was very interested in term rewriting as a basis for exotic programming languages and even AI. One of the big problems in term rewriting is that without a canonical deterministic ordering, you rapidly end up with an uncontrollable number of possibilities. You need ways to compress down the redundancy in some way. This e-graph ("equivalence-graph") technique is a good way to do at least part of that.
One thing this reminds me of is the interaction combinator system that supposedly gets optimal evaluation of lambda terms using heavy duty term sharing. (The LC is after all a term rewriting system). That guy Victor Taelin in twitter is working on GPU-accelerating these rewrite systems as an AI technique with his Higher Order Computing Company stuff (Bend, etc). Another thing it reminds me of is a paper I read many years ago about something like "complete laziness" or "total laziness" as a technique for evaluating lambda terms that had very interesting properties like crushing the time penalty of a tower of interpreters down to a constant offset: O(n) in the height of the tower, but O(1) in runtime (!!!). There's some very cool stuff in this area and some day it's going to lead to a big breakthrough paradigm.
About 10 years ago I