Bidirectionalizing Tree Transformations
Zhenjiang Hu1,2 , Kento Emoto1 , Shin-Cheng Mu1 , and Masato Takeichi1
1

Graduate School of Information Science and Technology,
The University of Tokyo{hu,emoto,scm,takeichi}@mist.i.u-tokyo.ac.jp
2

PRESTO 21, Japan Science and Technology Agency

Abstract. A transformation from the source data to a target view issaid to be bidirectional if, when the target is altered, the transformation
somehow induces a way to reflect the changes back to the source. Several domain-specific bidirectional transformation languages have been
proposed. In this paper, we intend to show that most existing unidirectional tree transformations can be made bidirectional. Therefore it may
be not really necessary to design new domain-specific languages for bidirectional transformation. As a case study, we consider the combinatorlibrary HaXML, which has been widely used in the Haskell community
for generating, editing, and transforming XML documents. We show thatany transformation in HaXML can be fully compiled into a bidirectionaltransformation.

1

Introduction

XML [1] has been attracting a tremendous surge of interest as a universal,
queryable representation for structured documents, which has in part been stimulated by the growth of the Web and e-commerce. It has emerged as the de facto
standard for representation of structured data and information interchange, andmany organizations use XML as an interchange format for data produced by applications like graph-plotters, spreadsheets, and relational databases. An XML
document is essentially a tree, which contains two basic types of content: tagged
elements and plain text. A tagged element is written as a start tag and an end
tag, possibly enclosing a sequence of contents (elements or text fragments). Figure 1 shows an XML document representing an address book, where each entry
contains a name, an email address, and a telephone number.
Transformation of XML documents from one format (structure) to anotherplays a significant role in data interchange. They are often described using atransformation language like XSLT. Figure 2 depicts an example of the treetransformation mapping the XML document in Figure 1 to a HTML document(Figure 3) which has an index of names and displays the contact details in atable. This transformation is unidirectional, in the sense that it describes thetransformation from the XML document to the HTML view, but not the other2

Zhenjiang Hu et al.
<addrbook><person><name> Zhenjiang Hu </name><email> hu@mist.i.u-tokyo.ac.jp </email><tel> +81-3-5841-7411 </tel></person><person><name> Kento Emoto </name><email> emoto@ipl.t.u-tokyo.ac.jp </email><tel> +81-3-5841-7412 </tel></person><person><name> Shin-Cheng Mu </name><email> scm@mist.i.u-tokyo.ac.jp </email><tel> +81-3-5841-7411 </tel></person><person><name> Masato Takeichi </name><email> takeichi@acm.org </email><tel> +81-3-5841-7430 </tel></person></addrbook>
Fig. 1. An XML Document of the Address Book

way round. The transformation itself does not give much clue how the XML
document shall be updated if the HTML view is altered.
There are many situations where one wants to transform some data structure into a different form and wish that changes made to the new form bereflected back to the source data. One may want modification on the view tobe reflected back to the original database, which is known as view updating in
the database commuinity [2–6]. One may want to synchronize the bookmark
files of several different web browsers (on different machines) [7], allowing bookmarks and bookmark folders to be added, deleted, edited, and reorganized in any
browser and later combining the changes performed in different browsers. One
may want to have a programmable editor [8] supporting interactive refinementin the development of structured documents, where one performs a sequence ofediting operations on the document view, and the editor automatically derives
an efficient and reliable source document and a transformation that produces
the document view.
These situations call for bidirectional transformations on tree-structured data.
In one direction, these transformations map a concrete tree into an abstract one;in the other, they map a modified abstract tree, together with the original concrete tree, to a correspondingly modified concrete tree. Several domain-specificlanguages [7, 9, 10, 8] have been proposed to define bidirectional transformations.
One would like to know, however, whether an existing transform written in tree-

Bidirectionalizing Tree Transformations<xsl:template match="/"><html><body><h1>IPL Address Book</h1><ul><xsl:for-each select="addrbook/person"><li><xsl:value-of select="name"/></li></xsl:for-each></ul><table><tr><th>Name</th><th>Email</th><th>Tel</th></tr><xsl:for-each select="addrbook/person"><tr><td><xsl:value-of select="name"/></td><td><xsl:value-of select="email"/></td><td><xsl:value-of select="tel"/></td></tr></xsl:for-each></table></body></html></xsl:template>Fig. 2. A Transformation in XSLT

3

4

Zhenjiang Hu et al.

<html><body><h1>IPL Address Book</h1><ul><li> Zhenjiang Hu </li><li> Kento Emoto </li><li> Shin-Cheng Mu </li><li> Masato Takeichi </li></ul><table><tr><th>Name</th><th>Email</th><th>Tel</th></tr></index><tr><td> Zhenjiang Hu </td><td> hu@mist.i.u-tokyo.ac.jp </td><td> +81-3-5841-7411 </td>
</tr>
<tr>
<td> Kento Emoto </td><td> emoto@ipl.t.u-tokyo.ac.jp </td><td> +81-3-5841-7412 </td>
</tr>
<tr>
<td> Shin-Cheng Mu </td><td> scm@mist.i.u-tokyo.ac.jp </td><td> +81-3-5841-7411 </td>
</tr>
<tr>
<td> Masato Takeichi </td><td> takeichi@acm.org </td><td> +81-3-5841-7430 </td></tr></table><body><html>
Fig. 3. A View of the Address Book in HTML

Bidirectionalizing Tree Transformations

5

transformation languages, like XSLT, can be made bidirectional. As far as weare aware, there is little work on this.
In this paper, we argue that most tree transformations can be made bidirectional. As a case study, we consider the combinator library HaXML [11], which
has been widely used in the Haskell community for generating, editing, andtransforming XML documents. The library HaXML can be seen as a domainspecific language embedded in the general-purpose functional language Haskell.
XML documents are represented using native Haskell data type, and HaXML
provids a set of powerful higher order functions to process them. A transform
coded in HaXML is usually more compact than its equivalent in DOM, SAX, or
XSLT.
In this paper we will present a technique we call bidirectionalization, which
compiles any HaXML transformation into a bidirectional language X [8], thereby
making it bidirectional. Our main result can be summarized as follows:
Any tree transformation in HaXML can be made bidirectional, according to which any part of the data before transformation can be updated
via editing operations on the transformed data if the transformation is
specified in HaXML.
The result is surprising because HaXML is a unidirectional tree transformation
language designed without bidirectionality in mind. With bidirectionalization,
we obtain bidirectional transformation for free.
The rest of the paper is organized as follows. We start by briefly reviewing
the core of HaXML [11], a general-purpose unidirectional transformation language, in Section 2. After explaining the basic concepts of bidirectionality anda bidirectional transformation language X [8] in Section 3, we show that any
transformation specified by HaXML can be translated to a bidirectional transformation in X in Section 4. Conclusions are made in Section 5.

2

Tree Documents and Tree Transformations

Before explaining how to bidirectionize tree transformations in Section 4, we
begin with a brief overview of the core concept of HaXML [11], a combinatorlibrary in Haskell [12], showing how tree documents are generated, edited, andtransformed with HaXML. We will use a Haskell-like notation for the rest of thispaper.
2.1

Documents as Trees

There are two basic types of XML contents: elements and text fragments. An
element consists of a tag and a sequence of contents. In HaXML, XML documents
are represented by native Haskell data structure:
data Content = CElem Element

6

Zhenjiang Hu et al.
addrbook = N "Addrbook"[ N "Person"[ N "Name" [N "Zhenjiang Hu" []],N "Email" [N "hu@mist.i.u-tokyo.ac.jp" []]N "Tel" [N "+81-3-5841-7411" []]],N "Person"[ N "Name" [N "Kento Emoto" []],N "Email" [N "emoto@ipl.t.u-tokyo.ac.jp" []],N "Tel" [N "+81-3-5841-7412" []]],N "Person"[ N "Name" [N "Shin-Cheng Mu" []],N "Email" [N "scm@mist.i.u-tokyo.ac.jp" []],N "Tel" [N "+81-3-5841-7430" []]],N "Person"[ N "Name" [N "Masato Takeichi" []],N "Email" [N "takeichi@acm.org" []],N "Tel" [N "+81-3-5841-7430" []]]]
Fig. 4. An Example of Simplified Representation of Tree Documents| CText String
data Element = Elem Name [Attribute] [Content]
For the sake of conciseness and simplicity, we shall omit attributes in documents
and represent tag labels by strings. Therefore, an XML document is essentiallyan internally labelled rose tree with text fragments as its leaves. To further
simplify the matter, we will represent documents by the following tree:
data Tree = N String [Tree]
This representation does not distinguish labels from texts, since both of them
are represented by strings. However, we may think of labels attached to inner
nodes as tag names, and labels to leaves as text. For an element with no content
such as <br/>, we may represent it by N "br" [N "" []].
Figure 4 gives an example of this representation of the the document sourcein Figure 1.
2.2

Tree Transformations

Combinators in HaXML are also called filters, with the type:
type Filter = Tree -> [Tree]
A filter takes a tree and returns a sequence of tree. The result might be empty,
a singleton list, or a collection of trees.

Bidirectionalizing Tree Transformations

7

Predicates:
none :: Filter
keep :: Filter
elm :: Filter
txt :: Filter
tag :: String → Filter{ zero }{ identity }{ tagged element? }{ plain text? }{ named root }Selection:
children :: Filter{ children of the root }Construction:
literal:: String → Filter
mkElem :: String → [Filter] → Filter
replaceTag :: String → Filter{ build plain text }{ build a tree with an inner node }{ replace root’s tag }Fig. 5. Basic Filters

Basic Filters
A set of basic filters in HaXML is given in Figure 5. The simplest possible filter,
none, fails on any input (returning an empty list); keep takes any tree and returns
just that tree. The filter elm is a predicate, returning just this item if it is not aleaf, otherwise it fails. Conversely, txt returns this item only if the item is a leaf.
The filter children returns the immediate children of the tree, if any. The filtertag t returns the input only if it is a tree whose root has the tag name t. The
function literal s discards the input and returns a leaf labelled s. The function
mkElem t fs builds a tree with the root label t; the argument fs is a list of filters,
each of which is applied to the current item. The results are concatenated andbecome the children of the created element.
Filter Combinators
Figure 6 lists all combinators one can use to compose filters. The most importantand useful among them is o, which plugs two filters together: the left filter isapplied to the results of the right filter. So, for instance, the expression
txt ‘o‘ children ‘o‘ tag ”title”
returns all the plain-text children immediately enclosed by the input, provided
that the input is labelled title.
The combinator f ||| g concatenates the results of filters f and g, while
cat f s is a generalisation of ||| to arbitrary numbers of filters. The combinatorf ‘with‘ g acts as a guard on the results of f , keeping only those which areproductive (yielding non-empty results) under g. Its dual, f ‘without‘ g, excludes
those results of f that are productive under g. The filter f ‘et‘ g applies f to

8

Zhenjiang Hu et al.

o
(|||)
cat
with
without
et
?> :>
chip

:: Filter → Filter → Filter:: Filter → Filter → Filter:: [Filter] → Filter:: Filter → Filter → Filter:: Filter → Filter → Filter:: (String → Filter) → Filter → Filter:: Filter → Filter → Filter → Filter:: Filter → Filter{ Irish composition }{ append results }{ concatenate ressults }{ guard }{ negative guard }{ disjoint union }{ condition }{ in-place children application }Fig. 6. Basic Filter Combinators

the input if it the input is a leaf tree, and applies g to the input otherwise. The
expression p ?> f :> g represents conditional branches; if the (predicate) filter
p is productive given the input, the filter f is applied to the input, otherwise g isapplied. The filter chip f applies f to the immediate children of the input. The
results are concatenated as new children of the root.

ExamplesA number of useful tree transformations can be defined as HaXML filters. For
instance, we may define the following two path selection combinators /> and</.
f /> g = g ‘o‘ children ‘o‘ f
f </ g = f ‘with‘ (g ‘o‘ children)
Both of them apply f to the input and prune away those subtrees of the resultthat does not make g productive (i.e., g does not fail): /> is an ‘interior’ selector,
returning the inner structure; </ is an ‘exterior’ selector, returning the outer
structure.
Another class of useful filter combinators allows one to process trees recurively. The combinator deep f
deep f = f ?> f :> (deep f ‘o‘ children)
potentially pushes the action of filter f deep inside the document sub-tree. It
first tries the given filter on the current node: if the filter is productive then it
stops, otherwise it moves to the children recursively. Another powerful recursion
combinator is foldXml: the expression foldXml f applies the filter f to every levelof the tree, from the leaves upwards to the root.
foldXml f = f ‘o‘ (chip (foldXml f ))

Bidirectionalizing Tree Transformations

9html[ body[ h1 [ literal ”IPLAddressBook” ],ul [replaceTag ”li” ‘o‘ (keep /> tag ”person” /> tag ”name”) ]table[ tr [ th [literal ”Name”, th [literal ”Email”], th [literal ”Tel”]],
foldXML tabling ‘o‘ (keep /> tag ”person”) ] ] ]wheretabling = tag ”person” ?> replaceTag ”tr” :>(tag ”name” ?> repalceTag ”td” :>(tag ”email” ?> repalceTag ”td” :>(tag ”tel” ?> repalceTag ”td” :>keep)))
Fig. 7. A Transformation in HaXML

Recall the transformation described by XSLT in Figure 2. By defining HTML
constructors byhtml = mkElem ”html”
body = mkElem ”body”
h1 = mkElem ”h1”ul
= mkElem ”ul”
li
= mkElem ”li”
table = mkElem ”table”
tr= mkElem ”tr”
th = mkElem ”th”
td = mkElem ”td”
we can define it in HaXML as in Figure 7.

3

A Bidirectional Transformation Language

In this section, we present the bidirectional transformation language X, whichis essentially the same as that in [8]. It will serve as the basis of our bidirectionalization transformation.
3.1

Bidirectionality

Before explaining our language, we clarify what we mean by being bidirectional.
Following the convention in [7], we call the type of source documents C (concreteview) and that of target documents A (abstract view). They are both embedded
in Tree but we nevertheless distinguish them for clarity. A transformation x
defined in X is associated with two functions. The function φx :: C → A maps

10

Zhenjiang Hu et al.
X ::= B
| X ; X
| X ⊗X| If P X X| Map X
| Fold X X
B ::= BFun (f, g)| Dup{ primitives }{ sequencing }{ product }{ conditional branches }{ apply to all children }{ fold }{ Bidirectional function pairs }{ duplication }Fig. 8. The Language X for Specifying Bidirectional Transformations

the concrete view to an abstract view, which is displayed and edited by the user.
The function Cx :: C × A → C takes the original concrete view and the edited
abstract view, and returns an updated concrete view. In [7] they are called get
and put respectively.
We call a transformation x bidirectional if the following two properties hold:
GET-PUT-GET : φx (c Cx a) = a where a = φx c
PUT-GET-PUT : c0 Cx (φx c0 ) = c0 where c0 = c Cx a
The PUT-GET-PUT property says that if c0 is a recently updated concrete
view, mapping it to its abstract view and immediately performing the backward
update does not change its value. Note that this property only needs to hold for
those c0 in the range of Cx . For an arbitrary c we impose the GET-PUT-GET
requirement instead. Let a be the abstract view of c. Updating c with a andtaking the abstract view, we get a again. Here, by ”updating”, we mean one of
the following four editing operations: insertion of a hole to the view, deletion ofa hole from the view, replacement of a subtree by a hole, and change of a node
name.

3.2

The Language X

The syntax of the language X for specifying bidirectional transformation is given
in Figure 8. Primitive transformations are denoted by non-terminal B. They canbe composed to form more complicated transformations by one of the combinators defined in X. The language looks very similar to the bidirectional languages
proposed in [9, 7]. The most important difference lies in the new language construct Dup, which enables description of data dependency inside the view. An
important property of the language X is the following theorem.
Theorem 1 (Bidirectionality of X).
Any transformation described in X is bidirectional.

¤

Bidirectionalizing Tree Transformations

11

Primitive Bidirectional Transformations
Bidirectional Primitive Transformations A bidirectional primitive BFun (f, g)
consists of two functions f and g satisfying the GET-PUT-GET and PUT-GETPUT properties. The bidirectional semantics of BFun (f, g) is given by
φBFun (f,g) c=f cc CBFun (f,g) a = g c a
For a special case where g does not use its second argument and is the inverseof f , we write it as GFun (f, g):
φGFun (f,g) c=f cc CGFun (f,g) a = g a
Let us see some useful primitive transformations defined in this way. The
simplest transformation is the identity transformation:
idX = GFun (id, id)
which relates two identical data, and is defined by a pair of two identity functions.
In this example, the pair of functions are inverse of each other.
Similarly, we may define other primitive transformations that are useful forprocessing tree locally.
– constX t ignores the concrete view and gives a constant abstract view t.
constX t = BFun (λx. t, λc a. c)– hoistX n: If the root has label n and a single child t, then the result is t.
hoistX n = GFun (f, g)
where
f (N m [t]) = t, if m = n
g t = N n [t]– exchangeX exchanges the root with the node of the leftmost child tree thathas no child.
exchangeX = GFun (f, f )wheref (N n (N m [ ] : ts)) = N m (N n [ ] : ts)– insertHoleX inserts Ω, a special tree denoting a hole, as the leftmost child of
the root.
insertHoleX = GFun (f, g)
where
f (N n ts) = N n (Ω : ts)g (N n (Ω : ts)) = N n ts

12

Zhenjiang Hu et al.

– deleteHoleX deletes the hole appearing as the leftmost child of the root.
deleteHoleX = GFun (f, g)
where
f (N n (Ω : ts)) = N n ts
g (N n ts) = N n (Ω : ts)– replaceHoleX t replaces the hole with tree t.
replaceHoleX t = GFun (f, g)
where
f Ω=t
g t0 = Ω, if t = t0
Duplication In the forward direction, the function φDup generates two copies
of its input.
φDup c = N “Dup” [c, c]
In the backward direction, CDup checks which of the two copies was touched by
the user by comparing them with the original view c, and keeps only the changedone.
c CDup (N “Dup” [a1 , a2 ]) = a2 if a1 = c= a1 if a2 = c= a1 otherwise
Here we assume that the user performs only one editing action before an updating
event is triggered. Therefore, if none of a1 and a2 equals c, it must be the casethat a1 = a2 , because they result from the same editing action.
Bidirectional Transformation Combinators
The set of transformation combinators is useful to construct bigger transformations.
Sequencing Given two bidirectional transformations x1 and x2 , the transformation x1 ; x2 informally means “do x1 , then do x2 ”. Its bidirectional semantics
is given by
φx1 ;x2= φx2 ◦ φx1
c Cx1 ;x2 a = c Cx1 ((φx1 c) Cx2 a)
The forward transform φx1 ;x2 is simply the sequential composition of φx1 andφx2 . To update the concrete view c with a modified abstract view a, we need toknow what the intermediate concrete view was. It is computed by φx1 c. The
expression (φx1 c) Cx2 a then computes an intermediate abstract view, which isused to update c with Cx1 .

Bidirectionalizing Tree Transformations

13

Product The product construct x1 ⊗x2 behaves similar to products in ordinary
functional languages, apart from that we are working on trees rather than pairs.
The forward transformation is defined by
φx1 ⊗x2 (N c (c1 : cs)) = N a (a1 : as)
where

a1
= φx1 c1
N a as = φx2 (N c cs).

The input tree is sliced into two parts: the left-most child, and the root plus
the other children. The transform x1 is applied to the left-most child, whilex2 is applied to the rest. The result is then combined together. The backward
updating is defined by updating the two slices separately.
(N c (c1 : cs)) Cx1 ⊗x2 (N a (a1 : as)) = N c0 (c01 : cs0 )
where

c01
= c1 Cx1 a1
N c0 cs0 = (N c cs) Cx2 (N a as).

Conditional Branches In the forward direction, the combinator If p x1 x2
applies the transform x1 to the input if the input satisfies the predicate p. Otherwise x2 is applied.
φIf p x1 x2 c = φx1 c if p c= φx2 c otherwise
In the backward direction, we check the root label to determine whether to apply
Cx1 or Cx2 to the modified view.
c CIf p x1 x2 a = c Cx1 a if p c= c Cx2 a otherwise
Map We define two (higher order) transformation combinators, Map and Foldto recursively transform trees.
The well-known function map on lists is defined by
map f [ ]=[]map f (a : x) = f a : map f x
The forward transform of Map x simply applies the transformation x to all
subtrees of the given tree, leaving the root label unchanged.
φMap x (N c cs) = N c (map φx cs)
The backward updating is defined by updating the subtrees separately,(N c cs) CMap x (N c as) = N c (zipCx cs as)14

Zhenjiang Hu et al.

where the abstract and the concrete trees should have the same label, and function zip is defined as follows.
zip⊕ [ ] [ ]=[]zip⊕ (a : x) (b : y) = a ⊕ b : zip⊕ x y
Fold The transform Fold x1 x2 is defined like a fold on rose trees. The transform
x2 is applied to leaves, x1 to internal nodes. Its forward transform is defined byφFold x1 x2 (N c [ ]) = φx2 (N c [ ])φFold x1 x2 (N c cs) = φ(Map (Fold x1 x2 ));x1 (N c cs)
In the base case, we simply apply x2 to the leaf. In the recursive case, Fold x1 x2
is applied to all subtrees of the input tree, before x1 is applied to the result, thus
the use of sequencing.
In the backward direction, we use the cached copy of the concrete view todetermine the depth of recursion to go into. Being able to reuse Map and sequencing significantly simplifies the definition.
(N c [ ]) CFold x1 x2 a = (N c [ ]) Cx2 ac CFold x1 x2 a
= c C(Map (Fold x1 x2 ));x1 a
Examples: Bidirectional Editing Operations
With the language X, we are able to define the important editing operations as
bidirectional transformations.
insertX v= insertHoleX ;(replaceHoleX v) ⊗ idX

deleteX= (constX Ω) ⊗ idX ;deleteHoleX

modifyRootX n = insertX (N n []) ;exchangeX ;deleteX
We may insert some document v as the leftmost child of the root using insertX v,
or delete the leftmost child using deleteX, or modify the root node information
with a new name n using modifyRootX n.

4

Bidirectionalization Translation

We are now ready to show how tree transformations in HaXML can be compiled
into the bidirectional transformation language X.

Bidirectionalizing Tree Transformations

4.1

15

Tree Represenation of Lists

Our idea is to translate each filter in HaXML to a bidirectional transformationin X. There is, however, a technical problem due to their type difference; a filter
is a map from Tree to [Tree], whereas a transformation in X is a map from Treeto Tree. We solve this problem by coding lists as a special tree whose root has a
special label “List”. For example, a list of trees [t1 , t2 , . . . , tn ] is represented by
N “List” [t1 , t2 , . . . , tn ].
Below are some functions on the tree representation of lists.
emptyList= N “List” []nullList (N “List” [])= True= FalsenullList (N )singletonList (N “List” [x]) = True
= FalsesingletonList (N )We are defining a set of primitive bidirectional transformations for manipulating tree representation of lists.
Transformation listizeX wraps a tree as a list that contains the tree as its
single element.
listizeX = GFun (f, g)
where
f t = N “List” [t]g (N “List” [t]) = t
Transformation appendX flattens a list that has two list elements to a newlist whose elements are a concatenation of the elements of the two element lists.
appendX = BFun (f, g)
where
f (N c [N a ta, N b tb]) = N c [N b (ta++tb)]
g (N c [N a ta, N b tb]) (N c0 [N b0 ts]) =N c0 [N a (take n ts), N b0 (drop n ts)]
where n = length ta
Transformation concatX is a generalization of appendX, applying to a list that
contains arbitrary number of list elements.
concatX = BFun (f, g)
where
f (N c ts) = N “List” (foldr (++) [] (map getContents ts))g (N c ts) (N “List” ts0 ) = N c (recons ts ts0 )getContents (N cs) = csrecons [N r cs] cs0 = [N r cs0 ]recons ((N r cs) : rs) cs0 =(N r (take n cs0 )) : (recons rs (drop n cs0 ))where n = length cs

16

Zhenjiang Hu et al.

Finally, transformation filterX keeps those list elements that satisfy conditionp.
filterX p = BFun (f, g)
where
f (N “List” ts) = N “List” (filter p ts)
g (N “List” ts) (N “List” ts0 ) = N “List” (recons ts ts0 )recons cs [] = csrecons (c : cs) (c0 : cs0 ) = if p c then c0 : (recons cs cs0 )
else c : (recons cs (c0 : cs0 ))4.2

Translation of Basic Filters

Under the tree representation of lists, filters in HaXML have the same type asthat of bidirectional transformations in X, which enables us to express filters
directly in terms of bidirectional transformation functions and combinators in
X to achieve bidirectionality.
The following is the definitions of the predicate filters in terms of X.
none = constX emptyList
keep = listizeX
elm = If (not ◦ leafNode) keep none
txt = If leafNode keep none
tag n = If ((== n) ◦ root) keep none
Function leafNode returns True if the input is not a leaf tree, and False otherwise.
Similarly, we can redefine the filters for selection and for tree construction.
children= modifyRootX “List”
literal n= constX (N n []) ; listizeX
mkElem n [x]= x ; replaceTag n
mkElem n (x : xs) = Dup ; (x ⊗ (hoistX “Dup” ; mkElem n xs)) ; appendX
replaceTag n= modifyRootX n ; listizeX
4.3

Translation of Filter Combinators

The bidirectionalization translation for the combinator filters is given below.
f ‘o‘ g= g ; Map f ; concatX
f ||| g= Dup ; (f ⊗ Map g) ; concatX
cat [f ]=fcat (f : fs) = Dup ; (f ⊗ Map (cat fs)) ; concatXf ‘with‘ g= f ; filterX (not ◦ nullList ◦ (φg ))f ‘without‘ g = f ; filterX (nullList ◦ (φg ))f ‘et‘ g= (f ‘oo‘ tagged elm) |>| (g ‘o‘ txt)
p ?> f :> g = If (not ◦ nullList ◦ (φp )) f g
chip f= Map (f ; hoistX “List”) ; listizeX

Bidirectionalizing Tree Transformations

17

Two derived filter combinators |>| and oo are used, whose definitions are
f |>| g = f ?> f :> gf ‘oo‘ g = g ; Map (curryX f ) ; concatX
in which the bidirectional transformation curryX is defined as follows.
curryX h = BFun (f, g)
where
f (N “Pair” [a, x]) = φ(h (root a)) x
g (N “Pair” [a, x]) y = N “Pair” [a, x C(h (root a)) y]
We omit detailed explanation of these definitions. It would not be difficult
to understand them if comparing them with those in [11].
4.4

An Application: Bidirectional Editing

Recall the example in the introduction, where we transform the data in Figure
1 to that in Figure 3. This data transformation can be specified in HaXML,
as seen in Section 2. According to the result in this section, we know that thistransformation is actually bidirectional. Therefore, we cannot only edit the data
in Figure 1 and ask a system to automatically update that in Figure 3, which
is usual, but also edit the data in Figure 3 and ask a system to automatically
update that in Figure 1, which benefits much from our bidirectionalization transformation.
We give three simple examples of bidirecetional editing below, and refer readers to the paper [8] for details about use of bidirectional transformations inconstruction of a programmable editor.
Example 1: If we change the first occurrence of Zhenjiang Hu to ZHENJIANG
HU in Figure 3, our bidirectional transformation will reflect this change back to
the data in Figure 1, by changing the name Zhenjiang Hu to ZHENJIANG HU.
Furthermore, a forward transformation from the updated data in Figure 1 willchange the second occurrence of Zhenjiang Hu to ZHENJIANG HU in Figure 3,
keeping data consistency.
Example 2: If we delete the table entry<tr><td>Zhenjiang Hu</td> ... </tr>
in Figure 3 (by first replacing this part by a special hole Ω − and then deletingthe hole), a backward transformation will delete the subtree<person><name>Zhenjiang Hu</name> ... </person>in Figure 1. Then a forward transformation will delete <li> Zhenjiang Hu</li>, keeping data consistency.
Example 3: If we modify the tag name body to newbody, an error message will
be reported, because this requires to change the transformation rather than thedata in Figure 1. Although not all data in Figure 3 are editable, any data in
Figure 1 can be modified by editing some part of data in Figure 3.

18

5

Zhenjiang Hu et al.

Conclusions

In this paper, we propose a new general transformation, called bidirectionalization, for making tree transformations bidirectional. As far as we are aware, thisis the first attempt. Our result is really encouraging: any tree transformation in
HaXML is bidirectional. This make HaXML be a more powerful transformation
language for data exchange than it was first designed. A rapid prototype system
has been implemented. Recently, we realized that both X and HaXML could be
redefined over a more fundamental but powerful injective language Inv [10, 13],This would enable us to bidirectionalize more complicated tree transformation,
and we are now investigating how to compile XSLT into efficient bidirectional
codes.

References
1. Bray, T., Paoli, J., Sperberg-McQueen, C.: Extensible markup language (xml) 1.0.
(1998)
2. Bancilhon, F., Spyratos, N.: Updating semantics of relational views. ACM Transactions on Database Systems 6 (1981) 557–575
3. Dayal, U., Bernstein, P.A.: On the correct translation of update operations on
relational views. ACM TODS 7 (1982) 381–416
4. Gottlob, G., Paolini, P., Zicari, R.: Properties and update semantics of consistentviews. ACM Transactions on Database Systems 13 (1988) 486–524
5. Ohori, A., Tajima, K.: A polymorphic calculus for views and object sharing. In:
ACM PODS’94. (1994) 255–266
6. Abiteboul, S.: On views and XML. In: Proceedings of the 18th ACM SIGPLANSIGACT symposium on Principles of Database Systems, ACM Press (1999) 1–9
7. Greenwald, M.B., Moore, J.T., Pierc, B.C., Schmitt, A.: A language for bidirectional tree transformations. Technical Report Technical Report MS-CIS-0308, Department of Computer and Information Science University of Pennsylvania(2003)
8. Hu, Z., Mu, S.C., Takeichi, M.: A programmable editor for developing structured
documents based on bidirectional transformations. In: Proceedings of ACM SIGPLAN 2004 Symposium on Partial Evaluation and Program Manipulation, ACM
Press (2004) 178–189
9. Meertens, L.:
Designing constraint maintainers for user interaction.
http://www.cwi.nl/~lambert (1998)
10. Mu, S., Hu, Z., Takeichi, M.: An injective language for reversible computation. In:
Seventh International Conference on Mathematics of Program Construction (MPC
2004), Stirling, Scotland, Springer Verlag, LNCS 3215 (2004) 289–313
11. Wallace, M., Runciman, C.: Haskell and XML: Generic combinators or typebased translation? In: ACM SIGPLAN International Conference on Functional
Programming, Paris, ACM Press (1999) 148–159
12. Bird, R.: Introduction to Functional Programming using Haskell. Prentice Hall
(1998)
13. Mu, S., Hu, Z., Takeichi, M.: An algebraic approach to bi-directional updating.
In: Second ASIAN Symposium on Programming Languages and Systems(APLAS
2004), Taipei, Taiwan, Springer Verlag, LNCS 3302 (2004) 2–18