Bidirectional transformation

In computer programming, bidirectional transformations (bx) are programs in which a single piece of code can be run in several ways, such that the same data are sometimes considered as input, and sometimes as output. For example, a bx run in the forward direction might transform input I into output O, while the same bx run backward would take as input versions of I and O and produce a new version of I as its output.

Bidirectional model transformations are an important special case in which a model is input to such a program.

Some bidirectional languages are bijective. The bijectivity of a language is a severe restriction of its power,^[1] because a bijective language is merely relating two different ways to present the very same information.

More general is a lens language, in which there is a distinguished forward direction ("get") that takes a concrete input to an abstract output, discarding some information in the process: the concrete state includes all the information that is in the abstract state, and usually some more. The backward direction ("put") takes a concrete state and an abstract state and computes a new concrete state. Lenses are required to obey certain conditions to ensure sensible behaviour.

The most general case is that of symmetric bidirectional transformations. Here the two states that are related typically share some information, but each also includes some information that is not included in the other.

Usage

Bidirectional transformations can be used to:

Maintain the consistency of several sources of information^[2]
Provide an 'abstract view' to easily manipulate data and write them back to their source

Definition

Bidirectional transformations fall into various well-studied categories.^[3]

A lens is a pair of functions $get:S\rightarrow V$ , $put:S,V\rightarrow S$ relating a source $S$ and a view $V$ . If these functions obey the three lens laws:

PutGet: $\forall s,v.get(put(s,v))=v$
GetPut: $\forall s.put(s,get(s))=s$
PutPut: $\forall s,v,v'.put(put(s,v),v')=put(s,v')$

It is called a well-behaved lens.^[4]

A related notion is that of a prism, in which the signatures of the functions are instead $get:S\rightarrow V+1$ , $put:V\rightarrow S$ . Unlike a lens, a prism may not always give a view; also unlike a lens, given a prism, a view is sufficient to construct a source. If lenses allow "focusing" (viewing, updating) on a part of a product type, prisms allow focusing (possible viewing, building) on a part of a sum type.

Both lenses and prisms, as well as other constructions such as traversals, are more general notion of bidirectional transformations known as optics.^[4]

Examples of implementations

Boomerang is a programming language that allows writing lenses to process text data formats bidirectionally
Augeas is a configuration management library whose lens language is inspired by the Boomerang project
biXid is a programming language for processing XML data bidirectionally^[5]
XSugar allows translation from XML to non-XML formats^[6]

References

^ Foster, Nate. "Semantics of Bidirectional Languages" (PDF). Archived from the original (PDF) on 26 July 2011. Retrieved 7 February 2011.
^ Czarnecki, Krzysztof; Foster, J. Nathan; Hu, Zhenjiang; Lämmel, Ralf; Schürr, Andy; Terwilliger, James F. "Bidirectional Transformations: A Cross-Discipline Perspective" (PDF). Retrieved 19 February 2024.
^ Foster, J. Nathan; Greenwald, Michael B.; Moore, Jonathan T.; Pierce, Benjamin C.; Schmitt, Alan (May 2007). "Combinators for Bidirectional Tree Transformations: A Linguistic Approach to the View-Update Problem". ACM Transactions on Programming Languages and Systems. 29. doi:10.1145/1232420.1232424. S2CID 53234629.
^ ^a ^b Riley, Mitchell (2018). "Categories of Optics". arXiv:1809.00738 [math.CT].
^ KAWANAKA, Shinya; HOSOYA, Haruo (2006). "biXid: A Bidirectional Transformation Language for XML" (PDF). doi:10.1145/1160074.1159830. Archived from the original (PDF) on 2 July 2007. Retrieved 7 February 2011.
^ "XSugar - Dual Syntax for XML Languages". brics.dk. Retrieved 19 February 2024.

External links

"GRACE International Meeting on Bidirectional Transformations". Archived from the original on 12 October 2014.
"Bidirectional Transformations". The Bx Wiki. Retrieved 19 February 2024.
Pacheco, Hugo; Cunha, Alcino (2012). Multifocal: A strategic bidirectional transformation language for XML schemas (PDF). International Conference on Theory and Practice of Model Transformations. Springer, Berlin, Heidelberg. doi:10.1007/978-3-642-30476-7_6.

[nate-foster-1] Foster, Nate. "Semantics of Bidirectional Languages" (PDF). Archived from the original (PDF) on 26 July 2011. Retrieved 7 February 2011.

[grace-report-2] Czarnecki, Krzysztof; Foster, J. Nathan; Hu, Zhenjiang; Lämmel, Ralf; Schürr, Andy; Terwilliger, James F. "Bidirectional Transformations: A Cross-Discipline Perspective" (PDF). Retrieved 19 February 2024.

[3] Foster, J. Nathan; Greenwald, Michael B.; Moore, Jonathan T.; Pierce, Benjamin C.; Schmitt, Alan (May 2007). "Combinators for Bidirectional Tree Transformations: A Linguistic Approach to the View-Update Problem". ACM Transactions on Programming Languages and Systems. 29. doi:10.1145/1232420.1232424. S2CID 53234629.

[lens-laws-4] Riley, Mitchell (2018). "Categories of Optics". arXiv:1809.00738 [math.CT].

[bixid-5] KAWANAKA, Shinya; HOSOYA, Haruo (2006). "biXid: A Bidirectional Transformation Language for XML" (PDF). doi:10.1145/1160074.1159830. Archived from the original (PDF) on 2 July 2007. Retrieved 7 February 2011.

[xsugar-6] "XSugar - Dual Syntax for XML Languages". brics.dk. Retrieved 19 February 2024.

[1]

[2]

[3]

[4]

[5]

[6]