Any FSM fans?

Hi Gang, I'm a big fan of FSMs and, being the wacky guy I am, I got this idea for an FSM "thing" in REBOL. My questions to you are: a) How many people here use, or have used, FSMs and would like to use them in REBOL? b) How many haven't used them because they think it's too much work, that they're too hard to maintain, etc.? c) Are there a couple gung-ho FSMers our there who would like to critique my design and give me their thoughts? I have a first-draft of the core concept working but would like to get a couple other perspectives. Thanks! --Gregg

umm... what's a FSM? :-P james

What is FSM? Thanks!! Ammon

Hi James, << umm... what's a FSM? :-P >> Finite State Machine. --Gregg

[Charset iso-8859-1 unsupported, filtering to ASCII...]

> umm... what's a FSM? :-P

> james >

http://dis.cs.umass.edu/research/fsmdummies.html Has some info. I am still looking for better infomation. Regards, Greg

Sounds like a way to accurately identify a series, almost like parse. Here is Xerox's words on it: http://cslu.cse.ogi.edu/HLTsurvey/ch11node8.html Seems that a FSM dialect that feeds into parse could implemented pretty easy, from my laymans perspective anyhow. --Ryan James Marsden wrote:

> umm... what's a FSM? :-P > james > [rebol-request--rebol--com] with "unsubscribe" in the > subject, without the quotes.

That doesn't tell me a whole lot. ;-( Thanks!! Ammon

[Charset iso-8859-1 unsupported, filtering to ASCII...]

> Hi James, > > << umm... what's a FSM? :-P >> > > Finite State Machine.

> --Gregg > -- > To unsubscribe from this list, please send an email to > [rebol-request--rebol--com] with "unsubscribe" in the > subject, without the quotes. >

Ryan, et al << Sounds like a way to accurately identify a series, almost like parse. >> They are often used to drive parsers (regex engines are a good example), but they are also used for much, much more. Very useful, but highly under-utilized (kind of like REBOL). Those that use them, love them; those that don't, just don't know what they're missing. :) << Seems that a FSM dialect that feeds into parse could implemented pretty easy, from my laymans perspective anyhow. >> Very easily as a matter of fact. :) --Gregg

Hi Ammon, << That doesn't tell me a whole lot. ;-( >> Don't sweat it then. :) I'll elaborate more in the future. --Gregg

Hi Gregg, AFAIR, Joel wrote some sort of a state machine dialect some time ago. It might be a tough competition for PARSE.

> -----Original Message----- > From: [rebol-bounce--rebol--com] [mailto:[rebol-bounce--rebol--com]]On Behalf Of > under-utilized (kind of like REBOL). Those that use them, love them; those > that don't, just don't know what they're missing. :)

<< AFAIR, Joel wrote some sort of a state machine dialect some time ago. It might be a tough competition for PARSE. >> Ahh, I probably caused some confusion when I responded to Ryan saying Ryan: "Seems that a FSM dialect that feeds into parse could implemented pretty easy, from my laymans perspective anyhow." What I meant was that I use parse to *create* the dialect (naturally). I.e. I feed my dialect to parse. I'm not outputting anything to parse. Hmmmm. I think I'm just digging myself in deeper here. :) --Gregg

Nevertheless, a well designed FSM dialect could become a parse alternative/supplement, couldn't it? Happy digging. Have you got an idea what would you prefer the dialect to look like? ...

I know what you mean. The closer I looked at it, parse is not a good fit for the parallel aspect of FSM's. A recursive 'switch should work, but I would prefer to emulate recursion--REBOL can only recurse just over 3000 times. I would like to see Joel's code. --Ryan Gregg Irwin wrote:

> << AFAIR, Joel wrote some sort of a state machine dialect some time ago. It > might be a tough competition for PARSE. >> > [rebol-request--rebol--com] with "unsubscribe" in the > subject, without the quotes.

Hi Robert, << I would suggest to go for petri-nets (IIRC it's a more general concept to a FSM?), which let you model very complex event systems in a nice and simple way. Local development view = global working system :-)). >> I don't know if I'd say more general, but they are a different. I think the approach I'm working on could actually be used for them, but I have the FSM version working already so... :) --Gregg

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

On 03-Nov-01, Gregg Irwin wrote:

> Whew! Anybody still awake? :)

Hey Carl, << Oh yes! Very nice description, and it looks like it'll be a lovely dialect to have available. >> I hope so. Now let's see, what I need is some kind of app that requires a simulation or AI component to try it out... :) --Gregg

On Thursday 01 November 2001 07:14 pm, you wrote:

> Hi Gang, > > I'm a big fan of FSMs and, being the wacky guy I am, I got this idea for an > FSM "thing" in REBOL. My questions to you are: > > a) How many people here use, or have used, FSMs and would like to use > them in REBOL?

Interesting program, but a dialect is still preferable. --Ryan Bob Paddock wrote:

<SNIP> > > However you might want to take a look here first: > > http://www.imatix.com/html/libero/index.htm >

RE: [REBOL] Re: Any FSM fans? [greggirwin--mindspring--com] wrote:

> --Gregg

Hi Bob, I looked briefly at Libero not too long ago but I'm aiming for something different than they are. There are some things we have in common, like being able to specify multiple actions for each transition. Something I like about the REBOL approach (though I'm not sure yet where it might also get me into trouble) is that you can enter a block of plain old REBOL code as your action and it will execute it. Another thing both do is allow you to define a special "default" state that you can use to simplfy your design. A big difference is that their stuff generates a driver that is wrapped around the STT (if I recall correctly). Once I get the core where I want it, I'll look at putting different drivers around it, but I also want to make it useable as *part* of an app, not just as the main processing loop. Libero may do this as well. Not sure. << How do I use Libero? Design your program visually as a state diagram; >> Is this in the Windows version? I DL'd the Windows version and, while it has a GUI for defining your state machine, it doesn't let you draw a state diagram in the true sense. I haven't looked at it in enough detail to know what I might have missed, but I didn't grok it immediately. << Choose your programming language; >> I don't envision my stuff being used with languages other than REBOL, but there's no reason you couldn't use it to drive a code generator. Lots of stuff can be built up around the core concept. Is the core concept sound? That's the first thing I need to find out. << Generate a framework for your program; Fill-in the framework to get from rapid prototype to working program; Repeat until your program is perfect. >> So Libero is smart enough not to touch your code. That's cool. Do you have to put your own code someplace special or is your code entertwined with the generated code? << What Languages can I use? >> I have to admit that I'm a fairly biased developer when it comes to languages. I am data agnostic, but I've always written my tools to work well for a specific target language. I've written a number of code generators over the years and the quality of the code they generate is directly related to the quality of the code I could write, by hand, for any given language. In this case, one of my main goals is *not* to generate code. :) <<... with open-ended support for other languages. Like Rebol? :-) >> Yeah, but writing a Libero schema would have been more work, and the result would be far less REBOLish. :) Since you've got experience with Libero, and said you would like to use FSMs in REBOL, would you be interested in looking at what I've got and giving me some feedback? Thanks! --Gregg

Hello Gregg! On 02-Nov-01, you wrote: Just a note, GI> switch state [ GI> locked [ GI> switch event [ GI> coin [ GI> do-unlock GI> state: unlocked GI> ] GI> pass [ GI> alarm GI> state: locked GI> ] GI> ] GI> unlocked [ GI> switch event [ GI> coin [ GI> do-lock GI> state: locked GI> ] GI> pass [ GI> thank-you GI> state: unlocked GI> ] GI> ] GI> ] An efficient way to do this in REBOL (which I used in the past to implement FSMs) could be the following: states: context [ locked: context [ coin: does [ do-unlock state: unlocked ] pass: does [ alarm ; redundant, could be avoided state: locked ] ] unlocked: context [ coin: does [ thank-you ; redundant, could be avoided state: unlocked ] pass: does [ do-lock state: locked ] ] ] state: states/locked ; ... state/coin ; etc... GI> Whew! Anybody still awake? :) Yup. ;-) Regards, Gabriele. -- Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/

Hi Volker, So, would you like to critique it and give me some feedback? Thanks! --Gregg

Thanks Gabriele! << An efficient way to do this in REBOL (which I used in the past to implement FSMs) could be the following: >> This kind of information is invaluable! Something people often overlook when writing tools, in my experience, is what the *calling* code will look like. You may design an elegant set of objects or functions, but then the user has to jump through hoops to make them work. Looking at things from the user's perspective is important. --Gregg

RE: [REBOL] Re: Any FSM fans? [greggirwin--mindspring--com] wrote:

> Hi Volker, > > So, would you like to critique it and give me some feedback? >

> Thanks! > > --Gregg

Hi Volker, << would it be possible to compile your dialect in Gabrieles objects, like vid compiles to faces? >> Yes. I just whipped up a little code generator for it, so it will generate the code in Gabriele's format. Generating objects directly shouldn't be a problem. It just means figuring out how we want to use these things so we know what to generate while minimizing redundancy. I.e. can I generate a single format that can be used for multiple purposes? If I write out formatted REBOL code, how do I make it easy to use the result with load, read, etc., whether in the same interpreter session, or loaded from disk? Something to keep in mind, and one of the reasons behind my design, is how REBOL creates objects. Since it clones them, you probably want to use that approach only when you have a small number of state machines (which will be the normal case). State Machine are now often being used to drive the AI in games. In those cases, you may have hundreds, or thousands of objects. In that scenario, you probably want to separate the state variable(s) from the state table they use. --Gregg

RE: [REBOL] Re: Any FSM fans? Hi Gregg, [greggirwin--mindspring--com] wrote:

> Hi Volker, > << would it be possible to compile your dialect in Gabrieles objects, like > formatted REBOL code, how do I make it easy to use the result with load, > read, etc., whether in the same interpreter session, or loaded from disk?

> Something to keep in mind, and one of the reasons behind my design, is how > REBOL creates objects. Since it clones them, you probably want to use that > that scenario, you probably want to separate the state variable(s) from the > state table they use.