CoRecursive: Coding Stories - Tech Talk: Crafting Interpreters With Bob Nystrom

Episode Date: May 31, 2019

Bob Nystrom is the author of Crafting Interpreters. I speak with Nystrom about building a programming language and an interpreter implementation for it. We talk about parsing, the difference between compiler and interpreters and a lot more. If you are wondering why many languages have hand-rolled parser implementations yet much work on build language implementations focuses on parser and tokenizer generators then Bob's insights will be eye-opening. Also, if you've ever used regexes to pull strings apart into structured data, and I sure have, then Bob's perspective on the simplicity of hand-rolled parsers will certainly open up some new possibilities for you. Links: http://craftinginterpreters.com/ http://gameprogrammingpatterns.com/ http://journal.stuffwithstuff.com/

Hello, this is Adam Gordon-Bell. Join me as I learn about building software. This is Code Recursive. If you're working on a language that has real users, the error messages, the error handling strategy of your parser is like the main user interface of your language. So this is like what you think about all day, every day is error recovery, good error messages, graceful error handling. Because if you watch what a user does when

they're sitting at their IDE, more than half the time, the code is in a broken state. That was Bob Nystrom. He is going to teach us about an area of fundamental computer science, but in a practical way, building a language implementation. Bob is writing a book about building interpreters. And today he walks us through the process for building our own programming language and language implementation. If you don't intend to build your own programming language, the skills and tricks that language authors use

to parse unstructured texts into a form that can be executed, it really comes up all the time in day-to-day programming. And if you find yourself reaching for regex a lot, I think that this knowledge will be quite helpful. Today, I'm speaking with Bob Nystrom, author of Crafting Interpreters. Bob, let's talk about interpreters. Oh, boys, my favorite subject. So I always start off with kind of these definitions to kind of get the context for things. I think it's going to be challenging in this case. So like, what's an interpreter?

Oh, man. So we can have the 30 second conversation about that, the five minute or maybe the three hour conversation. I actually spent a decent amount of time in one of the intro chapters of the book trying to come up with a good answer for what is a compiler and what is an interpreter. And I'm still not entirely satisfied with the answer. I think the short answer is an interpreter is a program where if you throw some source code at it, it will run it. I think that's probably the best one sentence answer I can give. How does that sound? That's a good definition. So then what is a compiler then something where, well, define a compiler in comparison, maybe. What do you think?

That's the harder question. And, you know, one of the things that's kind of tricky about this is because we're programmers and we tend to like things being black and white, we like really crisp definitions for things, right? And it's important to have canonical definitions because that's how we communicate with each other, right? If I use a word and you think it means something different, then we're not effectively sharing information. So there's this goal of clarity, but at the same time, our industry is getting older and naturally words change in meaning over time, right? So if you ask what a compiler means, you know, I think you'll get different answers if you ask different people and you'll get different answers over time. And that doesn't mean that those answers are wrong. It just means the word gets harder to use effectively. But, you know, the

sort of the pragmatic kind of informal answer is that people think of some kinds of programming language implementations as being compilers and some kinds of them as being interpreters. And I think there are a bunch of them that people have rough consensus on. Like if you ask a bunch of people, is GCC a compiler? They'll say yes. And if you ask a bunch of them that people have rough consensus on. Like if you ask a bunch of people, is GCC a compiler, they'll say yes. And if you ask a bunch of them, if Python is an interpreter, most of them will probably say yes. But then it starts to get more interesting, right? So one way to look at it is there's the sort of user experience answer, which is that a

compiler is a tool that takes some source code and turns it into another form, but doesn't actually run it, right? So if you have some code that says print hello world, a compiler is not going to put hello world on screen. It's going to produce some other output file that then you could use to put hello world on screen, but it won't do it itself. Whereas an interpreter will, right? Like maybe that's one way to sort of think of the distinction between the two. So it's like an interpreter has two steps or a compiler is just the first step and then it has to additionally be run sort of in the simplest form. Right. Or another way to think of it is those two steps exist, but in a

compiler, the developer sees them explicitly, whereas with an interpreter, they're both sort of bundled up together, right? So what would you say is the benefit to writing an interpreter or just a language implementation? You're writing a book about doing this. So I assume you think it's important. I don't know about important. I'm not the kind of person who thinks about things at that level a lot. The short answer is like, I just think programming languages are super cool, right? Who wouldn't want to make a programming language? It's awesome. Super fun. You know, to some degree, like one of the things that one of the categories of software that I find most rewarding is ones where I write a program of some finite length and it can do a combinatorial number of interesting things. Right. You know, if you think about so I was listening to the interview you did with James Buck a little while ago and maze generators are a good example of that.

Right. You know, you write this little hundred line program and it can generate an infinite number of mazes. And that feels like the sort of exponential power amplification, right? And programming languages are like that, right? You know, so you write an interpreter, maybe it's a thousand lines of code and you can throw an infinite number of programs at it and it can interpret all of them. And that's like a really cool sensation, right? Yeah. You know, so one answer is just like, there's like cool software, right? And they avoid kind of like a lot of the grungy stuff about programming. Like if you want to make a, you know, like a web app or something, you know, 90% of your job is just like looking up stuff on Stack Overflow and like dealing with like cruddy APIs. And like, it's just kind of like taping stuff together. And it's not super intellectually rewarding, right? Whereas if you're implementing a programming language, it doesn't actually touch the outside world very much. It's mostly like it just needs a string of input and, you know, maybe it produces a string of output or print some stuff to standard out. But then there's this big ball of code that you get to write in the middle. So you spend most of

your time kind of mentally focused on the interesting parts of the problem and the domain, which is kind of nice in terms of like, sort of, is this a fun kind of code to work on it? It's kind of fun in that sense, right? Yeah. And it's like working from first principles, like you're not, when I build a CRUD web app, I guess, like, I don't know, databases and web servers do a lot of the heavy lifting, right? And I'm just writing the glue. Yeah. And to some degree, that's good, right? Because it means you're effective. You know, you don't have to, you're really hard to make a web app if you had to like build your own database engine from scratch every time. But if you're a sort of bottom up thinker, and you're interested in like what's really going on under the hood, then programming at that level maybe isn't quite

as satisfying. Yeah. So in your book, you build this programming language called locks. What libraries do you use to build that? None. So one of the main conceits of the book, if you were a programmer, you were a consumer of languages. So they're relevant to your life, but they have a sort of reputation for being, you know, kind of mystifying, opaque, you know, something like, oh, you know, programming language people, those are different kind of people, they have these special skills, and can be kind of intimidating. So one of my goals of the book is to sort of demystify that and to make it more approachable and say like, yeah, this is, these are just programs. They're

just written in some code and they take in text and they output text and like, there's not any real magic going on there. And my goal is like, there's a sort of meta goal here, which is like, hopefully I can make people feel a little more confident and courageous in their ability to understand things, even things that seem intimidating or unapproachable at first. So that's kind of like the conceit of the book. And in order to make that tangible, the structure of the book is it shows you every single line of code in two complete interpreter implementations. And it doesn't defer to any compiler compilers or third-party libraries or anything. So we use the Java standard library, Ar know, ArrayList and HashMap. We use

the C standard library, which is nothing, printf. And that's it. And then, you know, I walk you through every single line of code. And it's not actually that much, which is kind of interesting, right? Like you can actually build a fairly full featured interpreter in just like, I think there, I think each of them is under 2000 lines of code. Oh, wow. Yeah, it's pretty cool, right? And I think it's a cool lesson to show that like, yeah, this is how simple they can be, right? I mean, it's a really simple language. And in particular, it has a really limited core library, right?

Like it can print and that's about all it can do. And that stuff tends to be a lot of the surface area of a language implementation. But in terms of language features, it's fairly full feature, right? Like it has a complete syntax. It has like infix operators, operator precedents, statements, control flow, function calls, recursion, classes, single inheritance, super calls, fields, methods, closures, full lexical scope. It's kind of semantically pretty close to JavaScript, except class-based instead of

prototype-based. So it is a real language, and it doesn't actually take that much code to implement one, which is kind of interesting. That is interesting, and it sounds like it has more features than at least most JavaScript until recently lacked. Yeah, it's a strictly smaller language than JavaScript, but JavaScript has a reputation for seeming small because there's this perception that prototypes

are conceptually simpler than classes. There isn't really complexity-wise that much difference between the two. So the fact that locks has classes doesn't really make it much bigger than JavaScript. And JavaScript has like just a lot of stuff, especially that, you know, over the past few years that it's accreted over time, you can think of locks as sort of like a toy JavaScript, maybe. Okay. Why did you choose something JavaScript ask as your language to build an implementation for? It's sort of coincidental. So syntactically, I wanted something in kind of the C tradition, so curly braces and semicolons, just to, one, to have something fairly familiar and approachable.

Because if I'm teaching someone how to write an interpreter for the first time, how to write their own parser and stuff, which they've never done before, I don't want to also force them to learn a new style of syntax, right? And I didn't want to do something Elisp-like syntax because one of the things that I think is interesting to talk about is how do you write a parser for a language that actually does have rich syntax and operator precedence and stuff like that? So in school, I took a course that was on compilers or whatever. We had the Dragon Book. And our big final project was translating

scheme into Java. Yeah. Like I get what you're saying because something with S expressions, it seems like cheating because it's already kind of parsed. Yeah. I mean, you still, you know, you technically have to still write a scanner and a parser, but it's almost trivial. Right. And in some areas, that's a totally good trade-off to make. If the interesting things you're trying to present to someone are not around syntax and parsing, then it's like, yeah, what's the minimal amount of syntax and parsing we can do to get to the stuff we care about, which, you know, in your class is code generation and semantics and things like that. But for me, if I'm trying to get someone to understand how does an actual programming

language work, most of the languages they use do have syntax, do have more complicated syntax. So they won't understand how that works unless I show them a parser that can handle that kind of syntax, right? Yeah. I like this approach. Very pragmatic. So where do we start? So we start with a string of, or a file of text and then what do we do? Yeah. So we basically move front to back. So you, you start with a string and it's literally just a, And then what do we do? it. They call it scanning and lexing. Basically, you can think of it as taking a string of letters and turning it into a string of words, right? So you end up with something that's still linear, it's still a sequence, but it's been kind of chunked together. So maybe you start with the characters VAR, and what you end up with is a single token that represents the keyword var,

right? Things like punctuation, you know, parentheses become single character tokens, things like identifiers and keywords become tokens that have multiple characters within them. So then what you're left with is you have this string of tokens, right? So this is kind of your words. The next phase of that is parsing. So if you've done, you know, kind of depending on how your English education was, there used to be a thing where people were taught how to diagram sentences. Oh, I hated that. It never made sense to me. Well, if I got the book for you. So diagramming sentences is basically what a parser does, right?

So it takes a series of words and it says, okay, there's actually this tree-like grammatical structure in there. And what a parser does is it builds that tree. So for example, if the tokens you get are a one token followed by a plus token followed by a two token, the scanner doesn't know that there's any relationship between those. Right. But the parser will say, OK, that's an addition where the plus is the operator and one and two are the two operands, the children of that addition tree node. Right. So the parser does that to your entire program and turns it into or or at least, you know, each source file individually and builds a big tree out of it. You know, you have statements that contain keywords and expressions. Expressions may contain sub-expressions all the way down to the leaves. And the leaves are little things like the, you know, literals, numbers, variables, stuff like

that. So that's your parser. So you get this sort of grammatical structure out of it. So you know how things are nested and how things relate to each other, but you don't actually know what anything means, right? So if you have, you know, if you have an expression that's like A plus B, you know, you're adding A and B, but you don't actually know what A and B are. You don't even know what they refer to. To make sure I'm following. So we start with a string of just characters. So we have var x equals seven, and then we turn that into like token so a token var a token x token equals token seven and then we turn this into a tree so what our tree look like so that tree is going to say okay the root node is a variable declaration statement and the name child node of that variable

declaration is going to be x and the initializer expression node is going to be X. And the initializer expression node is going to be seven, which is a integer literal expression node. It ends up kind of blowing up into something that feels like kind of verbose and legalese, right? Because you have, you're tracking not just the pieces of everything now, but what they represent in the grammar and how they kind of relate to each other. That makes sense. Yeah. So that's what the parser does. And then either after that or during that, there's a resolution process, which is where you start figuring out how different parts of the program refer to each other. So if you see an expression that mentioned some variable A during resolution, that means you go and you find the syntax for a variable declaration

where a variable named A was being declared and you say, okay, you know, I understand the scoping rules of the language. So now I know that this a expression is referring to that a declaration. So that's the point where you kind of, you start to get some actual semantics, right? You start to know what the program means. So I have that var x equals seven. And then if I have something else that says like Y equals X plus seven, then somehow I link those two in the tree or did I lose the plot? Yeah.

So if you imagine thinking about it at the starting at the very top level in like a scripting language, a program is like a series of statements. So then the root node of your program is going to be like this program node and it will have this list of child statement nodes. Right. And they you sort of walk them one after the other. So you'll have one of those statement nodes may be a variable declaration for var x equals seven.

You may have another one for var y equals three. Maybe you'll have another statement that's like print x. And then during resolution, you're walking those statements in order and you're keeping track of scopes as blocks begin and end. And then when you walk down that tree into expressions and you start finding variable references you can sort of look back at the variable declarations that you've already seen and said okay well i did see

a declaration for x before so i know that this x expression now is referring to that one that makes sense i was thinking like maybe this is not this is why i'm not a language designer like my implementation would be like just some hash map that I carried around and I just threw things in it. Maybe I put some sort of key on the front for like scoping. Yeah. So your intuition is exactly right. So the way that you do resolution is you build this thing called a symbol table and it's

exactly what you say. So you, it's a hash table that is keeping track of the variables that have been declared that are currently in scope. So actually, in a lot of implementations, what you do is you do a stack of hash tables because you have nested block scopes, right? So you get a hash table for each scope, and then you stack them up as you get into inner scopes. So the way it works is, you know, during resolution, you're walking through the tree that the parser produced. And each time you get to a variable declaration, you take that variable name and you add it to the hash table. And you say, OK, now I know that that variable exists. When you reach the open curly brace of a new block, you push a new empty hash table onto that stack because now you're in a new scope.

When you get to the right curly brace, you pop that hash table off because now all of those variables have gone out of scope and they don't exist anymore. And then whenever you find a variable expression node, you just look up in that stack of hash tables. You say, okay, can I find a key with that name? And if so, then that variable exists and it's in scope. And then you, you know, there's interesting questions around what are the values in that hash table represent? Do they point to declarations? That kind of depends on what your implementation is trying to do. But in general, yeah, you have this stack of hash tables and that kind of represents the language's understanding of the scope and the declarations that are available at any point in time.

One thing I like about getting in there and understanding this kind of parsing and evaluation step is I feel like it gives some intuition for, I don't know, aspects of languages that are like as a result of their implementation. I think you mentioned in your book, like I'm thinking of like Turbo Pascal. I think it is. You have to declare all your variables at the top. This probably has to do with how they kind of build this tree of state, right? Or this stack of... Yeah, it's exactly right. And it's actually kind of an interesting historical artifact too, right? Because you're building a compiler or an interpreter, you know, when you refer to a variable, you need to be able to figure out which declaration that variable refers to, right? Especially if it's a statically typed language, because you need to know the type of

that variable to know what to do with it, to know how to generate code for accessing it, or even to be able to interpret it at runtime, right? So the easiest way to make sure that that always happens is that the declarations always come before the uses of the variables, right? And for local variables, we sort of take for granted because if you use a local variable before it's declared, it doesn't have a value anyway. So the language forbids that. But it's a little more interesting to think about function calls, right? So, you know, we definitely do take advantage of recursion and we take advantage of mutual recursion, right? So you can have a function A that calls some other function B and under some circumstances B may call back to A, right? Something that we use fairly frequently,

but if you think about what the compiler has to do, you know, so it will be processing the body of that A function and it's going to see a call to B, and it hasn't processed B yet, it hasn't reached the declaration of the definition of B. And you can't move B first, because then you would get the exact same problem in the other direction, because the body of B refers to a right. So there's this question of like, you know, how does the language implementation handle this? And, you know, we kind of take for granted now that languages like JavaScript and Python and Java, this just works, right? So in Java, you can have a bunch of methods in a class and you don't have to think about the order that those methods appear at all, right? Because Java just makes it work and they can call each other freely and everything's

fine. The way that that works under the hood is when Java is doing resolution, it's a two-stage process, right? So it parses the whole file and it walks at once, finds all the declarations for the methods, and it keeps track of everything it needs to know about the existence of those methods. But it doesn't step into their bodies yet. It just says, okay, I know that there's this method and here's the parameters it takes. And then it walks through it again and then goes into the bodies. And then it can start actually compiling calls to those methods. And now that it knows every method already, it can compile a call to any of them. So recursion just is totally fine and everything's fine. It makes me think of like code style. Like some people will, let's say Java, they'll write their Java with all of the kind of

like helper private things at the top. And then like the thing that calls it at the bottom. And I, I kind of prefer the opposite where it's kind of like a top down where, you know, the first thing you see is kind of the top level thing, but this bottom up style, I think is just, opposite where it's kind of like a top-down where, you know, the first thing you see is kind of the top-level thing. But this bottom-up style, I think, is just because of what you're describing. Like, from languages where you needed to declare things before you could call them. Right. So, historically, we take for granted that Java can do that now because it's like, yeah, it's fine. Just parse the whole file and then walk it twice, right? No big deal. But if you were, you know, Nicholas Vert in the 70s writing a Pascal compiler, the computer that it was running on literally didn't have enough memory to hold the entire source file that you're compiling. So you couldn't walk the whole

file multiple times. Or if you did, you would have to actually reparse it multiple times, which is really computationally slow. So C and Pascal and a lot of other languages from the time were designed such that you had to, you could only call functions whose definition or declaration you had already seen, right? So that's why Pascal forces you to put all the types first and then all the variables and then the code that uses the variables, because it ensures that everything the compiler needs to know, it will have seen before it needs to know it. That's why in C you have explicit forward declaration. So anytime you want to do recursion in C, you have to do this, the separate syntax that says, here's the function, I'm not giving you the body, I'm just going to tell you the structure of it. So that the compiler sees that before it calls and compiles any calls to it, right? And it's purely just like a historical

artifact, which is like, we just didn't have enough memory, right? But then there is a sort of cultural effect, right? Because you do see some programmers, they kind of naturally order their functions in bottom up order versus top down order. And a lot of the ones who kind of do it in bottom-up order are older programmers coming from C where that's sort of the way you do it because you don't want to make unnecessary forward declarations, right? So you want to make sure that your helpers are first so that they're fully defined before you compile a call to it. And it's weird that that kind of, you know, this sort of like hardware limitation kind of lingers on in the culture, right?

Yeah. And if nobody rethinks it, this cultural aspect can travel forward in time way past when it's necessary. It's interesting. Yeah. We need a anthropologist or something. simultaneously working on a minor in sociology. And that whole side of things is like super fascinating to me, like how programming culture is built and how it's shared over time and changes over time, I think is super fascinating. If there was a job for being like a programming language anthropologist or something, that would be the career for me. Nice. You can make it happen. Let's make it happen. Yeah, maybe I should.

So I don't want to totally skip over parsing. As I said, I did this class back in university. It's been a long time. But what I recall is that we use some sort of like parser generator where we... Yeah, you probably used Yak or Flex, maybe Bison. Yeah. I don't even know which one. But my question is, why aren't you using a parser generator? So, yeah. So, there's a couple pieces to to that. So one of them is if we do use one and the reader doesn't know how that tool works, they may be left feeling that there's still some magic where they're like, yeah, I kind of understand this, but like I couldn't have written that tool myself. So I still really don't know what's going on. I'm still

obligated to rely on someone else's expertise to understand how a language works. So I wanted to make sure that it didn't have that problem, which is kind of the philosophical reason. The pragmatic reason, strangely, a lot of culture around parsers and a lot of cultural amount of math envy in the PL community. So the ideal programming language paper lets you prove things about a programming language. So they really like, you know, when they do parsers, they really like formalisms. And that also sort of leads them in a direction of they like parser generators because they say, okay, well, I can prove that I can write a tool that will correctly parse grammars of this nature. Then everyone will just use that tool and everything's better. And I've demonstrated something universal about grammars maybe. So in academia, parser generators are really popular. And if you read the Dragon Book,

if you read compilers, principles, practices, and tools, something like that, if you read the Dragon Book, a big chunk of it when it's talking about parsing is talking about parser generators and the discoveries they made about what you can prove about certain classes of grammars, and then taking those discoveries and then showing how you can use those to make your own parser generator. So that's a big thing in academia, right? I think that I skipped an important part of this, which is I should define a parser generator. Oh, sorry. Yes. So parser generator is a piece of software where you give it a textual description of your language's grammar, and it will spit out a chunk of code that is an implementation of a parser for that language, which is a sort of weird kind of meta

thing to think about, right? Because then the parser generator is also a parser because you're giving it this grammar specification that is itself a text file. So then you're like, how do you write your parser generator? I never thought of that. So it emits a program that given your string will produce the tree. Right, exactly right. So, and then you can think of it as a, it's basically a domain specific language for parsers. So these grammars are written in kind of a high-level declarative language, and then it spits out an imperative parser for you in C or Java, whatever your implementation language is. So you can do that. You can use one of these parser tools, and then all you have to do is write down your grammar,

and it will give you a parser implementation for you. Or you can hand-roll your parser. You just write the imperative code yourself by hand. So in the book, we hand-roll the parser. We don't use a parser generator. The part of it is because I don't want people to think that, okay, well, the parser generator is magic. So I still don't know what's going on. But also part of it is that if you look at language implementations that people actually use, most of those, in fact, do have hand rolled parsers. So, you know, when you're learning about programming languages, you're usually learning

about it from material coming out of academia, right? You're learning about it through textbooks and stuff like that. They all tell you, like, obviously you should be using a parser generator. Parser generators are way better. And that is kind of the dominant trend in academia. But meanwhile, over in industry, you know, these people are not writing books, but they're like, actually, we just hand rolled our parser. And that's kind of what they do, right? I like hand rolled parsers. I think they're kind of cool. So, you know, my book is focused on like, if you want to understand how the languages you actually use are implemented,

or if you're likely to build one yourself that is similar to how people write them, a hand-rolled parser is actually what you're most likely to do. So this is the real world implementation or a form of it. Yeah. I feel like I'm kind of slagging off on academia here.

There are really, the fact that parser generators exist is really cool. The technology behind them is really interesting. The algorithms are interesting. And there are a lot of good things about using them, right? So it's the exact reason why all declarative languages are useful, right? In that they let you express your intent at a higher level and they save you from doing a bunch of grungy work, right? So there are, you know, parser generators are cool. It's worth exploring them. But for the book, you know, I sort of think of them as non-essential and they weren't on the critical path of me getting you to understand every bit of how a language implementation works. Yeah. If you're going to build your own language and it's a learning exercise,

it's helpful to do it yourself. I think what you're saying is on the other end of the spectrum, if this is a real deal, programmers are going to use this everyday language, then maybe there's performance gains or optimizations or something that a hand rolled. Yeah. So there are pragmatic reasons to want to hand roll your parser. So they can be kind of more of a chore to maintain because you're handwriting them in a lower level. So it's kind of more tedious, but in return for that performance questions are a little hard to answer, but I think in general they can be fast and fast enough but in particular what you find is that hand-rolled parsers it's much easier to have high quality error handling so there are parser generators that can kind of do that okay but a lot of times like with just a typical parser generator if you

don't put a lot of effort into it the parser you get out of it if the user types in code that has a mistake will just give you some impenetrable error and you know if you don't put a lot of effort into it, the parser you get out of it, if the user types in code that has a mistake, will just give you some impenetrable error. And if you're just trying to write a really simple language implementation so that you can prove some other properties or say something interesting about programming language theory, that doesn't matter because you're not super interested in incorrect code anyway.

But if you're working on a language that has real users, the error messages, the error handling strategy of your parser is like the main user interface of your language, right? So this is like what you think about all day every day is error recovery, good error messages, graceful error handling. Because if you watch what a user does when they're sitting at their IDE, more than half the time, the code is in a broken state, right? They're in the middle of typing stuff. They make mistakes. So error handling is like a huge part of the job. And if you hand roll your parser, that's all your code.

So you can put whatever little weird error handling edge cases in there that you need to without any problems. Whereas if you're relying on code that's generated from a parser generator, it's harder to kind of put that stuff in there. In your language, I forget how many lines you said it was. Like how much of it is parsing? Is that a bulk of it or a small amount? No, it's not the bulk of it.

Like a hand-rolled recursive descent parser, which is the strategy we use for most of the parsers, is actually fairly straightforward. There's not too much overhead. I could, if you want to, you know, listen to me click around, I could even get the line count, but it's not the majority of the code base. It's one of the things that I found kind of interesting because, you know, when I was first getting into programming

languages, parsing is kind of intimidating because, you know, you read the literature and they spend a lot of time talking about it. So it makes it seem like, man, parsing is like a really big deal, right? Like there's like all these formalisms, they're talking about like LRK, LLK, LALR, and like there's like, they made all these tools to automate it for you. And it's just like, man, this has got to be like heavy stuff. But then, you know, you learn about recursive descent, which is kind of the main, kind of the simplest way to hand roll a parser. And it's just like, it's just imperative code for, you know, that basically looks like if you take the textual description of the grammar, which is, you know, you could say like an if statement starts with the keyword if, and then a left parenthesis, and then there's a condition expression. A recursive descent parser

is basically just that in imperative code, where you say, look for the if keyword, look for the left parenthesis, parse a condition expression. So there's not really that much to it. But for some reason, you know, I think the reason that there's a lot of focus on it in academia was just because there were a lot of fruitful things that they could research about it. But in terms of like, is it particularly difficult or important when you're making your language implementation today? It's like, no, it's kind of a thing you just do. I have a related story. So I was reading your book and another one. And then I had a ticket at work to basically look at what Python libraries have CVEs, like security issues. So there's like a GitHub project that's crowdsourced.

It'll basically give you a string that says if it's greater than or equal to version 1.07, but not less than 2, or if it starts with 3.0x so i had to basically determine if a library meets that rule and therefore you know it has a security condition yeah and i had done this in the past and uh it was kind of with big hairy regexes i guess like you kind of make some assumptions about the format so i ended up building this parser and it worked well it's actually not that complicated. I'm going to agree with you. Awesome. That's good to hear. Yeah. I went through the same phase when I was first learning programming languages too, where I'm like, I need to take this string and break it into pieces. Obviously I'm going to use regex and that gets you far enough to get yourself

into the weeds, right? So for really simple things that works, but once you get to something that starts to feel like real sort of nested expressions, then you kind of hit a wall and then it feels really difficult. And then you have this mentality of like parsing must be really hard because all of a sudden this got way more difficult. Right. But I think a lot of it is like, it's just that you hit the point where regex isn't the right technique. And if you don't know what technique to use instead, then the difficulty ramps up. But once you sort of wrap your head around a straightforward like scanner and a simple like prep parser or recursive descent parser you're like okay i know what to do now when i'm presented with a problem like this right like

and then you just use that technique yeah i think the tricky thing is taking this list of tokens and then turning that into a tree and especially when the tree basically precedence rules are complicated is what i would say yeah yeah and this is like it is a little. Like once you learn a couple of techniques and you sort of wrap your head around it and you're like, okay, it's not too bad, but it is difficult, especially at first, right? Because one it's recursive, right? You know, you have your parsing and arithmetic expression and some of the sub expressions are also arithmetic expressions and recursion itself is like hard for people to wrap their heads around, right? It takes a while to learn it. And the other thing is like, it was hard, right? Like if you go back and like the old, like early computer science literature, when they were building their first compilers, you know,

famous people that have Wikipedia articles, they struggled with this stuff too, right? Because it was like totally new to them. Like it's new to us now. And it turns out like it is difficult if you don't have those techniques, right? Like, and they, you know, it was even harder for them because they had to invent the techniques, but like, it is pretty if you don't have those techniques, right? Like, and they, you know, it was even harder for them because they had to invent the techniques, but like, it is pretty difficult to sort of wrap your head around, you know, you're stepping through this line of tokens one at a time, but you're trying to build up a tree that you don't know what the tree is going to be. Like it is kind of a weird thing to kind of wrap your head around.

Totally. That's why in this thing that I'm describing, there is actually a comment with a link to a blog post that you wrote. Hopefully some future me will know what it means. But it's such a cool feeling when you find those techniques, right? Where it's like, oh, yeah, once you have the mental model, then it's like, oh, I can solve this. I can solve an entire class of problems now. And it feels like you just grew another appendage or something, right? And especially if you've really tried to sort of meander your way through it without that technique. So you

really feel the pain of not knowing how to solve it. Then once you get that, you know, you learn that one trick and then you're like, Oh wow, I can, I can do this thing. It's a really cool sensation. Yeah. That makes me think of, there was like this blog post series way back with Ron Jeffries, and he was trying to make a Sudoku solver. And it's just hard. Yeah. And so he wrote 10 articles and then never got a solution. And then I'm trying to think of the other guy's name. Anyway, somebody else was familiar with constraint propagation.

It's just a way to kind of track and kind of find the, you know, a solution that works. And like they just had a hundred line Python solution, you know? But it's not that they were a genius. It's that they knew, hey, there's this class of problems and this fits within it. Yeah. They had the right tool, right? Yeah. So how did you get started on building programming languages? Oh man, it's an interesting question because I think the answer that I've given has changed

over time, even though the history hasn't. So the usual anecdote I give is that my oldest daughter had just been born. So I had a chunk of paternity leave. And I also had some vacation time at the same time. So I was like off work for a big chunk of time. And we were on this weird schedule where like my daughter was waking up in the middle of the night a lot. So I would just take all the nighttime feedings. And then my wife would get the daytime feedings. And I was basically on the night shift. So I was just nocturnal for like a month or so. And I had a lot of downtime while she was sleeping. So I was like, okay, well I need something to do. And I'd gotten this book on F sharp because I wanted to learn F sharp. It was an interesting

language. I was mostly a C sharp developer at the time. I needed something to write in F sharp. And the book had a couple of chapters on F sharp has built into it a version of Lex and yak, which are scanner and parser generators. So I was like, Oh, this is kind of interesting. Maybe I'll try to make like a little, you know, compiler programming language thing. And I started tinkering on that. And I was like, man, this is like the greatest thing ever, basically. And I got super into it. So that's kind of, you know, where it started, but thinking about it after that, there are definitely points prior to that where I had more interest in programming languages and I had a kind of an affinity for it. So I have a memory of like, so my first

programming language was basic when I was in like middle school, elementary school. And I can remember doodling on a notebook in school and imagining if I were to make my own programming language, like what keywords I would use and stuff like that. And thinking that that was like this really fascinating thing, even though I had zero idea as to like how basic worked, it was like totally magic to me, but there was still some part of my brain that was like, I want to make a language too. This seems cool. That's great. What was in your language? Was it, I think I've had the similar thought as a kid, but mine would be like to print something, you would have to say like, Adam's awesome. And then give him the string. And then it was, yeah, basically at that level. Yeah. I don't know if I remember any

details about it, but yeah, something along those lines. So did your F sharp language experiments like bear fruit? Did you end up playing around or implementing something? So I started making this little hobby language called magpie that went through a bunch of different incarnations over time. You can basically watch me discover different programming language concepts by seeing me reboot the language in different ways so it was initially statically typed and had sort of a an ml like type system because f sharp has a type system kind of like that and this was a brand new thing to me and i was like i want to make a thing like that and then at some point i discovered optional typing and i was like i should make it an optionally typed language and then at some point I discovered optional typing and I was like, I should make it an

optionally typed language. And then at some point I discovered multi-methods and I was like, I'm going to reboot it around multi-methods. And then it, you know, kind of fizzled out it, you know, it never had more than zero users. So in that sense, it was not successful, but in terms of like, you know, I learned a ton of things writing it. I had a lot of fun writing it and I wrote some blog posts that people have read and

like, maybe that helped them understand bits and pieces of other languages that they actually give a damn about. So maybe it provided some value to other people too. So I guess it felt fruitful to me, even though no one uses it. It's interesting in computer science, it seems to me there isn't very many areas where you can kind of do this historical exploration, but it sounds like you're uncovering existing old techniques. Yeah. I I, for whatever reason, a big part of my brain is just really fascinated by programming language history and features. So it's like, you know, some people just have like this, like encyclopedic memory for like baseball scores. They can tell you like who won the world series in 1967. I'm not that guy, but I am that guy for programming language history

and language features. And I don't know why I'm that guy, but I definitely am. All that stuff just sticks. And I spend a lot of time on Wikipedia and I'm just like, I don't know why, but I just find all this stuff fascinating. What's an interesting programming language historical anecdote? Oh man, they're all interesting. They're each beautiful snowflakes, right? So here's a kind of relevant one.

So a while back, I was reading about this language called Icon, which I can't remember, I'll get the details wrong here, but I think it sort of grew out of the Snowball family. But it's a, you know, it's like a scripting language, kind of high level. The interesting thing about it is it has generators, you know, which a lot of languages have them now, but they're sort of more deeply woven into the language where in icon, you know, in most language, an expression, you evaluate an expression and it produces a value. That's what expressions are. Expressions are things that produce a value. In icon, every expression can produce a value or no values or multiple values. So it's sort of like every expression is returning a generator, right? And then an expression that evaluates to no values is what they consider failure, right? And then never actually written. But in cases where it could be meaningful to not have a value arrive or to handle multiple values,

the language will sort of seamlessly do that, right? And it kind of does a bit of backtracking and repetition, almost like Prolog or another logic language. I won't do a good job of coming up with an example, but the idea is that in some places, it looks like you're just evaluating an expression, but what it'll really do is it'll sort of keep trying as long as it gets values until it finds one that sort of meets the criteria that it needs. And in other places where it looks like you're just evaluating an expression, if that expression fails to produce a value, like imagine you're reading from a file and the file doesn't exist, you won't get a string back. You'll get the absence of a value. And if you do that in certain contexts, it understands to just like, okay,

well, I'll just short circuit the rest of the expression because the file wasn't there, right? So it has this sort of short circuiting and error handling kind of seamlessly built into it, which is a really cool concept, but it was kind of like a language dead end, right? Like no one's using icon anymore. And there aren't, I don't think there are any languages that are significantly derived from it. It sounds like do notation and Haskell. I don't know if you're familiar. Yeah, it's a bit like that, right? It's like you get a little bit of programmatic control over the language's order of execution or short circuiting. I'm probably doing a poor job of explaining it. I certainly understand it poorly. The interesting part of the anecdote is

my day job now is I work on this programming language called Dart at Google. And one of the things that I've been working on the past year is the main framework that's growing really quickly in Dart right now is this framework called Flutter. And it's like a client application UI framework. So you're building UI and it doesn't use a separate template language. So your actual UI layout and stuff is all just like vanilla Dart code, right? It's just like expressions and constructor calls and stuff. And in practice, that means you're doing a lot of collection literals, like list literals, right? Like you build a, you know, you have some widget that contains a list of buttons. That means it's, you know, you're doing a constructor call that takes a list literal that has all the buttons

inside the list. And that actually works out fairly fine, right? Like it's surprising that like C syntax can handle that stuff kind of gracefully. But where it kind of falls down is like a lot of times you actually do need some like kind of interesting conditional logic in there, right? Where it's like you, you know, you want to make a widget that contains this list of buttons, but in some configurations, like you don't want two of those buttons, right? And when you're in that situation, you know, if you don't have that conditional logic, the code looks pretty clean and declarative, right? It's just like return constructor call for the outer widget, list literal right in place, all the child buttons, it has this nice sort of like textual tree shape where the shape of the code matches the shape of

the UI. And it's pretty nice. But once you need to do some kind of conditional behavior, then you're like, okay, well, that list literal now I need to hoist that out to a variable and then do some imperative code where it's like, if it's in this condition, add these child buttons to the list, otherwise do this. So now like the code doesn't look declarative anymore. It sort of reads bottom up instead of top down and it kind of like gets gross. So my job for the past year or so is like, you know, we need to figure out what language changes we can do to make that code more graceful, you know, more declarative, make it nicer. And what we're doing now is we basically, we added support for if inside list literals. So right in the middle of, you know, like, you know, Dart's like a typical scripting

language where it has like square brackets for list literals, like you do in, you know, Python, JavaScript. So right in the middle of that, you can do if, and, you know, so you could do, you know, square bracket, A comma B comma, if it's Tuesday, C comma D. And what that means is on Tuesday, you get a list with A, B, C, and D. And on other days, you just get A, B, and D, right? So when that condition doesn't meet, then you don't get that element, which is fairly straightforward, fairly intuitive. What's kind of interesting is it's, that looks a lot like languages like Ruby, where

everything is an expression. Yeah, it's like an if expression, right? You can evaluate it. Right. It's like an if expression, right? But it's not because, you know, in that example, when it's not Tuesday, you don't get a list of A comma B comma null comma D, right? So a list, an if expression always produces a value because that's what an expression does. An expression always produces a value, right? Yeah. But that's not what we want. What we want is this conditional thing that can sometimes produce a value or sometimes produce no values at all. And we also added a spread syntax, which lets you sort of unpack a list into another list, which means also we have the syntax that lets you produce multiple values right in place, right? Not an object containing multiple values, but the spread

set of them. And that sounds an awful lot like what icon does, right? So like an icon, these things that are sort of expression like can produce, you know, zero one multiple values. So I took that and I was like, that's actually like a great solution for what we need here, right? We need something that you can put inside a list literal that's kind of like an expression, but not really because it can produce an arbitrary number of values and they just sort of get interpolated right in place. So it's a really fun opportunity to take some random bit of like programming lore from like 30 years ago and be like, oh, this is like a great solution for this problem that I have right now today. That's awesome.

I read a sci-fi book before where like programmers were called like programmer archaeologists because it was in the future and there was like basically any problem they could find, there was already an existing solution. They just had to like dig through the eons of existing code and find something. Stack overflow. Yeah. Yeah. It does feel like that a lot of times. So what programming language feature doesn't exist yet? Or like what language feature is the world missing or combination perhaps? So one of my pet features that I think is super cool and wish was more popular is this thing called multi-methods. I don't know if you've ever heard that. I can talk about what multi-methods are. So I heard you say it earlier. Why don't you define it? Yeah. So they relate to like polymorphism and virtual dispatch. It kind of depends on which

language tradition you're coming from. So I will assume that you and most of the listeners are coming from an object-oriented background, right? So in an OOP language, when you call a method on some object, that method is polymorphic in that whatever object is to the left of the dot can have a different implementation of that method, right? And at runtime, it looks at the object, finds the right method based on that object's type, and then calls that method. So even though it looks like textually, it looks like you're just calling this method doStuff, that at runtime will dispatch to different actual concrete methods based on the type of the runtime type of the object on the left.

Going into pedantic detail here, because the actual details sort of get relevant. So in most object-oriented languages, so that's how it works with the receiver, the part of the method that is to the left of the method's name, right? But all the other arguments to the method, so if you call foo.doStuff, paren, bar, comma, baz, bar and baz don't get involved in choosing which doStuff method to call, right? So those arguments, they just aren't involved in the dispatch process at all.

So they say the most object-oriented languages are single dispatch, which means there's only a single argument that gets involved in the process of figuring out which actual method to call. And in most duplanguages, we make that object even syntactically look privileged by pulling it out of the argument left and out of the argument list

and putting it to the left of the method name, right? Oh, yeah. So multi-methods don't do that. Multi-methods do multiple dispatch. So what that means is that all of the arguments to the method get involved at runtime in determining which actual concrete method body you select. So most statically typed languages today, like C Sharp and C++ and Java, support overloading. So you can have multiple methods with the same name, but different argument lists, right?

Yes. Those overloads are selected at compile time based on the static type of the arguments. So with multi-methods, you can imagine something like overloading, except those overloads are selected at runtime based on the actual object types. So that sounds like super weird and obscure and theoretical. So what's interesting about it is if you've done a lot of object-oriented programming, you have run into stuff that just feels weird and hard, right? So one example is like if you've ever like written your own, like maybe you've done like a little graphics library or something and you've written

your own point or vector class, it's nice to have that support like arithmetic operators, right? So you can add a vector and, you know, add two vectors and stuff like that. Most languages do support a certain amount of operator overloading. You can imagine like being able to scale a vector and, you know, add two vectors and stuff like that. Most languages do support a certain amount of operator overloading. You can imagine like being able to scale a vector too, right? So you want to be able to scale its magnitude by a number, right? So you want to be able to support the multiply operator on vectors and numbers. And what's interesting is that in some object-oriented languages, like it's actually hard to do that well, right?

So you can add, you know, you can define the times operator on your vector class to take a number on the right. But sometimes it's hard to define the times operator on the number class to take a vector on the left or take a vector on the right. So there's this weird asymmetry, right? Where the left-hand side gets treated specially by the language. So multi-methods give you a graceful way to do that, right? Like you can just say, I'm just going to define a new star method that takes a vector and an int and a star method that takes an int and a vector. And there is already a star method that takes an int and an int and that's fine. And these are all totally separate methods. And then at runtime, it will pick the right one. It's sort of like pattern matching,

but across a bunch of methods. Yeah, that's exactly what it is. So my hobby language magpie, what it did was it took pattern matching from languages like SML and used that same sort of structure for defining multi-methods. So you can think of a set of multi-methods as kind of being an implicit series of pattern matches that it would kind of assemble together itself. A cool feature, right? I do a decent amount of game programming

and this comes up a lot in games because a lot of a game is entities interacting with each other, right? So like think about collision detection where you have, you know, different kinds of entities do different things when they run into each other. Maybe two enemies, you know, they don't touch each other when they collide because you don't want to deal with like friendly fire. But if the hero collides with an enemy, maybe that's an attack.

And if an enemy collides with the hero, that's like a parry. And so you have all these pairs of objects and you want to define how they interact. That's really difficult to do in a single dispatch language, but in a language with multiple dispatch with multi-methods, you can just walk all those cases and say, for this pair, do this, for this pair, do this. And the language will just pick the right one at runtime based on the actual objects. It's really cool. Is this what they call the expression problem? Is that the same thing? Yeah. Yeah. So the expression problem is part of that so you can think of multi-methods as being a way to solve the expression problem i think like c-sharp

and scala you can add to things that are you can add extension methods to things is is it yeah so you can add extension methods you can add so c-sharp lets you add you can add new operators where the left hand side is a type that you don't control, but all of those are all statically dispatched. So it works because at compile time, it can configure out which one you're trying to call. Multi-methods are a little more interesting because they let you do the actual runtime dispatch. So for example, in my case, talking about a game where you're sort of doing collision detection, you don't know at compile time when two entities collide what kind of of entity they are. That's the whole point is like, it's the game's interaction at runtime. So a multi-method would let you call the right method based on what they actually are. Yeah. Very cool.

Multi-method has been my pet feature for a long time. And then Julia came out and that is one of Julia's core features. So when Julia came out, I was like, man, that looks awesome. And my half-baked language magpie is not going anywhere. So I'm just going to consider them having solved this problem and I don't need to worry about it anymore. So do you think that we have too many programming languages or not enough? Is there more solution space to explore? I don't think we have too many programming languages, but I just like them a lot. So I'm not an unbiased person to ask that question. You know, I do, I generally think that the software field is growing in terms of the number of different domains that we touch and the different kinds

of problems we solve. So I think it's reasonable for the set of tools that we use to grow over time, right? So from that perspective, I think, you know, we should have a variety of languages, right? Because the best language for writing an operating system is probably not the best language for writing a web application. Yeah, I feel like there's two, there's two pressures with languages. So like one is like the table stakes for language are really high. People expect some sort of library, you know, system that you can import things. Yeah. They get higher over time too, right?

Yeah. And they expect so much from a standard library and they expect, I don't know, this and that packaging systems. But there's another opposing trend I'll say, which is like at my work, you know, everything I ship is like some sort of service that runs inside Kubernetes with some load balancer in front of it. So like, in fact, if there's not something in a standard library, I mean, it may be available as an external service. So like your standard library could actually be smaller for some languages if the things you need to call aren't libraries, but external calls. Yeah, that's interesting.

So you're definitely right that over time, the table stakes go up for and syntax highlighters and a library ecosystem and a package manager and formatter and all this stuff before it's just like, you know, the surface area is just really large, right? So from that perspective, it's harder to get in the game now than it used to be. But you're also right that, you know, we've moved to a model that enables polyglot programming more than it used to in the past, right? Like in the past, you know, decade or so, where I don't know if it's just because performance has gotten good enough, we can afford the overhead of our PCs. And that means that it's lower cost to have parts of your system written in different languages. And that sort of gives you a way to kind of incrementally adopt a new language and to take advantage of libraries in other languages that are already out there,

right? And to some degree, maybe that does kind of lower the on-ramp cost, which is, you know, for me, someone who's like excited about seeing new languages is a good thing, right? Yeah, definitely. I mean, there's benefits to depending on like something via RPC versus a library because like you don't have to worry so much about giant trees of dependencies. Maybe you're just externalizing that. I'm not sure now that I think about it. Yeah. It's like any abstraction layer, right?

You get some benefit from maybe it's lowering the cognitive load of what you need to know to interact with that system. But if that abstraction prevents you from knowing things that it turns out you practically do need to know, then that becomes, ends up becoming like a regretful abstraction, right? Yeah. So you mentioned you work on the Dart language. You, in this book, you build this locks language. I found that you had another language called Wren. And now you've mentioned one called Magpie. So many languages. How does the Dart implementation differ from this book, like an approach? They're pretty wildly different. So the Dart team is a big, giant industrial scale operation. And I've done bits and pieces of work on some of the parts of the actual language implementation,

but I mostly don't work on the language implementations for Dart. We have a couple of compilers to JavaScript, an IDE, and then a VM that jits and compiles to machine code. And I spent some time working on one of the JavaScript compilers, but I mostly don't work on the language implementations. But all of those are a lot more, I don't want to say sophisticated, because that has a sort of moral character. But those are bigger and more complex than what we do in the book. But if you were to read the book, implement locks and implement all the various pieces of things and then go over to the Dart implementation and start wading through these millions of lines of code, if I did my job right, you should still find stuff that looks familiar.

The parser may be 10,000 lines instead of 200 lines, but you can still say like, oh yeah, that's a parser. I can tell that it's doing recursive descent there. I can see where it's handling operator precedence. The backend is a lot more sophisticated on these because, you know, in the book, we go through a lexing and parsing and then a bit of kind of internal representation. And we do compiling to bytecode, but there's not a lot of complicated backend optimizations and we're not compiling directly to machine code. So there's a whole bunch of techniques there that we don't go into. So if you poke around in the Dart implementations for that side of things, then it's kind of like, okay, I don't know what's going on anymore. And part of

that is because like, I don't know that stuff, or at least I don't know it yet. So I wouldn't be the right person to write that book. Well, I think it's one reason the book is so valuable because you could say, yeah, if you want to learn how to write a compiler, go look at GCC, but I don't think it's going to get you anywhere. Like it's just a insurmountable mountain. Yeah, it's overwhelming, right? And even to some degree, like just the, the programming language textbooks, right? Like, you know, the dragon book actually liked the dragon book, but it's a lot to take in at once. Right. And it's not clear, you know, it starts off pretty theory heavy. So it's kind of hard to know what to focus on, what matters, what to care about, you know, it's also kind of impenetrable

in some ways. So my hope with my book is like, my intent is for it to not be the last programming language book you read, but hopefully it's a good first one for you to read. Oh, that's great. And I think it's probably a great place to end it. I have a lot of more questions like you're compiling to, it's an interpreter, but it compiles to bytecode. And how do you do garbage collection? But maybe we'll have to save those for some other time. Yeah, maybe so. Thank you for joining me, Bob. It's been great.

Awesome. Thanks, Adam. That was the show. I hope you enjoyed it. That Sudoku solver solution was by Peter Norvig and it was something we were discussing in the Slack channel a little while ago. Comparing it to Ron Jeffrey's solution is super interesting

and maybe shows some of the limits of test-driven development. I think it also shows how valuable it can be to be familiar with existing solutions. The reason Ron Jeffries didn't arrive at a solution was just he didn't know about constraint propagation. Multi-methods was super interesting as well. And I'm wondering if there is a type class-based solution to multi-methods.

If you know, let me know. Until next time.