Den v2: Demand-Driven Attribute Grammar over Scope Graphs

Den v2 replaces the 37-handler fx-pipeline (~7,000 lines) with demand-driven attribute evaluation over a scope graph, built on five standalone, fully decoupled libraries. Tree expansion is interleaved with evaluation via Nix's native laziness — no convergence loops, no flat pre-registration, no iteration.

Supersedes: 2026-05-19-hoag-pipeline-architecture.md, 2026-05-19-scope-engine-design.md

Prior Work

The fx-pipeline (den v1) uses an algebraic effects trampoline with 37 sequential handlers, 25 mutable state fields, and nix-effects for stack safety. Implementation analysis revealed that the complexity serves the handler-chain architecture, not inherent problem complexity. A subsequent compiler-passes model was us manually scheduling what Nix's lazy evaluation does automatically.

Theoretical Foundations

Knuth (1968) — Attribute grammars: inherited (top-down) and synthesized (bottom-up) attributes on trees
Vogt et al. (1989) — Higher-Order AGs: tree structure is a computable attribute (NTAs expand on demand)
Hedin (2000) — Reference AGs: cross-node references via import edges
Hedin & Magnusson (2003) — JastAdd: aspects modularly extend AGs; inter-type declarations parallel neededBy
Neron et al. (2015) — Scope graphs: P edges (parent/lexical), I edges (import/cross-scope), specificity D < I < P
van Antwerpen et al. (2016) — Statix: constraint-based scope graph resolution
van Antwerpen et al. (2018) — Scopes as Types: static guarantees of unambiguous resolution, custom edge labels
Mokhov (2017) — Algebraic Graphs: four primitives (empty, vertex, overlay, connect), compositional graph construction
Mokhov et al. (2018) — Build Systems à la Carte: demand-driven evaluation = what lib.fix does natively
Palmer et al. (2024) — Intensional Functions: program-point identity, closure inspection, search monad with intensional dedup
Reynolds (1972) — Defunctionalization: closures → tagged data + dispatch (parametric aspect wrapping)
Lorenzen et al. (2025) — First-Order Laziness: lazy constructors inspectable before forcing (deferredModule)
Arntzenius & Krishnaswami (2016) — Datafun: monotonic query combinators, fixpoint with termination guarantee
Sloane et al. (2010) — Kiama: demand-driven AG evaluation via lazy vals, attribute type vocabulary
Kiczales et al. (1997) — AOP: pointcuts ≈ policy guards, advice ≈ class delivery, join points ≈ scope graph positions
Batory (2005) — AHEAD: features as algebraic composition (GenVoca); feature ≈ den aspect
Tarr et al. (1999) — N Degrees of Separation: multi-dimensional concerns; classes are dimensions, aspects cut across
Kahn (1974) — Deterministic dataflow: named channels, monotonic accumulation
Radul & Sussman (2009) — Propagator networks: monotonic cells, partial information
Leijen (2005) — Extensible Records with Scoped Labels: row polymorphism for gen-schema
Bracha & Cook (1990) — Mixin-based Inheritance: gen-schema mixin composition

Library Stack (All Shipped, Fully Decoupled)

Library	Repo	Tests	Role in den v2
gen	`github:sini/gen`	40	Search monad (Palmer §3), record algebra (Leijen), mkIntensional, Either, identity
gen-schema	`github:sini/gen-schema`	129	Entity registries (mkSchemaOption, mkInstanceRegistry), `_topology`/`_edges`/`_kindNames` introspection, refs, mixins, refinements, collections
gen-aspects	`github:sini/gen-aspects`	40	Aspect type system: aspectType (Palmer flat dispatch), aspectSubmodule, aspectsType, canTake, cnf hooks (classes, moduleArgs, aspectModules, metaModules)
gen-graph	`github:sini/gen-graph`	105	Accessor-based graph query combinators (Arntzenius): C-level BFS via genericClosure, reachableFrom, canReach, selfReachable, dependentsOf, cycles, transitiveReduction, fleet-scale partitioning
gen-scope	`github:sini/gen-scope`	145	True HOAG evaluator: demand-driven eval via `lib.fix`, co-located `_eval` memoization, selective materialization (subtreeOf, nodesOfType, allNodesWhere), algebraic graphs (Mokhov), Neron resolution, circular attributes (Sloane)
gen-select	`github:sini/gen-select`	163	Selector algebra: pattern matching over attributed graph positions. 11 constructors, gen-scope + gen-graph adapters, CSS + SQL WHERE demos.
gen-bind	`github:sini/gen-bind`	40+	Module binding: inject external args into NixOS modules. Merge strategies, lazy contracts (Chitil), provenance (Findler), signature inference (Cardelli), thunk deferral.
gen-derive	(spec approved)	—	Guarded graph rewrite rules: stratified dispatch, fixpoint convergence, NACs, priority/override/specificity conflict resolution, canTake adapter.

Dependency chain (fully decoupled):

gen (pure primitives — shared foundation, zero deps)
├── gen-schema (imports gen; typed registries with _introspection)
├── gen-select (imports gen pure tier; selector algebra)
│   └── gen-derive (imports gen + gen-select; guarded graph rewrite rules)

gen-aspects (pure types, zero deps beyond lib)
gen-graph (accessor-based graph queries, zero deps beyond lib)
gen-scope (HOAG evaluator + resolution, zero deps beyond lib)
gen-bind (module binding with merge strategies, zero deps beyond lib)

No arrows between gen-graph, gen-schema, gen-aspects, gen-scope, and gen-select. Only gen is shared. The coupling point is the CONSUMER (den), not the libraries.

Planned: gen-select — selector algebra for pattern matching over attributed graph positions. Selector constructors (star, attrs, or, not, has, within, when, class, child, descendant), a matches function, and context builder. Used by den for neededBy selectors, pipe.gather/pipe.source predicates, and policy.when guards. Design informed by nest-traits' selectors.nix and CSS selector semantics. Separate spec forthcoming.

Architecture Overview

User declares:
  den.hosts, den.homes, den.aspects, den.policies, den.collections, den.classes

Den v2 evaluates (demand-driven via lib.fix):
  1. Root entity scopes declared from den.hosts/den.homes
  2. Attributes demanded on root nodes trigger:
     a. Policy dispatch → structural effects produce child scopes (HOAG tree expansion)
     b. Enrichment → context accumulation
     c. Aspect resolution → forward expand + neededBy + guards + constraints
     d. Class assembly → classify keys, apply reroutes, emit per-class module lists
     e. Collection routing → graph-native data flow (gather/ascend/target/channel)
  3. Child scopes materialize on demand, get their own attributes evaluated lazily
  4. Output: nixosConfigurations, darwinConfigurations, homeConfigurations

No explicit phases. No "build the graph, then evaluate." The graph GROWS during evaluation — a parent's children attribute produces child nodes, which get their own attributes computed when demanded. This is the true HOAG model (Vogt 1989).

The HOAG Evaluation Model

How It Works in Nix

gen-scope uses lib.fix to create a lazy fixpoint. node is a FUNCTION (not a map) — it resolves any node ID on demand by walking memoized children attributes from roots.

Each node carries a co-located _eval cache — a lazy attrset of its attribute computations, created when its parent's children attribute materializes it. This gives O(1) memoized attribute access for ALL nodes, including synthesized ones.

result = gen-scope.eval {
  roots = { "host:igloo" = { id = "host:igloo"; type = "host"; ... }; };
  attributes = { children = self: id: ...; inherited-context = self: id: ...; };
  parseParent = id: ...;  # O(1) resolution hint
};

# Demand-driven — tree grows when attributes are demanded
result.get "host:igloo" "children"           # → materializes user scopes
result.get "user:tux@host:igloo" "resolved-aspects"  # → evaluates tux's aspects
result.allNodes                              # → Tier 2: forces full tree for queries

Memoization via Co-Located `_eval`

When a parent's children attribute materializes child nodes, each child is wrapped with _eval — a lazy attrset of that child's attribute computations:

wrapChild = childNode:
  childNode // {
    _eval = builtins.mapAttrs (attrName: fn:
      if attrName == "children" then memoChildren self childNode.id
      else fn self childNode.id
    ) attributes;
  };

Every _eval.${attrName} is an attrset entry (lazy thunk). Nix shares attrset thunks across all access sites — each (id, attrName) evaluates exactly once. Proven empirically with builtins.trace.

Two Access Tiers (Transparent to Users)

Tier	Operation	Cost	When to use
Navigation	`self.get id attrName`, `self.node id`	O(depth) first access, O(1) after	Normal attribute evaluation
Collection	`self.allNodes`	O(n) — forces full tree	gen-graph queries, diagrams, fleet ops

Both tiers have full memoization. Users never think about tiers — they pick the appropriate accessor.

Tree Expansion Is an Attribute

Entity scopes are produced by the children attribute — a Vogt NTA (Non-Terminal Attribute):

attributes.children = self: id:
  let
    ctx = self.get id "enriched-context";
    effects = dispatchStructuralPolicies ctx;
  in
  listToAttrs (map (e: {
    name = e.nodeId;
    value = wrapChild { id = e.nodeId; parent = id; decls = e.decls; type = e.type; };
  }) effects);

No convergence loop. No iteration. If env:prod spawns host:web-1 which spawns user:tux, each level materializes on demand when the parent's children attribute is evaluated.

Import Edges as Computed Attributes

Import relationships (Neron I edges) are computed attributes, not structural data:

attributes.imports = self: id:
  let ctx = self.get id "enriched-context";
  in extractImportEdges (dispatchPolicies ctx);

Collection routing (pipe.gather) follows computed import edges. The scope graph's edge structure emerges from evaluation, not declaration.

Policy Architecture

One namespace, three effect vocabularies. Phase routing via policy.when/policy.for combinators. Guard dispatch via function signatures (canTake).

Effect Vocabularies

Vocabulary	Phase	When evaluated	Effects
Structural	`children` attribute	Produces child scope nodes	`spawn`, `enrich`
Resolution	Attribute eval	Operates on the graph	`edge`, `drop`, `reroute`, `inject`
Collection	Attribute eval	Routes data through edges	`pipe.from`, `pipe.gather`, `pipe.ascend`, `pipe.target`, `pipe.channel`

A policy returning effects from different phases is a definition-time error.

Vocabulary (Graph-Native)

Structural effects (building roadways):

Constructor	Replaces	Semantics
`spawn "kind" { bindings }`	`resolve.to "kind" { ... }`	Create child scope node (materialized via parent's `children` attr)
`spawn.shared "kind" { bindings }`	`resolve.shared.to`	Shared (non-isolated) fan-out
`enrich { key = val; }`	`resolve { ... }`	Add declarations to current scope node
`emit entityCfg`	`instantiate`	Wire entity into output configurations

Resolution effects (installing road signs):

Constructor	Replaces	Semantics
`edge aspect`	`policy.include`	Add I edge: current scope → aspect node
`drop aspect`	`policy.exclude`	Constraint: prune aspect from resolution subgraph
`reroute { from, to }`	`policy.route`	Redirect class content between classes
`inject { class, module }`	`policy.provide`	Direct emission into class output

Collection effects (traffic routing):

Constructor	Replaces	Semantics
`pipe.from name [stages]`	`pipe.from`	Declare collection routing for named channel
`pipe.gather pred`	`pipe.collect`	Traverse: gather from scopes matching predicate
`pipe.ascend`	`pipe.expose`	Data flows UP P edge (child → parent)
`pipe.target [aspects]`	`pipe.to`	Targeted delivery to specific aspects
`pipe.channel "other"`	`pipe.as`	Redirect to different collection name
`pipe.source pred`	(new)	Filter: only scopes matching pred emit
`pipe.filter pred`	`pipe.filter`	Remove entries not matching predicate
`pipe.transform fn`	`pipe.transform`	Map each entry
`pipe.fold fn init`	`pipe.fold`	Reduce to single value
`pipe.append value`	`pipe.append`	Add an entry
`pipe.for fn`	`pipe.for`	Replace entire list

Enrichment Model

Enrichment uses gen-scope's circular attribute for bounded convergence. While the audit found zero cross-enrichment usage in 13 external configs, den's own test suite (test-enrichment-chained-policies) validates the mechanism — Policy B can read enrichment keys set by Policy A:

# Policy A: reads declarations, sets isNixos
host-guards = { host, ... }: [ enrich { isNixos = host.class == "nixos"; } ];

# Policy B: reads isNixos (from A), sets platform — cross-enrichment dependency
platform-info = { isNixos, ... }: [ enrich { platform = if isNixos then "linux" else "other"; } ];

Modeled as a circular attribute with key-monotonic convergence (keys only added, never changed):

attributes.enriched-context = circular {
  init = self.get id "inherited-context";
  eq = a: b: builtins.attrNames a == builtins.attrNames b;  # converge on key set
} (self: id: prev:
  let
    effects = dispatchEnrichPolicies prev;
    newEnrichment = foldl' (acc: e: acc // { ${e.key} = e.value; }) {} effects;
  in prev // newEnrichment
) self id;

Convergence guaranteed: enrichment keys are drawn from a finite policy vocabulary, and each iteration can only ADD keys (monotone in the powerset lattice). Bounded by circular's maxIter (default 100, typically converges in 2-3 iterations).

After enrichment converges, resolution and collection policies dispatch on the stable enriched-context.

`policy.when` Phase Routing (Unchanged)

# Wrapping a policy function → gates dispatch with predicate (stays in policy path)
policy.when predicate policyFn

# Wrapping an aspect/effect → creates conditional aspect with meta.guard
# Routes to compile-conditional path, hasAspect from in-flight path set
policy.when predicate den.aspects.foo

Handles cycle avoidance: hasAspect predicates route to the guard system, not policy dispatch.

Backwards Compatibility

policy.include, policy.exclude, policy.route, policy.provide remain as aliases mapping to the new vocabulary. Existing configs work without modification.

Aspect Composition Model

Aspects are nodes in the scope graph. The include tree is a subgraph with I edges. This is the core shift from v1 → v2.

Aspect-Declared Edges

Declaration	Edge type	Direction	Scope
`includes = [ ... ]`	I edge	Forward (outbound)	Static
`neededBy = [ ... ]`	I edge	Reverse (inbound)	Expanded after forward resolution
`meta.guard = pred`	Gated edge	Conditional	Activates when predicate passes
`meta.drop = [ ... ]`	Constraint	Subtree	Prunes nodes from this subgraph
`meta.substitute = { X = Y; }`	Constraint	Subtree	Replaces edge target

Forward Includes (Existing)

den.aspects.my-stack = {
  includes = [ den.aspects.nginx den.aspects.postgres ];
  nixos.networking.hostName = "my-stack";
};

Produces aspect nodes with I edges:

aspect:my-stack ──I──► aspect:nginx
                ──I──► aspect:postgres

Entity binding creates a P edge from entity scope to aspect root:

host:igloo ──P──► aspect:my-stack ──I──► aspect:nginx
                                   ──I──► aspect:postgres

`neededBy` — Reverse Injection (New)

den.aspects.logging = {
  neededBy = [ den.aspects.nginx den.aspects.postgres ];
  nixos.services.journald.extraConfig = "...";
};

"If nginx or postgres is in the resolved set, add I edges FROM them TO me." Reverse direction — logging doesn't need to be explicitly included by every consumer.

Replaces provides.to-users and similar patterns with a general mechanism. The provides API remains as sugar, desugaring to neededBy + entity-kind scoping internally.

Selector support: neededBy accepts both literal aspect references and gen-select selectors:

# Literal: inject when specific aspects are present
den.aspects.logging.neededBy = [ den.aspects.nginx den.aspects.postgres ];

# Selector: inject wherever a pattern matches
den.aspects.monitoring.neededBy = sel.when ({ host, ... }: host.env == "prod");
den.aspects.shell-config.neededBy = sel.entityKind "user";  # replaces provides.to-users

This generalizes provides.to-users/provides.to-hosts — they desugar to neededBy with entity-kind selectors.

Design rule: neededBy must be statically declared on the aspect submodule, not inside parametric function bodies. Composition topology is static; content is dynamic.

Resolution Algorithm

Three-layer stratification: forward expansion → neededBy iteration → guard convergence.

attributes.resolved-aspects = self: id:
  let
    ctx = self.get id "enriched-context";
    effects = self.get id "policy-effects";

    # Layer 1: Forward expand (recursive, evaluates parametrics inline)
    forwardExpand = seen: aspects:
      foldl' (acc: aspect:
        let key = identity.key aspect;
        in if acc.seen ? ${key} then acc
        else let
          concrete = if isParametric aspect then aspect.__fn ctx else aspect;
          newSeen = acc.seen // { ${key} = true; };
          childResult = forwardExpand { seen = newSeen; nodes = acc.nodes; }
            (concrete.includes or []);
        in {
          seen = childResult.seen;
          nodes = childResult.nodes ++ [{ inherit key; content = concrete; }];
        }
      ) { inherit seen; nodes = []; } aspects;

    # Layer 2: neededBy iteration (reverse I edges, monotone)
    withReverse = seen: nodes:
      let extras = filter (a:
        !(seen ? ${identity.key a})
        && any (target: seen ? ${identity.key target}) (a.neededBy or [])
      ) allAspects;
      in if extras == [] then { inherit seen nodes; }
      else let r = forwardExpand seen extras;
        in withReverse r.seen (nodes ++ r.nodes);

    roots = directAspects ++ policyEdgeAspects effects;
    initial = forwardExpand {} roots;
    final = withReverse initial.seen initial.nodes;
  in
  applyConstraints (applyGuards final.nodes);

Layer 3: Guard convergence (monotone path set via circular):

attributes.guard-set = circular { init = resolvedAspectKeys; } (self: id: prev:
  let
    conditionals = filter (a:
      a ? meta.guard && a.meta.guard { pathSet = prev; hasAspect = k: prev ? ${k}; }
    ) allConditionalAspects;
    newKeys = prev // keysOf conditionals;
  in newKeys
) self id;

Guard-activated aspects are added to the resolved set but do NOT trigger additional neededBy expansion.

Parametric Aspects

Parametric aspects are functions taking entity context. Their subgraph is latent — edges discovered during traversal when the function is evaluated inline by forwardExpand.

den.aspects.per-host = { host, ... }: {
  includes = if host.isDesktop then [ den.aspects.gui ] else [ den.aspects.headless ];
  nixos.networking.hostName = host.name;
};

gen-aspects wraps these via functionTo (Reynolds defunctionalization). The OUTER submodule (name, includes — when static, neededBy, meta) is readable without evaluation. The INNER content materializes when the traversal evaluates the fn.

Constraints

Declarations on nodes that prune the subgraph. Propagate via parent-chain resolution (inheritAll).

Scope-level (from policy effects):

den.policies.prod-hardening = { host, ... }:
  lib.optionals (host.environment == "production") [
    (drop den.aspects.debug-tools)
  ];

Aspect-level (subtree-scoped):

den.aspects.hardened-stack = {
  includes = [ den.aspects.nginx den.aspects.postgres ];
  meta.drop = [ den.aspects.debug-tools ];
};

Constraint visibility is determined by ancestor/descendant relationships in the scope graph. Replaces v1's manual owner-chain threading.

Collection System (Formerly Pipes/Quirks)

Collections are named data aggregation channels. Aspects emit into them, aspects consume from them, policies route data between scopes.

Core Model

# Declare a named collection
den.collections.http-backends = {
  description = "HTTP backend addresses for load balancer aggregation";
};

# Emit: aspect uses collection name as a key
den.aspects.nginx = {
  http-backends = { addr = "10.0.0.1"; port = 80; };
};

# Consume: aspect takes collection as module arg
den.aspects.haproxy = {
  nixos = { http-backends, ... }: {
    services.haproxy.config = mkBackends http-backends;
  };
};

# Route: policy declares how data flows
den.policies.collect-backends = { host, ... }: [
  (pipe.from "http-backends" [ (pipe.gather { host, ... }: true) ])
];

Three Routing Primitives

Primitive	Graph operation	Behavior
Local	Data stays within scope's aspect resolution	Default, no policy needed
Ascend	Data flows UP P edge (child → parent)	`pipe.ascend`
Gather	Data flows IN from scopes via computed import edges	`pipe.gather pred`

Plus modifiers: Source (emit-side filter), Target (delivery to specific aspects), Channel (redirect to different collection name).

Collection Attributes

# Local collection data from this scope's resolved aspects
attributes.local-collection-data = self: id:
  let aspects = self.get id "resolved-aspects";
  in collectCollectionKeys collections aspects;

# Received collection data (gathered + ascended + transformed)
attributes.received-collections = collectionAttr {
  traverse = "imports";  # follows computed import edges
  extract = self: importId: self.get importId "local-collection-data";
  combine = a: b: a ++ b;
  filter = node: true;  # or predicate from pipe.gather
} self id;

Attribute Dependency Graph

inherited-context (inherited, top-down via P edges)
    │
    ├──► enrich-effects (structural policies on base context)
    │        │
    │        └──► enriched-context (base + enrichments)
    │                 │
    │                 ├──► policy-effects (resolution + collection policies on enriched ctx)
    │                 │
    │                 └──► children (HOAG: structural effects → child scope nodes)
    │
    ├──► resolved-aspects (forward expand + neededBy + constraints)
    │        │  reads: enriched-context, policy-effects (edge/drop),
    │        │         aspect graph (includes/neededBy)
    │        │
    │        ├──► guard-set (circular: monotone path set convergence)
    │        │
    │        └──► class-modules (classify keys + reroute + inject)
    │                 │
    │                 └──► output-modules (bindings applied, terminal)
    │
    ├──► imports (computed I edges from resolution policies)
    │
    └──► local-collection-data (collection keys from resolved aspects)
              │
              └──► received-collections (gather + ascend + transforms)
                        │
                        └──► output-modules

Attribute Definitions (11 total)

#	Attribute	Type	Reads	Produces
1	`inherited-context`	Inherited	Parent's context + node decls	Entity bindings `{ host, user, ... }`
2	`enrich-effects`	Synthesized	`inherited-context` + structural policies	Enrichment key-value pairs
3	`enriched-context`	Synthesized	`inherited-context` + `enrich-effects`	Full context for dispatch
4	`policy-effects`	Synthesized	`enriched-context` + resolution/collection policies	edge, drop, reroute, inject, pipe effects
5	`children`	HOAG NTA	`enriched-context` + structural policies	Child scope nodes (materialized on demand)
6	`resolved-aspects`	Synthesized	`policy-effects`, aspect graph, `enriched-context`	Deduplicated aspect list (parametrics evaluated)
7	`guard-set`	Circular	`resolved-aspects` + conditional guards	Converged path set
8	`imports`	Synthesized	`policy-effects` (collection routing)	Import edge IDs for collection data flow
9	`class-modules`	Synthesized	`resolved-aspects` (post-guard) + `policy-effects` (reroute/inject)	`{ nixos = [...]; darwin = [...]; ... }`
10	`local-collection-data`	Synthesized	`resolved-aspects` + collection registry	`{ channelName = [values]; }`
11	`received-collections`	Collection	`local-collection-data` (own + gathered/ascended), collection effects	`{ channelName = [transformed values]; }`
12	`output-modules`	Terminal	`class-modules` + `received-collections` + `enriched-context`	Final module lists

Acyclicity Guarantees

enrich-effects reads inherited-context, never enriched-context — no self-dependency
policy-effects reads enriched-context (already computed) — linear chain
children reads enriched-context and structural policies — produces nodes, doesn't read own children
resolved-aspects reads policy-effects but not guard-set — guards are separate layer
guard-set iterates monotonically over finite domain — bounded convergence
imports reads policy-effects — same linear chain
received-collections reads local-collection-data from OTHER scopes (via import edges), never self — no cycle
output-modules is terminal — reads everything, produces nothing upstream

How Den v2 Wires the Components

let
  # Libraries (fully decoupled)
  genScope = gen-scope { inherit lib; };
  graphLib = gen-graph { inherit lib; };
  bind = gen-bind { inherit lib; };
  schema = gen-schema { inherit lib; };
  aspects = gen-aspects { inherit lib; };

  # Root entity scopes from user declarations
  roots = buildRoots config.den;

  # Aspect type system wired with den's classes + collections
  cnf = {
    classes = config.den.classes;
    moduleArgs = defaultModuleArgs;
    aspectModules = [ neededByModule guardModule constraintModule ];
    metaModules = [ guardMetaModule dropMetaModule substituteMetaModule ];
  };

  # Static inputs (closed over, not demand-evaluated)
  allAspects = config.den.aspects;  # aspectsType cnf
  allPolicies = classifyPolicies config.den.policies;
  collections = config.den.collections;

  # Den-specific attribute definitions
  attributes = {
    inherited-context = genScope.inherit' { resolve = node: node.decls.bindings or null; };
    enrich-effects = ...;
    enriched-context = genScope.circular { init = ...; } ...;  # key-monotonic convergence
    policy-effects = ...;
    children = ...;          # HOAG NTA — produces child scopes from structural policies
    imports = ...;           # computed I edges from collection routing
    resolved-aspects = ...;  # forward expand + neededBy + guards + constraints
    guard-set = genScope.circular { init = ...; } ...;
    class-modules = ...;
    local-collection-data = ...;
    received-collections = genScope.collectionAttr { traverse = "imports"; ... };
    output-modules = ...;    # calls gen-bind.wrap per module
  };

  # ID convention: "type:name@parent" → O(1) parent resolution
  parseParent = id:
    let parts = lib.splitString "@" id;
    in if builtins.length parts > 1
    then lib.concatStringsSep "@" (lib.drop 1 parts)
    else null;

  # Evaluate — demand-driven, tree grows lazily
  result = genScope.eval { inherit roots attributes parseParent; };

  # Output: per-host nixosSystem using gen-bind for module wrapping
  nixosConfigurations = lib.mapAttrs (id: _:
    let
      classModules = result.get id "output-modules" |> .nixos or [];
      ctx = result.get id "enriched-context";
      receivedCollections = result.get id "received-collections";
      wrapped = bind.wrapAll {
        modules = classModules;
        bindings = ctx // receivedCollections;
        defaultMergeStrategy = "bind-wins";
      };
    in lib.nixosSystem { modules = wrapped.all; }
  ) (result.nodesOfType "host");

  # Fleet queries via gen-graph (accessor pattern over gen-scope memoization)
  graphAccessor = {
    edges = id: result.get id "imports";
    nodes = builtins.attrNames (result.nodesOfType "host");
  };
  # Example: "what hosts are affected if db goes down?"
  dbImpact = graphLib.impactOf graphAccessor "host:db-1@env:prod";
in { inherit nixosConfigurations; }

Forward Adapters (Tier 2 Redesign)

Tier 1 forwards are route sugar — reroute { from = "persist"; to = "nixos"; }. Already covered.

Tier 2 forwards (cross-class bridging with adapters) become derived children — nodes whose existence depends on other nodes' evaluated attributes (Vogt's NTA stratification):

attributes.derived-children = self: id:
  # Can read attributes of children-produced nodes (safe — they exist via children)
  let aspects = self.get id "resolved-aspects";
  in if hasForwardAdapter aspects then
    { "adapter:${id}" = wrapChild { ... adapter scope ... }; }
  else {};

Design deferred to implementation. The HOAG model natively supports this via derived-children — see gen-scope HOAG redesign spec.

Library Status

All libraries SHIPPED and DECOUPLED. No gaps remain. Ready for den v2 integration.

Library	Status	Key features
gen-scope	Shipped (145 tests)	True HOAG with `_eval` memoization, selective materialization (subtreeOf, nodesOfType, allNodesWhere), demand-driven tree expansion
gen-graph	Shipped (105 tests)	Accessor-based API, C-level BFS via `builtins.genericClosure`, canReach, dependentsOf, fleet-scale guidance
gen-bind	Shipped (40+ tests)	Merge strategies, lazy contracts (Chitil), provenance (Findler), signature inference (Cardelli), thunk deferral
gen-aspects	Shipped (40 tests)	`cnf.metaModules` hook, identity unification
gen-schema	Shipped (129 tests)	Decoupled (no scope-graph bridge), collections, flat `_`-prefixed introspection
gen	Shipped (40 tests)	Pure primitives (search, record, identity, either)
gen-select	Shipped (163 tests)	Selector algebra: 11 constructors, gen-scope + gen-graph adapters, CSS + SQL WHERE demos
gen-derive	Spec approved	Guarded graph rewrite rules: stratified dispatch, fixpoint convergence, NACs, conflict resolution

Den v2 Implementation Scope

Component	Responsibility	Est. lines
`buildRoots`	Entity declarations → root scope nodes	40-80
Attribute definitions (12)	Context, policy, children, aspects, classes, collections, output	400-600
Policy dispatch	`canTake` classification, effect validation, phase routing	100-150
Aspect subgraph builder	Forward expand + neededBy + guard convergence + constraints	80-120
Collection routing	Gather/ascend/target/channel/source + transform application	150-200
Output assembly	Per-class nixosSystem/darwinSystem/homeManagerConfiguration	60-100
Effect constructors	New vocabulary (spawn, edge, drop, reroute, inject, pipe.*)	80-100
Forward adapter (tier 2)	Cross-class bridging via derived-children	60-100
Migration shims	Old vocabulary aliases, provides→neededBy sugar	40-60
Total		~1,010-1,510

Replaces ~7,000 lines of pipeline code. 4-5x compression.

Performance

Fleet Evaluation Cost Model

Den v2's HOAG model evaluates attributes on demand. Building one host in a 500-host fleet does NOT evaluate all 500 hosts — only what the target host's attribute chain requires.

What forces what when building nix build .#nixosConfigurations.igloo:

output-modules (igloo)
  ├── class-modules (igloo) — igloo's NixOS modules only
  ├── received-collections (igloo) — follows import edges
  │     ├── local-collection-data (igloo) — igloo's own collection values
  │     └── [IF pipe.gather] local-collection-data (source hosts)
  │           └── resolved-aspects (source hosts) — CHEAP, no evalModules
  │               └── enriched-context (source hosts) — CHEAP, just declarations + policies
  └── enriched-context (igloo)

What is NOT forced:

Other hosts' class-modules (their NixOS module lists)
Other hosts' output-modules (their lib.nixosSystem evaluation)
Any host not reachable via import edges from igloo

Three Layers of Laziness

Layer	What's deferred	When forced	Granularity
Host isolation	Other hosts' full NixOS eval	Only when cross-host collections with `config` exist	Per-host
Attribute isolation	Each `(node, attr)` pair	Only when demanded by another attribute	Per-attribute
Collection value isolation	Each source host's collection contributions	Only when the consumer reads that source's data	Per-source-host

Config-Free Collections (Default, Cheap)

Collection values receive entity context ({ host, user, ... }) but NOT NixOS config. Cross-host collection only forces source hosts' aspect resolution — not their lib.nixosSystem evaluation.

# CHEAP: uses only entity declarations, no NixOS config
den.aspects.hostfile = {
  host-addrs = { host, ... }: {
    hostname = host.name;
    addr = host.addr;
  };
};

Config-Dependent Collections (Explicit, Expensive)

If a collection value genuinely needs computed NixOS config (rare — derived IPs, computed paths), use pipe.withConfig to explicitly mark it:

# EXPENSIVE: explicitly marked, forces source host's nixosSystem
den.aspects.derived-addrs = {
  host-addrs = pipe.withConfig ({ host, config, ... }: {
    addr = config.networking.defaultGateway;
  });
};

pipe.withConfig values travel as thunks through collection routing, carrying their source scope ID. Resolution is deferred until the consuming host's evalModules fixpoint — the source host's lib.nixosSystem is forced only at that point.

Fleet Cost Comparison

For a 500-host fleet building one host:

Scenario	Hosts evaluated	What's forced per source	Wall time impact
No cross-host collections	1	Nothing	Baseline
`pipe.gather` matching 10 hosts, config-free	11	Aspect resolution only	Milliseconds
`pipe.gather` all 500 hosts, config-free	501	Aspect resolution only	~1 second
`pipe.gather` all 500 hosts, config-dependent	501	Full `nixosSystem` eval each	Minutes — avoid

v1 vs v2 Comparison

Metric	v1 (fx-pipeline)	v2 (HOAG)
Per-aspect overhead	37 handlers + nix-effects trampoline	1 function call
Dedup	7 checkpoints per aspect per host	1 `seen` set check
Collection assembly	O(all scopes × all pipes) post-pass	O(import edges) demand-driven
nix-effects overhead	Per-effect thunk allocation + trampoline bounce	Eliminated entirely
Cross-host collection	Forces full pipeline per source host	Forces only `local-collection-data` attribute
Host isolation	Pipeline runs independently per host	Natural — `lib.fix` laziness

For 100 hosts × 3 users × 20 aspects: v1 ≈ 118,000 handler invocations with trampoline overhead. v2 ≈ 12,800 direct function calls. ~10x fewer computational steps, each cheaper (no trampoline).

Optimization Guidelines

For den v2 consumers:

Always provide parseParent. Without it, node resolution walks from all roots — O(roots) per synthesized node. With it, O(1). For 500 hosts this is the difference between 500 root checks vs 1 parent lookup per user node.
Keep collection values config-free. Use entity declarations (host.name, host.addr) instead of NixOS config (config.networking.hostName). Most "config" values are actually available as declarations.
Scope pipe.gather predicates narrowly. pipe.gather { host, ... }: true (all hosts) is much more expensive than pipe.gather { host, ... }: host.environment == "prod" (only prod hosts). The predicate determines how many source hosts are forced.
Use pipe.source to limit emitters. pipe.source { host, ... }: host.role == "app" prevents non-app hosts from even producing collection data for that channel.

See also: 2026-05-24-gen-scope-hoag-redesign.md for gen-scope internal optimization guidelines (co-located _eval, wrapChild, Tier 2 allNodes cost).

For NixOS integration:

lib.nixosSystem calls should be in output-modules only. This is the terminal attribute — the LAST thing evaluated. All upstream attributes (context, aspects, collections, classes) should work without forcing NixOS module evaluation. This preserves laziness: building one host doesn't force other hosts' nixosSystem.
Cross-host config access creates evaluation coupling. If host A's output-modules accesses host B's NixOS config (via pipe.withConfig collection values), both hosts' nixosSystem evaluations are coupled. Nix handles this via laziness (B is only forced when A's evalModules demands the thunk), but the wall-time cost is real. Minimize cross-host config dependencies.

Real-World Feature Adoption

Based on audit of 13 external den configs + sini's nix-config:

Feature	Adoption	v2 Priority
Aspects	13/13	Core path — must be perfect
Schema + classes	12/13	Core path
Provides/batteries	11/13	High — desugars to neededBy
den.default	11/13	High
Guards	4/13	Moderate — unchanged mechanism
Policies	3/13	Power-user — extended vocabulary
Forwards	2/13	Low — redesigned as reroute + derived-children
Collections (pipes)	0/13 (1 internal)	Greenfield redesign

Migration Path

No-change configs (10/13): Only use aspects, schema, provides, batteries. These work unchanged — the provides API remains as sugar.
Policy configs (3/13): policy.include → aliased to edge. policy.exclude → aliased to drop. policy.route → aliased to reroute. No code changes required.
Forward configs (2/13): den._.forward → desugars to reroute or tier 2 derived-children. Shim provided.
Collection configs (0 external, 1 internal): Full redesign with new grammar. den.quirks → den.collections. Internal migration only.

Safety Invariants

Bounded Synthesis (Vogt 1989)

In the HOAG model, tree expansion is demand-driven — nodes materialize when children attributes are demanded. Expansion is bounded by:

Entity hierarchies are shallow (flake → environment → host → user, depth ≤ 4)
Each children attribute produces a finite set of child nodes from finite entity declarations
Nix's native "infinite recursion" detection catches genuine cycles exactly

No artificial maxIter bounds needed. The tree is as deep as the demand chain, which is determined by the attribute dependency graph (acyclic by construction).

Well-Formedness Predicate (Neron 2015, Section 2.4)

Valid resolution paths must match P*·I* — once you follow an import edge (I), you cannot follow parent edges (P) from the imported scope.

In den v2: Aspect resolution follows I edges (includes/neededBy). Entity context flows via P edges (parent chain). These never mix in a single resolution query. The WF predicate is satisfied by construction.

Guard-Set / neededBy Stratification

Three layers, each completes before the next:

Layer 1: Forward expand (I edges from includes)
Layer 2: neededBy iteration (reverse I edges, monotone)
Layer 3: Guard convergence (monotone path set, no neededBy re-trigger)

Guard-activated aspects do NOT trigger additional neededBy expansion.

Collection Transform Monotonicity (Arntzenius 2016)

Collection transforms (pipe.filter, pipe.transform, pipe.fold) operate on fully-resolved collection data, outside the guard-set fixed-point. They need not be monotone. The pipe.gather traversal itself IS monotone (scope graph only grows, never shrinks).

Novel Contributions

1. Demand-Driven AG via Language-Native Laziness with Full Memoization

All AG systems in the literature (Kiama, JastAdd, Silver) implement their own evaluation scheduler. Den v2 uses lib.fix + Nix's native laziness. The co-located _eval mechanism achieves O(1) attribute access for ALL nodes (including synthesized) without a global registry — each node carries its own memoization cache, created lazily when materialized. No prior system has achieved full memoization in a HOAG evaluator without explicit scheduling infrastructure.

2. Effect Vocabularies as User-Facing API for Scope Graph Construction

Den v2 exposes graph construction as a user-facing effect vocabulary (spawn, edge, drop, reroute, inject) where users declare intentions and the system builds the graph. No paper combines scope graphs with a user-facing effect vocabulary for incremental graph construction.

3. `neededBy` with Entity-Kind Scoping

Combines reverse edge direction with activation predicate and subtree scoping. A genuinely novel composition mechanism not found in the FOSD, AOP, or AG literature.

4. Constraint Propagation via Scope Graph Ancestors

meta.drop propagates constraints down the include subtree via ancestor/descendant relationships. Neither Neron's import shadowing nor van Antwerpen's type constraints — a constraint system where visibility is determined by graph reachability in a specific direction, applied to feature composition.

5. Three Routing Primitives as Complete Basis for Configuration Dataflow

Local + ascend + gather (plus modifiers: source, target, channel) forms a complete basis for all configuration data routing patterns — validated against 13 external configs and one production fleet config.

Open Questions (Resolve During Implementation)

Forward tier 2 detail. Derived-children adapters running nested evalModules. Silver's forwarding (Van Wyk 2010) provides the formal model. Behavioral reference: forward.nix (202 lines).
Collection config thunk cross-scope resolution. When pipe.gather collects from another host containing config-dependent thunks. Propagator approach (Radul 2009): make cross-host values strict.
provides.to-users desugaring detail. Mapping to neededBy + entity-kind scoping. Scoped neededBy that activates only in descendant entity scopes.
Diagram capture. Adaptation hooks for scope graph + attribute results. Transitive reduction (gen-graph) provides minimal-edge diagram views.
Feature interaction detection. Post-resolution, pre-output: detect duplicate singleton options across composed aspects (Thüm 2014). ~50-80 lines, high user-experience value. Deferred to post-v2-launch.

References

Local copies: ~/Documents/papers/den-architecture/

Core — Attribute Grammars and Scope Graphs

Knuth, D. E. (1968). Semantics of context-free languages. knuth-1968-genesis-attribute-grammars.pdf
Vogt, H., Swierstra, S. D., & Kuiper, M. F. (1989). Higher order attribute grammars. PLDI '89, 131-145. vogt-1989-higher-order-ag.pdf
Hedin, G. (2000). Reference attributed grammars. Informatica, 24(3), 301-317. hedin-2000-reference-ag.pdf
Hedin, G. & Magnusson, E. (2003). JastAdd. Science of Computer Programming, 47(1), 37-58. hedin-2003-jastadd-aspect-oriented-ag.pdf
Neron, P. et al. (2015). A theory of name resolution. neron-2015-scope-graphs.pdf
van Antwerpen, H. et al. (2016). Statix. PEPM 2016. van-antwerpen-2016-statix-constraint-scope-graphs.pdf
van Antwerpen, H. et al. (2018). Scopes as types. van-antwerpen-2018-scopes-as-types.pdf
Van Wyk, E. et al. (2010). Silver. Science of Computer Programming, 75(1-2), 39-54. vanwyk-2010-silver-extensible-ag.pdf
Sloane, A. M. et al. (2010). Kiama. sloane-2010-kiama-ag-embedding.pdf

Algebraic Graphs and Build Systems

Mokhov, A. (2017). Algebraic graphs with class. mokhov-2017-algebraic-graphs.pdf
Mokhov, A. et al. (2018). Build systems à la carte. mokhov-2018-build-systems-a-la-carte.pdf
Arntzenius, M. & Krishnaswami, N. (2016). Datafun. arntzenius-2016-datafun.pdf

Defunctionalization and Inspectability

Palmer, Z. et al. (2024). Intensional functions. palmer-2024-intensional-functions.pdf
Reynolds, J. C. (1972). Definitional interpreters. reynolds-1972-definitional-interpreters.pdf
Lorenzen, A. et al. (2025). First-order laziness. lorenzen-2025-first-order-laziness.pdf

Aspect-Oriented and Feature-Oriented Composition

Kiczales, G. et al. (1997). Aspect-oriented programming. ECOOP '97. kiczales-1997-aspect-oriented-programming.pdf
Batory, D. (2005). AHEAD tool suite. GTTSE 2005. batory-2005-feature-oriented-ahead.pdf
Tarr, P. et al. (1999). N degrees of separation. ICSE '99. tarr-1999-n-degrees-separation.pdf
Apel, S. & Kästner, C. (2009). FOSD overview. JOT, 8(5). apel-2009-overview-fosd.pdf
Thüm, T. et al. (2014). SPL analysis strategies. ACM Computing Surveys, 47(1). thum-2014-analysis-strategies-spl.pdf

Dataflow and Propagation

Kahn, G. (1974). Parallel programming semantics. IFIP Congress '74. kahn-1974-parallel-programming-semantics.pdf
Radul, A. & Sussman, G. J. (2009). Art of the propagator. MIT CSAIL TR-2009-002. radul-2009-art-of-the-propagator.pdf

Open Records and Mixin Composition

Leijen, D. (2005). Extensible records with scoped labels. leijen-2005-extensible-records-scoped-labels.pdf
Bracha, G. & Cook, W. (1990). Mixin-based inheritance. bracha-1990-mixin-based-inheritance.pdf

sini/2026-05-24-den-v2-hoag-architecture.md