Forgy (1982) -- Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem

The paper

C. L. Forgy, “Rete: A fast algorithm for the many pattern/many object pattern match problem,” Artificial Intelligence, vol. 19, no. 1, pp. 17–37, 1982.

doi:10.1016/0004-3702(82)90020-0

A summary of the paper and how gen uses it.

Paper Summary

Production system interpreters spend up to nine-tenths of their execution time on pattern matching: given a set of productions (If-Then rules) and a set of working memory elements (attribute-value objects), the interpreter must find every element that matches each production’s left-hand side (LHS) conditions. Naive approaches iterate over both the production set and the working memory on every cycle. Forgy observes that between any two successive cycles, working memory changes only slightly — typically one or a few elements are added, modified, or removed. The Rete Match Algorithm exploits this temporal redundancy to avoid both iterations entirely.

The algorithm has two key strategies. First, it avoids iterating over working memory by maintaining persistent state: each pattern stores a list of the elements that currently match it, updating these lists incrementally as elements enter or leave working memory. The pattern matcher becomes a stateful black box that receives tokens (tagged descriptions of working memory changes: + for additions, - for deletions) and outputs changes to the conflict set (the set of all satisfied production instantiations). Second, it avoids iterating over the production set by compiling all LHS patterns into a single discrimination network — a tree-structured sorting index. Tokens enter at the root and flow through the network; only the patterns they actually match are ever reached.

The Rete network contains several node types. One-input nodes test intra-element features: properties of a single working memory element, such as whether its class is Expression or its operator attribute equals *. These nodes form linear sequences, one per pattern, filtering tokens against constant tests and intra-element variable consistency (two occurrences of a variable within one pattern must bind the same value). Two-input nodes (also called join nodes) test inter-element features: constraints arising from variables shared across multiple patterns, such as requiring the Object attribute of a Goal element to equal the Name attribute of an Expression element. Each two-input node has left and right memories storing tokens that arrived from each input path. When a new token arrives on one side, the node compares it against all stored tokens on the opposite side, outputting combined tokens for consistent bindings. Terminal nodes sit at the bottom and signal that a production’s LHS is fully satisfied, adding or removing instantiations from the conflict set.

A critical optimization is structural sharing: when two or more productions require identical tests, the compiler generates those nodes only once, routing both paths through the shared sub-network. In Forgy’s running example, the productions PlusOx and TimeOx share the entire Goal pattern test sequence and differ only in the operator test on the Expression pattern. This sharing extends naturally across large production sets, because many rules test similar features (same element classes, same attribute constraints). The shared prefix structure gives the network its tree (or more precisely, DAG) topology and is the primary source of the algorithm’s efficiency.

For negated patterns (conditions preceded by -), a second kind of two-input node maintains a count with each left-memory token indicating how many right-memory tokens allow consistent bindings. Tokens pass only when their count is zero — meaning no working memory element satisfies the negated condition.

The paper describes a concrete implementation in a PASCAL-like language, linearizing the network into a sequence of instructions analogous to von Neumann machine code. Seven node types (FORK, MERGE, TEQA, TEQS, AND, NAND, TERM) are encoded in 32-bit words. Tokens are represented on a stack, and a depth-first interpreter traverses the network using a separate state stack for backtracking through FORKs and suspending two-input nodes. The instruction sequences are short enough to be microcoded.

The analytical complexity results (Table 1) establish sharp bounds. Space: the number of tokens is O(1) in working memory size in the best case, O(W^C) in the worst case (W = working memory size, C = patterns per production). The number of nodes is O(P) in production memory size (P = number of productions). Time per firing: O(1) in working memory size best case, O(W^(C-1)) worst case; O(log2 P) in production memory size best case (from the tree indexing), O(P) worst case. All bounds are shown to be sharp — pathological production systems achieving each bound exist. Forgy notes three preconditions for the algorithm’s applicability: patterns must be compilable into feature tests, objects must be constant (no variables), and the object set must change slowly between cycles.

Key Concepts

• Incremental match via state preservation. The Rete network stores partial match results between cycles rather than recomputing from scratch. Each two-input node maintains left and right memories holding all tokens that have arrived from each input. When working memory changes, only the delta is processed — new tokens flow through the network, and only the nodes they reach are activated. This transforms the match cost from proportional to total working memory size to proportional to the size of the change.

• Compiled discrimination network. Patterns are compiled into a tree-structured network of simple feature-testing nodes, eliminating the need to iterate over productions. The compiler examines each LHS, determines its required intra-element and inter-element features, and builds a node chain for each. The network functions as a precomputed index: a token entering at the root is sorted to exactly the terminal nodes whose patterns it satisfies.

• Structural sharing across productions. When multiple productions require identical tests, the compiler generates those nodes once and shares them. This is the algorithm’s most distinctive feature: the network size grows as O(P) in the number of productions, not as the sum of all pattern lengths, because common prefixes are merged. Sharing also reduces runtime work — a test evaluated once for a shared prefix need not be repeated for each production that uses it.

• Two-phase feature testing. Features are divided into intra-element (properties of one element: class, attribute values, intra-element variable equality) and inter-element (cross-element variable bindings). One-input nodes handle intra-element tests; two-input join nodes handle inter-element tests. This decomposition keeps individual nodes simple and allows the intra-element tests to filter heavily before the more expensive joins.

• Token-based delta propagation. All communication in the network uses tokens: tagged pairs of a +/- tag and a list of working memory elements. The tag propagates through joins and terminal nodes, determining whether to add or remove from memories and the conflict set. Modification of an element is modeled as deletion of the old form followed by addition of the new form.

• Negated patterns via counted joins. The NAND node variant maintains a count per left-memory token. The count tracks how many right-memory tokens allow consistent bindings. Only zero-count tokens pass — no matching element exists for the negated condition. This is an efficient implementation of universal quantification over the absence of a match.

• Sharp complexity bounds. The algorithm’s worst-case time per firing is O(W^(C-1)) in working memory size and O(P) in production memory size, but the best case is O(1) and O(log2 P) respectively. The tree indexing gives logarithmic best-case production memory cost. All bounds are proven sharp, meaning pathological systems achieve them.

How gen uses this

gen-dispatch

gen-dispatch is a production rule system on the Rete paper’s condition-action model. Forgy’s productions are gen-dispatch rules, an LHS is a rule’s condition, an RHS is its produce function, and the conflict set becomes the grouped actions dispatch returns.

Condition-action rules (S1, S2). A Rete production is (LHS, RHS), where the LHS is a conjunction of patterns and the RHS a sequence of actions. mkRule { ... } condition produce is the analogue: condition is tested by the caller’s match function, and produce id ctx returns a list of tagged actions whose meaning belongs to the consumer. dispatch performs one recognize-act cycle (S1: match, conflict resolution, act). It tests every rule’s condition against the context, resolves conflicts, fires the surviving rules and returns their actions grouped.

Conflict resolution (S1, step 2). Forgy’s interpreter selects one instantiation from the conflict set and leaves the selection strategy to the language (S4, the TERM node’s UPDATECONFLICTSET). gen-dispatch resolves in three steps: a rule’s overrides list suppresses named rules, rules are sorted by numeric priority with declaration order breaking ties, and the optional exclusive mode keeps only the highest-priority rules.

Negated patterns (S2.3). Rete’s NAND nodes implement patterns that must not be satisfied. A gen-dispatch rule’s nac field is the analogue: a candidate rule survives only when its NAC does not match and its condition does.

Compiled pattern tests (S2.2.1). fromFunction builds a rule whose condition is the set of formal arguments of a Nix function, read with builtins.functionArgs. fromFunctionMatch tests that the context supplies every required argument. These are Rete’s intra-element feature tests. Each rule’s test runs on its own, with no network shared between rules.

The outer loop is the caller’s. dispatch is a pure function of rules and context, and keeps no record of which rules fired on earlier passes. Forgy’s outer cycle (S1 step 4, “Goto 1”) is run by the caller, which threads domain state through repeated dispatch, for example with gen-scope’s circular, and reads the actions at the fixed point. Because actions are recomputed from the converged state, they depend on that state and not on the order in which it was reached.

Summary of the correspondence:

• mkRule is a Rete production (S1: LHS and RHS).
• condition is the LHS patterns (S1; S2.2.1 intra- and inter-element features).
• produce is the RHS actions (S1: MAKE, MODIFY, REMOVE).
• nac is a negated pattern, the NAND node (S2.3).
• dispatch is one recognize-act cycle (S1 steps 1-3).
• fromFunction and fromFunctionMatch are compiled pattern tests (S2.2.1).
• mkActions and the caller’s classify manage the conflict set’s instantiations as tagged values (S2).
• Overrides, priority and exclusive generalise Forgy’s conflict resolution step (S1 step 2).

gen-memo

gen-memo uses Rete’s token vocabulary for changes. applyDelta records an input change, which is Forgy’s + token (in Acar’s terms the change δ ⊕ σ), and applyEdgeDelta replaces a node’s edge set as modify = delete + add (S2.1.1). The rebuild that follows is Acar’s change propagation, and the token vocabulary is Forgy’s.

Rules over a configuration graph

In a framework built on gen, entity context (host kind, user presence, platform) is the working memory, rules are the productions, and their actions change the configuration graph. A rule written as ({ host, ... }: [ ... ]) is a Forgy production: the argument pattern { host, ... } is the LHS and the returned action list is the RHS. fromFunction turns it into a gen-dispatch rule. Rules that create entities widen the context, which lets further rules match, which is Forgy’s recognize-act cycle with working memory growing between cycles.

Appendix: Follow-up Work

Unexploited Ideas

• A compiled discrimination network (S2.2.1, S3.2, Fig. 2). Forgy’s compiler builds a tree of one-input nodes with shared prefixes and linearises it into instructions with FORK and MERGE nodes. gen-dispatch tests each rule’s condition separately through match. A discrimination tree over builtins.functionArgs signatures would test common context keys once along shared paths. With hundreds of rules sharing key patterns this could measurably reduce dispatch cost.

• Two-input join memories (S2.2.3). Rete’s two-input nodes keep partial matches between cycles and join each arriving token against the stored tokens on the other side. gen-dispatch keeps no state between calls. When the caller dispatches repeatedly across many scope-graph positions, caching partial match results could avoid repeated condition tests.

• Linearised network representation (S3.2, S4). Forgy converts the network DAG into a flat instruction stream interpreted with a state stack. gen-dispatch is structured as function calls. For very large rule sets, where Nix function-call overhead dominates, a linearised form could help.

• Incremental re-matching with paired tokens (S2.1.1). A modification in Rete sends a - token for the old value and a + token for the new one. Each dispatch call tests every candidate rule. A paired-token model would re-test only the rules a context change affects.

Potential New Libraries or Features

• A compiled condition network. Compile a rule set whose conditions come from builtins.functionArgs into a discrimination DAG (S2.2.1), with shared prefix nodes testing common context keys once, and return a dispatch that walks the network instead of iterating over rules. Useful where many rules overlap in the keys they test.

• Partial match caching across repeated dispatch. Cache condition results between calls, and re-test only the rules whose conditions read keys that changed. The keys each fromFunction rule reads are already known from builtins.functionArgs.

• Delta-driven re-matching. Have each widening of the context report its changed keys, and re-test only the rules whose conditions reference them. That narrows each round from O(rules) to O(affected rules), and needs fromFunctionMatch to expose the keys it depends on.

Research Directions

• Sharing in real rule sets. Given a real framework’s rule set, measure the sharing factor of the compiled discrimination network. If most rules share { host, ... } or { host, user, ... } prefixes, the factor is high and a compiled network gives a large constant-factor gain.

• Lazy Rete. Rete propagates every token eagerly. In Nix, evaluation is demand-driven, and a lazy variant could activate nodes only when a downstream consumer demands a result, combining Rete’s incremental state with gen-scope’s demand-driven evaluation.

• Rete-like dependencies between attributes. gen-scope memoises computed attributes on each node’s _eval without recording which attributes a computation read. A Rete-style dependency network between attributes would allow recomputing only the attributes whose inputs changed when the scope graph’s structure changes. gen-memo provides this decision for a caller-supplied dependency accessor, following Mokhov 2018’s build-system traces.