Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
I don't think your use of goto there is actually that bad... –  hugomg May 4 '12 at 20:41
1  
How likely is a failure of any of the stages and what are the consequences of such a failure and of the response to failure? If failure is unlikely, I'd say that tearing down the whole thing and starting again is the simplest option. But it depends on the details of course. –  William Morris May 5 '12 at 3:50
    
@missingno: Thanks, and I agree, it's not that bad. But gotos used for anything other than cleanup-at-the-end is a slippery slope. One goto isn't too bad, but a couple more will start to obscure the logic of the code, and destroy any advantage in clarity which protothreads provides. –  bryhoyt May 5 '12 at 21:11
    
@WilliamMorris: Failure means that the device won't connect or disconnect properly, which is one of the core functions in this case. It needs to get data through, or it's failing as a product. A restart is not the end of the world, but the service provider in this case has specific requirements over what needs to happen when data isn't sent properly, so that still needs to be implemented one way or another. –  bryhoyt May 5 '12 at 21:16
2  
My inclination is always to keep things as simple as possible unless forced not to. So I would keep the response to failure as straightforward as possible without complicating the design. But it does depend upon the probability of failure. If failure is common and easy to provoke then it is worth spending significant design time handling it; it will be easily testable. If failure is rare then complicating the design to handle it is dangerous, especially if faults are hard to provoke; testing recovery is difficult. In the latter case, I would just bail out, clean up and start again. –  William Morris May 6 '12 at 1:42

2 Answers 2

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
share|improve this answer
    
Oops, lost my edit window: You're right, this code is still technically a state machine, but the point in this case is that it doesn't read like a state machine, and isn't intended to. The states aren't explicit, but the flow of logic is clear, and more suited to the problem being solved. Yes, in some cases, state machines are better than procedural code, but IMHO that's not often the case (hence "structured programming" and "goto considered harmful" etc). At any rate, I've chosen to use protothreads selectively for the blocking+asynchronous functions where it makes most sense. –  bryhoyt May 5 '12 at 21:25
1  
True, but you may have a problem for which there is a dense net of transitions between states, which is simply not expressible with reasonably linear code (it will get really branched). This may be the case here, therefore you may need to consider a targeted approach (a SM in C, a specialized design pattern in OOP). –  vski May 7 '12 at 15:17
    
thanks. You're right, a SM can be a very useful way to express certain complex nets of states. But in my particular case, the functionality is very much linear/procedural on the whole, but still with a few jumps to semi-arbitrary points in the procedure. My question is more about best to express these semi-arbitrary jumps in a mostly procedural context. A specialized OO design pattern is an excellent idea, the sort of thing I'm after -- but a) this is C ;-) which is unfortunately a non-negotiable on this project, and b) what design pattern? –  bryhoyt May 7 '12 at 20:20

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.

share|improve this answer
    
Good answer. One thing I want to avoid is having to wrap almost everything in a large block (the do-while block). In this example, it's fine, but it starts becoming more unclear when the function gets larger -- one disadvantage of protothreads is that factoring out into multiple smaller functions isn't always convenient, so your functions can start to get longish. That said, I like your answer. I'd eliminate one level of indentation by taking out the for(;;) loop and putting a RESTART() at the end of the function instead -- I forgot this in my original example. –  bryhoyt May 8 '12 at 3:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.