Comment by aseipp

Buck2 can express dynamic dependencies, so it can capture dynamic compilation problems like C++ modules, OCaml/Fortran modules, etc. in "user space" without built-in support like Bazel requires. The secret to why is twofold. One, your internal build graph can be fully dynamic at the implementation level; rather, it's a matter of how much expressivity you expose to the user in letting them leverage and control the dynamic graph. Just because you have a Monad, doesn't mean you have to have to expose it. You can just expose an Applicative.

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...