Archives for posts with tag: MDA

Blogs by Johan den Haan, Stefano Butti and Jordi Cabot raised interesting discussions about code generation (CG) and model interpretation (MI). One observation I took from these discussions is that MI is still little known. Previously I demonstrated operation of a custom-made model interpreter for a so-called weighbridge domain. Today I would like to share my experience of building this interpreter in a model-driven way.

MDE Approach

Two main choices underpin the process and technology used to develop the interpreter:

  1. Execution semantics of the interpreter is defined within the problem domain itself (weighbridge in this case), without translating it to another domain (e.g. .Net or Java) as it is the case with CG. Such definition of semantics is also known as operational semantics. The advantage is reduction of development complexity: out of at least 2 domains needed for CG, only one and the more abstract domain is sufficient.
  2. Operational semantics is defined within an MDE framework. This enables customization of modeling language for problem domains besides that of the weighbridge example. Moreover, transformation capabilities are used to define operational semantics. 

Domain-specific_nested_interpretation_mde_framework

Figure 1: Domain-specific, nested interpretation (DSNI) MDE framework

Figure 1 shows the MDA framework [1] after it has been adapted to reflect the above mentioned choices. (If you are confused between MDA and MDE, you might find this article useful.) In contrast to MDA, there is no PIM or PSM model, but single computational independent model (CIM) written in DSL. CIM is both source and target of Transformation Tool. Transformation Tool carries out transformation classified as same language, same model. Transformation Definition defines operational semantics. It is not important if Transformation Definition Language (TDL), extends the Metalanguage as in MDA or is customizable by means of meta-specification. Therefore TDL is omitted from the framework and TDL selection criteria are defined instead (see below). Finally, new concept System Context is connected to Transformation Tool. This is due to the fact that interpretation as system exhibits external behavior through communication with other systems.

This approach can be described as nested interpretation, where a domain-specific interpreter is executed (nested) by a generic interpreter. From this perspective, Transformation Tool assumes the role of a generic interpreter and execution of Transformation Definition fills in the role of the domain-specific interpreter.

TDL Selection Criteria

Selection criteria for transformation definition language are:

  • declarative modeling 
  • support for domain-specific notation

These criteria help to reduce development complexity and improve communication with problem domain experts.

Selected MD Technology

AToM3 is a free language workbench written in Python and under development at the Modelling, Simulation and Design Lab (MSDL) in the School of Computer Science of McGill University. The workbench closely matches the DSNI framework and meets the TDL selection criteria. 

In AToM3, DSLs and models are described as graphs. From a language specification written in the metalanguage (ER formalism), AToM3 generates a tool to visually manipulate (create and edit) models written in the specified DSL. Model transformations are performed by graph rewriting. The transformations themselves can thus be declaratively expressed as graph-grammar models. However, AToM3 provides no communication infrastructure as needed by the framework.

Proof of Concept

As demonstration, a language specification for the weighbridge domain was defined (see sections domain and weighbridge DSL here) and graph rewriting was used to model operational semantics (see below). Source code of AToM3 itself, being written in Python, was extended to support web services for the communication purpose.

Operational Semantics

As blueprint for operational semantics of the interpreter, we took πDemos [2], a small process-oriented discrete event simulation language. There is a number of πDemos events that change state of a weighbridge system. For each such event, [2] defined the transitions induced on system state. While the original used functional programming language, this work uses graph rewriting and a graph grammar (GG) rule is defined per event.

Priority GG Rule Description
50 importProcess Adds an external vehicle to EL
25 removeProcess Deletes a vehicle that has completed its todos (events)
40 newR Creates a new weighbridge
40 decP Creates a new vehicle class
40 newP Creates a vehicle from a vehicle class
40 getR Acquires a non-busy weighbridge
40 blockProcess Blocks a vehicle acquiring a busy weighbridge
40 promoteProcess Unblocks a delayed vehicle
40 useR Moves a vehicle on a weighbridge until service is complete
30 releaseResource Moves a served vehicle from a weighbridge to EL
41 putR Releases an occupied weighbridge

Table 1: Graph grammar rules of weighbridge events

Table 1 lists the minimum set of required events and their corresponding GG rules. Execution of such rules needs to be globally orchestrated through proper sequencing. The rules, together with execution sequencing, form an operational semantics model of the interpreter. 

For complete description of the model, please refer to [3]. In the following, we present a detailed description of an example rule, followed by the execution sequencing model.

Example GG Rule

LhsRhs

Figure 2: Subgraphs of the promoteProcess rule

Rule promoteProcess releases a busy weighbridge (bluish box in Figure 2.1) that delays at least one vehicle (yellow box labelled 5). In the new state, the weighbridge remains busy and the blocked vehicle (5) is removed from the head of queue Delay and inserted in waiting queue EL.

The rule is executed if:

  1. The left-hand side (LHS) shown in Figure 2.1 is matched in the host graph (the CIM model).
  2. Associated condition is true: the weighbridge in LHS is the one referred to in the imminent event putR (a todo) in the body (a todo list) of the first vehicle (label 21) in queue EL.

If the above holds, the matched part of the CIM model is substituted with the right-hand side (RHS) shown in Figure 2.2. Note new objects are labelled 10, 11, 13. The entities and relationships in RHS are initialized as follows:

  1. Objects copied from LHS keep all their properties. 
  2. Imminent event putR (a todo)  of the current vehicle (21) is completed. 
  3. All properties of blocked vehicle (5) are copied to vehicle (10).

Execution Sequencing

The execution sequencing is based on the next-event approach: Next event to execute is always the imminent event in the body of the current vehicle. Informally, the operational semantics of execution sequencing is as follows: if EL is empty, interpreter idles until at least one vehicle is inserted in EL. Such vehicle becomes current. If the body of the current vehicle is empty then it is removed from EL and EL is examined again. Otherwise, interpreter  executes a GG rule corresponding to the imminent event of the current and EL is examined again. Note that whenever interpreter is idle, EL is being updated with new vehicles that meanwhile might have arrived from system context.

The execution sequencing is implemented by organizing GG rules into groups, each group having its own base priority. These groups, in the descending order of priority are: vehicle removal, weighing activities and vehicle arrival. Within a group, each rule is assigned a relative priority. If pattern matching of two and more rules within a group is deterministic on the basis of LHSs and conditions, then these rules can share the same priority level. Example rule priorities are given in Table 1.

Conclusion

The demonstrated development approach is characterized by a very high level of abstraction, direct involvement of problem domain experts and absence of software development. All these factors contribute to fast development times: The lead time of this one man project including research and development was 3 weeks. Admittedly, tests of the produced model interpreter showed noticeable performance penalty due to 1) repurposing of MD technology that was not designed for use as interpreter and 2) the overhead introduced by nested interpretation. In my opinion there is much room for performance improvement and I am wondering if MDE can prove useful again. An important message from this experience is that model interpretation does not have to be prerogative of big commercial tools and can get closer to code generation in terms of accessibility.

References

[1] Anneke G. Kleppe, Jos Warmer and Wim Bast. “MDA Explained: The Model Driven Architecture: Practice and Promise”. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, April 2003.

[2] Graham Birtwistle and Chris Tofts. “An operational semantics of process-oriented simulation languages: Part 1 πDemos”. ACM Transactions on Modeling and Com- puter Simulation, 10(4):299–333, December 1994.

[3] Andriy Levytskyy. “Model Driven Construction and Customization of Modeling & Simulation Web Applications”. PhD thesis, Delft University of Technology, Delft, The Netherlands, January 2009.

Model interpretation approach is grasping attention of the model driven community. Industrial experiences of company Mendix has shown some very promising results. A recent post at a popular “model-minded” blog triggered a discussion about code generation versus model interpretation. Model interpretation in itself is not a new concept and there exist well known interpreters for generic and mainstream domains (e.g., Ptolemy and Simulink). The novelty in model interpretation today is that model driven methods provide efficiency and flexibility, which enable application of this concept to arbitrary problem domains. In a series of blogs we will illustrate this novel aspect and provide an example of model interpretation. Specifically this article will illustrate 1) how a custom modeling language (DSL) is developed for an arbitrary problem domain and 2) how a system behavior can be specified with the DSL and directly interpreted without any intermediate transformation steps. In a followup article we will show how a custom model interpreter can be efficiently built using a model driven method.

Model Interpretation As System

Traditional generative approaches like Model Driven Architecture (MDA) prescribe an (automated) code generation process that takes a system model as input and eventually produces code that implements the specified system. The system comes to existence when the code is executed. Alternatively, the code generation process can be skipped and a system model be executed directly.  Model Interpretation achieves such direct execution by means of a model interpreter. In this case the system comes to existence when the model is being interpreted. Thereby system behavior is completely defined by the model being interpreted. Fig. 1 illustrates a possible approach to model interpretation of event-driven systems.  An event-driven system exhibits behavior by generating (external) events in reaction to incoming external events. Therefore, the interpreter should support two-way event communication with the context. An example of an incoming external event is arrival of a positive signal from a motion sensor for an automated door. An outgoing external event could be a command to an actuator to open the door.

Media_httplsdluminisn_fhrvg

Figure 1: An approach to system as model interpretation In the figure, entities are shown as boxes and their roles w.r.t.  each other are shown in italic. Given that a domain-specific language (DSL) and an interpreter already exist, a domain expert uses the DSL to specify a system and its events at development time. Moving to the run-time, the same model (system configuration) represents the system and its events. During model execution, the interpreter reads system state from the model and interprets system events according to the semantics of the events. Interpretation may change the state of the system by changing the system configuration at run time, and communicate external events to the system’s context. Typically a sequence of external events is provided by the context of the system. Alternatively, these events can be specified in the system model and consequently generated by the interpreter itself (in this case, system behavior is simulated).

Domain

Today model interpretation can be applied to an arbitrary problem domain. To reflect this freedom, we chose a minor and uncommon weighbridge domain, whose purpose is to measure weight of vehicles. The following is a typical weighbridge scenario: One or more delivery vans arriving (at a factory) must pass over a weighbridge on entry. A weighbridge accepts one van at a time and each weighing operation takes a certain amount of time. If the weighbridge is busy, arriving vans join the waiting queue to the bridge. When the weighbridge becomes available again, the first van in the waiting queue drives over the bridge. This domain is characterized by a number of inherent variations, such as number of weighbridges, weighbridge capacity, weighing operation duration, number of arriving vans, arrival times of vans, etc.. The result is that a multitude of weighbridge system configurations are possible and per configuration a multitude of dynamic van arrival and weighing scenarios can play out.

Media_httplsdluminisn_foxbw

Figure 2: A weighbridge system modeled in a DSL Figure 2 shows a simplified weighbridge system configuration, originally described by Birtwistle and Tofts [1]. Yellow boxes are vans. The large blue box is a weighbridge and green entities are a van arrival queue (EL) at the factory and a van waiting queue (Delay) at a weighbridge. As you can see the factory’s configuration has a single weighbridge W, which is free at this time. Finally, three delivery vans V1, V2 and Main have arrived (external events). An execution of this model is illustrated further in the article. An AToM3 implementation of a DSL for the domain is briefly described next.

Weighbridge DSL

The earlier mentioned freedom of application depends on flexibility and efficient adaptation of model interpreters to new domains. Model driven methods achieve this flexibility through metamodeling. If you are not familiar with metamodeling, you can skip this section as it is not required for understanding the demo. A DSL is defined with abstract syntax, concrete syntax, static semantics and dynamic semantics. (Such a definition is known as metamodel.) Behind every DSL is a modeling paradigm that gives fundamental guidelines for metamodeling. In case of the weighbridge domain, a proper modeling paradigm is Process Interaction [2].

Media_httplsdluminisn_harrk

Figure 3: PI Metamodel For the purposes of this demo, a PI modeling language will suffice  and we will reuse and extend a PI metamodel developed by Juan de Lara [3]. We just have to keep in mind that Process and Resource in Juan’s metamodel correspond to van and weighbridge concepts in the demo domain. The abstract syntax of the PI DSL is illustrated in Figure 3. The concrete syntax of this DSL is illustrated in Figure 2. We skip static semantics (in other words, business rules) as the focus of the domain is interpretation, not domain modeling. The following is a brief description of the key PI concepts: Resource is a synonym for the Weighbridge concept. A weighbridge has the following attributes: Name is a unique identifier of Weighbridge: String State denotes availability of Weighbridge: Enum{idle, busy} Tproc is typical duration of weighing service: Time (used in simulated execution) Capacity denotes capability to weigh multiple vans at the same time: [1..N] Load denotes weighbridge’s capacity occupied with served vans: [0..Capacity] Process is a synonym of the Van concept. A van has the following attributes: Name is a unique identifier of Van: String Tcreation is time-stamp of Van’s arrival event: Time Tinitproc is the start time of weighing operation: Time Tendproc is the end time of weighing operation: Time Body is a sequence of tasks: sequence{task} (tasks examples are bridge access, van weighing, bridge exit, etc.) EVnext is the iterator for tasks in body: [0..N] For simulation purposes, additional concepts are defined: Time is a clock for simulated time. ProcIntGenerator specifies time intervals between van arrivals. Finally, to assist visualization of system state, the original metamodel was extended with additional relationship: manageElement specifies an operation (append, insert or remove) on an element (target end of this relationship) of a sequence (source end of this relationship). The final touch of DSL definition is dynamic semantics (meaning of DSL concepts). In the model interpretation approach, such semantics is defined in an interpreter. In case of a DSL and a pure interpretive approach there is a good chance that an interpreter exactly matching the DSL will need to be developed. More so if the interpreter has to meet additional specific requirements. In our case, such requirements were run-time visualization of system behavior and interpreter integration with the factory context (not covered in this article). In a followup article we will show how a custom model interpreter can be developed. Incidentally our development approach is also based on model interpretation.

Run Time Example

A picture is worth a thousand words. With that in mind an illustration of model interpretation is best done with a video. The following screencast shows execution of the weighbridge system configuration introduced earlier (see Figure 2). For the sake of visualization, execution is carried out in the step-by-step mode and displays how the state of the weighbridge configuration changes in response to events.

Conclusions

In our experience model interpretation is characterized by very fast development times. In fact it did not even feel like development at all as domain experts are completely shielded from all incidental technical details.  I believe that Birtwistle and Tofts, the scientists that coined the weighbridge benchmark, would feel at home with the demonstrated DSL and the interpreter in no time. With incidental complexity out of the equation and direct involvement of domain experts, I think we’ve come very close to the essential complexity of the domain and development times cannot be drastically improved any more. That said, I feel that those interested in this approach should be aware of run-time performance penalty due to interpreter indirection. Whether this will pose a problem, depends on the application domain. What are your experiences with model interpretation? What is your domain?

References

[1] Graham Birtwistle and Chris Tofts. An operational semantics of process-oriented simulation languages: Part 1 πDemos. ACM Transactions on Modeling and Computer Simulation, 10(4):299–333, December 1994. [2] Jerry Banks, editor. Handbook Of Simulation. Principles, Methodology, Advances, Applications, and Practice, pages 813 – 833. Wiley-Interscience Publication, New York, September 1998. [3] Juan de Lara. Simulacio ́n educativa mediante meta-modelado y grama ́ticas de grafos. Revista de Ensen ̃anza y Tecnolog ́ıa, 23, Mayo-Agosto 2002.