The engine

What runs the network network.md describes. The companion to ir.md (the DSL front end) and observability.md (listeners, inspection, the loop guard).

Status: implemented, end to end.

1. The one decision everything follows from

Clara propagates by mutating a transient memory while calling down the node tree, then converting back to a persistent memory at the end of fire-rules. That duality is why it needs an ITransport abstraction, four activation protocols, and seventeen listener methods sprinkled through every node.

This engine runs a flat propagation loop over an explicit work queue. A node is a function of state that returns the new state plus the work it produced, and the loop does the walking:

# lib/rete/engine/nodes.ex
handle(state, {op_kind, node_id, items}) :: {state, [op]}

Four consequences, all of which are load-bearing:

• no transport abstraction — it was indirection for a distributed transport that never shipped;
• one immutable Rete.Memory threaded through a fold, so a session is a value: holdable, comparable, forkable, sendable between processes with no coordination;
• propagation is flat iteration, so a cascade of any depth costs no stack;
• events are emitted in exactly one place — the loop — rather than in every node. That is what made the listener work in W5 cheap.

2. Two nested loops

insert / retract  ->  enqueue alpha ops  ->  drain
fire_rules        ->  drain, then: pop the most salient activation, run it,
                      insert what it returned, drain, repeat until the agenda is empty

Propagation is drained to completion before the next activation fires. A rule must see a settled network or it could act on a half-built match.

fire_rules/2 returns at quiescence: every rule whose left hand side holds has fired, and nothing is still asserting anything whose support has gone. That is the point at which a session is consistent, and it is the only state the public API ever hands back.

Ops

The last two are the work a node cannot carry out where it happens: retracting has to re-enter the alpha network, which only the engine can reach, and telling a listener is not a node's business.

3. What travels

Rete.Element — a fact that matched one condition, plus the bindings that match produced. Elements arrive from the right.

Rete.Token — a partial match: :matches, the [{fact, node_id}] behind it in order, and :bindings, the variables bound so far. Tokens arrive from the left.

Both are compared by value. Two tokens over equal facts with equal bindings are the same match whoever produced them, which is what makes retraction work when the term that triggered it is a different term of the same value. Match order is part of a token's identity: two tokens over the same facts in a different order are different matches.

Rete.Activation — a production node plus the token that satisfied it, plus the salience and compile order it will be sorted by.

4. The five memories

elements    node_id => join_key => [Element]           right side of a beta node
tokens      node_id => join_key => [Token]             left side of a beta node
accum       node_id => join_key => group_key => [fact] what a collection gathered
insertions  node_id => token => [[fact]]               truth maintenance
facts       fact => count                              what the session holds

Three properties matter more than the shapes.

Keyed by value, so removal must collapse. A join key and a group key hold the bindings they were built from. An entry left pointing at an empty leaf is not untidiness, it is a leak that grows with the number of distinct entities the session has ever seen — and Rete.Engine.Nodes depends on the collapse, because "no group" and "an empty group" are different answers and only a level that really is gone may disappear.

Multisets, not sets. facts counts. Inserting the same fact twice and retracting once must leave it present: two rules may each have concluded it, and one of them being invalidated does not make it false. elements and tokens are lists for the same reason, and are retracted one occurrence at a time.

insertions is the provenance graph. "This match at this production inserted these facts", which read backwards is exactly the edge Rete.Inspect.explain/2 walks. No separate bookkeeping exists for explanation; there is nothing to keep in sync.

root_seeded? is the one field that is not a memory — see §6.

5. Node behaviour

Every clause of Rete.Engine.Nodes has the same shape: take the state and the items, return the new state and the work produced.

The retraction rule

Every node must retract exactly what it propagated — the same value, not something equivalent, because downstream memories remove by value and a mismatch leaves a token stranded forever, which then fires a rule whose support is gone.

The discipline that makes it hold: a node never propagates from what it was handed, it propagates from what its memory says after the memory has been updated. Rete.Memory.remove_elements/4 and remove_tokens/4 report the occurrences they actually held, and only those are propagated onward. A retraction of something never stored produces no downstream work at all. This is the single contract no end-to-end property test can reach — every one of them still passes with the filtering removed — so it is tested directly against the memory.

A collection is one match, not many

An accumulate node emits the gathered list as a single binding. Change any member and the list is a different value, so it is a different token: the old one is retracted, the new one propagates, and truth maintenance replaces the conclusion. That is why a rule over a collection fires once per group rather than once per gathered fact.

Elements are kept in term order rather than appended on arrival, so the same fact set always produces the same list whatever order the facts arrived in, and a retract-and-reinsert round trip restores it exactly. That is an implementation guarantee — without it a rule that returns its collection would break order independence — and not a contract. See network.md §3.

6. The root token

Nothing binds before a rule's first condition, so a rule that opens with a negation, a collection or a test has no element to build its first token from. A RootJoin does not need one; a Negation hanging off the beta root has to pass something while nothing matches, and an Accumulate there has to emit its collection to someone.

Classic Rete answers with a single empty token seeded at the root, and so does this. It is planted at state creation, not on the first fact, because a rule whose whole left hand side is an absence or an empty collection is true of the empty session and must be able to fire before anything is inserted. Rete.Memory.root_seeded? makes it idempotent: a second root token would give every such rule a second support that no retraction ever clears.

It is machinery, not a match. Rete.Inspect never presents it as a fact.

7. Firing

Activations are ordered {salience, internal_salience} descending, then compile order ascending. Compile order — not map order — is what makes two rules of equal salience fire in the order they were written; a rules engine whose output depends on map iteration is impossible to reason about.

internal_salience is the tier that makes an extracted negation helper fire before the rule that negates its marker. Without it the negating rule observes an absence that had merely not been computed yet, fires, and is retracted — a visible spurious activation. It is reserved; a rule that sets it raises.

The agenda is bucketed by sort key, not a heap, because removal by value is the common operation rather than an afterthought: an activation is a pending match, and the facts behind it can be retracted before it fires. Rete.Agenda.remove/2 reports whether it found one, which is exactly the distinction a production needs on retraction — either the match never fired and simply never will, or it fired and its conclusions have to be taken back.

Every activation of one production shares a key — salience, internal salience and compile order all come from the node, none from the match — so there are at most as many buckets as there are production nodes, however many facts a session holds. One sorted list instead would walk past every match already queued for the same rule on each insertion.

Two matches of one rule

They fire in arrival order, and that runs deeper than the agenda. It holds because each of these is arrival ordered, in turn:

• a bucket hands its items back in the order they were pushed (Rete.Memory.Bucket);
• a batch of items arriving at a node is split into join groups in the order each key first appeared, not in map order — Enum.group_by/2 returns a map, and Elixir iterates one of up to 32 keys in term order and a larger one in an internal hash order, so taking that order would change a rule's firing sequence the moment a node saw its 33rd join key;
• the agenda appends within a bucket rather than inserting.

None of it changes what a session concludes — that is order independent, and the property suite says so. It decides the order :activation_fired events arrive in, which is what anyone reading a trace is relying on.

8. Truth maintenance

Facts a rule inserts are logical: they exist while the match that concluded them does. Each insertion is recorded against its token, and retracting that token retracts the facts, which may retract the support of other conclusions, cascading until it settles.

This is why the right hand side inserts and never retracts. A rule says what follows from a match; keeping that true as facts change is the engine's job. With no unconditional insert there is no way to leave a conclusion behind whose support is gone.

Support is well founded, not merely counted

A match that rests on the very fact it concludes would support that fact with itself: the count never reaches zero, so the fact survives the retraction of everything the user ever asserted and the memories behind it never drain.

defrule symmetric({:edge, a, b}), do: {:edge, b, a}

One {:edge, 1, 2} concludes {:edge, 2, 1}, which concludes {:edge, 1, 2} right back. So a conclusion the match already depends on is dropped: not inserted, not recorded, no count bumped. The check runs only when the fact is already present — the only way the loop can close — and walks the insertion records rather than the network.

The limit of deciding this at insertion time rather than by re-deriving on every retraction: the dropped support is not reconsidered later. If the grounded route to a fact goes away while the circular one would still have held, the fact goes with it.

9. Queries

A query terminal stores the tokens that reach it instead of activating. Rete.Engine.query/3 returns their :bindings, filtered by equality against the parameters given. Rete.Compiler rejects at build time a parameter the left hand side does not bind on every path, since it could never be satisfied.

A query reads the session as it stands, so one answered before fire_rules/2 reports what was true before the pending activations fired.

10. What is asserted about all of this

Facts alone are a weak lens. When a node propagates a token it had already propagated, the duplicate fact collapses into a count bump in the multiset: Rete.Session.facts/1 looks perfect and the corruption surfaces much later, as a fact that survives the retraction that should have removed it. The suite therefore asserts on session.state.memory, and these four are the invariants that actually catch engine bugs:

• full drain — retract everything, then every memory equals a fresh session's (Rete.Session.new([Mod]).state.memory). That pins both "drained" and "exactly one root token", which an emptiness check structurally cannot see;
• support counting — a fact concluded by exactly one match is held exactly once; two supports need two retractions and the first leaves the fact standing;
• round trip — insert X, fire, retract X, fire, compare against the state before;
• order independence — the same facts in any order, in any batching, give the same derived state, and any sequence of inserts and retracts leaves a session equal to one rebuilt from the surviving facts.

Plus one that no end-to-end property reaches, and so is tested against the memory directly: a memory reports the occurrences it actually held, not the ones it was asked to remove.

11. Firing bodies concurrently

fire_rules/2 takes :concurrency, defaulting to 1. Above 1 it pops a whole activation group — every agenda bucket sharing the leading {salience, internal_salience} — runs those rule bodies on tasks, and applies their conclusions in group order.

Only the body moves

fire/2 splits into a pure half and a stateful one:

node.rhs |> apply([node.hash, activation.token.bindings])  # pure: hash + frozen bindings
|> normalize_facts()                                        # pure
|> check_facts!(state, node, token)                         # reads the immutable taxonomy
|> well_founded(state, token)                               # reads state.memory

Only the first two lines run on a task. well_founded/3 reads working memory, and one activation's conclusions can retract the support of another, which is exactly what Rete.Agenda.remove/2's :removed/:missing split detects. So conclusions are applied one at a time with a drain() between, and a rule still sees a settled network.

The task closure captures {rhs, hash, bindings} and nothing else. Closing over the state or the network would copy the whole compiled network into every task.

Why the default is 1

A body that builds a tuple is 1.5% of fire_rules; the other 98.5% is propagation. A task costs ~3.5 µs per activation, so parallelising cheap bodies is a large net loss. Measured over 2,000 activations on 16 cores:

Break-even is ~5 µs — far above anything a pure body does, and far below any I/O, so the option pays exactly when a body waits on something. Sixteen bodies sleeping 20 ms go from 335 ms to 21 ms.

What it does and does not preserve

It preserves the resulting session, down to the truth-maintenance ledger. A property over the every-node-kind ruleset asserts that for concurrency 2..8.

It does not preserve firing order, and that follows from batching rather than from this implementation. Firing one at a time re-sorts the agenda after every activation, so a rule activated by another's conclusion can overtake one that was already pending. Popping a group freezes it, so the new activation waits for the next group:

sequential   a → b → c    b, activated by a, overtakes the already pending c
concurrent   a → c → b    the group {a, c} was frozen before a ran

It also does not guarantee a body runs only for matches that survive. A body may run for an activation that another in the same group then invalidates. What it computed is discarded — that activation does not fire, and Rete.Agenda.remove/2 returning :missing is what detects it — but a side effect the body performed is not undone. Clara documents the same for fire-rules-async. docs/dsl.md states the at-least-once contract.

Discarding rather than applying is the whole reason the group is peeked instead of popped. Taking the group off the agenda up front left the retraction nothing to cancel, so the conclusion was inserted against a token that no longer existed and no retraction could ever take it back. Rete.EngineTest pins both halves: the activation does not fire, and the session still drains to empty.

What a body runs in

A body runs on a Task, which means the usual process-boundary rules apply:

• $callers is set, so Ecto's SQL sandbox and anything else that walks the caller chain keeps working;
• Logger.metadata is not inherited. A body that logs loses the request metadata of the process that called fire_rules/2. Read it before firing and pass it in a fact, or set it inside the body;
• the bindings are copied into the task. That is nothing for scalars, but a collection binding copies the whole gathered list. Measured on 20 collections of 2,000 elements each: 0.1 ms at concurrency: 1, 1.6 ms at concurrency: 8. A collection rule looks cheap while being expensive to hand over, so it needs a genuinely slow body before raising :concurrency pays.

The result buffer is not chunked, deliberately

Task.async_stream with ordered: true does not bound its buffer: with a slow first item, every later one completes and is held until the first can be emitted. So a whole group's results can be in memory at once.

Chunking the stream would bound that, and was measured rather than assumed. It is not worth it. A group of 50,000 activations peaks at 66 MB sequentially and 79 MB at concurrency: 8 — the group itself dominates, and the buffer is ~20% on top of a cost both paths already pay. Against that, chunking costs throughput badly, because every chunk waits for its slowest member. On 256 bodies at concurrency: 8 with 10% stragglers, where perfect scheduling is 296 ms:

Paying 3.4× throughput to save 20% memory is the wrong trade for the workload :concurrency exists for. If a group ever grows large enough for the buffer to matter, a bounded-window pipeline — spawn ahead, apply in order as results land — gets both, at the cost of hand-rolling what Task.async_stream does.

A cycle is a group, not an activation

:max_cycles counts passes of the fire loop. One pass takes one activation at the default concurrency and one whole activation group above it, so a group is a single cycle however many activations it holds.

That is the point rather than a leak: raising :concurrency does not consume the allowance faster, it fires the same work in fewer, larger cycles. 500 pending matches of one rule are 500 cycles one at a time and one cycle as a group. An oscillating ruleset is still caught either way, because each round trip of the oscillation is its own cycle.

It also narrows the known gap below. Clara counts transitions between activation groups; above concurrency: 1 so does this.

Errors

A body's error is caught on the task and reraised in the caller with its original stacktrace, which already names the generated __rhs_<name>__ frame — without that, a rule body's exception would surface as an opaque task exit. Throws are re-thrown with :erlang.raise/3. A :timeout kills the task, and since there is then no original error to reraise, that one case raises a RuntimeError naming the rule.

12. Known gaps

• well_founded/3 costs a pass over the insertion records. Only when the concluded fact is already present, which is the only way the cycle can close, but a rule that keeps re-concluding what another rule concluded pays for it on every activation. Indexing that away was deferred.

• A dropped circular support is not reconsidered. See §8.

• The loop guard counts activations, not activation-group transitions. Clara's signal is better in principle — a ruleset that legitimately fires 50,000 activations in one settling pass is fine — but it misses a loop confined to a single salience level, which is the common runaway. See observability.md §3.

  Resolved by not guessing. The default was 10,000 until mix bench reached it with 4,000 facts through a three-rule chain — 12,000 activations, not a loop in sight — and the guard is now :infinity by default, the same opt-in call Clara makes. A count cannot separate a runaway from a large settling pass, so any default eventually fails correct code, and stopping part way through settling returns an answer that is wrong rather than late. The cost is that an oscillating ruleset now spins until interrupted. observability.md §3 carries the numbers for choosing a cap where that matters.

• No partial firing. fire_rules/2 runs to quiescence in the calling process. There is no fire-one-activation, no async, and no way to interrupt a settling pass other than the cycle cap.

• Nothing is durable. A session is an in-memory value; there is no serialization, checkpointing or distribution.

• Performance has been measured in one dimension only. A profiling pass found three quadratics in the size of a single join key's bucket and fixed them: Rete.Agenda is bucketed by sort key rather than held as one sorted list, Rete.Memory.Bucket replaced the list behind each key with an ordered multiset, and insert/3 and retract/3 no longer append to their op accumulator once per fact. Inserting 4,000 facts under one key went from 250 ms to under 10 ms; retracting 200 of them from a bucket of 8,000, from 108 ms to under 1 ms.

  mix bench (bench/run.exs) is what says so, and keeps saying so: nine scenarios at three sizes each, reporting the empirical exponent rather than a wall-clock number, so a reintroduced quadratic shows up as ~n^2 instead of as a figure nobody has a baseline for. Eight come out linear. The ninth does not, and is left in deliberately — filling one collection measures ~n^1.94, because the private insert_ordered/2 in Rete.Engine.Nodes is O(k) per member. A suite that only reported the good news would be worth less.

  Still unmeasured: wide disjunctions, many rules over one fact type, and sessions large enough to matter for memory rather than time. The fact-to-token index behind well-founded support is also still rebuilt on demand.

  A method note worth keeping. The first attempt fixed the wrong quadratic. Beta memory's append was real and had to go, but it was not what dominated — the agenda was, and an earlier version of this list had already named it. The tell was that a query terminal, which has no agenda, was near-linear while a production terminal was not. Split the measurement before believing an attribution.