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)

1. Set
2. Matrix
3. String
4. Terry Winograd developed a program called SHRDLU that was intended to model a simple ``world'' consisting of children's blocks of various shapes and colors. Among other things, SHRDLU was designed to simulate manipulation of the blocks by picking them up and placing them elsewhere. Design ADT block operations.

Thomas P. Kelliher
Tue Feb 20 13:20:01 EST 1996
Tom Kelliher