2 ms·
> code is a more useful blueprint than anything else for programs This is so clearly false that it can actually be mathematically disproven. To prove that ther
by pron 9y ago
> code is a more useful blueprint than anything else for programs
This is so clearly false that it can actually be mathematically disproven. To prove that there are better software blueprints than code, I will prove that there exist algorithms/systems for which sufficient formal blueprints exist, yet no code can capture. To prove that, I will need to define the terms more precisely. A "sufficient blueprint" is one that makes it possible to prove properties of interest about your software. "Code" is a formal representation of an algorithm, which always allows efficient mechanical execution, meaning, mechanically executing code is within a polynomial bound of the complexity of the algorithm that code expresses.
Now for the counterexamle: take the specification of the Quicksort algorithm, [1], shortened here as: 1. Pick a pivot. 2. Partition the elements around the pivot. 3. Recursively apply 1 and 2 to the resulting partitions.
I claim that this specification is sufficient. For example, from a direct formal statement of it, you can formally prove that it actually sorts and that it runs in worst-case quadratic time complexity. Yet, I claim that no code can express the above specification; in fact, no code can express any of the three steps. For example, step 1 says "pick a pivot", but it doesn't say which. This is not an omission. It doesn't say which because it doesn't matter -- any choice will do. And yet, code must necessarily say which pivot to pick, and when it does, it is no longer captures the specification, and is no longer a blueprint for all implementations of that specification. Similarly for the other two steps: code must specify which partitions are created of the very many possible and completely fine ones, and in what order the recursion takes place. QED
Languages like TLA+ can formally, i.e., mathematically, capture precisely the specification above and express anything code can. There is no magic here: Efficient execution of code (provably!) cannot be done in the presence of some quantifiers, yet quantifiers increase the expressiveness and "generality" of the language.
[1]: https://en.wikipedia.org/wiki/Quicksort#Algorithm https://en.wikipedia.org/wiki/Quicksort#Algorithm