Validity Check of Putback Transformations in Bidirectional Programming
Speaker: Zhenjiang Hu (National Institute of Informatics, Japan / Peking University)
A bidirectional transformation consists of pairs of transformations —a forward transformation |get| produces a target view from a source, while a putback transformation |put| puts back modifications on the view to the source— satisfying sensible roundtrip properties. Existing bidirectional approaches are |get|-based in that one writes (an artifact resembling) a forward transformation and a corresponding backward transformation can be automatically derived. However, the unavoidable ambiguity that stems from the underspecification of |put| often leads to unpredictable bidirectional behavior, making it hard to solve nontrivial practical synchronization problems with existing bidirectional transformation approaches. Theoretically, this ambiguity problem could be solved by writing |put| directly and deriving |get|, but differently from programming with |get| it is easy to write invalid |put| functions. An open challenge is how to check whether the definition of a putback transformation is valid, while guaranteeing that the corresponding unique |get| exists. In this talk we propose, as far as we are aware, the first safe language for supporting putback-based bidirectional programming. The key to our approach is a simple but powerful language for describing primitive putback transformations. We show that validity of putback transformations in this language is decidable and can be automatically checked. A particularly elegant and strong aspect of our design is that we can simply reuse and apply standard results for treeless functions and tree transducers in the specification of our checking algorithms.
Zhenjiang Hu is a full professor of National Institute of Informatics (NII) in Japan and a Changjiang Scholar in Peking University. He received his BS and MS from Shanghai Jiao Tong University in 1988 and 1991, respectively, and PhD degree from University of Tokyo in 1996. He was a lecturer (1997–1999) and an associate professor (2000–2007) in University of Tokyo, before joining NII as a full professor in 2008. His main interest is in programming languages and software engineering in general, and functional programming, parallel programming, and bidirectional model-driven software development in particular. He is the academic committee chair of the NII Shonan Meetings, an IFIP WG 2.1 member, and is serving on the steering committees of ICFP, Haskell, APLAS, ICMT, and BX. He also belongs to the editorial boards of IEEE Transactions of Software Engineering, Science of Computer Programming, and Software and Systems Modeling.