Statechart

[fasf]

Hi,
i'm looking for a good (and simple) way to implement statechart (in C)
avoiding switch-case statements....any suggestion?
Thanks

 

[Beej Jorgensen]

What's a statechart?

Basically a state diagram.

http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf

Abstract excerpt:

We present a broad extension of the conventional formalism of state
machines and state diagrams, that is relevant to the specification and
design of complex discrete-event systems, such as multi-computer
real-time systems, communication protocols and digital control units.
Our diagrams, which we call statecharts, extend conventional
state-transition diagrams with essentially three elements, dealing,
respectively, with the notions of hierarchy, concurrency and
communication.

There's a C++ lib for it in boost, FWIW:

http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html

-Beej

 

[Beej Jorgensen]

i'm looking for a good (and simple) way to implement statechart (in C)
avoiding switch-case statements....any suggestion?

Here's a similar question with some suggestions:

http://stackoverflow.com/questions/133214/is-there-a-typical-state-machine-implementation-pattern

http://tinyurl.com/ydw8hxj

-Beej

 

[Remo D.]

Here's a similar question with some suggestions:

http://stackoverflow.com/questions/133214/is-there-a-typical-state-ma...

http://tinyurl.com/ydw8hxj

-Beej

I just reiterate the suggestion I gave in that SO thread: define these
simple macros:

#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x

and map your diagram 1-to-1 with:

FSM {
STATE(x) {
...
NEXTSTATE(y);
}

STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}

I do have a slightly more complex implementation of those macro in
clibutl to allow "sub state", i.e. states that will return to the
state they were called from: http://code.google.com/p/c-libutl/source/browse/trunk/src/utl.h

Not exactly UML state machines but little bit closer.

What I really like of this approach is that it retains intact the
"shape" of the diagram one usually draw when designing a state
machine, the other approaches I've seen, tend to hide the diagram
structure using tables or loops.

Remo.D.

 

[Ben Bacarisse]

I just reiterate the suggestion I gave in that SO thread: define these
simple macros:

#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x

and map your diagram 1-to-1 with:

FSM {
STATE(x) {
...
NEXTSTATE(y);
}

STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}

I don't think these macros are "working hard enough" to justify their
existence. STATE(x) is slightly more obscure than STATE_x: which is
understandable and also obviously a label. NEXTSTATE(x); is not
much better than goto STATE_x;.

I do have a slightly more complex implementation of those macro in
clibutl to allow "sub state",

And there it might pay off. In the above, I don't think it does.

I'd also point out the using labels rather than, say, a big switch
looses the possibility of storing the states in a table or any other
structure (some C dialects like gcc can do a computed goto, but not
standard C). Sometimes the best way to find the target state is with
a table rather than an 'if'.

What I really like of this approach is that it retains intact the
"shape" of the diagram one usually draw when designing a state
machine, the other approaches I've seen, tend to hide the diagram
structure using tables or loops.

This is a big win when the process is documented as a state machine
but it can be a problem to unravel what a state machine is really
doing if the process is either not documented or is described by some
other means. I mention this just as a cautionary note: state machines
can be clear for the author but hard to decode for the reader!

 

[Remo D.]

This is a big win when the process is documented as a state machine
but it can be a problem to unravel what a state machine is really
doing if the process is either not documented or is described by some
other means.  I mention this just as a cautionary note: state machines
can be clear for the author but hard to decode for the reader!

I agree, follow the logic of an undocumented FSM could be a nightmare!

My point is just that other methods to encode a state machine in a C
program (e.g. via a table of pointers to functions or using while()
and state variables) just make the task harder, while using goto (in a
disciplined form as the macro above) preserve the state machine
structure.

This method is intended to be refined and adapted to the specific
case. For example, the STATE() macro could read a symbol from a
default input stream and handle the EOF condition.


#define STATE(x) s_##x : if ((c=fgetc(f)) == EOF) goto s_END;

#define ENDSTATE s_END:


The idea is to hide those details that are implicit in the FSM
structure. Of course you can do horribly wrong things using this
thecniique but this is true for 99.9% of C

 

[Marco]

Hi,
i'm looking for a good (and simple) way to implement statechart (in C)
avoiding switch-case statements....any suggestion?
Thanks

see
http://www.embedded.com/2000/0008/0008feat1.htm
I believe the code presented in this article is unlicensed versus some
similar GPL versions if this is an issue for you.

Dr Samek also has a book that is worth reading:
http://www.state-machine.com/psicc2/index.php