REIN: This episode is brought to you by PagerDuty. In an always-on world, teams trust PagerDuty to help them deliver a perfect digital experience to their customers every time. With PagerDuty, teams spend less time reacting to incidents and more time building for the future.
From digital disruptors to Fortune 500 companies, over 12,000 businesses rely on PagerDuty to identify issues and opportunities in real time and bring together the right people to fix problems faster and prevent them from happening again. We're like the central nervous system for a company's digital operations. We can analyze digital signals from virtually any software enabled system, and help you intelligently pinpoint issues like outages, as well as capitalize on opportunities, while empowering teams to take the right, real time action. To see how companies like GE, Vodafone, Box and American Eagle Outfitters rely on PagerDuty to continuously improve their digital operations, visit PagerDuty.com.
JACOB: Hello and welcome to Episode 152 of the Greater Than Code podcast. I'm joined by my co-panelist, Chante.
CHANTE: Hello everyone. Great to be here. Chante Thurmond here. And I'm going to introduce my fabulous co-panelist, Jess Kerr.
JESSICA: Good morning. Thank you, Jacob. Thank you, Chante. And I am here with Rein Henrichs.
REIN: Hello everyone. It is my great pleasure to introduce our guest today, Professor Philip Wadler, or as I like to call him as of just now, Phil. Phil is Professor of Theoretical Computer Science at the University of Edinburgh and Senior Research Fellow at IOHK. He is an ACM Fellow, a Fellow of the Royal Society of Edinburgh and editor-in-chief of the Proceedings of the ACM for Programming Languages. He is a past chair of ACM SIGPLAN and many other things. I don't have time to read right now. Previously, he worked or studied at Stanford, Xerox Parc, CMU, Oxford Chalmers, Glasgow, Bell Labs, and Avaya Labs. He has an h-index of 66 with more than 24,000 citations to his work (which means he is "a big deal". That's my editorialization, that's not in the book) according to Google Scholar. He has contributed to the designs of Haskell, Java, and XQuery, and is co-author of Introduction to Functional Programming (my personal favorite Haskell book), XQuery from the Experts, Generics and Collections in Java, and Programming Language Foundations in Agda, which is new as of 2018. Welcome, Phil.
PHILIP: Hi.
REIN: What is your superpower and how did you acquire it?
PHILIP: I think my superpower is that I'm not afraid of mathematics. One of my favorite quotes is from somebody I think around the 1500's who says if you are trying to solve a problem and you can apply math to it and you don't, then it's like having a candle in your hand looking for something in the dark but not lighting the candle. Mathematics is what lets us find elegant and beautiful and clear solutions to things. And to my great joy is trying to take theory and apply it to practice and then use practice to say, "Well, what other bit of theory do we need?" And the particular theory that underpins all of programming languages is something called Lambda Calculus. And I'm actually renowned for running around with this symbol on my chest. So this is like the Superman symbol, but the S has been replaced by a lambda, standing for lambda calculus. So it's earned me the nickname Lambda Man. I run around dressed like this sometimes and I love this little thing. This was actually made for me by some students. They 3D printed this symbol for me, so that's amazing. The other superpower is having great students.
REIN: This might be our first legitimate superhero on the show.
CHANTE: I'd say so.
JESSICA: That's true. He has a costume and everything. He wears it when he speaks at conferences and it's great.
PHILIP: Okay, I'm blushing now.
REIN: What shall we talk about? What's on your mind, Phil?
PHILIP: What's on my mind? Well, what's most on my mind these days is I used to be renowned for work I'd done with Haskell and I still teach a first year class for Haskell. I've got 460 students this year, which is amazing. But the class I really love is my class with 20 students where I'm teaching with my new textbook, which is Programming Language Foundations in Agda.
JESSICA: Tell us about Agda.
PHILIP: Agda is what Haskell wants to be when it grows up.
[Laughter]
JESSICA: Cool.
PHILIP: So, Agda is like Haskell, a functional language. Haskell has a type system. Agda has what are called dependent types. And the great thing about those is they're powerful enough that you can represent all the interesting bits of logic in your programming language. And there's this wonderful idea called Propositions as Types, which gives a correspondence. It says anytime you have an interesting logic -- okay, what are the components of a logic? Well, you've got propositions which are things that could be true or false. You've got proofs, which is if you have a proof of a proposition, then you know it's true, assuming your logical system is sound. And also they sometimes talk about simplifying proofs, which was important because it turns out that to show there's no proof of false, which is something you'd like to know, that's what [inaudible] you to do if you look at proofs in simplified form. So you've got these components and logic. And then what do we have in computing? We have types and we have programs which return values of the given type. Typically, a program might be a function. A function is itself a value. It's a value that if you give it a value, it will return another value. So it's all values all the way down. So you have types, which describe these things. You have programs or terms. And then you have a notion of evaluation, which is just simplifying the term. And it turns out there's a one-to-one correspondence that preserves all this structure. So one-to-one correspondence that preserve structure is called an isomorphism. And what that means is propositions correspond to types. A proof of a proposition is like a program of that type. And when you simplify a proof, that's exactly like simplifying the program that is evaluating the program. And it turns out this works for pretty much every interesting logic you can name and pretty much every interesting programming language feature you can name. There'll be some logic that captures it.
So when I first saw this, I just thought, "Oh, it's a stupid trick that these things correspond." I didn't understand how broad and deep this idea was. But after a while I realized it wasn't just a pun, it was the basis for my entire research career. So using this idea [inaudible] quantifiers in logic. So if I want to say, "For all X and Y, X + Y = Y + X," that becomes a type in my programming language. And a program of that type becomes a proof that addition is commutative. So I can write programs, I can prove properties of these programs all in one place. And I find that really exciting. So I used to just write Haskell programs and hope I'd got them right. Or maybe a quick check the tests that I've got them right. But now I can write a functional program and prove that it satisfies its specifications. I'm really excited about that. I'm really happy to have written a textbook about this and be teaching classes about it. Oh, so I have to tell you the name of the textbook. It's called Programming Language Foundations in Agda. And I have to tell you the URL, which is PLFA.inf.ed.ac.uk.
JESSICA: So in this correspondence, which is pretty exciting, it says that if you can write a program or a function to go from a certain set of types/parameters to another type, then that type is true or it's attainable.
PHILIP: Well, I'll give you one specific example of it, which might make this easier to understand. So in logic, I might say something like A implies B. You probably all know enough logic that that's familiar. So what would that mean to say A implies B?
JESSICA: Is that a function from A to B?
PHILIP: Exactly. It's a function that says, given a proof of A, I will return to you a proof of B.
JESSICA: So is the instance of the type, is that a proof that the type exists?
PHILIP: Exactly. The type is the proposition and all of the things that have that type are proofs of the proposition.
JESSICA: Oh, okay. So the actual like instances of that type are a proof. So if I have a type that is an array of length three and I instantiate an array of length three, then sure enough array of length three is a thing.
PHILIP: Right. An array of length three. So arrays aren't that interesting in logic because what an array of length three of type A say, "Okay, that's three proofs of A." But in logic, usually one proof is enough. You don't need to have three proofs of A.
JESSICA: So, it's boring to have multiple instances of [crosstalk].
PHILIP: I'll give you another data structure. The pair type has two things in it. It has an A and a B. So we call these record types or pair types or what have you. And the logic that corresponds to conjunction.
JESSICA: A and B.
REIN: You gave it away. You said an A and a B.
PHILIP: Right, exactly. You've got an A and you've got a B, so you've got a proof of A and B. So what does it mean to prove A and B? It means I've got two things in my hand. One is a proof of A and the other is a proof of B.
REIN: This is constructivist, which means if you can prove something, you'd better show it to me.
PHILIP: Right. So the interesting place where construction shows up is the only proof you can give that there exists an X such that X satisfies some property. What would a proof of that be? Well, it's going to be a pair, what's called a dependent pair. So, say the property is P of X. Well, let's pick a property. Let's say X is a natural number. I want to assert there exists a natural number, which is even. So let's define the property being even, first of all. What does it mean to be even? Well, there are two ways you can be even. You can either be a zero, so we know zero is even, or you can be the number N+2 where you know that N is even. So even of N implies even of N+2. And then, I can write this all down as the definition of a type even. Okay, now I want to say there exists an X such that even of X. I can prove that.
JESSICA: And X is a natural number?
PHILIP: Right. Where X is in this case a natural number. So there exists a natural number X such that even holds for X. What would the proof of that be? Zero, and I already told you zero is even so I just give you that piece of evidence or that part of the data type.
JESSICA: Or you could give me four.
REIN: And a proof that four is even.
PHILIP: [Crosstalk] Four is even is a little bit harder that says four is even because two is even because zero is even.
REIN: So the values of this type are both a natural number and a proof that that number is even.
PHILIP: Correct. This is great. You can never prove something exists actually getting a hold of it. And similarly for a disjunction. So, disjunction means 'or'. What would a proof of A or B look like? Well, it's going to be one of two things. It's either going to be a proof of A or a proof of B. We sometimes call these sums because let's say there were five different proofs of A and seven different proofs of B. How many possible proofs are there of A or B?
JESSICA: The sum of those.
PHILIP: Right. Twelve, because it's either going to be one of the five or one of the seven and there are no other possibilities.
JESSICA: It's a little confusing to people sometimes because a sum type is an 'or' type, it's a disjunction. It's a union type or an either. Whereas usually we use the word 'and' associated with sum four and seven is 12 but that's completely different.
PHILIP: Well, yeah. You have to use plus and be a little bit more precise.
JESSICA: Right.
PHILIP: One of the nice things about mathematics is it is quite precise. There's no way in mathematics that you confuse plus which acts on numbers with conjunction which acts on truth values.
JESSICA: Right. And that precision is part of the turning on the light.
PHILIP: Exactly.
REIN: This is also much used [crosstalk].
PHILIP: If you're just using language, you can get confused. But if you think about it mathematically, it will keep it straight for you.
JESSICA: Yeah, and that's very deliberate. Like English is ambiguous for reasons and there's great uses to that. But mathematics is very precise. And if you want to be precise, don't stick to English.
PHILIP: That's fair.
REIN: It's also much easier if rather than thinking this through in your head, you can have computer to help you get it right.
PHILIP: Right. I've actually been teaching a class in Theory of Computing for years. And a researcher named Benjamin Pierce said, "You know, it's better to teach it with a proof assistant, a computer thing that will check your proofs for you," because using a computer can be quite frustrating and annoying, but it does mean you get instant feedback when you've completed a proof, and that's very helpful for the students. So he collaborated with many other people and ended up writing a textbook called Software Foundations. And I taught from that for five years.
JESSICA: He also wrote Types of Programming Languages, right?
PHILIP: That's right, he did. And I taught from Software Foundations for about five years and he uses a proof assistant called Coq. I hope that doesn't violate the harassment...
JESSICA: C-O-Q, isn't it?
PHILIP: C-O-Q, yes. So I hope it doesn't violate the harassment policy if I pronounce its name. But I taught from it for five years and I decided, "No, I don't want to use this anymore. I want to use Agda. Agda will be much more beautiful." So I wrote my own textbook based on Agda. And I do find it much more fun teaching from that than from Software Foundations. Software Foundations is still a great book. It may be better for some people. But one thing in Coq is you have a separate language. Your proof is not a programming Coq. Your proof is a program that when you run it, it gives you the program that you want that's the proof. So you're one step removed. And sometimes that's really helpful if you're trying to prove something that has a lot of trivial cases that you don't want to write out in full. But for just understanding proofs, I think it's easier to write the proof directly. So that was one of the advantages of moving from Software Foundations which uses Coq, to my textbook Programming Language Foundations in Agda.
REIN: So if I were to describe using a proof assistant for our listeners who may be haven't, I would say it is like trying to have a conversation with a very pedantic but well-meaning friend.
JESSICA: Just like you.
PHILIP: Yes. With the emphasis on the very pedantic. That description is very good. But the other thing is it's like a video game because generally when you're doing a proof, you've got something you're trying to prove and then you apply some proof rule because I'm trying to prove A and B. Then I apply the proof rule and that says, "Okay, now I need to prove A and I need to prove B." A big proof breaks down into smaller proofs.
JESSICA: Like it gives you side quests?
PHILIP: Exactly. So the proof is what you call a goal. And then the smaller things you need to prove along the way are called sub-goals. And the way we should do a proof with a proof assistant is you say, "Okay, here's the thing I'm trying to prove. I'll try proving it in this way." So like say I'm trying to prove A or B and I stare at it. " I think A is true." My goal was A or B and my sub-goal is to just prove A because I've decided that's what's going to be so here. Or I might be proving A or B implies C or D and now I've got a function. I say, "Okay, let's look at my argument. Which was it? A or B." And then after looking at it, I say, "Okay, it's either going to be an A or B. If it's an A, I think C is true. But if it's a B, I think D is true." So now I've got sub-goals. Show that A implies B, show that C implies D. So anyhow, you've got some proof, you're looking at it and you've got some ways of breaking it down into sub-goals. So I think the goal is sort of shambling towards you and it's a zombie. And then you've got your proof rule and you hit it on the head with the proof rule, this big hammer and it breaks into two smaller zombies.
JESSICA: Now, that sounds scary.
PHILIP: Also shambling towards you called sub-goals. And then you hit those with more hammers and so on. And eventually it becomes obvious.
JESSICA: Like eventually they get small enough that you can step on them?
PHILIP: In Coq, you say reflexivity. And in Agda, you say control C, control A.
JESSICA: [Laughs]
PHILIP: But there's some standard trick that you use when it becomes obvious. So I referred to that as your shotgun and that just blows the zombie away. The zombie has gotten small enough that you can blow it away for shotgun. And then when you get all the zombies gone and it says QED at the end, then what happens is you type the command and everything turns the right color. The writing in black, it all turns blue and red and green and so on. The keywords are blue or green and the defined things are blue and the constructors are green. Everything gets its own color. And you hit a little window at the bottom and the window has nothing in it. That's really exciting that you've got this window with nothing in it because that means you have no errors.
JESSICA: You said when you get it right, can you get keyword highlighting?
PHILIP: Yes.
JESSICA: But before that while you're trying to construct the program, you don't get keyword highlighting?
PHILIP: Yeah.
REIN: It is incremental.
PHILIP: The idea of proof assistance are...Yeah, you can do it incrementally. You can get keyword highlighting along the way. So, you're right. The exciting thing is not that it's in color because often it'll be in color. The exciting thing is this little window at the bottom with nothing in it. And when you hit that, it's like you killed off the last zombie. In fact, you get the exact same serotonin rush that you get when you're playing a video game when you've killed off all the enemies. It's exactly the same thing. Mathematics and proof assistance is, "Oh God, I have to argue with this pedantic friend," which is true, but when you win the argument, it's just like winning a video game.
JACOB: I don't have a math background, but this is making me think of my experience working with TypeScript. It sounds like it's a little bit like what you're talking about, but maybe not as formal or strict. But my experience with TypeScript is I'm getting in an argument with the pedantic friends. And in a lot of cases, my friend is sort of holding me up over technicalities that I know aren't important to what I'm trying to do, and that can sometimes be frustrating. But what I find is it forces me to, just like you were saying, sort of step back and step out of the assumptions that I'm making in my own head. And it sort of forces me to write something that if a compiler can understand it, hopefully a person coming along who knows less about what I'm trying to do than I do, hopefully they can understand it too. And there's going to be a little bit less ambiguity in the system or in their person's interaction with the software.
PHILIP: About 20 years ago, people were beginning to teach Haskell in the industry. And a colleague who had taught such a course told me about it. It wasn't actually Haskell, it was something that was very much like Haskell. And the developers would come in and they'd learn -- I'll use Haskell -- they'd learn Haskell, and then they try to get their programs running and they'd get type errors. And they'd react exactly the way you reacted, "This is annoying." But what happened when they got all the type errors gone, they were doing fairly simple programs. So it turned out when they got all the type errors gone, their program ran the first time. And they understood the point of having the type errors. So a more complicated program that won't necessarily happen, but types are really helpful in helping you get it right. And getting all these type errors is actually great because it's doing the debugging without having to come up [crosstalk].
JACOB: Without running the program. Yeah, I found that as someone coming from more regular JavaScript or Ruby, the common thing I would do is I would write a little bit and then run the tests or refresh my browser or whatever. So write a little bit and then check the end result and back and forth. And I found that my working with TypeScript would be that, "Oh, I've been working in this sort of state of flow," where I've only been talking with my text editor, and I haven't been flipping over to see what happens for the last potentially half an hour or whatever. And I find that I can really enter a state of flow because I'm not sort of trying to go back and forth and then forget what I was doing when I flipped back to my text editor. It's this sort of one conversation without interruption.
PHILIP: Okay, that makes sense. So the types that you do a lot more without testing.
JACOB: Yeah, and I don't have to sort of switch contexts quite as often. I can really just think about it in one stream.
PHILIP: And then a proof assistant just sort of the ultimate form of that. Because if you write down proposition, that means your code matches your specification. And you prove that, which means it gets through the act of type checker, then you're done. You've now proved that works for every possible case.
JESSICA: Yeah. That lack of errors says a lot more than running a few test cases or even thousands of test cases.
PHILIP: Right. And some people say once you've proved it, that's it, you're done. I actually think if you have a program and you've proved it correct, you still want to test it. But once you've proved it correct, you know you have a lot more assurance that's going to do what you want.
JESSICA: Yeah, because you want to run it and find out if that specification means what you thought [crosstalk].
PHILIP: Exactly.
REIN: So when you were talking about working with a proof assistant, the model you sort of described is that you take a large problem and you break it down into smaller and smaller problems until eventually they become so obvious that you can just ask the computer to solve them for you. And I guess maybe the question is where does human creativity and insight come into this process? Is it a purely mechanical process? And I think it comes into the choice of goals that there's an insight about how you decompose a problem. There could be many different ways to decompose it. But I think it lets you think sort of just like you were saying, you can think in a sort of higher level, you can have a sort of a higher level of discourse with your computer where you're not worried about, "Oh, will this be nil here?" You're worried more about, "Is my specification right?"
PHILIP: Yeah, that's right. And then the specification helps you understand what special cases like nil you need to worry about.
REIN: And then the part where the human plays a role is not in thinking through what the implications of nil are. In this case, it's thinking through how I can creatively problem solve at sort of a higher level of thinking.
PHILIP: So I'll give you an example of this. This happened to me a long time ago as a post-doc at the time. So this is early 80's in Oxford. And I was writing a text editor. This was before Emacs had conquered the world. So I was writing a text editor and I wanted to make a change to it to make use of the cache so it didn't need to redisplay everything. And I only had an hour before class. I thought, "I'll never get this running in the hour. I know, I'll write down the specification instead." So I wrote down the specification of how the cache should work and it turned out that only took me about 10 minutes. And having done that, I realized, "Oh wait, I can use this as a guide to writing the code." And I had the whole thing running and tested in the one hour before class because I wrote down the specification first. If I had more time, it would've taken me a lot more time because I wouldn't have thought to write down the specification first.
JACOB: Sounds not dissimilar to TDD.
PHILIP: Maybe not, but it's not a matter of just writing out the test. It's a matter of writing out the actual formulas that define when this works just because I had the general formula, not just test cases, that I could go through the code and look for every place formula was violated and say, "This is the place where I need to insert some more code to make the cache work properly."
JESSICA: Right. Compared to starting with the implementation, TDD forces you to at least think of examples which is progress to think of a general formula is going much, much farther.
PHILIP: Right. TDD is great, but specification is even better.
REIN: One of the things you get with a dependently typed language like Agda is your specifications specify more. They say more than, for example, Haskell. So like in Haskell, I can say if I add two lists, I get a new list. In Agda, I can say if I add a list of list two and a list of list three, I get a new list and its link is always five.
PHILIP: Right. In fact in Agda, you can define either one and different things are useful at different times. But yeah, it gives you fine level control over what you want to say. So, if you can think of as many properties as you want and no matter how many there are, you can put them into your type.
REIN: And it reduces the space of possible programs that are proofs of that proposition. And if the space is small enough, there's just the one that fits and you're done.
PHILIP: Yes. Well, you might have to figure out which one that is. Agda might not be able to figure it out for you. Sometimes it can. But quite often, you'll have to tell it which one it is. And then it says, "Oh yeah, that works."
REIN: At the same time, isn't that specification? Is there a tension between putting all of that work into specification and it seems like if you over -- I don't know if overspecify is the right word -- but the more finely nuanced the specification is, you're putting a lot of work in there. Are you getting it all back out on the other end when you write the program?
PHILIP: Right. I think there's a sweet spot where if you just write the code or just write examples, it's harder than if you first write the spec and then use that to guide you in what you're doing. And there are tools like QuickCheck that let you check certain properties without proving them. Let's say I'm defining something I know is commutative, I can write a property that says, "F applied to two arguments is the same as F applied to those arguments swapped," and that can generate lots of random arguments and check it for you. That's what QuickCheck does. So just using the property, I can then check the property very quickly. We're proving that property, proving that it's always commutative might be much more work, but I have much higher assurance.
JESSICA: QuickCheck, the nice thing about that is you can use QuickCheck or a clone of it in any language.
PHILIP: That's right. I think writing down parts of your spec is always going to be better. Proving it can be very expensive and isn't for everybody. Generally, you only want to do the proof if it's worth the extra effort and expense of being sure that it always works.
JESSICA: In your text editor in that hour, you didn't prove the specification, but writing it down was incredibly valuable.
PHILIP: Correct, exactly. Even if you don't do proofs, specifications can be helpful.
REIN: What's your sense of someone with a lot of experience with this of where it makes the most sense to spend your effort in writing specifications? Where do you want more detail and where are you okay with more hand-waving?
PHILIP: A good example of where specification helps is compilers. There's a fellow named Xavier Leroy and he wrote out a specification for the C programming language and then a compiler and then he proved his compiler met specification. And somebody else decided to do something very much like QuickCheck. They decided we'll do random testing of compilers. "We'll just generate a bunch of C programs at random and we'll apply CompCert," that was the name of his compiler to the program, "And we'll apply GNU CC and we'll apply...
REIN: Did we mention Clang?
PHILIP: Clang, yes. Because that goes through this other low level machine whose name I forget. But they took all three of those and they just generated random programs and they saw they always gave the same answer. And in that way, they uncovered a large number of bugs that had never been seen before in your GNU CC and in Clang, but none in [inaudible].
JESSICA: That's the thing about QuickCheck. And that style of property test is called...
PHILIP: Property-Based Testing.
JESSICA: Yes. That's got style of property based test. But specifically, that strategy of property-based testing is when you have a known good solution. And so you write a new solution, you compare it to known good solution.
PHILIP: Oh, using a gold solution. Right. In this case, you don't need a gold solution. You can just test different compilers against each other. Maybe none of them is perfect.
JESSICA: Yeah, that's what you find.
PHILIP: But unless they all have the same error, you will find the error. But in this case, they found out that CompCert was perfect. It actually wasn't. I'm oversimplifying. There was an effort they found in CompCert. It was in the bit of it that wasn't proved.
JESSICA: Nice.
REIN: This does get back to the idea that Jess mentioned earlier, which is you know that you meet the specification, but you don't know that the specification says what you think it does. So they had a proof of a compiler that behaved the way the specifications said, but how do they know that the specification is a real embodiment of the C standard?
PHILIP: Well, in this case, the actual C compilers, when they differed from CompCert, it was always the other compiler that was wrong. They looked at it. That was always the other compiler was wrong.
REIN: But that's not a proof...
JESSICA: [Crosstalk] gives you evidence that you've got the right specification.
REIN: Right. That's evidence, but it's not a proof, right? I guess my questions is...
JESSICA: It's an existential proof and it proves that GCC and Clang or whichever one it was is wrong because you've got a case that demonstrates it. Hopefully, you don't need to duplicate that bug in the new compiler just because other users of the compiler have become dependent on it.
JACOB: Is this like arguing about like what's proper grammar in the English language?
REIN: For me, it's not quite. For me, it's if you don't have a type system where you can prove things, then you have all of your work ahead of you. You need to both figure out a way to specify the problem and figure out a way to turn the specification into a system without any help. If you have a language where you can write proofs, you still have half of your work ahead of you. You have to figure out a specification. The specification still has to match to the problem, but then you get help with the rest of it.
PHILIP: You get help and it's a lot more work. It will always be more expensive, I think, always more expensive to do proofs than to just write the code and test it against your specification.
REIN: So I guess my question ...
PHILIP: So, it has to be worth the expense. So places where it's worth the expense are compiler, which is widely used, an operating system. There's a mobile phone operating system called [NCL4] that's been proved correct. In fact, what they did to do that was they wrote out the whole operating system in Haskell [inaudible]. And then translated the Haskell to C by hand and then proved that the translation was correct. Again, using [inaudible]. And so they proved that entire mobile operating system correct in that way. So you can prove large often used systems correct that way. I think another place where we're going to want to be doing proofs is for cryptocurrency because systems like Ethereum, every six months, they lose a few tens or hundreds of thousands of dollars worth of cryptocurrency due to some error in a program. So then all of a sudden, proving it correct becomes worth it. Intel, it costs them, again, I think a few hundred million dollars when they had a chip with an error in it. So after that, they became very interested in doing proofs that their chips were correct.
JESSICA: AWS uses TLA+, I think, to prove some of their algorithms that they use for EC2 in their underlying systems. Very large scale.
PHILIP: I didn't know about that. That's interesting. I should try to read up on that. If you know any papers on that, please send me a link.
JESSICA: Oh, there is a talk at Strange Loop.
PHILIP: Of course there was.
JESSICA: [Chuckles] Of course.
PHILIP: You can send me a link to the [inaudible].
JESSICA: I'll see if I can find it.
REIN: We're talking about specifications in the large, specifying an entire C compiler. When I've worked with these systems, I found a lot of value in specifications very much in the small. So like a thing that might only take a few lines to write, but I want to know that I wrote it correctly and actually writing the type with enough detail makes the implementation fallout in a pretty obvious way.
PHILIP: Yeah, that can often happen.
JESSICA: Most programming winds up making decisions. And if you can get those decisions made at the specification level, writing that out can make implementing and encode a lot easier.
PHILIP: Yes, it's also great I think for documentation. So I mentioned that my textbook exists on a URL. That URL is not a place you can go to buy the textbook. It is the textbook. It's freely available. And one reason for that is because I want you to download and execute it.
JESSICA: Download the textbook and execute it?
PHILIP: Right. The URL I gave you for is the textbook. It's not just a place where you can buy the textbook. And that is the case because you're supposed to download the textbook. It's all an active program, it's a literate active program. And you run it. Or to do the exercises, you modify it and then run it. And writing the textbook in that way turned out to be really great because I know all the bits that are in Agda are correct because if I made an error, it wouldn't type check. So, people are telling me about typos in the book all the time, but they are not in the Agda bit.
JESSICA: [Laughter] That's wonderful.
PHILIP: And then the other great thing about doing it online is it's in GitHub. And when people tell me about -- it used to be people would send me emails saying, "You got this wrong in your paper." But now what happens with this textbook is people send me pull requests. Instead of going back and fixing it myself, I just need to accept the pull request. So I strongly recommend when you write something, do it on GitHub because it lets you collaborate very easily with other people. And then Wen Kokke who helped me write the book, she wrote a little script. So now whenever we accept some of these pull requests, that person's name gets automatically listed, added to the acknowledgement section of the book.
REIN: So Phil, you said sort of you're a bridge between both research and practice and between abstract and concrete. You brought monads to functional programming. What have you learned in the time since you wrote that paper about how to translate abstract concepts so that practitioners can use them?
PHILIP: Well, I've learned lots of people don't like the name Mona, they get scared of it. I think it's really funny that developers tend to get scared of mathematics because it's written in italic. But they're perfectly fine with JavaScript. I find something like JavaScript very scary because of all the special corner cases. And mathematics is much easier to deal with because the whole point of mathematics is you get rid of every single corner case you can. Mathematics is basically about getting rid of corner cases. JavaScript is about the opposite.
JESSICA: JavaScript is a lot squishier, but mathematics is smooth.
PHILIP: Yeah.
REIN: So in the monads paper, your approach, if I remember correctly, was you introduced the model and then you went through case analysis. You presented a number of examples of using this structure in practice. I think state was one of them. Is that the approach you would take today again, if you wrote the paper again?
PHILIP: First thing to say about monads is it was an old idea from category theory. Many people worked on it and then the real insight that it applied to programming languages came from Eugenio Moggi, who wrote a nice paper about applying it to semantics. And I realized, "Oh, we could use exactly the same idea, not just to structure the maths, but to structure our actual functional programs."
REIN: Across the propositions to types bridge perhaps.
PHILIP: I hadn't been thinking in terms of propositions as types then, but later I found out that indeed, remember I said every interesting computing idea has the corresponding interesting logic idea. Somebody else, three researchers at Cambridge wrote a paper pointing out that monads actually correspond to a particular kind of modal logic. That was one of the times I began to understand, "Oh, propositions as types isn't just a cute idea. It applies to lots of important things." So yes, in the paper I gave lots of examples. And one thing I discovered after I wrote the paper is, and people started using it, there were lots and lots of monad tutorials written and generally based on vague analogies, like a monad is like a burrito or something like that. And I found that mathematics, just give a few examples, much clearer than using a vague analogy.
JESSICA: Yeah, because burritos are squishy. And the whole point is you don't have to be squishy with math. You can be precise.
PHILIP: Yeah, like a smooth, polished pebble. So I felt that it was great that people want to write monad tutorials, but I felt that most very often people had done this without going back and reading the original papers that I had written. I felt that the original paper was actually clearer. I wish that some of the people who'd written tutorials had read the original paper first and maybe done things that way. There were few other tutorials that people did that were lots more examples and those were great. Many of them were just based on analogy I think were less helpful than the original work. So it's nice that people want to do it. This is something I got from reading Feynman. Whenever you're doing something, go back and read the original papers. You will learn a lot from them that you won't learn from other people who rewrote it later. So it's really worth going back and reading the original papers.
JACOB: That's something else, it seems like, a lot of developers could learn from because it seems like listening to people who have been in the field a lot longer than me, there's things that we are reinventing now often in JavaScript that it's a problem that's already been solved.
PHILIP: Right. So just doing the literature search before you start in on doing something is always a good idea. If you find something relevant, actually read the paper. You can't read all of everything. No, but you can find the relevant stuff and read that.
JESSICA: And those monad tutorials that are going to pop up, the information that comes to you is kind of random and use that as the tip of a thread and try to go back to the source of the thread to get the start of it. And everything in between will make more sense.
REIN: Monad tutorials for me are all a bunch of blindfolded people describing the elephant. They get a bit of it. They have a particular viewpoint.
JACOB: And of course, if you were wearing a blindfold, you wouldn't know to mix analogies here. You wouldn't know where the original paper is or that you should be looking for it.
PHILIP: So instead of blindfolded people describing an elephant, you should think of people in a dark room describing an elephant and [crosstalk].
REIN: There it is. This has tied it off in a nice bow for us.
JESSICA: Thank you so much for coming on the show.
PHILIP: Thank you guys. I really enjoyed this. Thank you very much for inviting me.
REIN: Thank you so much for your time. It was great to meet you.
PHILIP: Thank you very much.
REIN: I have a reflection. We've been talking a lot about mathematics, what's it good for, why are people so afraid of it. I mentioned when we were looking at how proof assistance worked, that there is still an opportunity for human creativity even as you're doing this rigorous process. And I think one of the issues with mathematics is that the way we're taught it makes us hate it. There is a great book called A Mathematician's Lament by Paul Lockhart, which describes in part how the education system doesn't really show people what math is. It just shows you, for example, geometry isn't about shapes. It's about rigorously putting things line by line until you have a proof. Whereas math, for me, even in my own limited experience is a highly creative pursuit. You get to be very, I don't know a better word than creative. It's a field that isn't rigorous to the extent that you can't have fun or to the extent that you can't create, find new ideas. It's not boring. It's not about numbers. It's not about the way you were taught in high school. It really is a fun, creative field.
JESSICA: You can slice those zombies in lots of different ways and you never know what shape they'll come out. Thank you, Rein. One thing that I latched onto was the books on the Foundations of Programming Languages by, you mentioned Benjamin Pierce and yours. There's a difference between learning the foundations of programming and learning the skills of programming. So some people are just like, "What does this have to do with what I'm doing? I write JavaScript and I should just learn more about JavaScript." Okay, that's a skill. But underlying that are foundations of how programs work at all and how we can think about them with precision and clarity and also those specifications that communicate to people as well. So there is something to go back and look at foundations and that kind of understanding is separate from skills.
PHILIP: Yep. That's fair.
JESSICA: Chante, did you have a reflection?
CHANTE: Yeah, I'm still here. And here's the thing, I'm the one of those people that hates math. And so, this conversation frankly felt a little exclusive. But here's my reflection on that or my question rather for the group is how do we make conversations like this more accessible and inclusive for people who maybe have a phobia or who perhaps have learning disabilities or things like that that they're like, "This is just way too technical." How do we make it more human? How do we invite people in? And like Rein was mentioning, how do we demonstrate and remind people that it's creative, that math can be really fun. I don't have an answer, but I would love to hear what the group is thinking.
PHILIP: I think by you saying math can be really fun. That really is an important thing to say. And you were talking about being exclusionary. There are lots of people who feel that math is not for them. And I think it's important to do a lot to say, "Well no, actually it is for you too if you approach it the right way." I think most people can appreciate and enjoy and use math, all of those things. But many people feel that they can't, which is too bad. I also wouldn't say that you shouldn't be left in there computing if you don't like math or if you don't want to do math. There are other important things as well, like writing good documentation. You'll always write better code if you know math. But there are other things like writing good documentation that aren't necessarily about knowing the maths.
CHANTE: Yeah. And the other interesting thing here is like, I'm thinking about just sort of society and like how we think about the future generations to come and how they're going to maybe get into this field. And so as we have more advances in technology that in some ways make our human brain a little bit more lazy and give us a pass, how do we kind of maintain this purity in the math that you're kind of discussing here today. Because I feel like it's really advanced and there's a beauty to it. I don't understand it, but it's really interesting and complex. So what's going to happen to the future of education and the students who have newer technologies to say, "I don't want to do that."
PHILIP: I think the new technologies will make it easier rather than harder to teach math.
CHANTE: I hope so.
JESSICA: A big part of advancing as a society is finding better ways to teach things so that it takes less overhead to learn what we already know and you can build on that to make more.
PHILIP: Right now, functional programming and maths are very much minority streams in computing. I'm hoping that if you look at things 50 or 100 years down the line, and it is important to have that kind of long-term perspective that we will find more people trained in these things. It's less of a minority thing and more of a majority thing.
REIN: If you follow the Programming Language Foundations in Agda book, you are learning math as you do that because propositions are types, but types are also propositions.
PHILIP: Yup, absolutely. It's a math textbook, but it's also a programming textbook. If you like programming, I hope you can follow it, but you'll also learn maths along the way. Hopefully, painlessly.
JESSICA: Because lots of us, Jacob, tell me if you're in this category, have learned skills of programming and it's not too late. In fact, you're in a great place having learned the skills and found programming useful and wanting to get better at it. It's a great time to go pick up some foundations.
JACOB: Yeah, that's right.
REIN: It's a bridge back from programming to math.
JACOB: It's true. I don't have a CS background and so I've learned a lot. I've learned plenty of skills with programming and then I see over here people on Twitter or whatever talking about or in this conversation talking about these really interesting things. And yeah, there's a switch in my brain that says, "Oh well, I'm just going to have to draw a wall around that because that's not for me." And yeah, this conversation is making me think about like, "Oh, there's no reason there needs to be a wall there. It's just something I don't know about yet." The other thing I was thinking about is like having the ability to get a really quick seamless feedback as you are talking, as you are writing your program because again, what my common experience is when I write a program in Ruby for example, it's to flip over to my terminal, run the test and then see what happens. But the thing is no matter what kind of test and writing, there's always going to be an indirect way for getting feedback because there's always some way or in between what I wrote and what I get back. But when I can type and literally as I am typing, find out if what I'm saying actually makes sense, then I feel like that is just such a much better way to interact with my program or the program that I am building. And yeah, I want to be thinking about like how can I find ways to be getting instantaneous feedback like that because I think that can really aid in the way that I think and interact with my program.
REIN: Jacob, the thing you're describing is a joint cognitive system. It's you and the computer working together.
JACOB: That is a great word for it.
REIN: There is a book called Joint Cognitive Systems.
JACOB: Is it about software...
REIN: It's about complex systems that include humans where humans and those systems work together to do things. So, for example, a pilot in a cockpit is a joint cognitive system.
JACOB: Yeah. And then that's a question like, I would really hope that that joint cognitive system is going to be very seamless. [Chuckles]
JESSICA: You would hope.
JACOB: Yes.
REIN: It's a way to reframe the traditional human machine model that came from Shannon where you say a thing to a computer and then it thinks, and then it says a thing to you, and then you think, and then you say a thing to a computer where it's more about you and the context, the machine, the computer, whatever it is. You as a part of the system, working together in a cycle of receiving feedback then acting on it to change things and so on to achieve goals.
JACOB: Yeah. Thanks for listening to our episode of Greater Than Code. We invite you to support us on Patreon to keep this show going. Even visit Patreon.com/GreaterThanCode.