Unlock This Episode
Our Free plan includes 1 subscriber-only episode of your choice, plus weekly updates from our newsletter.
So we think this is absolutely incredible. The users parser has undergone only one single cosmetic change, that of using the
.struct conversion instead of just the initializer, and almost as if by magic the parser has also become a printer. We can invoke the
We want to stress that it can be a little mind trippy sometimes to figure out how to simultaneously parse and print. When considering printing we have to constantly be mindful of what it means to reverse the effects of parsing, and that can be a very subtle thing. For example, the
Prefix parser consumes from the beginning of an input until a predicate fails, whereas the
Prefix printer appends to the end of an input only if the entire value satisfies the predicate.
Another example was
OneOf, where the
OneOf parser tries a list of parsers from top-to-bottom, or most specific to least specific, and stops at the first successful one. Whereas the
OneOf printer tries that list in reverse, from bottom-to-top, or least specific to most specific, and stops at the first successful one.
Even something as simple as mapping the output of a parser completely broke down when it came to printers. It is not enough to know how to transform an output into a new kind of output, you also need to know how to transform those new outputs back into outputs so that they can be printed.
Luckily, if you don’t care about printing, then you can just continue using the parser library as it exists today without ever thinking about printing. But, if you do care about printing, then all of these subtleties and complexities are problems that you would have even if you weren’t trying to create a unified parser-printer, it just may not be as obvious. Trying to create a parser-printer forces you to come face-to-face with the realities of how complex your domain is early since at every step of the way you have to prove that you can reverse the effects of parsing by printing. You are not allowed to just willy-nilly
.map your parsers without a care in the world because that is not a printer-friendly thing to do. Each time you map to transform an output you have to be prepared to also supply a reverse transform to undo the effects for printing. And that can be a challenge to wrap your head around.
So, you might think after 5 episodes we would be done with printing, but that is not the case. We thought we were done, and in fact we had already recorded a nice outro episode that we should be transitioning to right now. But, either Stephen is taking invertibility too seriously by reversing the growth of his hair, or we had to re-shoot this episode due to some new information that came to light.
And indeed, the week we kicked off the invertible parsing series there were some really interesting discussions happening in the parsing library’s repo that made us realize there is still another subtlety when dealing with parser-printers. This was brought up by a Point-Free subscriber, David Peterson, who is using our library to build a parser for a specific documentation format. While constructing his parsers he came across some very simple and natural parsers that could not reasonably be made into printers.
Turns out, one of the fundamental operations of how we compose printers was still not quite right. There is one small tweak we can make that instantly unlocks the ability to turn his parsers into printers, and even fixes a few drawbacks some of the library’s parser-printers have. It’s honestly a little surprising to see just how subtle parser-printers can be, especially since we’ve been thinking about them for over 4 years now, and we’ve iterated on the concepts and APIs many, many times, but we still never uncovered this one issue.
But luckily these subtleties are mostly for the library to worry about. Not the library user. By sweating the details of these tiny parser-printer combinators to make sure they plug together correctly we can allow people to build immensely complex parser-printers and be confident that what you have built is correct. And this is why we think a composable framework of parser-printers is so much more superior than writing ad-hoc parser-printers.
Subscribe to Point-Free
Access this episode, plus all past and future episodes when you become a subscriber.
Already a subscriber? Log in
Point-Free community member David Peterson brought it to our attention that it would be better if printers flipped the order in which they are run.
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”).