3 ms·
Goto is a useful precursor for writing a tail recursive solution. For instance, say we have a state machine for recognizing that the last four button presses w
by kazinator 5y ago
Goto is a useful precursor for writing a tail recursive solution.
For instance, say we have a state machine for recognizing that the last four button presses were 1234.
int keypad() // returns 1 if correct key is entered, otherwise loops forever
{
keypad:
switch (getkey()) {
case 1:
goto got_1;
default:
goto keypad;
}
got_1:
switch (getkey()) {
case 2:
goto got_2;
case 1:
goto got_1;
default:
goto keypad;
}
got_2:
switch (getkey()) {
case 3:
goto got_3;
case 1:
goto got_1;
default:
goto keypad;
}
got_3:
switch (getkey()) {
case 4:
return 1;
case 1:
goto got_1;
default:
goto keypad;
}
}
Now, refactor the same structure into tail calls. Now it's suddenly beyond reproach.
int got_1();
int got_2();
int got_3();
int keypad()
{
switch (getkey()) {
case 1:
return got_1();
default:
return keypad();
}
}
int got_1()
{
switch (getkey()) {
case 1:
return got_1();
case 2:
return got_2();
default:
return keypad();
}
}
int got_2()
{
switch (getkey()) {
case 3:
return got_3();
case 1:
return got_1();
default:
return keypad();
}
}
int got_3()
{
switch (getkey()) {
case 4:
return 1;
case 1:
return got_1();
default:
return keypad();
}
}
You can refactor any flow control graph based on goto, with local variables, into a network of tail calling functions. The tail call graph is isomorphic to the goto: it's just as complex and hard to understand. Yet it has the virtue of being beyond the reproach of computer science academia.
- ladberg 5y agoI think the better way to create a state machine would use another switch instead of the top-level goto like: int keypad() { int state = 0; // 0 = start, 1 = seen '1', 2 = seen '12', 3 = seen '123' while (true) { int key = getkey(); switch (state) { case 0: switch (key) { case 1: state = 1; default: state = 0; } break; } case 1: switch (key) { case 1: state = 1; case 2: state = 2; default: state = 0; } break; } case 2: switch (key) { case 3: state = 3; case 1: state = 1; default: state = 0; } break; } case 3: switch (key) { case 4: return 1; case 1: state = 1; default: state = 0; } break; } } } In my mind that reads more obviously as a state machine than a bunch of gotos and labels (and should function the same assuming I typed it correctly, I haven't run it anywhere). It's easy to see each state and how it flows into other states.
- kazinator 5y agoI don't see how that is better. Every one of your "state = N" assignment is just a goto in disguise, which requires the machinery to go back to the top and then jump somewhere again. Someone looking at "state = 1" has to understand that state is a variable which controls the outer switch, and that 1 is refers to "case 1:" of that outer switch. You have a proliferation of "case 1:" repetitions, so the reader has to follow the indentation carefully. The goto is not a simple goto, either. When we assign "state = 1" it doesn't just mean to branch to the "case 1" node, but to go through the "key = getkey()" initialization. The whole thing is less efficient than goto. Specifically to C, you have more lines of code now. You remembered your break statements in the outer switch, but in the inner switches, you carelessly changed the gotos to assignments without adding the required break statements, so you have a bug in every inner switch. When you fix those, you will have some seven more lines of code. Note how my original code has no variables at all, and neither does the transliteration into tail calls. You have two variables: key and state, plus you still have the same underlying goto graph structure. The only saving grace of this arrangement is that it factors out the common action of calling getkey() into one place which is only important if we can't turn that common action into a tiny function call with just two or three arguments. The property in my graph that getkey() is called in multiple places is a key property; it helps to farm off each block directly into a corresponding tail calling function in the mechanical transformation to the tail call graph. I used to write all state machines this way, with labeled states, and a loop around a switch and input processing in one place at the top. Quite recently, I did some ad hoc comaparative studies which convinced me I won't be doing that any more; I will be using disciplined goto graphs.
- kazinator 5y agoAlso note that switch (state) { case STATE_LABEL: ... } is a form of computed goto. Every time we use switch in a C program, we are using computed goto. The switch statement escapes the disparagement that is lobbed at goto for two reasons. 1. It doesn't have "goto" anywhere in its name. (Neither does an assembly language JMP instruction, yet it is still goto). 2. It has a limited scope: whereas goto can jump to any label anywhere in a function, a switch only branches within a statement. (But anywhere within that statement; into any level of nesting inside any sub-statement!) If you wrap the bulk of your function with a giant switch inside a dispatch loop on a state variable, then, effectively, the (2) limited scope defense of switch no longer applies: you have perpetrated a bare-faced computed goto scoped over the bulk of the function body.