Thomas Huining Feng  

Introduction

To give a living example of this, I implement a CD player from a statechart, and in this way I explore the general way to implement statecharts. Of course, as I mentioned in previous sections, the statechart itself is not rigorously defined in UML. To implement the CD player, I have to make assumptions. It is because of these assumptions that a model given by statechart is not universal -- a model may run quite well in a particular system, while it is unaccepted by another.

Some assumptions

My assumptions at least include the following:

Because the implementation is done in Python, I assume the properties of python: interpretive language, ability in recursion, short-circuit left-to-right boolean evaluation, weak type-checking, and so on. More over, because a model has to invoke methods in other objects, which do not fall in the scope of the model itself, I assume all the python modules are available (which turns out to be entirely impossible in another language). In this way, the condition (guard) and output of a transition depend heavily on python in that the condition can be any python boolean expression(s), and the output can be any sequential list of python commands.

For the computer to manipulate the model (to design or modify it, to put it in a larger model by composition, to execute it, and so on), I assume the textual representation of a model, which is written in a single file in a specific format. I myself define the format, and it is not likely that any other simulator would agree with my idea. Fortunately, my format is so flexable that one can easily convert a textual model and a graphical one back and forth.

Download release v0.1

Before we start detailed discussion in the subject, if you are interested, you may want to download the program and have a look at what I have done first.

In order to run my program, you have to install the python interpretor and pygame library.

The source code for my general simulator and the description for the CD player statechart is here.

The python interpretor can be downloaded from the python website.

The pygame library on which my model is built can be downloaded from the pygame website.

If you don't want to border with installing all these things, and if you are running Win32 system, there's an alternative for you.

The Win32 executable with all the required libraries is here (no installation required).

Brief explanation of usage

In the source code package there are five files: CDPlayer.py (class EventHandler, class Clock and a simulator), CDPlayer.des (the self-contained statechart description file), CDHardware.py (class CDHardware built above pygame to control CD-Rom and raise hardware events), CDPlayerGUI (class CDPlayerGUI to interact with the end user and raise GUI events) and Debugger (class Debugger).

If you run the program in python, just execute CDPlayer.py; if you use the Win32 executable version, CDPlayer.exe starts the program. Then you can see the CD player interface which may intrigue you to test its function. If you find bugs in it, please be kind enough to inform me.

No matter which state the CD player is in, pressing "d" on the keyboard will bring you to the debug mode (in the textual window). It is a python interpretor. Particularly, you may be interested in doing these:

Type in "eventhandler.state" to check the current state of the CD player at any time.

Type in "eventhandler.ShowStateH()" to read the internal representation of the statechart hierachy.

Type in "eventhandler.ShowTransitions()" to read the internal representation of transitions (don't be surprised by the output size).

If you have multiple CD-Roms, type in "eventhandler.ChangeCDRom(i)" where i is an integer changes the control of the CD player to another CD-Rom. For the first CD-Rom in your computer, i=0; for the second, i=1; and so forth.

Type in "exit" to leave debug mode.

Statecharts

The textual statechart is graphed in a more readable form.

CD player statechart

"Started.CDIn" substate

"Started.CDIn.Playing" substate

"Started.CDIn.Stopped" substate

"Started.CDIn.Paused" substate

"Started.CDIn.Paused.Normal" substate

Special thanks: part of the work is done by Simon Hinwai So.

Brief explanation of the algorithm

The most interesting part is in class EventHandler. It takes up the task to interpret the textual statechart model and carry out transitions between states during the evolution (execution).

When the class is instantiated, it reads in a description file, and converts the definition of statechart hierachy and transitions into an internal representation (which you can easily check with the above-mentioned methods). In this internal representation, python lists and dictionaries are involved.

The scheme for this process is very straightforward, except some important points which one should pay attention to:

A certain state is given by a "." notation, i.e. "StateA.StateB.StateC". The representation of state hierachy should be flexible enough so as to locate all the components of a state, and also find the default substate (or subsubstate as well) in it.

Note: states named "StateA", "StateB" and "StateD" may have other substates and deeper levels of hierachy, while "StateC" mustn't, otherwise "StateA.StateB.StateC" is not a valid internal representation, and must be replaced by some other.

A state has at least three predefined properties: default, concurrent and final. Among all the substates of a state, at most one can be denoted as default (by a "*" behind it's name); if a substate is denoted as concurrent (by a "&" behind it's name), all its sibling substates should also be concurrent; in a statechart, one can denote as many states as he/she likes (by "!" behind their names) as final states.

Sorting. It doesn't matter in which order the designer puts various transitions in the description file; but it does matter in which order they are stored in memory when the simulator runs the model, especially when the event handler blindly finds the first enabled transition and fires it. In my implementation, when multiple transitions are enabled when an event occurs, the one starting from the outmost state is fired, and the others do not notice this event. In this sense, when the EventHandler reads in the file, it automatically sorts transitions by the levels of their starting states.

Grouping. The performance of the event handler should be taken into account. Because of the general scheme, there is essentially only one eventhandler, which accepts a string parameter as the name of a certain event. If every time an event occurs the event handler looks up the whole transition table, it is not efficient and even wasting. So, on reading in the description, EventHandler groups the transitions by their associated events, and puts them in a python dictionary. In this way they can be looked up very quickly.

After loading the file, the simulator automatically places the model in an initial state. By the word state here I actually mean a set of states, because the probable existance of concurrency. This state is easily found in the given state hierachy. Once the simulator raises the initial event, so called "Start" or whatever else, the first transition is fired, which moves the model to a new state.

Be aware that this is the only event that the simulator can raise. Other events come from the interaction among different models and objects, where the simulator, as an inspector, never participates.

In the process of execution, there're also some important points to be highlighted:

Events may come from different sources simultaneously. The event handler should not be interrupted while it is handling an event by another. A semaphore is extremely important in this case.

In the output of a transition, a new event may be raised. One can do this by directly calling the event function in EventHandler. Theoretically this call should be the last output command for this transition; practically this call must be so no matter where the designer places it, because the semaphore disables the event function until the transition finishes.

In the current implementation of the CD player, the event handler does nothing to a final state: it is just treated the same as other states. It is the statechart designer's task to explicitly write code in the output of all the transitions to the final state to finalize the simulation (in this case, by calling the destroy function of the GUI object). This is not because of simple-mindedness -- a general event handler does not always know how to finalize the model, which is the designer's task. He may as well want to output some statistics data or release some resources on exit. In this light, one may choose never to put a "!" behind a state, though they know it to be final; but of course it is not a good habit.

Cliche on hardware control

The discussion on the hardware is not entirely uninteresting. Our statecharts are event-driven, while most of the hardware doesn't support events, and even if it does, from time to time it doesn't know how to invoke our event handlers or the events it raises may not satisfy our requirement. In these cases, we have to build hardware wrappers.

A wrapper is a module one level upper than the hardware library. This layer hides the direct hardware control from models. It also takes up the job of tailoring the function provided by the library: when the library cannot raise events, it checks the state of the hardware periodically and raise those events; when the library provided too limited functions, it must compose new ones from what is given.

In my CD player implementation, the wrapper runs in the background as a thread, which checks the state of the CD-Rom every 0.1 second. It takes up the task to report all the changes in the hardware states at any time. For instance, if in the last routine checking the CD is playing, and it is found to be stopped at this time, a so-called "Hardware Stopped" event is raised by this thread.

Opposed to hardware events, GUI events are raised directly from the interaction between the user and the graphical interface. So, one may expect the different between the events "GUI Stop" and "Hardware Stopped".

An important point to be noted is that the wrapper scheme is usually employed, when we strictly want our model to be event-driven, while the implementation of hardware doesn't take events into account.

Another subtlty accounts for timing. One may be eager to directly act on the hardware whenever he/she wants to. In the above example, when the "GUI Stop" event is detected, the designer wants to stop the CD playing by calling the stop method from the hardware library, and after that the "Hardware Stopped" event is expected. But I'm sure though this scheme works at most time, it is not always so. The reason is not so easy to discover unless the designer is familiar with milti-threading.

Don't forget the wrapper thread which checks the hardware every 0.1 second. If we are employers, the wrapper is the best employee, who never neglects his work! When we render a direct call to the hardware library, and at the same time the wrapper is performing his work, the hardware will be quite confused: it is not designed to be re-enterable.

This means that once you wrap, your wrapper must be perfect. It must completely hide the hardware interface, while providing another sufficiently broad interface to upper levels. To stop the CD, the model must call the stop function from the wrapper, and the wrapper must inform the thread and syncronize with it. The simplest way is to set a flag called "stop_received" and wait for the thread itself to stop it in the next routine checking. (0.1 second delay is imperceptible.)


Maintained by Thomas Feng, Winter 2002