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

An Experimental Implementation of
Self-adjusting Bidirectional Transformations
Huu-Phuc Vo, Hiroyuki Kato, Soichiro Hidaka, Zhenjiang Hu

Bidirectional transformations provide a novel mechanism for synchronizing and maintaining the consistencyof information between source and view. Despite many advantages, bidirectional transformations are limitedin achieving incremental computing that concerns maintaining the source-view relationship of a program as
the source of a program is changed. Recent work on incremental computing such as self-adjusting computation developed useful techniques for writing programs which can adapt their view to any small or largechange in the source. In this article, we realize that bidirectional transformations on trees can be mademore eﬃcient by using self-adjusting techniques. The underlying systems of forward and backward transformations are represented with dynamic dependence graphs that record the data dependencies and control
dependencies. When the source or the view is modified, a change propagation algorithm will update theconnected view or source, and the dynamic dependence graphs by propagating the changes through thegraphs and re-executing code where necessary. The idea is to use forward and backward dynamic dependence graphs to identify and re-execute the parts of the computation that are aﬀected by modifications on
the source or the view. We refer to this approach as self-adjusting bidirectional transformations and showthat it is practical and eﬃcient.

tured document development [26].

Bidirectional

1 INTRODUCTION

graph transformation approaches can be distin-

Bidirectional transformations [13] [20] provide aguished at least according to two diﬀerent sorts

novel mechanism for synchronizing and maintain-[13]: reversible graph transformation languages anding the consistency of information between source

truly bidirectional graph transformation languages.

and view.

Bidirectional transformations can be

Triple Graph Grammars (TGGs) [37] [38] are in

used in many interesting applications, such as thethe class of bidirectional transformation languages

well-known view updating mechanism which has[14]. TGGs define a language of related pairs of

been intensively studied in the database commu-

graphs and derive pairs of uni-directional forward

nity [10] [15] [21] [22] [28], interactive user interface

and backward transformations.

design [32], coupled software transformation [27],Despite many advantages, bidirectional transfor-the synchronization of replicated data in diﬀer-

mations are limited in achieving incremental com-

ent formats [20], and presentation-oriented struc-puting that concerns maintaining the source-view

An Experimental Implementation of Self-adjusting
Bidirectional Transformations.
Huu-Phuc Vo, Dept. of Informatics, The Graduate
University for Advanced Studies, Japan.
Hiroyuki Kato, Soichiro Hidaka, Zhenjiang Hu, National Institute of Informatics, Tokyo, Japan.

relationship of a program as the source of a program is changed. In order to maintain and synchronize the consistency of source and view, a bidirectional transformation consists of a pair of a forward and a backward transformation in the typicalsetting, the changes will be updated to the view

technique is used for programs which can respondor reflected back to the source by completely re-to the modifications to their source data by updat-

computing the forward or backward transformation

ing the dynamic dependence graphs (DDGs) andwhen the source or view is changed by updates. In

carrying out the change propagation. DDGs are

such cases, the forward and backward transforma-graphs that represent the relationships between thetions are re-computed from scratch.

data and control dependencies. They can be built

Lenses are one the most popular approaches todefine bidirectional transformations between dataas the program executes and used to update thecomputation and the view when necessary.

models, and have been proposed by Foster et al.

A complete list of references on incremental com-[20] as a linguistic solution to the view-update prob-

putation can be found in the bibliography of Ra-lem. Every lens program can be read as a function

malingam and Reps [35]. The most eﬀective tech-

mapping sources to views as well as one mappingniques to solve the incremental computation prob-

updated views back to updated sources. Edit lenses

lem are based on dependence graphs, memoization,

are one of the few approaches that operate directly

and partial memoization [4]. Diﬀerent techniqueson edits and work with descriptions of changes tofor incremental updates exist such as static depen-

structures rather than with the structures them-dence graphs (Demers et al. [16] and Reps [36];selves [24].

Hoover [25]) and memoization (Pugh and Teitel-With this approach, no matter how small or large

baum [34]; Bellman [11]; McCarthy [31]; Michie

modification is applied to the source, the forward[33]) which can apply to any pure functional pro-and backward transformations are re-computed

gram. Building on Pugh and Teitelbaum’s work,from scratch.

Given some source data, the for-applications of various forms of memoization to in-ward and backward transformations, without any

cremental computation have been investigated [1];modifications to the view, transformations are com-Liu et al. [29]; Heydon et al. [23] [7].

puted in the initial computation. When the source

A partial evaluation approach to incrementalor the view is modified, the only way to update thecomputation that requires users to fix the parti-

modifications to the view or reflect them back totion of the source on which the program will be

the source is to re-compute from scratch without

specialized is introduced by Sundaresh and Hudak

reusing the previous computations.

[42]. The limitation of this approach is that the

Recent work on incremental computing suchmodifications to the source must only within a pre-as self-adjusting computation [5] developed use-

determined partition. In the context of lambda cal-ful techniques for writing unidirectional programs

culus, Field and Teitelbaum have presented formal

which can adapt their view to any small or large

reduction systems which optimally use partiallychange in the source. The self-adjusting techniqueevaluated results [19] [18]. Incremental computa-

is useful in circumstances where a small change intion has also been studied in artificial-intelligence

the source will lead to a small change in the view.

and logic-programming communities with general-In some restricted cases, the small changes from the

purpose techniques (Stallman and Sussman [40];source can not avoid a complete re-computation of

Doyle [17]; McAllester [30]).

the view; but in most cases, the previous computa-

In this paper, we present the idea of self-adjustingtions can be reused to produce the view with thelenses which applies the self-adjusting technique torelative changes from the source. The self-adjustingbidirectional transformations. We follow linguis-tic approach by building lenses with both a forward function and a backward function, with an

2 PRELIMINARY

underlying system of the self-adjusting computa-

2. 1 Self-adjusting computation

tion. This system uses the dynamic dependence

Self-adjusting computation has been applied tographs to track the controls and data dependencies

various application domains, including dynamic al-in an execution, combine with memoization by re-

gorithms, motion simulations, machine learning,membering function calls and their results. The

and incremental invariant checking [39]. These ap-

modifications to the source or the view of bidi-

plications confirm that the self-adjusting approach

rectional programs are translated one at a time.

can be eﬀective for a broad range of practical ap-

An additional challenging is how to update the dy-

plications.

namic dependence graphs and dually propagate theIn the adaptive functional programming and self-changes from source and view. This work is one

adjusting approaches, the key point is a modifiable

step to experimentally combine the self-adjustingreference (or modifiable in short), which holds thetechnique and lenses as well as to introduce thedata that can change overtime. A constraint overmethods to construct self-adjusting lenses, that aremodifiables is that they are not be written no morepractical and eﬃcienct, and includes a test suite

than once within the self-adjusting program.

and experiments with self-adjusting lenses.

Dynamic dependence graphs: The underlying of

Outline: In this paper, we realize that bidi-

forward and backward transformations are repre-

rectional transformations on trees can work moresented with dynamic dependence graphs (DDGs)eﬃciently by using self-adjusting techniques. We

that record data dependencies and control depen-model the bidirectional transformations on tree-

dencies. When the source or the view is modified,structured data as lenses [20] which map the con-a change propagation algorithm will update thecrete tree into a simplified abstract view in one di-

DDGs and the view by propagating the changes

rection, and map the modified abstract view andthrough the graphs and re-executing code where

the original concrete tree to a modified concrete

necessary. The idea is to use forward and back-tree in the appropriate direction. We give an intro-

ward DDGs to identify and re-execute the parts ofduction to bidirectional transformations, and thethe computation that are aﬀected by modifications

incremental computing problem in Section 1. We

on source or view. The dynamic dependence graphs

state preliminary result of adaptive programmingis described more precisely in [9]. Dynamic depen-and self-adjusting computations for the incremental

dence graphs can be viewed as a representation ofcomputing problem and describe lenses which will

the data and control dependencies. DDGs of a pro-be used for experiments and evaluation in Section

gram can be built as it executes by tracking the

2. In Section 3, we talk about the self-adjusting

executed operations, and used to update the com-lenses, and the method to transform the pure lenses

putation and the view when the sources are modi-

to self-adjusting lenses. We show the implementa-

fied. The core primitive of self-adjusting programstion, experiments and the evaluation in Section 4.

for operating on changeable data are: the mod op-

In section 5, we present related work on bidirec-

eration that creates a modifiable, the read and thetional transformations and self-adjusting computa-

write operations that provide access to the modifi-tion. We conclude the paper and discuss the results

able. The dynamic dependence graphs are used toin Section 6.

identify and re-execute the parts of computations

which are aﬀected by modifications.
Structure of dynamic dependence graph:

A is a set of abstract view structures. Second, theThenotion of well-behavedness is defined so that it can

DDGs of computations can be represented as aconvey how the get and putback parts of a lens

dynamic function call tree with nodes and edges.

should behave in concert. The forward and back-The nodes of the DDGs represent function calls.

ward evaluations should satisfy the bidirectional

The edges are relations between computation data

properties. Such properties are called PutGet andand function calls that depend on them and rep-

GetPut laws in the lens framework. For example,

resent the caller-callee relationship between func-

if we use get to extract an abstract view a from ation calls as well. Edges between computation data

concrete view c and then use the putback part to(i.e., sources, intermediate results) and function

push the same a back into c, we should get c back.

calls represent data dependencies: if a function call

The meaning of the notations l ↗ and l ↘ is that

reads a piece of data, then there is an edge fromthe get part of a lens lifts an abstract view out of asuch data to that call. With this structure, theconcrete one, while the putback part pushes down

DDGs can monitor source data, function calls anda new abstract view into an existing concrete view.

the relations between them.

When f is a partial function, we write f (a) ⊑ b if

Change-propagation algorithm: With the given

f is not defined on argument a or f (a) = b.

dynamic dependence graphs of a program andWell-behaved lenses: Let l be a lens, C and

set of modified source modifiables. The change-

A be subsets of fixed set V . We say that l is a

propagation can track the controls and data depen-well-behaved lens from C to A, written l ∈ C ⇀↽ A,

dencies in an execution of a program. The idea of

if it maps arguments in C to results in A and vice

the change-propagation is to re-evaluate the reads

versa.
l ↗(C) ⊆ A

which are aﬀected by the source modifications inthe sequential execution order.
Self-adjusting program:Given a purely func-

tional program, the DDGs can be constructed bylaws:(GETPUT)

executing it with the source. The self-adjusting
program is defined when the source is changed during the computation, the computation and view will
be updated by performing the change propagation
through the dynamic dependence graphs.

(GET)l ↘(A × C) ⊆ C (PUT)
and its get and putback functions obey the followingl ↘(l ↗ c,c)⊑ c

for all c ∈ C(PUTGET)l ↗(l ↘(a,c))⊑ afor all (a, c)∈ A × C

In this article we represent lists as trees by using a standard cons-cell encoding, and introduce
some derived lenses which are used for making

2. 2 Lenses
In this section, we introduce several lenses suchas the identity lens, the head lens, the tail lens, thefilter lens, the hoist lens, and the plunge lens. Thoselenses have all been defined by Nate Foster et al.
[20].

First, we phrase basic lens definitions which are
specified together with a type of the form C ⇀↽ A,
where C is a set of concrete source structures andself-adjusting lenses. Then we define and implement those lenses. There are many diﬀerent lenses
such as generic lenses (i.e. identity, composition,
conditional, and recursion), structure manipulationlenses which modify the shape of the tree near theroot (i.e.

hoist, plunge), tree navigation lenses

which apply diﬀerent lenses to diﬀerent parts of thetree, or one lens deeper in the tree (i.e. map, fil-ter), “database-like” lenses (i.e. flatten, join), andthe view and the source, then it restores the fil-structure replication lenses (i.e. merge, copy).

tered part of the source. In case the source is miss-In practice, there will be cases when we want toing, the putback function restores the source andapply the putback function but the concrete views

propagates the changes made to the view using Ω.

(or source) is not available. In this case, a placeholder Ω, pronounced missing, handles missing concrete views. For example, l ↘ (a, Ω) means that

表3

Filter lensfilter pd = fork p id (const {}d)”lens l creates a new source from the information∀C ⊆ T.∀p ⊆ N.∀d ∈ C\p .

in the abstract view (or view)”

filter pd ∈ (C |p .C\p ) ⇐⇒ C |pΩ

Identity lens: Identity lens is the simplest one.
The identity lens is a bijective lens from any set to

Hoist lens: The hoist lens is used to shorten aitself. The concrete view c and the abstract viewtree by removing an edge at the top. In the getwill be copied in the get direction and and in the

direction, given a edge n, it remove the edge n andputback direction, respectively.

returns the child of n. On the other hand, the putback function restores the edge n, the value of old

表1

Identity lens

id↗ c

=

c

id↘(a, c)=asource is ignored and a new one is created with theedge n pointing to the given view.

Ω∀C ⊆ V.id ∈ C ⇐⇒ C

表4

Head and tail projections: This is very simple
lenses for projecting the head and tail of the list.

Hoist lens(hoist n)↗ c

=

c(n)

(hoist n)↘(a, c)={n 7→ a}Ω∀C ⊆ T.∀n ∈ N. hoist n ∈ {n 7→ C} ⇐⇒ C

The first list lenses extract the head or tail of acons cell list. The lens hd expects a default tree,

Plunge lens: Conversely, the plunge lens is usedwhich it uses in the putback direction as the tail of

to deepen a tree by adding an edge n at the top of

the created tree when the concrete tree is missing;

the tree. In the get direction, a single edge n points

the get direction, it returns the tree under *h. The

to the source tree to form a new tree. In the put-lens tl works analogously.

back direction, the value of a source tree is ignored
and the result of the plunge is the view tree which

表2

Head tail projections

has exactly one subtree.

hd d = focus ∗h{∗t 7→ d}Ω∀C, D ⊆ T.∀d ∈ D. hd d ∈ (C :: D) ⇐⇒ C
tl d = focus ∗t{∗h 7→ d}Ω∀C, D ⊆ T.∀d ∈ C. tl d ∈ (C :: D) ⇐⇒ D

表5

Plunge lens(plunge n)↗ c={n 7→ c}(plunge n)↘(a, c)

=

a(n)
Ω

∀C ⊆ T.∀n ∈ N. plunge n ∈ C ⇐⇒ {n 7→ C}
Filter lens: Given a predicate p and the source,in the get direction, this lens produces the view bykeeping all the elements of the source that satisfy

3 SELF-ADJUSTING LENSES

the predicate p. On the other hand, the putback

In previous sections, we introduce the self-

direction, the putback function of filter lens takes

adjusting technique which is very useful for theincremental problem when the modifications on

source data will be changed over time and placesource leads to relative changes from view, as wellit into modifiable references. By doing this, theas the lenses. In this section, we present a brief

source will be monitored to any changes. Second,

overview of the self-adjusting lenses. The idea for

we specify the read of the modifiables from the orig-

self-adjusting lenses is to apply the self-adjusting

inal programs. We place the results of each expres-technique to both the get direction and the putbacksion into modifiable. The new modifiables which

direction in bidirectional transformation. The un-hold all the changeable data in the computation

derlying system of the self-adjusting computation

will be created because the reads are change com-is using the dynamic dependence graphs to track

putation.

the controls and data dependencies in an execution

After the initial run, the source data can be

combining with the memoization by rememberingchanged and then the program need to update

function calls and their results.

its view by performing change propagation. The
source modification process can be repeated as

3. 1 The Interface

many times as desired.

We present the self-adjusting library which is im-

the dynamic dependence graphs and the change-

The eﬀectiveness of

The im-propagation in the self-adjusting lens vary from theplementation of the self-adjusting library is used

position of modifications. If the modifications takefor encoding the self-adjusting lenses and testing

place at the beginning of source, the change propa-

them with several sources as well as modifications.

gation will require a from scratch execution. If the

All the implementations are written in OCaml pro-new element is insert into the source list at the end

gramming language.

or in the middle, the change propagation will takeplemented from Acar et al.

work [8].

First, in order to show the practical use of theO(log n) or O(n) expected time, respectively.

self-adjusting lenses, we implement identity, head,tail, hoist, plunge, and filter lenses as self-adjusting

3. 3 Encoding of Self-adjusting Lenses

lenses by using the self-adjusting library. Second,

For the self-adjusting lenses, one of the diﬃcul-

we test and compare the pure functional lenses andties is how to monitor the modifications to bothself-adjusting lenses to present the eﬃciency of thesource and view. Given a pure functional lens, we

self-adjusting lenses with several test suite. The

first apply a two step transformation to get the self-source data that will be the source for the test suites

adjusting lens.

is encoded as cons cell list of integer.

In the forward transformation, the source of theself-adjusting lens is monitored as the changeable

3. 2 Transformation

source by placing it into the modifiables. As the

The lenses are implemented as pure functional

forward transformation of self-adjusting lens exe-

programs which are written in Ocaml. Then wecutes, the underlying system represents the datatransform those pure functional programs into self-and control dependencies in the execution via aadjusting programs by using the Self-adjusting li-

dynamic dependence graphs. When the source tobrary which is re-implemented in Ocaml (the orig-

the lens changes, a change-propagation algorithm

inal self-adjusting library is implemented in SML).

updates the dependence graphs and the view byThis transformation consists of two steps.

propagating the modifications through the dynamic

First, we need to determine what parts of thedependence graphs and re-executing the computa-

tions where necessary.
In the backward transformation, the original

tions, the FDDGs and BDDGs are consistent andsynchronized.

source and the view of the self-adjusting lens areused to produce the new modified source. In thiscase, suppose that no modifications are made to

4 IMPLEMENTATION AND EXPERIMENTS

the view, the putback function executes to produce

In this section, we will explain how to implement

the same source. In such direction, we consider thethe self-adjusting lenses such as identity lens, head

modified view and the original source as the source

lens, tail lens, hoist, plunge and filter lens. We will

and the modified source is the view.

demonstrate experiments of those lenses, evaluate

The problem is how to represent the dynamic dependence graphs and the change-propagation forand discuss the experimental results in later partsof this section.

both forward and backward transformations so thatwith any modifications to the source or view, they
can be reflected back to the source or updated to
the view.

4. 1 Implementation of Pure Lenses andSelf-adjusting Lenses
We prepare two diﬀerent versions for each lensWith the self-adjusting approach Acar et al.

that we use as examples in the implementation sec-

2009 [4], we can separately transform a pure func-

tion. The first version is the implementation of thetional lens to self-adjusting lens. The main idea topure functional lenses, while the second version issolve this problem is to represent two dynamic de-of self-adjusting lenses.

pendence graphs, one for the forward transforma-

First, we introduce the construction and some ex-tion and another for the backward transformation.

amples of the pure functional lens which are imple-

Given the lens and the source, the forward dynamic

mentented in straightforward way. We choose thedependence graphs (FDDGs) represent the source

head lens for the example in this section. Given aof the self-adjusting lens as source. In the othersource list the forward transformation of the head

hand, without any modifications to the view, welens produces the first element of the source list as

represent the original source and the view of theview in case the source list is non empty or returns

lens as the backward dynamic dependence graphs

an empty list in case the given source list is empty.

(BDDGs) to monitor the changes. In the first case,In the backward transformation, the new source iswhen the source of the lens is modified, the FDDGs

created by concatenating the view and the tail ofare updated and then propagate the changes to thethe original source without the first element.

view. Because the view is updated from the source

Second, we will explain how to implement an self-

modifications, the BDDGs need to be updated fromadjusting lens from the pure functional lens. Since

the modified source and modified view in the for-the self-adjusting technique is used to place theward transformation. In the second case, on thesources to the modifiables for monitoring, we dis-

contrary, when the view of the lens is modified,tinguish the source of the forward transformations

the BDDGs are updated and then propagate theas original source from the source of the backward

changes to the source. The FDDGs need to be up-transformation as original source and view.

dated from the modified view and original source

Considering the code for the pure functional headbecause the source is updated from the view modifi-

lens and a self-adjusting lens, as shown in Figure

cations.In both forward and backward transforma-

1. The transformation from pure functional lens

図1

The implementation of pure functional and self-adjusting version of filter lens.

to self-adjusting lens is done in two steps. 1) We
First generate a lists of modifiables by placing eachelement of the list into a modifiable. By designing
this kind of structure, the modifiable list can beinserted or deleted elements to and from by users.
2) The second, we change the program so that byusing the read, value of the modifiable can be accessed. In order to check whether the source list
is empty, the self-adjusting head lens uses a read,then write the result to desitnation d. A call to

図2

Initial forward transformation of Identity
lens

mod (through modl) creates the modifiables that
destination d belongs to. These modifiables form
the view list which now is a modifiable list.
Similarly, we can transform all the lenses described in this paper from pure functional lenses

to self-adjusting lenses using the two above steps.

図6
図3

Initial backward transformation ofInsertion into source at the end of Filter
lens in forward transformation

Identity lensconstruct the dynamic dependence graphs, we compare the initial run of pure functional lenses andself-adjusting lenses.
In order to measure the eﬀectiveness of the selfadjusting lenses, we modify the sources of both versions of lenses with the insertion into several positions. With the modified source, the pure functional lenses re-execute and the self-adjusting lenses
図4

Initial forward transformation of Filter
lens

propage the changes to update their views. The
eﬀectiveness of the self-adjusting techinique wasproved in the publication of Acar et al. [8].
We demonstrate the result of the initialization of
the forward and backward transforamtions of theidentity lens and the filter lens. We prepare therandom source in diﬀerent sizes, from 1 thousand to
65 thousands of elements. In Figure 2 and Figure 3,
we present the experimental results of the forward
and backward transformations of filter lens. Like-

図5

Initial backward transformation of Filter
lenswise, results of initial bidirectional transformationsof filter lens are showed in Figure 4 and Figure 5.
In Figure 6 and Figure 7, we show that the self-

4. 2 Experiments

adjusting bidirectional transformations are practi-

We conduct experiments of self-adjusting lenses

cal and eﬃcient. The performance of self-adjustingby using sources of diﬀerent sizes. The source lists

lens is better than the pure functional lens when in-

of integer for the lenses are randomly generalized in

sertion into the source or view at the end. The self-many diﬀerent sizes. The lenses sequentially con-adjusting lens is more eﬀective than the pure func-

sume the sources of sizes (from 1 to 65,000). In

tional lens because it represents all source data andgeneral, we use the same sources for the pure andcontrol dependencies in dynamic dependence graphs

self-adjusting lenses in the experiments. As the self-

in the initialization phase while the pure functional

adjusting lenses must execute at the first time tolens does not save any information during its exe-

5 RELATED WORK
Bidirectional transformations have been discussed and studied in many diﬀerent areas andcommunities including heterogeneous data synchronization [20], software model transformation [41],constraint maintenance for graphical user interfaces
図7

Insertion into source at the end of Filter
lens in backward transformation[32], interactive structure editing [26] and relational

databases [12].
In the area of programming languages, Foster

cutions. As a result, when the source or the view of

et al.

the lens is modified, instead of re-computing fromapproach, called lens, to solve the classical view-scratch, the self-adjusting lens can re-use the previ-

updating problem: when a concrete data model isous computations and show the better performance

abstracted into a view, the question is how modifi-

than pure functional lens.

cations made to the view can be propagated back[20] proposed bidirectional transformation

as modifications to the original model. Lenses must
4. 3 Evaluation and Discussion

include two functions, one for extracting the ab-

In the experimental section, we compare thestract view from the concrete view, called get func-

initialization of the pure functional lenses andtion, and another for putting back the modified ab-

self-adjusting lenses.

In the first run, the purestract view back into the original concrete view tofunctional lenses are more eﬀective than the self-

produce the updated concrete view, called putback

adjusting lenses because the self-adjusting lenses

function. Their linguistic approach was developed

save computations and data for later use. Fromto support the development of bidirectional trans-

the second runs, the self-adjusting programs areformation on strings and trees.

more eﬀective than the pure programs theoracti-

The concept of adaptive computation was first

cally. However, depend on the postion of modifi-

introduced by Acar et al. 2002 [6], called adap-

cations, the eﬀectiveness of the self-adjusting pro-tive functional programming (AFP), generalizedgrams can be vary. For instance, when we insert

dependence-graph approaches by introducing dy-

new value to the beginning of the source, it means

namic dependence graphs (DDGs) and providingthat from the next run, the program will be re-a change-propagation algorithm for them.

run from scratch. Because in the initial run, we

can be applied to any purely functional program.

construct the dynamic dependence graphs which

A change-propagation algorithm that can update

represent the data dependence and control depen-

the dependence structure of the dynamic depen-

dencies as function call tree. The modification to

dence graph by inserting and deleting dependencies

the beginning of the source aﬀects shallow function

where necessary, makes applications of adaptive

call in tree, so the change propagation is slow infunctional programs be possible. Adaptive func-

such case. In other case, if we modify the source

tional programs can be written by using type-safeto the end, this aﬀects the deep function call tree,

linguistic facilities that guarantee safety and cor-

the change propagation in this case is faster than

rectness of change propagation. The two papers,

previous case.

one on an SML library for self-adjusting compu-

AFPtation (Acar et al. 2006a [2]) and the other on
eﬃcient implementation of the library (Acar et al.
2006b [5]), are based on Acar’s thesis (Acar et al.
2005 [3]). The later self-adjusting work is on experimental analysis (Acar et al. 2009 [4]) which
combines two papers above.
Our work was greatly inspired by work on selfadjusting computation (Acar et al. 2006 [2]). Unlike ordinary functional programs, the bidirectional
programs allow modifications to either modify thesource or the view before updating to or reflecting
back to the view or source, respectively. How to
update the dynamic dependence graph and propagate the changes from source and view dually is achallenge. This work is one step to experimentally
combine the self-adjusting technique and lenses.

6 CONCLUSION
This article reports our first experiments on selfadjusting lenses using self-adjusting computation
approach to the problem of incremental computation. The self-adjusting lenses can respond thesource data quickly and eﬀectively.

We showthat the pure functional lenses can transform to
self-adjusting lenses in separate transformations.
This article describes the method to construct selfadjusting lenses by using the Ocaml self-adjusting
library and demonstrates the experiments of theself-adjusting lenses. The future work is how tounify separate self-adjusting transformations whenconstructing self-adjusting lens so that the modifications in either source or view can update or reflect
back to the view or source in forward and backward
transformation, respectively.
参 考 文 献[ 1 ] Abadi, M., Lampson, B., and Lévy, J.-J.: Analysis and caching of dependencies, SIGPLAN Not.,
Vol. 31, No. 6(1996), pp. 83–91.
[ 2 ] Acar, U., Blelloch, G., Blume, M., Harper, R.,
and Tangwongsan, K.: A Library for Self-AdjustingComputation, Electron. Notes Theor. Comput. Sci.,
Vol. 148, No. 2(2006), pp. 127–154.
[ 3 ] Acar, U. A.: Self-Adjusting Computation, Technical report, In ACM SIGPLAN Workshop on ML,
2005.
[ 4 ] Acar, U. A., Blelloch, G. E., Blume, M., Harper,R., and Tangwongsan, K.: An experimental analysis of self-adjusting computation, ACM Trans. Program. Lang. Syst., Vol. 32, No. 1(2009), pp. 3:1–
3:53.
[ 5 ] Acar, U. A., Blelloch, G. E., Blume, M., andTangwongsan, K.: An experimental analysis of selfadjusting computation, SIGPLAN Not., Vol. 41,
No. 6(2006), pp. 96–107.
[ 6 ] Acar, U. A., Blelloch, G. E., and Harper, R.:
Adaptive functional programming, SIGPLAN Not.,
Vol. 37, No. 1(2002), pp. 247–259.
[ 7 ] Acar, U. A., Blelloch, G. E., and Harper, R.:
Selective memoization, SIGPLAN Not., Vol. 38,
No. 1(2003), pp. 14–25.
[ 8 ] Acar, U. A., Blelloch, G. E., and Harper, R.:
Adaptive functional programming, ACM Trans.
Program. Lang. Syst., Vol. 28, No. 6(2006), pp. 990–
1034.
[ 9 ] Acar, U. A., Blelloch, G. E., Harper, R., Vittes,
J. L., and Woo, S. L. M.: Dynamizing static algorithms, with applications to dynamic trees andhistory independence, Proceedings of the fifteenth
annual ACM-SIAM symposium on Discrete algorithms, SODA ’04, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, 2004,
pp. 531–540.
[10] Bancilhon, F. and Spyratos, N.: Update semantics of relational views, ACM Trans. Database Syst.,
Vol. 6, No. 4(1981), pp. 557–575.
[11] Bellman, R.: Dynamic Programming, Princeton
University Press, Princeton, NJ, USA, 1 edition,
1957.
[12] Bohannon, A., Pierce, B. C., and Vaughan,
J. A.: Relational lenses: a language for updatable views, Proceedings of the twenty-fifth ACM
SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS ’06, New York,NY, USA, ACM, 2006, pp. 338–347.
[13] Czarnecki, K., Foster, J. N., Hu, Z., Lämmel,
R., Schürr, A., and Terwilliger, J. F.: Bidirectional Transformations: A Cross-Discipline Perspective, Proceedings of the 2nd International Conference on Theory and Practice of Model Transformations, ICMT ’09, Berlin, Heidelberg, SpringerVerlag, 2009, pp. 260–283.
[14] Czarnecki, K. and Helsen, S.: Classification ofModel Transformation Approaches, OOPSLA 03
Workshop on Generative Techniques in the Context
of Model-Driven Architecture, 2003.
[15] Dayal, U. and Bernstein, P. A.: On the correcttranslation of update operations on relational views,
ACM Trans. Database Syst., Vol. 7, No. 3(1982),

pp. 381–416.
[16] Demers, A., Reps, T., and Teitelbaum, T.: Incremental evaluation for attribute grammars withapplication to syntax-directed editors, Proceedingsof the 8th ACM SIGPLAN-SIGACT symposium on
Principles of programming languages, POPL ’81,
New York, NY, USA, ACM, 1981, pp. 105–116.
[17] Doyle, J.: Readings in nonmonotonic reasoning,
Morgan Kaufmann Publishers Inc., San Francisco,
CA, USA, 1987, chapter A truth maintenance system, pp. 259–279.
[18] Field, J. and Teitelbaum, T.: Incremental reduction in the lambda calculus, Proceedings of the 1990
ACM conference on LISP and functional programming, LFP ’90, New York, NY, USA, ACM, 1990,
pp. 307–322.
[19] Field, J. H.: Incremental reduction in thelambda calculus and related reduction systems, PhD
Thesis, Ithaca, NY, USA, 1991. UMI Order No.
GAX91-31429.
[20] 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).
[21] Gottlob, G., Paolini, P., and Zicari, R.: Properties and update semantics of consistent views,
ACM Trans. Database Syst., Vol. 13, No. 4(1988),
pp. 486–524.
[22] Hegner, S.: Foundations of canonical update
support for closed database views, ICDT ’90, Abiteboul, S. and Kanellakis, P.(eds.), Lecture Notes in
Computer Science, Vol. 470, Springer Berlin Heidelberg, 1990, pp. 422–436.
[23] Heydon, A., Levin, R., and Yu, Y.: Caching
function calls using precise dependencies, SIGPLAN
Not., Vol. 35, No. 5(2000), pp. 311–320.
[24] Hofmann, M., Pierce, B., and Wagner, D.:
Edit lenses, SIGPLAN Not., Vol. 47, No. 1(2012),
pp. 495–508.
[25] Hoover, R.: Incremental graph evaluation (attribute grammar), PhD Thesis, Ithaca, NY, USA,1987. UMI Order No. GAX87-24200.
[26] Hu, Z., Mu, S.-C., and Takeichi, M.: A programmable editor for developing structured documents based on bidirectional transformations,
Higher Order Symbol. Comput., Vol. 21, No. 12(2008), pp. 89–118.
[27] Lämmel, R.: Coupled Software Transformations(Ext. Abstract), Proc. Int’l Workshop on Software
Evolution Transformations (SETra), Nov. 2004.
[28] Lechtenbörger, J. and Vossen, G.: On the computation of relational view complements, ACM
Trans. Database Syst., Vol. 28, No. 2(2003),
pp. 175–208.
[29] Liu, Y. A., Stoller, S. D., and Teitelbaum, T.:
Static caching for incremental computation, ACM
Trans. Program. Lang. Syst., Vol. 20, No. 3(1998),

pp. 546–585.
[30] McAllester, D.: Truth maintenance, Proceedingsof the eighth National conference on Artificial intelligence - Volume 2, AAAI’90, AAAI Press, 1990,
pp. 1109–1116.
[31] Mccarthy, J.: A Basis for a Mathematical Theory of Computation, Computer Programming andFormal Systems, North-Holland, 1963, pp. 33–70.
[32] Meertens, L.: Designing Constraint Maintainers
for User Interaction, Technical report, 1998.
[33] Michie, D.: ”Memo” Functions and Machine
Learning, Nature, Vol. 218, No. 5136(1968), pp. 19–
22.
[34] Pugh, W. and Teitelbaum, T.: Incremental
computation via function caching, Proceedings ofthe 16th ACM SIGPLAN-SIGACT symposium on
Principles of programming languages, POPL ’89,
New York, NY, USA, ACM, 1989, pp. 315–328.
[35] Ramalingam, G. and Reps, T.: A categorized
bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages,
POPL ’93, New York, NY, USA, ACM, 1993,
pp. 502–510.
[36] Reps, T.: Optimal-time incremental semantic
analysis for syntax-directed editors, Proceedings of
the 9th ACM SIGPLAN-SIGACT symposium on
Principles of programming languages, POPL ’82,
New York, NY, USA, ACM, 1982, pp. 169–176.
[37] Schürr, A.: Specification of Graph Translatorswith Triple Graph Grammars, Proceedings of the20th International Workshop on Graph-Theoretic
Concepts in Computer Science, WG ’94, London,
UK, UK, Springer-Verlag, 1995, pp. 151–163.
[38] Schürr, A. and Klar, F.: 15 Years of Triple
Graph Grammars - Research Challenges, New
Contributions, Open Problems, 4th International
Conference on Graph Transformation, Vol. 5214,
Springer Verlag, Heidelberg, Lecture Notes in Computer Science (LNCS), Sep 2008, pp. 411–425.
[39] Shankar, A. and Bodı́k, R.: DITTO: automatic incrementalization of data structure invariant checks (in Java), SIGPLAN Not., Vol. 42,
No. 6(2007), pp. 310–319.
[40] Stallman, R. M. and Sussman, G. J.: Forward
reasoning and dependency-directed backtracking ina system for computer-aided circuit analysis, Artificial Intelligence, Vol. 9, No. 2(1977), pp. 135–196.
[41] Stevens, P.: Bidirectional model transformations
in QVT: semantic issues and open questions, Proceedings of the 10th international conference on
Model Driven Engineering Languages and Systems,
MODELS’07, Berlin, Heidelberg, Springer-Verlag,
2007, pp. 1–15.
[42] Sundaresh, R. S. and Hudak, P.: Incremental Compilation via Partial Evaluation, Conference
Record of the 18th Annual ACM Symposium on
POPL, January 1991, pp. 1–13.