The Abstract Data Type: A Promise, and a Hidden Representation
Chapter Seven
Syllabus topic Module 1, "Abstract Data Type: Introduction to ADT"
Pages 20 to 22 of 411
In one line
An Abstract Data Type is a set of values together with the operations allowed on them, described by what the operations do and deliberately not by how they are stored.
The definition, taken apart
An ADT has exactly two halves.
The values. What the thing holds. A bag of integers. A sequence of names. A collection of students.
The operations, described by their behaviour. What each one does, what it needs, what it gives back, and what happens when it is asked for something impossible.
And one deliberate absence, which is the whole idea:
No representation. The ADT does not say array or linked list. It does not say how many bytes. A reader of the ADT learns what the structure promises and learns nothing about how it keeps that promise.
That absence is not vagueness. It is a decision, and the next chapter is about why it is the right one.
An ADT written out properly
Here is the ADT for a Bag: a collection that holds items, allows duplicates, and has no order.
| Operation | Needs | Gives back | Behaviour |
|---|---|---|---|
Bag() | nothing | a new bag | creates an empty bag |
add(item) | an item | nothing | puts the item in; duplicates allowed |
remove(item) | an item | nothing | removes one copy; error if absent |
contains(item) | an item | true or false | is at least one copy present |
size() | nothing | a whole number | how many items, counting duplicates |
isEmpty() | nothing | true or false | is the size zero |
Notice what the table settles and what it refuses to settle. It settles that remove on an absent item is an error rather than silently doing nothing, which is a real design decision a reader needs. It refuses to say whether the bag is an array or a list, because a user of the bag does not need to know and should not depend on it.
The same ADT, built two completely different ways
This is the demonstration that makes the idea concrete rather than a sentence to memorise.
class BagAsList:
"""A bag kept as one row of items."""
def __init__(self):
self._items = []
def add(self, item):
self._items.append(item)
def remove(self, item):
if item not in self._items:
raise KeyError("not in the bag: %r" % (item,))
self._items.remove(item)
def contains(self, item):
return item in self._items
def size(self):
return len(self._items)
def is_empty(self):
return self.size() == 0
class BagAsCounts:
"""The same bag, kept as a table of item to how many copies."""
def __init__(self):
self._counts = {}
def add(self, item):
self._counts[item] = self._counts.get(item, 0) + 1
def remove(self, item):
if self._counts.get(item, 0) == 0:
raise KeyError("not in the bag: %r" % (item,))
self._counts[item] -= 1
if self._counts[item] == 0:
del self._counts[item]
def contains(self, item):
return self._counts.get(item, 0) > 0
def size(self):
return sum(self._counts.values())
def is_empty(self):
return self.size() == 0
def stock_report(bag, wanted):
"""A user of the ADT. It never asks how the bag is built."""
bag.add("pen")
bag.add("pen")
bag.add("book")
bag.remove("pen")
return (bag.size(), bag.contains(wanted), bag.is_empty())
for cls in (BagAsList, BagAsCounts):
print("%-12s ->" % cls.__name__, stock_report(cls(), "pen"))The Abstract Data Type: A Promise, and a Hidden Representation
BagAsList -> (2, True, False)
BagAsCounts -> (2, True, False)One function, stock_report, ran against two structures that share not one line of storage code. One keeps a row of items; the other keeps a table of counts. The caller could not tell the difference, because the ADT is what it was written against.
That is an ADT doing its job.
What the two representations actually cost
They are interchangeable to the caller and they are not equivalent to the machine, which is the second half of the lesson.
class BagAsList:
def __init__(self):
self._items = []
def add(self, item):
self._items.append(item)
def size(self):
return len(self._items)
class BagAsCounts:
def __init__(self):
self._counts = {}
def add(self, item):
self._counts[item] = self._counts.get(item, 0) + 1
def size(self):
return sum(self._counts.values())
import sys
N = 50000
kinds = 5
as_list = BagAsList()
as_counts = BagAsCounts()
for i in range(N):
item = "kind-%d" % (i % kinds)
as_list.add(item)
as_counts.add(item)
print("items added :", N)
print("distinct kinds :", kinds)
print("both report the size :", as_list.size(), as_counts.size())
print("counts version smaller :",
sys.getsizeof(as_counts._counts) < sys.getsizeof(as_list._items))items added : 50000
distinct kinds : 5
both report the size : 50000 50000
counts version smaller : TrueFifty thousand items of five kinds. The row keeps fifty thousand entries; the table keeps five. Same ADT, same answers, wildly different memory.
So the ADT tells you what you may ask for, and the choice of representation tells you what it will cost. Both are needed, and separating them is what lets you change the second without breaking every program that relies on the first.
Why the University prints the syllabus this way
Read MU's own labels again. "ADT for linked list". "Stack ADT for Stack". "Queue ADT". "ADT for Tree Structure". "Priority Queue ADT". "Graph ADT". "Hash Table ADT".
Seven of the eight structures in this paper are introduced by their ADT. That is deliberate, and it means the examinable content for each structure is in two parts: what it promises and how it is built. A question asking you to "write the ADT for a stack" is asking for the first, and an answer that starts with an array has answered a different question.
Quick revision
- An ADT is a set of values plus the operations on them, described by behaviour and not by
representation.
- The missing representation is the point, not an omission.
- The operations must say what happens in the impossible cases, such as removing an absent item.
- One ADT can have many representations; a caller written against the ADT works with all of them.
- The representations are not equivalent in cost, which is why the choice still matters.
- MU introduces seven of this paper's eight structures by their ADT, so "write the ADT for X" is a
The Abstract Data Type: A Promise, and a Hidden Representation
standard question and it is not asking for code.
Test yourself
1. Define an Abstract Data Type. A set of values together with the operations allowed on them, specified by what the operations do and deliberately not by how the values are stored.
2. What is deliberately left out of an ADT, and why is that not a weakness? The representation. Leaving it out is what lets the representation be changed without breaking any program written against the ADT.
3. An ADT for a bag says remove on an absent item is an error. Is that part of the ADT or part of the implementation? Part of the ADT. What happens in an impossible case is behaviour, and a user needs to know it.
4. Two bags, one a row of items and one a table of counts, gave identical answers. What does that show, and what does it not show? It shows they implement the same ADT, so a caller cannot tell them apart. It does not show they cost the same: with 50,000 items of 5 kinds the table is far smaller.
5. Why is the ADT written before the implementation is chosen? Because the ADT states the problem and the implementation is one answer to it. Choosing storage first fixes the costs before anyone has said what operations matter.
6. "Write the ADT for a stack." What should your answer contain and what should it not? It should contain the values it holds and each operation with what it needs, returns and does, including overflow and underflow. It should not contain an array, a linked list or any code.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.