research-article

Haskell, do you read me?: constructing and composing efficient top-down parsers at runtime

Authors:

S. Doaitse Swierstra,

Eelco LempsinkAuthors Info & Claims

Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell

Pages 63 - 74

https://doi.org/10.1145/1411286.1411296

Published: 25 September 2008 Publication History

Abstract

The Haskell definition and implementation of read is far from perfect. In the first place read is not able to handle the associativities defined for infix operators. Furthermore, it puts constraints on the way show is defined, and especially forces it to generate far more parentheses than expected. Lastly, it may give rise to exponential parsing times. All this is due to the compositionality requirement for read functions, which imposes a top-down parsing strategy.

We propose a different approach, based on typed abstract syntax, in which grammars describing the data types are composed dynamically. Using the transformation libraries described in a companion paper these syntax descriptions are combined and transformed into parsers at runtime, from which the required read function are constructed. In this way we obtain linear parsing times, achieve consistency with the defined associativities, and may use a version of show which generates far fewer parentheses, thus improving readability of printed values.

The described transformation algorithms can be incorporated in a Haskell compiler, thus moving most of the work involved to compile time.

Supplementary Material

JPG File (1411296.jpg)

Download
16.48 KB

index.html (index.html)

Slides from the presentation

Download
.95 KB

Audio only (1411296.mp3)

Download
11.90 MB

Video (1411296.mp4)

Download
164.40 MB

References

[1]

Arthur Baars and Doaitse Swierstra. Typed transformations of typed abstract syntax. http://www.cs.uu.nl/research/techreps/, Utrecht University, 2008.

[2]

Arthur Baars, Andres Löh, and Doaitse Swierstra. Parsing permutation phrases. J. Funct. Program., 14 (6): 635--646, 2004. ISSN 0956-7968.

Digital Library

[3]

Arthur I. Baars and S. Doaitse Swierstra. Type-safe, self inspecting code. In Haskell '04: Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, pages 69--79, New York, NY, USA, 2004. ACM. ISBN 1-58113-850-4. http://doi.acm.org/10.1145/1017472.1017485.

Digital Library

[4]

Eric Bouwers, Martin Bravenboer, and Eelco Visser. Grammar engineering support for precedence rule recovery and compatibility checking. Electron. Notes Theor. Comput. Sci., 203 (2): 85--101, 2008. ISSN 1571-0661.

Digital Library

[5]

Martin Bravenboer. Exercises in Free Syntax. Syntax Definition, Parsing, and Assimilation of Language Conglomerates. PhD thesis, Utrecht University, Utrecht, The Netherlands, January 2008.

[6]

M. Johnson. Finite-state approximation of constraint-based grammars using left-corner grammar transforms. In COLING-ACL '98, Montreal, Quebec, Canada, pages 619--623. Association for Computational Linguistics, 1998.

Digital Library

[7]

Ralf Lämmel and Simon Peyton Jones. Scrap your boilerplate: a practical design pattern for generic programming. ACM SIGPLAN Notices, 38 (3): 26--37, March 2003. Proceedings of the ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI 2003).

Digital Library

[8]

Ralf Lämmel and Simon Peyton Jones. Scrap more boilerplate: reflection, zips, and generalised casts. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP 2004), pages 244--255. ACM Press, 2004.

Digital Library

[9]

Conor McBride and Ross Paterson. Applicative programming with effects. Journal of Functional Programming, 18 (01): 1--13, 2007. 10.1017/S0956796807006326.

Digital Library

[10]

Emir Pasalic and Nathan Linger. Meta-programming with typed object-language representations. In Generative Programming and Component Engineering (GPCE'04), volume LNCS 3286, pages 136--167, October 2004.

[11]

JC Petruzza, Koen Claessen, and Simon Peyton Jones. Derived read instances for recursive datatypes with infix constructors are too inefficient. URL http://hackage.haskell.org/trac/ghc/ticket/1544. GHC Ticket 1544.

[12]

Simon Peyton Jones. Haskell 98 Language and Libraries: the Revised Report. 2003.

[13]

Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Geoffrey Washburn. Simple nification-based type inference for gadts. SIGPLAN Not., 41 (9): 50--61, 2006. ISSN 0362--1340.

Digital Library

[14]

Tim Sheard and Simon Peyton Jones. Template meta-programming for haskell. In Proceedings of the ACM SIGPLAN workshop on Haskell, pages 1--16. ACM Press, 2002. ISBN 1-58113-605-6.

Digital Library

[15]

S. D. Swierstra. The Utrecht Parsing Libraries. http://www.cs.uu.nl/wiki/bin/view/HUT/ParserCombinators, July 2008.

Cited By

Willis JWu NPickering M(2020)Staged selective parser combinatorsProceedings of the ACM on Programming Languages10.1145/34090024:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3409002
Krijnen JSwierstra DViera M(2014)ExpandProceedings of the 16th International Symposium on Practical Aspects of Declarative Languages - Volume 832410.1007/978-3-319-04132-2_14(200-215)Online publication date: 20-Jan-2014
https://dl.acm.org/doi/10.1007/978-3-319-04132-2_14
Bagge ALämmel R(2013)Walk Your Tree Any Way You WantTheory and Practice of Model Transformations10.1007/978-3-642-38883-5_3(33-49)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38883-5_3
Show More Cited By

Index Terms

Haskell, do you read me?: constructing and composing efficient top-down parsers at runtime
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
      2. Language types
        Functional languages

Recommendations

Haskell, do you read me?: constructing and composing efficient top-down parsers at runtime
HASKELL '08

The Haskell definition and implementation of read is far from perfect. In the first place read is not able to handle the associativities defined for infix operators. Furthermore, it puts constraints on the way show is defined, and especially forces it ...
Typed Transformations of Typed Grammars: The Left Corner Transform

One of the questions which comes up when using embedded domain specific languages is to what extent we can analyze and transform embedded programs, as normally done in more conventional compilers. Special problems arise when the host language is ...
Typed transformations of typed abstract syntax
TLDI '09: Proceedings of the 4th international workshop on Types in language design and implementation

Advantages of embedded domain-specific languages (EDSLs) are that one does not have to implement a separate type system nor an abstraction mechanism, since these are directly borrowed from the host language. Straightforward implementations of embedded ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell

September 2008

134 pages

ISBN:9781605580647

DOI:10.1145/1411286

Program Chair:
Andy Gill
University of Kansas, US

ACM SIGPLAN Notices Volume 44, Issue 2
HASKELL '08
February 2009
126 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1543134
Issue’s Table of Contents

Copyright © 2008 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: 25 September 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP08

Sponsor:

ICFP08: ACM SIGPLAN International Conference on Functional Programming

September 25, 2008

BC, Victoria, Canada

Acceptance Rates

Haskell '08 Paper Acceptance Rate 13 of 28 submissions, 46%;

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

9
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Willis JWu NPickering M(2020)Staged selective parser combinatorsProceedings of the ACM on Programming Languages10.1145/34090024:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3409002
Krijnen JSwierstra DViera M(2014)ExpandProceedings of the 16th International Symposium on Practical Aspects of Declarative Languages - Volume 832410.1007/978-3-319-04132-2_14(200-215)Online publication date: 20-Jan-2014
https://dl.acm.org/doi/10.1007/978-3-319-04132-2_14
Bagge ALämmel R(2013)Walk Your Tree Any Way You WantTheory and Practice of Model Transformations10.1007/978-3-642-38883-5_3(33-49)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38883-5_3
Viera MSwierstra DDijkstra A(2012)Grammar fragments fly first-classProceedings of the Twelfth Workshop on Language Descriptions, Tools, and Applications10.1145/2427048.2427053(1-7)Online publication date: 31-Mar-2012
https://dl.acm.org/doi/10.1145/2427048.2427053
Devriese DPiessens F(2011)Explicitly Recursive Grammar CombinatorsPractical Aspects of Declarative Languages10.1007/978-3-642-18378-2_9(84-98)Online publication date: 2011
https://doi.org/10.1007/978-3-642-18378-2_9
Baars ASwierstra SViera MKennedy AAhmed A(2009)Typed transformations of typed abstract syntaxProceedings of the 4th international workshop on Types in language design and implementation10.1145/1481861.1481865(15-26)Online publication date: 24-Jan-2009
https://dl.acm.org/doi/10.1145/1481861.1481865
Swierstra S(2009)Combinator ParsingLanguage Engineering and Rigorous Software Development10.1007/978-3-642-03153-3_6(252-300)Online publication date: 27-Jul-2009
https://dl.acm.org/doi/10.1007/978-3-642-03153-3_6
Blažević MLégaré J(2017)Packrats parse in packsACM SIGPLAN Notices10.1145/3156695.312295852:10(14-25)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3156695.3122958
Blažević MLégaré JDiatchki I(2017)Packrats parse in packsProceedings of the 10th ACM SIGPLAN International Symposium on Haskell10.1145/3122955.3122958(14-25)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122955.3122958

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.

Figures

Tables

Media

View Table of Conten