Doron holds several patents in the areas of state-chart synthesis and finite state machine optimization. He is president of R-Active Concepts and Co-Active Concepts, Ltd. Doron can be contacted at doron@ractive.com.
Because it enables code reuse and enhances maintenance, inheritance is one of the more-important properties of object-oriented programming. In a C++ implementation of firmware for a product such as a digital answering machine, for instance, one base (parent) program can perform operating-system-like routines (storing/deleting messages), while the other performs push-button and keypad control. With C++, different answering machines can inherit and enhance these "classes," thereby leading to specific versions of answering-machine firmware. Also, the parent designs can be reused in many other designs, without requiring intimate familiarity with the original parent design.
In my article "Extended State Diagrams and Reactive Systems" (DDJ, October 1994), I introduced the concept of extended state diagrams and illustrated their applicability for the design and development of "reactive" systems, which react to inputs that are not ready at any given point in time. Extended state diagrams (ESDs) are conventional finite state diagrams (FSDs) augmented with hierarchy (the ability to draw states inside states and do top-down design), concurrency (the ability to describe independent and conceptually concurrent threads of control inside any state), and visual synchronization (the ability to visually describe dependencies between these threads). In short, ESDs are the visual counterpart of an enhancement of FSMs.
ESDs address the limitations of traditional state diagrams, while retaining their visual and intuitive appeal. For instance:
To illustrate these concepts, consider the following specification for a traffic light controller (TLC):
C programmers might reuse the diagrams in Figures 1 and 2 by copying them into a new diagram, then refining them to meet all specification items. One drawback to this approach is that a change made to any parent diagram (due to a bug, new release, or whatever) has to be manually copied into all models of the controller. The situation worsens if some of the TLC models are reused by other designs. In other cases, you may not want the source diagram of any of the parents to be available to the programmers who are reusing it.
Consequently, in this article I'll describe how inheritance is incorporated in the ESD framework, allowing diagrams to inherit (multiple) parent diagrams without actually copying the parent diagrams into the child diagrams. To the best of my knowledge, the only software that currently enables ESD inheritance is BetterState Pro, a graphical state-machine design tool my company has developed.
Using two existing ESDs as parent (or base) designs, Figure 3 illustrates a diagram which captures all specification items for the TLC example. Inheritance is specified during code generation. The BetterState code generator provides a list of diagrams which will be inherited by the current diagram. In the case of Figure 3, these will be base1 (Listing One) of Figure 1, and base2 (Listing Two) of Figure 2. Each ESD is realized as a C++ class that inherits the classes of the parent controllers. Listing Three is the generated code for the child chart in Figure 3.
Each class has private data, representing its internal state configuration (we use more than one state variable to realize an ESD). It also has a public function, BS_Fire(), which executes a transition from one state to the following state within that class, much like the C function call described in my previous article. However, before the child's BS_Fire() function fires, it calls the parent's BS_Fire(), thereby allowing the parent controllers to traverse their own internal transitions.
Similarly, a controller starts up in its default state (for example, the Idle state in Figure 3) using its class constructor to set up the initial states. Again, the child's constructor calls its parent's constructors before it actually executes its own constructor. A special set of public functions, denoted as BS_in_St_xxx_Py() (where xxx is a state name and y is a page number) is available for sensing the state of a parent class from its children. In Figure 3, for example, the controller actually starts its activity only sensing that base1 (Figure 1) has moved to the Red2Main state. It aborts its activities and moves back to the Idle state when it senses that base1 has moved out of Red2Main. Similarly, it senses whether base2 (Figure 2) has detected a Car or a Truck. (Visual priorities were discussed in the previous article.) The two transitions in Figure 3--one from Car2 to Car3, and the other from Cars to Camera_Shoot--might fire simultaneously, thereby creating a race situation. The arrowhead colors in Figure 3 resolve this conflict by giving the purple transition (to Camera_Shoot) a higher priority than any of the white transitions.
Visual priorities are ever more important in the context of ESD inheritance. The transition labeled !BS_in_St_Red2Main_P1() leads to the Idle state. This transition might fire at the same time as another transition in Figure 3. Conflicts such as these are commonly generated when the designer of the child diagram is not aware of the design details of a parent diagram. In the example, you resolve the race situation by assigning a Black arrowhead to the transition leading to the Idle state, thereby giving it a higher priority than the purple or white transitions in Figure 3. Such priority assignments are effective for eliminating races between child and parent controllers. For example, a parent controller can specify that the three highest-priority levels are reserved for its class, out of which one was manifested by its own parent. This way, conflicts are resolved without disclosing or assuming knowledge about the contents or behavior of the parent design.
BetterState Pro 2.0 allows an ESD to inherit (or be inherited by) other types of diagrams, such as Petri-Nets (PNs). A PN looks much like a state diagram, but is by definition fully concurrent and requires special synchronization to limit concurrency and introduce explicit, sequential operation. This contrasts with an ESD, which is by definition sequential and requires concurrency to be explicitly defined. The code generator generates the same class structure for ESDs and PNs; therefore, an ESD can inherit and sense the state of a PN, and vice versa.
In my previous article, I showed how state hierarchy acts as an important mechanism for top-down design and teamwork design of complex controllers. In the context of this article, hierarchy is even more important because events from parent controllers often have a global effect on the child controller. For example, when base1 moves out of the Red2Main state in Figure 1, it must cause the child controller of Figure 3 to quit all activities and to return to the Idle state. Using hierarchy, we need no more than one transition to describe such a behavior.
Animated playback is a tool for simulating and debugging a design using animation. In Figure 1, for example, when the program being debugged moves from Green2Main to Red2Main, the Green2Main regains its original color and Red2Main turns red, thereby showing that it is the current state. Such visual simulation and debug capabilities are crucial for correctly designing complex diagrams, especially when concurrency is involved. When inheritance is incorporated, the animation tool ripples through the class hierarchy showing the state changes in each class, according to the actual order of execution. My approach to code generation (based on the realization of ESD and PN controllers as classes) lets you instantiate various composite objects. For example, you can use arrays or dynamic arrays of ESDs. Many modern applications need such capabilities, including cellular automata and fine-grain, parallel applications.
Figure 1 Base1 is the top-level processing of traffic light controller.
Figure 2 Base2 is a subcomponent of traffic light controller that controls a camera.
Figure 3 Complete traffic controller inherits from base1 and base2.
//==============================================================
// C++ Code-Generation Output File #1 of 1. Generated for Chart base1
// by the BetterState Code Generator v2.x
// R-Active Concepts, Cupertino CA, 95014, doron@ractive.com
//----- State ID dictionary for base1
// Use this dictionary to symbolically reference your states (for those
// States that you gave names in the chart editor).
//------------------------------------------------------------
#ifndef DUMMY
#define DUMMY -7
#endif
#ifndef DONT_CARE
#define DONT_CARE 0
#endif
const int St_Yellow_All_P1 = 9; // mapped to PS[0]
const int St_Green2Main_P1 = 61; // mapped to PS[0]
const int St_Red2Main_P1 = 72; // mapped to PS[0]
const int St_On_going_P1 = 60; // mapped to PS[1]
class CHRT_base1 {
private:
int PS[2];
int NS[2];
int BS_i;
// This flag, being 1, indicates that controller (or one of it's parents)
//reached a Terminal state.
int BS_Terminal_Reached;
//Local variables you defined in your drawing:
public:
// Use Macro to test across threads whether St_Yellow_All_P1 is present state
int BS_in_St_Yellow_All_P1(){return (PS[0]==St_Yellow_All_P1);};
// Use Macro to test across threads whether St_Green2Main_P1 is present state
int BS_in_St_Green2Main_P1(){return (PS[0]==St_Green2Main_P1);};
// Use Macro to test across threads whether St_Red2Main_P1 is present state
int BS_in_St_Red2Main_P1(){return (PS[0]==St_Red2Main_P1);};
// Use Macro to test across threads whether St_On_going_P1 is present state
int BS_in_St_On_going_P1(){return (PS[1]==St_On_going_P1);};
CHRT_base1()
{
// Reset state assignments
PS[0]=St_Yellow_All_P1;
NS[0]=DONT_CARE;
PS[1]=DUMMY;
NS[1]=DONT_CARE;
// On_entry actions for reset states
Color_Main=YELLOW;Color_Sec=YELLOW;
BS_Terminal_Reached=0;
}
int BS_Fire();
}; //end of BS controller class
int CHRT_base1::BS_Fire()
{
//-------
if (PS[0]==St_Yellow_All_P1)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
if (!Reset)
{
NS[0] = St_Green2Main_P1 ;
NS[1] = St_On_going_P1 ;
Color_Main=GREEN; Color_Sec=RED;
}
//-------
if (PS[1]==St_On_going_P1)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
if (Reset)
{
NS[0] = St_Yellow_All_P1 ;
NS[1] = DUMMY ;
Color_Main=YELLOW;Color_Sec=YELLOW;
}
//-------
if (PS[0]==St_Green2Main_P1)
if ( (NS[0] == DONT_CARE)
)
if (TIMEOUT)
{
NS[0] = St_Red2Main_P1 ;
Color_Main=RED; Color_Sec=GREEN;
}
//-------
if (PS[0]==St_Red2Main_P1)
if ( (NS[0] == DONT_CARE)
)
if (TIMEOUT)
{
NS[0] = St_Green2Main_P1 ;
}
// Assigning next state to present-state
for (BS_i=0;BS_i < 2;BS_i++)
if (NS[BS_i] != DONT_CARE)
{PS[BS_i]=NS[BS_i]; NS[BS_i]=DONT_CARE;}
// This return statement return 0 if and only if a terminal state was reached.
// Use the return value to break out of a loop in which the controller
// is called, if you want to suspend the controller in a terminal state.
return (!BS_Terminal_Reached);
};
// Bye
//==============================================================
// C++ Code-Generation Output File #1 of 1. Generated for Chart base2
// by the BetterState Code Generator v2.x
// R-Active Concepts, Cupertino CA, 95014, doron@ractive.com
//----- State ID dictionary for base2
// Use this dictionary to symbolically reference your states (for those
// States that you gave names in the chart editor).
//------------------------------------------------------------
#ifndef DUMMY
#define DUMMY -7
#endif
#ifndef DONT_CARE
#define DONT_CARE 0
#endif
const int St_s0_P2 = 140; // mapped to PS[0]
const int St_Peek1_P2 = 144; // mapped to PS[0]
const int St_Peek2_P2 = 145; // mapped to PS[0]
const int St_Car_detected_P2 = 146; // mapped to PS[0]
const int St_Truck_detected_P2 = 147; // mapped to PS[0]
const int St_Peeks_P2 = 143; // mapped to PS[1]
class CHRT_base2 {
private:
int PS[2];
int NS[2];
int BS_i;
// This flag, being 1, indicates that the controller (or one of it's parents)
//reached a Terminal state.
int BS_Terminal_Reached;
//Local variables you defined in your drawing:
public:
// Use this Macro to test across threads whether St_s0_P2 is the present state
int BS_in_St_s0_P2(){return (PS[0]==St_s0_P2);};
// Use this Macro to test across threads whether St_Peek1_P2 is present state
int BS_in_St_Peek1_P2(){return (PS[0]==St_Peek1_P2);};
// Use this Macro to test across threads whether St_Peek2_P2 is present state
int BS_in_St_Peek2_P2(){return (PS[0]==St_Peek2_P2);};
// Use Macro to test across threads whether St_Car_detected_P2 is present state
int BS_in_St_Car_detected_P2(){return (PS[0]==St_Car_detected_P2);};
// Use Macro to test whether St_Truck_detected_P2 is present state
int BS_in_St_Truck_detected_P2(){return (PS[0]==St_Truck_detected_P2);};
// Use Macro to test across threads whether St_Peeks_P2 is the present state
int BS_in_St_Peeks_P2(){return (PS[1]==St_Peeks_P2);};
CHRT_base2()
{
// Reset state assignments
PS[0]=St_s0_P2;
NS[0]=DONT_CARE;
PS[1]=DUMMY;
NS[1]=DONT_CARE;
BS_Terminal_Reached=0;
}
int BS_Fire();
}; //end of BS controller class
int CHRT_base2::BS_Fire()
{
//-------
if (PS[0]==St_s0_P2)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
if (Energy > THRESH)
{
NS[0] = St_Peek1_P2 ;
NS[1] = St_Peeks_P2 ;
}
//-------
if (PS[0]==St_Peek1_P2)
if ( (NS[0] == DONT_CARE)
)
if (Energy > THRESH)
{
NS[0] = St_Peek2_P2 ;
}
//-------
if (PS[0]==St_Peek2_P2)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
if (Energy > THRESH)
{
NS[0] = St_Car_detected_P2 ;
NS[1] = DUMMY ;
}
//-------
if (PS[1]==St_Peeks_P2)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
if (Energy > HIGH_THRESH)
{
NS[0] = St_Truck_detected_P2 ;
NS[1] = DUMMY ;
}
// Assigning next state to present-state
for (BS_i=0;BS_i < 2;BS_i++)
if (NS[BS_i] != DONT_CARE)
{PS[BS_i]=NS[BS_i]; NS[BS_i]=DONT_CARE;}
// Return statement return 0 if and only if a terminal state was reached.
// Use the return value to break out of a loop in which the controller
// is called, if you want to suspend the controller in a terminal state.
//
return (!BS_Terminal_Reached);
};
// Bye
//=========================================================================
// C++ Code-Generation Output File #1 of 1. Generated for Child Chart
// by the BetterState Code Generator v2.x
// R-Active Concepts, Cupertino CA, 95014, doron@ractive.com
//----- State ID dictionary for Child
// Use this dictionary to symbolically reference your states (for those
// States that you gave names in the chart editor).
//-------------------------------------------------------------------------
#ifndef DUMMY
#define DUMMY -7
#endif
#ifndef DONT_CARE
#define DONT_CARE 0
#endif
const int St_Wait_P3 = 164; // mapped to PS[0]
const int St_Car_1_P3 = 177; // mapped to PS[0]
const int St_Car_2_P3 = 178; // mapped to PS[0]
const int St_Car_3_P3 = 179; // mapped to PS[0]
const int St_Camera_Shoot_P3 = 181; // mapped to PS[0]
const int St_Idle_P3 = 182; // mapped to PS[0]
const int St_Cars_P3 = 180; // mapped to PS[1]
const int St_Active_P3 = 185; // mapped to PS[2]
class CHRT_Child: public CHRT_base1,CHRT_base2 {
private:
int PS[3];
int NS[3];
int BS_i;
// This flag, being 1, indicates that the controller (or one of it's parents)
//reached a Terminal state.
int BS_Terminal_Reached;
//Local variables you defined in your drawing:
public:
// Use this Macro to test across threads whether St_Wait_P3 is present state
int BS_in_St_Wait_P3(){return (PS[0]==St_Wait_P3);};
// Use this Macro to test across threads whether St_Car_1_P3 is present state
int BS_in_St_Car_1_P3(){return (PS[0]==St_Car_1_P3);};
// Use this Macro to test across threads whether St_Car_2_P3 is present state
int BS_in_St_Car_2_P3(){return (PS[0]==St_Car_2_P3);};
// Use this Macro to test across threads whether St_Car_3_P3 is present state
int BS_in_St_Car_3_P3(){return (PS[0]==St_Car_3_P3);};
// Use Macro to test across threads whether St_Camera_Shoot_P3 is present state
int BS_in_St_Camera_Shoot_P3(){return (PS[0]==St_Camera_Shoot_P3);};
// Use this Macro to test across threads whether St_Idle_P3 is present state
int BS_in_St_Idle_P3(){return (PS[0]==St_Idle_P3);};
// Use this Macro to test across threads whether St_Cars_P3 is present state
int BS_in_St_Cars_P3(){return (PS[1]==St_Cars_P3);};
// Use this Macro to test across threads whether St_Active_P3 is present state
int BS_in_St_Active_P3(){return (PS[2]==St_Active_P3);};
CHRT_Child():CHRT_base1(),CHRT_base2()
{
// Reset state assignments
PS[0]=St_Idle_P3;
NS[0]=DONT_CARE;
PS[1]=DUMMY;
NS[1]=DONT_CARE;
PS[2]=DUMMY;
NS[2]=DONT_CARE;
BS_Terminal_Reached=0;
int BS_Fire();
}; //end of BS controller class
int CHRT_Child::BS_Fire()
{
//Fire parent controller(s), and ripple down if Terminal state(s) was reached.
BS_Terminal_Reached ||= (!CHRT_base1::BS_Fire());
BS_Terminal_Reached |= ~CHRT_base2::BS_Fire();
//-------
if (PS[0]==St_Idle_P3)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE) && (NS[2] == DONT_CARE)
)
if (BS_in_St_Red2Main_P1())
{
NS[0] = St_Wait_P3 ;
NS[1] = DUMMY ;
NS[2] = St_Active_P3 ;
}
//-------
if (PS[2]==St_Active_P3)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE) && (NS[2] == DONT_CARE)
)
if (!BS_in_St_Red2Main_P1())
{
NS[0] = St_Idle_P3 ;
NS[1] = DUMMY ;
NS[2] = DUMMY ;
}
//-------
if (PS[1]==St_Cars_P3)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
if (BS_in_St_Truck_detected_P2)
{
NS[0] = St_Camera_Shoot_P3 ;
NS[1] = DUMMY ;
}
//-------
if (PS[0]==St_Wait_P3)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
if (BS_in_St_Car_detected_P2())
{
NS[0] = St_Car_1_P3 ;
NS[1] = St_Cars_P3 ;
}
//-------
if (PS[0]==St_Car_1_P3)
if ( (NS[0] == DONT_CARE)
)
if (BS_in_St_Car_detected_P2())
{
NS[0] = St_Car_2_P3 ;
}
//-------
if (PS[0]==St_Car_2_P3)
if ( (NS[0] == DONT_CARE)
)
if (BS_in_St_Car_detected_P2())
{
NS[0] = St_Car_3_P3 ;
}
//-------
if (PS[0]==St_Car_3_P3)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
if (BS_in_St_Car_detected_P2())
{
NS[0] = St_Camera_Shoot_P3 ;
NS[1] = DUMMY ;
}
//-------
if (PS[0]==St_Camera_Shoot_P3)
if ( (NS[0] == DONT_CARE) && (NS[1] == DONT_CARE)
)
{
NS[0] = St_Wait_P3 ;
NS[1] = DUMMY ;
}
// Assigning next state to present-state
for (BS_i=0;BS_i < 3;BS_i++)
if (NS[BS_i] != DONT_CARE)
{PS[BS_i]=NS[BS_i]; NS[BS_i]=DONT_CARE;}
// Return statement returns 0 if and only if a terminal state was reached.
// Use the return value to break out of a loop in which the controller
// is called, if you want to suspend the controller in a terminal state.
//
return (!BS_Terminal_Reached);
};
// Bye
Copyright © 1995, Dr. Dobb's Journal