H.S. Lahman on OO and MDA

1.0 What is a State Machine

Blog root page
next post in category

A state machine is an implementation of the mathematical notion of finite state automata. In a finite state automata an arbitrary set of input symbols is read sequentially. The automata consists of individual states and the state changes each time a symbol is processed. The number of possible states is finite and the change of states is known as a transition. The new state is determined by evaluating a state transition function:

new state = F(current state, current symbol)

Note that the new state is solely determined by the identity of the current state and the input symbol. Since the input symbols are arbitrary, the new state is also arbitrary once one is in a given state. Similarly, there is no way to deduce what the previous state was based solely on being in the current state. (BTW, there is nothing to prevent the new state from being the current state in

While this formalism provides a sound basis, it is not directly very useful for software development unless something else happens besides transitioning from one state to another. So for software we elaborate a bit on the notion of finite state automata be introducing the notion of a state action that does something when one transitions into a new states. So in a software context a state machine is a finite state automata with the following elements.

State. A state is a condition where some set of rules and policies apply. In an OO context those rules and policies will be extracted from the problem space and they represent intrinsic behavior responsibilities of the underlying problem space entity.

Transition. A transition is a valid change from one state to another. In general one cannot transition from the current state to any arbitrary state; typically only one or a few state changes are valid. In an OO context the valid transitions represent constraints on the sequence in which various state rules and policies may be executed during the life of the object.

Event. An event is equivalent to an input symbol in a finite state automata. In an OO context an event is a message with a specify identity and, optionally, a packet of data that will be processed by the state action. Only the event identity is relevant to evaluating the state transition function.

Action. The state action executes the rules and policies that are appropriate for the state whenever there is a transition into the state. That is true even if the previous state happened to be the same. (Transitions back to the same state are known as reflexive tranitions.) In the OO context a state action is a method.

In an OO context we map an entity's behavior responsibilities into a single object state machine during the process of abstraction. That object state machine is known as the object life cycle. Each state action represents a method that encapsulates a single, logically indivisible behavior responsibility at the level of abstraction of the object's class.

In an OO context the events that trigger transitions are almost always generated outside the receiving state machine. Those events represent collaborations with other objects in the subsystem or external stimuli.

Blog root page
next post in category

2.0 Mapping to OO

Blog root page
previous post in category
next post in category

State machines were employed to describe behavior in R-T/E development long before OO development existed. That's because the rules for finite state machines enforce a number of Good Practices that are a matter of survival in the very unforgiving world of R-T/E. In addition, finite state machines are ideally suited for design-by-contract (DbC) construction of software.

The rules for finite state machines require that a state cannot know what the previous state was or what the next state will be. That necessarily means that the action associated with a state cannot be dependent in any way on actions in other states. This implementation independence essentially removes the single greatest problem of traditional procedural code -- hierarchical implementation dependencies that led to the legendary Spaghetti Code.

The independence of state actions from other state actions maps very nicely into OO fundamentals. That context independence means the action is self-contained and encapsulated. Thus its implementation is hidden from other actions and objects. Since the action can't know anything about the sequence of state transitions, it can only describe behavior that is intrinsic to the state. That maps nicely into the notion that objects abstract intrinsic properties of problem space entities.

But the mapping to OO development doesn't stop there. State actions are executed as the state machine transitions into a state. That transition is triggered by an event generated elsewhere (usually an action executed in another state machine). That represents an interaction or collaboration between state machines and the event is a message that initiates that collaboration. This is exactly what happens in OO collaboration. In particular, the message is conceptually a quite different critter than the state action that executes in response to the transition.

This same separation of message and method is fundamental to OOA/D construction. In addition, the event maps conveniently into an interface for the state machine. If the state machine represents the life cycle of a single object, then the events that the state machine accepts define the behavioral interface to the object.

Finally, because events are generated in an ideal finite state machine without knowing where they are going, events map very nicely into the notion of DbC and peer-to-peer collaboration that are also fundamental to good OO development. (I will go into more detail about DbC in another post in this category.)

Blog root page
previous post in category
next post in category

3.0 Design by Contract (DbC)

Blog root page
previous post in category
next post in category

By way of a quick summary design-by-contract (DbC) is a software design technique that dates from the '50s. The notion was formalized initially for OO development by Bertrand Meyer in the early '80s and it has been steadily refined since then. The basic idea is that that there is a contract between client and service. The client specifies something to be done and the service is designed to satisfy that specification.

This sort of client/service relationship is a rather procedural view that had been modified in subtle ways in the OO context. In OO development the notion of contract has been abstracted and formalized around the notion of interface. Thus a client is not a specific entity in a particular problem context but a more generic notion that is closer to the idea of a bundle of requirements and a message. The bundle of requirements represents the specification for the responsibilities the object must fulfill to solve the problem in hand and the message defines an interface for accessing those particular responsibilities. So the notion of client has been generalized to any other object that might require access to the responsibilities.

So in an OO context DbC is executed by: (1) formally specifying the responsibilities an object must contribute to the solution of the problem; (2) define a generic interface to access those responsibilities that any object can access; and (3) design the implementation of the service to support the specification and the interface. One common technique to do (1) is to define preconditions and postconditions that must prevail before and after executing the responsibility as well as invariants that must prevail during the service execution.

The preconditions define obligations that the client must satisfy. The postconditions define the expectations of the client that the service must satisfy. The invariant conditions define constraints on the execution itself.

Since object state machines separate message and method and a state is defined as a condition where particular rules and policies apply, we have an ideal situation to apply DbC. Since the state is a condition that must exist for the execution of the action's rules and policies, it is effectively a precondition for executing those rules and policies. However, that condition can only exist as a postcondition of some other state action executing (i.e., some action must execute to modify the application condition).

Therefore we can define the sequence of execution by essentially "walking" through the conditions leading to the solution backwards. For an given state action to execute, its condition must prevail so one looks for another action whose postcondition is the same. One then generates the event to trigger the transition in that action. In this scenario the events are messages that simply announce that a postcondition prevails. The developer just matches that postcondition to another object's condition and consumes the event there.

Thus one has a daisy chain of precondition-to-postcondition contracts that define the actual sequence of messages for the problem solution in a mechanical fashion. A corollary is that one can specify all the object state machines prior to worrying about the flow of control of the overall problem solution. This deferral of concerns about sequences of operations is probably the most fundamental difference between OO development and procedural or functional development.

Do OO developers actually do this sort of thing in practice? Usually not literally unless especially thorny sequencing problems arise. That's because an experienced developer can multiplex and knows how responsibilities were allocated in other state machines when implementing the one in hand. However, conceptually they do because they separate message and method, treat messages as announcements (I'm Done) rather than imperatives (Do This), assume peer-to-peer collaboration on an as-needed basis, and construct object state machines around intrinsic life cycles of problem space entities.

A caveat. Life is rarely quite so simple. In OO development one also captures the notion of state in state variables (knowledge attributes) and well as state machine states. That is an orthogonal process with its own sequencing problems because of data consistency issues. So the contract precondition is likely to be compound. One condition will always be the state condition but it may be ANDed with conditions on various state variables being updated correctly.

Any update of a state variable must be done be some behavior responsibility so it will always be in an object state machine action if one employs object state machines to describe all behaviors. That means we can replace the data update precondition with the postcondition of the action that does the update. As a practical matter we do that by daisy chaining the conditions. So if we have dependencies that look like:

                       [PostconditionB] ------------ [DataX]
                       /
                      /
                     /
      [PreconditionA]
                     \
                      \
                       \
                       [PostconditionC]

then rather than having both PostconditionB and PostconditionC sending events to PreconditionA for synchronization, we can reorganize the dependencies as:

                       [PostconditionB] ------------ [DataX]
                               |
                               |
                               |
      [PreconditionA]          |
                     \         |
                      \        |
                       \       |
                       [PostconditionC]

Now part of the compound precondition of PostconditionC is that PostconditionB executed. So the action with PostconditionB sends an event to the object with PostconditionC and then that object sends an event to the object with PostconditionA when responding with PostconditionC.

The astute observer will note that I glossed over the fact that some action not shown triggered PostconditionC, so I have just moved the problem. Again, it is beyond this scope to go into details but I submit that most state actions modify state variables so their postconditions are effectively announcing that update. I also submit that since actions are logically indivisible, they should not encapsulate complex behaviors relative to the problem in hand. So as a practical matter it is usually pretty easy to organize the proper sequence.

I only went into this digression to make the point that matching action conditions to action postconditions is a rigorous and systematic approach to ensuring the correct flow of control to solve the problem. However, that is only possible if all behavior responsibilities are described with object state machines. If one mixes in synchronous behaviors that update state variables, there is no rigorous and systematic way to ensure correct flow of control -- it is a pure developer responsibility. IOW, this is a strong reason for describing all behavior responsibilities with state machines.

Blog root page
previous post in category
next post in category

4.0 Object Life Cycles

Blog root page
previous post in category

In the post on DbC I indicated that one can construct object state machines without worrying about flow of control in the overall problem solution. While not completely true, it is close enough for horseshoes because of the way we abstract the problem space when doing OO development.

It is crucial to OO development that one abstract intrinsic responsibilities for objects from underlying problem space entities. It is in the nature of the notion of intrinsic that those responsibilities should be context-independent. So, to that extent my statement is quite correct; we should be able to design object state machines without knowing anything explicit about the sequence of operations necessary to solve the customer's problem.

Where the hedge lies is that one only abstracts the properties one needs to solve the problem in hand. In addition, one tailors the abstraction to suit the problem in hand. To that extent one does have one eye on the problem to be solved and some general notion of the collaborations necessary to solve the problem. However, one doesn't need to know anything specific about solution flow of control -- it is quite feasible to design states, transitions, and actions without generating events in actions or assigning specific events to actions.

One does that by capturing the notion of an intrinsic object life cycle in the state machine. The basic notion behind an object life cycle is that the object is born (instantiated), wanders through some series of life stages, and dies. Like a person who may cycle through multiple marriages and divorces, the life of an object may have closed cycles within the overall linear born/die progression. Typically there are some structural rules about the order in which an object traverses its stages. Thus a person cannot changes state to a Divorced stage unless they were in a Married stage.

The mapping of an object life cycle ot a state machine is pretty straight forward at this level. A stage of life becomes a state and the valid changes between stages are mapped as transitions between states. Recognizing such life cycles is pretty easy for something like a light bulb, whose stages might be {OFF, ON, BURNED_OUT}. Alas, problem space entities are often more subtle than that and life cycle stages are more difficult to recognize.

However, if we think in terms of state machines we have an important clue. Since a state is a condition where a particular suite of rules and policies are relevant, we can define states around the object's behavior responsibilities. (At the Class Diagram level we already defined our objects, their mission, and the nature of their responsibilities in the problem context.) If we have logically indivisible behaviors we can associate them with states. Often this leads to discovering the intrinsic life cycle that is relevant to the problem in hand. In effect we are tailoring the life cycle to the problem in hand.

For example, suppose we are writing the controller software for an automatic garage door opener. We have identifier the Door as a central entity that will anthropomorphize behaviors. Initially the obvious states are {OPEN, CLOSED}. However, we have also identified a behavior that occurs when the electric eye detects something in the path of the door. If the door is already fully opened or closed, that behavior is irrelevant. It only has meaning if the door is in the act of closing. So we recognize that we need an additional state {OPEN, CLOSED, CLOSING} that is a condition relevant to the electric eye behavior.

A similar argument can be applied to receiving a clicker event. If the door is already open or closed, it toggles to the other state. But opening and closing take finite time so what does one do if another click is received while the door is in the process of closing or opening? Most requirements specify the door should reverse direction. But to accommodate that we also need an OPENING state. So after considering the behaviors needed to solve the problem and understanding the realities of the problem space (finite state transition time), we arrive at:

        at stop
    +-----------------------------------------------------+
    |                                                     |
    V        click                         obstruction    |
[Closed] ---------------------> [Opening] <-----------+   |
                                / |   ^               |   |
           at stop             /  |   |               |   |
   +--------------------------/   |   |               |   |
   |                              |   |               |   |
   |                        click |   | click         |   |
   |                              |   |               |   |
   V                              V   |               |   |
[Open] -----------------------> [Closing] ------------+   |
            click                   |                     |
                                    |                     |
                                    +---------------------+

So we have two new life cycle states developed from the object responsibilities that were not immediately obvious initially. However, as we review this state machine within the context of the problem we detect that it is not quite correct. The problem lies in recognizing that there is an obstruction. According to this model, it there is another click after the "obstruction" event is received, the door will start closing again and crush the baby carriage.

My point in bringing this up is that the analysis that leads to the solution, including recognizing and dealing with an incorrect preliminary state machine, can be done with no specific knowledge of the context. Everything I have described results from an analysis of the intrinsic responsibilities that we already identified for this object. The only external information we need to understand is the we must properly respond to clicker, electric eye, and stop detection events. The responses themselves and the state machine structure are all defined intrinsically in the nature a garage door opener.

For those curious about one possible solution:

        at stop
    +-------------------------------------------+
    |                                           |
    V        click                              |
[Closed] ---------------------> [Opening]       |
                                / |   ^         |
           at stop             /  |   |         |
   +--------------------------/   |   |         |
   |                              |   |         |
   |                        click |   | click   |
   |                              |   |         |
   V                              V   |         |
[Open] -----------------------> [Closing] ------+
   ^        click                   |
   |                                |
   | unobstructed                   |
   |                                |
   |          obstructed            |
[Obstructed] <----------------------+

Where the action for the OBSTRUCTED state is to order the hardware to open the door. Any "click" or "at Stop" events are ignored in that state. Since OPEN and CLOSED don't actually do anything except wait for a click event, everything Just Works.

[FWIW, I would be suspicious of this solution because it suggests a lack of cohesion in Door. There are two distinct groups of responsibilities: talking to the hardware about opening and closing vs. providing an appropriate response to the electric eye. I would be inclined to delegate the response to the electric eye to some other object. Object state machines are surprisingly easy to used despite their asynchronous nature -- but only if one keeps them simple, which is consistent with the OO notion of cohesion. However, this example was aimed at illustrating different issues.]

Blog root page
previous post in category