Hacker News Reader

Comment by jgeada | Hacker News Reader

Maybe I'm a dinosaur, but if the product you're building is so complex that it needs such a complex (and Turing complete!) description for how it needs to be built, maybe the problem is that product's architecture. Creating a meta build is fixing the symptom and not the problem.

Yes, it is unfortunate that "make" syntax is a bit odd. But if you can't describe the hierarchical DAG for how your product comes together, that ought to be the problem to tackle rather than building a Turing complete language to try to describe how you think maybe your product might come together.

View on HN

Ideally, a build system should be just a simple, declarative thing: here is the list of the files that need to be compiled, go do it. But the simple declarative tends to fail when you start getting to complex logic.

Things start out with a simple "oh, we need to do completely different things on different OSes. Compile only these files on Linux and these on Windows." Then, oops, we also have a feature that requires a long build time that half our developers don't want to build (also it's unstable and has a nasty dependency or something), so only build this files when this feature is enabled.

Then something gets complex and you now have part of your source code being autogenerated from some tool that needs to be built as part of the build. And the autogenerator needs to use the support library. And someone complains about the speed of the debug build, so the autogenerator needs to be built with optimizations enabled even when the rest of the program is disabled. And then cross-compilation is now more of a headache...

I haven't even touched on so many other possible complexities in the build system (autodownloading dependencies is another fun one). The point is that the idealized, simple, declarative build system only cuts it like 60% of the time (even that requires some level of conditional compilation which make can do but not nicely). At the upper end, you're going to need some complex logic to handle complex cases, and not providing some form of general-complexity features to achieve those cases is going to result in people trying to emulate them using existing features--ironically probably making it more complex as a result.

Giving users the ability to have Turing-completeness in their build system doesn't necessarily mean the buildsystem has to devolve into incomprehensiblity. I've come to like Mozilla's meta-build system in this regard, for example, this relatively complex build file: https://searchfox.org/mozilla-central/source/browser/app/moz...

>so many other possible complexities

This right here. When working with large enterprise clients I'm seeing insanely complex build chains.

Artifactories hosting all the built/allowable dependencies/binaries allowed in the customers software. Systems that check the added dependencies and verify any newly added dependencies match the allowed licenses for the application being built. Static checkers of different types. Open source analysis, dll version security analysis, SBOM, and more. Checks to see if enough build system servers are up and running at the time or if the job needs delayed. Seemingly continuous integration has swept this type of customer and the complexity of the build system to allow this has exploded.

Simple declarative models are great until they ... Aren't.

Essentially you have a DSL. A DSL can be great if you use it frequently enough to know the insurance and outs. Like SQL.

But a build DSL is something you muck with like ... Once every six months? And most build files I one off rather than write from scratch. I'm not going to o learn your DSL. I'm going to stack overflow it.

And build systems no matter how genius prescient the authors are, do weird things sometimes. Integrate with so e proprietary library? Have a required code generation step? Pull a dependency from a weird location? Auto annotate code?

Alas then you have to either be able to decompile the DSL to the base lang.in your head, or inject some "real code".

And ... By the standards of this article when dealing with the problem of building code (which, come on, evolves to a workflow engine eventually, and not a simple one) becomes meta.

Yup. This is the difference between computer science and software engineering. Build systems in the real world have to be resilient in all sorts of crazy scenarios.

I suspect that you can describe pretty muich all builds without turing completeness, but avoiding it is rarely particularly helpful. What you need is a language that has a reasonable amount of expressiveness to describe modules and how they fit together, including whatever decisions you need to allow for a) build configurations and b) dealing with platform variations. It's a lot easier to express this in a turing complete language than a non-turing complete language, and it's hard to make a non-turing-complete expressive enough without accidentally making it turing complete.

The reason make is not particularly great for writing a build system in is the language is pretty arcane, and it has annoying restrictions which make certain things particularly difficult to deal with (Spaces in filenames!). The fact that it's not turing complete is not really the key reason in my mind to use something like cmake instead. But, if you were to try to turn make into something that's more flexible and easier to use, you'd be making a lot harder on yourself if you still wanted to avoid turing completeness.

I have made a (internal only unfortunately) meta build system for my work. Instead of being Turing complete is uses Horn Clauses as the primary mode of logic. This means that the problem of determining "is this compiler flag set" or "is this file used in this build" is always solvable in polynomial time.

It has been in use for over ten years by multiple teams around the world for all sorts of whacky toolchaims and projects.

I don't believe anyone has missed Turing completeness.

Despite all that, I agree that if you need a metabuild system then things are probably too complicated. I guess the main reason I would argue for one is when building a cross platform thing, it is nice if developers using toolchain X don't need to modify build files for all the toolchains that aren't X - making Linux developers have to fight Visual Studio just to add a new file to a build is not ideal. But in principle - I still agree that the resulting question of "how do I build this thing from scratch?" Should probably be answerable in 2 sentences (e.g. "Compile and link all the C files with the top level directory in the include path. Don't compile files that have an operating system in their name unless you are building for that os")

Interesting. Can you give some details what you did there. What exactly is a horn clause modeling here?

Horn clauses just mean you can have a whole bunch of things saying "if x then y is true" where X is constrained to be a monotonic (i.e. no negation) Boolean function (i.e. OR and AND).

Given some starting known true values in the system (e.g. debug_build=true, platform_is_windows=true, build_curl_library=true) you solve to find the minimum set of other variables that need to be true.

Each variable can then have some effects tied to it (e.g. if build_curl_library is true, then make sure curl.c is compiled and curl/include is in the include path)

Being Horn Clauses, the solving is basically a flood fill - as soon as you know a variable is true, it is locked in as true. If there was negation, then you can have weird contradictions and reasoning about the system starts being really difficult.

Aren't Horn clauses enough to make a language Turing complete?

No, it is just a finite set of variables. The problem being solved is "given a known set of variables that are true, find the minimal set of other variables that need to be true" and this is basically a flood fill algorithm.

Could you elaborate on the "find the minimal set of other variables that need to be true" part? What other variables are you referring to? "need to be true" for what exactly?

The user of the build system defines boolean variables for any aspect of the build system that they think might be helpful. There are booleans for types of compiler flags (e.g. should I include debug symbols?) and booleans for specific chunks of code (e.g. should I build the unit test code) and booleans for how the thing is being built (e.g. am I building for linux? am I writing a makefile?)

The build system is then able to figure out a starting set of booleans which must be true (e.g. "I am writing the makefiles for the unit test project so it builds on linux in a debug build"). This translates into some starting assignment of boolean values to the boolean variables.

However, it is most likely, that this assignment will not satisfy every horn clause. For example: "if (debug build) then (include debug symbols = TRUE)" might be a clause, and so known that we have a debug build implies we need to set our boolean for including debug symbols to be true (we can break this out so we can then easily have things like optimized builds with debug symbols). Then once you know that you have debug symbols, we might have a clause like "if (debug symbols AND compiling with gcc AND writing a makefile) then (<magic side effect goes here>)"

Similar stuff happens for dependencies. If some code uses the maths library, then the place where the magic side effect says "add this file to the list of files being compiled" will also have a "link with maths library = TRUE" part to it, so then anyone who sets the boolean to get that file, will magically also be told that they need the maths library, and some other part of the system will be responsible for figuring out what that means (e.g. adding "-lm" to some makefiles)

The syntax for it is all simplified down so it doesn't really look like you are doing boolean arithmetic everywhere, but the semantics are mostly what I'm describing.

Now I understand, thanks so much! :)

Sure, you can avoid it. But I bet if it was turing complete you would not suffer for it either.

And the answer to 'how to build this' should be answerable by "run build_system". Any further details represents a failure of the build system (what you describe of having multiple build systems for each platform/IDE is especially hellish). Even a relatively small amount of code is likely to have details the matter beyond just 'compile and link'. Especially in embedded, where even if the codebase is all the code that's running on the system (no external libraries), it's far from trivial to actually get a working binary just by invoking the compiler.

Actually, Turing completeness would make it worse. This system means that when you pull in things from multiple places and multiple teams, the interactions between the different things would be really trivial to understand. e.g. if you want to know "why is this preprocessor macro being set?" then the tooling can tell you exactly why - even if the answer spans multiple modules from different teams. But the other side effect was that people tended to not do anything crazy or even just different (compare with the whole find_package business in cmake where different packages do things in different ways and frequently have conflicting compile/link requirements)

I am very familiar with embedded stuff, and this whole system was built precisely because of that. Some people are developing in visual studio so give them a good visual studio project that works well, some are working with a proprietary garbage toolchains, so you need to let them write makefiles and have enough flexibility to let them encode how to do that in the build system (e.g. all the different quirks you get for figuring out header file dependencies). The policy I used was "every toolchains needs some lowest common denominator support" and then "once you have that, let every toolchains be as good as possible with equivalences given abstractions". It did appear to work.

I think you may have misinterpreted me on the multiple build system thing. There is one build system and it produces files that each ide/toolchains can work with. So it can make xcode, visual studio, makefile, etc. No one edits those by hand, just like cmake, gyp, etc

I want everything declarative, and mostly things are. However I keep running into something weird that the build system designers didn't think of and so I need something to make it work. Note that I'm the cmake expert here, so when I say I keep running into these situations understand that most of the other developers never hit these things, but when it happens they go to me and so I run into them often even though they are rare.

Build systems do more than just build files. They find and run tests, analyze test results, analyze coverage. Conditionally generate code based on whether a feature is enabled or disable. Run "find dependency" logic. Read pkgconfig files.

Author here.

My go-to example is multi-language builds. Those get complex, and sometimes, multiple languages are necessary.

I've designed and shipped more than one multi-million line of code product that had parts in C, C++, Fortran, Python, Tcl, and even some assembly, plus the usual grab bag of open source dependencies. For none of those was anything more sophisticated than (admittedly fairly complex) hierarchical Makefile description to make it come together.

I'll be the first to admit that I've not seen it at all, but color me suspicious that it is an inherent problem of builds of a multi-language product, rather than unknown/unnecessary complexity in the architecture of the system being built.

Recursive Make isn't the best. https://aegis.sourceforge.net/auug97.pdf

That said, if Rig gives you nothing new, please don't even try it!

I'd rather you wait until you need it to try it; then you'll be more forgiving of the bugs. :)

There is something very fishy in that article: the order of traversal in a hierarchical make should be entirely expressed by dependency rules, not mere existence of a directory. Failure to describe dependencies is a flaw in the creation of the Makefile, not an inherent property of make itself.

Specifically, this idiom:

  all:
  for dir in $(MODULES); do \
    (cd $$dir; ${MAKE} all); \
  done

should be banished from everyone's Makefiles. make isn't a just way of cobbling together some collection arbitrary collection of scripts. Each of those modules should be a target with dependencies. The rule to make that module is the recursive make. But the order is determined by the explicit dependencies, not whatever random order glob gives you. ie, what you should have is:

  module1:
     (cd $module1_dir; make)

  module2: module1
     (cd $module2_dir; make)

etc etc etc

Every single time in my career that I've had someone complain about a flaw in make, what I discover is a significant flaw in their description of the make rules. If it is not behaving correctly, you did not fully describe the DAG.

> Every single time in my career that I've had someone complain about a flaw in make, what I discover is a significant flaw in their description of the make rules. If it is not behaving correctly, you did not fully describe the DAG.

You can look at the dependency graph in two ways. The first is, in order to build X, you first need to build Y and Z. These kinds of dependencies tend to be relatively easy to figure out. The second way is to ask, if Y changes, what needs to be rebuilt--and these kind of rebuild dependencies aren't going to be correct unless they're autogenerated, and getting autogenerated dependencies done correctly is challenging. (This basically reaches the point in the article that any system that doesn't support dynamic dependencies ends up hacking its way to support for dynamic dependencies).

The other key point I will make is that, while it can be possible to describe the DAG you want with make, it tends to fight you every step in the way. If almost everyone is complaining about how hard it is to get the DAG correct in make, then maybe the problem isn't that everyone can't figure out how to fully describe the DAG, it's that make isn't a good option for specifying the DAG.

file modtime-based dependencies is enough to kill any interest in make I might have had. When I update my working copy from version control to an earlier version to look at how things used to work, but the modtime is later, make does the wrong thing.

What if my product is not an executable, but a root filesystem?

Reply on news.ycombinator.com