[REBOL] Re: Any FSM fans?
From: greggirwin:mindspring at: 2-Nov-2001 13:01
Hi Ladislav,
<< Nevertheless, a well designed FSM dialect could become a parse
alternative/supplement, couldn't it? >>
Yes, absolutely. They key difference would be in how you design your
grammar. With an FSM approach, you would have an explicit driver (as the
parse function has inside it). Parse is more flexible, and has higher level
constructs than what I'm doing right now.
<< Have you got an idea what would you prefer the dialect to look like? >>
Yes. I have a first draft of the dialect working and some possible
alternatives for certain keywords.
My hope for the dialect is to be a semi-natural-language version of an STT
(State Transition Table). That is to say, adding clauses/keywords rather
than forcing you to enter data as a table. The goal is to let you *design*
the table in human friendly terms without being too verbose.
I'm going to ramble now since some people have asked what an FSM is. If you
really don't care about these things, feel free to stop reading. :)
A common (very small) example of a state machine is a turnstile. Here's a
natural language description of it, and its behavior:
It can be in one of two states (locked or unlocked) and can receive two
events (a coin is deposited or you pass through it). The actions it may
perform are: locking itself, unlocking itself, lighting up a "thank you!"
indicator, or sounding an alarm.
If it's locked, and you deposit a coin, it unlocks and is then unlocked.
If it's locked, and you try to pass through, it sounds an alarm, and is
still locked.
If it's unlocked, and you deposit a coin, it says "thanks!" and is still
unlocked.
If it's unlocked, and you pass through, it locks, and is then locked.
That's the human version of the spec. Programmer types, like us, might
handle it this way:
switch state [
locked [
switch event [
coin [
do-unlock
state: unlocked
]
pass [
alarm
state: locked
]
]
unlocked [
switch event [
coin [
do-lock
state: locked
]
pass [
thank-you
state: unlocked
]
]
]
(as you add more states and events, the standard switch approach gets ugly
real fast)
A State Transition Table is nice a concise (read dense) representation of
the logic:
STATE EVENT ACTION DEST-STATE
Locked Coin Unlock Unlocked
Locked Pass Alarm Locked
Unlocked Coin Thank-You Unlocked
Unlocked Pass Lock Locked
Here's what it looks like using my dialect:
when locked
coin causes unlock then unlocked
pass causes alarm
when unlocked
coin causes thank-you
pass causes lock then locked
(I also have it set up so you can define a state called "otherwise", which
means any other than one of the defined states, and an event called "other"
which means the same thing at the event level.)
So, that's the first part of the equation. The second part is doing
something with that design.
What some people have done (and I have as well), is to take something like
an STT and use it to drive a code generator that creates the switch case
code, state tables and drivers for them (e.g. table driven parsers), or a
set of classes if they're OOPers. When you do that, you have redundancy. You
have the design listed in one format, and then you have the generated code
in another. In some cases you are forbidden from touching the code, in
others you *have* to modify it. Either way, the design and code are separate
and you have to remember to regenerate the code if you change the design. If
you ever look at the code these things generate, you probably don't want to
touch it. Sometimes it isn't fit for human consumption, most times your
human friendly names get mapped to numeric values for states and events.
How is my approach different? The design *is* the code. OK, you do have to
pass it to a function so I can parse it and give you back the resulting data
structure, but you never have to deal with anything except the design.
You maintain a value for the current state and tell it to process events
(there is no driver wrapped around anything at this point). It executes the
actions you listed and returns the new state the machine is in, which you
just hold on to for use with the next event trigger.
Whew! Anybody still awake? :)
--Gregg
