No.091 Bidirectional Transformations

Icon

NII Shonan Meeting Seminar 091

Latest Information

Overview

Bidirectional transformations (BX) are a common pattern of computing: transforming data from one format to another, and requiring a transformation in the opposite direction that is in some sense an inverse. The most well-known instance is the view update problem from relational database design: a view represents a kind of virtual database table, computed on the fly from concrete source tables rather than being represented explicitly, and the problem comes when mapping an update of the view back to a corresponding update on the source tables.  In a similar way, the problem is central to model transformations, playing a crucial role in software evolution: having transformed a high-level model into a lower-level implementation, one often needs to restore consistency between the two parts that may have evolved separately.  Giving this widespread applicability, research on BX naturally spans multiple disciplines: Programming Languages (PL), Graph Transformations (GT), Software Engineering (SE), and Databases (DB).

  1. In PL research, the goal is to design languages that are suitable for programming BX (i.e., two opposing transformations are encoded in a single definition rather than with two separate definitions). Notable techniques includes lenses (collection of combinators, which can be read in two ways), and bidirectionalization (program transformation that constructs bidirectional programs from unidirectional ones).
  2. In GT research, a rule-based approach is taken by specifying consistency as a direction-agnostic graph grammar, i.e., a set of high-level graph transformation rules that generate the language of consistent pairs of graphs. Incremental forward and backward synchronizers with desirable properties are then automatically derived by operationalizing this grammar.
  3. In SE research, the goal is to support different software engineering activities with BX. In software development, people usually create different kinds of artefacts, and it has been a long-standing problem to synchronize these artefacts and keep them consistent. By applying BX to these problems, SE researchers have contributed to different aspects of BX research, such as synchronization of object-oriented models, delta-based BX, and exploring the design space of BX.
  4. In DB research, BX concerns the classical view-update problem of relational databases, the dual problem of incremental view maintenance, and modern manifestations of synchronization problems such as data exchange and provenance. XML transformations is another active research area of BX, effectively allowing queries to be made bidirectional.

The Shonan meeting proposed in 2016 will build on the momentum and results generated at previous meetings of similar nature (Dagstuhl 2011 and Banff 2013) to further develop cross-disciplinary research agenda and integration effort.

Topics

  • Connecting latest advances in individual areas to applications in other areas of BX.
  • Exploring unifying mathematical foundations and principles of BX.
  • Cross-disciplinary survey/tutorial paper to capture both the state of the art and open challenges for BX in theory and practice.
  • Status update and discussion on cross disciplinary collaboration.
  • Book on BX as part of the Shonan series by Springer.
  • Benchmark/example/demonstrator

Format of the Meeting
We plan to organize some of the following activities:

  • Tutorials and hands-on tool demonstrations
  • Presentations of new results since the last meeting (in different areas)
  • Cross-disciplinary group work
  • Panel discussion on the future of BX
    • Decide whether our BX workshop should become a BX symposium?
    • How to encourage DB participation?
    • How to increase impact?
  • Position statements and working groups
  • BX related project announcement and introduction

Travelling Information and Tips:

Organizers

Anthony Anjorin, University of Paderborn, Germany

Zinovy Diskin, McMaster University and the University of Waterloo, Canada

Meng Wang, University of Kent, UK

Yingfei Xiong, Peking University, China

Participants

Faris Abou-Saleh, Oxford University

Anthony Anjorin, University of Paderborn

Dominique Blouin, University of Potsdam

Zinovy Diskin, McMaster University and the University of Waterloo

Jeremy Gibbons, University of Oxford

Soichiro Hidaka, Hosei University

Frédéric Jouault, ESEO

Michael Johnson, Macquarie University

Ekkart Kindler, Technical University of Denmark

Hsiang-Shang Ko, NII

Yngve Lamo, Bergen University College

Ralf Lämmel, University of Koblenz-Landau

Erhan Leblebici, Technische Universität Darmstadt

Kazutaka Matsuda, Tohoku University

James McKinna, University of Edinburgh

Keisuke Nakano, University of Electro-Communications, Japan

Andy Schürr, Technische Universität Darmstadt

Tarmo Uustalu, Tallin University of Technology

Meng Wang, University of Kent

Jens Weber, University of Victoria

Bernhard Westfechtel, University of Bayreuth

Yingfei Xiong, Peking University

Vadim Zaytsev, Raincode

Haiyan Zhao, Peking University

Hao Zhong, Shanghai Jiao Tong University

Albert Zuendorf, University of Kassel

Schedule

shonancal

 

 

PROPOSED WORKING GROUPS

1. Design of Bidirectional Programming Languages
Chair: Kazutaka Matsuda

Since the original lens framework came out, a lot of studies on bidirectional transformations have been done; these studies include finer control on update (edit/delta) translation, and customization on backward behaviors. But, how can we *utilize* these results? More specifically, how can programming languages make us accessible to such results? For example, the working-group organizer recently proposed a higher-order and applicative (non-point-free) programming framework for classical lenses; can we have similar stories for other models of bidirectional transformations? For example, how can a programming language tell users what kind of updates are translatable and how they are translated? Can we use a type system or static analysis for this? Another question is: how can we evaluate such bidirectional programming languages?

In this working group, we would like to discuss how we can address these questions, and summarize pros and cons of programming languagefeatures when they are incompatible. Benchmarking examples/problems are also welcome.

2. BenchmarX Reloaded: Concrete Steps Towards an Executable Benchmark for BX Tools
Chair: Bernhard Westfechtel

In Dec 2013 at the Banff BX Seminar, requirements for and the basic structure of a BX benchmark (called a benchmarx) were discussed at the seminar and then proposed in form of a joint publication [1]. This paper was meant to inspire concrete benchmarx proposals, but up until today there is still no satisfactory benchmarx for even a single example. In this working group, we hope to discuss why this is the case, identify challenges to be tackled, and brainstorm for promising solutions. A recent benchmarx proposal for “batch-mode”, i.e., non-incremental bx [2], as well as our current collection of bx examples [3] can serve as inspiration.

[1] Anjorin, A., Cunha, A., Giese, H., Hermann, F., Rensink, A., & Schürr, A. (2014). BenchmarX. In S. K. Candan, S. Amer-Yahia, N. Schweikardt, V. Christophides, & V. Leroy (Eds.), BX 14 (Vol. 1133, pp. 82–86). Sun SITE.

[2] Westfechtel, B. Case-based exploration of bidirectional transformations in QVT Relations. Softw Syst Model (2016)

[3] James Cheney and James McKinna and Perdita Stevens and Jeremy Gibbons. Towards a Repository of Bx Examples. In S. K. Candan, S. Amer-Yahia, N. Schweikardt, V. Christophides, & V. Leroy (Eds.), BX 14 (Vol. 1133, pp. 82–86). Sun SITE.

3. Dependently Typed Edit Lenses on Containers
Chair: Jeremy Gibbons and Faris Abou-Saleh and James McKinna

Hofmann, Pierce and Wagner introduced an edit language for container types in their formulation for edit lenses. Recently we introduced a dependently-typed formulation of delta-based lenses. We have a skeleton proposal for the corresponding edit language for containers wrt such bx, but many details remain to be settled. We welcome discussion on appropriate language design for compositional editing on rich data structures; similarly for consistency relations/generalised lens complements in the sense of our recent work at Bx2016@ETAPS.

4. BX for new systems (cyber-security/reactive systems)
Chair: Michael Johnson

(This working group is merged from two proposals)
We already have examples of applications of Bx for cyber security reasons, and to satisfy privacy and other legislative requirements. Bidirectional transformations also have implications for reverse engineering and other fundamental cyber security problems. Bx can be used both to “open up” systems (by giving interconversions between different views of them) and conversely to construct them as safely sealed modules which interact only in a controlled way through bidirectional transformations that can be written and managed with partitioned knowledge (supporting military style “need-to-know” while minimising the “need” for any one individual or organisation). Is it time for us to jointly start discussing these applications?

Recently I’ve been looking at examples of reactive systems as bidirectional transformations but the fundamental correspondences seem to be between processes rather than data or states. Reactive systems and real-time computation would be important areas for Bx if indeed this is developed further, but also, there are echoes of other connections with extant Bx work. For example, Anthony’s “stable squares” (those that remain constant under forward and backward propagation and are (if I understand correctly) fundamental building blocks for his TGG tool work) are an instance of consistency between processes (the deltas on each side of the square); symmetric delta lenses when presented as spans have an inherent process consistency relation; attempts to define universal updates for symmetric lenses seem to depend upon a process consistency relation; the LRL=L rule of set-based symmetric lenses can be seen as arising from a process consistency relation; etc.

5. Can we put Put-Put to bed now
Chair: Michael Johnson

In a recent review of types of lenses I noted that all but one were explicitly required by their authors to satisfy an appropriately phrased Put-Put law (although sometimes the authors themselves were surprised to see that that was what they had required). (The one exception was “well-behaved set-based lenses”.) This is not an attempt to proselytise, but a genuine discussion as there are real empirical questions to be considered. But it is an attempt to step back from pre-formed views and see if we can come to common understandings as well as drawing on each others’ empirical experiences. It would be good for our community to clarify this topic

6. Synchronizing more than one model (handling concurrent changes)
Chair: Ekkart Kindler, Vadim Zaytsev

When a set of related models which are consistent with respect to some bx are changed concurrently by different people, the set of models needs to be made consistent again after these changes, which we call model synchronization. This seems to be a natural application domain for bi-directional transformations (bx) and is the topic of many applications.

However, it appears that rephrasing the synchronization problem in bx concepts and terminology precludes some approaches and hides away some important issues of synchronization. This is true already when we consider the consistency of two models — and even more so, when many models are involved.

Synchronization inherently involves the question of how two make two models consistent again in the best possible way. In the bx setting, a binary relation between two models would define consistency and a transformation in one direction of the other would re-establish consistency after one or both models have changed. Cheney et al. [1, 2] have proposed means for quantifying changes and to characterize changes with the “least surprise” for modelers. This work is an excellent starting point for this discussion. But, it also shows some shortcomings concerning the relevant engineering scenarios, the mathematical settings and formalizations, which limit the options for the adequate changes.

We will use this paper to identify some of the typical blind spots when we reduce model synchronization to bx, but there are more — in particular when it comes to synchronizing more than two models.

In the proposed working session, these limitations are identified and discussed, and then used to formulate a general framework for framing the synchronization (without the blind spots). In particular, notions of “most adequate changes” for synchronizing models are developed; they should build on the factors that have a bearing on what the “most adequate changes” are identified from some typical usage scenarios.

We could give a short presentation which motivates this session and a more detailed talk on the limitations of [1,2] which could be addressed in this session. This would hopefully trigger an intensive discussion and motivate others to join this work.

[1] James Cheney, Jeremy Gibbons, James McKinna, Perdita Stevens: Towards a Principle of Least Surprise for Bidirectional Transformations. In proceedings of Bx 15, volume of 1396 CEUR Workshop Proceeding, L’Aquila, Italy, July 2015.pp. 66-80

[2] James Cheney, Jeremy Gibbons, James McKinna, Perdita Stevens: On principle of Least Change and Least Surprise for bidirectional transformations. Special issue of JOT (selected papers of Bx15). Revised and extended version of [1]. To appear late 2016 / early 2017

7. Do lenses really address the view update problem?
Chair: Zinovy Diskin

In a well-known series of empirical studies [1,2], Jon Whittle et al. have shown that a major bottleneck for MDE adoption in industry is miscommunication between tool builders and tool users. The latter often misunderstand what a model management tool can actually do, because the former don’t have a precise language for specification of scenarios to be addressed by the tool, nor for how these scenarios are actually processed by the tool. Model synchronization can be especially sensitive to this sort of problems, which makes a proper classification of synchronization scenarios an important issue for bx.

It was shown in [3] that an accurate classification of bx scenarios requires going beyond the classical lens framework: the well-known informational (a)symmetry should be paired with another important bx parameter called organizational symmetry. Roughly, one side of a lens organizationally dominates the other side, if propagating updates from the former to the latter is less restricted (if at all) than the inverse propagation. Pairing two symmetries allows us to formally distinguish several important scenarios: view maintenance vs. view update vs. code generation vs. model compilation vs. reverse engineering, and so on. The total number of different synchronisation types formally distinguishable by different combination of two symmetries is surprisingly large and equal to 24.

The goal of the working group is to discuss these results and their possible applications to both bx theory and bx tooling. Specifically, a technically challenging topic is how to enrich the taxonomic space with concurrent updates (so far, the taxonomy has been built without considering concurrent updates). As for bx tooling, the builder-user miscommunication problem seems requiring to discuss both the cultural (cf. [1]) and the technical aspects of bx. Perhaps, we need to talk about a wider than technical view of bx tools.

[1] J. Whittle, J. Hutchinson, M. Rouncefield, H. Burden, R. Heldal, Industrial adoption of model-driven engineering: Are the tools really the problem? In: MoDELS’2013, p.1-17
[2] J. Hutchinson, J. Whittle, M. Rouncefield, S. Kristofferson, Empirical assessment of MDE in industry, In: ICSE’2011, pp. 471–480.
[3] Z. Diskin, H. Gholizadeh, A. Wider, K. Czarnecki, A Three-Dimensional Taxonomy for Bidirectional Model Synchronisation. J.Systems & Software, 111: 298-322 (2016)

 

 

PANEL DISCUSSIONS AND INVITED PANELLISTS

 

Panel 1: State- vs. delta-based bx: Pros and cons.

Any sync tool necessarily uses deltas. These deltas can be represented and managed in very different ways, but they should be there (unless the tool invokes some magic). Hence, the state-based setting is a rather abstract math model of the delta-based one. Formally, the former can be seen as a specialization of the latter, in which deltas are pairs of states with a trivial composition (a,b);(b,c)=(a,c). This is a very special specialization, which does not make too much sense for some, but is considered reasonable and useful by others.

Either way, the state-based framework is a math model of inherently delta-based tooling. The goal of the panel is to discuss the pros and cons of this model, and come to a reasonable conclusion on where and when this model should be used (if at all 🙂 ). Each of the panelists is asked to prepare a short 3-4 minute statement with a couple of slides (if needed), and share it with the other panelists and the audience. The first round of presentations will be followed by a discussion between the panelists, followed by a discussion with the audience.

Panelists:

  • Ekkart Kindler
  • Frédéric Jouault
  • James McKinna
  • Josh Ko
  • Soichiro Hidaka
  • Vadim Zaytsev

 

 

Panel 1:  Yes, we can, but maybe we shouldn’t: How to expand bx beyond
the boundaries of the bx community.

Synchronization of several artifacts is a practical problem of extreme importance for software engineering and databases. However, not only practitioners, but also researchers developing methodologies and experimenting with tools, manage this problem in ad hoc ways ignoring the basic ideas and terminology (not to mention methods and results) developed by the bx community. It’s not quite clear why this is the case. Maybe the models bx employs are inadequate, and/or the math is too complex, and/or the advertisement is too subtle.  Or perhaps it’s just normal, as the adoption of a new framework takes time.

How should the bx community react to this? One position, arguably wise, is to leave the situation as is, hoping that at some later time bx methods will be recognized and acknowledged by the wider community. Another position is to consider the status quo as something wrong, and try to fix it. Then the question is how: should we develop a few pilot applications, cracking the shell in some easily marketable domains like security or healthcare? Or should we develop a series of tutorial papers and tutorials for major conferences? Publish a textbook? or/and… ?

The goal of the panel is to discuss the problem in any relevant context not necessarily limited to the ideas above. Each of the panelists (listed below) is asked to prepare a short 3-4 minute statement with a couple of slides if needed, and share it with the other panelists and the audience. The first round of presentations will be followed by a discussion between the panelists, followed by a discussion with the audience.

Panelists:

  • Andy Schurr
  • Jens Weber
  • Jeremy Gibbons
  • Mike Johnson
  • Ralf Lammel
  • Yingfei Xiong