Abstract data types

What it does versus how it does it

When you use a Python list, you already think about it in two separate ways without noticing. There is what it lets you do: add an item, read the item at some position, ask its length. And there is how it manages that behind the scenes: where the values sit in memory, how it grows when it fills up. Most days you care only about the first. You call .append() and trust it to work; you never inspect the machinery.

That split has a name. An abstract data type, or ADT, is a description of a data type purely in terms of what operations it offers and how they behave, with no mention of how those operations are built. It is a contract. It says "you can do these things, and here is what each one promises", and stays silent on the internals.

The contract and the implementation

It helps to hold two words apart:

• The abstract data type is the contract: the list of operations and the rules they follow. For a simple counter, the contract might be "start at zero, increase adds one, value reports the current total".
• The implementation is the actual code that keeps the contract. There could be several different implementations of the very same contract, each with its own trade-offs. Code that uses only the promised operations cannot tell which one it got. Code that reaches past them, or that cares how long an operation takes, very much can.

Think of a light switch. The contract is "flip up for on, flip down for off". Whether the wiring behind the wall is old or new, copper or something else, does not change how you use the switch. The switch is the abstract type; the wiring is the implementation.

Why the separation pays off

Keeping the contract apart from the implementation buys you two real advantages.

First, you can use a data type by learning only its contract. You do not need to read the source of Python's list to store your grades in one. The promised operations are enough.

Second, whoever builds the type can change the implementation freely, as long as the contract still holds. If they find a faster way to store the data, your code keeps working untouched, because it only ever depended on the promises, never on the machinery. Code that leans on the contract survives; code that reaches inside the machinery breaks the moment the machinery changes.

A worked example: a scoreboard as a contract

Say a game needs a scoreboard. Before writing a line of storage code, describe the contract: what should a scoreboard do?

• record(team): give one point to a team.
• points(team): report how many points a team has.

That is the whole abstract type. Only now do you choose an implementation, and a dictionary from the earlier lesson fits neatly:

def new_board():
    return {}

def record(board, team):
    board[team] = board.get(team, 0) + 1

def points(board, team):
    return board.get(team, 0)

game = new_board()
record(game, "red")
record(game, "red")
record(game, "blue")
print(points(game, "red"))    # 2
print(points(game, "green"))  # 0

The rest of your program calls record and points and never touches the dictionary directly. That is the discipline the abstract type gives you: if you later swapped the dictionary for some other store, every one of those calls would keep working unchanged, because they only ever relied on the contract. The next two lessons, on stacks and queues, are two more contracts of exactly this kind.

Put both modules to work

The claim above is worth testing rather than believing: that swapping the store underneath would leave every call working. Here is the swap.

record(board, team)   ->  give one point to a team
points(board, team)   ->  report how many points a team has

print(points(game, "red"))

for team in game:
    print(team)

print(len(game))

record(game, "blue")

Check yourself

1. In your own words, what is the difference between an abstract data type and its implementation? Use the light-switch idea or an example of your own.
2. Why can the author of a data type change how it stores data without breaking programs that use it, as long as one thing stays the same? What is that one thing?
3. In the scoreboard example, the rest of the program only ever calls record and points. Why does that matter if you later decide to store the scores in a completely different way?