The structured program theorem claims three control forms suffice — what does its construction add to the code?

middlemust knowfreq 55%

answer

possible, not pleasant
same result, not the same steps
the rewrite may add state
one loop over one multi-way selection
arrows become assignments

basics

~20 s

It adds bookkeeping: a control variable holding which chunk of the original flowchart runs next, wrapped in one loop over a selection that dispatches on it. The rewrite preserves the computed result, not the structure a reader sees.

solid answer

~40 s

The theorem says any flowchart, however tangled, has an equivalent built from sequence, selection and iteration alone. Two qualifications matter. The equivalence is functional — same result from the same input, not the same steps in the same order. And the construction is allowed to introduce state the original did not have: cut the flowchart into straight-line chunks, number them, add a control variable next, and write one loop whose body is a multi-way selection on next, each arm running a chunk and then assigning the number of its successor. Every arrow becomes an assignment. So the tangle is not removed, it is re-encoded as data — which is why the theorem is a statement about what is possible, not advice about what to write.

The theorem says any flowchart, however tangled, has an equivalent built from **sequence**, **selection** and **iteration** alone. Two qualifications matter. The equivalence is functional — same result from the same input, not the same steps in the same order. And the construction is allowed to introduce state the original did not have: cut the flowchart into straight-line chunks, number them, add a control variable `next`, and write one loop whose body is a multi-way selection on `next`, each arm running a chunk and then assigning the number of its successor. Every arrow becomes an assignment. So the tangle is not removed, it is re-encoded as data — which is why the theorem is a statement about what is possible, not advice about what to write.

code

pseudocode · 16 lines

pseudocode

next = 1
while next is not HALT
    if next = 1
        hours = read timesheet
        next = 2
    else if next = 2
        gross = hours * rate
        if gross > 0 then next = 3 else next = HALT
    else if next = 3
        net = gross - deductions(gross)
        next = 4
    else
        emit payslip(net)
        next = HALT
    end if
end while

go deeper

for a junior

Learn the three forms by name — sequence, selection, iteration — and remember that the claim is about every program, not just tidy ones.

for a middle

Be able to sketch the construction: chunks numbered, one control variable, one loop, one multi-way selection whose arms assign the successor. Say out loud that equivalence means same result, not same steps.

for a senior

Show that you know what the rewrite costs a reader and a static tool, and that you would use it as a behaviour-preserving starting point rather than as a finished shape.

for a principal

The interesting trade-off is that the theorem guarantees an equivalent exists but picks none of them. Choosing which structured version a team should live with is the judgment the result deliberately leaves open.

What the theorem claims

The structured program theorem, the Böhm-Jacopini result, says that any program expressible as a flowchart — arrows going wherever they like, including into the middle of a stretch of code — has an equivalent built from only three control forms:

sequence: do one thing, then the next;
selection: test a condition, take one of two paths;
iteration: while a condition holds, repeat a body.

Two qualifications carry most of the weight, and they are the ones candidates drop.

The equivalence is functional. The rewrite computes the same result from the same input. Nothing says it performs the same steps, in the same order, or the same number of them.
The construction may introduce new variables. Take that freedom away, and forbid duplicating code as well, and the claim is false in general: there are flowcharts with no equivalent assembled from the three forms alone. The extra state is not an artefact of one proof; it is part of what is being claimed.

The construction

The classic construction is mechanical enough to automate, which is exactly why it is worth being able to sketch:

Cut the flowchart into chunks of straight-line code and number them 1..n, plus a HALT marker.
Introduce one control variable — call it next — initialised to the number of the entry chunk.
Write a single loop: while next is not HALT.
Make the loop body one multi-way selection on next. The arm for chunk k runs chunk k's statements, then assigns to next the number of the chunk the original arrow pointed at. Where the original chunk ended in a test, that assignment is itself a two-way selection on the same condition.

Every original arrow becomes an assignment; every original node becomes an arm. The loop turns over once per chunk visited, so the iteration count is the length of the path the original flowchart would have walked.

Where the structure went

	the original flowchart	the flattened equivalent
where control structure lives	in the arrows between chunks	in the values written to `next`
how you find a chunk's successor	follow its outgoing arrow	find every assignment to `next` in that arm
what changing one chunk can reach	its own outgoing arrows	any arm, through the shared variable
what a reader traces	a path through a picture	a simulation of one variable

That last row is the point of the whole question. The transformation does not delete the tangle; it re-encodes it as data. Someone who wants to know what may follow chunk 3 must now search the routine for assignments instead of looking at an edge, and a tool that reasoned about control flow must now reason about the values of a variable.

Two checks against intuition. First, nothing in the rewrite is cleverer than the original: the chunks survive verbatim inside the arms, and only the arrows are re-expressed. Second, the rewrite touches control flow only — no data computation changes — which is precisely why a tool can apply it to code nobody understands.

"Suffices" is a statement about possibility

The theorem says a structured equivalent exists. It does not say the mechanical one is the equivalent worth having, and it does not promise the result is shorter, faster or clearer. Usually it is none of those: the flattened form is normally longer than the original, and its control structure is invisible.

What the result does buy is a licence and a floor:

a licence: no piece of control flow is inherently unstructurable, so "this routine cannot be expressed with ordinary loops and conditionals" is never a true excuse;
a floor: the mechanical rewrite is always available as a behaviour-preserving starting point when the original is too risky to reshape by hand.

The engineering begins after that floor: finding the parts of the flattened routine that genuinely are a sequence, a choice or a repetition, naming them, and continuing until the control variable has nothing left to do and can be deleted.

What an interviewer is listening for

The three forms named without hesitation, with iteration as a while, not a vague "some kind of loop".
The word equivalent pinned to results rather than to execution.
The extra variable volunteered rather than extracted.
A clean separation between "this is always possible" and "this is what I would do to a real routine".

A candidate who recites "sequence, selection, iteration" and stops has given the definition. A candidate who adds "and the construction pays for it with a control variable, so the flow ends up in the data" has given the answer.

## What the theorem claims The **structured program theorem**, the Böhm-Jacopini result, says that any program expressible as a flowchart — arrows going wherever they like, including into the middle of a stretch of code — has an equivalent built from only three control forms: - **sequence**: do one thing, then the next; - **selection**: test a condition, take one of two paths; - **iteration**: while a condition holds, repeat a body. Two qualifications carry most of the weight, and they are the ones candidates drop. 1. **The equivalence is functional.** The rewrite computes the same result from the same input. Nothing says it performs the same steps, in the same order, or the same number of them. 2. **The construction may introduce new variables.** Take that freedom away, and forbid duplicating code as well, and the claim is false in general: there are flowcharts with no equivalent assembled from the three forms alone. The extra state is not an artefact of one proof; it is part of what is being claimed. ## The construction The classic construction is mechanical enough to automate, which is exactly why it is worth being able to sketch: 1. Cut the flowchart into chunks of straight-line code and number them `1..n`, plus a `HALT` marker. 2. Introduce one **control variable** — call it `next` — initialised to the number of the entry chunk. 3. Write a single loop: *while `next` is not `HALT`*. 4. Make the loop body one multi-way selection on `next`. The arm for chunk `k` runs chunk `k`'s statements, then assigns to `next` the number of the chunk the original arrow pointed at. Where the original chunk ended in a test, that assignment is itself a two-way selection on the same condition. Every original arrow becomes an assignment; every original node becomes an arm. The loop turns over once per chunk visited, so the iteration count is the length of the path the original flowchart would have walked. ## Where the structure went | | the original flowchart | the flattened equivalent | |---|---|---| | where control structure lives | in the arrows between chunks | in the values written to `next` | | how you find a chunk's successor | follow its outgoing arrow | find every assignment to `next` in that arm | | what changing one chunk can reach | its own outgoing arrows | any arm, through the shared variable | | what a reader traces | a path through a picture | a simulation of one variable | That last row is the point of the whole question. The transformation does not delete the tangle; it re-encodes it as data. Someone who wants to know what may follow chunk 3 must now search the routine for assignments instead of looking at an edge, and a tool that reasoned about control flow must now reason about the values of a variable. Two checks against intuition. First, nothing in the rewrite is cleverer than the original: the chunks survive verbatim inside the arms, and only the arrows are re-expressed. Second, the rewrite touches control flow only — no data computation changes — which is precisely why a tool can apply it to code nobody understands. ## "Suffices" is a statement about possibility The theorem says a structured equivalent **exists**. It does not say the mechanical one is the equivalent worth having, and it does not promise the result is shorter, faster or clearer. Usually it is none of those: the flattened form is normally longer than the original, and its control structure is invisible. What the result does buy is a licence and a floor: - **a licence**: no piece of control flow is inherently unstructurable, so "this routine cannot be expressed with ordinary loops and conditionals" is never a true excuse; - **a floor**: the mechanical rewrite is always available as a behaviour-preserving starting point when the original is too risky to reshape by hand. The engineering begins after that floor: finding the parts of the flattened routine that genuinely are a sequence, a choice or a repetition, naming them, and continuing until the control variable has nothing left to do and can be deleted. ## What an interviewer is listening for - The three forms named without hesitation, with iteration as a *while*, not a vague "some kind of loop". - The word **equivalent** pinned to results rather than to execution. - The extra variable volunteered rather than extracted. - A clean separation between "this is always possible" and "this is what I would do to a real routine". A candidate who recites "sequence, selection, iteration" and stops has given the definition. A candidate who adds "and the construction pays for it with a control variable, so the flow ends up in the data" has given the answer.

Why is the freedom to introduce auxiliary variables essential to the theorem rather than a convenience?
Because without it — and without permission to duplicate code — the claim fails in general: some flowcharts have flow that the three forms cannot mirror directly. The extra variable is what lets a single loop stand in for arbitrary arrows, by carrying the position the arrows would have encoded.
The flattened routine computes exactly what the original did. What has it made harder for a later reader?
Finding a chunk's possible successors. In the original that is one outgoing arrow; in the rewrite it is every assignment to the control variable inside that arm, and any arm can in principle send control to any other. Reading the routine now means simulating a variable rather than following a path.
Does the theorem say anything about how many loops the structured version needs?
The classic construction needs exactly one, because the single loop plus the dispatch simulates every arrow. That is an existence result, not a recommendation — a hand-written structured version of the same routine usually has several loops, each around the repetition it actually expresses.

It is the difference between a route drawn on a map and a list of numbered instructions that each end with "now go to step 7". Both get you there; only one shows you the shape of the journey.

saying these in an interview costs you the question

Claims the rewrite reproduces the original's step-by-step execution
Says the construction needs no variables the original lacked
Treats the theorem as advice on how to write new code
Asserts the flattened form is shorter and easier to read
Names iteration as any loop shape, sequence as any ordering

The structured program theorem claims three control forms suffice — what does its construction add to the code?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What the theorem claims

The construction

Where the structure went

"Suffices" is a statement about possibility

What an interviewer is listening for

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

What the theorem claims

The construction

Where the structure went

"Suffices" is a statement about possibility

What an interviewer is listening for

answer

go deeper