* State Machine Implementation @ 1998-08-05 0:00 Ray A. Lopez 1998-08-06 0:00 ` Matthew Heaney ` (4 more replies) 0 siblings, 5 replies; 8+ messages in thread From: Ray A. Lopez @ 1998-08-05 0:00 UTC (permalink / raw) Does anyone have any implementions of a state machine? The states would be just an enumerated type and I am guessing you would use a case statement. Just looking for more info on how to implement this using Ada. thanks... ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: State Machine Implementation 1998-08-05 0:00 State Machine Implementation Ray A. Lopez @ 1998-08-06 0:00 ` Matthew Heaney 1998-08-06 0:00 ` State Machine Implementation (long) dana ` (3 subsequent siblings) 4 siblings, 0 replies; 8+ messages in thread From: Matthew Heaney @ 1998-08-06 0:00 UTC (permalink / raw) "Ray A. Lopez" <rdsys@inficad.com> writes: > Does anyone have any implementions of a state machine? The states would > be just an enumerated type and I am guessing you would use a case > statement. Just looking for more info on how to implement this using > Ada. I prefer to implement a state machine using labels and gotos. That's how I usually write tasks. For example: task body IO_Manager is Mode : Missle_Mode; begin <<Idle>> null; select accept Start; or accept Stop; goto Idle; or terminate; end select; <<Main>> null; select accept Change_Mode (Mode : Missle_Mode) do IO_Manager.Mode := Mode; end; <transmit mode> <make asynchorous read> <<Waiting_For_Response>> null; select accept IO_Completion; goto Main; or accept ...; goto Waiting_For_Response; ... Scanners typically have a state-machine implementation. I just wrote a scanner to parse real literals that weren't quite in legal Ada format, using gotos to skip over optional parts of the lexical expression. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: State Machine Implementation (long) 1998-08-05 0:00 State Machine Implementation Ray A. Lopez 1998-08-06 0:00 ` Matthew Heaney @ 1998-08-06 0:00 ` dana 1998-08-06 0:00 ` Tarjei Tj�stheim Jensen 1998-08-06 0:00 ` State Machine Implementation dennison ` (2 subsequent siblings) 4 siblings, 1 reply; 8+ messages in thread From: dana @ 1998-08-06 0:00 UTC (permalink / raw) In article <35C90369.CFE8ED98@inficad.com>, "Ray A. Lopez" <rdsys@inficad.com> wrote: > Does anyone have any implementions of a state machine? The states would > be just an enumerated type and I am guessing you would use a case > statement. Just looking for more info on how to implement this using > Ada. > > thanks... That's the approach everyone starts with. One enumeral type for the states, and one for the events which drive the thing. But then things get complicated. If you have case statements, the number of possibilities are n (states) times M (events), then some jerk wants to add new states and events after you've just got the thing coded up. This works for the text book trivial case. case Current_State is when S_1 => case The Event is when E_1 => ... Many events when E_N => end; when S_2=> case The_Event -- do it all over again end; end; This gets double nuts when you have to have cases for the coarse AND destination states for the appropriate action code. This model falls apart with substates, and lots of conditions which restrict when an event actually causes a transition between states, Event (tune knob) does NOT cause the state to transition to OPEN if Dead_Bolt=Set. Then there's the problem of which "action: code gets executed on ANY entry to a state and which gets run only when traversing from a particular state. I once spent 4-6 months on a project (How long was it Stephe?) while we beat our heads on an incredibly complex state machine and all kinds complexities with dozens of states, events, and special cases. Not pretty. I was so horrified by this experience that the next time I had to work on a project with big state machines I wrote a state machine module where I defined the following classes (it was in C++ but should be easily doable in Ada95): State Event Transition Condition State_Machine Super_State Action Here are their descriptions State had a list of its exit transitions, entry condition, entry action, exit action. The one thing which you had to get over with this model was that you could not do something like "do this while in this state" if you wanted to do something on a regular basis while in a state, then you had to have a tick event handled by a tick transition whose action was to do think stuff which was to be done regularly. Event These were the thingies (and the only thingies) which made the state machine show signs of life. No event, no transitions, no actions, no outward signs of intelligence. I had the events carry pointers to user supplied data like X/Motif events do. For instance, the keypress event had event data (the key) and Transition Caused by an event, had a source and destination state, maybe a condition, maybe an action) Transitions are different than events because a single event can be tied to multiple transitions. Condition This called a user supplied function which returned a true/False result. Used to enforce special rules which did not warrant an extra state. Or for that matter, could make use of the current state of other state machines. State_Machine The class which contained everything. You had one instance of this class for every state machine your system had. It could print itself out so that you could actually see EXACTLY how your machine was going to be implemented. To make your program go, you would hand events to a member function of this class. The handle event function caused everything to happen from there. Because this was done in a true object oriented fashion, the handling of an event could cause the stack to wind up through 15-25 function calls until the action actually occurred. Super_State A cross between state_machine and state. These are extremely handy. They reduce the possible number of combinations by allowing a single event/transition take the machine out of one of many sub-states. These also offered the possibility of memory (when you re-enter a superstate with memory, it immediately goes into the last sub-state it was in. There were lots of fine points on the behavior of super-states and tier sub-states which I managed to dodge the bullet and leave hanging. Action This was just a container for a pointer to a function. Now possible in Ada95 as well as C. This was the only way for an event to cause an externally visable response from the state machine. ----------------------------------------------------------------------------- I wrote this almost 4 years ago and was quite impressed with myself. Did I manage to re-invent the wheel? I know there are template classes for directed graphs, but I think this goes well beyond that. We used this tool in loads of places where the state machine code could have been a bear. We used it in a few instances where it was arguable that the enumeral/case thing was sufficient but the thread of a new state, event, transition, or action being added was real. The State Machine class had a few cool things about it, it could be set to print out a trace of the processing which occurred when an event was handled. It could also report on its state. With super-states, the state of a state machine was not a simple enum answer. If you were two or three levels into superstates the answer looked more like: Surfing:News_Reading:Posting:Babling_Incoherantly Anything which might ask the current state should be ready for a non-simple answer. I've always wanted to code somthing like this up in Ada95. I would make State_Machine limited private and get rid of all the recurse and descend sillyness of the C++ version. I want to add a queuing mechanism for inbound events, and maybe event priorities. I see places were a software state machine which could also be configured from a config file would be extremely nice for maintenance purposes. I have no idea on how to handle the action routine accesses except for a compile time lookup table. With some work, the performance of such a system could approach that of an enum/case monster and I would think the improved provability/observability would be well worth the performance hit. For Q/A and testing purposes, you could substitute dummy bodies for the action routines and conditions, and feed events into the machine and observe the reaction in a bench test. You might even add a capability to jam load the machine with a particular, hard to reach state, and feed it events to test event/response type requirements. "The system SHALL, while in the RANTING state, POST_SILLY_STUFF when ever a SILLY_URGE event occurs". Anybody else with state machine experience out there with two cents to toss in? ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: State Machine Implementation (long) 1998-08-06 0:00 ` State Machine Implementation (long) dana @ 1998-08-06 0:00 ` Tarjei Tj�stheim Jensen 0 siblings, 0 replies; 8+ messages in thread From: Tarjei Tj�stheim Jensen @ 1998-08-06 0:00 UTC (permalink / raw) dana@indyweb.no.xyz.spam.net wrote in message ... >I see places were a software state machine >which could also be configured from a config file would be extremely nice >for maintenance purposes. I have no idea on how to handle the action >routine accesses except for a compile time lookup table. Plauger's Standard C library uses such state machines for character comparison and classifications. It is quite clear that such a thing would be very nice to have around. Greetings, ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: State Machine Implementation 1998-08-05 0:00 State Machine Implementation Ray A. Lopez 1998-08-06 0:00 ` Matthew Heaney 1998-08-06 0:00 ` State Machine Implementation (long) dana @ 1998-08-06 0:00 ` dennison 1998-08-06 0:00 ` John M. Mills 1998-08-06 0:00 ` Robert Dewar 1998-08-11 0:00 ` Bill Meahan 4 siblings, 1 reply; 8+ messages in thread From: dennison @ 1998-08-06 0:00 UTC (permalink / raw) In article <35C90369.CFE8ED98@inficad.com>, "Ray A. Lopez" <rdsys@inficad.com> wrote: > Does anyone have any implementions of a state machine? The states would > be just an enumerated type and I am guessing you would use a case > statement. Just looking for more info on how to implement this using > Ada. I just finished a lexical analizer, and that's how I did it. There are some folks here who feel like goto's are more straighforward for that purpose, though. T.E.D. -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: State Machine Implementation 1998-08-06 0:00 ` State Machine Implementation dennison @ 1998-08-06 0:00 ` John M. Mills 0 siblings, 0 replies; 8+ messages in thread From: John M. Mills @ 1998-08-06 0:00 UTC (permalink / raw) >In article <35C90369.CFE8ED98@inficad.com>, > "Ray A. Lopez" <rdsys@inficad.com> wrote: >> Does anyone have any implementions of a state machine? The states would >> be just an enumerated type and I am guessing you would use a case >> statement. Just looking for more info on how to implement this using >> Ada. I would consider something like: type Handlers is array(STATE) of access function(...) return STATE; (give or take the grammar, sorry). Each handler is associated with one state. Each handler performs what action it can, then determines if the machine's state has changed, returning the appropriate new or old value of STATE, which is used as the call index on the next iteration. Advantages: clean logic from outside the machine, and no massive case branch or decision tree. State handlers are totally decoupled from one another. Disadvantage: no externally obvious logic flow. -- John M. Mills, Senior Research Engineer -- john.mills@gtri.gatech.edu Georgia Tech Research Institute, Georgia Tech, Atlanta, GA 30332-0834 Phone contacts: 404.894.0151 (voice), 404.894.6258 (FAX) "Lies, Damned Lies, Statistics, and Simulations." ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: State Machine Implementation 1998-08-05 0:00 State Machine Implementation Ray A. Lopez ` (2 preceding siblings ...) 1998-08-06 0:00 ` State Machine Implementation dennison @ 1998-08-06 0:00 ` Robert Dewar 1998-08-11 0:00 ` Bill Meahan 4 siblings, 0 replies; 8+ messages in thread From: Robert Dewar @ 1998-08-06 0:00 UTC (permalink / raw) <<Does anyone have any implementions of a state machine? The states would be just an enumerated type and I am guessing you would use a case statement. Just looking for more info on how to implement this using Ada. >> A case statement is possible certainly, and it is hard to know exactly what you mean by "an implementation", since this is the sort of thing that occurs all the time in a programs, and the application dependent details are 95% of the code anyway. Note that an alternative, probably more efficient, and for many people more readdable way of coding a finite state machine in languages like Ada is to use a label on each state, and goto's to effect state transition, thus efficiently encoding the state in the program counter. Some people have this silly allergy to goto's (a case of understanding an important principle without really understanding it), but in fact this is for many programmers one of the very few legitimate uses of gotos. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: State Machine Implementation 1998-08-05 0:00 State Machine Implementation Ray A. Lopez ` (3 preceding siblings ...) 1998-08-06 0:00 ` Robert Dewar @ 1998-08-11 0:00 ` Bill Meahan 4 siblings, 0 replies; 8+ messages in thread From: Bill Meahan @ 1998-08-11 0:00 UTC (permalink / raw) See http://www.imatix.com Look at Libero - a _really_nice state machine package. No Ada code generator schema currently but it should be relatively easy to write and maybe Peter at Imatix will write one for you. Free software to boot! Ray A. Lopez wrote: > > Does anyone have any implementions of a state machine? The states would > be just an enumerated type and I am guessing you would use a case > statement. Just looking for more info on how to implement this using > Ada. > > thanks... -- Bill Meahan wmeahan@ford.com Ford Motor Company -- Ford Systems Integration Center Not an official statement of Ford Motor Company or anyone else except the author. ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~1998-08-11 0:00 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1998-08-05 0:00 State Machine Implementation Ray A. Lopez 1998-08-06 0:00 ` Matthew Heaney 1998-08-06 0:00 ` State Machine Implementation (long) dana 1998-08-06 0:00 ` Tarjei Tj�stheim Jensen 1998-08-06 0:00 ` State Machine Implementation dennison 1998-08-06 0:00 ` John M. Mills 1998-08-06 0:00 ` Robert Dewar 1998-08-11 0:00 ` Bill Meahan
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox