Unlock This Episode
Our Free plan includes 1 subscriber-only episode of your choice, plus weekly updates from our newsletter.
So we are now able to parse and print on more general types of input, which means we do not need to sacrifice performance in order to unify parsing and printing.
This is looking incredible, but there’s still one glaring problem that we have no yet addressed. Earlier we came across some innocent looking code that simply mapped on a parser to transform its output and we found that we couldn’t make that operation printer-friendly. The types simply did not line up.
Well, we are finally ready to tackle this seemingly simple problem. Turns out it’s not quite so simple, and to solve this we really have to contort our minds in some uncomfortable ways and it truly gets at the heart of what it means for printing to be inverse of parsing.
Subscribe to Point-Free
Access this episode, plus all past and future episodes when you become a subscriber.
Already a subscriber? Log in
Invertible syntax descriptions: Unifying parsing and pretty printingTillmann Rendel and Klaus Ostermann • Thursday Sep 30, 2010
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 using this interface. 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.
This publication (from 2010!) was the initial inspiration for our parser-printer explorations, and a much less polished version of the code was employed on the Point-Free web site on day one of our launch!
Unified Parsing and Printing with PrismsFraser Tweedale • Friday Apr 29, 2016
Parsers and pretty printers are commonly defined as separate values, however, the same essential information about how the structured data is represented in a stream must exist in both values. This is therefore a violation of the DRY principle – usually quite an obvious one (a cursory glance at any corresponding
ToJSONinstances suffices to support this fact). Various methods of unifying parsers and printers have been proposed, most notably Invertible Syntax Descriptions due to Rendel and Ostermann (several Haskell implementations of this approach exist).
Another approach to the parsing-printing problem using a construct known as a “prism” (a construct Point-Free viewers and library users may better know as a “case path”).