From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00, T_FILL_THIS_FORM_SHORT autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,b45952e5dedb7e9a X-Google-Attributes: gid103376,public From: dana@indyweb.no.xyz.spam.net Subject: Re: State Machine Implementation (long) Date: 1998/08/06 Message-ID: X-Deja-AN: 378441125 References: <35C90369.CFE8ED98@inficad.com> Organization: Indy Web Inc. Newsgroups: comp.lang.ada Date: 1998-08-06T00:00:00+00:00 List-Id: In article <35C90369.CFE8ED98@inficad.com>, "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... 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?