Decomposition and abstraction

Structure diagrams, and hiding the details of a job behind a function.

F4.4Functions and structured codeGCSE20 min

A delivery robot in a warehouse does one enormous job: collect orders and bring them to the loading bay. Nobody writes that as one enormous program. They break the job into smaller problems, and those into smaller ones, until each piece is simple. And they hide the details of each piece behind a name. Those two ideas are decomposition and abstraction, and they are how every large program is built.

Decomposition: breaking a problem down

The problem: BugBot delivers a parcel to three stops on the mat, signalling at each, and reports when it is done. Break it into parts, then break the parts down again, until each is something you can write:

deliver to three stops
├── go to a stop
│   ├── work out how far across and how far up
│   ├── drive across
│   └── drive up
├── signal at a stop
│   ├── light on and beep
│   └── light off
└── report

This is a structure diagram: the whole problem at the top, the smaller problems underneath. Each box at the bottom is small enough to be one function, or a few lines of one. Now you can work on one box at a time, and test it before moving on.

Abstraction: hiding the details

Abstraction means leaving out detail that does not matter for what you are doing now. The robot's mat in a simulator is an abstraction of a real room: it keeps the walls and distances and leaves out the carpet colour. A function is an abstraction too. Once go_to(x, y) works, the rest of the program only needs to know what it does, not how:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def go_to(x, y):
    """Drive to (x, y), in cm from where the robot started."""
    here_x, here_y = position()
    across = x - here_x
    up = y - here_y
    if across > 0:
        right(60, distance=across)
    elif across < 0:
        left(60, distance=-across)
    if up > 0:
        forward(60, distance=up)
    elif up < 0:
        backward(60, distance=-up)

go_to(30, 20)
go_to(30, 50)
go_to(0, 0)
print("back at", position())

Run this in the simulator

The three calls at the bottom read like a route: go here, then here, then home. Everything about position(), subtracting and choosing a direction is hidden inside go_to. BugBot can drive sideways, so it never needs to turn.

The line in triple quotes at the top of the function is a docstring: it says what the function does, for the person calling it. Good abstraction starts with a clear promise like that.

Building from the bottom up, testing as you go

Write and test the small pieces first, then the pieces that use them:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def signal():
    """Light and beep so a person can see a stop was reached."""
    led("green")
    tone(784, 0.3)
    led("off")

# test the piece on its own before anything uses it
signal()
signal()
print("signal works")

Run this in the simulator

When signal and go_to both work alone, the whole delivery is short, because all the hard parts are already done:

stops = [(30, 20), (30, 50), (0, 50)]
for x, y in stops:
    go_to(x, y)
    signal()
print("delivered to", len(stops), "stops")

Notice that the list of stops is data, separate from the code that drives. To change the route, change the list; the functions stay the same. That is abstraction again.

In the exam

Decomposition is breaking a complex problem down into smaller, more manageable sub-problems. Abstraction is removing unnecessary detail to focus on what matters. Questions ask you to define both, to spot them in a scenario, and to draw or complete a structure diagram. Decomposed parts are often written as subprograms.

OCR 2.1.1

OCR groups abstraction, decomposition and algorithmic thinking (working out the steps to solve a problem) as computational thinking. Structure diagrams are in 2.1.2.

AQA 3.1.1

AQA asks you to understand and explain decomposition and abstraction, and uses structure charts to show how a problem is broken down.

Edexcel 1.1.1, 6.1.1

Edexcel asks you to understand how decomposition and abstraction are used to solve problems. In Paper 2 (6.1.1) you are expected to use them when writing programs, so a well-decomposed solution made of functions is exactly what is wanted.

Task: three stops

Write go_to(x, y) and signal(), then use them to visit three stops in order, signalling at each: A at (30, 10), B at (30, 60) and C at (0, 60), all in cm from where the robot starts. The robot starts in the bottom left of the mat.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def go_to(x, y):
    """Drive to (x, y), in cm from where the robot started."""
    here_x, here_y = position()

def signal():
    """Light and beep at a stop."""
    led("green")

Challenges

Add a fourth stop and a trip back to the start, by changing only the list of stops.
Draw a structure diagram for a robot that tidies balls into a box. Which boxes could reuse go_to?
Make go_to return how far it drove in total, and print the length of the whole route.