Invertible Parsing: Bizarro Printing

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 .print method on the value to have a type safe way of transforming an array of users back into a string, which can then be saved to disk or sent over the network to an API.

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.