Tom Kelliher, CS23

Feb. 21, 1996

# Modularity for the 1,000th Time

Imagine:

1. Large team project to create, prove, develop product
2. Fiefdoms
3. Proof of concept prototype
4. Re-write for time/space efficiency before shipping

What can go wrong?

How can these problems be addressed?

• Procedural abstraction --- what, not how
• Information hiding
• Data abstraction

A collection of data together with a set of operations on that data.

• Simula68
• Objects
• Object oriented programming

Interface/Implementation (data structure)

• Integers
• Complex numbers
• The factorial of a number
• Matrices
• A chair
• An automobile
• A CD collection (classical vs. rock)

A list is a collection of ordered items

• Tail
• Successor, predecessor
• Order
• Items
• Insertion/deletion semantics --- yield different ``lists:''
• Anywhere --- list
• Insert at tail, delete at head --- queue
• Insert, delete at head --- stack

1. CreateList()
2. DestroyList()
3. ListIsEmpty()
4. ListLength()
5. ListInsert(newPosition, newItem, success)
6. ListDelete(position, success)
7. ListRetrieve(position, dataItem, success)

List Parameters???

Pre- Post-Conditions

Have we specified a data structure (implementation)?

Behavioral specification

Example:

```List l;
dataItem d;

l.CreateList();
l.ListInsert(2, butter, success);
l.ListInsert(3, jam, success);
l.ListInsert(4, toaster, success);
l.ListRetrieve(2, d, success);
l.ListDelete(2, success);
```

Without knowledge of the implementation:

1. Write a display function
2. Write a multiple insert function
3. Delete all items and destroy entire list
1. Sorted list
2. queue
3. stack

1. CreateSortedList
2. DestroySortedList
3. SortedListIsEmpty
4. SortedListLength
5. SortedListInsert(newItem, success)
6. SortedListDelete(item, success)
7. SortedListRetrieve(position, dataItem, success)
8. LocatePosition(anItem, position, success)