日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

Towards A Trace-based Approach to Increasing
the Comprehensibility and Predictability ofBidirectional Graph Transformations
Soichiro Hidaka, Martin Billes, Quang Minh Tran
Bidirectional graph transformation is expected to play an important role in model-driven software engineering where changes in the artifacts are reflected not only from upstream to downstream, but also into theother direction, in the compositions of transformations that refine the artifacts from high level specifications
down to concrete ones closer to implementation.
However, how the changes are propagated to which part, and what kind of updates are successfully
propagated, is diﬃcult to predict if not impossible, especially when the transformation becomes more
complex.
In this paper, we propose, in the compositional framework of bidirectional graph transformation, a welldefined tracing mechanism between source, transformation and target. In our GUI, when the user selects
some part of these artifacts, the corresponding parts in the other artifacts are highlighted. It helps theuser predict to which part of the source the modification is reflected, or which part of the code the user
should modify in case the part comes from the transformation. Moreover, edges of the target artifacts are
rendered in a classified manner so that any edits in the constant class are always rejected while in therest of correlated classes, simultaneous edits of multiple edges in a class amount to inconsistent edits sousers can know without executing backward transformation which parts can be safely edited. Our graphtransformation framework has been made comprehensible and predictable by our proposals.

1 Introduction
Models being used for Model-Driven Software
Engineering can become large, so large in factthat they become diﬃcult to comprehend for thedevelopers. To allow for better comprehension,
one can use a view of the model to highlightcertain interesting aspects of it. A view of a model
does not have to serve simplifcation alone: it
can provide a diﬀerent perspective on the model
information, like the classical transformation fromclasses to relational databases. With views arises
the problem of view updating. When the view of
グラフ双方向変換のトレースに基く分かり易さと予測可能性の向上にむけて
日高 宗一郎, 国立情報学研究所, National Institute ofInformatics.
マ ー ティン ビ レ ス, ア ウ グ ス プ ル ク 大 学, Augsburg
University.
クアン ミン トラン, ダイムラー IT イノベーションセ
ン タ ー/ベ ル リ ン 工 科 大 学, Daimler Center for IT
Innovations, Technical University of Berlin.

a model is modified, the source model should havethose changes reflected, if possible. This viewupdate problem can be solved with bidirectionaltransformations [5]. The view-update problem iswidely studied in the database community [1] [6]and more recently the programming language
community [7] [2].
In software engineering, bidirectional transformation is expected to play an important role,
especially in the generative approach taken inmodel-driven software development in whichmodels are manipulated by transformations togenerate models and other artifacts, where changes
in the downstream of the chain of transformations
are expected to be reflected back to upstream,so that, for example, defect found and fixed
downstream can be propagated to the upstream to
avoid reproducing the defect.
Such bidirectional transformations consist of twoparts (see Fig. 1): forward transformation (F ) andbackward transformation (B) [14]. A source modelis transformed to a view model via a forward trans-formation. The forward transformation may discard some of the information found in the source
and create some new information on its own. It
also has the possibility to rearrange the information found in the source model, sometimes duplicating parts of the source model. For this paper,
we assume source and view models to be represented in the form of edge-labeled graphs, GS and
GV , as we consider model transformation as ourprimary application and models are represented bygraphs [10] [11]. The supporting bidirectional graphtransformation [8] is based on bidirectional interpretation of existing unidirectional graph transformation language based on structural recursion on
unstructured data [3]. The bulk semantics of thestructural recursion that allows per-edge independent computation is utilized in the bidirectionalization.
In order to make bidirectional transformation
useful, we need round-trip properties [5]. In our
setting, given forward transformation F [[e]]ρ tocompute forward transformation e under variablebinding ρ (ρ corresponds to the source, and at
the start of the transformation it includes theglobal variable that binds the input graph) andbackward transformation ρ0 = B[[e]](ρ, G0 ) that
produces updated source ρ0 given the updated
view graph G0 and the original source ρ, wedemand that bidirectional transformation satisfy
the GetPut and WPutGet (weaker notion of
PutGet [7] or Consistency [1] because of therather arbitrary variable reference allowed in our
language) properties [8], which are:FJeKρ = GV
(GetPut)
BJeK(ρ, GV ) = ρ
BJeK(ρ, G0V ) = ρ0 F JeKρ0 = G00V
(WPutGet)
BJeK(ρ, G00V ) = ρ0
where GetPut says that if the view is not updated
after forward transformation, then the result of thefollowing backward transformation agrees with theoriginal source, and W(Weak)PutGet says that, theresult G00V of the forward transformation using theresult ρ0 of a backward transformation with updated view G0V may diﬀer from G00v , but the backward transformation using G00V with the original
source ρ produces ρ0 again. In other words, theeﬀect of G00V relative to ρ is the same as the eﬀect

F
GS

GV

G′S

G′V

edit operation

B
Fig. 1

Scheme of Bidirectional Transformationof G0V .
One question raised is whether backward transformation should be total or partial. In our case, wewant to look explicitly at partial backward transformation which rejects some updates on the viewgraph.
Given elements of the view such as nodes oredges, it may be hard to track the origin ofthat element. It is not immediately apparent
whether a part has its origin in the source graph orwhether it was created new in the transformation
query. When looking at the query itself, it is also
ambiguous which view elements are created by aquery construct at hand.
After edits to the view graph have been made,backward transformation is executed to reflect theview changes back to the source model. We shallrestrict the changes that can be made to the viewgraph to in-place updates where only the edge label is edited, not looking at cases of insertion ordeletion of edges. Some updates might be rejectedby backward transformation. In particular, edits ofan edge label cannot be reflected back if the label
appears as a constant of the query. This is because
the query itself cannot be updated by the processof backward transformation. If one of the updates
made to the view graph is rejected, backward transformation fails as a whole. After a collection of
update operations has been piled up, it becomesquite diﬃcult to track back the reason for a failing backward transformation: the transformation
itself is unable to give meaningful error messages
due to the bulk semantics we use in our implementation. In these bulk semantics, the view graphfirst needs to be decomposed into individual parts
before transformation is applied to it. That way,the error messages presented by backward transformation when it fails are in the local context ofthe decomposed graph and cannot easily be understood in a global context. With our framework of
tracing and classification of view edges, we can tellfor example which part of the query contribute to
the view, diﬀerent edits conflicts (classification), or
what part of the query caused the problem (suchas constant update violation).
There are some existing work that share ourgoals. For tracing, Van Amstel et al. [20] proposed
the visualization of traces, but in the unidirectionalmodel transformation settings. For the classification, Matsuda and Wang’s work [16] proposed
the extention of semantic bidirectionalization tocope with limitation of existing semantic bidirectionalization and used mechanism that turned out
to be very similar to our classification framework.
We discuss the correspondence in the related work
section (Section 7) in more detail.
The rest of the paper is organized as follows.
Section 2 is the preliminary content for the restof the paper, summarizing the semantics of ourunderlying graph data model, core graph language
UnCAL and the user-level syntax UnQL. Readersalready familiar with them can safely skip the firsttwo subsections of this section. Section 3 motivates
our work by examples, which are also used in
the following sections. Section 4 proposes tracing
mechanism that supports the highlighting of thecorrespondence between source, transformationand target. Section 5 proposes an algorithm toclassify the edges in the target to support showing
the editability (whether particular editing of theedge(s) fails or not). Section 6 describes how the
proposed mechanisms in the preceding sections
are integrated in our bidirectional graph transformation system GRoundTram (Graph Roundtrip
Transformation for Models) [10] [11]. Section 7
discusses related work, and Section 8 concludes
with future work.

2 Preliminaries
Our graph model builds upon graph constructors (see Fig. 2) that are a subset of the UnCAL(Unstructured CALculus) query language [3]. This
language allows us to describe all graphs with respect to bisimulation. A forward transformation
query is written in the UnCAL language or alternatively in UnQL (Unstructured Query Language) [3]which is syntactic sugar on top of UnCAL and istransformed to UnCAL before executing. The mostimportant element of the UnCAL language is the
structural recursion construct rec, which executes

e ::= {} | {l : e} | e ∪ e | &x := e | &y | ()| e ⊕ e | e @ e | cycle(e){ constructor }| $g{ graph variable }| if l = l then e else e{ conditional }| let $g = e in e | llet $l = l in e
{ variable binding }| rec(λ($l , $g).e)(e){ structural recursion application }l ::= a | $l
{ label (a ∈ Label) and label variable }Fig. 3

Core UnCAL Language

a query fragment in bulk independently on a setof edges. The raw view graph will have trace information stored in the node IDs that allow backward transformation to reverse the bulk semantics
algorithm and properly identify the iteration thata view edge was created by.
In the rest of this section, we explain the graphdata model we use, the UnCAL and UnQL languages in more detail, and then the additional extension of UnCAL forward transformation used in
the following sections.
2. 1 UnCAL
The graphs we deal with are multi-rooted, edgelabeled graphs where all information is stored inedge labels, and the label of nodes have no particular meanings other than as identifiers. There is noorder between outgoing edges of nodes. The notionof graph equivalence is based on bisimulation, so
equivalence between the graphs are eﬃciently determined [3], and we can always normalize [11] up
to isomorphism.
Figure 4 shows examples of our graphs. We
represent a graph by a quadruple (V, E, I, O),
where V is the set of nodes, E is the set ofedges where an edge is represented by a tripleof source node, label and destination node,
ranges over the set Edge ε , where labels range
over Label ∪ {ε}(Label ε ), and I is the set that
identifies the root nodes. Apart from the roots
as “entry points” of graphs, we also have “exitpoints” as represented by the set O. For example,
the graph on the left in Figure 4 is representedby (V, E, I, O) where V = {1, 2, 3, 4, 5, 6}, E ={(1, a, 2), (1, b, 3), (1, b, 4), (2, a, 5), (3, a, 5), (5, d, 6),(6, c, 3)}, I = {(&, 1)}, and O = {}.
The roots of the graph are uniquely identified
by the input markers denoted like &x that range
over the set Marker . We also call these roots in-

{} &

&y &
&y

&x1...&xm

()

∅

&x1

&xm

g1
&

l

@

ε ...

l

&

g1

g1

&x′1...&x′m′&z1... &zk&x′1...&x′m′&z′1... &z′k′

{_:_}

g1
&y1...&ym&y1...&ym

g2

g2&y1 ... &yn&y1 ... &yn&x1... &xm&x1...&xm &x1... &xm

g1

ε ε

&x1...&xm
cycle εg1&x1...&xm &y1... &yn&x1...&xm

ε ε

∪

g2

&y1...&ym′ &y′...
1 &y′n′

g1

ε

⊕

g2

Fig. 2

g1

g&y1...&ym′ &y′...
1 &y′n′&x1...&xm &y1... &yn&x1...&xm &y1... &yn&y1... &ym

g1&x′1...&x′m′&y′...
1 &y′n′

g2

&x

g2

&x′1...&x′m′&y′...
1 &y′n′g1

ε&y1... &yn&x.&y... 1 ... &x.&ym:=&z1 ... &zn

g&z1 ... &zn

Graph Constructors of UnCAL

put nodes and denote the input node identified bymarker &x by I(&x ). A special marker & is called thedefault marker, and we used the marker in the example. The nodes that correspond to “exit points”
are the nodes that are associated with markers, but
indicated by O instead of I, like {(4, &y)} if the node
4 has output marker &y. The graph in the example
has no output marker. We call the nodes that are
identified by O the output nodes. Output nodes
are used as connecting points to other graphs, as
we will explain shortly. We denote each component of the quadruple using “.” syntax, like g.V forgraph g. We represent the type of the graphs by
DB X
Y where X is the set of input markers and Y isthe set of output markers. The graph in the above
example has type DB &∅ . We omit the superscript if
the set is {&} and subscript if the set is empty. So
we also denote the type of the example graph simply by DB . We denote the (static) type of UnCAL
expression e similarly by e :: DB X
Y.
In UnCAL, we have nine graph constructors(Fig. 3) whose semantics is illustrated in Fig. 2.
We used hooked arrows (,→) in the figure stacked
with the graph constructor operator symbols todenote the computation by the constructors whereleft hand side is the operand(s) and the right handside is the result of the construction. There arethree nullary constructors. () constructs a graphwithout any nodes nor edges. Consequently no
input and output marker is present either, i.e.,
F[[()]] ∈ DB ∅ . {} constructs a graph with a nodewith default input marker (&) and no edges, so
F[[{}]] ∈ DB . &y constructs a graph similar to {}with additional output marker &y associated with
the node, i.e., F[[{}]] ∈ DB {&y }{ : } takes a label l and a graph g ∈ DB Y andprepend an edge labeled l to the root of the graph g,and the the source of the prepended edge becomesthe new root of the resultant graph with default
input marker, thus {l : g} ∈ DB Y . The graph unionX
g1 ∪ g2 for graphs g1 ∈ DB X
Y1 and g2 ∈ DB Y2 withidentical set of input markers X = {&x1 , . . . , &xm },new m root nodes associated with each element of
X are constructed, and for each of these nodes,
two ε-edges are extended from the new root to theoriginal roots of operand graphs for each of suchoriginal input marker, thus g1 ∪ g2 ∈ DB X
Y1 ∪Y2 .
The input node renaming operator :=takes a marker &x and a graph g ∈ DB Y
Zfor Y = {&y1 , . . . , &ym }, and returns a graphwhose input markers are prepended by &x , thus
x .Y(&x := g) ∈ DB &where the dot “.” operaZtion is a marker concatenation operation that,together with default input marker & forms a
monoid, i.e., &.&x = &x .& = &x for any marker&x ∈ Marker , and &x .Y = {&x .&y1 , . . . , &x .&ym } forY = {&y1 , . . . , &ym }. In particular, when Y = {&},
the := operator just assign a new name to the{&x }root of the operand, i.e., (&x := g) ∈ DB Yforg ∈ DB Y .
The disjoint union g1 ⊕ g2 of two graphs g1 ∈Y
DB X
X 0 and g2 ∈ DB Y 0 with disjoint set of input
markers, i.e., X ∩ Y = ∅, the resultant graph inherits all the markers, edges and nodes from the∪Yoperands, thus g1 ⊕ g2 ∈ DB X
Y 0 ∪Y 0 .
The remaining two constructors connect output
and input nodes with matching markers by ε-edges.
Graph append g1 @ g2 of two graphs g1 ∈ DB X
X 0 ∪Z0∪Z 0
and g2 ∈ DB X
withmatching
subsetof
markY
ers Y connects the output nodes and input nodes
with matching markers X 0 and discards the rest of
the markers, thus g1 @ g2 ∈ DB X
Y . As a useful idiom, this operator is often used to project (select)
one input marker and rename it as the default input marker, while discarding the rest of the input
makers (and thus they are left unreachable), liketaking X = {&}, Z = ∅ and X 0 = {&x 0 }, i.e., &x 0 @g2
to return a graph g2 with the input marker &x 0 renamed to the default one and leave the subgraphs
reachable from the rest of the input nodes unreachable. The cycle operator does operations similar
to @ but in an intra-graph instead of inter-graphmanner. For a graph g ∈ DB X
X ∪Y with X ∩ Y = ∅,cycle(g) connects output and input nodes of g withmatching markers X and construct m nodes with
input markers in X , connected with the original
input nodes of g with matching input markers by
ε-edges. The output markers in Y are left as is.
It is worth noting that any graph in the data
model can be expressed by using these UnCAL
constructors (up to bisimilarity). For example thegraph on the left in Figure 4 can be represented by&n1 @cycle((&n1 := {a : &n2 ,b: &n3 ,b: &n4 } ,&n2 := {a : &n5 } ,&n3 := {a : &n5 } ,&n4 := {},&n5 := {d: &n6 } ,&n6 := {c : &n3 })) .

The semantics of conditionals is standard, except
the condition is restricted to label equivalencecomparison. There are two kinds of variables:
label variables denoted like $l or $l1 , binds labels,
while graph variables denoted by $g . . . $g1 . . .
binds graphs. They are introduced by structural
recursion operator rec. For example, the following

transformation in UnCAL replaces every label a
by d and remove (shortcut) edges labeled c. So
if the graph variable $db is bound to the graphon the left of Figure 4, the result will be (after εremoval which is conducted in a standard manner
like those for automata, and flattening the node
identifiers) the one on the right of the figure.
rec(λ($l , $g). if $l = a then {d : &1 }2else if $l = c then {ε : &3 }4else{$l : &5 }6 )($db)7
We call the first operand of rec the the body expression and the second operand the argument expression. In the above transformation, the body
expression is an if conditional, and argument expression is the variable reference $db. We use $db
as a distinguished global variable to represent the
input of the graph transformation.
For the sake of bidirectionalization (and also usedin our tracing in this paper), we allocate for eachnode of the abstract syntax tree of UnCAL thecode position p ∈ Pos. The superscripts of each
expression in the above transformation represent
such positions.
Figure 5 shows the semantics of rec by the above
example input graph and transformation. Since
the evaluation of rec can be executed in parallelfor each edge and the subgraph reachable from thetarget node of the edge (that are correspondingly
bound to variables $l and $g in the body expression), the semantics is called bulk semantics. In thebulk semantics, the node identifier carry some information which has the following structure TraceID:
TraceID ::= SrcID| Code Pos Marker| RecN Pos TraceID Marker| RecE Pos TraceID Edge,
where SrcID is the base case and represents thenode identifier in the input graph, Code p &x
denotes the nodes constructed by {}, { : },&y, ∪ and cycle where &x is the marker that
inherited by the corresponding input nodes of theoperand(s) of the constructor, and for {} { : }and &y the marker is the default one and we omit.
RecN p v &z denotes the node created by rec at
position p for the node v of the graph resulted
from evaluating the argument expression. For
example, the node RN 7 1 in the figure originated

&
1

2

3

4

a c
d

a
5

Fig. 4

RN 7 1

1

b b

a

&

&

6

d

b b

2

3

4

d d
d

RE 7 (C 2) (1,a,2)

RE 7 (C 6) (1,b,3)

RE 7 (C 6) (1,b,4)

b

d

b

RE 7 (C 1) (1,a,2)

RE 7 (C 5) (1,b,3)

RE 7 (C 5) (1,b,4)

RN 7 2

RN 7 3

RN 7 4

RE 7 (C 2) (2,a,5)

RE 7 (C 2) (3,a,5)5Cyclic graph examples

from node 1 and 7 is the code position of rec inthe transformation (RecN is abbreviated to RN in
the figure for simplicity, and we do similarly todenote Code by C and RecE by RE). We have six
such nodes for each node in the input graph. Then
we evaluate the body expression for each bindingof $l and $g. For the edge (1, a, 2), the result will be({(C 2), (C 1)}, {(C 2, d, C 1)}, {(&, C 2)}, {(C 2, &)}),
with the nodes C 2 and C 1 constructed by theconstructors { : } and &, respectively. For the
shortcut edges, ε-edge is generated similarly. Theneach node v of the graph generated by the body
expression for edge ζ is wrapped with the trace
information RE like RE p v ζ for rec at position
p. These results are surrounded by round squares
drawn with dashed lines in Fig. 5. Then they areconnected together according to the original shapeof the graph as depicted in Figure 5. For example,
the input node RE 7 (C 2) (1, a, 2) is connectedwith RN 7 1. After removing the ε-edges andflattening the node identifiers, we obtain the resultgraph in Figure 4 on the right.
The variable binders let and llet are our extensions and have standard meanings, and used for
optimization by rewriting [9].
The notion of bisimulation is extended to copewith bisimulation, and it is known that every UnCAL expression preserves bisimulation [3], though
we do not use this property in this paper. Basedon this bulk semantics, it is easy that the termination is always guaranteed, even in the presence ofcycles.
In the backward evaluation of rec for in-place
updates, the process of ε-elimination is reversed torestore the shape like in Figure 5, and then thegraph is decomposed with the help of the structures of node with trace IDs, and then the decomposed graph is used for the backward trans-d

RE 7 (C 2) (6,c,3)d

RE 7 (C 1) (2,a,5)

ε

RE 7 (C 1) (3,a,5)

RN 7 5

RE 7 (C 1) (6,c,3)

RE 7 (C 6) (5,d,6)

d
RE 7 (C 5) (5,d,6)Fig. 5

RN 7 6

Bulk semantics by example

formation of each body expression. The backward
transformation produces as the updated input thevariable binding environment (in this body expression we obtain the bindings for $l , $g and $db andmerge these bindings to produce the final bindingof $db. For example, if we update the edge (1, b, 3)
in the view to (1, x, 3), then it is propagated via
the backward transformation of the body expression {$l : &}, which produces the bindings of $l updated with x and is reflected to the source graphwith edge (1, b, 3) replaced by (1, x, 3).
2. 2 UnQL as a Textual Surface Syntax ofBidirectional Graph Transformation
We use the surface language UnQL [3](Fig. 6),
for bidirectional graph transformation. It is bidirectionally interpreted by translation into UnCAL
and bidirectional interpretation of the translated
UnCAL expression [8]. It is based on the notionof structural recursion. It can be considered as adivide and conquer computation scheme using thefollowing equation:f ({})= {}f ({l : g}) = e(l, g) @ f (g)f (g1 ∪ g2 ) = f (g1 ) ∪ f (g2 ).
The correspondence with the rec in UnCAL withf above isf (g) = rec(e)(g).
The structural recursion function f , if given singleton node graph, returns the singleton node graph,or if given a graph with one edge labeled l on thetop, followed by subgraph g, then the result will be(template)(binding)(condition)(label)(label pattern)(graph pattern)(regular path pattern)

T

::=
|
|
|
B
::=
BC ::=|
L::=
Lp ::=
Gp ::=
Rp ::={L : T, . . . , L : T } | T ∪ T | $g
if BC then T else T
select T where B, . . . , B
letrec sfun fname(L : $G) = . . . in fname(T )Gp in $G | BC
not BC | BC and BC | BC or BC
L=L$l | a$l | Rp$G | {Lp : Gp, . . . , Lp : Gp}a || Rp.Rp | (Rp|Rp) | Rp? | Rp∗ | Rp+

Fig. 6

Syntax of UnQL

the concatenation of the result of some computation e using l and g, combined by append operation(@) with the recursive result with g. If given horizontal union of two graphs g1 and g2 , then the result will be the horizontal union of recursive resultswith g1 and g2 . Since the first and third equation
hold for any f , we only use the second equation forthe programming in UnQL.
Thanks to the translation to UnCAL with bulk
semantics, we can program graph transformations
as if we are programming on (infinite) trees as aresult of (conceptually) unfolding the input graphs.
We can combine the structural recursions to extract various graph patterns like regular expressionsof edge labels using mutual structural recursion.
A join operation of multiple graph patterns isachieved by nesting of structural recursions. The
following UnQL query returns the input graphbound to the variable $db if the graph has bothedge labeled a and that labeled b at the root,and otherwise returns a graph with single nodedenoting empty result.
letrec sfun f ({a : $g })letrec sfun f ({b: $g }) = {res : $db}
in f ($db )in f ($db )Higher syntactic sugar select allows the combination of these query patterns by simple SQL-like
syntax, combining querying and prepending edges
to the results arbitrarily. For example, the following transformation
select {result : $g}where {a .b: $g} in $db

extracts subgraphs under consecutive edges labeled
a and b, and prepends an edge labeled result foreach of these subgraphs. Next transformation
select {result : $name}where {Class . ( srcof . Assoc . dst )+:$class} in $db ,{isAbstract :{$b : $Any}} in $class ,$b = truecomputes the subgraphs with respect to transitive
closure of edges by traversing the label patternsrcof.Assoc.dst more than once, and choose
those having an edge labeled isAbstract. This is
extracted from an example of Class to Relationaltransformation appeared in our previous work [11].
All language constructs in UnQL are translated
into UnCAL [3] [13] [12]. In particular, select tostructural recursion, and structural recursion to
rec in UnCAL. We highlight the essential partof the translation in the following. Please refer
to [3] [13] [12] for details.
The template part (directly following the selectclause) appears in the innermost body of the nested
rec in the translated UnCAL. The edge constructor expression is directly passed through, while thegraph variable pattern in the where clause and thecorresponding reference are translated into a combination of graph variable bindings in nested recs
as well as a reference to them in the body of rec.
For example,
select {res : $db}
where {a : $g} in $db ,{b: $g} in $db

is translated intorec(λ($l ,$g ) . i f $l = a thenrec(λ($l ,$g ) . i f $l = bthen {res : $db} else {})($db )else {})($db ) .

Regular expression of labels are translatedfirst into non-deterministic finite automata, andthen they are translated into mutually recursive
letrec sfuns, and finally into rec in UnCAL
using multiple input/output markers and disjoint
unions using tupling [15] technique, where tuple
construction is encoded by disjoint union, and projection is encoded by graph append operation andoutput marker expression using idiom described in
the previous subsection.

is rather unpredictable. We use the transformation
query shown below and the source graph of Fig. 7
to produce the view graph in Fig. 8, then modify
the view graph so that the result is as in Fig. 9.
select ( i f $l = a then {a : $g} else {d: $g })where {$l : $g} in $db
Listing 1

2. 3 Forward Semantics with Traceable
View and Intermediate Results
In the extended forward evaluation of UnCAL
we leave not only the trace information in the node
identifiers but also every intermediate result of theoperands. We represent this information by extending the abstract syntax with the results subscriptedon the bottom left. We annotate an UnCAL expression e with overline e to denote this extended
abstract syntax, but omit the overline if it is clear
from the context. Moreover, if the subscripts are
not used, we omit them as well. For example, forthe edge constructor expression {el : e}, we have

{&}
10
a

3 Motivating Example
In this section, we want to give an example of acase where the result of backward transformation

b

c

d

0

4

6

8

x

y

z

w

1

5

7

9

Fig. 7

F[[{el : e}]]ρ = G {el : e}where G = {L : G0 }L el = F [[el ]]ρ
G0 e = F [[e]]ρ.
The special cases are the conditional expression
and structural recursion rec. For the former, we
keep only the branch that is actually evaluated. It
is denoted by if b eb e where b : Bool represents
the run-time branching behavior and it is true if
the then branch has been taken and false otherwise, and e is the extended evaluation result of the
body expression for the corresponding branch. For
the latter, we keep the map from the edge fromwhich the bindings of the label and the graph variable are created, to the result of the extended forward evaluation for the binding. It is denoted byrec(λ($l , $g).M )(ea ) where M denotes this mapping.
We denote the set of such extended expressions
e by Eval .

Transformation query in UnQL

Example source graph

10aFig. 8

d

d

d

0

4

6

8

x

y

z

w

1

5

7

9

Graph genrerated by transformation of
the graph in Fig. 7

10
d

d

d

d

0

4

6

8

x

y

z

w

1

5

7

9

Fig. 9Modified target graph

{&}
3

Query

{&}
0

File

File

2

File

4

3

save

open

1

2

SourceFig. 12

open save1

Fig. 100Class

Fig. 11

Qualified

Names

Members

As the result of backward transformation, there
are serveral possibilities that satisfy bidirectional
properties. One is to accept the change, reflecting
it by changing a to d. Another forward transformation would produce the same graph as the modified
view graph. Another possibility is to change thelabel a to anything other than a. Another forward
transformation would still produce the same graphas the modified view graph. What happens in the
backward transformation depends on the underlying backward transformation logic. (The system we
implemented rejects the update.)
As a second point of consideration, forward transformation allows us to replicate information fromthe source graph to produce a view graph whichcontains some information duplicate. We want tomotivate how this can lead to the possibility of inconsistent edits which make backward transformation fail.
{$l :{$l 0 : $g 0 }}selectwhere {$l : $g} in $db ,{$l 0 : $g 0 } in $g
Listing 2

Class to Qualified Name

The input graph from Fig. 10 represents a classwith several methods. Applying the query above
we can duplicate the top-level edge to produce theview graph in Fig. 11 showing the qualified namesof the methods. Now the class name “File” canbe inconsistently modified: If one label “File” ismodified to “Stream” and the other to “Buﬀer”,
backward transformation will try to propagate bothchanges to the same source edge with label “File”
and fail because of the inconsistency of the edit
operations.

V iew

Tracing mechanisms

We introduce the notion of equivalence classes
and say that two view edges are considered to bein the same equivalence class if backward transformation would cause edits to those view edges topropagate to the same source edge, allowing for the
possibility of inconsistent edits which make backward transformation fail. There is one such equivalence class for each source edge that the changes
can be propagated back to. Additionally, there isa class of view edges which cannot be modified at
all because their label originates from a constantdefined in the transformation query, as is seen withthe edges with label d in Fig. 8.
We (1) mark the edge that reject any updates,(2) highlight the source edge to which the modification would be propagated. (3) highlight the codefragment that generates the edge in the view graphon which user is trying to update. (4) classify theedges in the target edges with the same origin in
the source are identified. Inconsistent updates onthem would be rejected by the backward transformation.

4 Tracing Mechanisms
In this section, we will elaborate on mechanismsthat allow us to tell the correspondence between
elements of the source graph, code positions of
the transformation query and elements of the viewgraph in all feasable combinations (Fig. 12).
The UnQL query in Listing 1 is converted into
the following UnCAL expression.
rec (λ($l ,$g ) .
i f $l = a then {a : $g}else {d: $g })($db )Listing 3

UnCAL expression of UnQL queryin Listing 1

In the graphical user interface of our system,
when a view edge is selected, the corresponding
source edge or corresponding query code point ishighlighted, and vice versa.

4. 1 Tracing between Source and View
A view edge may either be freshly created by aedge constructor in the query or originate from anedge in the source graph. If a view edge originatesfrom a source graph, it is very helpful for the user tobe able to visually see the correspondending sourceedge of a view edge, particularty in complex transformation scenario.
The trace information associated with node identifiers that is used during backward transformation is suﬃcient for directly identifying the sourceof a view edge without executing backward transformation in its whole. If a view edge ζ is fromthe source graph, it must have a trace ID of theform (n1 , a, n2 ) where n1 and n2 are source IDs.
If the edge is created inside the body of a structural recursion at code position p, it will have theform (RecE p u ζ 0 , a, RecE p v ζ 0 ). Here, the edge
is the result of the evaluation of the structural recursion at ζ 0 and (u, a, v) is edge within the graphcreated by the body of the structural recursion.
Hence, we expand the tracing information by looking into (u, a, v) to detect the source edge. Nested
rec-constructs generate nested RecE traceable viewwhich can be expanded in the same way.
Formally, the following function
tr corr : Edge → Edge
returns the source edge of a given view edge if itexists and fails otherwise.
tr corr((u, a, v)) = (u, a, v) if u, v in ∈ SrcID
tr corr(((RecE p u ζ 0 ), a, (RecE p v ζ 0 ))) =tr corr((u, a, v))
tr corr(ζ) = FAIL otherwise
After a corresponding source edge has been foundfor each view edge that has one, this relationshipcan be easily reversed to allow tracing from thesource to the view:{ζt | ζt ∈ EV , ζs = tr corr ζt },where EV is the set of view edges. The notionof “corresponding source edge” defined here is the
copy relationship. The source edge calculated bythis algorithm is a true copy of the view edge fed
to the algorithm.
For example, if we apply tr corr to the edge
(0, x, 1) in the view graph (Fig. 8), we obtain
the edge (0, x, 1) in the source graph (Fig. 7)
which is the source edge from which the view edge
originates from. This obtained edge can then behighlighted accordingly.

We can relax the notion of corresponding sourceedge by weakening the second case:
tr corr(((RecE p u ζ 0 ), a, (RecE p v ζ 0 ))) =(tr corr((u, a, v)) if tr corr((u, a, v)) 6= FAIL
tr corr(ζ 0 ) otherwise
In this definition, the view edge is either a copyof the source edge or it is the result of applying a
structural recursion to the source edge. Note that,
if tracing (u, a, v) fails, we trace back to the sourceedge of ζ 0 , the edge being applied by the structural
recursion.
4. 2 Tracing between View and Query
Since view edges can be copied by graph variables$g or created by edge constructors {l : e}, we canhighlight the correspondence between view edges
and graph variables as well as edge constructors in
the query.
4. 2. 1 Tracing between View and Edge
Constructor
If the edge is constructed by an edge constructorin the query, we can reutilize the function for tracing to the source edge in Section 4. 1 and, insteadof looking for a trace ID with a source ID, look foran edge ID of the form (Code p m, , ). The expansion of rec-constructs (RecE) works the sameway.
In particular, given a view edge ζ, the following
function returns the code position p of the edge
constructor that creates ζtr cp : Edge → Pos
tr cp((Code p , , )) = p
tr cp(((RecE p u ζ 0 ), a, (RecE p v ζ 0 ))) =tr cp((u, a, v))
tr cp(ζ) = FAIL otherwise
The edge constructor at p can then be highlighted when selecting the view edge. For example,
if the user clicks on the view edge (10, a, 0) in
Fig. 8, the edge constructor {a : $g} in Listing
3 is highlighted because this constructor creates
the view edge (tr cp returns p when applied to theview edge). No edge in the source graph (Fig. 7)
is highlighted because the view edge is not copy of
any edge in the source graph.
4. 2. 2 Tracing between View and Graph
Variable
If the view edge is a direct copy from the source,
a graph variable can be highlighted in the queryinstead. This graph variable was used to output
the view edge to the view graph.
For a view edge ζ = (u, a, v) with a 6= , we define
the sequence of applied edges of ζ as the sequenceof edges that were successively applied by nested
structural recursions to create ζ as follows:
tr eval : Edge → [Edge]tr eval(((RecE p u ζ 0 ), a, (RecE p v ζ 0 ))) =tr eval((u, a, v)) ++ [ζ 0 ]tr eval(ζ) = [] otherwise
In the first case, if ζ has the form ((RecE p u ζ 0 ), a,(RecE p v ζ 0 )), it is produced by the structural recursion at code position p when applying the bodyto the edge ζ 0 . Then, we recursively collect appliededges in (u, a, v).
We also define the source edge of ζ as the resultof applying the following function to ζ.
tr srcEdg : Edge → Edgetr srcEdg(((RecE p u ζ 0 ), a, (RecE p v ζ 0 ))) =tr srcEdg((u, a, v))
tr srcEdg(ζS ) = ζSIn order to trace to graph variable references
within expressions with multiple input marker
types, identification of the input marker is required
to identify the correct occurrence of the reference
that produced the edges in the view.
The input marker &m of a view edge can be
identified by traversing the edge backwards to a
RecN p &m or Code p &m. If no such node exists,
the input marker is the input marker of the root
node reachable from the edge.
The algorithm for tracing graph variables is thenas follows:First, following the sequence of applied edges, we
can trace to the structural recursion body that created ζ. Formally, let e be the result of the forward
semantics to the input query and ζ a view edge.
Moreover, let Z = tr eval(ζ) and ζS = tr srcEdg(ζ)
be the sequence of applied edges of ζ and the sourceedge of ζ, respectively.
The body of the structural recursion in which ζis created is defined astr brec : Eval → [Edge] → Evaltr brec(rec(λ($l, $g).M )(ea ))[ζ 0 : ζs0 ] = tr brec(M ζ 0 ) ζs0
tr brec(e)[] = e

Recal that M maps the applied edge to the corresponding (extended) body expresssion so M ζ 0 denotes such expression.
Then, we identify the corresponding variable ref-erence by traversing the corresponding marker component in the UnCAL expression e, resulting fromapplying tr brec to Z, using the function tr gvar
where ζS = tr srcEdg(ζ) (Fig. 13) and π2 ◦ tr gvar
returns the set of positions of the graph variables,
while π1 ◦ tr gvar is used to trace beyond @ andcycle expressions that operate on markers. We assume that the type of the expression is annotatedfor every subexpression using type inference proposed in our previous work [9].
The positions in π2 ◦ tr gvar can be highlighted totell which graph variables produce ζ. For example,
applying tr gvar to the view (0, x, 1) in Fig. 8 will
result in ({}, {p}) where p is the code point of thegraph variable $g of the then branch, but not of
the else branch, in Listing 3. We can then highlight
this variable.
4. 2. 3 Tracing UnQL
The tracing mechanisms introduced above are defined for UnCAL. However, the user usually formulates a transformation in the more high-level language UnQL described in Section 2. 2. For practical use, it is desired that tracing between view andquery also works for UnQL.
The tracing mechanism also works straightforwardly for UnQL based on the following observation: When an UnQL query is desugared to UnCAL, all edge constructors and graph variables in
the UnQL query that create edges in the view graphare preserved in the UnCAL query. For instance,edge constructors {a : $g} and {d : $g} as well as
graph variables $g of the UnQL query in Listing 1
are transfered to the UnCAL query in Listing 3.
As a result, we can easily highlight edge constructors and graph variables in an input UnQL
query. Furthermore, thank to our marker-based
tracing of graph variables (Fig. 13), we can handle
UnQL queries containing regular expressions which
can lead to the generation of multiple markers.
In our system, the user can activate an optimizer
that can optimize an UnCAL query to increase
the eﬃciency. However, because of the excessive
reorganization of UnCAL expressions during the
optimization phase, we currently support neither
tracing UnCAL nor tracing UnQL if optimizationis activated.

tr gvar : {Marker } → {Marker } × {Pos}p= ({}, {p}) if ζS ∈ G.E
G $v({}, {}) otherwise
tr gvar {&}{}= ({}, {})tr gvar {&}{ : e}= tr gvar {&} etr gvar {&m}e1 ∪ e2= let (Z1 , P1 ) = tr gvar {&m} e1 in(Z2 , P2 ) = tr gvar {&m} e2 in(Z1 ∪ Z2 , P1 ∪ P2 )tr gvar {&}&z= ({&z }, {})tr gvar {&m}(e1 @ e2 ) = let (Z1 , P1 ) = tr gvar {&m} e1 inlet (Z2 , P2 ) = tr gvar Z1 e2 in(Z2 , P1 ∪ P2 )tr gvar {&m}cycle(e)= let (Z, P ) = tr gvar {&m} e in
(Z \ X , P ) where e::DB X
Y
tr gvar {&}()= ({}, {})tr gvar {&x .&m} (&x := e) = tr gvar {&m} e(e1 ⊕ e2 ) = tr gvar {&m} e1
tr gvar {&m}if e1 ::DB X
Y ∧ &m ∈ X
tr gvar {&m} e2 otherwise
tr gvar {&x .&z } rec(eb )(ea ) = tr gvar {&z } ebZ
where ea ::DB X
Y ∧ eb ::DB Z
tr gvar Z
if b e= tr gvar Z e
tr gvar (X ∪ Y) e
= let (Z1 , P1 ) = tr gvar X e in
(Z2 , P2 ) = tr gvar Y e in(Z1 ∪ Z2 , P1 ∪ P2 )tr gvar {&m}e= ({}, {}) if e::DB X/X
Y ∧ &m ∈tr gvar {&}Fig. 13

Marker-oriented Tracing of Graph Variables

5 Determining Editability
For the following section, we look at the underlying logic of the query in the UnCAL language,
which it is translated to if it was originally an UnQL
query. We want to use the following query which istranslated from Listing 2:rec(λ($l , $g).
rec(λ($l 0 , $g 0 ).{$l : {$l 0 : $g 0 }}($g))($db)
Whether an edit is accepted or not is dependent
on the query construct used to create the individual
view edge during forward transformation.
In the UnCAL query language, edges can be created by one of the following:
1. Graph variable usage $g. Edges in a graphvariable might be direct copies from the sourceor created elsewhere by edge constructors in
the query.

2. Edge constructors {l : e}. The label can be(a) an explicit label constant a ∈ Label(b) a label variable which might be boundto a source edge via structural recursion
or equal to another label constant or label
variable in an llet construct.
Only in the case of direct copies from the source
via graph variable usage, the trace information
found in these copy edges can directly identify thecorresponding source edge as seen above in section
4. 1. For 2a, a view edge created by this edge
contructor should be considered a constant edge.
Updating its label is not allowed, since backward
transformation prevents updates to constantlabels. For everything else, there needs to be a
dynamic (re-)evaluation of the query to determine
the exact value of the label or graph variable.
The rec construct is executed one time for eachpossible binding of ($l , $g) found in the argument
ea . The dynamic evaluation is performed on theintermediate evaluation results defined above insection 2. 3.
For dynamic evaluation, we define a variable environment η : env which is composed of a label
variable environment ηL : varL → Edge ⊥ and agraph variable environment ηG : varG → (Edge →Edge ⊥ ). We define V as the dynamic evaluation of
the query which returns a mapping of all edges ofthe view graph to their respective source edge or a
⊥ symbol in case it is a constant edge. This respective source edge could be considered the equivalenceclass id of the view edge at hand.
V : Eval → env → (Edge → Edge ⊥ )Let f∅ : Edge → Edge ⊥ be the partial function
with an empty domain
and define f {x → y} as(
y if a = x
f {x → y}(a) =f (a) if a 6= x and f defined for a
Further define a partial function f1 ∪ f2 for twopartial functions( f1 and f2 as
f1 (x) if f1 (x) defined(f1 ∪f2 )(x) =f2 (x) if f2 (x) defined but not f1 (x)The function aux(m, ζ) uses reachable to calculate
the edges reachable from the destination of the edgeζ (it may include ζ itself because of cycles). The
definition of aux is:
aux(m, ζ) = {(ζ 0 7→ eq) ∈ m | ζ 0 ∈ reachable(ζ)}
where eq denotes the equivalence class for edge ζ 0 .
The wrap function wraps each node ID in the keyof the Edge → Edge ⊥ mapping with the RecE trace
information, to make the result of V consistent withthe view graph of the forward transformation.
Then V is recursively defined according to thestructure of the top-level query construct in Fig. 14.
When V is then applied to the query as a wholeand an initial environment which maps $db to a
mapping of each source edge to itself, the output
is a mapping of all view edges to their equivalenceclass. For those equivalence classes with more than
one member, there is then a possibility for inconsistent edits. For an equivalence class eq1 , backward transformation will fail if there are two edges
that are part of the equivalence class, both havebeen updated by the edit operation to the view,
but the resulting edge labels are diﬀerent. Notably,
backward transformation does not fail in case someedges have been updated and others have not, justas long as the updates all have the same new label.
The GUI editor for the view graph can be modified

to take these equivalence classes into account.
When applying V to our example, we get threeequivalence classes, one for every source edge. Forward evaluation features one iteration of the outmost rec construct which contains two iteration of
the inner rec construct. That way, the $l for bothview edges with label File are in the equivalenceclass of source edge File. If the two File edges
in the view are modified inconsistently, backward
transformation fails.

6 Our GRoundTram System
We have integrated the tracing mechanisms in
the form of highlighting and editability support
described in this paper into our GRoundTram
system. We plan to publish the implementationfrom our project website at http://www.prg.nii.
ac.jp/projects/gtcontrib/cmpbx/.
In the following, we briefly summarize these features of GRoundTram from the user’s point of view.
Fig. 15 shows the screenshot of our GRoundTram
system.
When the user clicks on a view edge, there are
two possibilities.
1. If the view edge has been copied from thesource graph, the system highlights the corresponding edge in the source graph from which
the view edge originates. The system also highlights the graph variables in the query thathave produced the view edge.
2. If the view edge has been created by anedge constructor in the query, that edge
constructor is highlighted. In this case, noedge in the source graph is highlighted. Allgraph variables that have contributed tocreating the view edges are also highlighted.
The highlighting also works in the other direction. When the user clicks on an edge in the source
graph, all view edges that are copies of that sourceedge are highlighted. Additionally, when the usermarks an edge constructor or a graph variable in
the query, all view edges created by the constructor or variable are highlighted.
Multiple selection of edges in the view and source
graph as well as multiple marking of edge constructors and graph variables in the query are also supported.
In the screenshot (Fig. 15), the user selected mutiple view edges at the pane on the right. They areη = f∅
V G {}
η = f∅V G ()
η = (V G1 e η){(G.I(&), L, G1 .I(&)) 7→ ηL ($l )}V G {L $l : G1 e}
V G {a : G1 e} (a ∈ Label ) η = (V G1 e η){(G.I(&), a, G1 .I(&)) 7→ ⊥}η = (V G1 e1 η) ∪ (V G2 e2 η)
V G (G1 e1 ∪ G2 e2 )
η = (V G1 e1 η) ∪ (V G2 e2 η)
V G (G1 e1 ⊕ G2 e2 )
η = V G1 e η
V G (&m := G1 e)
η = f∅V G &mη = (V G1 e1 η) ∪ (V G2 e2 η)
V G (G1 e1 @ G2 e2 )cycle(e)η = V G1 e η
V G
G1
(if
b
e)
η = V G1 e ηV GG1η = ηG ($g)
V G $gSwrap(V Gb eb ηζ0 )V G rec(λ($l , $g).M )(G1 ea ) η = let m = V G1 ea η in(ζ7→G eb )∈M
bwith ηζ0 = (ηL {$l 7→ m(ζ)}, ηG {$g 7→ aux(m, ζ)})0with η 0 = (ηL , ηG {$g 7→ V G1 e1 η})V G (let $g = G1 e1 in G2 e2 ) η = V G2 e2 η
η = V G1 e (ηL {$l 7→ ⊥}, ηG )V G (llet $l = a in G1 e)
0
η = V G1 e (ηL {$l 7→ ηL ($l 0 )}, ηG )V G (llet $l = $l in G1 e)
Fig. 14

Fig. 15

The algorithm for calculating the equivalence class mappings.

Screenshot of GRoundTram system showing traces between source graph, UnQL
transformation and view graphrendered in two diﬀerent colors:• yellow (info,type, ”Kato”) if if they are directly copied from the source, as the corresponding edges are highlighted in the left top
pane and the graph varaible references that
produced these edges are highlighted in yellow
in the UnQL transformation in the left bottom
pane,• red (addr,customer name) if they are constructed in the transformation, and thecorresponding labels (all constants in thiscase) are highlighted in blue color in the UnQL
transformation in the left lower pane.
In addition to highlighting the correspondence
between source graph, view graph and query,
GRoundTram also renders view edges in a classified manner. In particular, constant edges areshown in a special way that can be recognizedeasily by the user. Editing these edges is disabledby the system. Moreover, when the user clicks

on a view edge, all view edges that cannot be
simultaneously edited in an inconsistent way arehighlighted.
These features have proven to be very useful tobetter comprehend and predict the behavior ofbidirectional transformations, especially of thosethat are non-trivial. Particularly useful is whena transformation query contains duplicate labelnames or graph variable names, the highlighting
clearly shows which name actually creates a
selected view edge. The editability allows the user
to avoid changes to the view graph that would
eventually lead to a failure without waiting until
the backward transformation is executed.

7 Related WorkThe notion of traces has been extensively studied in a more general context of computations, likeprovenance traces [4] for the nested relational calculus, as the importance of traceability is widely
recognized as the key to know the origin, ownership, or history of an object. One of the latest related works that shares our motivation in the model
driven engineering community is the work by Van
Amstel et al. who proposed a visualization framework for chains of ATL model transformations [20].
Although their work supports unidirectional transformations, they also consider it important not only
to trace from source to target but the transformation query should also be involved. Systematic augmentation of the trace-generating capability withmodel transformations is achieved by higher-ordermodel transformations [19]. We have already introduced the trace generation mechanism in our previous work [8] but the main objective was to thebidirectionalization itself.
Generation of tracing information is also studied
in the reversible computation [22] community whereminimization of the trace information is also seriously considered as in [23]. Currently the size of the
trace information in our GRoundTram for the proposed framework to work is prohibitive in terms of
performance even for middle scale examples. In thenormal mode of GRoundTram we internally compress the trace information and it is part of our
future work to make the proposed tracing work under the compression as well.
Tracing between a surface language (syntactic
sugar) and its core language, like between UnQL

and UnCAL in our work, is not easy in general dueto the big gap between the two languages. Pombrio
and Krishnamurthi [17] tackle this gap by proposing an approach to automatically reproducing anevaluation sequence in the core language in the surface language. This work may provide a partial solution for traceability between UnQL and UnCAL
in our graph transformation settings.
Triple Graph Grammars (TGG) [18] and frameworks based on it are studied extensively by thegraph transformation research community andapplied to model-driven engineering. It is basedon graph rewriting rules that consist of triples
of source graph pattern, target graph pattern,
and the correspondence graph in-between. The
triple of source graphs, correspondence graphs
and target graphs grow in parallel in the graphgrammars described by the rewriting rules. The
trace information is explicit in the link between
correspondence graphs and source/target graphs.
As another well-studied bidirectional transformation framework, semantic bidirectionalization [21]makes use of the polymorphism of the forward
transformation to derive the backward transformation. It generates the table of correspondence
between elements in the source and those in thetarget to guide the reflection of updates, and does
not even require inspection of the syntax of theforward transformation at all (thus called semantic
bidirectionalization).
Matsuda and Wang [16]addressed the problem of the inability of branchingby comparison with constant values that breaks
the polymorphism, by run-time recording of the
branching behaviors. They also cope with data
constructed during transformation. Ours framework is close to both of the above ( [21] and [16])frameworks in the sense that they also utilize aparticular run of a forward transformation. It isalso worth noting that UnCAL transformation is
also monomorphic in general because of the label
comparison in the if conditionals. Our bottom
equivalence class corresponds to Matsuda andWang’s location identifier #, and our ordinary
equivalence classes. correspond to their ordinary
numerical location identifiers.
Since the semantic bidirectionalization does nothave to walk through the backward transformation
syntax, what we are trying to do in our present
paper before execution is very close to what theyare doing in their backward transformation. For
example, they are able to detect inconsistent updates based on the location identifiers, and reject
the attempt to update data created during transformation by finding the attempt to update the dataon a location identified by #.
In the (purely) semantic bidirectionalization
framework, the source-target trace is generated byjust running the transformation giving “artificial”
input in which every occurrence of an element is
replaced by a unique identifier. This is possible
because polymorphic transformation does notinspect the concrete element values (labels in
our case). But as Matsuda and Wang addressed,
the inspection of labels breaks the framework.
So Matsuda and Wang instead make use of the
combination of location identifiers and the actual
input value.
We instead use input edges as
the combination of input and location identifierbecause input edges include not only the label
value but also node identifiers on both ends. With
respect to run-time recording, Matsuda and Wang
have only to record the branching behaviors that
inspected element values. This is implemented
by seamlessly wrapping the comparison operationthat takes care of that recording. Instead wecurrently record all the intermediate results.

8 Conclusion
Currently bidirectional transformations sometimes receive a reputation that the result of
backward transformation is diﬃcult to understandor predict. This applies to a framework like ourGRoundTram system in which the backward
semantics of the given forward transformation iscompletely provided, rather than (partially) left tothe users, so the logic of backward transformation
is rather fixed and hidden by the semantics.
Once the transformation gets more complex, theprediction is even more diﬃcult.
In this paper, we proposed, within a compositional bidirectional graph transformation
framework based on structural recursion, a comprehensive externalization of tracing between
source graphs, transformation and view graphs
in our system GRoundTram. The intermediate
results kept during forward transformations aswell as trace information used for backward

transformation, were utilized for the tracing.
We also classify every edge in the target graphso that users can know the attempts to edit every edge that is classified as constant edge lead to
failure of backward transformation, and for otheredges, the inconsistent updates for the edges classified identically will also cause the failure of backward transformation. Since the language we deal
with allows arbitrary variable references that causes
copies, identification of copies in the view had notbeen that trivial, but our proposal is simple as it
just maintains the mapping from source edge to theview edge per variables and updates the mappingsfor each variable binding construct.
We are now improving our implementation andplan to distribute it in our project website.
As our future work, we have found some potential in the classification framework in that it can
detect the branching behavior change that current
GRoundTram fails to detect. Unlike point-free approaches, we can always refer to non-local variablesin the transformation, which means that updates ofthe binding during backward transformation may
cause side eﬀect indirectly to the value referred byother variables. We would like to incorporate thisfix in the next release of GRoundTram. Anotherpotential is the capability of tracing the occurrence
position of graph variables as well as constants byextending the entry of the table maintained by theclassifier to store the code positions and graph variables. We would like to investigate this direction towards unifying tracing with classification. We alsoplan to overcome the limitation of tracing with optimization activated mentioned in Section 4. 2. 3 bydefining rules of how to pass position informationof edge constructors and graph variables in an UnCAL expression to the corresponding elements inthe optimized one. Our partial implementation inthis direction shows promising results.
We would like to investigate the possibility of accommodating update operations other than edge
renaming, like insertion of subgraphs, using thesame backward transformation semantics, because
we currently handle insertions using separate general inversion strategy which is costly. We currently
have limited support, however we do not have bidirectional property for complex expressions. One
obvious case that we can support is subgraph extraction like select {a : $g} where {a : $g} in $db

in which we could insert an arbitrary subgraph below the top level edge labeled a, because the subgraph is not “observed” in the transformation so
update will never interfere with the branching behavior. Even though that part is “observed” by
the bulk semantics, that part is left unreachable,
so update does not aﬀect the computation of thereachable part. If we extend the classifier function
to indicate which edge involved in the branching
behavior, inspired by [16], we could safely determine the part that accept the insertion or deletionof that part reusing the in-place update semantics,
thus achieving “cheap backward transformation”.
We have not discussed the performance aspect in
the paper. The trace based on algebraic data constructors increases the size of the trace dramaticallyas the composition of structural recursion increases.
It prohibits the execution of even middle-scale examples to work. We plan to compress the trace
information to restore scalability.
Acknowledgement The authors would like tothank Zhenjiang Hu and Hiroyuki Kato for theirvaluable comments, and Kazutaka Matsuda for discussing the branching behavior change detection.
The project was supported by the International Internship Program of the National Institute of Informatics.
References[ 1 ] Bancilhon, F. and Spyratos, N.: Update Semantics of Relational Views, ACM Trans. Database
Syst., Vol. 6, No. 4(1981), pp. 557–575.
[ 2 ] Bohannon, A., Foster, J. N., Pierce, B. C.,
Pilkiewicz, A., and Schmitt, A.: Boomerang: Resourceful lenses for string data, POPL ’08, 2008,
pp. 407–419.
[ 3 ] Buneman, P., Fernandez, M., and Suciu, D.:
UnQL: a query language and algebra for semistructured data based on structural recursion, The
VLDB Journal, Vol. 9, No. 1(2000), pp. 76–110.
[ 4 ] Cheney, J., Acar, U. A., and Ahmed, A.: Provenance Traces, CoRR, Vol. abs/0812.0564(2008).
[ 5 ] Czarnecki, K., Foster, J. N., Hu, Z., Lämmel,
R., Schürr, A., and Terwilliger, J. F.: Bidirectional
Transformations: A Cross-Discipline Perspective,
ICMT, Paige, R. F.(ed.), Lecture Notes in Computer Science, Vol. 5563, Springer, 2009, pp. 260–
283.
[ 6 ] Dayal, U. and Bernstein, P. A.: On the Correct Translation of Update Operations on Relational Views, ACM Trans. Database Syst., Vol. 7,
No. 3(1982), pp. 381–416.

[ 7 ] Foster, J. N., Greenwald, M. B., Moore, J. T.,
Pierce, B. C., and Schmitt, A.: Combinators forbidirectional tree transformations: A linguistic approach to the view-update problem, ACM Trans.
Program. Lang. Syst., Vol. 29, No. 3(2007).
[ 8 ] Hidaka, S., Hu, Z., Inaba, K., Kato, H., Matsuda, K., and Nakano, K.: Bidirectionalizing graphtransformations, ICFP’10, 2010, pp. 205–216.
[ 9 ] Hidaka, S., Hu, Z., Inaba, K., Kato, H., Matsuda, K., Nakano, K., and Sasano, I.: Markerdirected optimization of UnCAL graph transformations, Logic-Based Program Synthesis and Transformation, 21st International Symposium, LOPSTR 2011, Odense, Denmark, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 7225,
July 2012, pp. 123–138.
[10] Hidaka, S., Hu, Z., Inaba, K., Kato, H.,
and Nakano, K.: GRoundTram: An Integrated
Framework for Developing Well-Behaved Bidirectional Model Transformations (short paper), 26th
IEEE/ACM International Conference On Automated Software Engineering, IEEE, 2011, pp. 480–483.
[11] Hidaka, S., Hu, Z., Inaba, K., Kato, H., andNakano, K.: GRoundTram: An Integrated Framework for Developing Well-Behaved Bidirectional
Model Transformations, Progress in Informatics,
No. 10(2013), pp. 131–148.
[12] Hidaka, S., Hu, Z., Kato, H., and Nakano, K.:
Towards Compostional Approach to Model Transformations for Software Development, Technical Report GRACE-TR08-01, GRACE Center, National
Institute of Informatics, August 2008.
[13] Hidaka, S., Hu, Z., Kato, H., and Nakano,
K.: Towards a compositional approach to modeltransformation for software development, SAC’09:
Proceedings of the 2009 ACM symposium on Applied Computing, New York, NY, USA, ACM, 2009,
pp. 468–475.
[14] Hidaka, S. and Terwilliger, J. F.: Preface
to the Third International Workshop on Bidirectional Transformations, Proceedings of the Workshops of the EDBT/ICDT 2014 Joint Conference (EDBT/ICDT 2014) (EDBT/ICDT), Candan, K. S., Amer-Yahia, S., Schweikardt, N.,
Christophides, V., and Leroy, V.(eds.), CEUR
Workshop Proceedings, No. 1133, Aachen, 2014,
pp. 61–62.
[15] Hu, Z., Iwasaki, H., Takeichi, M., and Takano,
A.: Tupling Calculation Eliminates Multiple Data
Traversals, ACM SIGPLAN International Conference on Functional Programming (ICFP’97), Amsterdam, The Netherlands, ACM Press, June 1997,
pp. 164–175.
[16] Matsuda, K. and Wang, M.: Bidirectionalization for Free with Runtime Recording: Or, a Lightweight Approach to the View-update Problem, Proceedings of the 15th Symposium on Principles andPractice of Declarative Programming, PPDP ’13,
New York, NY, USA, ACM, 2013, pp. 297–308.
[17] Pombrio, J. and Krishnamurthi, S.: Resugaring: Lifting Evaluation Sequences Through Syntactic Sugar, Proceedings of the 35th ACM SIGPLAN
Conference on Programming Language Design and
Implementation, PLDI ’14, New York, NY, USA,ACM, 2014, pp. 361–371.
[18] Schürr, A.: Specification of Graph Translators with Triple Graph Grammars, Graph-Theoretic
Concepts in Computer Science, 20th International
Workshop, WG ’94, Herrsching, Germany, Mayr,
E. W., Schmidt, G., and Tinhofer, G.(eds.), Lecture Notes in Computer Science, Vol. 903, Springer,
June 1995, pp. 151–163.
[19] Tisi, M., Jouault, F., Fraternali, P., Ceri, S.,
and Bézivin, J.: On the Use of Higher-Order
Model Transformations, Proceedings of the 5th European Conference on Model Driven Architecture- Foundations and Applications, ECMDA-FA ’09,
Springer-Verlag, 2009, pp. 18–33.

[20] van Amstel, M. F., van den Brand, M. G. J., andSerebrenik, A.: Traceability Visualization in Model
Transformations with Tracevis, Proceedings of the
5th International Conference on Theory and Practice of Model Transformations, ICMT’12, Berlin,
Heidelberg, Springer-Verlag, 2012, pp. 152–159.
[21] Voigtländer, J.: Bidirectionalization for Free!
(Pearl), Proceedings of the 36th Annual ACM
SIGPLAN-SIGACT Symposium on Principles ofProgramming Languages, POPL ’09, New York,NY, USA, ACM, 2009, pp. 165–176.
[22] Yokoyama, T.: Reversible Computation and Reversible Programming Languages, Electron. Notes
Theor. Comput. Sci., Vol. 253, No. 6(2010), pp. 71–
81.
[23] Yokoyama, T., Axelsen, H. B., and Gluck, R.:
Minimizing Garbage Size by Generating Reversible
Simulations, Proceedings of the 2012 Third International Conference on Networking and Computing,
ICNC ’12, Washington, DC, USA, IEEE Computer
Society, 2012, pp. 379–387.