A More Object-oriented State Machine

Conrad Bock


Reprinted from
Journal Of Object-Oriented Programming Vol 12, No 8, January 2000
Copyright © 2000 SIG Publications, Inc, New York, NY



This is the third article in a series on modeling behavior in the context of object orientation. The first two reviewed three traditional categories of behavior model, how they can be used in an object-oriented way, and addressed their unification, especially in the Unified Modeling Language (UML). This article examines one of those models more closely, namely state machines. It identifies two common approaches to state modeling and explains why they provide more powerful analysis when combined under an object-oriented framework. The technique, an elaboration of Gamma's State Pattern, is proposed as an extension to UML.

Models of State

There are at least three approaches to modeling states, the third of which helps resolve the difficulties of the first two while preserving their benefits:

The first two kinds of state do not handle some common modeling situations. For example, suppose the PERSON class has a state machine with two states, WELL and SICK. We might want to model information for individual people, like how long John has been sick or how many times, and which doctor is taking care of his illness. Behavior-state machines are normally specification-time constructs defined on classes, so they cannot model information about instances that is only available at runtime. Instances are usually addressed during implementation of behavior-state machines, rather than at analysis-time as we are doing here. Feature states have some runtime instance modeling, because they record the feature values that satisfy the constraints for a person being in the SICK state, but this does not support our modeling requirements either.

The technique presented here starts with Gamma's State Pattern, and extends it, because the State Pattern is only aimed at applications in which the operations of an object have state-dependent methods. The pattern implements states as classes that are instantiated as an object enters each state. Operations invoked on the object are delegated to those instances, which have their own methods for the operations. However, as Gamma points out, it is not necessary to make state instances for each object when the data they require is already on the object, as is commonly the case. It is more efficient to use the flyweight pattern to share state instances across objects. For our application, on the other hand, we need each object, such as the one for John, to model information particular to that object, such as how long he has been sick. Gamma's presentation is aimed at an implementation of dynamic classification, to make it appear that methods are changing at runtime, and does not cover the improvements at the analysis level discussed here.

The first two state models are not necessarily related, even though they are the most common. A machine using behavior states can operate properly without an object, or without modifying the feature values of the object to which it happens to be attached. For example, a behavior-state machine can respond to events by sending out signals and messages to other objects, by returning values from an operation the machine implements, or by controlling the order and timing of queries that are directed at the object, as a facilitator does at a group presentation. This would be characteristic of Jacobson's control objects. The data on which such machines act are taken from the incoming events. No persistent information is required for the machine, except as relates to the status of the machine itself, which is internal to it, rather than a characteristic of the object to which it is attached. See the previous article in this series on the drawbacks of confusing models of behavior, like state machines internals, with models of objects, like feature states [2].

On the other hand, an object can satisfy the constraints of a feature state without receiving or noticing an event to transition the object into that state. For example a person can be sick or well based on their changing symptoms, without involving any event processed by a behavior-state machine.

Because the two interpretations are not connected in any fundamental way, they are weaker in their modeling capability than if they are brought together under an object-oriented framework. On one hand, behavior states do not model the conditions required for an object to be in a particular state, as feature states do. For example, the UML uses behavior states that can be attached to objects, but there is no adequate connection between those states and the feature values of the object to which they are attached [3]. A constraint can be linked to a state, but there is no specification of when the constraint should be tested. It could be tested when the object enters the state, leaves the state, or at any other time. Even if this were unambiguous, the consequence of violating the constraint is not defined, namely, to transition the machine to a state that has a constraint satisfied by the object. The UML-knowledgeable know this might be modeled as a change-event trigger on an exiting transition, but it would be redundant with the constraint recorded on the state and with triggers on other transitions leaving the state, thereby impairing maintainability.

On the other hand, an object's feature values must change for the object to change feature state, because a constraint on the feature values must be violated to do so. This means feature states cannot handle applications where feature values do not change from state to state, or where absolute constraints are not imposed on objects when they are in a state, as described earlier. For example, Odell requires that state machine transitions be triggered by and cause changes in feature states [4].

Since the two interpretations of state are fundamentally unrelated, methodologies usually adopt only one approach or do not distinguish the two, as in UML or Odell. The rest of this article examines how the two models can be flexibly joined and enhanced under one methodology. This is the third, OO state approach, described in the next section.

Object-oriented States

This technique starts by treating states as classes that are instantiated and deleted at runtime as the state machine executes, per Gamma's State Pattern. For example, when a person enters the state class for sickness, a state instance is created. Going back to the example of the last section, states WELL and SICK on PERSON are classes. Figure 1 shows this in UML state machine notation, extended by allowing states to have attributes, associations, and generalizations. Transitions are specified on the state class itself, not for inheritance to any of its children. Enhancing Gamma's pattern, state classes are specialized for particular people, to create for example, SUSAN-WELL, JOHN-SICK, and so on. The figure extends UML to support these specialized state classes also. They are part of an "instance-level" state machine, shown by the dotted container, which is a very reduced form of its class level counterpart. It does not have transitions, actions, or other behavior modeling aspects, which would only be redundant at the instance level.

Figure 1: Object-oriented States

State instances can record runtime information, such as how long the machine has been in a certain state. For example, the HOWLONG attribute is declared on SICK and inherits to JOHN-SICK. When John becomes ill, then a new instance of JOHN-SICK is created and a timer begins to track how long he has been in that state. The timer value is recorded on the new state instance. When John is no longer ill, the state instance is deleted or archived for his medical history.

State classes can participate in associations to model application-specific information. For example, the SICK state class is associated with the DOCTOR class. Each state instance created when John gets sick will have a link to a particular doctor, as shown in Figure 1. This is more accurate analysis than without state instances, because the doctor is concerned with John being sick, not his finances or John in his entirety. The doctor's lawyer could certainly attest to that. The specialized state classes can record summary statistics about their instances, like how many times the object has been in that state, that is, how many instances of that state have existed over time for that particular object. Figure 1 shows JOHN-SICK recording how many times John has been sick on its HOWMANYTIMES attribute (UML underlines attributes that are about classes rather than instances).

The reader who is uncomfortable with the idea of states as classes might consider the alternative model shown in Figure 2. It shows a specialization of PERSON called SICK-PERSON under which people are reclassified when they are sick. This new class can model how long the person has been ill, and the PERSON class can model how many times. A doctor can be assigned by defining an association between SICK-PERSON and DOCTOR. This is a perfectly normal way of analyzing the example. The state class technique of Figure 1 just combines this common-sense approach into a behavior-state machine, so that transitions can be defined for machine execution. The SICK-PERSON class of Figure 2 is translated to the SICK state class of Figure 1. This reduces the number of "free-floating" subclasses of PERSON and eliminates the need for dynamic classification, a service not supported by most programming languages.

Figure 2: Simplified State Class

Given the above arguments, one might ask why it is necessary to have a new set of instances for state classes, why not just use the instances already available, namely individual people? This way, state classes would be dynamically "mixed into" JOHN, for example, as the state machine executes, thereby inheriting state-related attributes and associations to JOHN. Aside from the analysis problem that domain objects like people are not states of a machine, this approach prevents the semantics of feature states from being modeled properly, especially for the case of concurrent states, as described next.

The reader may have noticed that the description of feature states so far did not elaborate on the distinction between feature values and constraints on those values. For example, the MARRIED feature state applies to a particular person, like Susan, because of a link to her husband. But it also applies to people in general, as a precondition or constraint on those that are in the married state. OO states provide an accurate model for this because state classes and instances provide separate places to record the two aspects of feature states:

  1. A state class specifies the general requirement for being in that state. For example, the MARRIED state class on PERSON has a precondition requiring a MARRIAGE link to another person, without saying which person.

  2. The state instance records a set of specific feature values that justify the object being in that state. For example, the MARRIED state instance on SUSAN records the MARRIAGE link to JOHN.

Figure 3 shows the above structure using UML's Object Constraint Language (OCL) to express constraints on the state class. The feature-state constraint expression uses the variable "this" to mean the object to which the state is attached. UML is also extended here to distinguish feature-state constraints with a stereotyped constraint note, because the semantics of ordinary constraint notes on a state is ambiguous (see last section). A feature-state constraint is required to be true for the entire time that the object is in the state. The line between the SUSAN-MARRIED 1 state instance and the marriage link between SUSAN and JOHN expresses the justification for Susan's married state, namely the marriage link between her and John. This is also a UML extension, because UML would normally require a link object interposed between the link and any associations to it (the notation of the figure means the same thing, but is more compact).

If we had used instances of PERSON as state instances, it would not be able to unambiguously record justifications for concurrent states, that is, when people are in multiple states at once, such as EMPLOYED and WELL. The justifications of any one state could not be distinguished from the others. This makes it hard to monitor the feature values that justify the state instance, and retest the constraint when any of them changes. Readers familiar with truth maintenance systems will recognize the application of justifications, which require an unambiguous link between facts and the constraints they support.

Figure 3: Formalization of Feature States Using OO States

State instances are also useful when applied in conjunction with actions invoked by a state. For example, UML state machines are used as the basis of activity modeling for business processes [2]. When a certain step (state) in a business process is reached, an operation might be invoked. A particular behavior that is started this way will take some time and consume resources. State instances provide a place to record this information as the execution proceeds. The modeler can define associations between state classes and various kinds of resources [5]. If the target system supports process instances, as is the case for most operating systems, then this information is more properly recorded on those objects, but even in this case, the states can be associated with those processes in order to find them from the state machine model. Such a link supports monitoring the runtime process through a graphical depiction of the state machine.

For those interested in UML meta modeling, OO states can be added as a specialization of CLASSIFIER and STATEVERTEX. Transitions, actions, and other aspects of states do not inherit to state instances, because the links for these are instances of META-ASSOCIATION, not ASSOCIATION, and consequently are not instantiated to the runtime level.

Space limitations prevent showing how OO states apply to substates, state machine inheritance, and concurrent states. The reader can take it as an exercise to use state classes and instances in these situations until a later article addresses the topic. Also the reader might consider the applications where operations on state classes would be useful. Please send in any interesting results.

Conclusion

Two common state models, behavior and feature states, are combined under an object-oriented framework. The new approach elaborates on Gamma's State Pattern and is described as an extension to UML. It preserves the benefits of both of the earlier approaches while supporting more expressive analysis modeling.

Acknowledgements

Thanks to Eran Gery for his very helpful comments, and Jim Odell for his collaboration on the OOIE meta-model, during which the idea for this article arose.

References

[1] Gamma, Erich, et al, Design Patterns: Elements of Reusable Object-oriented Software, Addison-Wesley, Reading, MA, 1995.

[2] Bock, Conrad, "Unified Behavior Models," Journal of Object-Oriented Programming, 12(5), September 1999.

[3] Rational Software, et al, UML Semantics, version 1.1, Rational Software Corporation, Santa Clara, CA, September 1997. The 1.3 revision will be available at http://www.omg.org.

[4] Martin, James, and James J. Odell, Object-Oriented Methods: A Foundation (UML edition), Prentice Hall, Englewood Cliffs, NJ, 1998.

[5] Meta Data Coalition, Business Engineering Model, part of the Open Information Model, available at http://www.mdcinfo.com/OIM/models/BEM.html.



Return to Bock Online
If you have any comments on this page or problems, contact Conrad Bock (conrad dot bock at nist dot gov)