Good ways to jump to a particular state in a yielding stateful function?

Question

I'm working on some embedded code using C. Various pieces of functionality need non-blocking stateful functions, which are mostly implemented using a switch on various states. For example, a modem connection manager (pseudo-code):

void manage_connection(void) {
    static states state = IDLE;
    switch (state) {
        case IDLE:
            if (connection_requested()) state = BACKOFF;
            break;
        case BACKOFF:
            if (random_delay_timeout()) {
                do_connect();
                state = CONNECTED;
            }
            break;
        case CONNECTED:
            result = send_data();
            if (result == DATA_SENT) {
                state = IDLE;
            } else if (result == ERROR) {
                // Go straight to backoff state and connect ASAP
                state = BACKOFF;
            }
            break;
    }
}

State machines are nasty at the best of times, so I've started to move to a different paradigm using coroutine-style functions, using a "yield" statement. Of course, C doesn't provide a "yield" statement, but I'm using protothreads to achieve this. Protothreads is great, and gives me exactly what I want to implement the above non-blocking state machine in a structured-programming style. The above function roughly translates to (pseudo-code):

void manage_connection(void) {
    WAIT_UNTIL(connection_requested()); // or, while(!condition) yield;
    WAIT_UNTIL(random_delay_timeout());
    do_connect();
    WAIT_UNTIL((result = send_data()));

    if (result == DATA_SENT) {
        // RESTART starts from top. It is part of the protothreads API.
        RESTART();
    } else if (result == ERROR) {
        // This is the part which doesn't translate so well.
        // Could use an ugly goto:
        goto backoff;
        // Or similar alternatives, none of which scale well:
        // - Set a flag to skip the states I don't want, and RESTART();
        // - Use while loops or other control logic to branch appropriately.
    }
}

As you can see, the protothreads version is, on the whole, much clearer & simpler in terms of the flow of logic (once you learn how protothreads work, and look past some very minor boilerplate which I haven't included in the example).

But jumping to a particular state in a state machine is a common pattern that I'm come across, which the state machine version handles elegantly, but the procedural version does not. Of course, that's why the procedural version is less bug-prone and clearer -- because you can't jump all over the place on a whim (except for goto, which I'd like to avoid for the usual reasons).

However, when you have a good reason to want to jump, it adds significant bug-prone lack of clarity to what is otherwise a very straightforward function.

Obviously there are plenty ways to achieve the necessary functionality, but none of them scale well to more than a few states. Bear in mind this is the simplest possible example -- my real-world functions fill half a screen.

What are some ways to solve this problem in a way that doesn't muddy the otherwise-lucid flow of logic?

Answer 1

Unfortunately, I don't think there's a clear way out of this in plain C.

Your "otherwise-lucid flow of logic" (be it implemented with protothreads, threads or fibers) is still a state machine (as any program is), which is only apparently clean, because it's missing its lateral cases: transitions into error states, or transitions back (on failure or timeout); if you plug these transitions in, you find that you need to goto or muddy up the design, which, as you have observed, tends to get ugly.

One potentially cleaner solution is to set up a declarative state machine: you can use an array of state transition entries, each entry holding the state of origin, the final state, and at least two function pointers: a transition checker (can I perform this transition?), and a transition action (what to do when the transition is performed). When you need to perform a transition, go through the array entries with state of origin == current state, run the first one for which the checker returns TRUE, execute its action, and move to the new state. Mind that the checkers should be light or NULL (maybe just context checking - because you run them all the time), and the actions should be heavy (do stuff).

This is a good pattern for dense SMs (with lots of transitions); its only drawback is that it separates implementation (the checkers and actions) from the SM declaration (which may lead to a bit of yo-yo-ing when trying to understand what it does).

You can further improve this model with stuff such as:

• Actions which execute every time a state is reached (regardless of the state of origin), before or after the transition;
• Exceptions (actions which execute when the transition reports a failure somehow);
• Nested SMs

Answer 2

First of all, thank your for let me find out protothread: very clever! This also means, I'm everything but an expert at protothread.

I think I would write your state machine as follow:

void manage_connection(void) {
    for (;;) {
        WAIT_UNTIL(connection_requested());
        do {
            if (attempts++ >= MAX)
                RESTART();
            WAIT_UNTIL(random_delay_timeout());
            do_connect();
            WAIT_UNTIL(result = send_data());
        } while (result != DATA_SENT);
    }
}

The whole point is that you need a conditional branch to deal with a non-linear case. Plus, the connection attempts cannot be infinitive.