finite state machine
b...@coolgroups.com
For instance you could have every state as a function. Then, to
switch
states you call another function. Eventually, you'd run out of stack
space though, but you could get around this by adjusting your stack
pointer at the beginning of all FSM functions.
Alf P. Steinbach
> What is the best way to translate a finite state machine into code?
The number of tails a dog has depends on the dog.
However, books about writing compilers treat this subject in detail.
Generally, the two preferred ways to generate code from a finite state
machine specification are the same as the ways of representing booleans:
state as dynamic data, or state as program execution position. And just
as for booleans those two ways can be mixed. State as dynamic data
yields code that is more maintainable for a human, whereas state as
program execution position can be more efficient wrt. execution time.
> For instance you could have every state as a function. Then, to
> switch states you call another function.
That would in general be a stupid way.
> Eventually, you'd run out of stack
> space though, but you could get around this by adjusting your stack
> pointer at the beginning of all FSM functions.
That would be even worse.
Cheers, & hth.,
- Alf
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Logan Shaw
> What is the best way to translate a finite state machine into code?
There are sort of two ways to take this question. One is that you want
to make some kind of complex transformation, so that you go from a
state machine to code that no longer looks like a finite state machine
when you're done with it. I don't really have any comments on this
first interpretation.
The other interpretation is that you really want to think in terms of a
finite state machine (because that sort of model is useful for working
with whatever type of problem you are solving) and you want to write code
that will look and work like a state machine, but you're just looking for
a pattern on how to do that. That is, you want to basically transliterate
a state machine into code and you're looking for a good, clean way to do
it in a commonly-used programming language.
For this second interpretation, I can suggest three obvious ways.
The first method is to simply define an enumerated type (enum in C) where
each value of the enum is a state. Then have a while loop that contains
a switch statement. The switch statement will switch on the state and
each case of the switch statement will run code for a state, setting the
new state.
The second method is to assign an integer value for each state, then define
a table of function pointers. Then you have loop just like in the first
method, but instead of using a switch statement in the body, you simply
use the current state as an index into the table (probably an array) of
function pointers, and you call the function you get out of the table.
The function returns the next state as its return value.
And the third method is like the second, but you eliminate the array.
You simply have functions return pointers to other functions. Then the
loop simply calls a function, stores its return value (which is a function
pointer), and then when it repeats calls the function specified by the
return value. This is actually very similar to your method where one
function calls another, but since you return first and it is a loop body
that repeatedly calls functions, you don't need to worry about the stack
overflowing.
- Logan
JPWoo...@gmail.com
Let me suggest that you look at http://www.christ-usch-grein.homepage.t-online.de/Ada/FSM.html
Here is a precis of that page:
FSMedit is an editor for finite state machines. It is written in Ada
with the graphical user's interface <...>
After specification of the transition diagrams, you can execute a
simulation of the machine interactively or via scripts.
From the transition diagrams, Ada code can be generated; also the
reverse, extraction of transition diagrams from Ada code is possible.
There are analysis tools for reachability analysis and also for
comparison of two machines.
John
Gene
> * b...@coolgroups.com:
>
> > What is the best way to translate a finite state machine into code?
>
> The number of tails a dog has depends on the dog.
>
> However, books about writing compilers treat this subject in detail.
>
> Generally, the two preferred ways to generate code from a finite state
> machine specification are the same as the ways of representing booleans:
> state as dynamic data, or state as program execution position. And just
> as for booleans those two ways can be mixed. State as dynamic data
> yields code that is more maintainable for a human, whereas state as
> program execution position can be more efficient wrt. execution time.
>
> > For instance you could have every state as a function. Then, to
> > switch states you call another function.
>
> That would in general be a stupid way.
Ah, you should avoid using the word stupid lest it bounce back and hit
you. Since a tail-recursive call is equivalent to a goto, the OP's
suggestion is perfectly reasonable. It's exactly what you proposed:
representing state by program execution position. In Scheme e.g. it
would be a natural idiom. Perhaps you should read some of the
compiler books you mentioned.
>
> > Eventually, you'd run out of stack
> > space though, but you could get around this by adjusting your stack
> > pointer at the beginning of all FSM functions.
>
> That would be even worse.
Again, the OP is re-inventing some basic computer science that
apparently you do not know. He is describing the optimization of tail
recursion, where the stack frame of the current call is removed before
jumping to the tail recursive entry. You ought to be congratulating
him for creativity rather than disrespecting him.
Alf P. Steinbach
> On Dec 15, 11:50 pm, "Alf P. Steinbach" <al...@start.no> wrote:
>> * b...@coolgroups.com:
>>
>>> What is the best way to translate a finite state machine into code?
>> The number of tails a dog has depends on the dog.
>>
>> However, books about writing compilers treat this subject in detail.
>>
>> Generally, the two preferred ways to generate code from a finite state
>> machine specification are the same as the ways of representing booleans:
>> state as dynamic data, or state as program execution position. And just
>> as for booleans those two ways can be mixed. State as dynamic data
>> yields code that is more maintainable for a human, whereas state as
>> program execution position can be more efficient wrt. execution time.
>>
>>> For instance you could have every state as a function. Then, to
>>> switch states you call another function.
>> That would in general be a stupid way.
>
> Ah, you should avoid using the word stupid lest it bounce back and hit
> you. Since a tail-recursive call is equivalent to a goto, the OP's
> suggestion is perfectly reasonable. It's exactly what you proposed:
> representing state by program execution position.
It can be largely equivalent in a language and implementation of that
language that guarantees the reuse-stack-frame optimization, but not in
general.
In general it would be stupid.
And absolutely not "exactly what you proposed".
> In Scheme e.g. it
> would be a natural idiom.
Maybe. I don't know Scheme well enough to say whether you're mistaken
or (on the other hand) the language provides optimization guarantees
that make debugging a nightmare.
> Perhaps you should read some of the
> compiler books you mentioned.
Thank you for that suggestion. I have implemented a few small
languages, but only one compiler (t'was Pascal, and a student exercise,
about 25 years ago). It was my intention to delve into the Spirit
framework some day, and perhaps I'll do that.
>>> Eventually, you'd run out of stack
>>> space though, but you could get around this by adjusting your stack
>>> pointer at the beginning of all FSM functions.
>> That would be even worse.
>
> Again, the OP is re-inventing some basic computer science that
> apparently you do not know. He is describing the optimization of tail
> recursion, where the stack frame of the current call is removed before
> jumping to the tail recursive entry. You ought to be congratulating
> him for creativity rather than disrespecting him.
You imply that given that the OP asked about a stupid solution
(presumably due to lack of knowledge, not lack of intelligence) he must
be stupid, or is perceived as stupid.
You should apologize to the OP for implying that he is (perceived as)
stupid. And while you're at it, apologize to me for your trolling.
Cheers,
Gene
Not a troll at all, just an old teacher who cringes at seeing a person
trying to learn something, showing some real insight (that stack
chopping loses no information in this case), and being told that the
insight is stupid. In a certain setting of a traditional imperative
language, the OP's idea is impractical. That's true. But IMHO you're
enslaved by the tools of your apprenticeship. In any functional
language, lisp (the Scheme standard e.g. guarantees no stack growth
for tail-recursive calls), F#, Standard ML, Haskell, etc., what the OP
proposed is natural and an efficient idiom. State is represented by
the function currently executing. It's not stupid. Really. Just not
conventional. God bless the kids with the questions that make us
think.
Cheers indeed,
Gene
EventHelix.com
The following article describes a state machine using the state
machine pattern:
http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm
--
EventStudio 4.0 - http://www.eventhelix.com/eventstudio/
Sequence diagram based systems engineering tool
Logan Shaw
> Not a troll at all, just an old teacher who cringes at seeing a person
> trying to learn something, showing some real insight (that stack
> chopping loses no information in this case), and being told that the
> insight is stupid. In a certain setting of a traditional imperative
> language, the OP's idea is impractical. That's true. But IMHO you're
> enslaved by the tools of your apprenticeship. In any functional
> language, lisp (the Scheme standard e.g. guarantees no stack growth
> for tail-recursive calls), F#, Standard ML, Haskell, etc., what the OP
> proposed is natural and an efficient idiom.
On a side note, is there anything other than merely tradition that
prevents implementations of (and standards of) imperative languages
from eliminating tail recursion? In fact, don't modern versions of gcc
offer this optimization? It seems like this is mostly independent of
the imperative/functional distinction (except, again, for tradition).
- Logan
Alf P. Steinbach
In C++ apparent tail recursion at the source code level is often not
tail recursion at the abstract machine level, due to destructors being
invoked and (although this feature is in practice seldom used)
exceptions being checked against exception specification list.
Java lacks automatic destructor invocation on leaving scopes, but in
that language exception checking is commonly used. Exception checking
by itself still leaves room for optimization if the tail-recursive call
is a call to the same routine, or if the routine called has the same
exception specification. However, Java's exceptions include a
description of the call chain.
Even when there is abstract machine tail recursion, reusing the stack
frame loses information about the call chain, which can be critical when
the program doesn't work as expected. And just about all code has bugs.
The question when such a bug is encountered is, how the heck did the
execution end up /here/, in foo()? With the optimization the
information at hand says that foo() was called by mainLoop(), but,
there's no call to foo() in mainLoop().
And in particular, when the code has been implemented under the
assumption of cost-free tail recursion, tracing the calls in that code
with a tool that doesn't support that optimization can be a nightmare,
because there will be lots of calls, a Very Large Call Depth.
So it's both a practical tool usage matter (largely language
independent) and a matter of tail recursion not necessarily being
present at the abstract machine level even if it seems to be tail
recursion at the source code level (language dependent). The
perspective that tail-recursion optimization is a free lunch only
considers program execution time and memory consumption. It fails to
consider programmer's time, which is generally much more important.
Cheers, & hth.,
Gene
Yes. Great question. Under just the right conditions, gcc removes tail
recursion, and not just recently. Versions have done so for at least
10 years. Actually I think it's more like 15.
The following little FSM prints a message when it sees a C comment.
It has zero stack growth when compiled with gcc -O2 on my Win32 box.
Same with VC 2005 Express.
I still wouldn't classify this as practical for general
implementation. For example gcc -O3 _does_ produce stack growth. It
seems the inliner confuses the tail recursion remover! Still, the OP
was not so far afield...
#include <stdio.h>
int ch;
static void get_next(void)
{
ch = fgetc(stdin);
}
static int saw_slash(void);
static int in_comment(void);
static int saw_star(void);
static int start(void)
{
get_next();
if (ch == '/') return saw_slash();
return start();
}
static int saw_slash(void)
{
get_next();
if (ch == '*') return in_comment();
return start();
}
static int in_comment(void)
{
get_next();
if (ch == '*') return saw_star();
return in_comment();
}
static int saw_star(void)
{
get_next();
if (ch == '/') { printf("ate a comment!"); return start(); }
return in_comment();
}
int main(void) { return start(); }
John Slimick
would to support the general thread of FSM's.
When I have taught the intro to CS course
I have introduced four machines:
1. The trivial vending machine (boring!)
2. The Roman numeral recognizer (boring!)
3. The stoplight FSM suitable for implementing
in ROM (less boring!)
4. Convert ASCII to float (important)
(A story about [4]: I taught briefly at a school
in Tennessee where the semester before I got there
someone had assigned the problem, and not one student
had gotten it working. I brought the FSM and one student
had it working on the third compilation -- such is
the power of FSM's)
All these are hand-coded. In another class I used
a FSM to scan lines of assembler.
All these FSM's were hand-constructed, and were simple.
I harangued about the importance of FSM's.
I have taught "better" models such as lex and flex.
And I teach C++ regexp in the data structures course.
I heartily recommend the use of FSM's.
john slimick
sli...@pitt.edu