There and back again: arrows for invertible programming

ABSTRACT

Invertible programming occurs in the area of data conversion where it is required that the conversion in one direction is the inverse of the other. For that purpose, we introduce bidirectional arrows (bi-arrows). The bi-arrow class is an extension of Haskell's arrow class with an extra combinator that changes the direction of computation.The advantage of the use of bi-arrows for invertible programming is the preservation of invertibility properties using the bi-arrow combinators. Programming with bi-arrows in a polytypic or generic way exploits this the most. Besides bidirectional polytypic examples, including invertible serialization, we give the definition of a monadic bi-arrow transformer, which we use to construct a bidirectional parser/pretty printer.

REFERENCES

• 1: Artem Alimarine , Marinus J. Plasmeijer, A Generic Programming Extension for Clean, Selected Papers from the 13th International Workshop on Implementation of Functional Languages, p.168-185, September 24-26, 2001
• 2: Wei Chen , Jan Tijmen Udding, Program inversion: more than fun!, Science of Computer Programming, v.15 n.1, p.1-13, Nov. 1990 [doi>10.1016/0167-6423(90)90042-C ]
• 3: A. Courtney and C. Elliott. Genuinely Functional User Interfaces. In Proceedings of the 2001 Haskell Workshop, September 2001.
• 4: Edsger W. Dijkstra, Program Inversion, Program Construction, International Summer Schoo, p.54-57, July 26-August 06, 1978
• 5: J. Nathan Foster , Michael B. Greenwald , Jonathan T. Moore , Benjamin C. Pierce , Alan Schmitt, Combinators for bi-directional tree transformations: a linguistic approach to the view update problem, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.233-246, January 12-14, 2005, Long Beach, California, USA
• 6: R. Glück and M. Kawabe. Derivation of deterministic inverse programs based on lr parsing. 2998:291--306, 2004.
• 7: Robert Glück , Masahiko Kawabe, Revisiting an automatic program inverter for Lisp, ACM SIGPLAN Notices, v.40 n.5, p.8-17, May 2005 [doi>10.1145/1071221.1071222]
• 8: R. Hinze and S. Peyton Jones. Derivable type classes. In G. Hutton, editor, Proceedings of the 2000 ACM SIGPLAN Haskell Workshop, volume 41.1 of Electronic Notes in Theoretical Computer Science. Elsevier Science, Aug. 2001. The preliminary proceedings appeared as a University of Nottingham technical report.
• 9: P. Hudak, A. Courtney, H. Nilsson, and J. Peterson. Arrows, Robots, and Functional Reactive Programming. In J. Jeuring and S. Peyton Jones, editors, Advanced Functional Programming, 4th International School, volume 2638 of LNCS, Oxford, 2003. Springer.
• 10: P. Hudak, J. Peterson, and J. Fasel. A gentle introduction to Haskell 98. http://www.haskell.org/tutorial/, 1999.
• 11: John Hughes, Generalising monads to arrows, Science of Computer Programming, v.37 n.1-3, p.67-111, May 2000 [doi>10.1016/S0167-6423(99)00023-4 ]
• 12: Patrik Jansson , Johan Jeuring, Polytypic Compact Printing and Parsing, Proceedings of the 8th European Symposium on Programming Languages and Systems, p.273-287, March 22-28, 1999
• 13: Patrik Jansson , Johan Jeuring, Polytypic data conversion programs, Science of Computer Programming, v.43 n.1, p.35-75, April 2002 [doi>10.1016/S0167-6423(01)00020-X ]
• 14: Andres Löh , Dave Clarke , Johan Jeuring, Dependency-style generic haskell, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.141-152, August 25-29, 2003, Uppsala, Sweden
• 15: Ross Paterson, A new notation for arrows, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 16: R. Paterson. Arrows and Computation. In J. Gibbons and O. de Moor, editors, The Fun of Programming, A symposium in honour of Professor Richard Bird's 60th birthday, pages 201--222, Oxford, 2003. Palgrave.
• 17: S. Peyton Jones and Hughes J. et al. Report on the programming language Haskell 98. University of Yale, 1999. http://www.haskell.org/definition/.
• 18: R. Plasmeijer and M. van Eekelen. Concurrent CLEAN Language Report (version 2.0), December 2001. http://www.cs.ru.nl/~clean/.
• 19: B. Ross. Running programs backwards: the logical inversion of imperative computation. Formal Aspects of Computing Journal, 9:331--348, 1997.
• 20: Z. H. S-C. Mu and M. Takeichi. An algebraic approach to bidirectional updating. In The Second Asian Symposium on Programming Language and Systems, volume 3302 of LNCS, pages 2--18. Springer, 2004.
• 21: P. Wadler. Monads for functional programming. In M. Broy, editor, Program Design Calculi: Proceedings of the 1992 Marktoberdorf International Summer School. Springer-Verlag, 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Algorithms

Keywords:
arrows, haskell, invertible program construction, polytypic programming