Zb: An Early-Stage Build System

And actually, if you take the view that build systems are a form of staged programming, then all build systems are monadic because the first stage is building the graph at all, and the second stage is evaluating it. Make, for example, has to parse the Makefiles, and during this phase it constructs the graph... dynamically! Based on the input source code! Rather it is during the second phase done later, when rules are evaluated, and that is now the time when the graph is static and all edges must be known. See some notes from Neil Mitchell about that.[1]

The other key is in a system like Buck or Bazel, there are actually two graphs that are clearly defined. There is the target graph where you have abstract dependencies between things (a cxx_binary depends on a cxx_library), and there is the action graph (the command gcc must run before the ld command can run).

You cannot have dynamic nodes in the target graph. Target graph construction MUST be deterministic and "complete" in the sense it captures all nodes. This is really important because it breaks features like target determination: given a list of changed files, what changed targets need to be rebuilt? You cannot know the complete list of targets when the target graph is dynamic, and evaluation can produce new nodes. That's what everyone means when they say it's "scalable." That you can detect, only given a list of input files from version control, what the difference between these two build graphs are. And then you can go build those targets exactly and skip everything else. So, if you make a small change to a monumentally sized codebase, you don't have to rebuild everything. Just a very small, locally impacted part of the whole pie.

In other words, "small changes to the code should have small changes in the resulting build." That's incremental programming in a nutshell.

OK, so there's no target graph dynamism. But you can have dynamic actions in the action graph, where the edges to those dynamic actions are well defined. For example, compiling an OCaml module first requires you to build a .m file, then read it, then run some set of commands in an order dictated by the .m file. The output is an .a file. So you always know the in/out edges for these actions, but you just don't know what order you need to run compiler commands in. That dynamic action can be captured without breaking the other stuff. There are some more notes from Neil about this.[2]

Under this interpretation, Nix also defines a static target graph in the sense that every store path/derivation is a node represented as term in the pure, lazy lambda calculus (with records). When you evaluate a Nix expression, it produces a fully closed term, and terms that are already evaluated previously (packaged and built) are shared and reused. The sharing is how "target determination" is achieved; you actually evaluate everything and anything that is shared is "free."

And under this same interpretation, the pure subset of Zb programs should, by definition, also construct a static target graph. It's not enough to just sandboxing I/O but also some other things; for example if you construct hash tables with undefined iteration order you might screw the pooch somewhere down the line. Or you could just make up things out of thin air I guess. But if you restrict yourself to the pure subset of Zb programs, you should in theory be fine (and that pure subset is arguably the actual valuable, useful subset, so it's maybe fine.)

[1] https://ndmitchell.com/downloads/paper-implementing_applicat...

[2] https://ndmitchell.com/downloads/slides-somewhat_dynamic_bui...

Please do not give into the temptation to just write a version manager and stitch together some hodgepodge and throw the hard problem over the fence to the "community", a set of balkanized repositories to make everything work. It is really really really hard to overstate how much value Nixpkgs gets from going the monorepo route and how much the project has been able to improve, adapt, and overcome things thanks to it. It feels like Nixpkgs regularly pulls off major code-wide changes on an average Tuesday that other projects would balk at.

(It's actually a benefit early on to just keep everything in one repo too, because you can just... clean up all the code in one spot if you do something like make a major breaking change. Huge huge benefit!)

Finally: as a die hard Nix user, I also have been using Buck2 as a kind of thing-that-is-hermetic-cloud-based-and-supports-Windows tool, and it competes in the same space as Zb; a monorepo containing all BUILD files is incredibly important for things to work reliably and it's what I'm exploring right now and seeing if that can be viable. I'm even exploring the possibility of starting from stage0-posix as well. Good luck! There's still work to be done in this space and Nix isn't the final answer, even if I love it.