2015年11月
"Bidirectionalization for free" for monomorphic transformations
Science of Computer Programming
- ,
- 巻
- 111
- 号
- 開始ページ
- 79
- 終了ページ
- 109
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.scico.2014.07.008
- 出版者・発行元
- ELSEVIER SCIENCE BV
A bidirectional transformation is a pair of mappings between source and view data objects, one in each direction. When the view is modified, the source is updated accordingly with respect to some laws. Over the years, a lot of effort has been made to offer better language support for programming such transformations. In particular, a technique known as bidirectionalization is able to analyze and transform unidirectional programs written in general purpose languages, and "bidirectionalize" them.
Among others, an approach termed semantic bidirectionalization proposed by Voigtlander stands out in terms of user-friendliness. A unidirectional program can be written using arbitrary language constructs, as long as the function it represents is polymorphic and the language constructs respect parametricity. The free theorems that follow from the polymorphic type of the program allow a kind of forensic examination of the transformation, determining its effect without examining its implementation. This is convenient, as the programmer is not restricted to using a particular syntax; but it does require the transformation to be polymorphic.
In this paper, we lift this polymorphism requirement to improve the applicability of semantic bidirectionalization. Concretely, we provide a type class PackM gamma alpha mu, which intuitively reads "a concrete datatype gamma is abstracted to a type alpha, and the 'observations' made by a transformation on values of type gamma are recorded by a monad mu". With PackM, we turn monomorphic transformations into polymorphic ones that are ready to be bidirectionalized. We demonstrate our technique with case studies of typical applications of bidirectional transformation, namely text processing. XML query and graph transformation, which were commonly considered beyond semantic bidirectionalization because of their monomorphic nature. (C) 2014 Elsevier B.V. All rights reserved.
Among others, an approach termed semantic bidirectionalization proposed by Voigtlander stands out in terms of user-friendliness. A unidirectional program can be written using arbitrary language constructs, as long as the function it represents is polymorphic and the language constructs respect parametricity. The free theorems that follow from the polymorphic type of the program allow a kind of forensic examination of the transformation, determining its effect without examining its implementation. This is convenient, as the programmer is not restricted to using a particular syntax; but it does require the transformation to be polymorphic.
In this paper, we lift this polymorphism requirement to improve the applicability of semantic bidirectionalization. Concretely, we provide a type class PackM gamma alpha mu, which intuitively reads "a concrete datatype gamma is abstracted to a type alpha, and the 'observations' made by a transformation on values of type gamma are recorded by a monad mu". With PackM, we turn monomorphic transformations into polymorphic ones that are ready to be bidirectionalized. We demonstrate our technique with case studies of typical applications of bidirectional transformation, namely text processing. XML query and graph transformation, which were commonly considered beyond semantic bidirectionalization because of their monomorphic nature. (C) 2014 Elsevier B.V. All rights reserved.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.scico.2014.07.008
- DBLP
- https://dblp.uni-trier.de/rec/journals/scp/MatsudaW15
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000368557000005&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/scp/scp111.html#journals/scp/MatsudaW15
- ID情報
-
- DOI : 10.1016/j.scico.2014.07.008
- ISSN : 0167-6423
- eISSN : 1872-7964
- DBLP ID : journals/scp/MatsudaW15
- Web of Science ID : WOS:000368557000005