Haskell, Do You Read Me; Constructing and Composing Efficient Top-down Parsers at Runtime

M. Viera, S.D. Swierstra, E. Lemspink

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageUndefined/Unknown
Title of host publicationProceedings of the first ACM SIGPLAN symposium on Haskell
EditorsA. Gill
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Number of pages12
Publication statusPublished - 25 Sept 2008


  • Wiskunde en Informatica (WIIN)

Cite this