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

Any FSM fans?

 [1/30] from: greggirwin::mindspring::com at: 1-Nov-2001 17:14


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

 [2/30] from: james:mustard at: 2-Nov-2001 13:19


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

 [3/30] from: ammonjohnson:ya:hoo at: 1-Nov-2001 18:25


What is FSM? Thanks!! Ammon

 [4/30] from: greggirwin:mindspring at: 1-Nov-2001 17:34


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

 [5/30] from: alans:cuervo:stanford at: 1-Nov-2001 16:30


[Charset iso-8859-1 unsupported, filtering to ASCII...]
> umm... what's a FSM? :-P
I knew if I waited long enough, somebody else would ask first...;^)
> james >
--Alan <[alans--cuervo--stanford--edu]>

 [6/30] from: gschwarz:netconnect:au at: 2-Nov-2001 11:33


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

 [7/30] from: ryanc:iesco-dms at: 1-Nov-2001 16:36


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
<<quoted lines omitted: 34>>
> [rebol-request--rebol--com] with "unsubscribe" in the > subject, without the quotes.
-- Ryan Cole Programmer Analyst www.iesco-dms.com 707-468-5400

 [8/30] from: ammonjohnson:y:ahoo at: 1-Nov-2001 18:50


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

 [9/30] from: alans:cuervo:stanford at: 1-Nov-2001 16:52


[Charset iso-8859-1 unsupported, filtering to ASCII...]
> Hi James, > > << umm... what's a FSM? :-P >> > > Finite State Machine.
oh!...duh!...yes, that does sound pretty REBOLable, doesn't it?...
> --Gregg > -- > To unsubscribe from this list, please send an email to > [rebol-request--rebol--com] with "unsubscribe" in the > subject, without the quotes. >
--Alan <[alans--cuervo--stanford--edu]>

 [10/30] from: greggirwin:mindspring at: 1-Nov-2001 18:04


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

 [11/30] from: greggirwin:mindspring at: 1-Nov-2001 18:15


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

 [12/30] from: lmecir:mbox:vol:cz at: 2-Nov-2001 9:18


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

 [13/30] from: robert:muench:robertmuench at: 2-Nov-2001 9:38


> -----Original Message----- > From: [rebol-bounce--rebol--com] [mailto:[rebol-bounce--rebol--com]]On Behalf Of
<<quoted lines omitted: 6>>
> under-utilized (kind of like REBOL). Those that use them, love them; those > that don't, just don't know what they're missing. :)
Hi, right! 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 :-)). Robert

 [14/30] from: greggirwin:mindspring at: 2-Nov-2001 2:40


<< 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

 [15/30] from: lmecir:mbox:vol:cz at: 2-Nov-2001 11:31


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? ...

 [16/30] from: ryanc:iesco-dms at: 2-Nov-2001 9:42


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. >>
<<quoted lines omitted: 10>>
> [rebol-request--rebol--com] with "unsubscribe" in the > subject, without the quotes.
-- Ryan Cole Programmer Analyst www.iesco-dms.com 707-468-5400

 [17/30] from: greggirwin:mindspring at: 2-Nov-2001 10:50


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

 [18/30] 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

 [19/30] from: carl:cybercraft at: 3-Nov-2001 10:05


On 03-Nov-01, Gregg Irwin wrote:
> Whew! Anybody still awake? :)
Oh yes! Very nice description, and it looks like it'll be a lovely dialect to have available. -- Carl Read

 [20/30] from: greggirwin:mindspring at: 2-Nov-2001 15:16


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

 [21/30] from: bpaddock:csonline at: 2-Nov-2001 18:34


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?
Yes. However you might want to take a look here first: http://www.imatix.com/html/libero/index.htm How do I use Libero? Design your program visually as a state diagram; Choose your programming language; Generate a framework for your program; Fill-in the framework to get from rapid prototype to working program; Repeat until your program is perfect. What Languages can I use? ANSI C PHP Java C++ Perl Awk UNIX shells - Korn shell, BASH, Bourne shell, C shell Rexx MS Visual Basic MS Test Basic COBOL PL/SQL MS 80x86 Assembler ... with open-ended support for other languages. Like Rebol? :-)

 [22/30] from: ryanc:iesco-dms at: 2-Nov-2001 16:13


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 >
</SNIP>

 [23/30] from: nitsch-lists:netcologne at: 3-Nov-2001 3:46


RE: [REBOL] Re: Any FSM fans? [greggirwin--mindspring--com] wrote:
<great stuff about FSM-dialect>
now yes :-) interesting! btw Holger mentioned he builds async protocols based on state-machine too?
> --Gregg
-Volker

 [24/30] from: greggirwin:mindspring at: 2-Nov-2001 21:25


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

 [25/30] from: g:santilli:tiscalinet:it at: 3-Nov-2001 15:20


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/

 [26/30] from: greggirwin:mindspring at: 3-Nov-2001 10:05


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

 [27/30] from: greggirwin:mindspring at: 3-Nov-2001 12:08


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

 [28/30] from: nitsch-lists:netcologne at: 4-Nov-2001 1:13


RE: [REBOL] Re: Any FSM fans? [greggirwin--mindspring--com] wrote:
> Hi Volker, > > So, would you like to critique it and give me some feedback? >
Hmm, i just beginning being a fan. no qualified coments yet ;-) would it be possible to compile your dialect in Gabrieles objects, like vid compiles to faces?
> Thanks! > > --Gregg
-Volker

 [29/30] from: greggirwin:mindspring at: 4-Nov-2001 13:32


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

 [30/30] from: nitsch-lists:netcologne at: 6-Nov-2001 4:02


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
<<quoted lines omitted: 6>>
> 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?
yes, that was was made me wake again :-) your dialect seems to express FSM's well, while i usually read "this are the concepts" wow short and here is a code-sample ugh..
> 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
<<quoted lines omitted: 3>>
> that scenario, you probably want to separate the state variable(s) from the > state table they use.
seen in view-faces and protocolls: instead of using functions in objects, objects contain a special function-object like /feel or /handler. because its an object, it is not copied by make, so all faces or ports of a kind can share their functions while seperating their data. drawback is, on calls one has to pass the object as argument, as you see in the various /feel-functions. but with a dialect most of that [face/action face ..] uglity can be hidden. in layouts for example the action is simply a block, and vid makes [action: func[face..]arg-block] from it. nice feature: if you change the feel or handler, you change the behaviour of the object. since with functions [open read close] one can start with a handler accepting 'open and throwing errors on everything else, after open change handler forbidding open and allowing [read close]. in a way this works like a little state-machine :-) could this be helpfull with a larger amount of state-machines? -Volker

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted