Modeling Complex Behavior Simply - Embedded.com

Modeling Complex Behavior Simply



UML Point/Counterpoint:
Modeling Complex Behavior Simply

Stephen J. Mellor

Go to the Counterpoint to this article: How to Simplify Complexity by Bran Selic

“Things should be made as simple as possible, but not simpler.”
-Albert Einstein


Size does matter. When it comes to modeling languages, sometimes it can be too big to do the job right. As real-time system designers, we need to specify, construct, visualize, and document the dynamic behavior of a system. This task is the one taken on by the Unified Modeling Language (UML). The point I wish to make is that the language for modeling complex dynamic behavior is too big to do the job right. “Doing the job right” is a rather subjective phrase, of course, so let’s begin by examining the requirements for a modeling language.

Expressive. When we model a system, we have to use a modeling technology that’s expressive enough to define the problem at hand, and do so economically. A Turing machine is mathematically powerful, and the binary number system is economic in its use of symbols, but neither is expressive enough to be useful for modeling.

Reliable. When we model a system, we have to know it’s right. Software that is almost right is wrong, and wrong software can kill, maim, or incur significant economic losses. A modeling language must therefore be precise in its specifications, while at the same time allowing for visualization early in development.

Cheap. Not only do we have to get it precisely right, market pressure forces us to get it right quickly. It takes time to learn sophisticated languages, but the less investment required, the better.

Universal. We build models to communicate. No matter how correct or precise our modeling tools are, and no matter how stunning our own mastery of them, others must also be able to understand the models. When communicating with hardware engineers, for example, arbitrary differences in notation or concepts for state machines can lead to confusion or error.

Scaleable. We model systems today whose complexity represents an exponential increase over previous models. A modeling language that matches the model's complexity will not provide any benefit.

How does UML dynamic modeling stack up?
The UML provides a rich set of modeling tools to model behavior, which we may divide into two groups. The heart of the tool set is the state chart, a hierarchical state machine that may be associated with a class. The state chart also allows the developer to add actions to states or transitions. The second set of tools models collaborations of various kinds: net synchronous and asynchronous communication between classes or instances and — using essentially the same diagrams — showing particular scenarios one by one.

To get a feel for the size of the dynamic modeling tools in the UML, examine Table 1, which is a prècis of the notational elements and accompanying definitions that comprise a state chart, taken from the UML Semantics Guide, Version 1.3. How many of these elements do you know offhand? Understand in detail what they are? Know what they mean in execution? How they relate to one another syntactically? Semantically? Could you use all of these today? With training?

Table 1: Notational elements that comprise a state chart
Element Definition
Call event The reception of a request to synchronously invoke an operation
Change event An event that occurs when a boolean expression becomes true as a result of a change in value of one or more attributes or associations
Composite state A state that contains other state vertices
Event A specification of a type of observable occurrence
Final state A special kind of state signifying that the enclosing composite state is completed
Guard A boolean expression attached to a transition, evaluated when an event instance is dispatched by the state machine that controls firing of the transition
Pseudo-state (In seven kinds) An abstraction of different types of transient vertices in the state machine graph
Signal event The reception of a particular asynchronous signal
Simple state A state without substates
State An abstract metaclass that models a situation during which some invariant condition holds
State machine A specification that describes all possible behaviors of some dynamic model element
State vertex A node in a statechart graph
Stub state An actual subvertex contained within the referenced state machine
Submachine state A macro-like expansion, semantically equivalent to a composite state
Synch state A vertex used for synchronizing the concurrent regions of a state machine
Time event The expiration of a specific deadline
Transition A directed relationship between a source and target state vertex.
It may be a part of a compound transition.

One glance at that table and I'll happily agree that the state chart is expressive.

As for reliable, cheap, and universal, the state chart is too big and complex to meet these requirements. It misuses hierarchy, has overly complex interactions, and allows too many ways to say the same thing.

No matter how correct or precise our modeling tools are, and no matter how stunning our own mastery of them, others must also be able to understand the models.

Misuse of hierarchy. One popular mechanism to manage large systems is to use hierarchy to zoom in from a larger unit to component parts or zoom out to hide details. In a well-formed hierarchy, the larger unit is transparent: it simply groups state machines together with no additional semantics. In a nontransparent hierarchy as employed by the UML state chart, the larger units — the super-states — have meaning, incorporating interactions with initial state, final state, and deep and shallow histories. Therefore, the meaning of a state model is dependent on its context, which is akin to saying that a change in the outline changes the meaning of a book.

Can we really do without hierarchical state machines? To illustrate, consider an automobile with a cruise control system that can be turned on or off at any time. One way to model this is to decompose the model of automobile into various subsystems including cruise control, using the hierarchical facilities of the state chart. When the driver turns cruise control off, we exit the superstate that represents cruise control. The other, transparent, way is to model the button that turns the system on and off, and communicate between that and the other things in the system as peers, instead of nesting them. This approach requires no additional constructs.

At this point we could enter into a contest to see whose approach is bigger and better than the other. But I'll agree that the use of simpler constructs can lead to models that have more elements — more states, more transitions, whatever. But we can partition again to yield more-though more manageable — state machines, and package the resulting group of state machines together transparently. No new constructs, just a zooming out from a single state machine to a group of flat, related, peer state machines.

It's worth remarking at this point that the act of partitioning a model in this manner — or better still, starting from the bottom and working up — almost always exposes problems that weren't visible in hierarchical state machines. Satisfaction is very much a matter of improved technique.

Overly complex interactions. The UML allows for very complex interactions between state machines. As an example, consider two communicating state machines in which one state machine sends an event to another that is guarded. At the time that the event is sent, the guard can evaluate as true, but the event is deferred in the destination state. At some later time, the event can be handled, but now the guard is no longer true. Does the transition take place? What happens in what order? What is the value of the attribute when it is read by which method? Personally, I haven't a clue.

For the sake of argument, let's stipulate that the semantics of all these elements and their interactions are precisely defined. That's not the problem. The problem is being able to retain the definitions and use them — and to be certain that everyone else on the project has the same understanding. Would you want to stake your life on the assumption that everyone involved in modeling your automobile understands the model the same way?

In addition, interactions on the state chart are software-specific: calls, guards, and the like. As embedded systems engineers, we also work with hardware folk, who use state machines without such embellishments. The more the concepts in the UML state chart differ from those found in other disciplines, the less universal the state chart will be.

The state chart would be more effective if it had fewer modes of interaction.

Too many ways to say the same thing. Consider this problem: when our example automobile reaches the desired speed, we wish to change the color of the cruise control light. How can we model it?

We can do this in many ways: with a watchdog that causes an event to be generated that will cause a change in the state of the light. Or we could place a guard on a transition, so that each time the speed changes, the transition is enabled but it only takes place if the speed is at or above the desired speed. Or we might abstract the concept of reaching the correct speed as a signal event, and show it directly on the state machine.

Each of these is subtly different in respect to how it thinks about time. In the first case, we're polling. In the second case, we look at each change in speed as a signal event, but then we have to carry out some computation that is not an action (it’s a guard). In the third case, the signal event models what we actually care about, even if no interrupt corresponds exactly to it.

It isn’t clear whether these differences are important or merely happenstance. Are we saying how we intend to handle time in the system, or are we instead just choosing an arbitrary way to model the signal? This is a problem because it encodes design decisions (watchdog timer) with requirements (change color at speed).

In my view, there should be a very limited number of ways to model a single logical concept-in this case, the fact that the car has reached a certain speed. How that single logical concept is then implemented is an altogether separate issue you can take up later.

The combination of these three issues — misuse of hierarchy, complicated interactions, and too many ways of saying the same thing — contrive to make the modeling language unreliable, expensive, and parochial.

The language that couldn’t say no
It seems there’s always something else that simply must be added to the language. At present, moves are afoot to add “real-time capabilities” to the language, including scheduling, timing, and the like. Certainly these are important issues, but attempting to add all these features to the UML is a fool’s errand.1

This sort of feature-packing simply has no end. Today, it's scheduling and timing. Tomorrow it will be something else. No doubt other ways of communicating between software components will soon come about, new languages will spring up with new capabilities, and new hardware architectures will have a need for new facilities in the language. Should all these be accounted for in UML?

As an analogy, think about writing a large number in roman numerals. What comes after M anyway? L? D? Once you look it up in the 808-page Roman Numeral Reference Manual, what if our representation still isn't big enough?2 We'll have to add a new letter once we run out of the allocated ones. And what happens when we use up all 23 letters of the Roman alphabet?

Today, before all of these potential additions, the state chart has a multitude of concepts that have specifically to do with deployment and implementation, most of which are useful in real-time systems. The UML as a whole also has mechanisms for extending the language (stereotypes and tags) by adding to or changing the meaning of existing notational constructs, which will, of course, serve to make matters worse.

As a consequence, we have to conclude that the UML dynamic modeling capabilities are extensible, but they are not scaleable. In sum, the state chart is expressive — but it's also excessive.

What can a developer do?
As a developer, you have a need to model dynamic behavior, so what can you do? First, we all gain from having standards. It's easier to hire people; communication is easier because we're all talking the same language; and we can avoid pointless notation arguments. The UML is a de facto standard and now it’s up to us to use it wisely. So how can we do that?

Subset, radically subset. Here's my suggestion.

A radical subset. The primitives for the state chart comprise only transitions, events and the data that accompany them, (non-hierarchical) states, and actions associated with each state. Actions are of only four types: data access, transformations of input data into output data, transformations of input data into mutually exclusive control outputs, and asynchronous signal generators. All four types may operate on single values or collections.

The execution model defines run-to-completion semantics for the action set; it preserves order of signal events only between sender and receiver object instance pairs; it requires the developer to synchronize state machines to avoid data access conflict (or be oblivious to it); and it treats all events as having the same priority.

Collaborations are shown using the UML collaboration diagram, essentially unchanged, though not all variations are required. (Because the diagrams can and should be derived from the state charts using a tool, you should use any diagram that you find helpful. The underlying semantics are handled by the state charts.)

Before my learned colleague impugns my manhood, isn't this simplified state chart rather inadequate and sparse? Don't we really need hierarchy, synchronous states, and guards? After all, event messages do have priorities and we really do cause a state machine to change state as the result of a call, not a signal.

Inadequacy. A deadline-driven real-time system such as one that controls an automobile surely requires priorities on events. When we put the brake on, it takes priority over the cruise control system, no matter what is going on. Surely we need watchdog timers, guards, and the rest in the UML. I think not.

How did we solve the problem with the Roman numeral system? We found a way to combine elements in separate dimensions to yield an extensible, scaleable system. Instead of an ever-increasing list of letters, we used a limited set, the ten digits, and combined them with a second idea — an exponent, normally expressed by position, for each. This system scales, while the Roman system does not.

To model dynamic behavior, we should distinguish between the logical behavior required of a problem (“at speed,” for example), and the mechanism required to make it so (a watchdog or a computation associated with the analog inputs that check range). The mechanism that supports the logical concept “at speed” belongs in a different layer from the one reading the analog values, process input/output. The separation of the application model from the application-independent process input/output subject matter is analogous to the notion of using an exponent in the decimal number system.

To link the two subject matters, we must state “translation rules” so that the logical model signal event “at speed” is defined to be realized by an analog input signal reaching a certain value. As a consequence, no need exists to have explicit modeling constructs for every possible real-time concept.

Sparseness. Some languages have an until construct that is exactly equivalent to while not, so you can write intuitively expressive statements like until hell_freezes_over do. The until construct is syntactic sugar: it's not fundamental, nor does it add anything that we can’t otherwise write.

We may apply this notion to the state chart. Starting with the radical subset above, or a similarly trimmed-down formulation, add your favorite syntactic shorthand. If you find a deferred event to be something you can't live without, use the UML notation and define its semantics in terms of existing metamodel elements. We may define the deferred event as an additional (hidden) class that acts as a queue. Similarly, to add a guard, show the guard as an action that generates an event if the guard passes. And so on.

This approach builds from a well-defined simple subset, so you can guarantee it has a clear definition. Better, we custodians of the UML should define a kernel UML and then build profiles that formalize the extensions from the subset.

The point
The point is to get complex systems out correctly, quickly, and cheaply. The best way to do that is to use a small, well-defined subset of the UML state charting mechanisms.

Stephen J. Mellor is best known for his contribution to the development of object-oriented analysis, recursive design, and the Shlaer-Mellor Method. He is vice president of Project Technology, Inc., where he consults, teaches, and researches applications of the method. Steve is currently working with Object Management Group (OMG) to define extensions to the UML for executable and translatable models. He is also a member of the editorial board for IEEE Software.

References

1. Not quite as powerful as the wonderful line, “Jane, you ignorant slut” from the Saturday Night Live “Point-Counterpoint” skit, but I'm more polite.

2. The UML Reference Manual (Object Management Group, Framingham, MA, 1998) is 808 pages long.

Leave a Reply

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