Ryan Peterman · Ryan Peterman · Transcript & summary by WhipScribe
In nine minutes a Turing Award winner tells, first hand, where the Liskov substitution principle came from and why her replication protocol lives in Paxos's shadow.
Tap a chapter to open that moment in the transcript; the link to it is copied for you.
“That's when I discovered that there was such a name.” Barbara Liskov · at 7:59 — open in the transcript →
“So what Leslie says is, I went around giving all the talks and she implemented it.” Barbara Liskov · at 8:40 — open in the transcript →
Barbara Liskov, the Turing Award-winning MIT computer scientist, explains to Ryan Peterman how one of the most cited rules in object-oriented design came out of a disagreement about meaning. Smalltalk and the languages built on it had inheritance, and their authors wanted a subclass's type to relate somehow to its parent's type, but they described classes by how their code differed from the superclass. Liskov, who thought of modules through their specifications, said the relationship is about behavior: a subclass must act like its superclass wherever the superclass is expected. She worked that out while preparing a keynote for the object-oriented programming conference around 1986, later formalised it with Jeannette Wing as behavioral subtyping, and only discovered the label 'Liskov substitution principle' in the 1990s when someone emailed asking her to confirm an interpretation of it.
The specification-first habit came from teaching. A course she built at MIT with John Guttag trained students to reason about what a module means before worrying about how it is implemented, which set her apart from the implementation-minded West Coast Smalltalk community. With no internet yet, her CLU group, the Alphard team at Carnegie Mellon and the Smalltalk researchers worked in parallel streams that barely talked.
The same pattern of independent discovery shows up in her distributed systems work. A paper by Bob Kahn on programs split across networked computers drew her to the field, leading to Argus, a language that ran computations across nodes as atomic transactions. Her Viewstamped Replication turned out to be essentially the same idea as Leslie Lamport's Paxos; Google engineers believed they were using Paxos in the Google File System. Liskov and Peterman agree that Lamport's talks, papers and catchier name explain why his version is the famous one.
Turing Award-winning computer scientist at MIT who designed the CLU and Argus languages and developed Viewstamped Replication. The Liskov substitution principle is named after her.
Barbara Liskov told Ryan Peterman she never named it herself. She described the idea in a keynote around 1986, and only in the 1990s, after the internet arrived, did she get an email asking whether a certain interpretation of 'the Liskov substitution principle' was correct. That message is how she learned the name existed, and how she realised the idea had become important.
Barbara Liskov says the principle is about behavior, not shared code: a subclass has to behave like its superclass whenever it is used in a place where the superclass is expected. She arrived at it because Smalltalk-era papers wanted subclass types related to parent types but could not say how, since they described classes by their implementation differences.
Yes. Barbara Liskov says her Viewstamped Replication and Leslie Lamport's Paxos are essentially the same idea, developed independently without the two ever working together. There are small technical differences in the details, but she calls them basically the same system.
Barbara Liskov recounts Leslie Lamport's own explanation: he went around giving the talks while she implemented the protocol. She agrees there is something to that, since Lamport gave many talks and wrote several papers on Paxos. Ryan Peterman adds that Paxos is a catchy name, and Liskov agrees it is a cute one.
Argus was Barbara Liskov's first distributed computing project, an object-oriented language strongly influenced by her earlier language CLU. Its key object, the guardian, was a module living on a single computer, and guardians talked to each other through remote procedure calls. To make a computation spanning several guardians either finish completely or leave no trace, Argus ran it as an atomic transaction, an idea Liskov borrowed from databases.
Barbara Liskov says she read a paper by Bob Kahn, whom she credits with Vint Cerf as a founder of the internet, describing his dream of programs made of pieces on different computers linked by a network. Nobody knew how to build such programs, and she was looking for a new problem, so she moved into the field.
Barbara Liskov says a course she developed at MIT with John Guttag taught students design, modularity and data types, and also how to write specifications and reason about correctness. Its emphasis on understanding what a module means first, with the implementation hidden inside, is why she could define subtypes by behavior when the Smalltalk community was focused on implementations.
Our own transcript of the public episode, with a timestamp about every 90 seconds. Tap a timestamp or the link button on a paragraph to copy a link that opens this page there.
0:00What got you into distributed computing? I read a paper by Bob Kahn, who was with Vint Cerf considered to be the founders of the Internet. And Bob talked about his dream of distributed computing, where you would have a program composed of pieces on different computers connected by a network. And nobody knew how to build those programs. And so I just thought, great problem. And I was looking for a new problem, so I jumped into distributed computing. And the first project was actually a programming language to write distributed programs in. And then I started looking at other problems in the distributed systems area. What was that first programming language? And then I started looking at other problems in the distributed systems area.
0:45What was that first programming language? It was called Argus. It was very strongly influenced by Clue. It was an object-oriented language. It had a special kind of object called a guardian, which was a module sitting at a single computer. And then guardians could communicate through remote procedure calls. One of the things you run into in distributed computing is if you have a computation that starts at one guardian and then makes use of other guardians at other nodes in the network, in the end, you want that computation to either complete entirely or have no effect at all. And how do you do that? Well, I borrowed the notion of transactions coming out of the database field. And that was part of how Argus worked.
1:37It ran computations as atomic transactions. Oh, interesting. Like distributed transactions across those nodes. the internet stored at multiple sites with correct behavior and always accessible as long as enough nodes are up and running and the network is working. I see. And what is view stamp in this context? Oh, that had to do with some details of how the system worked. And it was a way of noticing when some nodes failed and other nodes had to take over, you could figure out which ones had the most recent state in them so you could pick up and not lose anything that had happened in the past. What if the clocks are out of sync? It had nothing to do with clocks because it was just numbers. In other words, we
2:44were in view 25, the next view was 26. Oh, okay. Just incrementing some number that's passed around. Yeah. This reminds me a lot of Leslie Lamport's work. Actually, yes. Did you ever work with him? No. Leslie and I developed what is essentially the same idea independently. And he had the system he called Paxos, and I developed what is essentially the same idea independently. And he had the system he called Paxos. And I had this thing called view stamp replication. Oh, interesting. And they're essentially the same thing. They are, yeah. Are there pros and cons of the two approaches? Yeah. I mean, when you do this kind of system, there's lots of little details you can play around with. So you could decide to do... It gets technical, but there's tiny differences. But no,
3:38they're basically the same. In fact, what happened was the first time that I'm aware of that this was actually used in a real system was when the Google file system came along. And one of my former students who was, I think he was a consultant at Google, looked at what was going on in there and he said, oh, he says that's FUTAMP replication. So the people at Google seemed to think it was Paxos, but in fact, they are the same system. I also noticed like when you were, when you came up with abstract data types, maybe it's just because the internet wasn't there, that there was also the object-oriented stuff going working on Clue. And then at Carnegie Mellon, Bill Wolf and Mary Shaw were working on Alfard, which was another data abstraction language. And you're right, there was
4:32no internet, although there was the ARPANET. But it was like there were two independent streams of research going on, and we weren't talking to each other. And so I wasn't paying much attention to small talk. And on the West Coast, I don't think they were paying much attention to data abstraction. And this led to the Liskov substitution principle, which, I mean, the story is a sort of acute one because in 1986, I think it was, I was asked to give a keynote at Uppsala. Uppsala is the object-oriented programming conference. And this was the second year it was happening. And so I decided, I think I'll read all those papers about Smalltalk. And there were other languages being developed that were based on Smalltalk and see what's going on with them. And I discovered, so Smalltalk has this idea of inheritance in it, where you can have a class
5:31and a subclass, which borrows from the way the class is implemented and changes it a bit. And Clue doesn't have that. Clue just has what we call clusters, and they're all independent. So I saw that they were talking about this notion of classes and subclasses. And then I saw that they were also talking about something they call type hierarchy, where they wanted the type implemented by a class to be related in some way that they didn't understand to the type that was implemented by a subclass. I really thought about modules in terms of their specifications. This partly had to do with a class I developed at MIT that I developed jointly with my colleague John Gutag. And in that class we taught the students how to do design, about modularity, data types, and so forth, but also how
6:25to write specifications, how to reason about correctness. And so it had a big focus on think about the meaning of things first, and the implementation is something that's kind of hidden inside and you don't worry about it very much. And so that was a different way of thinking about things than what was going on on the West Coast, where they were really thinking in terms of classes and subclasses. And I even saw papers where they would describe the behavior of a class by explaining how its implementation was different from the implementation of the superclass. So they were kind of focused on implementations in a way that we weren't. And so when I read these papers about type hierarchy and I saw they just couldn't figure out what it was
7:12supposed to mean, I was thinking about it from the terms of meaning. And so I was able to say it has to do with the behavior. And this subclass better behave like the superclass if you use it in an environment where the superclass is expected. And that became what ended up being called the Liscaw Substitution Principle. And ultimately, Jeanette Wing and I wrote a paper on behavioral subtyping, which is the formal definition. And then how did it get that name? Because you didn't go off on stage and say, hey, everyone, here's the Liskov. No, no. But no, as I said, one day in the 90s after the internet had arrived, I got an email saying, can you say if this is the correct interpretation of the Liskov substitution principle?
8:00That's when I discovered that there was such a name. And I don't think I had really been aware of how important it was until that point, because I wasn't thinking about this stuff. I was working on other stuff. In the academic community, it seems very reasonable to have multiple people have similar ideas, but it seems like some ideas stick more than others. For instance, like the view stamp replication versus Paxos. They're the same thing. I'm wondering, like in that case, for instance, why would Paxos be more known than view stamp replication? Yeah. So what Leslie says is, I went around giving all the talks and she implemented it. Really? Something to that. Then he got notoriety for speaking about it.
8:58Yeah, he did give lots of talks about it and wrote several papers and so forth. And I didn't realize it was the same system, but finally it became clear that they were the same system. I also wonder how much the name matters because Paxos is kind of catchy. It is a cute name. It's a cute name. Yeah. Right. So I could see maybe it has better marketing around the idea, I guess.