CS201J: Engineering Software, Fall 2002

Notes: Tuesday 10 September 2002
Assignments Due
 Now: Problem Set 2
 12 September: Read Ch 5.35.10
 19 September: Problem Set 3
 Lab hours this week (Small Hall): Thursday, 57pm (Sol); 79pm (Tiffany); Sunday 46pm (Mike), 68pm (Serge)
Notes and Questions
What are the advantages and disadvantages of using abstract data types?
Specifying Abstract Data Types
StringSet Specification
 Overview: what does the type represent. Should always include:
 Mutability/Immutability (e.g., A StringSet is a mutable set of Strings.)
 Abstract Notation (e.g., A typical StringSet is { x1, , xn }.)
 Operations: specifications for constructors and methods clients use Describe in terms of abstract notation introduced in overview.
 Ways to create objects of the data type
 Creators: create new objects of the ADT from parameters of other types
 Producers: create new objects of the ADT from parameters of the ADT type (and other types)
 Ways to observe properties: observers
 Ways to change properties: mutators (mutable data types only)
public class StringSet // OVERVIEW: StringSets are unbounded, mutable sets of // Strings. A typical StringSet is { x1, ..., xn } public StringSet () // EFFECTS: Initializes this to be empty: { } public void insert (String s) // MODIFIES: this // EFFECTS: Adds x to the elements of this: // this_post = this_pre U { s } public boolean isIn (String s) { // EFFECTS: Returns true iff s is an element of this. public int size () // EFFECTS: Returns the number of elements in this.
Representation Invariant
The Representation Invariant expresses properties all legitimate objects of the ADT must satisfy. It is a function from concrete representation to boolean:
I: C → booleanTo check correctness we assume all objects passed in to a procedure satisfy the invariant and prove all objects satisfy the invariant before leaving the implementation code.
public class StringSet { // OVERVIEW: StringSets are unbounded, mutable sets of Strings. // A typical StringSet is {x1, ..., xn} // Representation: private Vector rep; // RepInvariant (c) = c contains no duplicates && c != nullAbstraction FunctionThe Abstraction Function maps a concrete state to an abstract state:
AF: C → AIt is a function from concrete representation to the abstract notation introduced in overview specification.// AF (c) = { AF_{String} (c.els[i])  0 <= i < c.els.size () }It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures.Alan Perlis
University of Virginia Department of Computer Science CS 201J: Engineering Software 
Sponsored by the National Science Foundation 
cs201jstaff@cs.virginia.edu 