# Structured program theorem

Structured program theorem Graphical representation of the three basic patterns of the structured program theorem — sequence, selection, and repetition — using NS diagrams (blue) and flow charts (green).

The structured program theorem, also called the Böhm–Jacopini theorem,[1][2] is a result in programming language theory. It states that a class of control-flow graphs (historically called flowcharts in this context) can compute any computable function if it combines subprograms in only three specific ways (control structures). These are Executing one subprogram, and then another subprogram (sequence) Executing one of two subprograms according to the value of a boolean expression (selection) Repeatedly executing a subprogram as long as a boolean expression is true (iteration) The structured chart subject to these constraints 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 goto commands and exclusively uses subroutines, sequences, selection and iteration.

Contents 1 Origin and variants 1.1 Single-while-loop, folk version of the theorem 1.2 Böhm and Jacopini's proof 2 Implications and refinements 3 Application to Cobol 4 See also 5 References 6 Further reading Origin and variants The theorem is typically credited[3]: 381  to a 1966 paper by Corrado Böhm and Giuseppe Jacopini.[4] David Harel wrote in 1980 that the Böhm–Jacopini paper enjoyed "universal popularity",[3]: 381  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"[3]: 381  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.[3]: 383  Harel also writes that the more generic name was proposed by H.D. Mills as "The Structure Theorem" in the early 1970s.[3]: 381  Single-while-loop, folk version of the theorem This version of the theorem replaces all 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.[3]: 383  Another, even older source that Harel traced the folk version of the theorem is Stephen Kleene's normal form theorem from 1936.[3]: 383  Donald Knuth criticized this form of the proof, which results in pseudocode like the one below, by pointing out that the structure of the original program is completely lost in this transformation.[5]: 274  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."[6] p := 1 while p > 0 do if p = 1 then perform step 1 from the flowchart p := resulting successor step number of step 1 from the flowchart (0 if no successor) end if if p = 2 then perform step 2 from the flowchart p := resulting successor step number of step 2 from the flowchart (0 if no successor) end if ...