In a recent blog post, I shared a preliminary version of the paper on build systems that Neil Mitchell, Simon Peyton Jones and I submitted to the ICFP 2018 conference. The paper was accepted and yesterday, after months of revisions and polishing, we’ve finally completed this work. The paper and associated executable models are openly available; here is a direct link to the PDF.

Build systems, such as classic Make, are big, complicated, and used by every software developer on the planet. But they are a sadly unloved part of the software ecosystem, very much a means to an end, and seldom the focus of attention. Rarely do people ask questions like “What does it mean for my build system to be correct?” or “What are the trade-offs between different approaches?”. For years Make dominated, but more recently the challenges of scale have driven large software firms like Microsoft, Facebook and Google to develop their own build systems, exploring new points in the design space. In this paper we offer a general framework in which to understand and compare build systems, in a way that is both abstract (omitting incidental detail) and yet precise (implemented as Haskell code).

As one of our main contributions we identify two key design choices that are typically deeply wired into any build system: (i) the order in which tasks are built (the scheduling algorithm), and (ii) whether or not a task is (re-)built (the rebuilding strategy). These choices turn out to be orthogonal, which leads us to a new classification of the design space, as shown in the table below.

We can readily remix the ingredients to design new build systems with desired properties: the spot marked by X is particularly interesting since it combines the advantages of Shake and Bazel build systems. Neil is now working on implementing this new build system — Cloud Shake.

Read the paper, it’s fun. We even explain what Frankenbuilds are 🙂