gen-derive: stratified rule dispatch with fixpoint convergence — guarded graph rewrite rules for Nix

2026-05-25-gen-derive-design.md

gen-derive — Stratified Rule Dispatch with Fixpoint Convergence

Date: 2026-05-25 Status: Draft Depends on: gen (pure tier: mkIntensional, intensionalEq) for core; gen-select for adapter tier

Purpose

gen-derive is a rule dispatch engine for guarded graph transformations. Given a set of rules (condition + action producer), a position in a graph, and a context, gen-derive answers: "which rules fire here, and what actions do they produce?" It owns the dispatch protocol, phase ordering, fixpoint convergence, conflict resolution, and rule dedup. It does NOT own the action vocabulary — actions are opaque tagged values whose semantics belong to the caller.

The same pattern appears in den (policies), nest-traits (CSS-dispatched rules), and sql-schema (WHERE-clause rules). gen-derive extracts the generic dispatch engine so each consumer defines its domain vocabulary without reimplementing the hard parts (convergence, dedup, phase validation).

Position in Ecosystem

gen (pure primitives — shared foundation)
├── gen-select (selector algebra)
│   └── gen-derive adapter tier (bridges selectors as conditions)

gen-derive core (rule dispatch + fixpoint — depends on gen pure tier only)

# Independent, no cross-deps:
gen-scope, gen-graph, gen-aspects, gen-schema, gen-bind

# Consumer wires them together:
den (gen-derive + gen-select + gen-scope + gen-graph + gen-aspects + gen-schema + gen-bind)

Two-tier import model following gen's pure/lib pattern:

• Core tier — imports gen pure tier only. Conditions are opaque; caller provides match.
• Adapter tier — imports gen-select. Bridges gen-select selectors into gen-derive conditions.

Terminology

All terms drawn from academic literature to avoid bleeding den's current fx-pipeline naming.

Term	Definition	Source
Rule	Guarded transformation unit: condition + action producer + identity	Ehrig et al. 2006; Forgy 1982
Condition	Predicate that determines when a rule fires	Forgy 1982 (RETE LHS)
Action	Opaque tagged value produced when a rule fires	Forgy 1982 (RETE RHS)
Phase	Named dispatch group with DAG ordering constraints	Arntzenius 2016 (stratified negation)
Match	Process of testing a condition against a position	Ehrig 2006 (match morphism)
Fixpoint	Convergent dispatch loop with monotone feedback	Arntzenius 2016 (fix); Radul 2009 (quiescence)
NAC	Negative application condition — pattern that must NOT match	Ehrig 2006

Rule Shape

{
  condition : opaque;                 # anything the match function accepts
  nac       : opaque | null;          # negative application condition (default: null)
  produce   : id -> ctx -> [ action ];
  identity  : string | null;          # mkIntensional name, or null (anonymous)
  priority  : int;                    # default: 0 (higher = fires first)
  overrides : [ string ];             # identities of rules this one replaces (default: [])
}

Condition — opaque to gen-derive. The caller's match function interprets it. Can be a gen-select selector, a builtins.functionArgs record, a bare predicate, or any caller-defined type.

NAC — same type as condition, checked before condition. If nac matches, the rule does not fire. Provides traceability ("rule X suppressed by NAC" vs "rule X didn't match") and clean separation of "where does this apply?" from "what would make it wrong to apply here?"

Identity — used for dedup across fixpoint iterations and for overrides targeting. gen-derive detects mkIntensional-wrapped functions via the three-field check (name && __functor && closure) and extracts identity automatically. Rules with identity = null are anonymous — they fire every iteration they match, never appear in the fired set, and cannot be targeted by overrides.

Priority — numeric, higher fires first. Equal priority = all fire (additive). With exclusive = true on dispatch, only the highest-priority group fires.

Overrides — list of rule identities this rule replaces. When an overriding rule matches, overridden rules are pre-seeded in the fired set and suppressed. Requires both rules to have identities — overriding anonymous rules is a definition-time error.

Action Shape

Opaque tagged values. gen-derive classifies but does not interpret them.

# Example: den v2 would define
{ __action = "spawn"; nodeId = "user:tux"; decls = { ... }; }

# gen-derive sees: classify action → "structural"
# gen-derive does NOT know what "spawn" means

The caller provides classify : action -> string mapping each action to its phase name. gen-derive validates that all actions from a single rule invocation classify to the same phase.

Phase DAG

Phases are named dispatch groups with DAG ordering constraints. Inline entry constructors over lib.toposort (~15 lines, zero external deps).

phases = {
  structural = derive.entryAnywhere {};
  resolution = derive.entryAfter [ "structural" ] {};
  collection = derive.entryAfter [ "resolution" ] {};
};
# toposort → [ "structural", "resolution", "collection" ]

Dispatch processes phases in topological order — all rules in phase N complete before phase N+1 begins.

Degenerate case: Consumers who don't need phases:

phases = { default = derive.entryAnywhere {}; };
classify = _: "default";

Single phase, no validation, dispatch/fixpoint reduce to flat rule matching.

Entry constructors:

derive.entryAnywhere : data -> entry           # no ordering constraints
derive.entryAfter    : [ name ] -> data -> entry  # fires after named phases
derive.entryBefore   : [ name ] -> data -> entry  # fires before named phases
derive.entryBetween  : [ name ] -> [ name ] -> data -> entry  # between two sets

Core API

Match Contract

Caller-provided function that interprets conditions:

match : condition -> id -> ctx -> bool

gen-derive calls match for both condition and nac fields. Same function, same type — NACs are just conditions with inverted semantics.

A rule fires when: match condition id ctx AND (nac == null OR NOT match nac id ctx).

derive.dispatch

One-shot: fire all matching rules at a position, return actions grouped by phase.

dispatch {
  rules;              # [ rule ]
  id;                 # current position
  context;            # caller-defined context
  match;              # condition -> id -> ctx -> bool
  classify;           # action -> phase name
  phases;             # DAG of phase entries
  exclusive ? false;  # if true, only highest-priority group fires
} → {
  actions;            # { structural = [ ... ]; resolution = [ ... ]; ... }
  fired;              # { ruleIdentity = true; ... }
}

Dispatch sequence:

1. Evaluate all rules: check NAC (if present), then condition
2. Collect matched rules
3. Remove rules whose identities appear in overrides of other matched rules
4. Sort by priority (descending)
5. If exclusive: keep only the highest-priority group
6. Fire each matched rule's produce id context
7. Classify actions, validate single-phase-per-rule
8. Group actions by phase in topological order
9. Return actions + fired identity set

Phase validation error:

gen-derive: rule "host-guards" produced actions in multiple phases: structural, resolution

derive.fixpoint

Convergent dispatch loop with monotone feedback.

fixpoint {
  rules;              # [ rule ]
  context;            # initial context
  match;              # condition -> id -> ctx -> bool
  classify;           # action -> phase name
  phases;             # DAG of phase entries
  extract;            # actions -> attrset (feedback from actions)
  combine;            # old ctx -> extracted -> new ctx
  eq;                 # old ctx -> new ctx -> bool (stability check)
  exclusive ? false;
  maxIter ? 100;      # safety cap
} → {
  actions;            # all actions from all iterations, grouped by phase
  context;            # final stable context
  iterations;         # int
}

Loop structure:

iteration 0:
  dispatch rules against context → actions₀, fired₀
  feedback₀ = extract actions₀
  context₁ = combine context feedback₀
  if eq context context₁ → STABLE, return
  else → iteration 1

iteration N:
  dispatch rules against contextₙ (with accumulated fired set) → actionsₙ, firedₙ
  feedbackₙ = extract actionsₙ
  contextₙ₊₁ = combine contextₙ feedbackₙ
  if eq contextₙ contextₙ₊₁ → STABLE, return
  else if N >= maxIter → throw "gen-derive: fixpoint did not converge after ${maxIter} iterations"
  else → iteration N+1

Each iteration carries the accumulated fired set — rules with identity fire at most once across all iterations. Anonymous rules (identity = null) may fire every iteration.

Convergence guarantee: The caller's responsibility. gen-derive provides the iteration cap as a safety net. Typical pattern: eq = a: b: builtins.attrNames a == builtins.attrNames b (key-monotonic — converges when no new keys appear).

derive.fromFunction

Converts a Nix function into a rule using builtins.functionArgs as the condition (canTake pattern from gen).

fromFunction : fn -> rule
fromFunction = fn:
  let
    args = builtins.functionArgs fn;
    isIntensional = fn ? name && fn ? __functor && fn ? closure;
  in {
    condition = args;
    nac = null;
    produce = _id: ctx: fn ctx;
    identity = if isIntensional then fn.name else null;
    priority = 0;
    overrides = [];
  };

The default match implementation for fromFunction conditions checks that all required args (non-optional in functionArgs) are present in the context:

fromFunctionMatch = condition: _id: ctx:
  let
    required = lib.filter (k: !condition.${k}) (builtins.attrNames condition);
  in lib.all (k: ctx ? ${k}) required;

Callers using fromFunction can use this as their match function, or compose it with other matchers.

Conflict Resolution

Three strategies, applied in order during dispatch. All work with opaque conditions in core; specificity requires the gen-select adapter.

Priority (core)

Rules declare priority : int (default 0). Higher priority fires first. Within the same priority level, all matching rules fire (additive).

With exclusive = true, only the highest-priority group fires — lower priorities are suppressed entirely.

Override (core)

A rule's overrides field names rule identities it replaces. When an overriding rule matches at a position, overridden rules are pre-seeded in fired and do not fire, even if their conditions match.

{
  condition = ...;
  produce = ...;
  identity = "custom-host-guards";
  overrides = [ "host-guards" ];
}

Constraints:

• Both the overriding rule and all targets must have non-null identities
• Override of anonymous rules throws: gen-derive: cannot override anonymous rule
• Overrides are applied BEFORE priority sorting — an overridden rule is suppressed regardless of its priority level. The intent of overrides is "I replace this rule," which must hold unconditionally

Specificity (adapter tier)

When multiple rules match at the same priority level, most-specific condition wins. Specificity is measured by counting constraint terms in the gen-select selector structure.

# specificity 1
sel.attrs { type = "host"; }

# specificity 2 (more specific, wins)
sel.attrs { type = "host"; env = "prod"; }

Specificity function (adapters/select.nix):

selectorSpecificity : selector -> int

Counting rules:

• Each key in sel.attrs = +1
• Each combinator (sel.has, sel.within, sel.parentMatches) = +1
• sel.and / sel.or = sum of children
• sel.not = specificity of inner selector
• sel.star = 0
• sel.when = 0 (opaque, no measurable specificity)

Resolution order: override suppression → priority (descending) → specificity (descending) → ties fire additively.

Rule Composition Combinators

Three convenience methods in core. Each produces a new rule from existing rules.

derive.restrict

Narrows a rule's condition. The new rule matches only when both the original condition AND the extra condition hold.

derive.restrict : condition -> rule -> rule

Produces a { __restricted = true; original; extra; } tagged condition. The match function receives this — the default fromFunctionMatch checks both. The gen-select adapter AND-s both selectors. Custom match functions handle the tag themselves.

NACs are preserved from the original rule unchanged.

# Restrict a host rule to prod only
derive.restrict (sel.attrs { env = "prod"; }) hostRule

derive.override

Sugar over the overrides field. One rule replaces another.

derive.override : rule -> rule -> rule
derive.override = original: replacement:
  if original.identity == null
  then throw "gen-derive: cannot override anonymous rule"
  else replacement // {
    overrides = (replacement.overrides or []) ++ [ original.identity ];
  };

derive.chain

Sequential composition. Rule A's actions feed as context to rule B.

derive.chain : { extract } -> rule -> rule -> rule
derive.chain = { extract }: ruleA: ruleB: {
  condition = ruleA.condition;
  nac = ruleA.nac;
  produce = id: ctx:
    let actionsA = ruleA.produce id ctx;
    in actionsA ++ ruleB.produce id (ctx // extract actionsA);
  identity =
    let a = ruleA.identity or "anon";
        b = ruleB.identity or "anon";
    in "chain:${a}:${b}";
  priority = ruleA.priority;
  overrides = ruleA.overrides ++ ruleB.overrides;
};

The extract parameter is the same function used by fixpoint — converts actions into context additions. Callers already have this function; chain reuses it for intra-rule composition.

Negative Application Conditions (NACs)

The nac field on rules — a condition that must NOT match for the rule to fire. Same type as condition, checked before it.

{
  condition = sel.attrs { type = "host"; };
  nac = sel.has (sel.attrs { type = "monitoring"; });
  produce = id: ctx: [ ... ];
  identity = "add-default-monitoring";
}

Semantics: match condition id ctx AND (nac == null OR NOT match nac id ctx).

Why not just sel.not inside the condition?

1. Traceability — dispatch can report "rule X suppressed by NAC" distinctly from "rule X condition didn't match." Debugging fixpoint loops is hard enough without collapsing two failure modes.
2. Separation of concerns — condition = "where does this apply?" NAC = "what would make it wrong to apply here?" Different questions, declared separately.
3. Composition — derive.restrict composes conditions but preserves NACs. If NACs were baked into the condition via sel.not, restriction would accidentally narrow the negative check too.

Dedup and Identity

Rules are deduped across fixpoint iterations via their identity field.

Rules with identity (identity != null): tracked in fired set. Once fired at a position, never re-fired even if context changes. Prevents infinite loops — a rule that enriches context doesn't re-trigger itself.

Rules without identity (identity = null): fire every iteration they match. Useful for stateless projections. The fixpoint still converges because eq checks context stability, not rule firing.

fromFunction and identity: By default, fromFunction produces identity = null. Callers who need dedup wrap with mkIntensional first:

# No dedup — fires every iteration it matches
derive.fromFunction ({ host, ... }: [ ... ])

# Deduped — fires at most once per position
derive.fromFunction (mkIntensional "host-guards" {} ({ host, ... }: [ ... ]))

Dedup scope: The fired set is scoped to the dispatch/fixpoint call. The caller controls position granularity — if they call dispatch per-node, dedup is per-node. If they call it once for the whole graph, dedup is global. gen-derive doesn't impose a scoping model.

Optional Helper: mkActions

Generates tagged action constructors and a classify function from a phase declaration.

derive.mkActions {
  structural = [ "spawn" "enrich" "emit" ];
  resolution = [ "edge" "drop" "reroute" "inject" ];
  collection = [ "pipe.from" "pipe.gather" "pipe.ascend" "pipe.target" "pipe.channel" ];
}
→ {
  spawn    = args: { __action = "spawn"; } // args;
  enrich   = args: { __action = "enrich"; } // args;
  # ... etc for all tags
  classify = action: /* looks up action.__action in the phase map */;
}

Optional. Complex consumers like den write their own constructors (e.g., policy.resolve.to with __targetKind) and provide classify directly. mkActions covers the simple case where constructors are plain taggers.

Deferred: RETE Network Optimization

Not implemented in v1. Designed for future addition without API changes.

RETE (Forgy 1982) optimizes multi-rule matching by sharing condition evaluation across rules via alpha/beta networks. In Nix, laziness provides some of this naturally — ctx.data id is memoized, repeated attribute access is O(1).

RETE would require conditions to be inspectable structured data (not opaque predicates), which is compatible with the gen-select adapter tier but not the opaque core. A future derive.rete function could accept [ rule ] where all conditions are gen-select selectors and build an indexed dispatch network.

Why defer: Known consumer scale (den ~30 rules, nest-traits ~50) doesn't justify the complexity (~200-400 lines). The API is forward-compatible — derive.rete would have the same return shape as derive.dispatch.

File Layout

gen-derive/
  default.nix              -- entry point, exports API
  flake.nix                -- gen as sole flake input
  lib/
    core/
      rule.nix             -- rule constructor, fromFunction, fromFunctionMatch
      dispatch.nix         -- one-shot dispatch, phase validation, conflict resolution
      fixpoint.nix         -- convergence loop, dedup tracking, iteration cap
      dag.nix              -- entryAnywhere/After/Before/Between over lib.toposort
      actions.nix          -- mkActions helper
      compose.nix          -- restrict, override, chain
    adapters/
      select.nix           -- gen-select bridge: mkMatch, selectorSpecificity
  templates/
    ci/                    -- core test suite (nix-unit)

Estimated size: ~300-400 lines total (core ~250-320, adapter ~30-50, DAG ~15).

Dependencies

• Core: gen (pure tier: mkIntensional, intensionalEq) + lib from nixpkgs
• Adapter: gen-select (selector matching, structural inspection for specificity)
• No dependency on gen-scope, gen-graph, gen-schema, gen-aspects, or gen-bind

Test Suite

Follows gen ecosystem conventions: auto-discovered test files, nix-unit, Justfile shortcuts.

templates/ci/flake.nix

• Inputs: gen-derive (the library), gen (for mkIntensional in tests), nixpkgs, nix-unit
• Auto-discovers all .nix files in ./tests/
• Imports each with { lib, deriveLib, genPure } context
• Exposes flake.outputs.tests for nix-unit, checks.${system}.default for CI

templates/ci/Justfile

system := `nix-instantiate --eval --raw -E builtins.currentSystem`

ci test="" *args:
  nix-unit --override-input gen-derive ../.. --flake .#.tests{{if test != "" { "." + test } else { "" }}} --gc-roots-dir .gcroots {{args}}

repl:
  nix repl --override-input gen-derive ../.. .

Test files

File	Suite	Coverage
rule.nix	rule	Rule construction, fromFunction, identity detection from mkIntensional
dispatch-basic.nix	dispatch-basic	Single rule, multiple rules, no matches, all-match
dispatch-phases.nix	dispatch-phases	Phase grouping, topological ordering, single-phase validation error
dispatch-nac.nix	dispatch-nac	NAC suppression, NAC with condition, null NAC passthrough
conflict.nix	conflict	Priority sorting, exclusive mode, override suppression, override-of-anonymous error
fixpoint.nix	fixpoint	Convergence in 1/2/3 iterations, maxIter cap, dedup across iterations, anonymous re-firing
compose.nix	compose	restrict, override, chain — each produces correct rule shape
dag.nix	dag	Entry constructors, toposort ordering, cycle detection
actions.nix	actions	mkActions generates constructors + classify, unknown action error
adapter-select.nix	adapter-select	mkMatch bridges gen-select, selectorSpecificity counting

Test file pattern

{ lib, deriveLib, genPure, ... }:
let
  derive = deriveLib;
  mkI = genPure.mkIntensional;

  # Simple action vocabulary for tests
  fx = derive.mkActions {
    structural = [ "spawn" "enrich" ];
    resolution = [ "edge" "drop" ];
  };

  # Match function for fromFunction-style conditions
  match = derive.fromFunctionMatch;

  # Simple context
  ctx = { host = { name = "igloo"; env = "prod"; }; };
in
{
  dispatch-basic = {
    test-single-rule-fires = {
      expr = derive.dispatch {
        rules = [
          (derive.fromFunction ({ host, ... }: [ (fx.spawn { nodeId = "user:tux"; }) ]))
        ];
        id = "host:igloo";
        context = ctx;
        inherit match;
        classify = fx.classify;
        phases = { structural = derive.entryAnywhere {}; };
      };
      expected = {
        actions = { structural = [ { __action = "spawn"; nodeId = "user:tux"; } ]; };
        fired = {};  # anonymous rule, not tracked
      };
    };
  };
}

Consumers in Den v2

Den v2 mechanism	gen-derive equivalent
Policy functions { host, ... }: [ effects ]	derive.fromFunction — signature is the condition
policy.when predicate policyFn	derive.restrict (sel.when pred) rule
policy.for entity policyFn	derive.restrict (sel.attrs { id_hash = entity.hash; }) rule
Enrichment convergence loop	derive.fixpoint with extract/combine/eq
Phase separation (structural/resolution/collection)	derive.dispatch with three-phase DAG
policy.include aspect	Action with { __action = "edge"; ... } — caller vocabulary
policy.exclude aspect	Action with { __action = "drop"; ... } — caller vocabulary
Policy dedup (dispatchedPolicies)	Rule identity + fired set
Conditional aspects (meta.guard)	derive.restrict with guard predicate as condition
nest-traits CSS rule dispatch	derive.dispatch with gen-select adapter, selectors as conditions
sql-schema WHERE-clause rules	derive.dispatch with sql-specific match function

Academic Provenance

Feature	Paper
Rule = condition + action	Forgy (1982) "RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem"
Algebraic graph rewriting rules	Ehrig et al. (2006) "Fundamentals of Algebraic Graph Transformation"
Stratified dispatch phases	Arntzenius & Krishnaswami (2016) "Datafun: A Functional Datalog" — stratified negation
Fixpoint convergence via monotone feedback	Arntzenius & Krishnaswami (2016) fix; Radul & Sussman (2009) "The Art of the Propagator" — quiescence
Negative application conditions (NACs)	Ehrig et al. (2006) — NACs in graph transformation rules
Rule identity and dedup	Palmer et al. (2024) "Intensional Functions" — Theorem 5.12, program-point identity
Function signature as condition (canTake)	den (novel, already extracted to gen)
Conflict resolution: priority / specificity	Forgy (1982) salience; W3C CSS specificity
Rule composition (restrict/override/chain)	Batory (2005) "Feature-Oriented Programming and the AHEAD Tool Suite" — feature refinement algebra
Chemical reaction model (rules as reactions)	Berry & Boudol (1990) "The Chemical Abstract Machine"
Phase ordering via DAG	home-manager dag pattern; lib.toposort from nixpkgs
Open action types with classifier	Hedin & Magnusson (2003) "JastAdd" — host-language-typed attributes, framework owns dispatch