Turing Award Winner: Data Abstraction, Dijkstra, Distributed Systems | Barbara Liskov

0:00Don't do incremental work. This is Barbara Liskov. She's a Turing Award winner famous for her fundamental contributions to programming languages and distributed systems.

0:10Barbara Liskov:Encapsulation is a crucial part of making modularity work. Your team is really only as strong as your weakest programmer. I asked her for stories from her career. That paper was the go-to statements considered harmful. Is Dykstra in person also like his writing? He was not always as tactful as he might be. There were people saying, why did she get the Turing Award? Why do you think that they said that about your work? Here's the full episode.

0:46You applied to multiple places, and Princeton was one of them, and they had rejected you on the grounds of you being a woman. How did you get into programming in an environment that's so hostile?

1:00Barbara Liskov:Okay, so this was when I got my bachelor's degree. And I applied to several graduate programs in math, which is what I majored in as an undergraduate. And I got this little card back. It was a postcard from Princeton saying, we do not admit women, which was surprising. I knew they didn't have women in their undergraduate program, but I hadn't realized it extended to the graduate program. But, you know, it was how it was. So what happened was I did get into Berkeley, which is where I did my undergraduate work, but I decided I really wasn't ready to do a PhD in math and that I should get a job instead and just sort of see how things were.

1:50Barbara Liskov:And the best job offer I got was as a programmer. So that's how I got into computer science, by a happy accident. You were consistently, at least at Berkeley, you were consistently a top student. So it is odd that you wouldn't even get an opportunity to play in some cases. But that's how it was back then. It was just, I hadn't realized it was more than an undergraduate thing. And Berkeley was co-ed. So, you know, there, what I found was there weren't very many women in my classes. There were lots of women students, but very few of them majoring in math. And there were only maybe a couple of women in my classes.

2:35Barbara Liskov:But the idea that a door was shut and women couldn't do things, that was not what went on at Berkeley. So it was a different environment. Of course, nowadays in the top schools, the women are about 50 % in computer science. I want to talk about some of the core problems that you're solving in your career. And so I understand that there's the software crisis in the 1970s. And I was wondering if you could give the context behind what the problem was at that time. Well, it was a huge problem at the time because people did not know how to build big programs that worked. And so you would often pick up the newspaper and see an article about some company that had spent millions of dollars and hundreds of man years developing some software system for their company.

3:36Barbara Liskov:And then in the end, they'd have to throw it away because it simply didn't work. The problem was that to get a big program that works, you need modularity. And you need to break your program up into small pieces. Each piece provides an interface with a hopefully complete description of what service it provides for you. And then inside is an implementation that's hidden and nobody pays any attention to it on the outside. modified. And if you have a system organized like that, you can actually reason about its correctness one module at a time. But in those days, people didn't know how...they couldn't figure out how to design systems that were modular.

4:24Barbara Liskov:And the only kind of modularity mechanism present in programming languages was a procedure. And procedures didn't match the kinds of modules you needed. Because if you think about a file system or a database or Amazon or whatever, they aren't a procedure where you put something in and get something out. They're a much more complicated thing. So there was no notion of a module that sort of matched the kind of things that people were looking for. So when you saw that problem, what were the early solutions like? Well, so people were proposing modularity and they were talking about how important modularity was.

5:09Barbara Liskov:They didn't exactly know what a module was. And so it wasn't like they could give you a rule, this is a module. It was just a chunk of code. In fact, there were papers written that talked about how big a module should be and stuff like that, just a chunk of code. That's not going to work because you need to design these systems. So you need a way of thinking of a design that sort of fits into this notion of modularity. They also didn't really know what the rules should be for modularity. And it turned out that in some of the early work I did after grad school when I was working at MITRE, I had already invented a notion of modularity that was sort of more complete than what people had been talking about.

5:52Barbara Liskov:Just because I had a small team of programmers, we were building a complicated system. and I wanted to keep us out of trouble. And so I had that sort of sitting there when I started to work on this topic. And it enabled me to see this idea of data abstraction. All of a sudden, I sort of saw that this thing I had, this kind of modularity mechanism, which consisted of basically what I just described, a bunch of code providing you with an access through a number of what I called operations. So you could call it in various ways and then inside was all hidden and whatever data it was using was not accessible to the outside.

6:37Barbara Liskov:And then at some point I saw I could see this as a data abstraction. It could be a set, it could be a sequence, it could be, you know, and so forth. And that meant we had a new type of module. Now, when I look back at the papers from the time, I see that idea is almost there, except people hadn't managed to pick it out. And so it was probably, I think this happens in science a lot. There's sort of a time when an idea is ready, and I happened to see it. You pieced these together, and you put it into the CLU programming language that you're working on. How did you see it influencing the industry?

7:17Barbara Liskov:The first thing that happened was I wrote a paper with a man who was a graduate student at MIT, Steve Zillis, about this idea of data abstraction. And it sketched a notion of what abstract data types would be and how a programming language could support them. And this was a very impactful paper. And so there was a big impact on the research community. And then Clue came along, and that involved a lot of additional research in the programming language area. The next thing that happened, so people were watching this in the research community, but of course, people who are in companies that want to write programs, they need a programming language.

8:04Barbara Liskov:and I decided I wasn't going to try and turn Clue into a product because that would have required working in a company. In those days, you didn't just put software out on the internet and people used it. There wasn't an internet yet, for one thing. And I was much more interested in doing research than in, you know, working in a company. So I put Clue on the side. It had a user base, But for companies to use a programming language in those days, they wanted a company behind that language. The next thing that happened was the government put out a call for a programming language they could use. This led to the ADA programming language.

8:49Barbara Liskov:So, you know, that was already a big impact if you think about it. There was a language explicitly being designed to have data abstraction in it. And then finally in the 90s, Java came along. I thought it'd be interesting because you worked on Clue. You designed that programming language to ask you about other programming languages. You said somewhere that there's something wrong with Python. I was curious to hear your thoughts of why. Python has modules, but it doesn't have encapsulation. So it allows code on the outside to muck around with what's going on on the inside of a module. And that's all I was talking about.

9:29Barbara Liskov:Encapsulation is a crucial part of making modularity work. And when you're building big programs, so you have many programmers working on them, your team is really only as strong as your weakest programmer. So it's nice if the compiler can enforce things and make certain kinds of bad behavior not possible. I mean, Python has another intended use. It's helping naive programmers learn quickly how to write programs and stuff like that. And people in the programming language world do think about issues like this, like how to make languages safer and so forth. But since I stopped working in that area, I'm no longer an expert in programming languages.

10:17What got you into distributed computing?

10:19Barbara Liskov: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?

11:05Barbara Liskov: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 compute, 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.

11:52Barbara Liskov:And that was part of how Argus worked. It ran computations as atomic transactions. Oh, interesting. Like distributed transactions across those nodes. Yeah, yeah, yeah. And I think it led right into the work I did on view stamp replication, which was that was the beginning of cloud storage. I was thinking in terms of a file system, but it doesn't really matter what it is. You know, how do you have data out on 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 ViewStamp in this context?

12:35Barbara Liskov: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 were 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?

13:17No.

13:17Barbara Liskov:Leslie and I developed what is essentially the same idea independently. And he had the system he called Paxos, and I had this thing called U-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, they'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.

14:02Barbara Liskov: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 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 on on the West Coast. Yes. Alan Kay was developing Smalltalk at the same time that I was working on Clue. And then at Carnegie Mellon, Bill Wolf and Mary Shaw were working on Alphard, which was another data abstraction language.

14:48Barbara Liskov:And you're right, there was no internet, although there was the ARPANET. So we did. 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 OOPSLA. OOPSLA is the object-oriented programming conference, and this was the second year it was happening.

15:32Barbara Liskov:And so I decided, I think I'll read all those papers about small talk, and there were other languages being developed that were based on small talk, and see what's going on with them. And I discovered, so small talk has this idea of inheritance in it, where you can have a class and 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 and understand to the type that was implemented by a subclass.

16:23Barbara Liskov: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 Guttag. And in that class, we taught the students how to do design, about modularity, data types, and so forth, but also how to 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.

17:09Barbara Liskov: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 supposed 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 Liskov substitution principle.

17:52Barbara Liskov: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? That'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.

18:31In 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?

18:57Barbara Liskov:So what Leslie says is, I went around giving all the talks and she implemented it.

19:07Barbara Liskov:Really? Something up to that. Then he got notoriety for speaking about it. Yeah, 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. Yeah, right. So I could see maybe it has better marketing around the idea, I guess. I also think that this approach to solving this problem, which both Leslie and I picked up independently, in my case, came from the work I'd been doing with transactions.

19:52Barbara Liskov:because in transactions, there's a leader that says, now we're going to commit and asks everybody, can we commit? And if they all say, okay, but unlike in transactions, in transactions, if the leader fails, there's what's called, this can be a real problem. Here, we had to have a way of moving to a new leader if the old leader failed. And that's the big step forward that happened in both view stamp replication and Paxos. Now, there was also Byzantine fault tolerance, which came along later, that was developed. So view stamp replication, I developed with my student, Brian Occhi. It was his PhD thesis.

20:35Barbara Liskov:And then Paxos, I developed with my student, Miguel Castro. It was his PhD student thesis. And Miguel got interested in this problem because there was a DARPA request for proposals, and there was one about this problem on the internet. By then, there were Byzantine attacks and malicious attacks and nodes that were purported to be working correctly, but actually they had been compromised and so forth. And so view stamp prolification in Paxos only handled crashes, and if there were messages that had been played with, you could tell when they arrived that they were bad. And that was about the extent of what we dealt with.

21:20Barbara Liskov:But these malicious attacks with nodes that purported to be working when they weren't, that was a big step forward. And Miguel saw this request for proposals and he said to me, why don't we see whether we can come up with a protocol that works in the presence of Byzantine attacks? And I think, by the way, Leslie is the one that invented the word Byzantine to - I think he did. Yeah, right. I saw in the software crisis stuff, there's the paper with Dykstra that you had mentioned was one of the papers you wrote that said we need modularity. And that paper was the go-to statements considered harmful.

21:59Barbara Liskov:Right. And I'm curious because Dykstra, I mean, when I was studying computer science, we all know his name. Did you ever meet him or work with him? Oh, yeah, many times. I never worked with him, but I did meet him multiple times. And, you know, he had very interesting ideas. And that paper, Go-To Statement, Consider Harmful, it's not actually a paper. It was a letter to the editor of the communications of the ACM. But it was very impactful. And what was really important about that paper was that Dykstra was talking about how difficult it is to reason about the correctness of code. And this was at a time when in the sciences, computer science was kind of dismissed as nothing much and anybody can write code.

22:53Barbara Liskov:And, you know, Dijkstra was trying to make a point, which I think was actually important, that it's not as trivial as you think it is. It's not trivial at all. And he was also pointing out that go-to's can be misused. And it was controversial at the time. It was, yeah. But today, I've written code for over a decade. People don't use go-to. I haven't even seen a go-to in the code. So why was it controversial at the time? The programming languages were different then. First of all, there were people writing programs in Assembler. In Assembler, you have to use go-to's. programming languages didn't have some of the constructs in them that we think of today.

23:40Barbara Liskov:And so some people were using go-tos because they had to. And also compilers didn't do all the kinds of optimizations that they do today. So there was a concern if you didn't have go-tos, maybe your program wouldn't be efficient enough. And then there were people who used go-tos and wrote really good code and they were offended that Dijkstra was saying your code is bad. So there was a whole but, and Dijkstra was not the most diplomatic person. So, you know, so he didn't write it in a nice, you can imagine writing that paper more nicely where you said, so that, but there were many reasons why it was controversial.

24:26Barbara Liskov:You know, people were offended, but then there were also concerns about programming languages don't have these features I need. What am I supposed to do? And then there were concerns about what the compiler was doing. And so the world is very different now. But clearly Dykstra won the day because no go-tos. And is Dykstra in person also like his writing? He was not always as tactful as he might be. But, you know, he was a very distinguished researcher. Computer science has had such a huge impact on the industry. Why did you choose to stay in academia instead of going into industry? So I like doing research.

25:18Barbara Liskov:And I enjoy working with students. and teaching was never my favorite thing, but I always felt teaching and research were very closely connected. But also it was a different time. So this business about how professors are all forming companies and so forth, which goes on today, that wasn't happening 20 years ago, or maybe it was happening 20 years ago, but 30 years ago it wasn't. And so when I was young, it wasn't the thing that you did. It was sort of an either or sort of thing. So I wasn't even thinking about doing stuff like that. I did work in a startup briefly at the end of the 90s. I didn't like it.

26:05Barbara Liskov:I much prefer doing research. And as a professor, you have this, it's a gift and a curse. The gift is you can do whatever you want. The curse is you have to figure out what it is that you're doing. But I like that freedom and the fact that I just could go off in any, I mean, my career is full of these interesting zigzags where I would switch to something else. I had the freedom to do that. What stops you from going off in a very useless direction? You won't get tenure. Who's the judge? The community. Yeah, it's not, you know, what the way that you're viewed at your university has mostly to do with one very important facet of it is how are you viewed in your research community?