Three Complementary Approaches to Bidirectional Programming

Authors: N. Foster, K. Matsuda, and J. Voigtländer
Published: In Spring School on Generic and Indexed Programming (SSGIP'10), Oxford, England, Revised Lectures, volume 7470 of LNCS, pages 1-46, Springer, 2012.
DOI: 10.1007/978-3-642-32202-0_1
BibTeX: FMV12.bib
Abstract: This paper surveys three distinct approaches to bidirectional programming. The first approach, syntactic bidirectionalization, takes a program describing the forward transformation as input and calculates a well-behaved reverse transformation. The second approach, semantic bidirectionalization, is similar, but takes the forward transformation itself as input rather than a program describing it. It requires the transformation to be a polymorphic function and uses parametricity and free theorems in the proof of well-behavedness. The third approach, based on bidirectional combinators, focuses on the use of types to ensure well-behavedness and special constructs for dealing with alignment problems. In presenting these approaches, we pay particular attention to use of complements, which are structures that represent the information discarded by the transformation in the forward direction.
Download: ThreeComplementaryApproachesToBidirectionalProgramming.pdf
Rights: Copyright held by Springer.