topical media & game development

talk show tell print

object-oriented programming

Instructor's Guide: Abstract Data Types


This chapter presents an introduction to the theoretical foundations of abstract data types. In particular, an algebraic treatment is given of abstract data types defined by equational theories. We then extend this approach to include objects with dynamic state changes. We start this chapter with a discussion of the notion of types and reflect on how types affect object-oriented programming. At the end of the chapter, a distinction is made between a syntactic, semantic and operational interpretation of types.


The viewpoint expressed in this chapter, and more fully worked out in the two subsequent chapters, may be characterized by the phrase types as constraints. In presenting the material you may need to emphasize the intuition underlying this viewpoint. Put simply, the more information you have, the more precisely a type is defined, and the more restricted the set of elements that belong to the type. Subtyping means narrowing down by providing more information.

Project assignments

The notion of data abstraction gives rise to a wealth of possibly interesting assignments.

For example, one may think of exploring

including proof-theoretical aspects with respect to invariance properties, as outlined in chapter refinement.

Another interesting area of investigation is

In particular, do we need modules when we have classes, and how may they be integrated with classes with respect to visibility and protection?


Section Algebra, covering an algebraic approach to the specification of abstract data types and objects, may be too demanding for students with no background in mathematical logic and set theory.
[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

(C) Æliens 04/09/2009

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.