=Paper=
{{Paper
|id=Vol-2019/me_1
|storemode=property
|title=A Look-Ahead Strategy for Rule-Based Model Transformations
|pdfUrl=https://ceur-ws.org/Vol-2019/me_1.pdf
|volume=Vol-2019
|authors=Lars Fritsche,Erhan Leblebici,Anthony Anjorin,Andy Schürr
|dblpUrl=https://dblp.org/rec/conf/models/FritscheLAS17
}}
==A Look-Ahead Strategy for Rule-Based Model Transformations==
https://ceur-ws.org/Vol-2019/me_1.pdf
A Look-Ahead Strategy for Rule-Based Model
Transformations
Lars Fritsche∗ , Erhan Leblebici∗ , Anthony Anjorin† and Andy Schürr∗
∗ TU Darmstadt, Germany
Email: firstname.lastname@es.tu-darmstadt.de
† Paderborn University, Germany
Email: anthony.anjorin@upb.de
Abstract—Model-Driven Engineering (MDE) promises an in- different stakeholders, model transformations often have
crease in the maintainability and extensibility of modern software to be ”bidirectional”, i.e., executable in either direction.
systems. Furthermore, it encourages the usage of multiple models In general, a pair of transformations in reverse directions
of the same system to simplify the involvement of different
stakeholders, tools, and domains. The concurrent engineering of (usually referred to as forward and backward transformations)
such multiple models requires, however, support for consistency as well as consistency checking between two given models
management including consistency restoration and consistency are needed to tackle consistency challenges in an MDE
checking of and between existing models. Bidirectional trans- landscape. These tasks are addressed by bidirectional model
formation (bx) approaches are able to address these challenges transformation (bx) approaches. Bx implementations can
with various paradigms that come along with different dis-
/advantages. Rule-based techniques, as one of these paradigms, be categorized into three paradigms, namely, bidirectional
provide a declarative approach to implementing such consistency programming languages (e.g., BiGUL [1]), constraint-based
management solutions. However, rule-based approaches rely on approaches (e.g., JTL [2]) and rule-based approaches (e.g.,
finding an appropriate sequence of rule applications, e.g., such TGG [3]). Bidirectional programming languages are powerful
that the transformation process does not lead to a dead-end. with respect to expressiveness and provide more fine-grained
In case of a wrong choice of rule applications, backtracking
(of arbitrary depth) is in general not a satisfactory solution as control over the transformation process. However, they
it has exponential runtime in the number of rule applications. usually entangle high-level transformation goals with the
We, therefore, propose a novel look-ahead strategy for rule- low-level (e.g., computation-focused) instructions of the
based bx approaches that governs the rule application process by underlying programming language. In contrast, constraint-
generating additional application conditions based on the current based approaches are based on relationship specifications
and possible future state of relevant edges in the model. We
demonstrate and evaluate our approach on a compact yet non- that are then checked and enforced with constraint solving
trivial scenario that requires careful decision making among rule techniques which in general yields good results but suffers
applications. from performance issues due to large search spaces as
compared to the other two techniques [4]. Rule-based
Index Terms—Model-driven development approaches, finally, offer a compromise as their performance
is better than constraint-based approaches, and transformations
I. I NTRODUCTION are implemented in a more declarative way as compared to
Model-Driven Engineering (MDE) has become an bx programming languages. In general, they rely on finding
important technique to cope with the increasing complexity an appropriate sequence of rule applications to perform a
of modern software systems. Its consequent use is said to transformation. This, however, can lead to dead-ends and
improve both the quality of developed software as well as undesired transformation results due to wrong choices when
the effectiveness of the development process. However, as applying the rules. A naive but expensive solution is to use
a software system evolves and becomes more complex, so backtracking to find the valid sequence or to correct a ”wrong”
do the underlying models that represent different views onto rule application. It is, however, in general too expensive and
the system. While each view has its own characteristics scales poorly to use such brute-force methods. Thus, the
and priorities, they normally share information that may amount of available choices of rule applications must be
be altered and changed such that it no longer complies limited by applying advanced static analysis techniques.
with other related models. To cope with these changes and
keep those related models consistent to each other is of In this paper we will focus on Triple Graph Grammars
particular interest for an integrated development process. (TGGs), which is a declarative, rule-based bx-approach to
Hence, tools are needed that analyse models for compliance define consistency between two correlated models. However,
with their correlated counterparts and, in case consistency as a rule-based technique, TGGs also have to avoid dead-ends.
has been violated, are able to transform the models into To cope with this, we propose in this paper a look-ahead
an updated consistent version without incurring unintended strategy for rule-based model transformations on the example
loss of information. As different models are maintained by of a TGG specification. It was inspired by look-ahead
techniques of string parsing approaches which were early speaking, it is highly beneficial to be able to automatically
adapted to improve graph grammar parsers. Furthermore, extract a meaningful documentation from an existing project
we conduct experiments with our look-ahead strategy and and furthermore, to keep it consistent. It might also make
evaluate its added-value with respect to reliability of model sense to first define a documentation structure and to extract
transformations, i.e., if dead-ends are reliably avoided. Last an EMF skeleton that conforms to the documentation so that
but not least, the performance of our approach is compared developers may work more purposively. Last but not least,
to an existing look-ahead strategy based on so-called ”filter for given projects and documentations in ongoing software
NACs” [5] with rather limited search space reduction projects it is often not clear which parts are still consistent to
capabilities and a naive TGG implementation without any each other and which are not. To discover (in-)consistencies
look-ahead at all. and return a valid mapping, that covers as many elements
of both sides as possible, is sometimes crucial when the
The rest of the paper is organized as follows: In Chapter II alternative would be to start the documentation from scratch.
we will introduce our running example and TGGs. Chapter These scenarios may be handled by bx approaches in general;
III introduces a novel look-ahead strategy that brings a however, we will focus on Triple Graph Grammars (TGGs)
minor overhead for forward (and analogously backward) as our tool of choice which is a rule-based bx technique.
transformations for the sake of more reliable transformations.
In case of more rule application-intensive tasks such as EPackage
EPackage
consistency checking, the strategy even yields a substantial Employee :
performance gain by reducing the search space of rule EClass
interface = false Person
Employee
applications. In Chapter IV we present the results of our
approach with respect to success rates and performance. Person :
EClass
Subsequently, in Chapter V we will discuss related work. interface = false Serializable Observable
Finally, in the last chapter we will summarize the results and
Observable :
give an overview over future work. EClass
interface = true
II. RUNNING E XAMPLE AND F UNDAMENTALS Serializable:
EClass
Our running example is depicted in Figure 1. It is interface = true
inspired by an example from the example zoo provided
by [6] and is concerned with the consistency between class Fig. 1. Running example
diagrams (metamodels) in the Eclipse Modeling Framework
(EMF) and a custom documentation structure. On the
left side, an EMF class diagram model consisting of two TGGs [3] are a declarative, rule-based bidirectional
EPackages and four EClasses is depicted while on the right transformation approach which was initially proposed
side, we have two Folders and four Doc-files. The blue by Schürr. While ”meta-models” define the structure of
dotted connections between the EMF and documentation models in a MDE context, a TGG specification defines
model represent traceability relationships between related consistency between instances of two meta-models. A TGG
elements in different models. In detail, the example consists consists of a finite set of transformation rules that define how
of an EPackage which contains two interfaces, namely consistent pairs of both source and target model co-evolve.
Serializable and Observable that are of type EClass Consistency is defined between structural features of the
(note the attribute values interfaces = true). Furthermore, source and target meta-model via a third one which is called
the EPackage contains additionally a sub-EPackage with the the correspondence meta-model. Each rule defines a pattern
two EClasses Person and Employee which are concrete where elements are said to be in source, correspondence or
classes. There exist multiple inheritance relations from target domain if they belong to the corresponding meta-model.
Person to Serializable and Observable where
Employee inherits from Person. The point of interest Figure 2 depicts the TGG rules of our running example.
in this example is the definition of multi-inheritance which We focus on an excerpt including structural features of and
may be defined in two ways, namely as generalization or between EPackage and EClass. The target side consists
as realization. EMF does not differ between generalization of Folders and Doc(-Files) which ideally should document
and realization and represents both relations uniformly. To the structure of Ecore packages and classes with their
still be able to differ between both, we have to take a look inheritance relations. Each TGG rule consists of two kinds
at the target of such an edge to see if it is defined as an of structural features, namely nodes and edges. Every node
interface or a concrete class. The documentation model on and edge has a state which determines if it is a context
the right side represents the same information as the left side or created element. The first state is depicted as black
with the minor difference that there are two explicit types of nodes and edges of a pattern, in the following referred
inheritance links, namely realizes and generalizes. Both links to as context elements, that are taken as pre-requisite for
are visualized in conformance to UML syntax. Generally each rule application. Green nodes and edges, additionally
++
++
++
++
++ one EClass. In contrast, R5 also defines correspondence for
:EPackage :P2F :Folder
:EPackage :P2F :Folder an inherits link but together with the EClass from which
classes files
R1: Package-To-Folder Rule ++ ++ ++ ++ ++ it origins. In summary, we demand that generalization can
++ ++
:EClass :C2D :Doc only be translated once together with the originating node.
:EPackage :P2F :Folder Furthermore, we allow multiple realizations as long as the
R4: EClass-To-Doc Rule
subpackage subfolder targeted EClass is an interface.
++ ++ ++ ++ ++
++ ++
:EPackage :P2F :Folder :EPackage :P2F :Folder
A TGG is a consistency specification for which operations
R2: Subpackage-To-Subfolder Rule classes
++ ++
files
++ such as forward and backward transformations or even
++ ++
++ ++
:EClass :C2D :Doc consistency checks can be derived. This means that in order
:EClass :C2D :Doc
inherits generalizes
to perform those operations, we have to operationalize the
inherits realizes ++ ++
++ ++ TGG rules first. In the following we will explain how to
:EClass
:EClass
:C2D :Doc interface==false
:C2D :Doc operationalize TGG rules to perform forward transformations;
interface==true
backward transformations are handled analogously. For a
R3: Inherits-To-Realization Rule R5: Inherits-To-Generalization Rule
forward transformation, the source side is given as an input
model and the target side is to be derived. Hence, in contrast
Fig. 2. EMF To Doc Example: TGG Rules
to model generation, we do not create new elements on the
source side, but rather mark those elements that have already
been translated. This implies that elements on the source
marked by ’++’, define which structural features are to side of a TGG rule are all context elements for a forward
be created in conformance to the pattern in case that the operationalization. Figure 3 depicts all ”forward rules” for
pre-requisite of the pattern is fulfilled. A major goal of
++ ++
defining patterns is to find matches, where a match is defined ++ ++ :EPackage :P2F :Folder
:EPackage :P2F :Folder
as a valid mapping of pattern elements to model elements.
classes files
Thus, a match defines an occurrence of the pattern in a model. F1: Package-To-Folder Rule ++ ++ ++
++ ++
:EClass :C2D :Doc
:EPackage :P2F :Folder
In the following, we will explain each of the five rules F4: EClass-To-Doc Rule
in detail: 1) The first rule R1 is axiomatic, due to the lack subpackage
++
subfolder
++ ++
of context elements. It does not define any pre-requisites but :EPackage
++
:P2F
++
:Folder :EPackage :P2F :Folder
creates an instance of type EPackage and a corresponding
F2: Subpackage-To-Subfolder Rule classes files
instance of type Folder. This correspondence is expressed as ++ ++ ++
++ ++
an instance of type E2F which is visualized by a hexagon :EClass :C2D :Doc
:EClass :C2D :Doc
and connects both of EPackage with Folder. 2) Given an inherits generalizes
inherits realizes ++
existing correspondence between elements as defined in R1, ++
:EClass
:EClass :C2D :Doc
R2 creates a sub-EPackage with a corresponding sub-Folder :C2D :Doc interface==false
interface==true
under the pre-requisite that a parent EPackage and Folder F5: Inherits-To-Generalization Rule
F3: Inherits-To-Realization Rule
have been found previously. 3) The other rules can be read
analogously, where R3 creates an inherits link on the source Fig. 3. EMF To Doc Example: Forward Rules
domain and a corresponding realizes link on the target domain
if the target EClass of the inherits link is an interface. 4) R4 our given TGG. Note that all former created nodes on source
creates an EClass and a corresponding Doc given already side have been converted to context elements. The difference
processed EPackage and Folder instances. 5) Last but not between those elements that are context in the plain TGG
least, R5 defines that an EClass and an inherits link on source rule and those we converted is depicted as marking signs
side are created together with a corresponding Doc and a on each node and edge on source side. X indicates that this
generalizes link on target side, under the condition that the element has to have a marking which in turn means that it
context EClass node is not an interface. must be already translated. → X indicates that this rule
marks an unmarked element to be translated if it is applied.
Note that the distinction between R3 and R5 is made These forward rules are able to transform a given source
due to the EMF specification of EClass that internally model into a corresponding target model in accordance with
describes whether it is an interface or a real class. In Java the original TGG rules.
a class may generalise only one other class which prohibits
multiple inheritance using the extends directive. It is, however, With the given forward rules this process is not deterministic
possible to mimic multiple inheritance using interfaces and as is demonstrated in Figure 4. It depicts a source model
the implements directive which is extensively used by EMF. with two EPackages, namely root and sub where sub is
For this reason R3, in combination with R1, is able to define a sub-package of root. Given this model and our forward
correspondence of multiple inherits links originating from rules, there are two rule application sequences that are
III. L OOK -A HEAD S TRATEGY
root:EPackage
subpackage For forward and backward transformations, the challenge is
how to find a sequence of rule applications that does not lead
sub:EPackage
to a dead-end where certain elements remain untranslatable.
To cope with this, advanced static analysis techniques [5], [8]
F1@root F1@root can be used to filter sequences such that ideally all applicable
F1@sub F2@sub
rules avoid dead-ends by construction. Let us assume that
the TGG rules of Figure 2 have been operationalized for
:Folder :Folder forward transformations as explained in the previous chapter.
subfolder
Furthermore, we assume that our input model is equivalent
to the one presented in Figure 4. It consists of two instances
:Folder :Folder of EPackage where sub is a subpackage of root. In the
left case we translate both EPackages using F1; however, this
Fig. 4. The upper model may be translated with two rule application
lets the subpackage edge remain untranslated as there is no
sequences. The left sequence ends in a state where the subpackage edge forward rule that translates a single subpackage edge. The
can not be translated with any forward rule. The right sequence translates right case represents a viable sequence of rule applications.
all elements.
The root element still gets translated using F1 but sub and
subpackage are both translated using F2, leaving no element
or edge untranslated. Summarizing, the conflict arises from a
local choice of applicable rules where one choice leads to a
possible and are depicted at the bottom of the Figure. The dead-end.
sequence of the left is an application of the axiomatic F1 rule
on both EPackages; however, this results in a state where To prevent this, Herman et al. [5] proposed a static
the subpackage edge can no longer be translated with any analysis with the goal to guide the transformation process
forward rule. The reason for this is that there are no forward towards a control flow that avoids untranslated edges. The
rules that will enable us to translate the edge after we applied analysis consists of three steps which are explained in the
F1 to sub. The second sequence on the right depicts a following: 1) First, we analyse those situations where a node
valid rule application sequence that does indeed translate all gets translated taking into account the possibility of other
elements. It translates both EPackages plus the subpackage rules being able to translate all adjacent edges. 2) For every
link between them if we apply F1 to root and F2 to sub detected node and for every possible edge, the analysis tries
and the link. The choice of which rule application sequence to to find a forward rule which might be applied in the future
use is not trivial, but may be solved through backtracking by to translate this edge. In general this means that a rule has
revoking former application, if a dead-end has been detected. to be found where the current to-be-translated element is a
However, backtracking can result in exponential runtime in context element and the problematic edge is translated. If we
model size which quickly becomes infeasible [5]. A standard find such a rule the analysis terminates. 3) If such a ”saving”
approach (inspired from string parsing) is to use a look-ahead rule can not be found then the current rule is extended
to reduce the cases in which backtracking is required. by a negative application condition (NAC) that forbids the
existence of such an edge for the given node.
Last but not least, we need to operationalize the rules
such that for a given source and target model we find These NACs are called ”filter NACs” as their intention
correspondences between both which is often referred to as is to filter those rule applications that would otherwise
consistency check. In the context of TGGs this means that certainly lead the model transformation process into a dead-
we have to construct the correspondence model given both end. An example of this is given in Figure 5. It depicts the F1
source and target models. In general, this means that we rule which is extended by a NAC that prohibits the existence
have to collect matches of the source and target sides of of an incoming subpackage edge for the p1 element, such an
each TGG rule, respectively. Given these two sets, we have edge would always remain untranslated in case that this rule
to find correspondences if possible and in an optimal way. is applied. This solves the previously encountered problem as
This means that a pairing has to be determined between for now there will never be an F1 match that translates sub
matches coming from the source side of a rule to those of leaving the only translating forward rule to be the one that
the target side. The challenge is the complexity of this task does not lead to a dead-end.
regarding possible pairing candidates and that certain pairs
of matches contradict each other. This problem can be solved Now, if we extend our example model as depicted in
efficiently with constraint solving techniques as was proposed Figure 6, we will very likely encounter a new dead-end
by Leblebici et al. [7] as long as the search space of possible case. The example consists of the sub EPackage plus
pairing candidates remains moderate. two EClasses in sub, namely Employee and Person.
++ ++ from later application, thus, leaving elements untranslated.
++ ++
p1:EPackage :P2F :Folder The steps are described in the following: 1) Similar to the
previous analysis we extend the given rules such that for
F1: Package-To-Folder Rule every created element we search for existing edges that are
not translated by this rule. 2) If such an edge does not exist,
the rule may be applied directly. 3) However, in case there
are such potential edges, the analysis demands that there also
:EPackage exists a valid match of the source1 side of a saving rule.
subpackage
Hence, we demand that after applying this rule, the edge is
still translatable in the future. This concept of demanding
the existence of a certain pattern C, that extends a match
p1:EPackage
of another pattern P, is called positive application condition
(PAC) which intuitively represents an ”if-then” relationship.
Fig. 5. Package-To-Folder - NAC
:EPackage :P2F :Folder
Additionally, Employee inherits from Person. Translating
classes files
this model requires translating the EPackage first which is ++ ++ ++
handled the same way as before and may be disregarded, ++ ++
ec1:EClass :C2D :Doc
which leads us to the translation of both EClasses. Now,
we have to use F3, F4 and F5 to translate the remaining F4: EClass-To-Doc Rule
elements and the inherits edge between them but, as in the
previous example, we may end up in a dead-end depending
on which forward rules we apply. A valid rule sequence
would be to apply F4 to Person following the application ec1:EClass
of F5 to Employee and the remaining inherits edge. But, inherits Premise
starting with F4 applied to Employee would lead to an
untranslated inherits edge as there would never again be any ec2:EClass
rule able to process the edge. The reason why the previous
analysis does not hold in this case is that the F3 rule is Conclusion
theoretically able to translate an inherits edge wherever it
originates from. Thus, there won’t be any NAC generated ec1:EClass :C2D :Doc
for the F4 rule that would guide the translation process safely.
inherits realizes
ec2:EClass
sub:EPackage :C2D :Doc
interface==true
classes classes
Inherits-To-Realization Rule - Source
Person Employee
:EClass :EClass
inherits
interface=false interface=false
Fig. 7. EClass-To-Doc - PAC
F4@Person
F4@Person
F4@Employee
F5@Employee
Figure 7 depicts the approach applied to F4. Analogously
to the former analysis, we inspect ec1 as a node whose
:Folder :Folder translation might lead to an untranslated inherits edge. In
files files contrast to the former approach, the possibility that the edge
might be translated by F3 no longer suffices. We, thus,
Person:Doc Employee:Doc Person:Doc generalises Employee:Doc
demand that in case the inherits with ec2 as target exists,
there must also exist a concrete match of the source side of
Fig. 6. The upper model may be translated with two rule application
sequences. The left sequence ends in a state where the inherits edge can
the F3 rule. This ensures that the edge can be translated by
not be translated with any forward rule. The right sequence translates all F3 in the future, which means that we have a real look-ahead
elements. for specific edges to prevent them from not being translatable
later on.
To rule out these cases we propose a more sophisticated
look-ahead strategy which also takes into account that context
and attribute constraints might prevent a false ”saving” rule 1 target for backward translation
In case there are no such saving rules, this approach is one remaining edge contradicts the translation of another, yet,
equivalent to the former static analysis because the Premise untranslated edge.
may be true but the Conclusion will always be false.
This means that the resulting Premise and Conclusion are IV. E XPERIMENTAL R ESULTS
reduced to a (filter) NAC forbidding the existence of a
certain edge as it would remain untranslatable. Hence, if no In the preceding chapter we presented both filter NACs and
saving rules are found, the PAC-based look-ahead strategy our novel PAC-based look-ahead strategy. Both approaches
falls back to filter NACs. This means, however, that filter were shown on a TGG specification based on our running
NACs are a subset of our new PAC-based look-ahead strategy. example. In the following, we will evaluate the new approach
by comparing it to filter NACs and an implementation that
The PAC-based look-ahead strategy can also be used to does not use any context analysis techniques. We, therefore,
improve the performance of consistency check. As was state three research questions that are investigated with our
explained in the previous chapter, consistency checking relies experiments: RQ1: For each approach, how does consistency
on the discovery of matches of the source and target side check scale with increasing model size? RQ2: Does the new
of each rule. By applying our strategy on both source and approach introduce an advantage to model transformations
target side, we can filter matches analogously to the forward regarding success rates? RQ3: How is the performance of
transformation case. Hence, by decreasing the number of model transformations comparing all three approaches and
possible matches, we decrease the search space of possible does the new analysis technique introduce any noticeable
pairings. This, finally, increases the efficiency as the number overhead?
of possible candidates increases quadratically in the number
of matches. The experimental results that support this As our tool of choice we use eMoflon [9] a graph
conclusion are presented in the next chapter. transformation tool that supports TGGs. In the current version
it is based on an incremental pattern matcher [10] and an ILP
The implementation of this strategy appears computationally solver [11]. The experiments are executed on a machine with
more expensive at a first glance as for every rule which is an Intel Core i5-3550, 16GB memory and Ubuntu 16.04.
applied, we have to find also occurrences for those patterns
that have been added by the analysis. However, given a The models used for forward transformation and consistency
closer look specifically at the generated PAC, the matches check are generated in conformance to the previously
for all saving rules must have already been collected before, introduced TGG specification. Thus, by applying the original
which is in general the bottleneck of rule-based bx tools. TGG rules directly, we are able to simultaneously build up
Thus, before applying a certain match, we only have to check all three domains. Consequently, we can create models of
for the existence of these pre-calculated matches regarding arbitrary size from scratch that are consistent with respect
possible saving rules. to our TGG specification by applying rules this way. Hence,
we define the model complexity as the number of rule
There are cases when this analysis does not suffice and applications that were used to generate a model. Note,
the translation process still ends up in a dead-end. Any however, that this model size is not equal to the number of
scenario which requires an analysis of a sequence of future nodes since R3 does not create a node but rather an edge
rule applications of length greater than one to avoid a between two existing ones; thus, the model size is an indicator
dead-end is not considered here. Handling these scenarios for the complexity that results not only from nodes but also
requires a look-ahead greater than one; however, this requires from inheritance relationships. For both tested scenarios we
the generation of nested application conditions. For a look- generate 20 variations for each examined model size and
ahead of k, a nesting level of k+1 is needed, which is not repeat execution of each variation five times. The resulting
covered by our implementation that only supports simple times are the average values over the median times of each
application conditions with a Premise and a Conclusion variation.
pattern for a look-ahead of one. Nonetheless, the extension to
nested application conditions can be handled analogously by For consistency check, we will measure the time to
generating PACs for every Conclusion. highlight performance differences between a naive approach,
filter NACs and our PAC-based look-ahead strategy. Since
Another scenario is connected to our assumption that consistency check is handled as a constraint solving problem,
dead-ends in a transformation process correspond to single we do not have to measure the success rate because even if
untranslatable edges. This means that we always identify such irrelevant matches are processed, the optimal solution of the
cases when there is a possibly untranslatable edge; however, problem does not change.
the current implementation may underestimate the rule
application sequence needed to translate all adjacent edges. RQ1: Figure 8 depicts the measured times for consistency
It does not incorporate that there are dependencies between check, including the search for rule occurrences on both
Conclusion patterns (saving rules) where the translation of source and target model and the constraint solving to find an
400 100
350
success rate in [%]
300 80
time in [s]
250 60
200
150 40
100
20
50
0 0
0 2000 4000 6000 8000 10000 1 3 5 7 9 20 40 60 80 100 140 180
model complexity model complexity
No Analysis Filter NACs PAC-based Look-Ahead No Analysis Filter NACs Look-Ahead
Fig. 8. Consistency Check - Measured times Fig. 9. Forward transformation - Success rates
optimal mapping. The biggest model size2 using the naive almost reaches 0 percent for model sizes bigger than 30. In
approach is 360 with a runtime of ~6 minutes. Using filter comparison to the former plot, filter NACs tend to perform
NACs, consistency check is able to process a maximal model much better as long as we transform solely EPackages, since
size of 3000 in slightly more than 6 minutes. Finally, the filter NACs can not cope with dead-ends that occur during
PAC-based look-ahead enables consistency check to process translation of an EClass hierarchy. The success rate drops
a maximal model size of 10000 within approximately one from almost 100 percent to 80 for a model size of 6 and
minute. rapidly falls down to almost 0 percent for model sizes 10 to
40. In contrast, the PAC-based look-ahead strategy is always
The results show a significant performance gain of the able to translate all elements such that no nodes or edges stay
PAC-based look-ahead and filter NACs compared to an untranslated.
implementation without analysis. The naive approach tends
to be impractical for even moderate model sizes as the The success rates of filter NACs and an implementation
runtime increases too steeply. The filter NACs perform better without analysis drop rapidly until they reach ~0 percent at
in comparison to the naive approach; however, for models a model size of 40. In contrast, the PAC-based look-ahead
bigger than 2000 the runtime increases substantially. Finally, strategy remains constantly at 100 percent. This means that
the runtime of PAC-based look-ahead rises very slightly the transformation does not end up in a dead-end and that all
and stays close to one minute for model sizes of 10000. elements were translated.
These measurements show that both filter NACs and our
PAC-based look-ahead are able to decrease the complexity RQ3: Given those results, we now want to take a look
of the consistency check task. Regarding the PAC-based at the runtime performance which is depicted in Figure 10.
look-ahead, we can even further increase the performance and As can be seen, all three plots are not easy to keep apart
process a multiple of the maximal model size of filter NACs. as they lie very closely. The maximum times for a maximal
model size of 4500 are 89 seconds for the naive approach, 97
Regarding forward transformation, we are interested in two seconds for filter NACs, and 97 seconds for the PAC-based
measurements. First, the success rate of the transformation look-ahead strategy.
where an execution is considered as failed if not all elements
were translated3 . Second, pattern matching is usually the 120
bottleneck of modern rule-based tools and both filter NACs 100
and our PAC-based look-ahead strategy introduced new 80
time in [s]
patterns that have to be found in the input model. Thus, we 60
are interested in how expensive the new approach is with 40
respect to the runtime performance. 20
0
RQ2: Figure 9 depicts the success rate of each experiment. 500 1000 1500 2000 2500 3000 3500 4000 4500
All three plots start at a success rate of 100 percent for model complexity
a model size of one as this is equivalent to a model with No Analysis Filter NACs Look-Ahead
one single package and dead-ends are not to be expected.
However, after adding a sub-EPackage or a new EClass the Fig. 10. Forward transformation - Measured times
success rate for the naive approach drops to 60 percent and it
2 Equivalent to the number of rule applications used to generate the model The measurements indicate that all three approaches
3 Note that each input model is by construction fully translatable have a very similar performance. The naive implementation
using no analysis tends to be slightly faster; however, the correct and that all elements were successfully translated [18].
performance gain comes at the price of a very low success
rate. Comparing filter NACs with the PAC-based look-ahead, Our implementation of filter NACs is based on the work of
there is no considerable difference of performance. Note, Klar et al. [8] and Hermann et al. [5]. Both papers analysed
however, that the naive approach and filter NACs leave certain TGGs with negative application conditions and introduced
elements untranslated. This means that the runtime may be a strategy to avoid several rule application sequences that
affected such that it appears slightly faster than it would if all would leave elements untranslated. Klar et al. focussed on the
elements were processed. Nonetheless, since the runtime of identification of dangling edges, i.e., edges that may remain
our PAC-based look-ahead strategy does not differ noticeable untranslated if a node is translated using a specific rule. If
from the other approaches, we conclude that the introduced such an edge is detected, the analysis reacts as was explained
overhead is not relevant and may be disregarded. in Chapter VI and tries to generate a NAC that forbids the
application of the rule in this particular case. In contrast,
Threads to Validity. External validity is of major interest but Hermann et al. used the critical pair analysis [19] to argue on
it requires investigation of further non-trivial case studies. how to avoid several critical pairs of rules that conflict with
We argue, however, that the presented example represents a each other; however, both yield similar results using NACs
significant challenge that emerges frequently with increasing and can not cope with scenarios in which it is necessary to
case complexity. Furthermore, the results are based on an use PACs.
incremental pattern matching framework and a constraint
VI. C ONCLUSION AND F UTURE W ORK
solver. It remains to be investigated if the performance
changes considerably with the use of other frameworks and In this paper we introduced a novel PAC-based look-ahead
solvers. Internal validity has to be investigated further as the strategy for rule-based bx techniques. Although the approach
generation of test cases was not deterministic. This means was explained and exemplary implemented for a TGG
that, despite of the number of repetitions and variations for specification, it is not limited to TGGs. In fact, it offers
each model size, the results have a certain variance of around a strategy for rule-based approaches in general to govern
+/- 15 percent. the transformation process in order to avoid dead-ends or
even enhance the performance. To evaluate our approach, we
V. R ELATED W ORK chose a compact excerpt of the Eclipse Modeling Framework
In this paper we proposed a PAC-based look-ahead strategy together with a corresponding documentation structure as our
for rule-based bx approaches. This strategy was inspired by running example. We conducted experiments using a naive
predictive string parsing techniques which use a variable TGG implementation, an existing statical analysis called filter
look-ahead to resolve issues that arise while parsing. Early NACs and our PAC-based look-ahead strategy. In the case of
approaches that tried to adapt string parsing techniques to forward transformations, we showed that the new approach is
graph grammars were inspired by the Early-Style-Parser [12] able to avoid dead-ends that both other approaches encounter.
which is a top-down-parser that uses dynamic programming Furthermore, the results indicate that the costs of the new
to determine rule application entry points. As such it is strategy do not raise significantly regarding the performance.
related to our TGG approach; however these parsers were For consistency check we showed that the new approach
restricted to context-free grammars and suffered from a high is able to greatly increase the performance with respect to
computational complexity [13], [14]. Nonetheless, recent runtime and maximal model size as it reduces the overall
work also shows that predictive parsing yields promising number of possible rule applications in the search space.
results for graph grammar parsing, by substantially reducing
the runtime complexity for specific scenarios [15]. To our For future work, it remains open to investigate more
knowledge, we are the first to elevate the idea of using a challenging scenarios, e.g., more complex models and
look-ahead for rule-based bx approaches to reduce the space consistency specifications with intensive look-ahead
of conflicting rule applications. requirements. Another important topic is the extensibility
of this approach. Examples for such extensions might be, a
Our implementation is based on eMoflon as our tool of look-ahead factor of more than one, or a generalisation of this
choice; however, there are other TGG tools such as TGG approach to also handle conflicts that do not only arise from
Interpreter [16] or MoTE [17]. MoTE is restricted to conflict- adjacent edges of nodes but also from nodes themselves. Last
free TGG specifications, implying that for any translatable but not least, the evaluated implementations are based on an
element there is only one applicable rule at any time. external incremental pattern matcher framework and an ILP
Using this restriction, MoTE does not need backtracking solver. For future work, we would like to investigate how the
or a look-ahead to resolve issues as they forbid ambiguous performance changes with respect to other frameworks.
specifications in general [18]. TGG Interpreter is not limited R EFERENCES
to conflict-free TGG specifications; however, the tool is
[1] H.-S. Ko, T. Zan, and Z. Hu, “Bigul: A formally verified
not able to use any backtracking or look-ahead to avoid core language for putback-based bidirectional programming,” in
conflicts. Hence, it does not guarantee that its results are Proceedings of the 2016 ACM SIGPLAN Workshop on Partial
Evaluation and Program Manipulation, ser. PEPM ’16. New 289, 2002, gETGRATS Closing Workshop. [Online]. Available:
York, NY, USA: ACM, 2016, pp. 61–72. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S157106610480210X
http://doi.acm.org/10.1145/2847538.2847544
[2] A. Cicchetti, D. Di Ruscio, R. Eramo, and A. Pierantonio, JTL:
A Bidirectional and Change Propagating Transformation Language.
Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 183–202.
[Online]. Available: http://dx.doi.org/10.1007/978-3-642-19440-5 11
[3] A. Schürr, Specification of graph translators with triple graph
grammars. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995, pp.
151–163. [Online]. Available: http://dx.doi.org/10.1007/3-540-59071-
4 45
[4] A. Anjorin, Z. Diskin, F. Jouault, H. Ko, E. Leblebici, and
B. Westfechtel, “Benchmarx reloaded: A practical benchmark
framework for bidirectional transformations,” in Proceedings of
the 6th International Workshop on Bidirectional Transformations co-
located with The European Joint Conferences on Theory and Practice of
Software, BX@ETAPS 2017, Uppsala, Sweden, April 29, 2017., 2017,
pp. 15–30. [Online]. Available: http://ceur-ws.org/Vol-1827/paper6.pdf
[5] F. Hermann, H. Ehrig, U. Golas, and F. Orejas, “Efficient analysis
and execution of correct and complete model transformations based
on triple graph grammars,” in Proceedings of the First International
Workshop on Model-Driven Interoperability, ser. MDI ’10. New
York, NY, USA: ACM, 2010, pp. 22–31. [Online]. Available:
http://doi.acm.org/10.1145/1866272.1866277
[6] “Bidirectional transformations - ecore2html example,” http://bx-
community.wikidot.com/examples:ecore2html, 2017, accessed: 2017-
06-29.
[7] E. Leblebici, A. Anjorin, and A. Schürr, Inter-model Consistency
Checking Using Triple Graph Grammars and Linear Optimization
Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2017,
pp. 191–207. [Online]. Available: http://dx.doi.org/10.1007/978-3-662-
54494-5 11
[8] F. Klar, M. Lauder, A. Königs, and A. Schürr, Extended Triple Graph
Grammars with Efficient and Compatible Graph Translators. Berlin,
Heidelberg: Springer Berlin Heidelberg, 2010, pp. 141–174. [Online].
Available: http://dx.doi.org/10.1007/978-3-642-17322-6 8
[9] E. Leblebici, A. Anjorin, and A. Schürr, Developing eMoflon with
eMoflon. Cham: Springer International Publishing, 2014, pp. 138–145.
[Online]. Available: http://dx.doi.org/10.1007/978-3-319-08789-4 10
[10] D. Varró, G. Bergmann, Á. Hegedüs, Á. Horváth, I. Ráth, and Z. Ujhelyi,
“Road to a reactive and incremental model transformation platform:
three generations of the viatra framework,” Software & Systems Model-
ing, vol. 15, no. 3, pp. 609–629, 2016.
[11] “Gurobi solver,” http://www.gurobi.com, 2017, accessed: 2017-06-29.
[12] J. Earley, “An efficient context-free parsing algorithm,” Commun.
ACM, vol. 13, no. 2, pp. 94–102, Feb. 1970. [Online]. Available:
http://doi.acm.org/10.1145/362007.362035
[13] H. Bunke and B. Haller, A parser for context free plex grammars.
Berlin, Heidelberg: Springer Berlin Heidelberg, 1990, pp. 136–150.
[Online]. Available: http://dx.doi.org/10.1007/3-540-52292-1 10
[14] G. Costagliola, M. Tomita, and S.-K. Chang, “A generalized parser for 2-
d languages,” in Proceedings 1991 IEEE Workshop on Visual Languages,
Oct 1991, pp. 98–104.
[15] F. Drewes, B. Hoffmann, and M. Minas, Predictive Top-Down
Parsing for Hyperedge Replacement Grammars. Cham: Springer
International Publishing, 2015, pp. 19–34. [Online]. Available:
http://dx.doi.org/10.1007/978-3-319-21145-9 2
[16] J. Greenyer and J. Rieke, “Applying advanced tgg concepts for a
complex transformation of sequence diagram specifications to timed
game automata,” in Proceedings of the 4th International Conference on
Applications of Graph Transformations with Industrial Relevance, ser.
AGTIVE’11. Berlin, Heidelberg: Springer-Verlag, 2012, pp. 222–237.
[Online]. Available: http://dx.doi.org/10.1007/978-3-642-34176-2 19
[17] D. Blouin, A. Plantec, P. Dissaux, F. Singhoff, and J.-
P. Diguet, Synchronization of Models of Rich Languages with
Triple Graph Grammars: An Experience Report. Cham: Springer
International Publishing, 2014, pp. 106–121. [Online]. Available:
http://dx.doi.org/10.1007/978-3-319-08789-4 8
[18] E. Leblebici, A. Anjorin, and y. v. Andy Schürr and Stephan Hildebrandt
and Jan Rieke and Joel Greenyer, journal=ECEASST, “A comparison
of incremental triple graph grammar tools.”
[19] D. Plump, “Essentials of term graph rewriting,” Electronic
Notes in Theoretical Computer Science, vol. 51, pp. 277 –