Decomposition, composition and automation

Thinking procedurally, compound procedures and compound data, and putting a model into action.

A2.6Recursion and computational thinkingA level20 min

At GCSE you broke a delivery job into smaller parts and drew a structure diagram (F4.4). At A level this becomes three linked ideas: decomposition takes a problem apart, composition builds a solution back up from pieces, and automation puts the finished model to work. OCR calls the planning side of this thinking procedurally.

Decomposition

Procedural decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided. You stop when each piece is small enough to write and test on its own.

Here is a robot that tidies coloured balls into a box:

tidy the mat
├── find a ball
│   ├── turn in steps, looking for a colour
│   └── record where it was seen
├── fetch the ball
│   ├── drive to it
│   └── close the gripper
├── deliver the ball
│   ├── drive to the box
│   └── open the gripper
└── decide whether to stop
    └── any balls left in view?

Thinking procedurally is the questions you ask while doing this:

What are the components of the problem? Here: finding, fetching, delivering, stopping.
What are the components of the solution? The subroutines, and the data they share, such as the colour being looked for and the position of the box.
What order must the steps happen in? A ball must be found before it can be fetched; some steps (such as recording and turning) could be done in either order.
Which sub-procedures are needed, and can any be reused? "Drive to" appears twice, so it should be written once.

Composition

Composition is the opposite direction: building bigger abstractions by combining smaller ones.

Combining procedures forms compound procedures. fetch is built from drive_to and grip; tidy is built from find, fetch and deliver.
Combining data objects forms compound data. A reading is a record; a survey is a list of readings; a map is a grid of cells. A tree is compound data made of nodes, each holding a value and a list of smaller trees.

def to_cm(inches):
    return inches * 2.54

def round_to_whole(value):
    return round(value)

def compose(f, g):
    """A new function that does g, then f on the result."""
    def both(x):
        return f(g(x))
    return both

inches_to_whole_cm = compose(round_to_whole, to_cm)
print(inches_to_whole_cm(10))
print(inches_to_whole_cm(7.5))

Run this in the simulator

compose builds a new function from two existing ones without writing any new arithmetic. Compound data works the same way. This tree records how the tidy job is made of parts, as nested tuples of a name and a list of smaller trees. The recursive function walks it:

tidy = ("tidy the mat", [
    ("find a ball", [("turn and look", []), ("record position", [])]),
    ("fetch the ball", [("drive to it", []), ("close gripper", [])]),
    ("deliver the ball", [("drive to box", []), ("open gripper", [])]),
])

def show(tree, depth=0):
    name, parts = tree
    print("    " * depth + name)
    for part in parts:
        show(part, depth + 1)

def count_leaves(tree):
    name, parts = tree
    if parts == []:
        return 1
    total = 0
    for part in parts:
        total = total + count_leaves(part)
    return total

show(tidy)
print("jobs small enough to write:", count_leaves(tidy))

Run this in the simulator

Automation

Automation is putting models (abstractions of real-world objects or phenomena) into action to solve problems. It takes four steps:

creating algorithms;
implementing the algorithms in program code;
implementing the models in data structures;
executing the code.

Everything in this module so far leads here. The grid from the last lessons is a model in a data structure; a path-finding algorithm is written in code; when it runs, the robot drives. Automation is also where the gap between model and reality shows: if the model left out something that matters, the executing code will make the wrong decision, however correct the algorithm is.

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

# the model, as data: a triangle is a list of (distance cm, turn degrees) moves
triangle = [(20, 120), (20, 120), (20, 120)]

def drive_moves(moves):
    for cm, degrees in moves:
        forward(60, distance=cm)
        turn_right(30, angle=degrees)

drive_moves(triangle)                  # execution
print("model driven, now at", position())

Run this in the simulator

In the exam

Questions give a scenario and ask you to decompose it (often as a hierarchy chart), to identify the components of the problem and of the solution, to put steps in order, and to say which sub-procedures could be reused. AQA also asks you to explain composition and automation in words.

AQA A level 4.4.1.9, 4.4.1.10, 4.4.1.11

AQA defines procedural decomposition as breaking a problem into sub-problems that each accomplish an identifiable task, which might be further subdivided; composition as combining procedures to form compound procedures, and combining data objects to form compound data such as a tree; and automation as putting models into action by creating algorithms, implementing them in program code, implementing the models in data structures, and executing the code.

OCR A level 2.1.3, 2.2.2

OCR's thinking procedurally asks you to identify the components of a problem and of a solution, to determine the order of the steps needed, and to identify the sub-procedures necessary. Problem decomposition is also one of the computational methods in 2.2.2.

Task: a route built from pieces

A leg is a tuple (direction, cm), where direction is one of "forward", "backward", "left" or "right" and cm is a distance. A shape is a list of legs. A route is a list of shapes. The starter builds this route from two shapes:

step = [("forward", 20), ("right", 20)], square = [("forward", 20), ("right", 20), ("backward", 20), ("left", 20)], route = [step, square, step]

Write three procedures, each built from the one before:

drive_leg(leg) prints leg <direction> <cm> and drives that leg at speed 60, sliding sideways for left and right (the robot never turns);
drive_shape(shape) drives every leg of a shape, using drive_leg;
drive_route(route) drives every shape of a route, using drive_shape.

Drive the route, then print route done: <shapes> shapes, <legs> legs, which for this route is route done: 3 shapes, 8 legs. The robot should finish 40 cm right of and 40 cm up from where it started.

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

step = [("forward", 20), ("right", 20)]
square = [("forward", 20), ("right", 20), ("backward", 20), ("left", 20)]
route = [step, square, step]

def drive_leg(leg):
    direction, cm = leg

def drive_shape(shape):
    pass

def drive_route(route):
    pass

Challenges

Add a shape zigzag and a new route that uses it twice, without changing any of the three procedures.
Draw the route as a tree like the tidy job. What are the leaves?
Decompose "play a game of robot football" as far as three levels. Which sub-procedures would two robots share?