A build graph that rolls dice

Dynamic derivations make Nix’s build graph generative: instead of declaring every derivation up front (an applicative model), steps can emit new derivations as the build runs (a monadic model). The write-up contrasts apply vs bind to show why a monadic scheduler can’t produce a complete graph before execution. Nix already used bind in the evaluator (import-from-derivation), but dynamic derivations move that bind into the scheduler, letting builders spawn further .drv files that the scheduler can run, cache, and distribute. A concrete example (chain.nix + step.sh) rolls a d6 at each step; rolling a six produces a terminal derivation that writes the depth, otherwise the builder writes a passthrough derivation that imports chain.nix for depth+1. Only the initial derivation exists at instantiate time and builtins.outputOf can still be used, but dry-run and nix-store queries cannot see the expanding graph while the build runs.

Empirically, running the dice-chain 900 times produced a geometric-like distribution (mean ~6.18, median 4, max observed 46, contrived runs up to 500), illustrating unbounded frontier growth until a stopping condition. The key consequences are practical: an entirely new, post-build graph appears that current tooling can’t introspect, and many novel uses become possible - on-the-fly game emulation, state-space search or model checking, targeted fuzzing, and link crawling - because the frontier is discovered rather than predeclared. The author flags open questions about limits, safety, and how to reason about builds that are invented as they run.