implementing a state machine using the "yield" keyword

Question

Is it feasible to use the yield keyword to implement a simple state machine as shown here. To me it looks like the C# compiler has done the hard work for you as it internally implements a state machine to make the yield statement work.

Can you piggy-back on top of the work the compiler is already doing and get it to implement most of the state machine for you?

Has anyone done this, is it technically possible?

Choiseul

Answer 1

It's feasible but it is a bad idea. Iterator blocks were created to help you write custom iterators for collections, not for solving the general-purpose problem of implementing state machines.

If you want to write a state machine, just write a state machine. It's not hard. If you want to write a lot of state machines, write a library of useful helper methods that let you cleanly represent state machines, and then use your library. But don't abuse a language construct intended for something completely different that just happens to use state machines as an implementation detail. That makes your state machine code hard to read, understand, debug, maintain and extend.

(And incidentally, I did a double-take when reading your name. One of the designers of C# is also named Matt Warren!)

Statehood

Yeah I found his blog a while back, it's always weird when you find someone with the same name!! I did think this could be a bit of a abuse of iterator blocks, that's why I wanted to check first. – Choiseul

Oops. Sorry I did a bad abuse of the language (I did feel the pain when I was writing my example)! But I think there's a lot of overlap between FSM (esp. w/o interaction) and "generating a sequence." For instance, I think it works in scenarios where you want to, say, like a RegEx, finds matching patterns in some input; essentially, using it as something like a DFA. What's your opinion on this? – Commencement

I think the general idea of treating an FSM as a mapping from a sequence of inputs to a sequence of states is not that terrible an idea. If that's how you conceive of an FSM, then using iterator blocks is not a terrible idea. But if you're going to do that, then it makes sense to capture the "rules" in some sort of object that can efficiently do the mapping from (state, input) --> state. That way you're capturing the FSM logic in an object where you can inspect it in a debugger, rather than capturing it in the IL where its hard to see. – Statehood

I think any kind of non-trivial FSM might be best matched with an explicit FSM, but the simpler the FSM is, the better it is represented by iterator blocks. Simple if-else seems like a good candidate for this type of usage as an explicit FSM would seem to me to be rather unwieldy and harder to read than an if-else code block. – Nematic

Answer 2

Yes, it's absolutely possible and easy to do. You can enjoy using control flow constructs (for, foreach, while, ... goto (using goto particularly suits this scenario ;))) along with yields to build one.

IEnumerator<State> StateMachine
             (Func<int> currentInput /* gets current input from IO port */, 
              Func<int> currentOutput) {
    for (;;)  {
       if ((currentInput() & 1) == 0) 
           yield return new State("Ready"); 
       else {
           if (...) {
               yield return new State("Expecting more data");
               SendOutput(currentOutput());
               while ((currentInput() & 2) != 0) // while device busy
                    yield return new State("Busy");
           else if (...) { ... } 
       }
    }
}

// consumer:
int data;
var fsm = StateMachine(ReadFromIOPort, () => data);
// ...
while (fsm.Current != "Expecting more data")
    fsm.MoveNext();
data = 100;
fsm.MoveNext();

Commencement

Maybe I'm not thinking straight, but I can't see how you'd do this in code, do you have an example that can start me off? – Choiseul

I would be somewhat surprised to see a real life situation where this provided genuinely cleaner code than an explicit state machine. – Caudle

Jon: I have to agree. It can quickly become too complicated. Anyway, if state machine is mostly automatic, it'll work pretty well. – Commencement

I'm sure there are cases where iteration like this is okay - but you have a state machine that is now wired only for cyclic behavior. What happens with this state machine if ReadFromIOPort is delayed, the port closed unexpectedly, or the port is busy with something else? What if you want to set a time-out for receiving data? The cyclic nature of the machine must be changed to handle anything that goes wrong. – Mears

Answer 3

Iterator blocks do indeed implement state machines, but the tricky bit is getting the next input. How are you going to know where to move next? I guess you could have some sort of shared "current transition" variable, but that's somewhat icky.

If you don't need any input (e.g. your state machine is just cycling between states) then it's easy, but that's not the interesting kind :)

Can you describe the kind of state machine you're interested in?

Caudle

Even if you have input, you can easily use captured variables. It's a bit ugly, but I think it worths not implementing it by hand. – Commencement

I need the input to come from event handlers that are wired up to respond to I/O signals coming from a piece of external hardware. – Choiseul

@Mehrdad: I think I'd rather write my own state machine than use captured variables as a form of input... especially if the state transitions are at all complicated. – Caudle

Answer 4

While this is not a state machine in the classical sense, the article about Iterator-based Micro Threading uses yield creatively for state-based actions.

IEnumerable Patrol ()
{
    while (alive){
        if (CanSeeTarget ()) {
            yield return Attack ();
        } else if (InReloadStation){
            Signal signal = AnimateReload ();
            yield return signal;
        } else {
            MoveTowardsNextWayPoint ();
            yield return TimeSpan.FromSeconds (1);
        };
    }
    yield break;
}

Aqua