Invertible Parsing: The Point

Episode #184 • Apr 4, 2022 • Subscriber-Only

We conclude our series on invertible parsing by converting a more complex parser into a parser-printer, and even enhance its format. This will push us to think through a couple more fun parser-printer problems.

Unlock This Episode

Our Free plan includes 1 subscriber-only episode of your choice, plus weekly updates from our newsletter.

Introduction

Phew, ok. We didn’t plan on having to do this additional episode after the last one, but it just goes to show how truly bizarre parser-printers can be. We didn’t think it would take us 6 episodes to cover the foundations of parser-printers, yet here we are.

But, we don’t think it’s appropriate to end the series just yet. So far we’ve only built a single parser-printer, which is essentially just a CSV parser that transforms the data into an array of User structs. While we did encounter some mind trippy stuff along the way, real world parser-printers can have even more bizarre situations that need careful thinking. So, we want to end this series by building one more parser-printer that is a lot more complex.

Recall that the parser we used as an example when building up the parser library from scratch in past episodes was a “marathon race” parser. It worked on a textual format that described a collection of races, each race of which had a city name, an entry fee with different currencies, and a list of geographic coordinates that described the race route.

This episode is for subscribers only.

Subscribe to Point-Free

Access this episode, plus all past and future episodes when you become a subscriber.

See plans and pricing

Already a subscriber? Log in

References

Invertible syntax descriptions: Unifying parsing and pretty printing

Tillmann 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 Prisms

Fraser 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 FromJSON and ToJSON instances 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”).

Downloads