From State- to Delta-Based Bidirectional Model Transformations: the Asymmetric Case

From State- to Delta-Based Bidirectional Model Transformations: the Asymmetric Case
Zinovy Diskin, Yingfei Xiong, and Krzysztof Czarnecki
Journal of Object Technology 10(6):1-25, 2011

This paper is the journal version of an ICMT 2010 paper, which I had read a few years ago.  The journal version is sufficiently different to make it worthwhile to read if you'd already read the conference version; I had particular trouble with the small figures/examples in the conference version, and this one is much better in that respect.

The idea is to revisit the notion of "lens" or (asymmetric) bidirectional transformation, introduced in now-classic work by Foster et al. (POPL 2005, TOPLAS 2007).  Basically, a lens is a pair of functions
$\newcommand{\AA}{\mathbf{A}}$
$\newcommand{\BB}{\mathbf{B}}$

\[
\begin{eqnarray*}
get &:& \AA \to \BB\\
put &:& \AA\times \BB \to \AA
\end{eqnarray*}
 \]

where the idea is, $get$ maps some source data $A \in \AA$ to a "view" $B \in \BB$, and $put$ takes a (possibly updated) $B' \in \BB$ and the original $A \in \AA$ and produces a corresponding $A' \in \AA$.  These are expected to satisfy some basic consistency laws.


This paper argues that purely state-based lenses have some undesirable features,  gives some examples illustrating this, and argues that taking deltas into account can solve the problems.  To do this, the authors suggest viewing spaces of states with updates as categories, where the states $\AA_0$ are the objects and updates linking them $\AA_1$ are the arrows.  Then the get and put functions have two components: the traditional mappings on states, and mappings on deltas:

\[
\begin{eqnarray*}
dget &: &\AA_1 \to \BB_1\\
dput &:& \BB_1 \times \AA_0 \to \AA_1
\end{eqnarray*}
\]

The examples are a little handwavy and do not always make it easy to follow the point being made.  For example, Figure 2 compares two different ways of editing a view to get the same updated state, and (from the text) it seems that one of the updates is meant to correspond to a local change (replacing a string with another string) while the other update corresponds to deleting a larger part of the view and replacing it with a whole new view.  However, the updates $b_1$ and $b_2$ in the figure don't seem to correspond to this behavior: $b_1$ is written $\{p_1 \to p_1',p_2 \to p_2'\}$ and $b_2$ is written $\{p_1 \to \bot, p_2 \to p_2'\}$.  The update language being used here isn't really carefully defined (at least not this far into the paper) so while I get the gist of the example, the apparent typo is confusing.  Figure 6 has a similar problem, where the update $b$ includes a mapping $p_3 \to p_3$ and there is no $p_3$ in the states being modified.

A later example, in Figure 3, is characterized as "incorrect", but I believe its behavior satisfies at least the well-behavedness laws.  So apparently the authors mean "unintuitive", or at least the precise sense in which the example is incorrect is not spelled out.  The accompanying discussion in section 2.2 suggests that transformations are only composable when both states and deltas are in agreement, but it isn't clear what composable means yet - ordinary state-based lenses can be composed and composition respects the laws; so the authors presumably have some additional desirable property that isn't stated.

Section 3.2 discusses forward propagation of deltas, which is another incarnation of the incremental view maintenance problem in databases, and is also studied in a number of other settings, such as self-adjusting computation.  The discussion of traceability structures suggests a form of provenance could be used.  The citations might be worth chasing to learn more about how traceability links are used in software engineering/bidirectional model transformations, for comparison with trace data structures in self-adjusting computation or provenance.

The paper never makes fully explicit what the "models" being studied are.  They seem a lot like simple unordered trees/dictionaries, maybe with cycles.  It might be interesting to work out the details for a very simple setting such as flat key-value maps.  It would also be interesting to instantiate the overall setting with relations and compare with the classic work on incremental view maintenance / update translation.