More Web Proxy on the site http://driver.im/

Article

There and back again: arrows for invertible programming

Authors:

Artem Alimarine,

Sjaak Smetsers,

Arjen van Weelden,

Marko van Eekelen,

Rinus PlasmeijerAuthors Info & Claims

Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell

Pages 86 - 97

https://doi.org/10.1145/1088348.1088357

Published: 30 September 2005 Publication History

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]

A. Alimarine and R. Plasmeijer. A Generic programming extension for Clean. In T. Arts and M. Mohnen, editors, The 13th International workshop on the Implementation of Functional Languages, IFL'01, Selected Papers, pages 168--186. Älvsjö, Sweden, Sept. 2002.]]

Digital Library

[2]

W. Chen and J. T. Udding. Program inversion: more than fun! Sci. Comput. Program., 15(1):1--13, 1990.]]

Digital Library

[3]

A. Courtney and C. Elliott. Genuinely Functional User Interfaces. In Proceedings of the 2001 Haskell Workshop, September 2001.]]

[4]

E. W. Dijkstra. Program inversion. In Program Construction, pages 54--57, 1978.]]

Digital Library

[5]

J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt. Combinators for bi-directional tree transformations: A linguistic approach to the view update problem. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Long Beach, California, 2005. Extended version available as University of Pennsylvania technical report MS-CIS-03-08. Earlier version presented at the Workshop on Programming Language Technologies for XML (PLAN-X), 2004.]]

Digital Library

[6]

R. Glück and M. Kawabe. Derivation of deterministic inverse programs based on lr parsing. 2998:291--306, 2004.]]

[7]

R. Glück and M. Kawabe. Revisiting an automatic program inverter for lisp. volume 40, pages 8--17, New York, 2005. ACM Press.]]

Digital Library

[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]

J. Hughes. Generalising monads to arrows. Science of Computer Programming, 37(1-3):67--111, 2000.]]

Digital Library

[12]

P. Jansson and J. Jeuring. Polytypic compact printing and parsing. In S. D. Swierstra, editor, Proceedings 8th European Symposium on Programming, ESOP'99, Amsterdam, The Netherlands, 22-28 March 1999, volume 1576, pages 273--287. Springer-Verlag, Berlin, 1999.]]

Digital Library

[13]

P. Jansson and J. Jeuring. Polytypic data conversion programs. Science of Computer Programming, 43(1):35--75, 2002.]]

Digital Library

[14]

A. Löh, D. Clarke, and J. Jeuring. Dependency-style Generic Haskell. In Proceedings of the eighth ACM SIGPLAN International Conference on Functional Programming (ICFP'03), pages 141--152. ACM Press, 2003.]]

Digital Library

[15]

R. Paterson. A new notation for arrows. In International Conference on Functional Programming, pages 229--240. ACM Press, Sept. 2001.]]

Digital Library

[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.]]

Cited By

Xu XWu JWang YYin ZLi P(2021)Automatic Generation and Validation of Instruction Encoders and DecodersComputer Aided Verification10.1007/978-3-030-81688-9_34(728-751)Online publication date: 15-Jul-2021
https://doi.org/10.1007/978-3-030-81688-9_34
Delaware BSuriyakarn SPit-Claudel CYe QChlipala A(2019)Narcissus: correct-by-construction derivation of decoders and encoders from binary formatsProceedings of the ACM on Programming Languages10.1145/33416863:ICFP(1-29)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341686
Tan GMorrisett G(2018)Bidirectional Grammars for Machine-Code Decoding and EncodingJournal of Automated Reasoning10.1007/s10817-017-9429-160:3(257-277)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s10817-017-9429-1
Show More Cited By

Index Terms

There and back again: arrows for invertible programming
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell Symposium

Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12

Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Idioms are Oblivious, Arrows are Meticulous, Monads are Promiscuous

We revisit the connection between three notions of computation: Moggi s monads, Hughes s arrows and McBride and Paterson s idioms (also called applicative functors). We show that idioms are equivalent to arrows that satisfy the type isomorphism A B 1 (A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell

September 2005

126 pages

ISBN:159593071X

DOI:10.1145/1088348

Program Chair:
Daan Leijen
Universiteit Utrecht, The Netherlands

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

Haskell05

Sponsor:

Haskell05: Haskell Workshop 2005

September 30, 2005

Tallinn, Estonia

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
571
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xu XWu JWang YYin ZLi P(2021)Automatic Generation and Validation of Instruction Encoders and DecodersComputer Aided Verification10.1007/978-3-030-81688-9_34(728-751)Online publication date: 15-Jul-2021
https://doi.org/10.1007/978-3-030-81688-9_34
Delaware BSuriyakarn SPit-Claudel CYe QChlipala A(2019)Narcissus: correct-by-construction derivation of decoders and encoders from binary formatsProceedings of the ACM on Programming Languages10.1145/33416863:ICFP(1-29)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341686
Tan GMorrisett G(2018)Bidirectional Grammars for Machine-Code Decoding and EncodingJournal of Automated Reasoning10.1007/s10817-017-9429-160:3(257-277)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s10817-017-9429-1
Tan GMorrisett G(2016)Bidirectional Grammars for Machine-Code Decoding and EncodingVerified Software. Theories, Tools, and Experiments10.1007/978-3-319-48869-1_6(73-89)Online publication date: 8-Nov-2016
https://doi.org/10.1007/978-3-319-48869-1_6
Danielsson NWeirich S(2013)Correct-by-construction pretty-printingProceedings of the 2013 ACM SIGPLAN workshop on Dependently-typed programming10.1145/2502409.2502410(1-12)Online publication date: 24-Sep-2013
https://dl.acm.org/doi/10.1145/2502409.2502410
Pierce BLenzerini MBenedikt M(2012)Linguistic foundations for bidirectional transformationsProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems10.1145/2213556.2213568(61-64)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1145/2213556.2213568
Arnoldus Bvan den Brand MSerebrenik A(2011)Less is moreACM SIGPLAN Notices10.1145/2189751.204788747:3(137-146)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2189751.2047887
Arnoldus Bvan den Brand MSerebrenik ADenney ESchultz U(2011)Less is moreProceedings of the 10th ACM international conference on Generative programming and component engineering10.1145/2047862.2047887(137-146)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2047862.2047887
Wang MGibbons JMatsuda KHu Z(2010)Gradual refinementProceedings of the 10th international conference on Mathematics of program construction10.5555/1886619.1886643(397-425)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/1886619.1886643
Rendel TOstermann K(2010)Invertible syntax descriptionsACM SIGPLAN Notices10.1145/2088456.186352545:11(1-12)Online publication date: 30-Sep-2010
https://dl.acm.org/doi/10.1145/2088456.1863525
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents