Incremental forward-chaining match — a TREAT-style alpha network.
The reference forward chainer (vaelii.impl.chain) is semi-naive: a new fact seeds
the agenda, candidate rules are found by the rule index, and each candidate's
non-trigger antecedents are re-joined against the store on every assert. That
re-join goes through res/match-pattern, which walks the count-aware trie —
and the trie narrows strictly left to right, so a non-trigger antecedent with a
leading variable ((parentOf ?x Pi), the second half of a grandparent join)
can only be answered by scanning the whole parentOf extent. That scan is O(N)
in the fact count, once per assert — the grandparent chain measured
6.4ms/assert at n=200 and 10.3ms/assert at n=400, a textbook quadratic load.
This namespace keeps alpha memories in RAM — the stored facts grouped by
functor and indexed by argument value — and answers a non-trigger antecedent with
a hash lookup on its most selective ground argument instead of a scan. A leading
variable no longer forces a full extent walk: (parentOf ?x Pi) reads the bucket
of facts with Pi in position 2 directly.
The one and only novelty here is which stored facts a non-trigger antecedent
finds. Everything else — the semi-naive agenda, the trigger match (match1),
context placement, exceptWhen blocking, the definitional checks on the derivation
path, justification dedup, functional-equality twins, the depth guard — is the
reference's, reached by binding one seam (chain/*matcher*) and calling
chain/chain-all unchanged. So the network cannot diverge in any of those; it
can only diverge in the match, and rete-match-pattern is written to return the
identical set res/match-pattern returns — same belief filter, same
polarity check, same symmetric mirror, same subtype fan-out, same ?ctx binding —
differing only in the candidate source (a RAM bucket, a superset of the trie hits,
filtered by the identical unify). rete_oracle_test pins that equality directly
(per pattern) and end to end (the derived sentex + justification sets over randomized
assert/retract sequences must match the reference chain).
A per-KB atom, {:by-functor {f {:all {id sentex} :by-arg {[pos val] {id sentex}}}}}. Only ground
facts live here (rules are matched by the rule index, not as facts, and never
appear among a fact pattern's trie hits). Belief is not baked in: a datum stays
in its memory when it is defeated or superseded, and in? is consulted at read
time exactly as match-one does — so a belief flip needs no memory update, and the
only structural mutations are a stored fact arriving (kb/create-sentex) or leaving
(integrate/sentex-removed!), routed here through vaelii.impl.observe. Subtype
and symmetric resolution also happen at read time (over the live taxonomy), so a
genl or symmetric edge change needs no memory update either.
See docs/inference.md, "Incremental rule matching".
Incremental forward-chaining match — a TREAT-style alpha network.
The reference forward chainer (`vaelii.impl.chain`) is semi-naive: a new fact seeds
the agenda, candidate rules are found by the rule index, and each candidate's
non-trigger antecedents are re-joined against the store on every assert. That
re-join goes through `res/match-pattern`, which walks the **count-aware trie** —
and the trie narrows strictly left to right, so a non-trigger antecedent with a
*leading variable* (`(parentOf ?x Pi)`, the second half of a grandparent join)
can only be answered by scanning the whole `parentOf` extent. That scan is O(N)
in the fact count, once per assert — the grandparent chain measured
6.4ms/assert at n=200 and 10.3ms/assert at n=400, a textbook quadratic load.
This namespace keeps **alpha memories** in RAM — the stored facts grouped by
functor and indexed by argument value — and answers a non-trigger antecedent with
a hash lookup on its most selective ground argument instead of a scan. A leading
variable no longer forces a full extent walk: `(parentOf ?x Pi)` reads the bucket
of facts with `Pi` in position 2 directly.
## Correctness by reuse, not by reimplementation
The one and only novelty here is *which stored facts a non-trigger antecedent
finds*. Everything else — the semi-naive agenda, the trigger match (`match1`),
context placement, `exceptWhen` blocking, the definitional checks on the derivation
path, justification dedup, functional-equality twins, the depth guard — is the
reference's, reached by binding one seam (`chain/*matcher*`) and calling
`chain/chain-all` unchanged. So the network cannot diverge in *any* of those; it
can only diverge in the match, and `rete-match-pattern` is written to return the
**identical set** `res/match-pattern` returns — same belief filter, same
polarity check, same symmetric mirror, same subtype fan-out, same `?ctx` binding —
differing only in the candidate source (a RAM bucket, a superset of the trie hits,
filtered by the identical `unify`). `rete_oracle_test` pins that equality directly
(per pattern) and end to end (the derived sentex + justification sets over randomized
assert/retract sequences must match the reference `chain`).
## The alpha memories
A per-KB atom, `{:by-functor {f {:all {id sentex}
:by-arg {[pos val] {id sentex}}}}}`. Only ground
**facts** live here (rules are matched by the rule index, not as facts, and never
appear among a fact pattern's trie hits). Belief is *not* baked in: a datum stays
in its memory when it is defeated or superseded, and `in?` is consulted at read
time exactly as `match-one` does — so a belief flip needs no memory update, and the
only structural mutations are a stored fact arriving (`kb/create-sentex`) or leaving
(`integrate/sentex-removed!`), routed here through `vaelii.impl.observe`. Subtype
and symmetric resolution also happen at read time (over the live taxonomy), so a
`genl` or `symmetric` edge change needs no memory update either.
See docs/inference.md, "Incremental rule matching".(chain kb seed opts)Run chain/chain (the settle-time re-chain seed) with the incremental matcher.
Run `chain/chain` (the settle-time re-chain seed) with the incremental matcher.
(chain-all kb seed opts)Run chain/chain-all with the incremental matcher. Engages the observers and
materializes this KB's alpha first, so a fact created during the run (a derived
conclusion) is in the memories before a later join reads it.
Run `chain/chain-all` with the incremental matcher. Engages the observers and materializes this KB's alpha first, so a fact created *during* the run (a derived conclusion) is in the memories before a later join reads it.
(disable!)Restore the reference trie matcher and drop the observers/alphas.
Restore the reference trie matcher and drop the observers/alphas.
(disengage!)Uninstall the observers and drop every alpha, so the store choke points do nothing
extra and the reference path is exactly as before. A no-op while the matcher is
the global default (enable!): a caller that merely track!ed one KB must not
tear the network out from under a globally-enabled engine.
The undo of engage!, and placed here rather than beside it because that no-op is the
whole of its contract: it reads enabled?, which reads the matcher defined above.
Uninstall the observers and drop every alpha, so the store choke points do nothing extra and the reference path is exactly as before. A **no-op while the matcher is the global default** (`enable!`): a caller that merely `track!`ed one KB must not tear the network out from under a globally-enabled engine. The undo of `engage!`, and placed here rather than beside it because that no-op is the whole of its contract: it reads `enabled?`, which reads the matcher defined above.
(enable!)Route all forward chaining through the incremental matcher by installing it as
chain/*matcher*'s root and engaging the observers. Off by default: the reference
matcher is the root, and this is the one switch that replaces it globally. The
oracle and the whole suite run through it (VAELII_RETE=1 lein test).
Route **all** forward chaining through the incremental matcher by installing it as `chain/*matcher*`'s root and engaging the observers. Off by default: the reference matcher is the root, and this is the one switch that replaces it globally. The oracle and the whole suite run through it (`VAELII_RETE=1 lein test`).
(enabled?)Is the incremental matcher currently installed as the global default?
Is the incremental matcher currently installed as the global default?
(engage!)Install the store observers so every alpha stays in step with the fact set.
Idempotent. Called by chain-all / chain before they run, and directly by the
oracle test.
Install the store observers so every alpha stays in step with the fact set. Idempotent. Called by `chain-all` / `chain` before they run, and directly by the oracle test.
(rete-match-pattern kb pattern context)The matcher chain/*matcher* is bound to when the network is engaged. Signature
and result are res/match-pattern's — (kb pattern context) -> ([handle bindings] …)
— answered from this KB's alpha memories.
The matcher `chain/*matcher*` is bound to when the network is engaged. Signature and result are `res/match-pattern`'s — `(kb pattern context) -> ([handle bindings] …)` — answered from this KB's alpha memories.
(track! kb)Engage the observers and materialize kb's alpha memories now, so every fact
kb already holds and every one it gains from here is in the memories. After
this, any operation on kb run under (binding [chain/*matcher* rete-match-pattern] …)
is matched incrementally. Exposed for tests and for a caller driving one KB
through the network without flipping the global default.
Engage the observers and materialize `kb`'s alpha memories now, so every fact `kb` already holds and every one it gains from here is in the memories. After this, any operation on `kb` run under `(binding [chain/*matcher* rete-match-pattern] …)` is matched incrementally. Exposed for tests and for a caller driving one KB through the network without flipping the global default.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |