4 ms·

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

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.

TheNewAndy 3y ago
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")
- rcxdude 3y ago
  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.
  - TheNewAndy 3y ago
    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
- talideon 3y ago
  Aren't Horn clauses enough to make a language Turing complete?

TheNewAndy 3y ago

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")

rcxdude 3y ago
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.
- TheNewAndy 3y ago
  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
talideon 3y ago
Aren't Horn clauses enough to make a language Turing complete?