Data Abstraction

In 1971 Liskov left Mitre and joined the MIT (Massachusetts Institute of Technology) faculty as a professor in the Laboratory for Computer Science. It was there that she worked on all the ideas that led to her Turing Award starting with Data Abstraction, recognised as a powerful technique that can be used to improve the quality, maintainability, and reusability of software. It is one of the most important concepts in computer science, and it is used in virtually all modern programming languages.

According to her own account the idea came out of nowhere but she immediately saw its importance and how it fit the idea of modularity and in the spring of 1973 she started working on it jointly with Steve Zilles and together they published the paper "Programming with abstract data types" and submitted it to the Conference on Very High Level Languages. This highly influential paper posited that abstract data type (ADT) is a data structure that is defined by its behavior, rather than its implementation which means that the user of an ADT does not need to know how the data structure is implemented internally in order to use it. This makes ADTs easier to use and understand, and it also makes them more flexible and reusable. 

CLU Programming Language

Liskov then began to think about what a programming language that allowed users to define new data abstractions would be like, and this led to the project on CLU - pronounced "clue" although the name came from the concept of a cluster, which was CLU's type extension system and corresponds generally to the concept of a "class" in an OO language. While CLU did not find extensive use, it introduced many features that are used widely now, and is seen as a step in the development of object-oriented programming (OOP). As well as abstract data types, key contributions include  call-by-sharing, iterators, multiple return values (a form of parallel assignment), type-safe parameterized types, and type-safe variant types. It is also notable for its use of classes with constructors and methods, but without inheritance.

In this video snippet Liskov explains how Lisp, the language designed by John McCarthy for AI programming, influenced CLU and how this made it different from another emerging language, Alphard being developed at CMU (Carnegie Mellon University) by Bill Wulf and Mary Shaw.

Distributed Computing

Looking for a new field of interest around 1980 Liskov started thinking about ARPANET (Advanced Research Projects Agency Network), which had been developed in the late 1960s and early 1970s and was the first wide-area packet-switched network with distributed control.  She read a paper by Bob Kahn, where he described the vision of distributed computing: there would be a system built of components that ran on different computers and communicated through a network and realized it would be a good area for research. Her first project was to design and implement a new programming language, called Argus, that would support  programs on remote machines. Argus was an extension of CLU in which programs were made up of objects called guardians with each guardian resides entirely at a single computer and communicating with others by making remote procedure calls to one another’s operations.

Liskov's subsequent research was mainly been in the area of distributed systems and has covered many aspects of operating systems and computation, including important work on object-oriented database systems, garbage collection, caching, persistence, recovery, fault tolerance, security, decentralized information flow, modular upgrading of distributed systems, geographic routing, and practical Byzantine fault tolerance. Many of these, like Byzantine fault tolerance, deal with situations where a complex system fails in arbitrary ways and Liskov developed methods to allow correct operation even when some components are unreliable.

Liskov Substitution Principle

As formalized in 1994 in a paper co-authored with Jeannette Wing, the Liskov Substitution Principle (LSP) characterizes when it is safe to substitute an object of a subtype for an object of the parent type, thus preventing strange behaviors when the program is run. However it was several years earlier that Liskov came up with the idea of "behavioral subtyping". As explained in this video snippet, Liskov was invited asked to give a keynote at OOPSLA (Object-Oriented Programming, Systems, Languages & Applications) one of the ACM's annual research conferences and decided that this was a good opportunity to learn about what was going on in object-oriented languages, in particular the work being done on Smalltalk by Alan Kay and Adele Goldberg. By reading the papers on it she discovered that hierarchy was being used for two different purposes. The first was simply for inheritance. The second was for type hierarchy where the idea was that the superclass would define a supertype, and then a subclass would extend this to become a subtype. The papers showed there was a lot of confusion around this and prompted Liskov to ask: 

“What does it really mean to have a supertype and subtype?”

She came up with an informal rule which she presented in her keynote at OOPSLA which simply said that a subtype should behave like a supertype as far as you can tell by using the supertype methods.

Also in this video she recalls with amusement that sometime in the ’90s she I received an email from someone asking, “Can you tell me if this is the correct meaning of the Liskov substitution principle?” and that was the first time she had any idea that this name had developed. She goes on to say:

"I discovered there were lots and lots of people on the Internet having arguments about what the Liskov substitution principle meant. So it was nice to have something that had an impact like that."