Effective UML mapping for modeling state machines - Embedded.com

Effective UML mapping for modeling state machines

Many concurrent, distributed and real-time applications have to tightlywork with other objects or hardware, called service providers. Aservice is formally specified by a set of primitives (operations)available to service users (applications).

These primitives describe some action or report on an action to beperformed by a peer component/entity. The service primitives can beclassified into four categories: request, indication, response andconfirm[1].

It is natural to use state machines for modeling these applications,as an application that must carry out a series of actions, or handleinputs (responses and indications) differently depending on what stateit's in, is often best implemented as a state machine.

State machine modeling technology for these software developmentsprovides users a visual, dynamic view in design and implementationsteps, greatly improving development efficiency and curtailingdevelopment cycles.

Through this modeling, we can mainly benefit in two ways:readability, which enables a clear system description by capturing theinternal structure and external behaviors of a system; reusability,which makes a system's code be easily reused in some other similarprojects/objects.

While there are already many good UML tools such as RationalRose, VisualStateand others, this paper proposes a new feature of round-tripengineering support. An important rule in software design is that nodesign remains unchanged.

This is as true for small systems as it is for large systems. Duringdevelopment, the design structure defined in the UML model does undergochanges to incorporate physical differences in implementation that maynot have been envisaged during design. It becomes very difficult tokeep the design of the system updated with the changes in the sourcecode.

Most of the preceding related work has been focused on UML diagramdrawing and code generation, or, in other word, one-way mapping. Weconsider two-way approach to mapping between state chart and executablesource code. Our solution tends to enforce the UML tool's capability ofsynchronizing its model according to modification in code part inreal-time.

For example, developers can visually do a drag-and-drop operation instate chart diagram and subsequently the source code would change aswell; to the contrary, developers may directly rectify the code partwhile modification will be automatically shown in state chart diagram.It can be seen that the solution is two-way between state chart diagramand source code.

Our study is mainly based on our open source project, UMLStateWizard [3] , which bringsout an alternative view in rapid development based on round-tripengineering theory.

StateWizard aims at not only being a model or code generation tool,but also being a full-featured UML dynamic model tool with reverseengineering and round-trip engineering features. It models program withthe State Charts or the State Tree, on the other hand, it synchronizesthe model with the changes in the application code in the stages ofsoftware design and coding.

Just like VisualC++ ClassWizard, StateWizard runs inside the popular IDE(integrated development environment). No need to switch between toolsfor design/development, while many other UML model tools run standalone. It rapidly builds applications with state machine basedframeworks and efficiently codes state charts directly inplatform-independent standard C/C++, as well as provides statetracking, simulation and debugging for embedded system development.

In this article we study the state modeling problems related withmapping, in particular, the problem of efficient code generating, givena mapping between the state machines and the source code, and ofrebuilding state machines through this mapping.

While the techniques we describe are, at a high-level, intuitive,the main contributions of the paper are the techniques we developed toapply mapping between state chart and source code to rapid development,and the experimental study of their practical impact. All put together,our mapping techniques speed up application development, therebyenabling efficient development on projects of significant size.

Concepts of Hierarchical StateMachine
In general, a hierarchical state machine (HSM)[4] is any device that stores thestatus of something at a given time and can operate on input to changethe status and/or cause an action or output to take place for any givenchange. A hierarchical state machine should include the followingelements:

* A set ofhierarchical state
* An initial state or record ofsomething stored somewhere
* A set of input events
* A set of outputevents
* A set of actionsor output events that map states and input to output (called a stateevent handler)
* A set of actionsor output events that map states and inputs to states (called a statetransition)

Overview of Traditional Approaches
Considerable work has been done on implementing a hierarchical statemachine in programming languages. The most common technique toimplement a state machine is the doubly nested switch statements with a”scalar variable” used as the discriminator in the first level of theswitch and event-type in the second level [4][5].

This works well for classical “flat” state machines and is widelyemployed by automatic code synthesizing tools. Manual coding ofentry/exit actions and nested states is, however, cumbersome, mainlybecause code pertaining to one state becomes distributed and repeatedin many places, making it difficult to modify and maintain when thetopology of the state machine changes.

Another technique is the object-oriented “State” design technique,based on delegation and polymorphism [4][5]. States are represented assubclasses implementing a common interface (each method in thisinterface corresponds to an event). A context class delegates allevents for processing to the current state object. State transitionsare accomplished by changing the current state object (typicallyre-assigning one pointer).

This pattern is elegant but is not hierarchical. Accessing contextattributes from state methods is indirect (cannot use an implicitpointer) and breaks encapsulation. The addition of new states requiressub-classing and the addition of new events requires adding new methodsto the common interface. Also, it might suffer from efficiencyproblems.

Mapping Solution in StateWizard
Our implementation of the HSM pattern is, to some degree, throughaction-state tables containing typically sparse arrays of actions andtransitions for each state. Actions (including entry/exit, statereactions, and actions associated with transitions) are most commonlyrepresented as pointers to functions. Representing state hierarchy in aflat action-state table is sometimes cumbersome, and does not alwaysperceive the complete design.

We chose an easy-to-use problem where we define a series of macrosas state machine mapping data. This makes it possible for users totouch the state machine's building task without any pre-knowledge onthe internal implementation. On the other hand, these mapping data willbe parsed by StateWizard to construct state machines when source codefiles are loaded, modified.

Our mapping data are partitioned into: state enumerationdeclaration, event handler declaration, state event handler table,state tree definition and application variable definition.

The first two components are declarations used in header files whilethe remained ones are in source files. As the way ClassWizard in VisualC++ does, these mapping data need not manually created but doneautomatically by StateWizard. Furthermore, manual modification in codepart is permitted if it conforms to the syntax of mapping data.

Figure1: The Player application state chart

Figure 1, above , and Figure 2 below show the Playerapplication state chart/tree. The top super state of a state machinestate stands for an application, which encapsulates a group of childrenstates but has no parent. PowerDown and PowerUp statesare brothers while and PlayingPause states are children of Powerup . Thestate chart and the state tree can help you create and manage the statemachines for your program. You can construct state hierarchy, defineevent handlers and navigate through your source files, and more.

Figure2: The Player application state tree

State Enumeration and EventHandler Functions
These two structures are used in header files to declare states andtheir handler function respectively before we define them. As we do tokeep a good style in popular programming languages like C/C++ and Java,we should declare variable before we use it. State enumerationdeclaration intends to declare each state in the state machine. Forexample, we declare the Player application states and event handlers asbelow:

SME_BEGIN_STATE_DECLARE(Player)
/*{{SME_STATE_DECLARE(Player)*/
SME_STATE_DECLARE(Player)
SME_STATE_DECLARE(PowerDown)
SME_STATE_DECLARE(PowerUp)
SME_STATE_DECLARE(Playing)
SME_STATE_DECLARE(Pause)
SME_MAX_STATE(Player)
/*}}SME_STATE_DECLARE*/
SME_END_STATE_DECLARE
/*{{SME_BEGIN_EVENT_HANDLER(Player)*/
intPlayerEntry(struct SME_APP_T *pApp, struct SME_EVENT_T *pEvent);
intPlayerExit(struct SME_APP_T *pApp, struct SME_EVENT_T *pEvent);
intOnPowerDownEXT_EVENT_ID_POWER (struct SME_APP_T *pApp, structSME_EVENT_T *pEvent);

/*}}SME_END_EVENT_HANDLER*/

State's Event Handler Table
This structure offers a whole definition of event handlers for eachstate. As discussed earlier when an event is dispatched, the statemachine should respond by executing corresponding event handler. Inaddition, such an event handler can be partitioned into two parts:entry/exit handler; normal event handler. An entry/exit handler has tobe performed at the time the state is entered/exited. However, a normalevent handler would be activated only when its specific event isdispatched. In our mapping, the former one is of the form:

SME_STATE_ENTRY/EXIT(handler name);

While the latter one is of the form:

SME_ON_EVENT(event name, handler name, belonged state name).

For example, we define the even handler table of the PowerUp stateas below:

SME_BEGIN_STATE_DEF(Player,PowerUp)
/*{{SME_STATE_DEF(Player,PowerUp)*/
SME_STATE_ENTRY_FUNC(PowerUpEntry)
SME_STATE_EXIT_FUNC(PowerUpExit)
SME_ON_EVENT(EXT_EVENT_ID_POWER,OnPowerUpEXT_EVENT_ID_POWER,PowerDown)/*}}SME_STATE_DEF*/
SME_END_STATE_DEF

State Tree
This structure mainly provides the profile of state tree/chart. Itrecords critical information (including state name, event handler andrelationship among them) to draw state chart or rebuild state tree.Modification in this code part will directly be reflected in the statechart/tree while changes in state chart/tree would cause automaticrectification in this structure as well.

Elements in this structure are states under the dedicatedapplication node, which are of the form SME_STATE(applicationname, state name, parent state name, default child state name) .For example, we define the Player state tree as below:

SME_BEGIN_STATE_TREE_DEF(Player)
/*{{SME_STATE_TREE_DEF(Player)*/
SME_STATE(Player,Player,SME_INVALID_STATE,PowerDown)
SME_STATE(Player,PowerDown,0,-1)
SME_STATE(Player,PowerUp,0,Playing)
SME_STATE(Player,Playing,PowerUp,-1)
SME_STATE(Player,Pause,PowerUp,-1)
/*}}SME_STATE_TREE_DEF*/
SME_END_STATE_TREE_DEF

Application Variable Definition
We regard a state machine as an application. In our mapping, we declarean application with a structure in type of SME_APP_T , whichis of the form

SME_APPLICATION_DEF(application, “application name”)

For example, we define the Player application as below:

SME_APPLICATION_DEF(Player,”Player”)

Testing the concept
Based on the mapping technology illustrated above, we have worked out asolution to produce 1-to 1 mapping between source code and statechart/tree in state machine. State tree could be built by analyzingsource code, and meanwhile, we could also construct state machinesthrough state tree. Such round trip way also happens on state chart. Itis easy to draw state charts according to the state tree and we couldalso build state machines by state charts.

Using StateWizard, we developed a mobile phone embedded systemprogram[3] . After embeddedsystems' simulating and debugging in Visual C++ developer studio, wecould move program to a destination working environment with little orno extra investment of effort.

Conclusions
Presented here is what we believe is an effective round-trip 1 to 1mapping solution between state chart and its implementation of a satemachine. Our techniques can be applied to various applicationdevelopment based on state machine including platform-independentembedded systems, Win32 or WinCE.

We believe this approach will greatly improve the productivity insoftware development and consequently decrease the cycles indevelopment. Moreover, we have developed StateWizard using ourtechnology to implement round-trip engineering, enabling the UML toolto synchronize the model with the changes in the application code.

Jin Yuanping is professor anddeputy dean of the school of computer science andengineering, Southeast University, China. His current researchinterests includeintegration of heterogeneous data resources, data warehouse and datamining, XMLdata management and processing, embedded software development. Jin Xinis a developer of UML StateWizard software at Intelliwizard.

Acknowledgements
Thanks to Steve Hanka, an IEEECertified Software Development professional, in editing this article.

References
[1] Andrew S.Tanenbaum.Computer Networks
[2] Hei Wei, Jin Yuanping, JinXin. Design and Application of Reusable Software Framework. Based onHierarchy State Machine Computer Application and Software, to bepublished in 2006
[3] Jin Xin. UML StateWizard[Z].http://www.intelliwizard.com/
[4]
Samek M. Practical State charts in C/C++: QuantumProgramming for Embedded Systems [M]. CMP BOOKS, 2002.
[5] Barr, Michael. ProgrammingEmbedded Systems in C and C++. O'Reilly & Associates[M],1999
[6] Duby, Carolyn. Class203:  Implementing UML state chart diagrams. Proceedings ofEmbedded Systems Conference[C], Fall, San Francisco, 2001
[7] Egon Borger, AlessandraCavarra, Elvinia Riccobene. Modeling the Dynamics of UML State Machines

Otherresources on Embedded.com about UML :

1) Executable and Translatable UML
2)Need for modeling tools rises with design complexity
3) In Focus: Unified Modeling Language
4) Introduction to UML statecharts
5) UML evolves total system perspective
6) Introduction to UML Class Diagrams
7) State machine shortcuts
8)FromUML to embedded system: Is it possible?

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.