The Theory of Build Systems

Build System vs. Scripting

Ever asked yourself why people use build systems? Well, I did, and came to some interesting conclusions. One of the first build systems was likely ancient make and its many derivatives. Later we got ant with more derivatives. The goal of all of them is to organize the tasks for building a software system from sources. This includes downloading libraries, compiling sources, compiling documentation, checking out and possibly in of version control systems, packaging, uploading, advertising. What would you say if someone asks you to organize these task for a certain software system by means of your favorite scripting language, instead of using, say, ant?

I am pretty sure that you would say: "Hey, no problem!" We can formulate all those individual task in nearly every scripting language. Then just string them together and we are done. Why would anyone want a build system? What does it provide over plain scripting?

Looking at ant and make it is easier to spot what they don't provide: decent scripting? On the other hand, they provide two related features that go beyond normal scripting.

1. Methods that run at most once.
2. Methods that run only if necessary.

When I say method here, you may read task. The following discussion will show that and how the two are closely related. In the list, you may be missing dependencies, but we will see that this is not a differentiating feature.

One Shot Methods

Compare an ant task with a method or function you may write in a scripting language. During one invocation of the build script, a task is only ever evaluated once. If it is called a second time, it is simply skipped, because it was done already. A function or method, on the other hand, is performed every time it is called.

Is this feature important for a build system? Well, it depends on how you look at it. Given that the typical task during a build is idempotent, i.e. repeating application always yields identical results, this feature is not needed from a functional perspective. It is only an optimization, and it depends on the complexity of the build process whether the optimization is really necessary.

Guarded Method Evaluation

Another of the key features of make is that it compiles source code only if it is newer than the resulting object file or if the object file is missing. Put another way: the task of compiling the source code is only performed after testing whether this is really necessary.

Again we can ask the same question: is this feature important for a build system? And the question is the same as above. No, not for proper semantics of the build system. Assuming again idempotence of build tasks, functionally there would be no harm to simply perform all tasks during a build, not just the necessary ones. Interestingly, when compiling Java sources, there is almost no test that correctly determines for all situations whether it is necessary to compile that is more efficient than the compilation itself.

For completeness it should be mentioned that one shot methods are themselves only an optimization of guarded method evaluation. Instead of performing the test that guards a method, the build system keeps track of the methods that were already run. In principle it could just run the test again.

Why then a build system?

If the features that differentiate a build system from a script language are mere optimizations, do we really need them then. Computers get ever faster, and whoever once tried to debug either a broken makefile or hunted after an astray classpath in an ant script may wonder why not just formulate each task of the build process as a method in the favorite script language and run them all in turn. If you think dependencies are cool, just model them with method calls. You may end up letting the computer do a bit too much, but who cares? The benefit is, that it is much easier to write most tasks in a scripting language, and it is easy to grasp what happens during the build process. Just follow the method calls.

Nearly convinced to ditch ant and string together a few lines of bash, Python, Tcl, Ruby, or Groovy? Then lets make a point for the guarded method evaluation and then derive a list of requirements for a simple but effective build system on top of the scripting language of choice.

The Case for Guarded Method Evaluation

The author must admit that this does not come easily. Partly the arguments are driven by the fact that there must be something important of build systems just because so many people use them and nobody uses the pure scripting approach. But anyway, here are the points.

Performance: Ok, there are build processes out there that would take ages without guarded method evaluation. Preventing completely unnecessary computations is a Good Thing.

Prevent polynomial explosion: Consider a task that involves a nested pair of loops. Inside the inner loop, a dependency is declared, i.e. another task is called. Obviously this task is run a quadratic number of times, if its evaluation is neither guarded by a test nor is implemented as one shot. Here the case of performance optimization starts to become important.

Understandability: Personally I always considered it helpful to follow which tasks make performed after I changed some source. This was somehow lost when I started working with ant, because it seems that many tasks don't contain proper guards and are always performed anyway.

You name it: I would be interested in more arguments to go here.

Build System Requirements

As a conclusion from the discussion above, my first and foremost requirement is:

1. Use a trusted and tested scripting language.

Don't invent a half baked broken one, and in particular don't confuse XML with a programming language.

2. Provide for guarded method evaluation.

Basically this means that a task to be performed during the build process can be modelled by a pair of a worker method and a guarding test. Before the method is run, the test is performed. Only if the test indicates that it is still necessary to perform the task, the method is run.

The build system may and probably should store the result of the test and not even run the test again, if the task is invoked another time during the same build process. The assumption is, as mentioned, that tasks are idempotent.

Another helpful feature would be to provide the test of a task with all the test results of dependent tasks. Usually a task must be performed, if one of the dependent task had to be performed. This is a generalization of make's feature were tasks triggered each other due to the fact that their target artifacts were freshly made and therefore newer than target of the next task.

There is but one feature that was not yet talked about, which also differentiates a build system from a pure scripting language. It is a rather practical aspect: a library of idioms or functions regularly needed during a build process. Lending from ant as an example, at least filesets come to mind.

3. Provide helpful library of task.

Not worth mentioning in this category, I feel, are ant's abstractions of calls to programs like javac, jar, etc. They just introduce another syntax for these programs with dubious benefit.

We see that the requirements are quite simple and the first two can easily be accomplished in a few lines of code. Why then do build systems grow into arcane beasts like make and ant?