CSE 130 Lecture Notes, May 1, 2002

CSE130 LECTURE NOTES

May 1, 2002

ADMINISTRATION

Today we start a major new topic. This will lead to talking about object-oriented programming next week.

THE DEFINITION OF AN ADT

An abstract data type introduces a new type indirectly, by providing a set of operations that can produce and operate on a new set of values. The new set of values is characterized by specifying the relationships between the operations introduced.

All PL types are high-level since the details of how the values of the type are represented are abstracted away. For regular types these details are taken care of by the compiler. For ADTs, these details are given by the programmer who creates the type. In both cases, a programmer who uses the type does not need to know the implementation details.

Formally: An ADT has two parts: a specification part and an implementation part. A specification has two parts: a signature and constraints. An implementation has two parts: a concrete type and a signature implementation.

Informally:

the signature states the types of the basic operations available on values of the new type;
the constraints state properties that these operations must satisfy;
the concrete type gives an actual representation for values;
the signature implementation gives code for the operations, that satisfies the satisfies the signature and constraints, and that depends on the particular concrete type chosen.

The specification part of an ADT is "public": it is what a user of the ADT needs to know.

The implementation part of an ADT is "private": only the implementer needs to know the details of exactly how values are represented, and how the basic operations on values are accomplished.

AN EXAMPLE ADT FOR PRIORITY QUEUES

Some PLs provide ADT facilities while others do not. Even if a PL does not provide ADT features, a programmer can still choose to think in terms of ADTs. Using an ADT is then a question of discipline.

This example uses ML syntax, but the ideas are applicable to any PL. First here's a signature:

signature pqsig = sig
    type pq
    val onil: pq
    val ohd: pq -> int
    val otl: pq -> pq
    val null: pq -> bool
    val insert: int -> pq -> pq
    val sort: int list -> pq
end;

Next here is a sketch of appropriate constraints on the functions introduced in the signature:

null nil = true;
forall i:int x:pq null (insert i x) = false
forall i,j:int x:pq insert(i,insert(j,x)) = insert(j,insert(i,x))
...

Of course many more equations are also true about relationships between the operations named in the signature.

One obvious concrete representation for priority queues is as unordered lists. Here's an appropriate (incomplete) implementation:

structure pqstruct : pqsig = struct
     datatype pq = wrap of int list
     fun doinsert (n: int) [] = [n]
       | doinsert n (a::x) = if n <= a then n::(a::x)
                             else a::(doinsert n x)
     val onil = (wrap [])
     fun ohd (wrap (a::x)) = ...
     fun otl (wrap (a::x)) = ...
     fun null (wrap []) = true
       | null (wrap (a::x)) = false
     fun insert n (wrap x) = wrap (doinsert n x)
     fun sort x = (wrap x)
end

Notice that the sort function is implemented as a "no-op". This implies that the ohd and otl functions must have non-trivial implementations.

Important note: The semantic part is conceptually important but programming languages typically do not require it. There are two reasons for this: (1) verifying that an implementation actually satisfies a specification is an unsolved problem in artificial intelligence, and (2) the semantics of specification languages is an open question.

PUBLIC VERSUS PRIVATE

The specification part of an ADT is "public": it is what a user of the ADT needs to know, and should be able to know.

The implementation part of an ADT is "private": only the implementer needs to know the details of exactly how values are represented, and how the basic operations on values are accomplished.

Languages have various mechanisms for making ADT function names visible. For example in ML:

- pqstruct.onil;
val it = wrap [] : pqstruct.pq
- open pqstruct;
- onil;
val it = wrap [] : pq