Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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