We Speak Your Language - Nora Sandler

Darius: Welcome. 

I am Darius, and I will be your host today, here at “We speak your language”, the podcast for programming language nerds. 

There are many books about languages and compilers out there, timeless classics, like the super famous Dragon Book, the contributions by Niklaus Wirth, Steve Muchnik (a personal favorite of mine), and others.

Over the years, most topics related to programming languages and compilation have been covered multiple times, and the underlying theory has not evolved with a such a pace that there would be an obvious need for a continuous flow of new contributions. 

The precious few new books published about languages and compilers nowadays take tangents, go for an angle, focus on languages as mathematical objects, on domain-specific languages, on the compilation of functional languages or on backends such as the JVM, .NET or LLVM. 

Nora Sandler is our guest today, and she is not fussy. She does not take tangents. She does not have an angle.

Her new book, soon to be published when we record this, is titled “Writing a C compiler”. From a distance, it seems to be yet another generic compiler book, but I am sure there is more to it than this. I can’t wait to learn how this project came to fruition, what its motivations are and who the target audience is.

Nora, welcome to the show.

Nora: Thank you for having me, Darius.

Darius: So, tell us a little bit about yourself.

Nora: So, I first got involved in compilers and programming languages as an undergraduate. I was working on the Manticore[NS1]  Project at the University of Chicago, which was focused on building a compiler for a parallel dialect of standard ML, and I ended up doing my B.A. thesis on a different parallel dialect of standard ML targeting GPUs. And so this was exactly the sort of very specialized programming research that you talked about in your introduction. After that, I got a job doing web security testing as a security consultant. And I thought, well, programming languages were fun, compilers were fun, but I thought I’d never work on those again.

After doing that for a few years, I wanted to change track a little bit and do something different. I ended up spending a session at a place called the Recurse Center - that's “recurse” as in “recursion” - which describes itself as a self-directed educational retreat for programmers. The idea is you go there - It's in New York but right now they're remote. But at the time, you physically went to New York and for three months or possibly a little less time than that, you focus on whatever you want to programming-language wise and learning aboutand exploring anything you want, surrounded by other people of a very, very wide range of skill levels and a very, very wide range of interests doing the same thing.

While I was there, the project I ended up being drawn towards was going back to compilation, and trying towrite my own compiler completely from scratch, and fill in sort of the gaps in what I had learned as an undergraduate because I had been focusing on these

very specific research questions, but hadn't actually taken an undergraduate compilers course. So I feel like there were some of the fundamentals that I didn't really know and

I didn't have a great sense of the big picture. And in particular, I didn't have a great sense of the big picture of compiling a language that was, I don't want to say real because, the line between real and fake languages is very blurry, but a language that was very widely used.

Darius: Yes, because we could agree that all languages are fake. Reality is overrated anyway.

Nora: Right, exactly. And of course, research languages can become real languages, and toy languages can become real languages, and you can have a language that's real, but hardly anybody uses it. So in some sense, the idea of a real language is nonsense. But I really wanted to write a compiler for a language that I had actually written code in.

That is sort of how this project started. The basis for it, the thing I used as a roadmap, was a paper that one of the other people in my session at the Recurse Center shared with me. It's called “ An Incremental Approach to Compiler Construction “. It's by Abdulaziz Ghuloum and it I think has a good answer to your question of why another compiler book, because it's not introducing new techniques or a new theory. It is introducing a new approach to learning it. And the approach is: we are not just laying out the information, we're going to make you build it yourself. We're not going to do one pass at a time where first you build the entire lexer, then you build the entire parser. And so finally, after you've been through the whole thing, you end up with a real compiler, because that is a deeply demoralizing way to write a compiler, right? You have to go through your entire undergrad class before you actually have something that's working. 

His idea was, “let's start with the world's tiniest compiler”. He was compiling Scheme. “So let's start with the compiler that takes just an integer and then we'll add unary operators and then we'll add binary operators and so on, and we'll build this out into something real.” So I took that, and really wanted to include parsing as an aspect too, because that was something I wanted to learn more about. And again, I wanted a language that I had worked with more than Scheme.

And so I thought, C is such a small language, it's such a low level language, it'll be really easy to write a C compiler.

Darius: I'm keeping my opinion to myself. ‘C is easy’ that's a new quote!

Nora: Well, I learned the hard way, that that is not the case. At the time, I thought that it would be a relatively doable project and I started working it. I started blogging about it at the same time, so I had this series of blog posts that was sort of a tutorial to follow along with this project. It turned out that a lot of other people were interested in this and also wanted to undertake something similar. So, after I'd been doing that for about a year, at the end of 2018 an editor from No Starch Press reached out to me and said, “Have you thought about turning this into a book?”

So that's how the book came about. And then the other thing I ended up doing after the end of my time at the Recurse Center was I got a job at a security company called CrowdStrike working on domain specific languages there, so I did end up making the switch from security testing into actually working with compilers professionally. [NS2] So that is my spiel and now I'll let you share your opinion, which I think I'm going to agree with about the idea that C is an easy language.

Darius: When it comes to compilation there is a saying, which is “writing a simple compiler for a reasonable language is easy enough”. It takes a few months and you can have something working, but as you need to optimize it even a bit, it turns into a nightmare. And where you start makes virtually no difference. I mean, writing an elementary C compiler is straightforward. Writing a C compiler that compares in a non too ridiculous way with compilers on the market is a gigantic undertaking, and the  scope between those two extremes is just amazing, but I like the idea of saying “C - how hard can that be”. That I’ve seldom heard!

So usually on this podcast we don't go into technical details, but I think that here it would be warranted. The way you describe writing a compiler essentially from scratch - and I apologize, there is no irony in the question,but you assume that people have access to a C compiler when writing their compiler?

Nora: Yes. In that sense, it is not truly from scratch. You do need a compiler. And also you're not writing your own preprocessor, you're not writing the assembler, you're not writing the linker yourself. In that sense, you're not creating the universe to make an apple pie from scratch or whatever the quote is there.

Darius: But at the end of the process, can you compile your own compiler?

Nora: You cannot, because I don’t recommend writing the compiler in C.

So I actually wrote the reference implementation for it in OCaml, and I figured that the average reader was not going to want to do that. So the book itself is in pseudocode so that people can write it using whatever language they want, so that they can focus on the ideas using a language they're comfortable in, rather than focusing on using a specific implementation language. And I mean, frankly, even aside from really liking OCaml in particular, I would not choose C as the language to write a compiler in general.

Darius: That's wonderful. I mean, it's wonderful because when I interview new hires, one of my favorite questions is, if given the choice, what language would you use to write a compiler? And C and C++ are the answers I receive almost all the time, and I agree with you that they are the worst answers ever, but I’d like to have your reasoning behind that.

Nora: I mean, so obviously in terms of why not C or  C++, the big strength of those languages for systems programming, which is what they're really good at, is you have so much direct access to memory. Their weakness for something like writing a compiler is that you have so much direct access to memory, and you're going to spend all of your time managing pointers instead of actually manipulating the data structures you need to work with.

In terms of OCaml in particular, at the very, very start of this process, I actually started writing my compiler in Python and I gave up and I switched to OCaml, which was a language that I did not know as well as Python, because I just needed algebraic data types in order to complete the project and not tear all of my hair out. So that's sort of the short answer. Having algebraic data types, having pattern matching just to me is a much, much more natural way to think about programming language transformations. And of course, in general a more functional paradigm is sort of an easier way to think about this kind of problem.

Darius: So, this is the limit of my expertize, but from where I stand, I always had the idea that OCaml was a very French thing, that the center of gravity of the OCaml world was in France. Whether Xavier Leroy is in the loop or was part of the loop, it is his universe. Obviously it's great that you chose it, but how did you get how did you bumped into that of all languages?

Nora: I bumped into it because as I mentioned earlier, my previous compiler construction experience was in standard ML. And so I wanted something that was ML-like, but that was better supported and had the tooling,the libraries and the ecosystem around it that made it really viable to use for a larger project.

You're absolutely right: OCaml is a pretty French thing, but it also has a real user base in the United States.And I think the big one is actually financial tech companies and Jane[NS3]  Street in particular has done a lot of work building out the library there and contributing to the language, so it’s very French, but not solely French.

Darius: No, obviously not. Don't get me wrong. As much as I enjoy spending time in the States, I think that the States can be a little self centric and I think it's great that contribution from the rest of the world can get adopted to your side.

But you essentially you wrote a book about writing a compiler from scratch. You don't give code, you give pseudocode so that people have to write code themselves. 

What about the gap? If you write pseudocode and the pseudocode is super functional in its lingo, in its paradigm, and you want to express it in a non-functional language, it can be really painful. Similarly, the pseudocode that is built into the abstract, we can map wonderfully to a language that does have a garbagecollector and fail pathetically if you don't have it. So what about the gap?

I mean, one of the downsides of pseudocode is that it is in fact code written in a non-existing language. So there's an impedance mismatch whenever you translate it to something “real” and executable. How about that?How did you deal with that?

Nora: So, the honest answer is that is something that I'm worried about. I hope it will not be too much of an obstacle for readers. But the way that I dealt with it is that the pseudocode in the book is a little more imperative. It actually looks a lot like Python

because Python is basically pseudocode if you read it. I've seen a few people online mentioning the series of blog posts saying that it's written in Python, which is not true [NS4] and then the reference implementation itself,which is in OCaml is going to be released at the same time as the book. So you have pseudocode and a complete implementation, and you have something a little more imperative, and you also have something a little more functional. Hopefully that will be enough to get readers over the gap.

Also, just anecdotally, what I've heard from people who read the blog posts is that they did find it useful, and they were able to adapt it themselves. The other thing is that honestly, I think the challenge of having to adapt it from one style to another is going to be useful pedagogically. It is going to force people to really understand itin a way that they might not if it were very, very close to whatever they were already working with. I think I've given people enough tools to work with, but we'll see.

Darius: I understand correctly and please correct me if I'm not, but based on our previous conversation, you told me that this was pretty much from scratch, which means that you do not use nor rely on the parsergenerator, nor do you use or rely on anything when it comes to the back end. So in other words, you don'thave something where you use that same ANTLR for the frontend and the LLVM for the back, you are in that sense, if not entirely open, you are almost self-sufficient. How did that go?

Because, it's an argument we have and trust me, I'm not excessively biased in that area because there are both sides to this. But when people write compilers, often they say parser generators are nice so that you can get the first version out quite easily because it's solved, but also at the end of the day what it solves is a fairly trivial problem. As a demonstration of how trivial it is, you've been able to do it yourself without a parsergenerator. So you can survive without a parser generator quite obviously, and having your own has its own benefits, I appreciate that. Still, in the context of a book, even though I appreciate that you may have sliced it differently, unless I’m badly mistaken, my understanding would be that you have been repeating things about parsing that have been published like 700 times in 700 other books before.

Nora: Yeah. I mean that's absolutely true that this is not the world's first explanation of how

to write a recursive descent parser. So, you are correct in your understanding, it is a handwritten recursive descent parser, and it is directly generating 64 bit x86 assembly code, so it's not targeting LLVM or anything like that, and it certainly is covering ground that's covered elsewhere, but it's presenting it in a project based way that makes it accessible to people who might not sit down and read a compiler textbook.

I'm not going to sit down and read a compiler textbook without something to motivate it. You also can't write a book like this and say, OK, go read this chapter of the Dragon Book and then come back and talk to me. So it's really not about presenting new material, but giving people a more accessible and hopefully a more engaging way of learning the material that's already out there.

Darius: For parsing it's not black and white. I see the upside. There's the industrial upside of having your own parsers, at least for a reasonably simple language like C. C++, for instance, is notoriously super hard to parse up to a point where there are companies that have one product, and that's a C++ frontend and that's all they do, because it is a specialty in its own right.

But for the back end, there are very few books that actually go as far as describing a back end that talks aboutthe actual architecture, either they go for a simplified representation such as a stack base virtual machine, or they go for one of the existing virtual machines such as .NET to JVM or LLVM for that matter, but this is typically a part of the complexity which in most books is generally outsourced. Industrially, I do compilers for a living, I really cannot imagine circumstances where industrially I would consider going for my own code generator nowadays. I deal with the wide range of situations, and I can't think of a single case where I think“OK I'm going to write a compiler and I'm going to generate native code directly”.

Nora: Certainly, if I were writing a compiler for my own language that I wanted to use in a production context, that I wanted people to really use, I might handwrite the parser, but I would not generate assembly code directly. That was a decision because this was a learning project and not because that is in general the most efficient way to create a new language.

The motivation of building this whole thing from scratch as much as possible was to demystify the compilers that people work with every day. And for people who write C or write C++, or certainly who extensively use software written in those languages - which is everyone - to really understand what that code is doing and have a really in-depth sense of every aspect of the compiler, not just the aspects that you're most likely to write yourself.

Darius: Sometimes when I tell people I make compilers, people have very creative images about what it is all about. I usually that compilers are, at the end of the day, a fairly straightforward matter. There are just 50 tricks of the trade that you have to know and that you cannot learn unless you've bumped into them for real. There's virtually no rocket science. I'm pretty sure I mean that in the LLVM internals there are things that I would never understand, but the bulk of what I do is not that hard. Just tricks of the trade.

If you were to contribute one (you did more than writing a compiler, you wrote an entire book about how to write a compiler from scratch), what would be the trick you would contribute? Imagine you wanted to write a compiler but you’re talking to someone who is not willing to read your book for any kind of good or bad reason,and then you try to give him or her some wisdom, what would that be?

Nora: Well, I think a lot of the tricks depend on, of course, what you're trying to build. And  this is maybe less of a trick and more of a general approach, but the basic strategy of starting really tiny, starting with something that's tiny but actually working and adding features individually, I found to be really effective and really usefulfor managing the complexity of what's going on.

The other thing that really helped me manage the complexity in the cases of this project was taking a very type-driven approach—I guess I'm sounding like an OCaml programmer here—but starting with the data structure, starting with what does your AST look like, what does your IR look like and letting that drive the rest of the development process. I don't know if those are tricks, but those are sort of the strategies that workedwell for me.

Darius: I would so wholeheartedly agree. I spend my time yelling at people telling them data types are going to save them. This is going to lead me to another question, but that's going to be a bit later. 

What you said about strong typing, I can only agree with. XXXX Compilers are non-trivial pieces of software, and you can use any help you can get. Typing is a guarantee of consistency. Do you really want to be responsible for that, rather than have an automated tool named a compiler check it for you? That's my spiel, so we are pretty much on the same page here. 

I would probably disagree with the concept of starting tiny and grow.

Aren't you then faced with cases where you started tiny and you end up having to redo quite a few things, because what you did was tiny indeed and now you’re faced with the problem of scale, or being too specialized?  Sometimes, as much as I appreciate how scary it is, you just have to say, well, this is it.

You can’t get to the moon using ladders, just starting with a small one. At some point you’re going to collapse.Aren't your ladders collapsing at some point?

Nora: Yes. That actually happened with the first version of this project, because what I was initially doing was following the implementation in Ghuloum's paper, which was parsing to an AST and then generating assembly code directly from that. And eventually my ladders collapsed, like you said. Even though the the architecture of the compiler was very simple, understanding the assembly code that was being generated was very difficult.Debugging that code was very difficult. Understanding each of the individual steps of the code generation process was getting sort of out of hand and I was really concerned that it was going to make the optimizationpasses extremely difficult. So I ended up having to refactor it and introduce a three address code IR between the AST and assembly generation. But I would much rather hit the point where things are falling apart and need to refactor, than make a guess at the beginning about what's going to carry me through the whole way and then end up needing to refactor anyway.

Darius: How complete is your reference implementation?

Darius: How much of it is usable or is it a subset that makes it useless except for test programs?

Nora: It is a pretty limited subset. The biggest thing that's missing from it is typedef,  because I wanted to keep the architecture very simple. So I wanted to keep all of the semantic analysis separate from the parsing, which obviously was a challenge because typedef makes it a context sensitive grammar.

I really go back and forth on whether that was the right thing to do. If there was ever a second edition that might be different. In general in the book I've tried not to shy away from introducing complexity when it was needed. The problem with typedef in particular is that it would have meant introducing a more complex architecture very early in the book where you wouldn't see the payoff until much later, because the type system doesn't really happen until part two. So that was the rationale behind it. I do waffle[NS5]  about whether that was the right thing.

Darius: Yes, because for someone who is so serious about types, to say “why don’t you run a compiler withoutsupporting types” I’d say I feel cheated. And for someone who says, I'd rather do things incrementally and then refactor and then say “but this is too annoying, let's get this out of the way”  that's cheating!

I mean, very respectfully, Nora, I think that that you've been shying away from something very real. And at the end of the day, it's not even the end of the world. I don't think that To support this during parsing when you write your own parser manually is a fairly straightforward matter. It's just a table you maintain somewhere and it’s not that hard.

Nora: I do want to say I think you said something about not having types. It does have types, it does have most of the type system, it just doesn't have typedefs.

Nora: You can't create type aliases. It doesn't support the typedef keyword.

You can still define your own structure types and that sort of thing.

Darius: Because my next question would have been (OK, I know the answer. So I'm not going to be long on this), since you have a reference implementation and you cover a decent subset of C, have you been able to test that on the portfolios of millions of lines of existing C code?

Nora: Unfortunately, the answer is that it doesn't, it's not quite full featured enough to be able to do that.

Darius: At least not yet! We look forwards to the second edition for that.

So who exactly is your target audience? Who do you think if you were to describe if you were to to to describe Steven? I don't mean this to be gendered, but I'm sorry I have to pick one. Steven is your ideal target audience for the book. What would you say about Steven, who is he?

Nora: I would say that my ideal reader, who I'm going to call Linda, is someone who certainly already knows how to program, she is a pretty proficient programmer. It is certainly not a book for novices. She knows some C, but isn't necessarily an expert C programmer, but knows enough that she's not going to be tripped up by reasoning about pointers and how they work while she's completing the project. She really likes to understandhow her tools and her system work and wants to go beyond using abstractions to understand how they're implemented. She is driven by curiosity and the desire to know things better. And that is hopefully why she will pick up the book.

Darius: Is there anything you wanted to add to your book and finally recanted because the complexity was not worth the cost - something you thought might be a good idea, something you thought was a great feature, but explaining it would have been just too much of a burden?

Nora: There really isn't anything I can think of in that category. The one thing that I mentioned earlier was typedef, which I think, as you rightfully pointed out, the complexity

there isn't really prohibitive. I just ended up making the call that I couldn't include everything and that's what I didn't include. 

Everything else that ended up not being in there would have been not prohibitive to add, but the book is already pretty long. At some point, you have to leave things out. Any one individual thing wouldn't have been terrible and my hope is that it's built in a way that anything that readers do want to add on their own, they'll be in a very good position to do that, whether it's typedef, whether it's function pointers, whether it's additional optimizations. The deciding factor was just length.

Darius: How do you describe what you do when you meet people outside of the computing world?

Nora: Well, I try not to.

Darius: You try not to meet people outside the computing world, or you try not to explain what you do?

Nora: No, I try not to explain what I do. Occasionally, it will come up that I'm writing a book, and people get very excited and want to know what it's about. And so I'll say it is about compilers. They are programs that taketext that programmers write, source code, turn them into executables that run on computers. This book is about how to write one of those yourself. At that point, people's eyes sort of glaze over and then I change the subject

Darius: Yes, socially, things are more comfortable when talking to a language or compiler person. But that'swhat made this question interesting. You say we all know how awkward it is, so how do we share experiences there?

Nora: I would love to come up with a hook that makes the topic interesting to people outside of computing, but I haven't found one yet.

Darius:

I have a Proust-like questionaire for you, made of the standard question we ask everybody.

If you've listened to a past episode, you’ll recognize them.  Hopefully you're not too prepared and they remain spontaneous. What would you do if you weren't involved in languages and compilers?

Nora: I think if I weren't involved in languages and compilers, I would probably still be involved in security. That was my first job out of school, it's still something I'm very interested in and of course, there's a huge overlapbetween security and compilers in terms of thinking rigorously about how programs behave. Obviously, compilation has lots of implications for security and vice versa. They're both very finicky, detail oriented sorts of disciplines. So yeah, I think probably security.

Darius: And what if you weren't involving computing at all? Let's say that computing is no longer an option.What would you do?

Nora: Well, I think I would really love being a crossword puzzle constructor. I don't know if I'd be any good at it,but I do really like solving crossword puzzles. And then if I really cared even less about paying the bills, I mighttry to be a poet. I've written poetry off and on since high school, and I love reading poetry. So that's something that is an interest of mine. It's something I'd love to spend more time on.

Darius: I wouldn't be able to say much about poetry, but when it comes to crosswords, I am more of a geek than you are, because I fantasized numerous times about writing software that would build crossword puzzles.You know, because I'm not interested in building them, I'm more interested in writing code that would build one.That’s the geek in me I guess.

Nora: I think those actually do exist, and they're pretty standard.

Darius: Yes, sure. I'm pretty sure they do exist.

Nora: Now if you can come up with software that can create good crossword puzzles, that would be impressive.

Darius: What is the essence of a good crossword puzzle?

Nora: A lot of it is the clueing, which I think most crossword construction software

doesn't do for you. For now, humans are still writing clues, but presumably getting a machine learning model to do that would be fun. XXXX In terms of the fill itself, you want something that is not incredibly dated, that is not crosswordese, and that's fun. You want fun words and fun phrases. I'm sure you can get a computer to learnwhat fun phrases are.

Darius: How old were you when you wrote code for the first time?

Nora: I was, I think in middle school, maybe in fifth grade. That was just HTML and CSS. I made a website for a school project, and I think I maybe had a GeoCities[NS6] . Then beyond that, I didn't really do any programming until a class in high school where we learned C++ and it was so dreadful and so boring that I gave up and said, OK, I'll try learning to program again in college. So I didn't become really interested in programming until I got to college.

Darius: And what was the first programming language you used? No disrespect to HTML, it is a language but I would not consider that as a programming language.

What was the first programming language you actually enjoyed?

Nora: That I actually enjoyed? My first college computer science course was in in Scheme. We used DrRacket and it was designed as an introduction to functional programming, a really big emphasis on understandingrecursion, that sort of thing. That was a lot of fun and that's what really got me hooked on programming.

Darius: What software project would you have loved to be part of?

Nora: I think CompCert I would really love. I am really excited about formal verification and really interested in software correctness. I've never used Coq before, but I have worked with Agda a little bit and that was extremely fun. So getting to work on a substantial project in Coq I think would be really exciting.

Darius: You’re still in the OCaml universe, we're talking about the same people.

What would you consider the most important quality for someone in our trade?

Nora: I think it might be empathy, because as a programming language implementer, you're pretty much, by definition, building things that are being used by people who know the language not as well as you do. And it's very, very difficult to put yourself in their shoes and understand how they're going to think about it, what they're going to get tripped up by, what the pain points are going to be, and I think being able to have empathy for people who don't know the technology as well as you do is how you figure out which parts are most difficult, which problems are really worth solving, and which problems are the most important problems.

Darius: So that's very consistent with the very project of your book where you want to be able to demystify things.

Darius: What do you consider your most important professional, technical, scientific quality? What makes you good at what you do?

Nora: I'm extremely pedantic. I really I love details. I love sort of getting into the nitty gritty of how things are implemented. I love looking at edge cases, and that definitely pays off in this field.

Darius: And so, the opposite. What is your biggest flaw? What makes you suck at what you do?

Nora: So, it's the flip side of that same answer is that being really invested in details can also turn into tunnel vision, where I'll be really excited about whatever is in front of me which makes it hard to step back and say, “Is this the thing that I really should be working on? Is this the most important problem? Am I sort of focusing on the thing that grabs my interest instead of being a little bit more deliberate about what I should be learning or what I should be building?” 

Darius: And this is my favorite question because the answers just never fail to amaze me.

If there was one language you wish never existed, one language you could erase from the planet, which would that be?

Nora: Well, I was going to say CSS, because that is the language that I personally have found the most frustrating to work with, because I have no mental model of what's going on with it. So I just have to use trial and error to figure out what's happening. But since I've been informed that CSS is not a real programming language…

Darius: That's for me personally, you don't have to take your cues from me.

Nora: I know.

Darius: But let's see which programming language you've used. You mentioned C++,

which you seem not to be too happy about. Is there anything about that language that would make you say, I'm never going to use this language, if this language could disappear, i'd be very happy?

Nora: Well, I actually haven't really worked with C++ extensively. I've worked with C, not so much with C++. Other than CSS, I'd say JavaScript is also extremely frustrating, the level of type anarchy is not for me

Darius: I was pointing to that earlier in the conversation: I assumed that JavaScript will pop up. Someone who has interest in types like you do, cannot be enthusiastic about JavaScript, I could see that coming.

If you were to direct our audience, to read one book, one article, one author, computer related or not, what would that be?

Nora: So, I'm going to suggest an article, and it's actually not a programming languages article. It is a distributed systems article. It's called “Using Lightweight Modeling to Understand Chord”. It's by Pamela Zave, and it's looking at a distributed hash table protocol called Chord. She uses a formal modeling tool called Alloy to understand it better and what she finds is that this very well known protocol not only does not actually have any of the properties that its authors proved that it had in their previously published work, but that all of the different papers about it actually present different versions of the algorithm that are meaningfully different in terms of correctness and what properties they have.

And the way she puts it is that this protocol exists in a haze of uncertainty, keeping in mind that obviously, this is not just true of this particular protocol, but a lot of the algorithms and formalisms that we work with as programmers exist in this haze of uncertainty. It is useful as a reminder of how difficult it is to be rigorous about that and the benefits of using tooling and using formal methods when we can to clear up that uncertainty a little bit.

Darius: That's great choice. And what is the book you wish you could force yourself to forget so that you can read it over and over and over again?

Nora: Well, most books that I really love I don't want to forget because I liked them. The only exception that I can really think of are murder mysteries, because, of course, those don't have a lot of reread value once you know who the murderer is. So if I could forget all of the Sherlock Holmes stories I've ever read so that I could read them again, that would be great!

Darius: And what would you like to be remembered for?

Nora: I don't really know. I'm 29, so I'm hoping that whatever I'm remembered for is something that I haven't done yet. But that said, if “Writing a C Compiler” is not necessarily the thing that I'm remembered for, but it gets someone interested in compilers and programming languages who otherwise wasn't interested in them, if it encourages someone to learn more about the topic, if it gets someone actually working on that or contributingto those projects long term, that's something I would feel really good about.

Darius: Hey, Nora, thank you so much. You've been the most graceful of guests. Have a wonderful day.

Nora: Thank you so much for having me. This was a lot of fun.

 [NS1]this is correct

 [NS2]We might cut this since it’s a bit of a non-sequitur, but I’m also okay with leaving it in

 [NS3]this is correct

 [NS4]I’d like to cut this sentence, but I’m fine leaving it in if we can’t cut it out easily

 [NS5]this is correct

 [NS6]this is correct