In programming language theory, the structured program theorem, generally called the Böhm–Jacopini theorem, states that a class of control-flow graphs (historically called flowcharts in this context) can compute any computable function using only the following three control structures to combine subprograms (statements and blocks):
Sequence Executing one subprogram, and then another subprogram Selection Executing one of two subprograms according to the value of a boolean expression Iteration Repeatedly executing a subprogram as long as a boolean expression is true More precise definitions are listed in the next section. The structured chart subject to these constraints, particularly the loop constraint implying a single exit (as described later in this article), may however use additional variables in the form of bits (stored in an extra integer variable in the original proof) in order to keep track of information that the original program represents by the program location. The construction was based on Böhm's programming language P′′. The theorem forms the basis of structured programming, a programming paradigm which eschews the goto statement, exclusively using other control semantics for selection and iteration.
Origin and variants In 1964, Corrado Böhm had defined a simple Turing-complete programming language (P′′), based on sequence and iteration. In a subsequent paper, Böhm and Giuseppe Jacopini restated this result. The structured program theorem is typically credited to that 1966 paper. Harel wrote in 1980 that the Böhm–Jacopini paper enjoyed "universal popularity", particularly with proponents of structured programming. Harel also noted that "due to its rather technical style [the 1966 Böhm–Jacopini paper] is apparently more often cited than read in detail", and after reviewing a large number of papers published up to 1980, Harel argued that the contents of the Böhm–Jacopini proof were usually misrepresented as a folk theorem that essentially contains a simpler result, a result which itself can be traced to the inception of modern computing theory in the papers of von Neumann and Kleene. Harel also writes that the more generic name was proposed by H.D. Mills as "The Structure Theorem" in the early 1970s. The evolution of the theorem was as follows.
1. Böhm 1964 (Program Creation / Computation)
Result Every partial recursive function can be computed by a program using only sequence and iteration. Notes This result focuses on program generation. Selection is not required: conditional behavior is encoded by loops. P′′ prevents unstructured control flow through language design, enforcing structure at the source. Böhm restates his results in part 2 of Böhm-Jacopini (1966).
2. Böhm–Jacopini 1966 (Program Transformation) Result Every flowchart (control-flow graph, CFG) can be transformed into a structured program using only sequence and iteration. Notes This version of the theorem focuses on program transformation. It is primarily relevant to compiler optimization, rather than to software design decisions. In part 1 of Böhm–Jacopini (1966), Jacopini proves that any control-flow graph (CFG) can be rewritten as a structured graph, using only selection, sequence, and iteration, while preserving the original program’s structure. In part 2, Böhm shows that selection is not strictly necessary: any CFG can be transformed using only sequence and iteration.
Jacopini's proof proceeds by induction on the structure of the flow chart. Because it employed pattern matching in graphs, the proof was not really practical as a program transformation algorithm, and thus opened the door for additional research in this direction.
3. Folk Theorem (Loop-Minimal Transformation) Result Every flowchart is equivalent to a while-program with one occurrence of while-do, provided additional variables are allowed. Notes This version of the theorem flattens the Böhm–Jacopini transformation, reducing all iteration to one single loop. Selection is reintroduced for clarity, but is theoretically optional. The folk theorem replaces the original program's control flow with a single global while loop that simulates a program counter going over all possible labels (flowchart boxes) in the original non-structured program. Harel traced the origin of this folk theorem to two papers marking the beginning of computing. One is the 1946 description of the von Neumann architecture, which explains how a program counter operates in terms of a while loop. Harel notes that the single loop used by the folk version of the structured programming theorem basically just provides operational semantics for the execution of a flowchart on a von Neumann computer. Another, even older source that Harel traced the folk version of the theorem is Stephen Kleene's normal form theorem from 1936.
Donald Knuth criticized this form of the proof, which results in pseudocode like the one above, by pointing out that the structure of the original program is completely lost in this transformation. Similarly, Bruce Ian Mills wrote about this approach that "The spirit of block structure is a style, not a language. By simulating a von Neumann machine, we can produce the behavior of any spaghetti code within the confines of a block-structured language. This does not prevent it from being spaghetti."
4. Modern Textbook Statement Structured programming is frequently stated as
Result Every partial recursive function can be computed by a structured program using (selection, ) sequence and iteration; moreover, with suitable encodings of control state, a single while loop suffices. Notes This combines: Böhm (1964) – who proved that for every partial recursive function there exists a (structured) program P′′ which computes it — establishing the existence of an algorithm rather than rewriting an existing one; Böhm–Jacopini (1966) – which shows that any existing program or flowchart can be rewritten using only selection, sequence, and iteration (with selection in fact redundant); The folklore single-loop result, showing that iteration can be reduced to one loop via explicit control-state encoding.
… excerpt ends here. Continue reading the full article.
