🎉 Black Friday Sale! Save 30% when you subscribe today.

Invertible Parsing: The Solution, Part 1

Episode #179 • Feb 28, 2022 • Subscriber-Only

Now that we’ve framed the problem of printing, let’s begin to tackle it. We will introduce a Printer protocol by “reverse-engineering” the Parser protocol, and we will conform more and more parsers to the printer protocol.

Collection
Invertible Parsing
Invertible Parsing: The Solution, Part 1
Locked

Unlock This Episode

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

Sign in with GitHub

Introduction

So, all of this leads us to want to find a better way. We shouldn’t have to spend a lot of time writing a parser, and then spend an equal amount of time writing a printer, and then always remember that we need to synchronize future updates of one to the other. Ideally we should be able to write parser and printer code at exactly the same time, in the same package, guaranteeing that they will stay in sync.

And amazingly, it is possible. And even better, the theory of parser-printers looks remarkably similar to just plain parsers, so everything we have learned so far will be applicable. There are only a few twists and turns along the way that we have to be mindful of.

Let’s first develop the theory of printers much like we did for parsers. We will distill its essence into a single function, and we will explore examples of printers as well as operators on printers that allow us to build large, complex printers from smaller ones.

Inverting the parser protocol

References

  • Invertible syntax descriptions: Unifying parsing and pretty printing
    Tillmann Rendel and Klaus Ostermann • Sep 30, 2010
    Note

    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!

    https://www.informatik.uni-marburg.de/~rendel/unparse/
  • Unified Parsing and Printing with Prisms
    Fraser Tweedale • Apr 29, 2016
    Note

    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”).

    https://skillsmatter.com/skillscasts/16594-unified-parsing-and-printing-with-prisms

Downloads

Get started with our free plan

Our free plan includes 1 subscriber-only episode of your choice, access to 64 free episodes with transcripts and code samples, and weekly updates from our newsletter.

Sign up for free →
View plans and pricing