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.
I think I may even have used it in Go once, but I can't remember what for. Go's defer keyword obviates the above use of goto, and labeled breaks almost any other case I can think of.
In a higher-level language, it's as silly as asking if you should avoid explicit malloc/free when writing SQL.
How would the Rust compiler deal with goto? You could dodge ownership and start operating on data before/after it's created/deleted.
A try-with-resources/using in Java/C# would no longer offer its guarantees.
How about async blocks in general? Do you just wander into another thread's code (but keep your own stack frame?)
Lambdas? Closures?
People probably
> regurgitate the age old argument against the use of goto
because there's no new arguments for it.
While people are familiar with Functional and OOP, most forgot or don't know about structured programming. Because it has proven to be good by default almost universally.
Look at the COBOL ALTER statement or GCC computed GOTO to see what the issues were.
While there are Böhm–Jacopini theorem purists that argue break and return, it is the law of diminishing returns.
Break and return may be syntactic sugar for GOTO, but they don't have the same problem of the unrestricted transfer of control that was and is considered harmful.
GOTOs are just one of the oldest ones, but these days, for example, we have polymorphism, and OO, in general, and, for some folks, anything that is \(!$HOLY_MANNA) is bad.
In my work, I tend to mix brand-new techniques with very old ones (probably older than some of the folks reading these words of prose).
Writing Solid Code was written in 1992. Many of its techniques have been integrated into toolchains, some are outdated, and some are still every bit as valid, today, as they were, then.
I will say that reading it was a watershed, for me.
That same book also teaches something important: programs based only on control structures like if and while generate goto graphs that meet a certain important property. All non-forward gotos in the graph are backwards gotos, dominated by the statement to which they branch.
A situation like this isn't generated by control structures; it requires goto:
if (condition0) {
statement1;
label0:
statement2;
}
if (condition1) {
goto label0;
}
The "goto label0" is not a true backwards goto.
Backwards gotos return to nodes which dominate the goto statement; i.e. go back to a point in the program that had to be visited in order to reach the goto. Here, label0 doesn't dominate the goto at all. The goto can be reached without reaching that label.
I have never experienced the need for a ‘goto’ otherwise.
Now, 1970’s COBOL, that was another story.
> - Using a single goto and single label to exit several levels of scope.
Better handled by putting the nested scope in a function and using `return`.
> - Using a goto in the middle of complex construction to short cut to the top of a loop.
Use `continue`.
> - Starting a highly optimized do { ... } while loop that is best initiated by jumping into the center first. (Because your compiler is not cooperating.)
This one's tricky, first be sure that the optimization is actually needed. Then, with a quick glance at DRY for apology put a copy of the second half of the loop before the `do`.
> - Extensions of duff's device.
Oh come on. The original Duff's device is not intuitive when first approaching it, and there is pretty much one use for it. I wouldn't even suggest to juniors that they be aware of this trick at all, tbh. It's a curiosity but I balk at it being a justification for adding gotos to make your own custom extension of it. See above, check that you really need such a severe optimization. You likely don't.
The goto of Dijkstra jumps to somewhere else in the program. You're somewhere in the call stack and decide to scribble on some registers and jump to some arbitrary location. Like longjmp with the restrictions taken off. As in across function boundaries. When you're writing assembly that works exactly as it it sounds like it would.
The goto of C jumps to somewhere else in the same function with a bunch of compiler warnings if you manage to bypass an initialisation. You can make control flow more complicated within a single function, sure.
Goto in C is not a significant problem. Jumping between different functions in assembly is however legitimately confusing.
This is something of a pet annoyance because various languages or coding standards decide to outlaw the friendly easy goto as it has such a scary reputation. This makes some algorithms much more complicated to express and others inherently slower.