ยง Good reference to the Rete pattern matching algorithm
The Rete pattern matching algorithm
is an algorithm that allows matching a huge number of rules with a huge database
of "facts".
MLIR ("multi-language intermediate representation") is a new technology that
hopes to centralize much of the research and development of various compilers
into a single authoritative source. The major claim-to-fame is that it allows
one to mix various "dialects" (much as Racket does). So, to a first order
approximation, MLIR is "JSON for compiler intermediate representations".
What MLIR gets right is tooling . They take the experience that the LLVM project
has mined for the last decade and a half, and bake many of the good stuff that
came with LLVM right in. For example, MLIR comes in-built with a pretty printer,
a notion of types, a notion of "attributes", SSA, enforced provenance
tracking of code (so one can always know what the original source code was
that led to some assembly). Sound engineering might see MLIR succeed where
many others failed.
I was reminded of Rete since the MLIR folks are trying to solve the pattern
matching problem in general for their Generic DAG Rewriter .
They currently just use a worklist based algorithm. I'm trying to understand
if Rete can be used instead. Rete is famous for being hard to understand,
so I began a quest to look for good sources to implement it. I found a great
PhD thesis written by Robert B. Doorenboos ,
which quips:
Since the Rete match algorithm provides the starting point for much of the work in this thesis, this chapter describes Rete. Unfortunately, most of the descriptions of Rete in the literature are not particularly lucid,1 which is perhaps why Rete has acquired \a reputation for extreme differentialculty."(Perlin, 1990b) To remedy this situation, this chapter describes Rete in a tutorial style, rather than just briey reviewing it and referring the reader to the literature for a full description. We will first give an overview of Rete, and then discuss the principle data structures and procedures commonly used to implement it. High-level pseudocode will be given for many of the structures and procedures, so that this chapter may serve as a guide to readers who want to implement rete (or some variant) in their own systems.
I now have a reference to an accessible description of this stuff. I might
implement Rete to understand it, so that it's part of my toolkit if I ever
need it.