Advanced Programming I Lecture Notes

14 February 2006 • Abstract Data Types

Outline

• History

• Motivation

• Description

• Implementation

An Equation

• Nicklaus Wirth wrote a well-known book called
  Algorithms + Data Structures = Programs

• This equation tells you what programs are, but not how they're structured.

• Structure can be imposed along a continuum with two extremes:

  • No structure.

  • Complete isolation.

No-Structure Structure

• In unstructured programs, data structures are intermingled with each other and the code that uses them.

  • This is true for all data structures and algorithms used in the program.

• Such programs are usually marked by most or all data being global.

No-Structure Analysis

• No-structure programs

  • are easy to write (the first time).

  • have little or no execution-time overhead.

• But, no-structure programs also

  • are hard to understand and modify.

  • brittle in the face of change.

Isolated Structure

• In isolated-structure programs, each data structures is almost completely isolated from every other component of the program.

• Selected algorithms provide indirect access to data structures.

  • The algorithms themselves are also almost completely isolated.

• Such programs are usually marked by lots of modules and lots of procedure calls.

Isolated-Structure Analysis

• Isolated-structure programs

  • are easy to design, write, understand, and modify.

• But, isolated-structure programs also

  • may be difficult to optimize globally.

  • may confound other global-scale manipulations (such as system testing).

No-Structure vs. Isolation

• Programming progress over the past 40 years can be thought of as the process of moving from no-structure to isolated-structure programs.

• The trade-off is between execution-time efficiency and programmer efficiency.

  • No-structure programs are (may be) execution-time efficient.

  • Isolated-structure programs are (may be) programmer-time efficient.

Implementing Isolation

• Encapsulation is the main technique for implementing isolation.

  • Encapsulation limits and enforces visibility constraints on the names of objects being encapsulated.

• Abstract data types (ADTs) are one approach for providing isolation via encapsulation.

  • There are many others.

ADT Structure

• An ADT has three components:

  • One or more operations (public procedures).

  • Zero or more internal procedures.

  • A set (possibly empty) of internal data.

• Only operations are visible outside the ADT.

  • Internal data and procedures are directly inaccessible outside the ADT.

  • Thus: encapsulation.

ADT State

• The state of an ADT corresponds (roughly) to the set of values contained in the internal data.

• ADT state is not directly observable outside the ADT.

• Outside an ADT, state is observable only via the actions of public functions.

  • This is the externally observable state.

ADT Operation Categories

• Each ADT operation falls into one of three categories:

  1. Maintenance operations.

  2. Manipulation operations.

  3. Query operations.

Maintenance ADT Operations

• A maintenance operation manipulates the entire ADT state.

  • Maintenance operations manipulate both internal and externally observable state.

• Example maintenance ADT operations:

  • Create an ADT instance.

  • Delete an ADT instance.

  • Resize an ADT instance.

Manipulation ADT Operations

• A manipulation operation adds or removes data in an ADT instance.

  • Manipulation operations change externally observable state.

• Example manipulation ADT operations:

  • Add data to an ADT instance.

  • Remove data from an ADT instance.

  • Clear all data from an ADT instance.

Query ADT Operations

• A query operation returns information about an ADT instance.

  • Query operations do not change externally observable state.

• Example query ADT operations.

  • Empty

  • Size

  • Data access (e.g. operator [])

Implementing ADTs

• Identify an ADT with a class.

  • ADT = class - inheritance.

• ADT operations are public class methods.

  • Constructors and destructors are maintenance operators.

• ADT state are private instance variables.

ADTs vs. Classes

• Why not just use classes and skip ADTs?

• Inheritance complicates things enormously.

  • ADTs are simpler for eliminating inheritance.

• Template-based parametric polymorphism will see us through most of the way.

  • We'll pick up inheritance-based subtype polymorphism later.

References

• Data Structures + Algorithms = Programs, Nicklaus Wirth, Prentice-Hall, 1976.

• On the Criteria to be used in Decomposing Systems into Modules, David Parnas, Communications of the ACM, December 1972, pages 1053-1058.