Barbara Liskov by @SebastianNavasF

Barbara Liskov — Inventor of Abstract Data Types

She might have done her PhD thesis about Artificial Intelligence under the supervision of John McCarthy, becoming the first woman to get a computer science PhD in the United States, or have a programming principle that’s named after her, but back in 1974, she changed the software world for ever: She invented Abstract Data Types.

Back in the ’70s the hardware designers were kings–recalls Liskov in her QConKeynote–so nobody believed that there was something hard about doing software. Back in those days, writing a procedure was as far as it went when it came to abstraction.

This is a time where a paper like “Go To Statement Considered Harmful” was controversial, because GOTO was pretty much the way used to structure programs back then. Liskov, among other software thinkers of the day, was trying to understand how to structure programs in a way that made them easier to reason about.

The idea that software programming was an intellectual activity that required a great deal of thought was kind of controversial – Barbara Liskov

Her concerns came from her work on the operating system Venus, implemented while she was working at MITRE Corporation. There she tried to understand how the programmer could isolate parts of the program, how one could make it more modular. Of course, back in the day, it wasn’t clear what modules were about either.

She understood that modules, had to allow a programmer to reason locally about its behavior. They would offer an API, a contract, which had to be satisfied to the other users of the module. That meant that as a programmer you could modify the contents of the module, and as long as you didn’t break the contract, the program would continue working as expected.

In Liskov’s words:

What we desire from an abstraction is a mechanism which permits the expression of relevant details and the suppression of irrelevant details. In the case of programming, the use which may be made of an abstraction is relevant; the way in which the abstraction is implemented is irrelevant. — Programming With Abstract Data Types

This all sounds very basic to us, forty four years later, but back in the 1974 this was all a revelation.

How did Liskov and her colleagues at MIT went about solving this problem? They designed a new programming language where they could test their ideas, while at the same time implementing systems with it:

Programming languages allow you to do almost anything, but the question is: Do the things you really need to do, are they easy to do, or hard to do? — Barbara Liskov

The result of this research is the programming language CLU, a predecessor of many modern OOP languages. You could define abstract types with it, and then create instances of those objects. It had information hiding as a way to make programs easier to prove correct. It provided strong type checking, and many other techniques, that are so widespread today, that almost seem basic to be talking about them.

What I really like from their approach is how they tested their ideas creating an actual language. This wasn’t your theoretical paper, about “it’d be nice to code this way”, but “here’s a language that can do what we propose”. Also as she said, does a language makes the things you want to do easy to do? That seems like a maxim not only for language design, but for software design in general.

Barbara Liskov while designing ADTs
Her pioneering research has made her one of the world’s leading authorities on computer language and system design. — Susan Hockfield, MIT President

Advent Calendar — Help us make it a book!

From December 1st until December 24th we plan to release one article each day, highlighting the life of one of the many women that have made today’s computing industry as amazing as it is: From early compilers to computer games, from chip design to distributed systems, we will revisit the lives of these pioneers.

Each article will come with an amazing illustration by @SebastianNavasF.

If you want to see these series to become a book with expanded articles and even more illustrations by Sebastián, then subscribe to our newsletter below.

References