Video #183: Invertible Parsing: Bizarro Printing

Episode: Video #183 Date: Mar 28, 2022 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep183-invertible-parsing-bizarro-printing

Description

We’ve had to really stretch our brains to consider what it means to reverse the effects of parsing, but let’s looks at some parsers that take it to the next level. They will force us to reconsider a fundamental part of printing, and will make our printers even more powerful.

Video

Cloudflare Stream video ID: d202777eace5fc1caef058f0f2084006 Local file: video_183_invertible-parsing-bizarro-printing.mp4 *(download with --video 183)*

References

Transcript

— 0:05

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.

— 0:28

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.

— 0:55

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.

— 1:13

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.

— 1:27

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.

— 2:17

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.

— 2:37

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.

— 3:05

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.

— 3:37

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. The problem

— 4:02

So, with that said, let’s explore this new subtlety of parser-printers and see how we can fix it.

— 4:10

But before diving in, let’s get everything in building order again. Last time we updated our User type from having an isAdmin boolean field to a role field described by an enum of three cases. We haven’t updated the input accordingly, so let’s quickly fix that.

— 4:52

We can see the problem if we take another look at our users parser: let users = Many { user } separator: { "\n" } terminator: { End() }

— 5:14

While we have implemented most of this printer’s functionality, there is still one glaring omission, and that’s the terminator.

— 5:22

Recall that the terminator was introduced to the Many parser in order for it to more accurately describe what it expects to consume, and provide better error messaging when it fails. For example, if we tried parsing some input that accidentally used a boolean instead of a role, it fails: try users.parse( """ 1,Blob,admin 2,Blob Jr,member 3,Blob Sr,true """ ) error: multiple failures occurred error: unexpected input --> input:3:12 3 | 3,Blob Sr.,true | ^ expected "admin" | ^ expected "guest" | ^ expected "member" error: unexpected input --> input:2:17 1 | 1,Blob Jr,guest | ^ expected end of input

— 6:20

Previously, before we introduced the terminator, the users parser would consume the first two lines, produce an array with a couple user, and the rest of the input would be left unconsumed. This seems too lenient since something definitely went wrong, and we’d like to know what.

— 6:42

The terminator parser is run once the element parser has consumed all it can. If it fails then re-throw any errors thrown by the element or separator parser.

— 7:15

So, this is really cool, but we aren’t actually using the terminator at all when printing: extension Many: Printer where Element: Printer, Separator: Printer, Separator.Output == Void, Result == [Element.Output] { func print( _ output: [Element.Output], to input: inout Element.Input ) throws { var firstElement = true for elementOutput in output { defer { firstElement = false } if !firstElement { try self.separator.print((), to: &input) } try self.element.print(elementOutput, to: &input) } } }

— 7:24

We don’t even require the terminator to be a printer, as evident by the fact that we never made the End parser into a printer.

— 7:27

We can make the Many printer take the terminator into account by simply printing with it once all the elements and separators have been printed: for elementOutput in output { … } try self.terminator.print

— 7:39

But of course this means the Terminator generic must be a printer: extension Many: Printer where Element: Printer, Separator: Printer, Separator.Output == Void, Terminator: Printer, Result == [Element.Output] { … }

— 7:46

But even then the terminator printer is too generic: try self.terminator.print(<#Terminator.Output#>, to: &<#Element.Input#>)

— 7:51

We know nothing about Terminator.Output , and so we have no hope of being able to pluck a value out of thin air just so that we can feed it to the print method.

— 8:01

We need to further constrain this like we did for the separator to only work with Void printers: extension Many: Printer where Element: Printer, Separator: Printer, Separator.Output == Void, Terminator: Printer, Terminator.Output == Void, Result == [Element.Output] { … }

— 8:08

And now we can finish implementing the method: func print( _ output: [Element.Output], to input: inout Element.Input ) throws { var firstElement = true for elementOutput in output { defer { firstElement = false } if !firstElement { try self.separator.print((), to: &input) } try self.element.print(elementOutput, to: &input) } try self.terminator.print((), to: &input) }

— 8:17

This gets the Many time compiling, but we now have some compiler errors down below because we have lost printability on our users parser since End is not a printer: Referencing instance method ‘print(_:to:)’ on ‘Many’ requires that ‘End<Substring>’ conform to ‘Printer’

— 8:47

So, let’s see what it takes to make End into a printer: extension End: Printer { func print(_ output: (), to input: inout Input) throws { <#code#> } }

— 9:04

We need to somehow print a void value into the input. We’re not really sure what it means to print the “end” of something. Perhaps we can take some inspiration from the parser implementation of End in order to figure out what it is we want to reverse: public struct End<Input: Collection>: Parser { @inlinable public init() {} @inlinable public func parse(_ input: inout Input) throws { guard input.isEmpty else { throw ParsingError.expectedInput("end of input", at: input) } } }

— 9:22

So it seems that End only works on collections, and that makes sense because we need some way to check if the input is “empty” in some sense so that we know if there’s anything left to consume. And all the parser does is confirm the collection is empty, and if not we throw an error. It doesn’t actually consume from the input or produce an output. In fact, the output is Void .

— 9:40

Now we can’t simply do the same for printing because input contains what we have printed so far: extension End: Printer { func print(_ output: (), to input: inout Input) throws { guard input.isEmpty else { throw PrintingError() } } }

— 9:53

This doesn’t really make any sense because of course the input is not going to be empty by the time we run the End printer. We should have printed everything by that point.

— 10:09

It doesn’t seem right, but it looks like the only thing we can really do here is… well, nothing: extension End: Printer { func print(_ output: (), to input: inout Input) throws { } }

— 10:16

I guess printing an End just means to do nothing. That seems a bit strange considering the parser does have actual logic and can fail. In fact, we can show concretely why this is weird by looking into how round-tripping behaves.

— 10:38

Suppose we did something non-sensical like parse with the End() parser, and then immediately after parse the string “Hello” from the beginning of the input: try Parse { End() "Hello" } .parse("Hello")

— 10:50

This of course shouldn’t work because the End parse fails right away since we are not at the end of the input: error: unexpected input --> input:1:1 1 | Hello | ^ expected end of input

— 11:10

And even if we are at the end of the input, parsing will fail since it somehow expects to parse “Hello” immediately after: try Parse { End() "Hello" } .parse("") error: unexpected input --> input:1:6 1 | | ^ expected "Hello"

— 11:24

However, printing this non-sensical thing works just fine: input = "" try ParsePrint { End() "Hello" } .print((), to: &input) input // "Hello"

— 11:39

It doesn’t complain at all and happily prints “Hello” to the input.

— 11:44

In order to properly implement a Printer conformance for End we need to somehow guarantee that the End printer is run after every single other printer. It’s not exactly clear how that is even possible. Currently the print method is handed the input of what has been printed so far, yet here we seem to want to know what is going to be printed in the future so that we know when we are at the end or not.

— 12:24

That seems really strange, but let’s look at another example of this idea in order to gain more intuition.

— 12:31

The library ships with a parser called the Rest parser, and it’s kinda related to the End parser. It simply consumes the entire rest of the input and returns it: public struct Rest<Input: Collection>: Parser where Input.SubSequence == Input { @inlinable public init() {} @inlinable public func parse(_ input: inout Input) throws -> Input { guard !input.isEmpty else { throw ParsingError.expectedInput("not to be empty", at: input) } let output = input input.removeFirst(input.count) return output } }

— 12:55

It may seem a little strange that we are throwing an error if the input is not empty, but we do this in order to catch some potentially non-sensical parsing situations.

— 13:04

For example, suppose you formed a parser that used two Rest parsers: try Parse { Rest() Rest() } .parse("Hello World")

— 13:14

We could interpret this to mean we are parsing a tuple that holds "Hello World" ” and an empty string, but it seems quite strange to knowingly use to Rest parsers when the whole point of it is to consume everything left of the input.

— 13:36

And we can run it to confirm it does in fact fail: error: unexpected input --> input:1:12 1 | Hello World | ^ expected a non-empty input

— 13:46

Now, you may think we are being way too strict with the Rest parser by throwing an error. After all, what if we really do need to allow for an empty input by the time the Rest parser runs? try Parse { Int.parser() Rest() } .parse("123") error: unexpected input --> input:1:4 1 | 123 | ^ expected a non-empty input

— 14:08

Well, you can always use the Optionally parser to promote it to a parser that produces an optional and always succeeds: try Parse { Int.parser() Optionally { Rest() } } .parse("42") // (42, nil)

— 14:34

Or you can use the .replaceError(with:) operator to coalesce any errors thrown to a concrete value, such as an empty string: try Parse { Int.parser() Rest().replaceError(with: "") } .parse("42") // (42, "")

— 14:46

So we don’t feel that it’s that big of a deal in practice to make the Rest parser strict.

— 14:50

Let’s now see what it would take to make it a printer: extension Rest: Printer { func print(_ output: Input, to input: inout Input) throws { <#code#> } }

— 14:56

We need to somehow print an Input value into an Input value. The only thing we know about Input is that it is a collection. We would hope we can append two input values so that we could append the rest of the input to what we have printed so far: extension Rest: Printer { func print(_ output: Input, to input: inout Input) throws { input.append(contentsOf: output) } } Value of type ‘Input’ has no member ‘append’

— 15:24

However that doesn’t work because generic Collection s don’t have an append method. This is exactly what motivating us to introduce the AppendableCollection protocol, and so if we constrain against that then we will see that everything now compiles: extension Rest: Printer where Input: AppendableCollection { func print(_ output: Input, to input: inout Input) throws { input.append(contentsOf: output) } }

— 15:40

This now compiles, but there is a small bit of additional logic we could layer on. Just as the Rest parser fails if you try parsing an empty string, we can make the Rest printer fail if you try to print an empty string: extension Rest: Printer where Input: AppendableCollection { func print(_ output: Input, to input: inout Input) throws { guard !output.isEmpty else { throw PrintingError() } input.append(contentsOf: output) } }

— 16:18

But is it correct? If we try to print with the non-sensical Rest / Rest printer we will see it happily just concatenates the two output strings into one: input = "" try ParsePrint { Rest() Rest() } .print(("Hello", "World"), to: &input) input // "HelloWorld"

— 16:56

This seems strange that because it should never be the case that running this parser produces two non-empty strings. After all, the first run of Rest should consume the entire input, so there would be nothing left for the second Rest to consume. Yet the print will happily accept two non-empty inputs and just concatenate them together.

— 17:18

The strangeness we are hinting out here is a direct result of the fact that this parser-printer does not round-trip. The printer takes two strings and returns a single one, and if we feed that string back into the parser we will see it throws an error: try Parse { Rest() Rest() } .parse("HelloWorld") error: unexpected input --> input:1:12 1 | Hello World | ^ expected not to be empty

— 17:38

This is not what we want to happen if round-tripping is an important property of our parser-printers.

— 18:00

It should even be clear from the implementation of the Rest printer that things aren’t quite right. There’s some logic in the parser that we are not capturing in the printer. In particular, we are failing the parser if one tries to parse the rest of an empty input, but we can’t do the same for the rest printer.

— 18:20

But if we naively add that logic it of course won’t be correct: extension Rest: Printer where Input: AppendableCollection { func print(_ output: Input, to input: inout Input) throws { guard !output.isEmpty, input.isEmpty else { throw PrintingError() } input.append(contentsOf: output) } }

— 18:28

Since input represents everything that has been printed so far, it will not typically be empty unless the Rest parser-printer is the first and only thing to be run.

— 18:35

And if we run our printer, we’ll see it fails quite simply. Playground execution terminated: An error was thrown and was not caught: PrintingError()

— 18:40

So there doesn’t seem to be a way to properly implement a Printer conformance for Rest that fully reverses the effects of the Parser conformance. What we really need to properly implement Rest as a printer is to somehow know for certain that it is the last printer listed in a builder context. Then the Rest printer could fail if it’s not the last one, but it is not clear at all how to achieve that.

— 19:11

This shortcoming, along with what we witnessed with the End parser, should have been enough for us look deeper into why this is happening, but it took someone from the Point-Free community, David Peterson , to bring up two more examples of how parser-printers can get a little weird.

— 19:26

For his domain he makes use of parsers known as Not and Peek , which allow you to perform a kind of “dry run” with a parser to check if it would succeed or fail. The parsers will not consume anything, and that’s why it’s a “dry run.”

— 19:40

For example, suppose we were parsing lines of a programming language, and we wanted a small parser that all it does it consume non-commented lines. We can use the Not parser to confirm that the first two characters of the line are not forward slashes, and if that succeeds we then take everything up to the next newline: let uncommentedLine = Parse { Not { "//" } Prefix { $0 != "\n" } }

— 20:35

This parser will succeed on non-commented lines: try uncommentedLine.parse("let x = 1") // "let x = 1"

— 20:58

But will fail on commented lines: try uncommentedLine.parse("// let x = 1") error: unexpected input --> input:1:1-2 1 | // Hello World! | ^^ expected not to be processed

— 21:05

And it even prints out a pretty good error message, showing the exact characters where parsing failed.

— 21:14

The Not parser works by running an upstream parser on the input, and if it succeeds then the Not parser fails, if it fails then we make the Not parser succeed, and in either case we always backtrack the input so that the upstream does not consume anything: public struct Not<Upstream: Parser>: Parser { public let upstream: Upstream … public func parse(_ input: inout Upstream.Input) throws { let original = input do { _ = try self.upstream.parse(&input) } catch { input = original return } throw ParsingError.expectedInput( "not to be processed", from: original, to: input ) } }

— 21:35

Notice that the Not parser must necessarily be a Void parser because it succeeds only when the upstream fails, which means we don’t have any meaningful output we can return.

— 21:51

Let’s see what it would take to make Not into a printer: extension Not: Printer { func print(_ output: (), to input: inout Upstream.Input) throws { <#code#> } }

— 22:17

We need to somehow print a void value into the upstream’s input. The only thing we have access to is the upstream parser, which if we constrain to also be a printer then we do get access to its print method: extension Not: Printer where Upstream: Printer { func print(_ output: (), to input: inout Upstream.Input) throws { self.upstream.print(<#Upstream.Output#>, to: &<#Upstream.Input#>) } }

— 22:26

But that’s not very useful because the upstream is a generic parser-printer, and so we need to feed it some output.

— 22:37

I suppose we could further constrain the upstream to be a Void parser-printer: extension Not: Printer where Upstream: Printer, Upstream.Output == Void { func print(_ output: (), to input: inout Upstream.Input) throws { try self.upstream.print((), to: &input) } }

— 22:52

And this certainly gets things compiling, but is it correct? Intuitively it seems it can’t possibly be correct because it has not done enough work to reverse the effects of parsing. The parser could throw an error based on how the upstream parser behaved, but here we are just 100% delegating to the upstream printer.

— 23:06

Let’s see this concretely by trying to round trip some printing and parsing. Let’s first try printing a commented line: input = "" try uncommentedLine.print("// let x = 1", to: &input) input // "//// let x = 1"

— 23:44

This is quite strange. Because the Not printer simply invokes the upstream printer with no logic it will first print two slashes, and then the Prefix printer will print the output we provide, which is “// let x = 1”. This causes us to get 4 leading slashes.

— 24:18

So maybe we shouldn’t do any printing at all inside the Not printer: extension Not: Printer where Upstream: Printer, Upstream.Output == Void { func print(_ output: (), to input: inout Upstream.Input) throws { } }

— 24:23

This also seems strange, but at least we don’t double up our slashes: input = "" try uncommentedLine.print("// let x = 1", to: &input) input // "// let x = 1"

— 24:37

But if we try to round-trip by feeding this input into the parser we get a failure: try uncommentedLine.parsers(input) error: unexpected input --> input:1:1-2 1 | // let x = 1 | ^^ expected not to be processed So this can’t be right.

— 24:47

A correct implementation of Not would somehow need to be able to see what the subsequent Prefix prints so that it could see whether or not a commented line was inserted. If it was, then the Not printer could choose to fail, and otherwise it could let things pass by without error. The solution

— 25:04

We have now see 3 examples of seemingly simple parsers that do not have satisfactory printer conformances. In each case we needed access to far more global context than what is available to us via the input argument. That input value simply represents what we have printed so far, but it appears that sometimes we need to know what later printers are going to print so that we can layer on additional logic.

— 25:27

For the Rest and End printers that manifested in wanting to know that they were the last in the list of printers, and for the Not printer it manifested by wanting to know what later printers were going to print so that it could fail if they print invalid things.

— 25:41

This all leads us to believe that perhaps we haven’t quite nailed down the right shape of our printers, and this is exactly what Point-Free community member David Peterson brought to our attention.

— 25:51

Let’s look again at the uncommentedLine parser-printer: let uncommentedLine = Parse { Not { "//" } Prefix { $0 != "\n" } }

— 26:01

The Not printer would love to see what Prefix printed so that it could layer on additional logic for deciding if it should fail or not. But that’s not possible right now, because if we put a print statement inside the Not to inspect its input: extension Not: Printer where Upstream: Printer, Upstream.Output == Void { func print(_ output: (), to input: inout Upstream.Input) throws { Swift.print("Not's input:", input) } }

— 26:24

And then run the printer: input = "" try uncommentedLine.print("// let x = 1", to: &input) input

— 26:27

We will see that the input is just an empty string: Not's input:

— 26:38

And this makes sense because the input handed to print is everything printed so far, and the Not printer is the first printer to run, hence nothing has been printed so far.

— 26:52

It’s almost like we want to run printers in reverse order in builder contexts. We already encountered this with the OneOf printer in which we needed to try the printers in reverse order in order to properly undo the effects of parsing: let field = OneOf { quotedField Prefix { $0 != "," } }

— 27:14

When printing we want to first try printing with the Prefix printer, and if that fails (which can only happen when the string we are printing contains a comma) we will fallback to the quotedField printer which simply put quotes around the string we hand to it.

— 27:26

Perhaps we just need to flip the order of printing in our Zip types, which is what parser builders use under the hood. For example, since the uncommentedLine printer lists a void parser and then a non-void parser, the builder secretly calls out to a ZipVO printer to coordinate running both printers, one after the other: extension Parsers.ZipVO: Printer where P0: Printer, P1: Printer { func print(_ output: P1.Output, to input: inout P0.Input) throws { try self.p0.print((), to: &input) try self.p1.print(output, to: &input) } }

— 28:02

Perhaps we just need to flip this so that we first print with p1 and then print with p0 : extension Parsers.ZipVO: Printer where P0: Printer, P1: Printer { func print(_ output: P1.Output, to input: inout P0.Input) throws { try self.p1.print(output, to: &input) try self.p0.print((), to: &input) } }

— 28:10

Now when we run the uncommentedLine printer we see that it has access to everything Prefix printed: Not's input: // let x = 1

— 28:18

In particular we see that Prefix printed a commented line, which means now the printer has all the information it needs to figure out if it should fail or not. We can simply run the upstream parser on this input, and if it succeeds we know we need to fail: extension Not: Printer where Upstream: Printer, Upstream.Output == Void { func print(_ output: (), to input: inout Upstream.Input) throws { var input = input do { try self.upstream.parse(&input) } catch { return } throw PrintingError() } }

— 29:17

Now when we try printing something that holds a commented line: input = "" try uncommentedLine.print("// let x = 1", to: &input) input

— 29:22

An error is thrown: Playground execution terminated: An error was thrown and was not caught: PrintingError()

— 29:26

And when printing a non-commented line it passes through just fine: input = "" try uncommentedLine.print("let x = 1", to: &input) input // "let x = 1"

— 29:31

So it seems that this little flip of the order in the zip printer has given our printers the ability to see what later printers do so that it can layer on additional logic. And in doing so we have also fixed the round-tripping property of the Not parser-printer, which is awesome.

— 30:01

Does this mean we should go flip the order in all of our zip printers? Well, it worked out quite well in this specific printer, but it turns out it’s still not fully baked. There’s a problem we aren’t seeing because the Not printer doesn’t actually do any printing, it just does validation.

— 30:16

If we run two printers that both do actual printing we will instantly see the problem: input = "" try ParsePrint { "Hello " Int.parser() } .print(42, to: &input) input // "42Hello "

— 30:42

This has printed the “Hello “ and the “42” in opposite order. This shouldn’t be too surprising because we flipped the order of the ZipVO printer so that the int printer runs first and then the “Hello “ printer.

— 30:53

So, what can be done about this? Well, recall that all of our printers have so far been implemented by appending content to the end of the input handed to us. That made since because input represented what all the previous printers had printed so far, and so we just needed to append to the end of it.

— 31:09

But now we are flipping things. Now input represents what all the following printers will have printed. So rather than append to the end of it, it sounds like we should prepend to the beginning of it. In fact, it seems like it was wrong for us to organize around an AppendableCollection protocol. Perhaps what we really need is a PrependableCollection protocol: protocol PrependableCollection: Collection { mutating func prepend<S: Sequence>(contentsOf newElements: S) where Element == S.Element }

— 31:38

It is going to take too much work to update everything to use this new protocol, so instead let’s temporarily just enlarge AppendableCollection ’s list of requirements to include a prepend method: protocol AppendableCollection: Collection { mutating func append<S: Sequence>(contentsOf newElements: S) where Element == S.Element mutating func prepend<S: Sequence>(contentsOf newElements: S) where Element == S.Element }

— 31:49

And once we get everything compiling we can rename AppendableCollection to PrependableCollection and remove the append requirement.

— 32:11

We can make Substring conform to this: extension Substring: AppendableCollection { mutating func prepend<S>(contentsOf newElements: S) where S: Sequence, Character == S.Element { self.insert(contentsOf: Array(newElements), at: self.startIndex) } }

— 32:53

But this implementation isn’t great. We’re doing the extra work of converting newElements to an array just to do the insertion, and further, because Substring isn’t a RandomAccessCollection , insert can be an expensive operation.

— 33:11

If instead, we can avoid this extra work by creating a new substring and appending to it twice. extension Substring: AppendableCollection { mutating func prepend<S>(contentsOf newElements: S) where S: Sequence, Character == S.Element { var result = ""[...] defer { self = result } result.append(contentsOf: newElements) result.append(contentsOf: self) } }

— 33:46

Note that we have decided to create an empty substring and append to it rather than using the insert(contentsOf:at:) method, and this is just for performance reasons. Appending is much faster than inserting.

— 33:49

Next we have UTF8View , which can simply call out to Substring.prepend : extension Substring.UTF8View: AppendableCollection { … mutating func prepend<S: Sequence>(contentsOf newElements: S) where String.UTF8View.Element == S.Element { var str = Substring(self) switch newElements { case let elements as Substring.UTF8View: str.prepend(contentsOf: Substring(elements)) default: str.prepend( contentsOf: Substring( decoding: Array(newElements), as: UTF8.self ) ) } self = str.utf8 } }

— 34:10

We can now update some of our printers to prepend content to the beginning of inputs rather than append. For example, the integer printer: extension Parsers.IntParser: Printer where Input: AppendableCollection { func print(_ output: Output, to input: inout Input) { // input.append(contentsOf: String(output).utf8) input.prepend(contentsOf: String(output).utf8) } }

— 34:23

And the string parser: extension String: Printer { func print(_ output: (), to input: inout Substring) { // input.append(contentsOf: self) input.prepend(contentsOf: self) } }

— 34:28

And with just those few changes our printer is now printing in the correct order: input = "" try ParsePrint { "Hello "; Int.parser() } .print(42, to: &input) input // "Hello 42"

— 34:45

So it seems we just have to rejigger our brains a little bit when it comes to printing. We should think of the input provided to us as everything that gets printed after what we currently want to print, and to print the output we should prepend its content to the beginning of the input. If we do that then our printers get some extra super powers that allow them to be even smarter about how they print.

— 35:09

Let’s quickly update all of our parsers. First we can just replace all instances of append(contentsOf:) with prepend(contentsOf:) .

— 35:28

And then we can update all conformances of Zip to the Printer protocol so that we print in the reverse order.

— 35:55

With just those few changes everything works exactly as it does before, but now we can beef up the logic of some of our printers so that they can better describe what they allow and what they don’t allow.

— 36:12

For example, the End printer can now force that the input be empty: extension End: Printer { func print(_ output: (), to input: inout Input) throws { guard input.isEmpty else { throw PrintingError() } } }

— 36:31

This effectively means that the End printer must be listed last in a parser builder context. In fact, this printer now fails to print: input = "" try ParsePrint { End() "Hello" } .print((), to: &input) input

— 36:55

Previously, before the zip ordering change, we had no choice but to make the End printer always succeed, and so it was not possible to catch situations like this.

— 37:11

In fact, the Rest printer conformance we wrote earlier is now magically correct, since it’s now checking the input that’s printed by the next parser, rather than previous one: extension Rest: Printer where Input: AppendableCollection { func print(_ output: Input, to input: inout Input) throws { guard !output.isEmpty, input.isEmpty else { throw PrintingError() } input.prepend(contentsOf: output) } }

— 37:21

And now non-sensical printers like this throw an error: input = "" try ParsePrint { Rest() Rest() } .print(("Hello", "World"), to: &input) input

— 37:33

It can only do this because the first Rest can see that the second Rest was going to print something and so it know it must fail.

— 37:43

So, incredibly, our simple flip of the semantics of running many printers has enabled us to implement the correct logic for End , Rest and Not so we now have even stronger guarantees that our massively composed parsers are working as we expect.

— 37:58

But, unfortunately this flip has caused some of our existing printers to now be incorrect. For example, our usage of users.print is now throwing an error: input = "" try users.print([ User(id: 1, name: "Blob", role: .admin), User(id: 2, name: "Blob, Esq.", role: .member), ], to: &input) input An error was thrown and was not caught: PrintingError()

— 38:13

It seems that some printer that makes up the users printer is now failing. It would be nice if we had some helpful error messaging to let us know what exactly went wrong, but we aren’t going to concentrate on printer errors right now.

— 38:26

Instead we can easily track down the error must be thrown in the Many printer because the user parser seems to work just fine, and the users parser is just a Many parser that makes use of the user parser.

— 38:44

Looking at the implementation of Many ’s print method we see what the problem is: func print( _ output: [Element.Output], to input: inout Element.Input ) throws { var firstElement = true for elementOutput in output { defer { firstElement = false } if !firstElement { try self.separator.print((), to: &input) } try self.element.print(elementOutput, to: &input) } try self.terminator.print((), to: &input) }

— 38:49

We run the element and separator printers for each value in the output array, and when it finishes we print the terminator. The terminator we are currently using is the End printer, which now verifies that the input is empty.

— 39:04

This printer is always going to fail because we have already run the element and separator printers, which means the input now has data in it, and so the empty check will never succeed.

— 39:19

Considering we have been flipping the order of operations for printers, maybe we should be running the terminator at the beginning of the print method rather than at the end: func print( _ output: [Element.Output], to input: inout Element.Input ) throws { try self.terminator.print((), to: &input) var firstElement = true for elementOutput in output { defer { firstElement = false } if !firstElement { try self.separator.print((), to: &input) } try self.element.print(elementOutput, to: &input) } }

— 39:32

Now things run without throwing an error, but the string printed is funny looking: 2, "Blob, Esq.", member 1, Blob, admin

— 39:37

It has printed the users in reverse order. This is because we are currently iterating over the array of outputs in order to print each one. Sounds like we also need to reverse the array before iterating over it: func print( _ output: [Element.Output], to input: inout Element.Input ) throws { try self.terminator.print((), to: &input) var firstElement = true for elementOutput in output.reversed() { defer { firstElement = false } if !firstElement { try self.separator.print((), to: &input) } try self.element.print(elementOutput, to: &input) } }

— 40:02

Now it prints correctly: 1, Blob, admin 2, "Blob, Esq.", member

— 40:08

So that was pretty straightforward, and now technically all of the parsers and printers in this playground work exactly as they did before, but there is one more printer that we created previously that can be strengthened thanks to the new powers our printers have been endowed with.

— 40:21

The Prefix printer seems simple enough, it just checks that the thing we are printing is satisfied by the predicate, and if it is it prepends that output to the beginning of the input: func print(_ output: Input, to input: inout Input) throws { guard output.allSatisfy(self.predicate!) else { throw PrintingError() } input.prepend(contentsOf: output) }

— 40:34

But now that input passed into this method represents what later printers have accomplished, we get the opportunity to strengthen this printer a bit.

— 40:41

To see the problem consider this seemingly innocuous parser-printer that consumes everything up to the next comma or newline, and then captures that comma or newline character using the First parser: try ParsePrint { Prefix { $0 != "," && $0 != "\n" } First() }

— 41:06

We haven’t made First a printer yet, but that’s easy enough to do. extension First: Printer where Input: AppendableCollection { func print(_ output: Input.Element, to input: inout Input) throws { input.prepend(contentsOf: [output]) } }

— 41:49

As a parser it is pretty straightforward: input = "Hello,World" try ParsePrint { Prefix { $0 != "," && $0 != "\n" } First() } .parse(&input) // ("Hello", ',') input // "World"

— 42:25

And as a printer it makes sense too: input = "" try ParsePrint { Prefix { $0 != "," && $0 != "\n" } First() } .print(("Hello", ","), to: &input) input // "Hello,"

— 42:48

The strange thing though is that we can feed data to the print method that is non-sensical. It can be data that could have never been output by the parser, such as if we wanted to print "Hello" and "!" : input = "" try ParsePrint { Prefix { $0 != "," && $0 != "\n" } First() } .print(("Hello", "!"), to: &input) input // "Hello!"

— 43:03

The printer has happily concatenated the strings together to form “Hello!”, but it also doesn’t make any sense. There is no string we could ever parse to produce a “Hello” string and a “!” string. The Prefix parser consumes everything until a comma or newline, and hence it would have also captured the “!”. It would never be left over.

— 43:23

To put it in very concrete terms why this printer is strange we only need to turn to the round-tripping property that we have used over and over in this series of episodes. If we try printing this erroneous data and then turn around and parse the printed string we are instantly faced with an error: input = "" try ParsePrint { Prefix { $0 != "," && $0 != "\n" } First() } .print(("Hello", "!"), to: &input) input try ParsePrint { Prefix { $0 != "," && $0 != "\n" } First() } .parse(input) error: unexpected input --> input:1:7 1 | Hello! | ^ expected element

— 43:48

This shows us that our Prefix printer is still not quite right.

— 43:51

Previously we would not have been able to implement this correctly, but now that the order of our parsers has been flipped we have access to what future printers are going to print. This means we can check the first character of the future input to see if it satisfies the predicate. If it does we can fail the printer because that means that somehow the Prefix didn’t consume everything it should have, which shouldn’t be possible: extension Prefix: Printer where Input: AppendableCollection { func print(_ output: Input, to input: inout Input) throws { guard input.isEmpty || !self.predicate!(input.first!) else { throw PrintingError() } guard output.allSatisfy(self.predicate!) else { throw PrintingError() } input.prepend(contentsOf: output) } }

— 45:05

Now everything still compiles and runs, but we are getting a PrintingError thrown down below: input = "" try ParsePrint { Prefix { $0 != "," && $0 != "\n" } First() } .print(("Hello", "!"), to: &input) input An error was thrown and was not caught: PrintingError()

— 45:18

This is now catching the non-sensical data we are feeding to the print. It knows it is impossible for the parse method to output a “Hello” string and “!” string, and so it has prevented printing entirely and thrown an error. This makes the printer just a little bit stronger in its guarantees, and we can be even more confident that once we construct a complex parser it behaves how we expect. Next time: the point

— 45:42

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.

— 45:59

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.

— 46:28

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.

— 46:50

Let’s try converting this parser to be a parser-printer, and along the way we are going to come across some really interesting challenges, and thinking through those challenges in detail should help you as you build out your own parser-printers…next time! References David Peterson 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. https://twitter.com/david_peterson 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 Sample code 0183-parser-printers-pt6 Point-Free A hub for advanced Swift programming. Brought to you by Brandon Williams and Stephen Celis . Content Become a member The Point-Free Way Beta previews Gifts Videos Collections Free clips Blog More About Us Community Slack Mastodon Twitter BlueSky GitHub Contact Us Privacy Policy © 2026 Point-Free, Inc. All rights are reserved for the videos and transcripts on this site. All other content is licensed under CC BY-NC-SA 4.0 , and the underlying source code to run this site is licensed under the MIT License .