3 ms·

Unmentioned in the article is the fact that the Rete algorithm, due to how it breaks down and deduplicates predicates, has O(1) scaling behavior respective to t

Unmentioned in the article is the fact that the Rete algorithm, due to how it breaks down and deduplicates predicates, has O(1) scaling behavior respective to the number of rules in the system, with the trade off of needing sufficient memory for the objects to be matched and the predicate network. It is completely fascinating to me that a rule system with one million rules could execute in the same time as one with a single rule. I've become mildly obsessed with the potential applications of that behavior, and one of my favorite ideas (of which I'm mostly unqualified to implement) is a compiler super-optimizer, storing the rewriting rules as individual rules in the rule engine. This would also allow for adding interesting optimizations that might be purposefully omitted from existing optimizing compilers due to their infrequent or expensive matching. It would also allow for optimizations anywhere in the compiler pipeline without having to worry much about modularity, which could open up the possibility of macro-level optimizations at the AST level (for example, rewriting an array of objects as an object of arrays to speed up folds and maps over the array), or the machine code level (taking advantage of small differences in instruction sets and other on-die resources). That being said, I'm pretty sure the existing Rete implementations are poorly suited to matching on subtrees as would probably be required for this type of optimization, and the memory requirements would mean compilation would likely need to be done on servers. Tradeoffs aplenty, but I would still love to see it happen.

hendler 11y ago
RETE is often used as the inference engine for RDF/OWL/SPARQL servers. (I believe Sesame/SAIL was one of the first in early 2000s using Jena [1]) Since there are many graph databases now, some have added RDF/OWL and inference support. [1] - https://jena.apache.org/documentation/inference/ https://jena.apache.org/documentation/inference/ Related https://en.wikipedia.org/wiki/Semantic_reasoner https://en.wikipedia.org/wiki/Semantic_reasoner Some more background http://www.stat.ucla.edu/~tukw/waim05.pdf http://www.stat.ucla.edu/~tukw/waim05.pdf
abecedarius 11y ago
You can find a matching subtree in time independent of the number of patterns using essentially the same idea as the Aho-Corasick method of string pattern matching. This is done in term rewriting systems -- e.g. I just looked up the Pure term-rewriting language and this code appears to work that way (just going by the comment): https://bitbucket.org/purelang/pure-lang/src/b7486ed110e5c509cd329b335a83ff74ca77d750/pure/matcher.hh?at=default&fileviewer=file-view-default#matcher.hh-147 https://bitbucket.org/purelang/pure-lang/src/b7486ed110e5c50... You could try out your idea by expressing your optimizer rules as a program in Pure. I don't know if after a rewrite they rescan the tree from the root, or try to get smarter and restart the matcher automaton from a point only just far enough up the tree (and back in the matcher) to allow for any change from the rewrite. It might be interesting to apply Rete directly to the tree represented as a set of tuples, for instance (define (double x) (* 2 x)) as (root G0) (branch G0 define G1 G2) (branch G1 double x) (branch G2 * 2 x) and now a rewrite like (* 2 N) => (+ N N) would go (rule (branch ?name * 2 ?node) => (branch ?name + ?node ?node)) I'd be surprised if this worked out better in general, but maybe there are some interesting cases. BTW the GHC compiler for Haskell lets library authors define optimizations by rewrite rules -- like your array of records to record of arrays, I guess.
pge 11y ago
I did some work with Charles Forgy, and if I remember correctly, the challenge with RETE was that it scaled very well with a large number of rules (as you note), but it scaled very poorly with the size of the data set against which those rules were applied. He subsequently developed versions of RETE that addressed some of the weaknesses in the original algorithm, but the subsequent versions were not released in the public domain. For example, RETE3 (early 2000s) is now owned by Fair, Isaac.

hendler 11y ago

RETE is often used as the inference engine for RDF/OWL/SPARQL servers. (I believe Sesame/SAIL was one of the first in early 2000s using Jena [1]) Since there are many graph databases now, some have added RDF/OWL and inference support. [1] - https://jena.apache.org/documentation/inference/ https://jena.apache.org/documentation/inference/ Related https://en.wikipedia.org/wiki/Semantic_reasoner https://en.wikipedia.org/wiki/Semantic_reasoner Some more background http://www.stat.ucla.edu/~tukw/waim05.pdf http://www.stat.ucla.edu/~tukw/waim05.pdf

abecedarius 11y ago

You can find a matching subtree in time independent of the number of patterns using essentially the same idea as the Aho-Corasick method of string pattern matching. This is done in term rewriting systems -- e.g. I just looked up the Pure term-rewriting language and this code appears to work that way (just going by the comment): https://bitbucket.org/purelang/pure-lang/src/b7486ed110e5c509cd329b335a83ff74ca77d750/pure/matcher.hh?at=default&fileviewer=file-view-default#matcher.hh-147 https://bitbucket.org/purelang/pure-lang/src/b7486ed110e5c50... You could try out your idea by expressing your optimizer rules as a program in Pure. I don't know if after a rewrite they rescan the tree from the root, or try to get smarter and restart the matcher automaton from a point only just far enough up the tree (and back in the matcher) to allow for any change from the rewrite. It might be interesting to apply Rete directly to the tree represented as a set of tuples, for instance (define (double x) (* 2 x)) as (root G0) (branch G0 define G1 G2) (branch G1 double x) (branch G2 * 2 x) and now a rewrite like (* 2 N) => (+ N N) would go (rule (branch ?name * 2 ?node) => (branch ?name + ?node ?node)) I'd be surprised if this worked out better in general, but maybe there are some interesting cases. BTW the GHC compiler for Haskell lets library authors define optimizations by rewrite rules -- like your array of records to record of arrays, I guess.

pge 11y ago

I did some work with Charles Forgy, and if I remember correctly, the challenge with RETE was that it scaled very well with a large number of rules (as you note), but it scaled very poorly with the size of the data set against which those rules were applied. He subsequently developed versions of RETE that addressed some of the weaknesses in the original algorithm, but the subsequent versions were not released in the public domain. For example, RETE3 (early 2000s) is now owned by Fair, Isaac.