A stack has a useful rule: the last item put on is the first taken off. A program can use that rule without knowing how the items are stored. Barbara Liskov’s work on data abstraction helped make that separation a practical way to build software, supported by a language rather than left as an informal promise.
Her name also appears in SOLID, a set of five object-oriented design principles: its L stands for the Liskov Substitution Principle. (Robert C. Martin, “Solid Relevance”.)
Finding a way into computing
Liskov was born in 1939 and studied mathematics at Berkeley, graduating in 1961. Programming work at Mitre helped draw her into computing. She completed a Stanford doctorate in 1968, returned to Mitre and worked on the Venus operating system before joining MIT in 1972. The Computer History Museum’s career account traces how building software informed her later research.
An operating system combines many interacting responsibilities. Being able to understand and change one part without inspecting everything else is a practical need, not just a tidy way to arrange a listing. Liskov and her collaborators investigated what a language could do to support that kind of reasoning.
Operations define the type
In their 1974 paper Programming with Abstract Data Types, Liskov and Stephen Zilles describe a type through the operations available on it. A stack, for example, offers ways to put an item on, take one off and test whether it is empty. The calling program uses those operations; the representation belongs inside the implementation.
Imagine changing an implementation from a fixed array to linked records. If the promised behaviour is preserved, the rest of the program need not learn the new arrangement. That makes the boundary useful when checking and changing software. The paper’s operation clusters, or “clusters”, put the type and its operations together while restricting access to its representation. (Liskov and Zilles, pp. 50–59.)
Making the boundary work
Liskov led the MIT group that developed CLU. In her history of the project, she names Russ Atkinson, Craig Schaffert and Alan Snyder as the other principal language designers, with further collaborators contributing to design and implementation. Zilles helped establish the early ideas and then concentrated on specifying abstract types.
CLU’s iterators let a program visit a collection’s items without exposing its storage. Liskov credits Atkinson with their design in 1975, inspired by work on the Alphard language. A collection could provide its elements one at a time, avoiding a separate copy of the entire collection. (A History of CLU, sections 3.2 and 3.10.)
Her subsequent work included Argus, a language for distributed programs. Once parts of a program run on different computers, communication and partial failure become part of its design. MIT’s account also records later work on fault-tolerant systems. Her 2008 Turing Award was announced in March 2009.
The L in SOLID
The Liskov Substitution Principle concerns what a program can safely expect from a type. A subtype is a more specialised type that can be used in its place. To be a valid substitute, it must preserve the behaviour promised by the original type.
Consider a routine that uses a stack. It expects the last item added to be the first removed. A supposed subtype that removes the oldest item instead would break that promise, even if its methods had the expected names. The program needs the agreed behaviour as well as the right operations.
Liskov and Jeannette Wing gave behavioural subtyping a formal account in their 1994 paper A Behavioral Notion of Subtyping. They required properties established for objects of the original type, the supertype, to hold for its subtype objects too. Their work addresses the reasoning behind safe substitution. The principle later became the L in SOLID, connecting Liskov’s research with everyday software design. (Liskov and Wing, introduction; Martin, “LSP”.)
Margaret Hamilton’s flight-software history examines recovery under different constraints, while Grace Hopper’s tools reduced other kinds of repeated programming work. These connections help locate abstraction within the wider history of women’s contributions to computing.
Sources
- Barbara Liskov and Stephen Zilles, “Programming with Abstract Data Types”, 1974, pp. 50–59, DOI 10.1145/942572.807045. Primary paper, publicly accessible mirror: operations, representation, clusters and worked examples.
- Barbara Liskov, A History of CLU, MIT/LCS/TR-561, April 1992, sections 3.2 and 3.10, and Appendix B. Primary participant history: named designers and implementers, iterators and their relation to Alphard.
- Computer History Museum, “Barbara Liskov”, 2023 Fellow. Museum career account: education, Mitre, Venus, MIT and collaborative language development.
- MIT, “Barbara Liskov wins Turing Award”, 10 March 2009. Institutional account of CLU, Argus and fault tolerance; distinguishes announcement date from the 2008 award.
- Barbara H. Liskov and Jeannette M. Wing, “A Behavioral Notion of Subtyping”, ACM Transactions on Programming Languages and Systems 16(6), November 1994, pp. 1811–1841, especially the introduction and section 2, pp. 1811–1814. Primary research paper: behavioural requirements for subtypes. The stack-order example above illustrates the principle rather than reproducing the paper’s bag/stack example.
- Robert C. Martin, “Solid Relevance”, 18 October 2020, “LSP” section. Primary account identifying the substitution principle and its place within SOLID.
- National Inventors Hall of Fame, “Barbara Liskov”. Biographical corroboration, including birth year and MIT appointment.