Mokhov, Mitchell & Peyton Jones (2018) -- Build Systems a la Carte

The paper

A. Mokhov, N. Mitchell, and S. P. Jones, “Build systems à la carte,” Proceedings of the ACM on Programming Languages, vol. 2, no. ICFP, pp. 1–29, 2018.

doi:10.1145/3236774 · read the paper

This page is our reading of it, not a substitute for it.

Paper Summary

Mokhov, Mitchell, and Peyton Jones observe that build systems — despite being used by every software developer — are rarely studied systematically. Individual systems (Make, Shake, Bazel, Excel, Nix, Buck) are understood as isolated artifacts, each with its own architecture, terminology, and implementation quirks. The paper asks: is there a unifying framework that can decompose any build system into orthogonal components, compare systems by their design choices, and prototype new systems by recombining those components?

The answer is a purely functional, executable framework implemented in approximately 400 lines of Haskell that models any build system as the composition of two independent choices: a scheduler (how tasks are ordered) and a rebuilder (how the system decides whether a task needs re-execution). The framework’s central abstraction is the polymorphic task type Task c k v = Task { run :: forall f. c f => (k -> f v) -> f v }, where c is a constraint (Applicative for static dependencies, Monad for dynamic), k is the key type, and v is the value type. A task description is completely isolated from stores, caches, and schedulers — it only knows how to compute one output given a fetch callback for its dependencies. The constraint c on the functor f classifies tasks: Task Applicative permits static dependency extraction via the Const functor trick (S3.7), while Task Monad enables dynamic dependencies where the identity of a dependency depends on intermediate computation results (S3.5).

Three schedulers are identified (S4.1). Topological (Make, CloudBuild, Buck) pre-computes a linear build order from statically known dependencies, requiring c = Applicative. Restarting (Excel, Bazel) processes tasks in an arbitrary order, aborting and deferring when an out-of-date dependency is discovered. Suspending (Shake, Nix) suspends the currently running task when a dependency is requested, recursively bringing it up to date before resuming — the task “blocks” on its dependency, and the scheduler recurses. The suspending scheduler naturally handles dynamic dependencies and achieves minimality when combined with appropriate traces.

Four rebuilders are identified (S4.2). Dirty bit (Make, Excel) — one bit per key, set when inputs change; supports minimality but not early cutoff. Verifying traces (Shake, Ninja) — record dependency hashes from the previous build; verify by checking if current hashes match; supports dynamic dependencies, minimality, and early cutoff. Constructive traces (Bazel, CloudBuild) — store actual result values alongside dependency hashes in a shared cloud cache; enable downloading pre-built results without local execution. Deep constructive traces (Buck, Nix) — record only terminal input hashes, ignoring intermediate dependencies; enable cloud lookup from inputs alone at the cost of requiring deterministic tasks and losing early cutoff.

The 3x4 matrix of scheduler-rebuilder combinations (Table 2, S4.4) yields 12 possible build systems, 8 of which are inhabited by real systems. Nix occupies the cell (Suspending, Deep Constructive Traces) — it uses lazy evaluation as a suspending scheduler and content-addressed derivations as deep constructive traces. The most interesting unoccupied cell is (Suspending, Constructive Traces), which the authors call “Cloud Shake” and implement in 3 lines by composing the suspending scheduler with the ctRebuilder (S5.4, Figure 10).

Correctness is defined precisely (Definition 3.1, S3.6): after a build, (1) no inputs are corrupted, and (2) every non-input key’s stored value equals what recomputing its task with the final store would produce. Minimality (Definition 2.1) requires executing tasks at most once per build and only if they transitively depend on changed inputs. The framework enables formal reasoning about which scheduler-rebuilder combinations satisfy which properties: topological+dirty-bit (Make) is minimal but has no early cutoff; suspending+verifying-traces (Shake) is minimal with early cutoff; restarting+constructive-traces (Bazel) is not minimal (may restart tasks) but supports cloud sharing and early cutoff.

The paper also addresses engineering concerns (S6): partial stores and exceptions, parallelism (each scheduler has a parallel variant), impure/non-deterministic tasks (modeled via MonadPlus), cloud implementation details (communication, offloading, eviction, shallow builds), self-tracking build systems (where task descriptions themselves are tracked for changes), and iterative/cyclic computations. The connection to self-adjusting computation (S7.2) and memoization (S7.3) is noted — the Levenshtein edit distance example demonstrates that a minimal build system with dynamic dependencies subsumes dynamic programming with memoization, and additionally supports incremental recomputation when inputs change.

Key Concepts

• Scheduler/Rebuilder Decomposition (S4, Table 2). Any build system can be factored into two orthogonal components: the scheduler (topological, restarting, or suspending) determines task execution order; the rebuilder (dirty-bit, verifying-traces, constructive-traces, or deep-constructive-traces) determines whether a task needs re-execution. These compose freely: type Scheduler c i ir k v = Rebuilder c ir k v -> Build c i k v.

• Task Constraint Polymorphism (S3.2, S3.4). The constraint c on Task c k v classifies task descriptions by their dependency structure. Applicative = static dependencies extractable without execution; Monad = dynamic dependencies requiring intermediate computation; Functor = linear chains; MonadPlus = non-deterministic tasks. This classification is not ad hoc — it emerges necessarily from the polymorphism of the fetch callback.

• Static Dependency Extraction via Const (S3.7). For Task Applicative, dependencies can be extracted without execution by instantiating f to Const [k], exploiting the Applicative instance of Const to accumulate keys. This is the mechanism that enables topological schedulers.

• Suspending Scheduler (S4.1.3, S5.3). The suspending scheduler recursively brings dependencies up to date when they are requested, suspending the current task. Combined with a done set to avoid redundant work, this achieves minimality for dynamic dependencies. Implemented via continuation-passing or green threads. Nix’s lazy evaluation is a native suspending scheduler — attribute thunks “suspend” until their dependencies are forced.

• Deep Constructive Traces (S4.2.4, S5.4). Record only terminal input hashes, enabling cloud lookup from inputs alone without building any intermediates. Nix’s content-addressed store derivations are this: a derivation’s output hash is determined by the hashes of all its source inputs (recursively to terminal inputs). Trade-off: requires deterministic tasks and cannot support early cutoff at intermediate levels.

• Correctness Definition (S3.6, Definition 3.1). Formal specification: inputs unchanged, non-input values consistent with task recomputation against the final store. Extended for non-determinism (S6.3: result must be one of the possible outputs) and shallow builds (S6.4: only target key and inputs must match a hypothetical correct full store).

• Minimality (S2.1, Definition 2.1). A build system is minimal if it executes each task at most once per build and only when the task transitively depends on inputs that changed since the previous build. Not all correct systems are minimal (Bazel’s restarting scheduler may execute a task multiple times).

• Self-Tracking (S6.5). Build systems that detect changes to task descriptions themselves, not just inputs. Modeled as tasks depending on a key representing their own formula. Excel and Ninja support this; most software build systems do not.

• Memoization Subsumption (S7.3). A minimal build system with dynamic dependencies subsumes memoization (demonstrated via Levenshtein edit distance as Tasks Monad), and additionally provides incremental recomputation — an optimization memoization alone cannot achieve.

Implementation Mapping

Current Usage in Gen Ecosystem

gen-scope (Minor — architectural foundation recognized, not directly implemented)

The paper’s classification of Nix as occupying the (Suspending scheduler, Deep Constructive Traces) cell in Table 2 informed a critical architectural insight for gen-scope: Nix’s lazy evaluation is not merely “similar to” a suspending scheduler — it IS a suspending scheduler in the formal sense of S4.1.3. When gen-scope’s result.get "host:igloo" "region" forces an _eval thunk that depends on another node’s attribute, Nix suspends evaluation of the current thunk, recursively evaluates the dependency, and resumes. This is exactly the suspending scheduler from Figure 9:

suspending rebuilder tasks target store = fst $ execState (fetch target) (store, Set.empty)
  where
    fetch key = do
      done <- gets snd
      case tasks key of
        Just task | key `Set.notMember` done -> do
          ...
          newValue <- liftRun newTask fetch  -- fetch recurses: dependency is "suspended"
          ...

The done set that prevents redundant work in the paper’s suspending scheduler corresponds to gen-scope’s _eval memoization: once a thunk is forced, Nix caches the result, and subsequent accesses return the cached value without re-evaluation. The paper’s abstract fetch callback is gen-scope’s self.get id attrName. The paper’s Task is an attribute equation self: id: value.

gen-scope does NOT implement the rebuilder dimension. There is no persistent trace store, no dirty-bit tracking, no cross-build incrementality. Each nix-instantiate or nix eval evaluation is a fresh build from scratch — the “store” is empty at the start of every evaluation. Nix’s content-addressed store provides some build-level caching (derivation output hashing), but gen-scope operates entirely within a single evaluation, where the only “trace” is Nix’s native thunk memoization.

• Files: eval function in gen-scope (scheduler = Nix lazy evaluation), _eval co-located cache (rebuilder = not applicable, single-evaluation model)
• Mapping: Paper’s suspending scheduler (S4.1.3, S5.3, Figure 9) = Nix lazy thunk evaluation; Paper’s done :: Set k = Nix thunk memoization (forced thunks cached); Paper’s fetch callback = self.get; Paper’s Task = attribute equation self: id: value

gen-algebra (Minor — conceptual parallel)

The search monad’s converge function (Palmer 2024 S3) is structurally similar to the paper’s iterative computation pattern (S6.6): iterate until a fixed point, with a bounded iteration count as safety guard. The paper notes that build systems rarely support cyclic dependencies but cites Pottier (2009) and Radul (2009) for monotonic fixed-point computation frameworks. gen-algebra’s search monad operates in this space — monotonic index accumulation with convergence detection — though it derives from Palmer rather than from this paper directly.

Relevance to Den v2 HOAG Pipeline

The Build Systems a la Carte framework provides the classification vocabulary for understanding den v2’s evaluation architecture:

Paper concept	Den v2 realization
Suspending scheduler (S4.1.3)	Nix lazy evaluation — attribute thunks suspend/resume on dependency access
fetch callback	self.get id attrName in gen-scope
Task c k v	Attribute equations self: id: value
c = Monad (dynamic deps)	Attribute bodies can conditionally access different attributes based on intermediate values
done set	_eval memoization — each thunk evaluated at most once
Deep constructive traces (S4.2.4)	Nix store derivation output hashing (at build level, not within gen-scope evaluation)
Correctness (Definition 3.1)	AG well-formedness: attribute values consistent with their defining equations against the final tree
Minimality (Definition 2.1)	Demand-driven evaluation: only attributes actually accessed are computed
Early cutoff (S2.3)	Not applicable within single evaluation; at Nix store level, content-addressed outputs provide cutoff

The paper’s key insight for den v2 is that the suspending scheduler is the most powerful: it handles dynamic dependencies, achieves minimality, and composes with any rebuilder. Nix’s lazy evaluation provides this for free. The gen-scope architecture exploits this by defining attributes as pure functions and letting Nix’s evaluator schedule their computation. No explicit topological sort, no restarting with aborts, no calc chain — just recursive thunk forcing.

The rebuilder dimension is where future work lies. Currently den v2 has no cross-evaluation incrementality: every nix eval recomputes everything from scratch. The paper’s trace taxonomy (verifying, constructive, deep constructive) provides a roadmap for adding incrementality. The natural fit would be verifying traces (Shake-style): record which attributes were accessed and their content hashes, and on re-evaluation, skip attribute computation when all dependencies have unchanged hashes. Combined with the existing suspending scheduler, this would place den v2 in the (Suspending, Verifying Traces) cell — the Shake cell — achieving minimal, incremental, early-cutoff-capable attribute evaluation.

Appendix: Follow-up Work

Unexploited Ideas

• Verifying traces for attribute-level incrementality (S4.2.2, S5.3). The paper’s vtRebuilder records dependency hashes after each task execution and skips re-execution when hashes match. Applied to gen-scope, this would mean recording which _eval entries were accessed during attribute computation and their content hashes, then on re-evaluation checking if the hash of each dependency still matches. This is the core mechanism for incremental AG re-evaluation — the missing rebuilder dimension in gen-scope.

• Constructive traces for attribute caching across evaluations (S4.2.3, S5.4). Beyond verifying “is this still valid?”, constructive traces store actual results indexed by dependency hashes. For gen-scope, this would mean a persistent attribute cache: given the same scope graph structure and the same input declarations, attribute values can be looked up rather than recomputed. This extends Nix’s derivation-level content-addressing down to the attribute level.

• Self-tracking for aspect change detection (S6.5). The paper models self-tracking as tasks depending on their own formula. In den v2, this would mean detecting when an aspect definition changes (not just its inputs) and selectively re-evaluating affected attributes. Currently, any change to any aspect triggers full re-evaluation. Modeling aspect definitions as hashable inputs to the attribute computation would enable targeted invalidation.

• Early cutoff at the attribute level (S2.3, S4.2.1-4.2.2). When an attribute is recomputed and produces the same value as before, dependents need not be recomputed. gen-scope’s _eval provides no cutoff — once a thunk is forced, all downstream thunks that reference it will be forced regardless of whether the value changed. Implementing attribute-level early cutoff would require explicit hash comparison after computation, matching the paper’s description of Shake’s mechanism (S5.3, vtRebuilder).

• Task constraint classification for static analysis (S3.4, S3.7). The paper’s Applicative/Monad distinction enables static dependency extraction for applicative tasks. In gen-scope, most attributes are monadic (they conditionally access different dependencies), but some are purely applicative (e.g., inherit' always walks the parent chain regardless of values). Identifying applicative attributes would enable static dependency graph construction for those attributes, supporting pre-computation of evaluation order and parallel evaluation.

Potential New Libraries or Features

• gen-trace — Attribute-level verifying traces. A library that wraps gen-scope’s eval to record dependency hashes during evaluation and provides a verify function that checks if cached attribute values are still valid. Architecture: intercept self.get calls to record (sourceId, sourceAttr, hash) tuples; persist traces to a JSON/Nix file; on re-evaluation, verify traces before forcing thunks. Scope: moderate — requires instrumenting gen-scope’s accessor chain without breaking laziness. Interaction: gen-scope provides the evaluation substrate; gen-trace adds the rebuilder dimension. Combined, they place the system in the Shake cell (Suspending + Verifying Traces).

• gen-scope applicativeAttr combinator. An attribute constructor that guarantees Applicative-only dependency access, enabling the Const [k] dependency extraction trick from S3.7. The combinator would take a list of dependency declarations and a pure function, rather than a self: id: callback. Scope: small — a restricted attribute constructor with static dependency metadata. Interaction: enables pre-computation of partial evaluation orders, static cycle detection without evalDebug, and potential parallel evaluation of independent applicative attributes.

• Incremental eval for gen-scope. An evalIncremental variant that takes a previous evaluation result and a set of changed node IDs, and returns a new result that only recomputes affected attributes. Implementation would combine verifying traces (to detect which attributes are invalidated) with the existing suspending scheduler (to recompute on demand). Scope: large — requires persistent trace storage, invalidation propagation, and careful interaction with _eval memoization. Interaction: the primary consumer (den v2) would benefit from sub-second re-evaluation when a single aspect changes in a large fleet configuration.

Research Directions

• Optimal trace granularity for Nix-embedded AGs. The paper’s trace taxonomy (verifying, constructive, deep constructive) applies at the task/key level. In gen-scope, the “task” is an attribute equation and the “key” is a (nodeId, attrName) pair. The question is: what is the right granularity for traces? Per-attribute traces give maximal incrementality but high storage overhead. Per-node traces (invalidate all attributes when any input to the node changes) are coarser but cheaper. Per-subtree traces (invalidate at the scope-graph subtree level) align with den v2’s entity boundaries. The trade-off space has not been characterized for lazy-evaluation-embedded AGs.

• Content-addressing as deep constructive traces. Nix already provides deep constructive traces at the derivation level: a derivation’s output is determined by the recursive hash of all terminal inputs. Can this mechanism be extended inward, to attribute-level caching? If an attribute’s value is a function of (a) the scope graph structure hash and (b) the declaration content hashes, then the attribute value could be looked up in a content-addressed cache without re-evaluation. This would fuse gen-scope’s evaluation model with Nix’s store model, potentially enabling cross-evaluation attribute sharing.

• Suspending scheduler with non-deterministic tasks for policy dispatch. The paper models non-determinism via MonadPlus (S6.3). In den v2, policy dispatch through gen-derive produces non-deterministic effects (multiple rules may fire, producing different action sets depending on evaluation order). The paper’s correctness definition for non-deterministic tasks (S6.3: getValue k result \elem` computeND task result`) could formalize what it means for den v2’s policy dispatch to be “correct” — the final configuration must be one of the possible results of the non-deterministic task, regardless of rule firing order.

• Self-adjusting computation bridge (S7.2). The paper notes the deep connection between build systems and self-adjusting computation (Acar et al. 2002, 2007). The gen ecosystem’s fixpoint loops (gen-algebra converge, gen-scope circular, gen-derive fixpoint) are all instances of self-adjusting computation within a single evaluation. The question is whether the incremental/adaptive computation literature provides algorithms that can be applied to gen-scope’s evaluation model to achieve sub-linear re-evaluation cost when inputs change incrementally, beyond what trace-based rebuilders provide.