Do state machine based programs have a processing loop - or even exist?

Question

Short Version

If we had an application based on a state machine - transitioning between states to run the application: is repetition, and in fact the entire state machine, based on the presence of an event loop?

Something like:

void Main()
{
    while (_currentState != State.Exit)
    {
       switch (_currentState)
       case State.CharacterEntityReference: DoCharacterEntityReference();
       case State.NamedCharacterReference: DoNamedCharacterReference();
       case State.NumericCharacterReference: DoNumericCharacterReference();
       case State.AmbiguousAmpersandState: DoAmbiguousAmpersandState();
       case State.HexadecimalCharacterReferenceState: DoHexadecimalCharacterReferenceState();
       case State.DecimalCharacterStartState: DoDecimalCharacterStartState();
       case State.DecimalCharacterReferenceState: DoDecimalCharacterReferenceState();
       default: break;
    }
}

I ask because I've never seen or imagined something like that before:

• an entire application programmed as a state machine
• entirely based on short subroutines, and a giant switch statement.

Is this a thing? Was this ever a thing? Was this programming in the 1950s?

Long Version

I know about state machines: a data structure of nodes and edges, with your current "location", and various state transitions triggered by some event.

• But this isn't a data structure inside the program
• this is the program.

I was looking at the whatwg HTML 5 spec, where they document the correct parsing of HTML (i.e. into a DOM tree).

And I was reading it as though it described subroutines and methods. But I got stuck when a "function" to read a decimal string seemed like it would only read one digit and then give up:

13.2.5.79 Decimal character reference state

Consume the next input character:

• ASCII digit: Multiply the character reference code by 10. Add a numeric version of the current input character (subtract 0x0030 from the character's code point) to the character reference code.
• U+003B SEMICOLON: Switch to the numeric character reference end state.
• Anything else: This is a missing-semicolon-after-character-reference parse error. Reconsume in the numeric character reference end state.

My reasonable translation of that might have been something like:

void DecimalCharacterReferenceState()
{
   Consume();
   switch (_currentInputCharacter)
   {
      AsciiDigit:
         referenceCode *= 10;
         referenceCode += (Word)currentInputCharacter - 0x0030;
         break;
      default: 
         Reconsume();
         return;
   }
}

Except in all cases that method only reads one character, and then gives up. But this is the function that's supposed to collect a whole bunch of characters. That's when I realized that the function can only run again if:

• the state machine's loop jumps back to the top,
• realizes we're in this state,
• and calls our method again.

I'd never considered structuring a real program like that. Is this how Chromium, Safari, or Firefox perform their work? In a giant case statement?

Or is the State Machine model just a mental model:

13.2.5 Tokenization

Implementations must act as if they used the following state machine to tokenize HTML. The state machine must start in the data state. Most states consume a single character, which may have various side-effects, and either switches the state machine to a new state to reconsume the current input character, or switches it to a new state to consume the next character, or stays in the same state to consume the next character. Some states have more complicated behavior and can consume several characters before switching to another state. In some cases, the tokenizer state is also changed by the tree construction stage.

I'm used to the idea of a state machine being a data structure that I query, and push to a new state (like TCP connection state diagram).

But I'm not used to a state machine being the program.

Or is this just a Turing machine? (but the Turing machine didn't have a while loop)

Answer 1

It depends on where you draw the line. (Von Neumann) Computers are by definition finite state machines in an infinite loop. Most programs aren’t modeled this way because, well, it’s hella tedious and impractical to list all of the states of an integer to make math work.

But parsers very often are implemented this way, because their grammars are almost always in BNF (or some variant) which can be trivially generated into this finite state machine style code. They do it because it is very important to cover all of the possible permutations of input in an unambiguous way. Protocols have similar sort of needs, so also tend to be state machines even if they are (usually) less rigorously defined.

Answer 2

This is a fairly common pattern. Examples:

• all Windows desktop applications work on a message loop: they have while(GetMessage()) at the top, and the body is essentially a big switch statement that works out where to route the message to. See the Hello World example. In that code the library function TranslateMessage() calls WindowProc() which has the switch in it.

• embedded systems often operate on a timer loop that runs forever. When woken by the timer they poll all the inputs, decide what to do, and go back to the top of the infinite while loop.

• almost all video games have a loop of "take input", "update state (move objects in world etc", "render frame".

Answer 3

It is not strictly necessary to have a state variable and giant switch statement, as just having different sections of code can well represent states.

The following code snippet represents states as locations in the code, and so does not use a current state variable.  This is used for parsing infix expressions, which have 2 states: unary and binary.  In the unary state (also the start state) we expect unary operators, like -, *, or parenthesis or identifiers/numbers.  After consuming a unary operator, it remains in the unary state, but after consuming an identifier, changes to the binary state.  In the binary state, those same tokens, -, * are seen as binary operators, while parenthesis means function invocation rather than precedence grouping.

for (;;) { // outer loop, starts state 1

    // state 1, unary state
    for (;;) { // state 1 loop
        switch (token(nextChar())) {
        case Alpha: 
            // consume entire ID
            break; // leave state 1 for state 2
        case Numeric:
            // consume entire number
            break; // leave state 1 for state 2
        case '*' :
            // * in state 1 (unary state) means indirection
            push(indirectionOperator);
            continue; // stay in state 1
        case '(' :
            push(groupingParenthesis);
            continue; // state in state 1
        }
        break;
    }

    // cycling from state 1 to state 2 by coming here

    // state 2, binary state
    for (;;) { // state 2 loop
        switch (token(nextChar())) {
        case '(' :
            push(functionInvocation);
            break; // switch back to state 1
        case '*' :
            push(multiplicationOperator);
            break; // switch back to state 1
        case ')' :
            // pop operators until matching '(' or error
            continue; // stay in state 2
        }
        break;
    }

    // end of outer loop body: 
    // cycling from state 2 back to state 1 by looping
}

In the above, break; stops a case, which causes a state loop to exit, returning the program to the next state (by falling through from state 1 to state 2, or via the outer loop cycling from state 2 back to state 1), whereas continue; makes it remain in the current inner loop, staying in the same state.  The program knows what state it is in by code location — i.e. if it is running anywhere in the state 1 loop, it is in state 1.

In summary, the current execution location is a representation of state.  Programs other than parsers also maintain state this way: what code is currently running tells what to do now and controls what to do next; plus, they augment with variables & data structures that help with decisions and actions.

Answer 4

Your example of a scanner is not a program, it would be a tiny subroutine in a much larger program. If you use it as a co-routine, it would have internal state, but likely not enough to call it a “state-machine”.

Many applications have the goal of not being modal. At any point, the user should be able to take any action, so having a state machine would be avoided.

What is extremely common is an event processing loop, where some code that you wrote gets executed every time some event happens. You will likely not have that loop in your application code, but hidden in the GUI frameworks.

Answer 5

No, a state machine does not need a top level event loop. A state machine can be implemented with GOTO's to transition to a new state. Here is a silly example:

blueState:
  PRINT "State is blue!"
  IF somethingRandom THEN GOTO blueState ELSE GOTO greenState
greenState:
  PRINT "State is green!"
  IF somethingRandom THEN GOTO blueState ELSE GOTO greenState

A direct implementation of the HTML entity parsing algorithm could look something like this:

decimal_character_reference:
  character_reference_code = 0
decimal_character_reference_next:  
  char = consume()
  if char >= '0' and char <= '9'
    digitValue = char - '0';
    character_reference_code = character_reference_code * 10 + digitValue
    goto decimal_character_reference_next
  else if char = ';'
    goto numeric_character_reference_end
  else
    log('missing-semicolon-after-character-reference parse error')
    backtrack()
    goto numeric_character_reference_end

The use of GOTO is slightly controversial though, so implementors might chose to use a different approach, for example based on an event loop or function calls. In the GOTO-based solution, the state is implicit in the control flow. With a global event loop you would need one or more variables to explicitly represent the state. Whether you think this improves the clarity of the code is up to you.

The use of functions to represent states is probably the easiest to understand, but have the limitation that you can only exit to one state. In this case there is only one exit state (the "numeric character reference end state"), so it can be implemented as a function.