Decomposition Detective

Decomposition Detective

A whole program looks impossible when you stare at it all at once. Good programmers never do that, and they avoid it with two habits of mind that sound similar and are not. Decomposition cuts a problem into pieces. Abstraction decides how much of each piece you need to think about. Confusing the two is the commonest mistake in this topic, so the next card puts them side by side before anything else.

Decomposition against abstraction

Both make a hard problem manageable, and they do it in completely different ways:

Which one is this?

A programmer writing a route-finder decides to treat the whole road network as nothing but a set of points joined by lines with distances on them. Road surface, width, scenery and street names are all discarded. Which technique is that, and what would the other one have produced instead?

• Abstraction. The road network has been simplified by discarding everything irrelevant to finding a route, and it is still one road network. Decomposition would have split the task into separate sub-problems, such as reading the map data, finding the route, and displaying it
• Decomposition, because the network is being broken down into individual points and lines
• Both equally, since simplifying always involves breaking things up
• Neither. This is just data modelling, which is a separate activity

Subprograms

Decomposition gives you pieces. A subprogram is how a piece becomes actual code:

Procedure or function?

You are writing a shop program. One subprogram works out the total cost of the items in a basket; another prints a "thank you for your order" message at the end. Which should be a function, and why?

• The total-cost one, because the rest of the program needs the number back to use it: to print a receipt, take payment and check against a budget. The thank-you message hands nothing back, so it is a procedure
• The message one, because printing something to the screen counts as returning it to the user
• Both, since every subprogram returns something even if it is only a signal that it finished
• Neither. Functions are only for mathematical calculations, so both should be procedures

Why does it help?

One problem, decomposed

The problem: a program that lets a student log in and shows their timetable. The sub-problems, each becoming a subprogram: • checkPassword(username, password) → a function, returns true or false. • loadTimetable(username) → a function, returns the student's lessons. • displayTimetable(lessons) → a procedure, prints them and returns nothing. • logAttempt(username, success) → a procedure, records what happened. Where the abstraction is. displayTimetable needs the lessons and does not need to know whether they came from a database, a file or a test fixture. checkPassword might hash the password, compare it and rate-limit repeated failures, and everything calling it sees only true or false. Each subprogram presents a simple front and hides its own machinery behind it. That split is the reason the pieces can be worked on separately at all. Change how passwords are stored and nothing else in the program has to be touched, because nothing else ever knew.

Decomposing a quiz game

You are asked to build a quiz game. Put the stages of decomposing it into a sensible order.

• State the whole problem clearly: build a quiz game
• Break it into main sub-problems: ask questions, check answers, keep score, show the result
• Decide what each sub-problem needs passed in, and what it should hand back
• Write a subprogram for each, and test each one on its own
• Combine the tested subprograms into the finished game

Both can be overdone

Over-decomposition. A subprogram that does one trivial thing, called from exactly one place, adds a layer without removing any work. The reader now has to jump somewhere else to find out that nothing much happens there. A good subprogram does one meaningful job and its name says what that job is; if you cannot name it clearly, it is probably not a real piece. Over-abstraction. Hiding detail is only safe when the detail truly does not matter. A route-finder that throws away road width will happily send a lorry down a lane it cannot fit through. The question is never "is this detail interesting?" but "could ignoring this make my answer wrong?" And a warning about speed. Decomposition does not make a program run faster. Calling a subprogram costs a very small amount of time, so a decomposed program is usually a shade slower. What it saves is your time, not the computer's, and saying otherwise in an exam loses the mark.

Is this good decomposition?

A student is told their 20-line program should be decomposed. They split it into 15 subprograms, most of them a single line long, each called from exactly one place. Is that good decomposition?

• No. The aim is pieces that each do one meaningful job and can be understood or tested on their own. Fifteen one-line subprograms add fourteen places to jump to without making anything simpler, and the program is now harder to follow than the original
• Yes. More subprograms always means better decomposition, since each piece is as small as it can possibly be
• No, because 15 subprogram calls would make the program noticeably slower
• Yes, as long as each subprogram is given a clear name

Which are genuine benefits?

Select the THREE that are genuine benefits of decomposing a program into subprograms.

• Code needed in several places can be written once and called from each of them
• Each part can be tested on its own before the whole is assembled
• Different people can work on different subprograms at the same time
• The finished program runs faster, because subprograms execute more efficiently than one long block
• The program always ends up with fewer lines of code overall
• The program cannot contain logic errors, since each part has been checked separately

Building the school system

You are designing the login-and-timetable program. Three decisions.

• A colleague suggests writing the login and the timetable as one subprogram, since the login always runs immediately before the timetable and they will never be used apart. What is the strongest response?
• The password check is currently a simple comparison. Later it must change to a hashed comparison with a limit on repeated attempts. How much of the rest of the program has to change?
• For the timetable display, someone proposes abstracting away the day of the week, on the grounds that a lesson is a lesson. Is that a sound abstraction?

Layers of abstraction

Computing is built from layers, each hiding the one beneath it. Put them in order, closest to the hardware first.

• Machine code: the actual binary instructions the processor executes
• Assembly language: the same instructions given short names, so a human can read them
• A high-level language: loops and variables, with the instructions and memory addresses hidden
• A library subprogram: one call that does a whole job, with the high-level code inside it hidden too
• Your own program, which calls that library without knowing anything about any of the layers below

Detective summary

_____ breaks one problem into smaller sub-problems, so you end up with more things, each simpler. _____ strips out detail that does not matter, so you end up with the same thing, simplified. Each sub-problem becomes a subprogram, and one that hands a value back to whatever called it is a _____. The benefits are reuse, independent testing and parallel working, but not _____: a subprogram call costs a little time rather than saving it.