Another paper to read

Last week, I found Jeremy Wertheimer's master thesis from MIT; Derivation of an efficient rule system pattern matcher. It seems very interesting. He derives a Rete implementation using program transformations (in the programming language Refine which seems to be some Lisp dialect or other). Apparently he starts out with a small formal specification of Rete and applies transformations to it step by step in order to derive an efficient pattern matcher. Very cool.

2 kommentarer:

woolfel sa...

cool paper. A mathematical proof of RETE. the content seems familiar, but I can't remember if I've read it before :)

man I must be going senile early or my memory is going faster than i'm aging.

Johan Lindberg sa...

Who needs memory? As long as you remember how to get on the internet, you won't have to remember a thing ;-)

You know, I've been googling "rete algorithm" quite a lot this last year, but I only just found this thesis. And I found it via the comp.lang.scheme newsgroup of all places. Makes me wonder what else is out there and how much Google searches actually covers...

As for the approach of derivation, I think it sounds marvellous. I can't remember how many times I've read about trade-offs: this approach works best if the rule base is small, this works best if there's not many facts in working memory etc etc. Imagine to be able to customize the pattern matcher at run-time depending on, say, the size of the working memory or the number of rules or whatever else there is.

I don't know if that was the intent of his research but that's for sure what I'm hoping to read about.