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

research-article

Invertible syntax descriptions: unifying parsing and pretty printing

Authors:

Tillmann Rendel,

Klaus OstermannAuthors Info & Claims

Haskell '10: Proceedings of the third ACM Haskell symposium on Haskell

Pages 1 - 12

https://doi.org/10.1145/1863523.1863525

Published: 30 September 2010 Publication History

Abstract

Parsers and pretty-printers for a language are often quite similar, yet both are typically implemented separately, leading to redundancy and potential inconsistency. We propose a new interface of syntactic descriptions, with which both parser and pretty-printer can be described as a single program. Whether a syntactic description is used as a parser or as a pretty-printer is determined by the implementation of the interface. Syntactic descriptions enable programmers to describe the connection between concrete and abstract syntax once and for all, and use these descriptions for parsing or pretty-printing as needed. We also discuss the generalization of our programming technique towards an algebra of partial isomorphisms.

Supplementary Material

JPG File (haskell-0910.jpg)

Download
7.91 KB

MOV File (haskell-0910.mov)

Download
124.88 MB

References

[1]

}}Sergei Abramov and Robert Glück. Principles of inverse computation and the universal resolving algorithm. In The essence of computation: complexity, analysis, transformation, pages 269--295. Springer LNCS 2566, New York, 2002.

Digital Library

[2]

}}Artem Alimarine, Sjaak Smetsers, Arjen van Weelden, Marko van Eekelen, and Rinus Plasmeijer. There and back again: arrows for invertible programming. In Proceedings of the workshop on Haskell (Haskell '05), pages 86--97, New York, 2005.

Digital Library

[3]

}}Kenichi Asai. On typing delimited continuations: three new solutions to the printf problem. Higher-Order and Symbolic Computation, 22(3): 275--291, September 2009.

Digital Library

[4]

}}Claus Brabrand, Anders Møller, and Michael I. Schwartzbach. Dual syntax for XML languages. Information Systems, 33(4-5):385--406, 2008.

Digital Library

[5]

}}Olivier Danvy. Functional unparsing. Journal of Functional Programming,8(6):621--625, 1998.

Digital Library

[6]

}}Olivier Danvy. From reduction-based to reduction-free normalization. In Advanced Functional Programming, pages 66--164. Springer LNCS 5832, 2008.

Digital Library

[7]

}}J. Fokker. Functional parsers. In J. T. Jeuring and H. J. M. Meijer, editors, Advanced Functional Programming, First International Spring School, number 925 in LNCS, pages 1--23, 1995.

Digital Library

[8]

}}J. Nathan Foster, Alexandre Pilkiewicz, and Benjamin C. Pierce. Quotient lenses. In Proceeding of the International Conference on Functional Programming (ICFP '08), pages 383--396, New York, 2008.

Digital Library

[9]

}}Nathan J. Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt. Combinators for bi-directional tree transformations: A linguistic approach to the view update problem. In Proceedings of the symposium on Principles of Programming Languages (POPL '05), pages 233--246, New York, 2005.

Digital Library

[10]

}}Ralf Hinze. Formatting: a class act. Journal of Functional Programming, 13(5):935--944, 2003.

Digital Library

[11]

}}Christian Hofer, Klaus Ostermann, Tillmann Rendel, and Adriaan Moors. Polymorphic embedding of DSLs. In Proceedings of the Conference on Generative Programming and Component Engineering (GPCE '08), pages 137--148, New York, October 2008.

Digital Library

[12]

}}John Hughes. The Design of a Pretty-printing Library. In J. Jeuring and E. Meijer, editors, Advanced Functional Programming, pages 53--96. Springer LNCS 925, 1995.

Digital Library

[13]

}}John Hughes. Generalising monads to arrows. Science of Computer Programming, 37:67--111, May 2000.

Digital Library

[14]

}}Graham Hutton and Erik Meijer. Monadic parsing in Haskell. Journal of Functional Programming, 8(4):437--444, 1998.

Digital Library

[15]

}}Patrik Jansson and Johan Jeuring. Polytypic compact printing and parsing. In European Symposium on Programming, pages 273--287. Springer LNCS 1576, 1999.

Digital Library

[16]

}}Patrik Jansson and Johan Jeuring. Polytypic data conversion programs. Science of Computer Programming, 43(1):35--75, 2002. Oleg Kiselyov. Type-safe functional formatted IO. Available at http://okmij.org/ftp/typed-formatting/, 2008.

Digital Library

[17]

}}Edward A. Kmett. category extras: Various modules and constructs inspired by category theory. Available at http://hackage.haskell.org/package/category-extras, 2008.

[18]

}}Daan Leijen and Erik Meijer. Parsec: Direct style monadic parser combinators for the real world. Technical Report UU-CS-2001-27, Department of Computer Science, Universiteit Utrecht, 2001.

[19]

}}Conor McBride and Ross Paterson. Applicative programming with effects. Journal of Functional Programming, 18(1):1--13, 2008.

Digital Library

[20]

}}Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi. An injective language for reversible computation. In Proceedings of the International Conference on Mathematics of Program Construction (MPC '04). Springer Verlag, 2004.

[21]

}}Nicolas Oury and Wouter Swierstra. The power of pi. In Proceedings of the International Conference on Functional Programming (ICFP '08), pages 39--50, New York, 2008.

Digital Library

[22]

}}Tim Sheard and Simon Peyton Jones. Template meta-programming for Haskell. SIGPLAN Not., 37(12):60--75, 2002.

Digital Library

Cited By

Teegen FPrott KBunkenburg NHage J(2021)Haskell⁻¹: automatic function inversion in HaskellProceedings of the 14th ACM SIGPLAN International Symposium on Haskell10.1145/3471874.3472982(41-55)Online publication date: 18-Aug-2021
https://dl.acm.org/doi/10.1145/3471874.3472982
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
Edelmann RHamza JKunčak VDonaldson ATorlak E(2020)Zippy LL(1) parsing with derivativesProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385992(1036-1051)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385992
Show More Cited By

Index Terms

Invertible syntax descriptions: unifying parsing and pretty printing
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Invertible syntax descriptions: unifying parsing and pretty printing
HASKELL '10

Parsers and pretty-printers for a language are often quite similar, yet both are typically implemented separately, leading to redundancy and potential inconsistency. We propose a new interface of syntactic descriptions, with which both parser and pretty-...
Syntax error recovery in parsing expression grammars
SAC '18: Proceedings of the 33rd Annual ACM Symposium on Applied Computing

Parsing Expression Grammars (PEGs) are a formalism used to describe top-down parsers with backtracking. As PEGs do not provide a good error recovery mechanism, PEG-based parsers usually do not recover from syntax errors in the input, or recover from ...
Packrat parsing:: simple, powerful, lazy, linear time, functional pearl

Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '10: Proceedings of the third ACM Haskell symposium on Haskell

September 2010

166 pages

ISBN:9781450302524

DOI:10.1145/1863523

General Chair:
Jeremy Gibbons
University of Oxford, UK

ACM SIGPLAN Notices Volume 45, Issue 11
HASKELL '10
November 2010
156 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2088456
Issue’s Table of Contents

Copyright © 2010 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP '10

Sponsor:

SIGPLAN

ICFP '10: ACM SIGPLAN International Conference on Functional Programming

September 30, 2010

Maryland, Baltimore, USA

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

35
Total Citations
View Citations
455
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Teegen FPrott KBunkenburg NHage J(2021)Haskell⁻¹: automatic function inversion in HaskellProceedings of the 14th ACM SIGPLAN International Symposium on Haskell10.1145/3471874.3472982(41-55)Online publication date: 18-Aug-2021
https://dl.acm.org/doi/10.1145/3471874.3472982
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
Edelmann RHamza JKunčak VDonaldson ATorlak E(2020)Zippy LL(1) parsing with derivativesProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385992(1036-1051)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385992
Zhu ZKo HZhang YMartins PSaraiva JHu Z(2020)Unifying Parsing and Reflective Printing for Fully Disambiguated GrammarsNew Generation Computing10.1007/s00354-019-00082-yOnline publication date: 29-Apr-2020
https://doi.org/10.1007/s00354-019-00082-y
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
Xia LOrchard DWang M(2019)Composing Bidirectional Programs MonadicallyProgramming Languages and Systems10.1007/978-3-030-17184-1_6(147-175)Online publication date: 6-Apr-2019
https://doi.org/10.1007/978-3-030-17184-1_6
Matsuda KWang M(2018)Embedding invertible languages with binders: a case of the FliPpr languageACM SIGPLAN Notices10.1145/3299711.324275853:7(158-171)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3299711.3242758
Matsuda KWang MWu N(2018)Embedding invertible languages with binders: a case of the FliPpr languageProceedings of the 11th ACM SIGPLAN International Symposium on Haskell10.1145/3242744.3242758(158-171)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3242744.3242758
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
Matsuda KWang M(2018)FliPpr: A System for Deriving Parsers from Pretty-PrintersNew Generation Computing10.1007/s00354-018-0033-736:3(173-202)Online publication date: 27-Aug-2018
https://doi.org/10.1007/s00354-018-0033-7
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