In the previous chapter, you saw how vague statements can be transformed into a concrete and unambiguous specification of the problem logic realized as a set of executable models. The models contain problem-oriented concepts that you can discuss with your customers and users to make informed decisions about the relevant problem logic. Although completed models define exactly what the implementation should do, they do not say just how to do it.
Now we must decide how to translate the various model elements into code:
How are classes and instances represented in the program?
How will the identifier attributes be realized in memory?
How will instances be accessed?
How will relationships be navigated?
How will events be signaled and dispatched?
And so on. We must ensure that every model element is translated into code to realize all of the required functionality. And foremost, we must end up with a functioning and efficient implementation. When models are being created, we are focused on analyzing the requirements and capturing the logic of the problem in executable modeling constructs. When models are translated, we must analyze the models themselves to make decisions about the appropriate code constructs to implement the model logic.
This chapter serves as an introduction and overview of the key decisions that must be made when translating the ATC model. In the subsequent chapter, we get our hands dirty and start building a pycca model script to specify those decisions. For now, though, we just take an inventory of what needs to be done.
The types of decisions discussed here are specific to both our target platform and to the way pycca accomplishes a model translation. This does not imply that the process of translation is unique to our platform and methods. Different platforms necessarily require varied strategies for the implementation and, consequently, a distinct mapping from model elements to implementation. Nonetheless, we continue to focus on pycca and our particular target platform to illustrate how our example becomes a running program.
Reviewing the Target Platform
The target platform sets boundaries for a practical implementation. Our target of small, embedded microcomputers, for example, leads us to hold all of our application data in directly addressable memory. Because we intend to use C as an implementation language, and C exposes variable addresses, we have decided to use the memory address of an instance as an implementation-based identifier. Where possible, we replace each identifier from the model with this implementation-defined identifier. For example, Duty Station.Number is replaced with its instance’s memory address. Using a pointer-based identifier then allows us to use pointer values to navigate relationships, resulting in many implementation efficiencies. Our platform uses C as the implementation language, but the same principles can be applied to any other statically typed language such as Java. In that event, a Java-specific translator with compatible runtime libraries (pyjca, let’s say) would be required. But that’s a different book (bonus points if you get the acronym pajama to work).
Figure 3-1 illustrates our overall process leading from models to code, using pycca. The model is transformed in two steps.
Figure 3-1. Overview of pycca translation
The first step is to encode all of the model elements, from all three facets, as a series of pycca language statements in a single file. We call this the model script. This script captures the structural aspects of the models as well as the processing they perform. This script incorporates, along with the model elements, numerous design decisions. You also include C code in the script at a later point. (pycca is an acronym for “pass your C code along,” and that’s the C you’ll be passing along.) The set of available pycca statements defines a domain-specific language (DSL) for an xUML model implementation. We’ll introduce the language as the example is worked out and guide you through the key concepts. If you wish to read all the details about pycca, they are readily available in online materials. The DSL is summarized in Appendix C.
When your model script is complete, you feed it to the pycca program, which transforms any pycca statements along with included C code for the activities into a specially organized source and header file pair. The C code for the activities contains supplied preprocessor macro invocations to interface to the runtime code. From here, the C preprocessor, compiler, and linker do all the work: the pycca C macros are expanded and pycca-supplied runtime libraries are linked to yield a runnable program.
When modeling, we consider the three facets of data, behavior, and processing, in that order. When translating, we follow the same order. Translation decisions for implementing the data facet of the model impact the other facets, so it is important to pin down the application data structures first. In the following sections, we show the types of implementation decisions that must be made to translate each facet of the model.
Working with the Class Model
We first script the entire structure of the class model. This consists of the classes, attributes, data types, and all relationships. We also populate the structure by specifying an initial instance population. Figure 3-2 shows the pycca script elements that are derived from the class model.
Figure 3-2. Defining the class model as a script
A class is made up of attributes, and each attribute is constrained by a data type. Data types, then, are essential building blocks that must be defined before we can proceed with the rest of the class model.
Data Types
Figure 3-3 shows the transformation of model data types to implementation types.
Figure 3-3. Data type decisions
A model data type defines the set of values that may be assigned to a class attribute. Aircraft Quantity is a model-level concept that represents an actual quantity of aircraft. This means that it is a positive integer, because it is nonsensical to talk about negative quantities of aircraft. An implementation data type defines a set of allowable values for a programming language variable. The C language data type corresponding to Aircraft Quantity would probably be unsigned. Be sure to choose an implementation data type that supports all operations required by the modeled data type.
C typedef statements bind each model data type with its associated implementation data type. These typedef statements can then be included at the top of the generated code file.
Classes and Attributes
Each modeled class is specified with a pycca class statement. Just as a model data type is different from an implementation data type, a class in the model is different from its corresponding implementation class. Because pycca converts each class statement into a C struct, there are no classes in the generated code at all.
Figure 3-4 shows the transformation from modeled class to C structure.
Figure 3-4. Translating model classes to C structures
The class statement encloses a series of attribute and reference statements. The descriptive, identifier, and referential roles of each attribute require different implementations.
A descriptive attribute, such as Control Zone.Traffic, has real-world meaning. Its implementation data type defines the set of values consistent with this real-world meaning. An identifying attribute, such as Control Zone.Name, which is used in a descriptive manner, is handled the same way.
By contrast, an identifier attribute with no real-world meaning, such as Duty Station.Number, is simply deleted. Pycca creates an implementation-defined identifier for each class instance. If a model identifier is not used for any descriptive purposes, we can substitute the generated identifier for it. This technique is so commonly used in implementation languages that we tend to overlook the fact that we are substituting one identifier for another.
Associations
A referential attribute, such as Control Zone.Controller, is handled in the context of associations. The specification of associations and referential attributes requires more consideration because a significant gap exists between the “this class is related to that class” model-level abstraction, and the implementation collection and pointer traversal mechanisms. The model purposely leaves many choices up to the implementer. We could, for example, choose to use a linked list or array traversal mechanism for a particular association. Or a self-balancing tree. To decide, we need to examine the runtime characteristics of each association, and then encode that decision in a pycca statement and let the pycca processor generate the relevant C code.
When an instance must refer to a single related object, the simplest way is to map a referential attribute to a pointer. Because referential attributes refer to identifying attributes of the associated class, and because we are using the address of the instance as an implementation-defined identifier, storing a pointer value in the place of a referential attribute realizes the model-level association.
This simple approach works well when following the pointer, but would be cumbersome in the other direction, because this would mean we’d have to search the objects of a class looking for matching pointer values. For the price of the memory occupied by a pointer, storing a pointer in both classes makes following in both directions efficient. On the other hand, the single-sided reference approach would be sufficient and efficient if there were no accesses from the “one side” to the “other side.”
So, we approach the implementation of an association by examining the needs of each side and considering each model association as two independent access directions. Figure 3-5 shows how the association, R2, is decomposed into one direction referring from On Duty Controller to Control Zone, and one referring in the opposite direction from Control Zone to On Duty Controller.
Figure 3-5. Decomposing a model association
Then we decide on an implementation for each direction of the association based on direction of access, multiplicity, and changeability:
Access: Is the association accessed from one side only? Or from both sides? Storage for a reference is required only for the side that is accessed. What is the frequency of that access?
Multiplicity: How many instances participate in the association from each side? A multiplicity of one is implemented as a single pointer value. If the multiplicity is greater than one, multiple pointer values must be stored, and pycca gives us several common arrangements for that storage.
Changeability: Are the participating instances static, or do they change over time? If the instances participating in the association change, we will store the pointer values in data structures that are efficient to update.
When we translate the model, we decide on an implementation for each side of the association. So for the preceding example, we may choose to implement the association from the Control Zone to the On Duty Controller as a pointer, while a linked list would be preferable in the direction of On Duty Controller to Control Zone. We then encode those decisions in text by using the proper reference statement types. There are many more choices, but the main point is that you must decide on an implementation while encoding the model, and that decision should be based on the execution characteristics of the model.
Generalizations
In our interpretation of a generalization, each instance of a subclass refers to exactly one instance of the superclass, and each superclass instance refers to exactly one instance of a subclass from among all the subclasses of the generalization. This implies that when we traverse a relationship from the superclass instance to a particular subclass, we either find a single related instance, or we come up empty because the superclass instance is not actually related to an instance of that particular subclass. To implement the traversal from a superclass to a subclass, pycca uses a subtype statement as a part of the superclass class definition. The result is that pycca adds an extra member to the generated C structure that encodes the related subclass. This lets us navigate the generalization from the superclass to a subclass and know whether we have found a related instance.
Storage for the subclass objects can be implemented in one of two ways. Figure 3-6 shows the two alternatives.
Figure 3-6. Generalization implemention alternatives
One approach is to treat each sub/superclass relationship as a bidirectional association. In this formulation, each On and Off Duty Controller instance would require a reference to its corresponding Air Traffic Controller instance. The subclass statement in Air Traffic Controller would be declared as a reference subclass, and a pointer to the subclass would be generated as another ATC structure member.
The other approach is to store the related subclass as a member of a C union. In this formulation, the subclass statement in the ATC superclass would be declared to be of the union type. Pycca generates the structure of the superclass to have a C union member containing the structures of the subclasses of the generalization. Space for the subclass instance is then included as part of the space for the superclass instance. This technique is quite common in C to implement a form of inheritance, even though inheritance is not our intent here. The subclass instances no longer need a reference to the superclass, and navigating the generalization is done via pointer arithmetic rather than pointer indirection.
Both approaches have their tradeoffs. For simple cases, the union formulation is more space-efficient.
Initial Instance Population
The last part of data translation is to specify the initial instance population. These are the instances of a class that are to be in place when the system starts. It is analogous to specifying the starting state for a state model. As the system evolves in time, attribute values change from known starting values.
Our strategy is to place the initial instance data directly into memory as variable initializers so that no code is required to create instances at initialization time. There is usually a small amount of initialization code that copies data initializers into their proper memory location. This behavior is a guarantee of the C language, and the code is usually supplied as a compiler library and is run before main is invoked. This eliminates wasting memory on code that will be executed only once. And we also avoid having to write tedious sequences of code just to set the values of structure members. Just as important, the initial instance population gives us insights prior to runtime for generating more-efficient code.
The initial population of the domain was specified as a table in Chapter 2. We can encode the table for each class, and store the instances of that class as an initialized C array. Descriptive attributes are assigned to the appropriate structure member in the initializer for the array element as shown:
table Control_Zone(Czone_Name Name) (Aircraft_quantity Traffic) R2@sfo {"SFO37B" {27} -> atc53@oak {"OAK21C" {18} -> atc67@sjc {"SJC18C"} {9} -> atc51end
Because we have generated an implementation-defined identifier (namely, the address of the object in memory) for each class instance, we need a way to refer to instances to specify the association and generalization pointer values. We cannot use actual addresses, because they are not known until link time. So pycca allows you to associate an optional name with the @ symbol on the left and to use that name when specifying the reference values. Pycca keeps track of where the named instances reside in the allocated storage array and emits the proper address expressions as initializers. Naming an instance is optional, but if you don’t name it, you can’t refer to it later.
Pycca also allows you to specify whether a class population is static or dynamic, indicating whether instances are created or deleted at runtime. A static population is allocated only enough space to hold the initial instance population. For a dynamic population, the total allocated space holds both the initial instance population plus the number of additional slots declared for it. All classes have a fixed-size storage pool allocated to them at compile time. The runtime library manages each pool for dynamic allocation, but there may never be more class instances than allowed by the size of the storage pool. This means that class instances are never allocated on the system heap, and there are no calls to malloc by the runtime library. This is in keeping with the usual design conventions for embedded microcontrollers.
Populations can also be marked as constant. For embedded systems, memory is usually partitioned into read-only and read/write types. There is usually much more read-only memory than read/write memory. A constant population is placed in read-only memory, which means that its attributes cannot be updated and that it cannot have an associated state model. Model classes that contain only specification data usually can be marked as constant and so save RAM memory.
Describing the State Models
We depicted state models graphically in the previous chapter, because the diagrams make it easier to visualize and achieve a well-designed solution. But this representation is incomplete for testing, implementation, and error analysis because a state diagram highlights expected normal behavior. The diagram does not show how to process an event that occurs and does not trigger a transition. When implemented, state machines have an annoying tendency to execute those unexpected transitions. Does the unexpected event require an error condition? Or was the event anticipated, but not warranting a transition?
There are three possible responses when an event is dispatched:
A transition to a new state occurs.
The event is ignored.
It is a logical impossibility for the event to occur in the given state.
The first response, a transition, represents common, expected behavior.
Sometimes the best response to events, like children, is to ignore them. Events may arrive too late or too early. Consider the response to an Open button pressed after an elevator door is already open. An ignored event is in the realm of normal behavior and does not constitute an error of any sort. It simply does not merit a transition, and is signified by an IG (ignore) response.
The third response is quite different. It says that there is no logical way the event could occur given the current state and is signified by a CH (can’t happen) response. If it does occur, it is deemed a serious error. When the runtime code encounters a CH transition, it causes a system error. It is important not to interpret a CH transition as a “shouldn’t happen” or “doesn’t happen very often” situation. A CH transition means that it logically cannot under any circumstance happen and, if it does, we no longer know how to proceed. Regardless of how small the probability that an event may occur in a state, it is not a CH transition if the probability is nonzero.
Figure 3-7 shows the progression from state diagram to its translated code. A state table specifies a definitive response (one of the three indicated previously) for every event in each state. In the first two cases, transition and ignore indicate that the response can and should be modeled. But with a CH response, the modeler indicates that the model is not designed to handle that case.
Figure 3-7. Translating a state model
We now specify each state model state by using a pycca machine statement. Each state and its activity code is specified by using a state statement. Each state table cell is specified by using a transition statement. A transition statement records the new state into which an event causes a transition from the object’s current state.
class Air_Traffic_Controller## attribute and reference statements#machine## state and transition statements#endend
States
Each state has an activity associated with it, which we capture as a function. Because the activity is executed on state entry, all inbound transitions to the state must carry the same event data, which is passed in as parameters.
Each state and its associated activity, executed upon entry into the state, is represented with a state statement:
state Verifying_Adequate_Break(Station_number Station_id){// C code intermixed with C macros that perform common// model-level operations such as signal generation and// relationship navigation.}
We cover the activity specification in Chapter 4, but you can see here that the activity in a state is enclosed within a state statement.
Events, Transitions, and Responses
State transitions specify responses to events by the state model:
transition OFF_DUTY - Ready_for_duty -> Verifying_Adequate_BreakThis statement says that, when in the OFF_Duty state, the Ready_for_duty event causes a transition to the Verifying_Adequate_Break state. There are no pycca statements for events. Their names are taken from the transition statements.
Executing State Machines
When we translate class models, some aspects of data operations, such as access to an attribute, are directly supported by corresponding C language constructs. State machines, on the other hand, are not a native C construct. To execute them, we must provide additional code, also written in C, to enable state machine behavior such as dispatching signals and calling state activities when transitions are invoked.
The transition statements encode state models statically, and we need runtime code to use the generated data structures to cause transitions. When a signal is dispatched, the runtime code uses the event signaled and the current state to determine the new state. Then, by calling a single function, it executes the logic of the new state. In Chapter 5, we show exactly how the runtime code signals and dispatches events.
Translating Processing
The last step is to translate the processing expressed by the action language of the model into C. Translation does not add to the processing logic in any way. We are concerned only with producing the C code that is logically equivalent to the processing specified by the action language statements. All of the processing is expressed by action language. When translated into C, a state’s actions are packaged by pycca into a function that is invoked upon state entry.
Coding from Models
The strategy is to take each line of action language and write the corresponding C. As we analyze the actions, we’ll find that that the elements fall into a small handful of categories. These are typically model-execution functions, data-access operations, and standard mathematical expressions and flow-control statements.
An action language statement may invoke an aspect of the model execution architecture. These include signal generation and relationship traversal. These types of elements may be translated by substitution with one of the many pycca-provided C macros. These macros hide decisions about data structures and just how a signal might be implemented.
Data access is provided by the normal C mechanism for access to structure members via a pointer. To realize this, each state action has a self variable that points to the instance memory. Action code can find and manipulate data across an association by using macros such as link and unlink, which hide the association implementation.
State action code must also interface to the runtime event dispatcher to generate events. We provide a set of helper C preprocessor macros so that we can use the same names for events as used in the state model. Pycca generates preprocessor symbol definitions to encode the state and event names into numbers. The naming conventions of that encoding are hidden by a set of preprocessor macros so you can use the names in the state model definition even though we must ultimately produce something that the C compiler recognizes.
All other actions, such as computation and flow control, are coded in C statements that are passed directly through to the output code file.
Translating a Model
There is a method at work here, and the order of doing the tasks has been worked out to give the best results. In the next chapter, we show the translation of the ATC model by using the decision-making process described in this chapter. We repeat the steps taken here, substituting the specifics of the ATC model.
Summary
We have examined the key translation decisions that must be specified in a pycca model script so that the appropriate C code can be generated and, in some cases, passed along.
Class models are broken into data type, class, attribute, and relationship definitions. We convert class definitions into pycca class definitions that end up as C structure declarations. Initial instance populations are specified in tabular form, to be converted into a set of array initializers.
State models, expressed as tables, are specified as a collection of state and event/response statements. State models define data structure values, including a state table, used by the runtime event dispatch mechanisms. Each state activity is converted into a function.
The correspondence between the encoded source and C output is direct and predictable. Pycca generates the many kinds of arbitrary encodings that are required, such as encoding event names into integers; it calculates the pointer values for relationship references, and it orders the resulting code in a way that suits the C compiler. The results are an ordinary C code and header file pair that can be integrated into the system build.