Video #179: Invertible Parsing: The Solution, Part 1

Episode: Video #179 Date: Feb 28, 2022 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep179-invertible-parsing-the-solution-part-1

Description

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.

Video

Cloudflare Stream video ID: 9cb1c92ab8af43756e19dd33296d71e4 Local file: video_179_invertible-parsing-the-solution-part-1.mp4 *(download with --video 179)*

References

Transcript

— 0:05

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.

— 0:26

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.

— 0:41

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

— 0:59

Recall that parsers in our library are currently specified by a protocol with a single requirement: a parse method that turns an input value into an output value: public protocol Parser { associatedtype Input associatedtype Output func parse(_ input: inout Input) throws -> Output }

— 1:12

The input is marked as inout because the process of parsing can consume some bits from the input, and the function throws because parsing can fail to produce an output, such as if you tried to parse an integer from the string “Hello”.

— 1:24

Types conform to this protocol to expose the functionality of parsing. For example, the library conforms String to the Parser protocol to represent a parser that checks if the beginning of an input begins with a string, and if it does it consumes those characters, and if it does not it fails with a parsing error: extension String: Parser { @inlinable public func parse(_ input: inout Substring) throws { guard input.starts(with: self) else { throw ParsingError.expectedInput(String(self).debugDescription, at: input) } input.removeFirst(self.count) } }

— 2:02

We are going to follow this style for exploring printers. We want a protocol that expresses a printer type, which needs to essentially reverse the effects of parsing. In order to see what this “reversed” parser shape is supposed to look like, let’s take a deeper look at the current parser shape: parse: (inout Input) throws -> Output

— 2:31

The inout argument makes it ergonomic to consume the input because we can just mutate the input directly and we don’t have to return anything from the function.

— 2:40

Equivalently we could have modeled the parsing signature like this: parse: (Input) throws -> (Output, Input)

— 2:55

This says that to parse an Input we have to return the produced Output as well as a new Input that represents the rest of the input left to parse.

— 3:03

Implementing functions in this form is a lot less ergonomic than functions using inout because it is up to you to construct a whole new Input to return, and for large, complex Input types that can be quite onerous. Whereas with inout we can just mutate it directly.

— 3:19

What we are seeing here is that inout in Swift is essentially special syntactic sugar for making a common programming pattern more ergonomic. We often come across functions of the shape: (S) -> (S, A)

— 3:35

We’re seeing it here with parsers, we’ve seen it in the past with reducers , and we’ve even seen it with random number generators , which is something we discussed over 3 years ago on Point-Free.

— 3:44

Whenever we come across a function signature that has the same type on the left and right side of the arrow we have the opportunity to drop the type from the output at the cost of changing the input to an inout : (inout S) -> A

— 4:00

This is something to always be on the look out for. Whenever you see a function shape like (S) -> (S, A) you should strongly consider turning it into a (inout S) -> A shape.

— 4:14

So, now that we know the de-sugared parser signature is this: parse: (Input) throws -> (Output, Input)

— 4:19

Let’s reverse it in a very naive way: print: (Output, Input) throws -> Input

— 4:31

All we’ve done is literally just flip the direction of the function arrow.

— 4:35

This signature says that we have an output value we want to print, as well as a “rest” input, which represents what we have printed so far, and then we return a final printed input value. The idea of taking the “rest” input as an argument and returning a new input represents the idea of “incremental” printing, much like we had “incremental” parsing. Further, we are allowing printing to be failable, just like printing, which although we haven’t see an instance of this in our printers yet, we will soon see it is important.

— 5:17

Let’s now convert this function signature to something more ergonomic by switching back to Swift’s inout feature since Input appears on both the left and right side of the function arrow: print: (Output, inout Input) throws -> Void

— 5:35

We dropped the Input from the right side of the arrow at the cost of changing the Input argument to be inout , but since that was the only type on the right side, and because we need to return something, we have replaced it with Void .

— 5:44

So now this signature says that we are given an output we want to print, as well as an inout input that we want to print to, and we can throw to represent a failure of printing. This is really starting to feel similar to parsing, where instead of incrementally consuming bits from the beginning of an input we will be incrementally appending bits to the end of an input.

— 6:06

So, inspired by these findings we are going to define a Printer protocol like so: protocol Printer { associatedtype Input associatedtype Output func print(_ output: Output, to input: inout Input) throws }

— 6:26

Here we have called the inout argument to in order to mimic the print function in the standard library, which can incrementally print to a string or text output stream: print(<#items: Any...#>, to: &<#TextOutputStream#>)

— 6:50

Let’s take this for a spin. We can start naively by just creating an all new type to conform to the protocol, and inside its print method we will just accomplish some of the printing we did before in an ad-hoc fashion.

— 7:02

For example, we could create a UserPrinter : struct UserPrinter: Printer { func print(_ user: User, to input: inout String) throws { input.append( contentsOf: """ \(user.id), \ \(user.name.contains(",") ? "\"\(user.name)\"" : user.name))，\ \(user.admin) """ ) } }

— 7:43

In fact, since this printer doesn’t error at all we can drop the throws since non-throwing functions can fulfill throwing protocol requirements: struct UserPrinter: Printer { func print(_ user: User, to input: inout String) { … } }

— 7:54

And since the input we are printing to is inout , we can now break this up into multiple statements to make it a little nicer: struct UserPrinter: Printer { func print(_ user: User, to input: inout String) { input.append(contentsOf: "\(user.id), ") input.append( contentsOf: user.name.contains(",") ? "\"\(user.name)\"" : user.name ) input.append(contentsOf: "，\(user.admin)") } }

— 8:32

If we don’t like ternaries we could even do: struct UserPrinter: Printer { func print(_ user: User, to input: inout String) { input.append(contentsOf: "\(user.id), ") if user.name.contains(",") { input.append(contentsOf: "\"\(user.name)\"") } else { input.append(contentsOf: user.name) } input.append(contentsOf: "，\(user.admin)") } }

— 8:56

We haven’t accomplished too too much here. We mostly just moved code from one place to another, and then slightly improved the ergonomics of the code since we have an inout variable at our disposal that we can append to.

— 9:07

But we can keep going by next introducing a UsersPrinter type that calls down to the UserPrinter() under the hood: struct UsersPrinter: Printer { func print(_ users: [User], to input: inout String) { for user in users { UserPrinter().print(user, to: &input) input += "\n" } } }

— 9:51

However, this will print a trailing newline that we do not want, so we need to keep track of some mutable state to know when we actually want to include it: struct UsersPrinter: Printer { func print(_ output: [User], to input: inout String) { var firstElement = true for user in output { defer { firstElement = false } if !firstElement { input += "\n" } UserPrinter().print(user, to: &input) } } }

— 10:23

Now we have a users printer that is slightly more verbose than before, but also slightly more performant, as we no longer create that intermediate array and are instead appending to an inout value directly. And to make things weirder we are constructing a UserPrinter value just to get access to its print method and then entirely discarding of the value.

— 10:55

But, with that done we can make use of the printer to make sure it does the right thing: var inputString = "" UsersPrinter().print(output, to: &inputString) inputString // "1,Blob,true\n2,Blob Jr,false\n3,Blob Sr,true,4,"Blob, Esq.",true"

— 11:32

Looks like it did. It even quoted the “Blob, Esq.” field since it contains a comma. Also notice that we didn’t have to call .print with try even though the protocol requirement is throwing. This is because the Users parser didn’t throw, and Swift preserves that information.

— 11:50

However, this is not how we’d like to interact with printers, just as this is not how we interact with parsers. With parsers we very rarely construct all new types to conform to the Parser protocol, and instead we piece together existing parsers the library ships with using operators the library ships with. In fact, of the 15 complex parsers we create for the benchmarks of the repo we only create a few custom Parser conformances, and some of those should (and will) live in the library itself someday.

— 12:33

So, just as we described the users parser as a big parser comprising 4 smaller parsers, each of which comprise smaller parsers: let zeroOrOneSpace = OneOf { " "; "" } let field = OneOf { Parse { "\"" Prefix { $0 != "\"" }.map(String.init) "\"" } Prefix { $0 != "," }.map(String.init) } let user = Parse(User.init(id:name:admin:)) { Int.parser() Skip { "," zeroOrOneSpace } field Skip { "," zeroOrOneSpace } Bool.parser() } let users = Many { user } separator: { "\n" } terminator: { End() }

— 12:41

We would like the same to be true of printers. We should be able to construct a user and users printer by piecing together smaller printers that concentrate on just one small thing.

— 12:52

In fact, if we could somehow make all of these parsers also conform to the Printer protocol, then we would be able to magically call .print on users , pass it an array of users, and we should get back a comma-separated list of users in a textual format: users.print(output, to: &input)

— 13:30

This would mean that the users value simultaneously describes how to parse a string into an array of users and how to print an array of users into a string.

— 13:40

Even better, this single package would encapsulate all the subtleties and logic that guides the parsing and printing, so if we printed a user that contained a comma in their name, then the printed string would quote that field, but not any of the other fields: users.print( [ User(id: 1, name: "Blob", admin: true), User(id: 2, name: "Blob, Esq.", admin: true), ], to: &input ) Value of type ‘Many<Parse<User, Parsers.ZipOVOVO<FromUTF8View<Substring, Parsers.IntParser<Substring.UTF8View, Int>>, Skip<Parsers.ZipVV<String, OneOf<Parsers.OneOf2<String, String>>>>, OneOf<Parsers.OneOf2<Parse<String, Parsers.ZipVOV<String, Parsers.Map<Prefix<Substring>, String>, String>>, Parsers.Map<Prefix<Substring>, String>>>, Skip<Parsers.ZipVV<String, OneOf<Parsers.OneOf2<String, String>>>>, FromUTF8View<Substring, Parsers.BoolParser<Substring.UTF8View>>>>, [User], String>’ has no member ‘print’

— 13:54

Of course none of this works yet because users is composed of many, many parsers that are not yet printers. In fact, it looks like there are 13 parsers here: Many Parse Parsers.ZipOVOVO FromUTF8View Parsers.IntParser Skip Parsers.ZipVV OneOf Parsers.OneOf2 Parsers.ZipVOV Parsers.Map Prefix Parsers.BoolParser

— 14:19

Conforming parsers to printers

— 14:19

So, it should be as “easy” as simply making each of these parsers conform to the Printer protocol. But when we say “easy” we say it with big scare quotes around it. Most of these parsers are quite straightforward to turn into printers, but some take some mental gymnastics to figure out how to print, and others are just not possible to make into printers without some changes to the types.

— 14:39

Now, it’s a little intimidating to attack this huge list of parsers at once, so let’s first attack a smaller subset.

— 14:50

Let’s see what it takes to turn a smaller composed parser into a printer. The field parser looks like a good place to start: let field = OneOf { Parse { "\"" Prefix { $0 != "\"" } "\"" } Prefix { $0 != "," } } .map(String.init)

— 15:10

In fact, even this is a lot to bite off and chew all at once, so perhaps we should decompose it into smaller parsers, by say extracting a quoted field parser that tackles that problem on its own. let quotedField = Parse { "\"" Prefix { $0 != "\"" } "\"" } let field = OneOf { quotedField Prefix { $0 != "," } } .map(String.init)

— 15:21

If we try printing this parser we will see all the parsers that are lurking in the shadows: Parse { "\"" Prefix { $0 != "\"" }.map(String.init) "\"" } .print("Blob, Esq.") Value of type ‘Parse<Parsers.ZipVOV<String, Prefix<Substring>, String>, String>’ has no member ‘print’

— 15:34

This is a smaller list of parsers than the users parser is composed of, so let’s try making each of these parsers into a printer. String parser-printing

— 15:46

One of the simplest parsers being used right now is the string parser, which simply confirms that the input matches the string, and if it does it consumes those characters and succeeds, and otherwise it fails: Parse { "\"" // ⬅️ Prefix { $0 != "\"" }.map(String.init) "\"" // ⬅️ }

— 16:00

We accomplish this by making the String type conform to the Parser protocol: extension String: Parser { @inlinable public func parse(_ input: inout Substring) throws { guard input.starts(with: self) else { throw ParsingError.expectedInput( String(self).debugDescription, at: input ) } input.removeFirst(self.count) } }

— 16:07

And here we can see the logic it implements. It first checks if the input matches the string, throwing an error if it does not. And if it does, it consumes those characters from the string.

— 16:22

So, let’s try making this parser into a printer. We want to do the opposite of the work the printer is doing. We can start extending String to conform to the Printer protocol: extension String: Printer { }

— 16:37

And we can let Xcode fill in the stub of the print method to satisfy the protocol: extension String: Printer { func print(_ output: (), to input: inout Substring) throws { <#code#> } }

— 16:39

And in here we need to decide how we want to print. We are handed a Void value and an inout Substring . The Void value is here because the string parser is a Void parser in these sense that it doesn’t return anything of value. It either succeeds and consumes, or it fails.

— 16:54

So, to do the reverse of consuming from the beginning we can just append to the end of the input: extension String: Printer { func print(_ output: (), to input: inout Substring) throws { input.append(contentsOf: self) } }

— 17:09

We can even drop the throws since it cannot fail: extension String: Printer { func print(_ output: (), to input: inout Substring) { input.append(contentsOf: self) } }

— 17:13

And just like that we have our first reusable printer! And we can take it for a spin by asking a string, thought of as a printer, to print a void value: input = "" "Hello".print((), to: &input) input // "Hello"

— 18:02

Of course, this isn’t anything too impressive yet, but this is just the beginning. As we convert more and more parsers to be printers we will be able to print more and more complicated things.

— 18:12

Before moving onto the next parser to upgrade to a printer, let’s also remark on a very important property of our parser-printers. We’ve mentioned this before, but every time we write one of these printer implementations we should make sure that in some sense it roundtrips with the corresponding parser implementation.

— 18:28

We can do this round-tripping by making sure that if we start with an input, parse it, and then print it, we get back to the same input, and if we print a value and then parse it we should get back the same value: "Hello".print((), to: &input) input // "Hello" try "Hello".parse(&input) // () input // ""

— 19:09

It looks like our first parser-printer satisfies this condition. Prefix parser-printing

— 19:13

Let’s try another parser that our quoted field parser uses. Let’s see what it takes to make the Prefix parser into a Printer : Prefix { $0 != "\"" }

— 19:27

We can start by getting a stub in place for its Printer conformance: extension Prefix: Printer { func print(_ output: Input, to input: inout Input) throws { <#code#> } }

— 19:32

This method signature looks a little confusing because it says we want to print an output of type Input into something of type Input . The reason the argument label is output is because typically printers transform outputs into inputs since it goes in the opposite direction as parsers. However, recall that as a parser, Prefix will output the beginning of its input until a predicate is not satisfied, and so its output is the same type as its input. That’s why this argument is output: Input .

— 20:01

So, how do we implement this print method? We have two Input values, both are collections, and one is even inout . Since the parser functionality of Prefix consumes from the beginning of the input, perhaps the printer functionality should do the “opposite” by appending to the end of the input: extension Prefix: Printer { func print(_ output: Input, to input: inout Input) throws { input.append(contentsOf: output) } } Value of type ‘Input’ has no member ’append’

— 20:24

Unfortunately, the input does not have a .append(contentsOf:) method because Prefix ’s Input generic is just too generic to support such an operation. Right now it is just constrained to be any collection whose SubSequence is itself, which allows for performant mutations to the collection: public struct Prefix<Input>: Parser where Input: Collection, Input.SubSequence == Input { … }

— 20:45

And collections do not have an .append(contentsOf:) method. However, in our current situation we are not dealing with any collection. We are just dealing with Substring , which does have the append(contentsOf:) method. So, just temporarily, let’s overly constrain our Printer conformance so that it only works on inputs of Substring s: extension Prefix: Printer where Input == Substring { func print(_ output: Input, to input: inout Input) throws { input.append(contentsOf: output) } }

— 21:06

Now this compiles. But is this correct?

— 21:09

Our primary metric for whether or not a printer is correct is how it behaves when round-tripping it with the parser. So, if we parse an input and then print it, how does the newly formed input compare with the original? And conversely, if we print an output and then parse it, how does the newly formed output compare with the original?

— 21:27

Well, turns out our Prefix printer here acts a little strange in this regard. If we take a prefix of everything up until the first comma, and then print something with a comma: input = "" try Prefix { $0 != "," }.print("Blob, Esq.", to: &input) input // "Blob, Esq."

— 22:00

It will happily just append the entire “Blob, Esq.” string to the input. There’s no logic that determines if, when or how we print.

— 22:07

On the other hand, if we now take that same input that we printed, and feed it through the parser: try Prefix { $0 != "," }.parse(&input) // "Blob" input // ", Esq."

— 22:23

We see that the parser only consumed up to the comma and left the comma and everything after unconsumed. This is not a fully reversible roundtrip process. When we printed and then parsed we got something different from what we started from.

— 22:33

The reason for this is that our Prefix printer conformance does not reverse the effects of the parser conformance. We are just blindly appending the output without any additional logic. But the parser does have logic. It consumes everything from the beginning of the input while a predicate is satisfied. To undo this work with printing we could print all of the output to the input as long as all of its elements are satisfied by the predicate.

— 22:59

To do this we will add a guard to make sure the predicate is satisfied on the entire output that we are trying to print: extension Prefix: Printer where Input == Substring { func print(_ output: Input, to input: inout Input) throws { guard output.allSatisfy(self.predicate) else { throw <#???#> } input.append(contentsOf: output) } } Value of optional type ‘((Input.Element) -> Bool)?’ must be unwrapped to a value of type ’(Input.Element) -> Bool’

— 23:16

The predicate is held inside the Prefix type as optional for performance reasons. If you want to use Prefix without a predicate, like say to get the prefix via a count, then we can short-circuit the work of checking if the characters match a predicate. We should be dealing with this optionality in the correct way here, but to keep things simple and because our use of Prefix does use a predicate, we are just going to force unwrap it. extension Prefix: Printer where Input == Substring { func print(_ output: Input, to input: inout Input) throws { guard output.allSatisfy(self.predicate!) else { ??? } input.append(contentsOf: output) } }

— 23:46

If the entire output is not satisfied by the predicate then we need to fail. This is our first example of a printer failing, and to just get things compiling we can create a PrintingError to throw: struct PrintingError: Error {} extension Prefix: Printer where Input == Substring { func print(_ output: Input, to input: inout Input) throws { guard output.allSatisfy(self.predicate!) else { throw PrintingError() } input.append(contentsOf: output) } }

— 24:02

We are not going to focus a ton of the concept of printing errors right now like we did for parsing errors, but we will discuss it in the future.

— 24:08

This is a more correct Printer conformance for Prefix , one that takes into account the predicate. Now when we try our round-tripping code we immediately get caught on an error: input = "" try Prefix { $0 != "," }.print("Blob, Esq.", to: &input) input An error was thrown and was not caught: PrintingError()

— 24:19

Because it is not valid to use a prefix of characters not equal to a comma to print a string with a comma.

— 24:31

But, we can print strings that do not contain commas just fine: input = "" try Prefix { $0 != "," }.print("Blob Jr.", to: &input) input // "Blob Jr."

— 24:48

And if we change the prefix to instead look for quotes, we can then properly print strings with commas: input = "" try Prefix { $0 != "\"" }.print("Blob, Esq.", to: &input) input // "Blob, Esq."

— 25:01

This is very cool. The logic of whether or not this printer succeeds is baked into its fundamental definition. If you use Prefix with a predicate, then the only way to print something with it if is the predicate is satisfied on the entire value, just as when parsing with it it only consumes the parts that are satisfied by the predicate.

— 25:20

It’s worth noting that the prefix printing logic we just implemented is just a highly abstract, highly localized version of the ad hoc printing logic we were previously doing. When we tried printing the user long ago we inserted some gnarly logic to figure out if the name contains a comma in order to determine how we want to print: struct UserPrinter: Printer { func print(_ user: User, to input: inout String) { input.append(contentsOf: "\(user.id), ") if user.name.contains(",") { input.append(contentsOf: "\"\(user.name)\"") } else { input.append(contentsOf: user.name) } input.append(contentsOf: "，\(user.admin)") } }

— 25:38

It’s hard to see from this, but the shape of checking a predicate and then doing printing logic is exactly what the prefix printer does. We are just focusing our attention on tiny, minuscule printing problems that will soon be pieced together into large, complex printers. Parser-printer combinators

— 25:52

So, we have another printer under our belt. Nothing we have accomplished yet has been too impressive, and this last one in particular was a little head-trippy to wrap our minds around since we needed to think about it from the perspective of undoing the effects of parsing, but we are making some headway.

— 26:07

The way we will really start to unlock real power from printers is by creating “printer combinators”, meaning printers that use other printers to do their job. We should all be familiar with “parser combinators”, which are parsers that use other parsers to do their job. This includes things like the .map operator, the OneOf parser, and the .take / .skip operators which were recently refactored to use result builder syntax .

— 26:40

If we look back at the smaller parser we are concentrating on: let quotedField = Parse { "\"" Prefix { $0 != "\"" } "\"" }

— 26:45

There are actually 2 parser combinators lurking in the shadows here, but let’s take them one at a time.

— 26:49

First, there’s the Parse parser, which acts as our entry point into parser builder syntax. It’s just a top-level type that can be initialized by providing a closure, and then in that closure we are free to use parser builder syntax.

— 27:09

We can tell it’s a parser combinator because in its definition it holds onto a parser under the hood: public struct Parse<Parsers: Parser>: Parser { public let parsers: Parsers … }

— 27:16

And its parse method simply calls the .parse method on the parser it holds onto: @inlinable public func parse( _ input: inout Parsers.Input ) throws -> Parsers.Output { try self.parsers.parse(&input) }

— 27:23

This seems so simple that you may wonder why does this type need to exist at all? The main reason is for its initializer, which exposes a @ParserBuilder closure: public init(@ParserBuilder _ build: () -> Parsers) { self.parsers = build() }

— 27:34

Which is exactly what allows us to use the type like so: Parse { … }

— 27:39

It serves a similar purpose that the Group view does in SwiftUI, which is an entry point into view builder syntax: import SwiftUI Group { Text("Hello") Button("Tap") { } }

— 27:48

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

— 28:00

We need to somehow print the output value into the inout input value. We don’t know anything about these types, they are fully generic, so we have to look at what else we have access to in order to implement this method:

— 28:14

All we really have access to is self.parsers , which we know is a parser, and so has a parse method on it. That doesn’t help us because that transform is from input to output, and we need to go in the opposite direction of output to input.

— 28:43

In fact, this method is not possible to implement as it is currently stated. It’s just not reasonable to expect to make this type into a printer unless we know more about the Parsers generic.

— 28:57

So, just as Parse is made into a Parser when its generic is also a Parser , we will constrain the Printer conformance for when the generic is also a Printer : extension Parse: Printer where Parsers: Printer { func print( _ output: Parsers.Output, to input: inout Parsers.Input ) throws { <#code#> } }

— 29:11

This is a pattern we will see a bunch when turning parser combinators into printer combinators. We will invariably have to make all the parsers held onto by the combinator conditionally conform to the Printer protocol.

— 29:25

We now have a better shot at implementing this because self.parsers is a printer, and therefore has a .print method: extension Parse: Printer where Parsers: Printer { func print( _ output: Parsers.Output, to input: inout Parsers.Input ) throws { try self.parsers.print(output, to: &input) } }

— 29:37

And now it compiles.

— 29:40

We mentioned this briefly in our episodes on error messages, but it’s worth calling out again. Although print is marked as throws , it doesn’t actually throw. It only throws if the underlying self.parsers throws. Typically that means you can mark the function as rethrows : func print( _ output: Parsers.Output, to input: inout Parsers.Input ) rethrows { … }

— 30:02

This allows Swift to interpret print as non-throwing if self.parsers is not throwing, which can be very powerful. However, rethrowing functions cannot satisfy throwing requirements of protocols. Non-throwing functions can satisfy such requirements, but rethrowing cannot. There are discussions in the Swift forums to remedy this situation, and there’s experimental support for it in the compiler. In fact, some of Swift’s new concurrency tools even make use of this experimental tool, so hopefully everyone will get access to it soon.

— 30:30

Now that this is a printer we can take it for a spin. If we wrap any existing printer inside Parse we will get back another printer: input = "" try Parse { Prefix { $0 != "\"" } } .print("Blob, Esq.", to: &input) input // "Blob, Esq."

— 30:44

It of course doesn’t do anything too special because it’s just calls down to the printer it wraps, but at least we are getting more tools for building new printers from existing printers.

— 30:58

We are getting very close to turning this parser into a printer: Parse { "\"" Prefix { $0 != "\"" } "\"" } .print("Blob, Esq.") Referencing instance method ‘print’ on ‘Parse’ requires that ‘Parsers.ZipVOV<String, Prefix<Substring>, String>>’ conform to ‘Printer’

— 31:09

There is only one parser left to convert: something weird called Parsers.ZipVOV .

— 31:21

This Parsers.ZipVOV type is what our parser builders use under the hood. In previous episodes when we built up the theory of parser builders, we showed that we needed to create many, many overloads of buildBlock for handling a certain number of parsers listed in the builder closure, and for handling every combination of void and non-void parsers. These overloads explode exponentially in number based on the arity we support, and so they must be code generated, and hopefully some day soon Swift will have tools like variadic generics that will allow us to express this concept in a much simpler way.

— 31:58

But, when we released a new version of swift-parsing with parser builders support we decided to support up to 6 parsers in a builder closure, which means 127 overloads to support all combinations of void and non-void parsers up to arity 6. Under the hood those overloads construct a parser called Zip with a suffix appended that describes which of the contained parsers are void and which are non-void.

— 32:27

So, Parsers.ZipVOV represents a parser whose first and third parser is void, and the second output is non-void. We can go to its definition to see how it works: extension Parsers { public struct ZipVOV<P0: Parser, P1: Parser, P2: Parser>: Parser where P0.Input == P1.Input, P1.Input == P2.Input, P0.Output == Void, P2.Output == Void { public let p0: P0, p1: P1, p2: P2 @inlinable public init(_ p0: P0, _ p1: P1, _ p2: P2) { self.p0 = p0 self.p1 = p1 self.p2 = p2 } @inlinable public func parse( _ input: inout P0.Input ) rethrows -> P1.Output { do { try p0.parse(&input) let o1 = try p1.parse(&input) try p2.parse(&input) return (o1) } catch { throw ParsingError.wrap(error, at: input) } } } }

— 32:40

We can see that it’s a parser that wraps 3 other parsers, the first and third of which are void parsers, and its parse method simply runs one after the other, and if they all succeed it returns the output of the second parser.

— 32:59

Let’s see if we can turn this into a printer by somehow reversing the effects of parsing. We can start by getting a stub of a conformance into place: extension Parsers.ZipVOV: Printer { func print( _ output: P1.Output, to input: inout P0.Input ) throws { <#code#> } }

— 33:20

We need to somehow print P1.Output into a P0.Input value. The reason that we are only dealing with P1.Output is because P0 and P2 are both void parsers, and so their outputs are being ignored. And the reason we are only dealing with P0.Input is because P0 , P1 and P2 are all required to have the same type of input since that’s the only way we could run all the parsers together.

— 33:47

Just like the Parse type, this type cannot be made into a printer without some more information. We definitely at least need P0 , P1 and P2 to be printers: extension Parsers.ZipVOV: Printer where P0: Printer, P1: Printer, P2: Printer { … }

— 34:03

And then we can at least use each parser to print, and if any of them fail we can fail the entire printer. Remember that p0 and p1 are Void parsers, so we can just feed them void values to make them do their work: extension Parsers.ZipVOV: Printer where P0: Printer, P1: Printer, P2: 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) try self.p2.print((), to: &input) } }

— 34:36

And just like that we have implemented another printer combinator! This printer is capable of running 3 printers, one after another. input = "" try Parse { "\"" Prefix { $0 != "\"" } "\"" } .print("Blob, Esq.", to: &input) input // "\"Blob, Esq.\""

— 35:10

Amazingly this now compiles!

— 35:22

And we finally have our first printer that is doing something moderately interesting. In a single package we have simultaneously described how to parse a field from a quoted string, and how to print a string into a quoted field: let quotedField = Parse { "\"" Prefix { $0 != "\"" } "\"" } input = "" try quotedField.print("Blob, Esq.", to: &input) input // "\"Blob, Esq.\"" And everything round trips too: input = "" try quotedField.print("Blob, Esq.", to: &input) input // "\"Blob, Esq.\"" let parsedQuotedField = try quotedField.parse(&input) // "Blob, Esq." try quotedField.print(parsedQuotedField, to: &input) input // "\"Blob, Esq.\"" Parser-printer builder syntax

— 36:14

One thing that stands out looking at this new parser-printer is that its construction uses the Parse entry point: let quotedField = Parse { … }

— 36:24

But now quotedField is a parser and a printer. It would be cool if we could indicate that more obviously with something like: let quotedField = ParsePrint { … }

— 36:33

And luckily we can do that quite easily with a type alias: typealias ParsePrint<P: Parser & Printer> = Parse<P>

— 36:51

And now ParsePrint compiles! By having a dedicated ParsePrint entry point, it is not only more descriptive that we have a parser-printer, but it also forces the compiler to keep us in check before we try to call .print on it. Next time: more combinators

— 37:48

We are getting very close to having our first moderately complex printer.

— 38:03

We are now on the precipice of something really amazing. Let’s take a look at the field parser, which is responsible for first trying to parse a quoted field, and if that fails it just parses a regular field up until the next comma: 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 Sample code 0179-parser-printers-pt2 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 .