Links

Categories

Tags


« | Main | »

Implementing sequential state machines

By Jewe | May 25, 2013

This example is a part of my series on implementing state machines.

A recurring pattern in state machines is what I call here the sequential state machine. That is, the class has a number of states and sequentially hops to the next state once the current state is finished. The common way to implement such a machine in C would be with a switch:

static int State = 0;
static const char* DoState()
{
    const char* result = "";
    switch (State)
    {
        case 0:
            // do something
            // ...
            // when done return a result
            result = "Hi, this is state A.";
            // go to next state
            State = State + 1;
            break;
        case 1:
            // do something
            // ...
            result = "And this is state B.";
            State = State + 1;
            break;
        case 2:
            // do something
            // ...
            result = "State C is done.";
            State = State + 1;
            break;
        default:
            // state machine ran through
            break;
    }
    return result;
}

In C++ we would of course put the code in a class and have the state counter as a member variable, but that’s just decoration. The main problem stays the same: The class must keep track of it’s current state itself. With a single state counter that’s not a big problem. But imagine the state machine gets more complex. Then the class is suddenly faced with handling and managing multiple counters and flags and things get ugly fast.

Fortunately in JewelScript there are better ways and there are cases where we don’t need to use switch or state variables at all. First of all, lets put the actual code of the three states nicely into class:

class Actor
{
    method Actor() {}
    method string A() { return "Hi, this is state A"; }
    method string B() { return "And this is state B"; }
    method string C() { return "State C is done."; }
}

There are no state variables in this class. Instead, our actor just knows the things it needs to know. Which is, the code that should be executed each step. Now we could just call each method of the object after the next, but that wouldn’t be a state machine. In a state machine, we could leave the current function and memorize which method we have called. Then, when we come back, we would execute the next function.

In JewelScript we can use a co-function for exactly this purpose. A co-function is a function that has it’s own stack context that is independant from the current execution context. You can think of it as a small thread, only that it doesn’t run automatically in the background. Instead, the user decides when a co-function is resumed and yielded:

cofunction string Sequencer(Actor actor)
{
    yield actor.A();
    yield actor.B();
    yield actor.C();
}

I should probably explain what happens in this function, in case some readers aren’t familiar with co-functions. A co-function thread will continue to run until it is yielded. So once the above code is resumed, it will call the first method of our actor, then return it’s result and stop. Execution will then return to the function that resumed the co-function. When that function resumes the co-function again, execution will continue where it left off. Thus, the second method of actor is executed. Again, the result is returned and execution returns to the caller.

Here’s how we would use our sequential state machine:

function main()
{
    Sequencer s = new Sequencer(new Actor());

    println( s() ); // prints "Hi, this is state A"
    println( s() ); // prints "And this is state B"
    println( s() ); // prints "State C is done."
}

So what happens once our Sequencer co-function has reached it’s end? It would always return its last result, but without calling the last method again. To remedy this, we could add the following statement to the end of the co-function:

    yield "";

If we don’t want the state machine to end after the last step, but instead start over, we would simply wrap the code in an infinite loop:

cofunction string Sequencer(Actor actor)
{
    for(;;)
    {
        yield actor.A();
        yield actor.B();
        yield actor.C();
    }
}

So what would we do if we wanted an option to alter the order in which the states are called?

Well, we could pass an additional flag to the co-function and then implement all variations there, but that wouldn’t be very object-oriented.

Nothing prevents us from having multiple Sequencer implementations, so we could make another that calls C, B, A and another that calls C, A, B. When creating the Sequencer and our Actor, we would then simply choose the co-function needed for the job and the rest of our code would remain the same:

cofunction string Sequencer(Actor actor)
{
    yield actor.A();
    yield actor.B();
    yield actor.C();
}

cofunction string SequencerReverse(Actor actor)
{
    yield actor.C();
    yield actor.B();
    yield actor.A();
}

function main(int reverse)
{
    Actor actor = new Actor();
    Sequencer s = null;

    if( reverse )
        s = new SequencerReverse(actor);
    else
        s = new Sequencer(actor);

    println( s() );
    println( s() );
    println( s() );
}

Topics: coding tips, docs | Comments Off on Implementing sequential state machines

Comments are closed.