CSE 130 Lecture Notes, May 6, 2002

CSE130 LECTURE NOTES

May 6, 2002

ADMINISTRATION

Here are some notes about the current project:

It's due this Wednesday, before the start of class.
It is difficult. We don't expect every team to finish it successfully. It's like the real world in this respect.
However, we will give partial credit for solutions that are incomplete but show knowledge and skill.
Documentation and honest disclosure are important: Explain what you have achieved so far, and how to test it.
For the report, we want detailed facts, explanations, and examples, much more than opinions.
Like projects in the real world, thisone has many facets: coding, understanding algorithms, finding technical information, report-writing, and teamwork.
Unlike projects in the real world, there is a detailed published grading guide.

The next project will be easier.

Reminder: Plagiarism will not be tolerated. You may not copy sentences from web pages, or anywhere. If you use text from anywhere, you must do both the following: use quotation marks or indentation to indicate very clearly that someone else wrote this text, and provide a citation immediately before or after the text that is copied.

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

Implementation parts typically contain completely private auxiliary functions that are not declared in the public signature.

ADTs provide "representation independence" (better called implementation independence) to their consumers. Hiding the concrete implementation of the type is crucial for this. ML is poorly designed in that the concrete implementation is not completely hidden. In the example above, the wrapper wrap is visible to users of the ADT.

The same signature can have multiple implementations. These may differ, for example, on efficiency. Remember all the data structures you know for sets.

RESTRICTING VISIBILITY

In Java the programmer can choose four levels of visibility for the components (i.e the state variables and methods) of an object. public any user of the object can access the component friend any class in the same package have access protected only subclasses can access the component private only methods in this class have access. The default is "friend".

Traditional abstract data types only allow the "public" and "private" possibilities.

The visibilities "friend" and "protected" take into account the role of classes as modules of separate implementation and compilation.

PURE VERSUS UPDATABLE ADTS

A pure ADT is one where all operations are pure functions. This means that operations have no side-effects. In particular, they do not modify or update their input arguments. They just use these arguments to generate outputs, which are fresh values of the ADT (or of other types).

Most concrete types are pure. For example, no operation on integers actually modifies an integer. Instead, all the operations like + produce fresh outputs.

An updatable ADT is one where some operations actually change values of the ADT. For example, suppose we had an operation called pop that took a priority queue as argument and modified it by removing the highest-priority item. This operation would be impure and the whole ADT would then be impure also.

PACKAGES

Abstract data types are generalized in modern languages (e.g. Ada) to so-called "packages".

A package has a public signature and a private implementation, like an ADT. The difference is that a package can simultaneously provide many types, many specific values, and many operations.

This increases flexibility and allows mutually dependent types but loses the analogy with concrete data types.

Packages preserve the crucial ADT idea of "information-hiding." Details that a user does not need to know are not visible to him.

Packages are best-known in Ada. ML signatures and structures are in fact packages also. Ada and ML both provide parametrized ADTs and packages.

One important use for packages is as units of separate compilation. All the types in a package typically provide related functionality and are implemented by the same person or team, so it is reasonable for the classes in a package to have access to each other's implementation, i.e. to all the state variables and methods of each other.