The compiled network

What the build phase produces and the engine runs. The companion to ir.md, which covers everything up to a classified Rete.IR.Production, and to engine.md, which covers what happens to a network once it exists.

Status: implemented, end to end.

1. Pipeline

The DSL front end runs at compile time, inside each defrule. What is left for build time is the part that depends on the whole rule set rather than on one rule:

Rete.Compiler.build([MyRuleset])
  |> Rete.Compiler.Negation.extract/1   rewrite compound negations into helpers
  |> Rete.Compiler.BetaGraph.build/1    beta nodes and edges, shared where equal
  |> Rete.Network.new/3                 alpha nodes grouped by code, taxonomy indexed

Node sharing is why this cannot happen per rule: whether two conditions collapse onto one node depends on what every other rule already put in the graph.

2. Structure

%Rete.Network{
  alphas:      %{code => %Node.Alpha{}},   # one per distinct expression code
  alpha_beta:  %{code => [beta_id]},       # the beta nodes each alpha feeds
  taxonomy:    %Rete.Taxonomy{},           # indexed: fact type => alpha codes
  graph:       %Rete.Compiler.BetaGraph{}, # beta nodes and their edges
  queries:     %{name => beta_id},
  productions: [%Rete.IR.Production{}]     # including generated helpers
}

The network is built once and never mutated, so any number of sessions can share one. Working memory, the agenda and pending propagations are the engine's, not the network's.

How a fact travels

1. Rete.Taxonomy.alpha_ids/2 maps the fact's type to alpha codes. This is the only place the taxonomy is consulted.
2. Each alpha's arity 1 function turns the fact into a bindings map, or nil. It matches a fact of any type on purpose — the type decision was step 1.
3. Matching elements go to the beta nodes in alpha_beta, and the engine propagates along the graph's forward edges.

3. Node kinds

Nodes are data; activation lives in Rete.Engine.Nodes. No node carries its children: they are the graph's forward edges, because a node is shared precisely when it is equal, and equality must not depend on how many rules happen to have hung children off it.

:propagates_empty? on the accumulate nodes

The locked empty-collection rule, precomputed. Note that :new_bind for a collection counts only participating variables: one that no other condition's pattern matches on is local to the collection and excluded, so a guarded collection over otherwise-local variables is ungrouped and does propagate []. See the Rete.IR.Coll section of ir.md.

• true when the pattern introduces no new variables. Every variable it uses is already fixed by the token, so there is exactly one group and the node propagates [] when nothing matches — the rule fires with an empty list.
• false when it introduces one. It groups by that variable, and a group only exists where a fact created it, so there is no empty group to invent.

Collection element order is unspecified

A rule may not depend on the order of the list it receives. Sort in the right hand side if order matters.

The engine does in fact keep collections in a deterministic order — elements are inserted by 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 deliberate: without it a rule that returns its collection would produce a different fact depending on insertion order, and the engine's order-independence property would hold for every rule except that one.

But it is an implementation guarantee, not a contract. Term order is arbitrary from the author's point of view, and nothing about it is a useful thing to build on.

4. Sharing

Two conditions collapse onto one node when they are equal and have the same parent set. Equality alone is not enough, and the difference is a correctness bug, not a missed optimisation:

defrule a({:customer, cid}, {:order, cid, amt})
defrule b({:vendor, cid},   {:order, cid, amt})

The two {:order, cid, amt} conditions are equal but sit under different parents. Sharing them would let a token from {:vendor, ...} join elements that only ever belonged to {:customer, ...}, so a would fire on b's facts. Clara records the same requirement as issue 433.

Equality is Rete.Network.Node.sharing_key/1, built from expression codes — never from captured functions, which are never equal, and never from a struct holding :__ast__, which would compare quoted AST that is not part of identity. W1 guarantees a code is deterministic across compilations and equal exactly when behaviour is equal, which is what makes sharing reproducible between a full build and an incremental one.

A terminal keys on its production's identity, so two rules with an identical left hand side still get one terminal each and fire independently.

Alpha sharing is the same idea one level up: conditions are grouped by expression code, so a condition written in four rules is matched once per fact. {:order, cid, _amt} and {:order, cid, _} share, because W1 canonicalises discarded variables.

5. Disjunctions

{:or, [b1, b2]} adds each branch as its own chain under the current parents and hands the union of the branch terminals to the next condition. That is why a condition is added under a list of parent ids: the condition after a disjunction has one parent per branch, and the branches re-converge on it.

This is also why the left hand side is never flattened to DNF. Whole-LHS DNF is exponential in the number of disjunctions; fanning out and re-converging per condition is linear.

6. Compound negation extraction

A negation node watches one condition. It cannot watch a conjunction, and de Morgan does not rescue it: not(and(a, b)) = or(not a, not b) is sound propositionally, but rule conditions share existentially quantified variables, so with orders {1} and refunds {2} the original is true and the rewrite is false. Rete.DSL.Normalize therefore leaves a CompoundNegation for Rete.Compiler.Negation.

defrule clean({:customer, cid}, {:nand, [{:order, cid}, {:refund, cid}]})

# becomes, in effect
defrule clean__neg_1({:customer, cid}, {:order, cid}, {:refund, cid}) do
  {:"...clean__neg_1", %{cid: cid}}        # the marker
end
defrule clean({:customer, cid}, {:not, [{:"...clean__neg_1", cid}]})

Three properties make this correct:

• The marker is scoped. It carries the ancestor bindings the conjunction joins on, and the negation matches on them. Otherwise one customer with both an order and a refund would suppress the rule for every customer — the negation would ask "does any match exist" instead of "does one exist for this cid". Clara's issue 304.
• The helper repeats the prefix, which is what binds those variables, and means the marker is only produced for groups that reached the negation.
• The helper fires first, via :internal_salience. Otherwise the negating rule observes an absence that had merely not been computed yet, fires, and is retracted by truth maintenance — a visible spurious activation.

The marker's type is the generated name, so the alpha index routes it to exactly one place. Its alpha is the one exception to "an alpha matches a fact of any type": it checks the tag, because a marker is engine machinery rather than a user fact and a stray tuple of the same shape must not be mistaken for one.

Extraction runs after macro expansion, so a helper's expressions are plain closures wrapped in Rete.IR.Expr rather than functions generated into a module.

7. What the engine must honour

• Activation order is {salience, internal_salience} descending, then node id. Rete.Network.production_nodes/1 already returns them in that order. Ignoring :internal_salience breaks extracted negations.
• Only logical inserts. A production's :rhs returns facts to insert, truth maintained. There is no unconditional insert and no RHS retract. Session level retract exists, and TMS cascades from it.
• Taxonomy is the index's job. Never re-check a fact's type inside an alpha.
• :propagates_empty? decides whether an accumulate node emits [].
• A Test node has no fact input, so it neither joins nor binds.

8. Known gaps

• No subsumption between rules. Two rules whose left hand sides differ only in a redundant condition build separate chains.
• Sharing is prefix-only. Two rules that share a suffix but not a prefix do not share anything, which is inherent to how a beta network is built.