September 26, 2016

Abstract Data Types

—A look at Barbara Liskov's paper on Abstract Data Types.

I was reading "Contracts, Scenarios and Prototypes" and learned that Abstract Data Types were first presented by Barbara Liskov and Stephen Zilles in their paper "Programming with abstract data types" (requires access to the ACM Digital Library). The main contribution made by this paper is that it identifies an abstract data type as class of object completely characterized by the operations it can perform.

Liskov and Zilles' paper was written in 1974. It lists thirteen references that provide insight on how abstract data types were arrived at. It's an interesting list of references including work from Dijkstra, Neumann, Parnas and Wirth.

What is compelling about the introduction of "Contracts, Scenarios and Prototypes" is the depth of the references provided on the development of contracts. In addition to abstract data types, this introduction includes a look at Hoare's "An Axiomatic Basis for Computer Programming" which introduces pre- and post-conditions via Hoare Triples and Parnas' "A Technique for Software Module Specifications with Examples" for description of good specifications and strongly typed languages.