4 ms·
I've been working my way through the latest volume of The Art of Computer Programming (Volume 4B, released last year) which is about combinatorial algorithms.
by OskarS 3y ago
I've been working my way through the latest volume of The Art of Computer Programming (Volume 4B, released last year) which is about combinatorial algorithms. One of the very first algorithms he presents Algorithm B, "Basic backtrack". It's like a generic backtracking algorithm that you could use to solve combinatorial problems (e.g. n-queens, things like that).
Every time I've seen this algorithm presented, it's used recursion, because that's a very natural way to express backtracking. But Knuth doesn't, he basically never uses recursion in his TAoCP algorithms, he expresses his algorithms in a "flow chart" style, not assuming things like stacks or subroutines (in fact, one of the exercises in the chapter is to convert Algorithm B to a recursive version, which he then quickly dismisses in the answer to the exercise as "elegant, and works find for small problems" but fundamentally not very high performance and not really clearer than the non-recursive version).
So, I set down to implement Algorithm B in a generic way and used it to solve n-queens. The way Knuth has written it, it can be straightforwardly translated using `goto`s (it has lines like "if so-and-so, go to step B4, else B3"), but being the modern, structured programmer that I am, i tried to convert it to structured programming using loops and if statements.
It was doable, but when benchmarking, my versions were always slightly slower than Knuth's original "goto" formulation, and honestly I don't think they were more readable either. You had to add a bunch of variables to keep some state around that was implicit in Knuth's version. The recursive version was definitely more readable, but Knuth was of course correct, you pay a performance penalty for that readability.
It was a real eye-opener. In the hands of a master, "goto"s really do have a place, and when well-deployed, they can sometimes simply be superior to "structured" code using loops, ifs and recursion.
- afiori 3y agoOne of the arguments un favour if Tail Calls Elimination it that it allows to implement a goto-state-machine with mutally recursive functions.
- OskarS 3y agoYeah, this is a really interesting point, I should try this again with [[musttail]] on clang.
- afiori 3y agoMy understanding is that while it is possible to compile Tail Calls to be as efficient as an inline function it is (often) not possible in C.
- kazinator 3y agoBut the goto state machine is no easier to understand than the one with gotos. There was an argument like this on the comp.lang.c newsgroup a few years ago. Someone proposed a coding problem: I think it was writing a program that removes comments from C source, but preserves preprocessing directives and all else. So various solutions were posted. I wrote one that used a state machine based on goto; no control structures at all beyond assigning to variables and if/goto. That original poster then revealed his solution. It consisted of mutually tail calling functions. He specifically criticized the goto graph solution. I claimed they are basically the same, and to bolster my argument, I wrote a trivial simple text filter which converted that tail calling solution to a goto graph. Tail calling is not a higher level feature compared to goto. It is only syntactic sugar which leaves the program with the same organization. In some ways, the goto program is easier to understand. Why? Because: 1. The variables of the graph are all declared together in one place. Say you have a local variable x. All goto graph blocks that refer to x are referring to the same thing. In the tail program, every function that does something with x has to declare it for itself as its own parameter. It's not obvious that those x's are supposed to be the same entity. 2. Typically, functional languages, like C, do not have named parameters. The state is passed among the tail-calling function via strictly positional arguments. Not all functions have all the state variables, so a given state variable could be argument 3 in one function or argument 1 in another function. In the goto program it's very clear. If you have bar: x = s + 1; goto foo; we know: oh okay, this block updates the x state from s, and goes to foo. In the functional version: bar(s) -> foo(s + 1) we don't know what s + 1 is doing. We have to read foo: foo(x) -> ... ok, we know that s + 1 will be called x in foo. But is that consistent? Is it the same as every other x we see everywhere in the tail call graph? We easily see that consistency in the goto graph: there is a single x variable in the scope of the entire graph; anything that assigns to x is preparing a new value for that x.
- afiori 3y ago> In some ways, the goto program is easier to understand. Why? Because: > 1. The variables of the graph are all declared together in one place. [...] > 2. Typically, functional languages, like C, do not have named parameters. [...] I have little experience in C, but probably I would try to use a struct for the machine state. Even with no tail calls I think I would try to write the machine as mostly block of bar: step_bar(&state); goto foo; From my optic the benefit of tail calls is the ability to mix flow control and machine steps with function abstractions.