Contents
The goal of this project is to provide a general framework for the analysis and transformation of Ptolemy II models.
In Ptolemy, models are visually represented with graphs. An actors is represented with a box or an icon. A relation is represented with a filled diamond shape. A links between an actor's port and a relation is represented with a solid line. For the two-way connection between an actor's output port and another actor's input port, the relation in between is usually omitted from the visual representation, and the two links connecting the relation with the two ports are simplified as a single line.
Ptolemy supports hierarchy in the models. A component with detailed implementation hidden inside is called a composite actor. The modal model in Figure 1, “Top-level view of the StateTracker model” is an example. Because of the hierarchy, the graph representation of models that we deal with are not flat in general. [1]
Note that in this work we do not distinguish model analysis from model transformation, because the former can be considered as a special case of the latter, where only certain attributes of the model change. Data dependency, firing counts, firing order, buffer sizes, etc, are all examples of such attributes.
In the context of this work, models refer to instances of the above described graph representation. Therefore, model transformation is graph transformation in essence. This is different from model transformation in other contexts, such as XML transformation using XSLT (the Extensible Stylesheet Language Transformations), program source transformation, database schema transformation, etc.
Traditional graph transformation techniques deal with graphs that has no hierarchy. Transformation is expressed with rules. Each rule has a left hand side (LHS) and a right hand side (RHS), both of which are graphs. (A rule may also have a boolean application condition, which must be satisfied to apply it.) To apply a rule to a host graph (a jargon to call the graph to be transformed), there must exist a subgraph isomorphism m1 from the LHS to the host graph. After the application, there must be a subgraph isomorphism m2 from the RHS to the result graph. The application itself can be considered as preserving the elements (nodes or edges) that are in both the LHS and the RHS, removing the elements that are in the LHS but not in the RHS, and adding the elements that are not in the LHS but are in the RHS.
Hierarchy is an extension that has been explored. Almost all the contemporary model transformation tools support hierarchy in their models, though the hierarchy may have different meanings in different tools.
In practice, rules are usually combined in some way to form more complex transformation. For example, a tool may manage a set of rules, and assign a numerical priority to each of them. A rule is enabled if subgraph isomorphism m1 exists from its LHS to the host graph. Transformation can be performed if at least one rule is enabled. If multiple rules are enabled at the same time, the one with the highest priority has preference.
Besides this simple priority-based scheme of rule choice, more sophisticated and flexible schemes have been developed, such as those that employs state machines or control flows, which we will review below.
Various representations have been used for model transformation rules. In this section, we summarize some representations found in the contemporary tools.
LHS and RHS of a transformation rule may be separately specified in two graphs. The commonality between the two graphs is the nodes and edges that need to be found in the pattern and are preserved after the transformation. If we use GL = <VL, EL> to represent the LHS graph and use GR = <VR, ER> to represent the RHS graph, then this commonality is GL ∩ GR = <V', E'>, where V' = VL ∩ VR and E' is the intersection of EL and ER with dangling edges removed. On application of a rule in this representation, the nodes and edges in GL but not in GL ∩ GR are removed, and the nodes and edges in GR but not in GL ∩ GR are added to form the result graph.
This simple representation of transformation rules are widely adopted by a number of tools, including PROGRES (PROgrammed Graph REwriting Systems) [11], AGG (the Attributed Graph Grammar system) [10], AToM3 (A Tool for Multi-formalism and Meta-modelling) [6], VMTS (Visual Modeling and Transformation System) [4], and VIATRA2 [1], a component of the Eclipse GMT (Generative Model Transformer) sub-project.
The observation that in many cases there is a lot of commonality between the LHS and the RHS leads to another representation that combines the two in one graph. It makes it much easier to maintain this commonality when either the LHS or the RHS is changed, while in the separated representation, changing part of the LHS that should be preserved in the result requires according change on the RHS.
There must be a way to distinguish the parts to be deleted or added, however, in the combined graph. The parts to be deleted exist in the LHS only, and those to be added exist in the RHS only. In FUJABA (From UML to Java And Back Again) [9], the parts to be deleted are tagged with “{destroyed}” in red, and the parts to be added are tagged with “{new}” in green. This notation has not been standardized, however. GReAT (Graph Rewriting and Transformation) [5] highlights the parts to be added in blue and the parts to be deleted in green.
The complexity of subgraph isomorphism makes it necessary to keep the transformation rules simple. The first step of rule application is to find a match from the LHS to a subgraph of the host graph. The complexity of this step has been shown to be NP-complete. Therefore, a key to fast test of a rule'a is enablement is to limit the size of its LHS, and to associate attributes and constraints that help to restrict the search space. Another reason for keeping the LHS simple is to improve readability.
Because rules are usually simple, in many applications they need to be combined to express more complex transformation. The simplest way of combining rules may be to sequentialize them and apply them one by one. In practice, more flexible ways of combining rules are needed, leading to the invention of various control mechanisms.
Tools such as AToM3 transforms the initial graph with a set of rules until no more rules apply. Before every transformation, a rule must be picked from the set of enabled rules. If only one rule is enabled, that rule is applied and a new graph is generated for the next transformation (unless no more rules apply to the new graph). If multiple rules are enabled at the same time, the choice among them is based on the enabled rules' priorities, which are the numbers associated with them a priori. If more than one rule has the same priority, the choice is non-deterministic. For some applications, this non-deterministic behavior may be desired, while for others it is unexpected and may reflect a design flaw.
The difficulty of specifying priority for rules is that the rule designer must forsee the rules that may be enabled at the same time, and break the tie with appropriate priority numbers. This requires knowledge about the model's execution as well as the tools used to execute them (since different tools may produce diverse execution behavior that the model allows).
To better control the application of rules in a model transformation process, control flow constructs, such as branches and loops, are supported in some existing tools, such as FUJABA. [8] In the story diagrams supported by FUJABA, edges between nodes represent the transfer of control. Diamond shapes denote branches, with a condition labeling each of its out-going edges. A block in the diagram can be considered as a task. This is similar to traditional control flow diagrams, except that within the blocks are single graph transformation rules, each of which is an atomic step of transformation.
Graph
Rewriting Formal Definitions
is a one-page summary on the key concepts on graph rewriting, based on
[3].
An introduction to graph rewriting with the PacMan example can be found here:
Introduction to
Graph Rewriting
. These slides are inspired by [7]
and [12].
[1]
Advanced
model transformation language constructs in the VIATRA2 framework
. SAC '06: Proceedings of the 2006 ACM symposium on Applied computing. Oct. 2006. Esslingen, Germany. 1280-1287. BIBTEXEndNote
[2] Model
transformation with triple graph grammars. Model Transformations in Practice Workshop. Oct. 2005. BIBTEXEndNote
[3] The design and implementation of a graph rewrite engine for
model transformations. Department of Computer Science and Engineering, Helsinki University of Technology. May 2005. BIBTEXEndNote
[4]
A
systematic approach to metamodeling environments and model transformation
systems in VMTS
. International Workshop on Graph-Based Tools (GraBaTs). Oct. 2004. Rome, Italy. BIBTEXEndNote
[5]
A
UML-based graph transformation approach for implementing domain-specific model transformations
. International Journal on Software and Systems Modeling. 2003. BIBTEXEndNote
[6] AToM3: A tool for multi-formalism and meta-modelling . FASE '02: Proceedings of the 5th International Conference on Fundamental Approaches to Software Engineering. Apr. 2002. Grenoble, France. BIBTEXEndNote
[7] Tutorial introduction to graph transformation:
A software engineering perspective. International Conference on Graph Transformation (ICGT 02). Oct. 2002. Barcelona, Spain. BIBTEXEndNote
[8]
Story
diagrams: A new graph grammar language based on the unified modelling language and Java
. Lecture Notes in Computer Science. 296-309. 2000. BIBTEXEndNote
[9]
The FUJABA environment
. ICSE '00: Proceedings of the 22nd International Conference on Software Engineering. Jun. 2000. Limerick, Ireland. BIBTEXEndNote
[10]
AGG: A tool enviroment
for algebraic graph transformation
. Proceedings of Applications of Graph Transformations with Industrial
Relevance (AGTIVE). Sep. 1999. Kerkrade, The Netherlands. BIBTEXEndNote
[11]
Graph
grammar engineering with PROGRES
. Proceedings of the 5th European Software Engineering Conference. Sep. 1995. Sitges, Spain. 219-234. BIBTEXEndNote
[12] Practical use of graph rewriting. Department of Computing and Information Science, Queen's University. Kingston, Ontario, Canada. 95-373. Jan 1995. BIBTEXEndNote
[1] Not all hierarchical models can be easily converted into flat ones while preserving their designed behavior. This is due to the fact that at any level of the hierarchy, only one model of computation is allowed, but different models of computation can be used across levels.