3 ms·
I 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 = star
by ladberg 5y ago
I 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.