The structured program theorem, also called the Böhm–Jacopini theorem,
is a result in
programming language theory
Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages. Programming language theory is clos ...
. It states that a class of
control-flow graphs (historically called
flowcharts in this context) can compute any
computable function
Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...
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, 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 Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making specific disciplined use of the structured control flow constructs of selection ( if/then/else) and repet ...
, a programming paradigm which eschews
goto commands and exclusively uses subroutines, sequences, selection and iteration.

Origin and variants
The theorem is typically credited
[ to a 1966 paper by ]Corrado Böhm
Corrado Böhm (17 January 1923 – 23 October 2017) was an Italian computer scientist and Professor Emeritus at the Sapienza University of Rome, University of Rome "La Sapienza", known especially for his contributions to the theory of structured ...
and . David 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 he 1966 Böhm–Jacopini paperis 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
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
.[
Harel also writes that the more generic name was proposed by H.D. Mills as "The Structure Theorem" in the early 1970s.]
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
The program counter (PC), commonly called the instruction pointer (IP) in Intel x86 and Itanium microprocessors, and sometimes called the instruction address register (IAR), the instruction counter, or just part of the instruction sequencer, ...
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
The von Neumann architecture—also known as the von Neumann model or Princeton architecture—is a computer architecture based on the '' First Draft of a Report on the EDVAC'', written by John von Neumann in 1945, describing designs discus ...
, which explains how a program counter
The program counter (PC), commonly called the instruction pointer (IP) in Intel x86 and Itanium microprocessors, and sometimes called the instruction address register (IAR), the instruction counter, or just part of the instruction sequencer, ...
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
Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its exec ...
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
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
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. 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."
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
...
if p = n then
perform step n from the flowchart
p := resulting successor step number of step n from the flowchart (0 if no successor)
end if
end while
Böhm and Jacopini's proof
The proof in Böhm and Jacopini's paper proceeds by induction on the structure of the flow chart.[ Because it employed pattern matching in graphs, the proof of Böhm and Jacopini's was not really practical as a ]program transformation
A program transformation is any operation that takes a computer program and generates another program. In many cases the transformed program is required to be semantically equivalent to the original, relative to a particular Formal semantics of p ...
algorithm, and thus opened the door for additional research in this direction.[
]
Reversible version
The Reversible Structured Program Theorem is an important concept in the field of reversible computing
Reversible computing is any model of computation where every step of the process is time-reversible. This means that, given the output of a computation, it's possible to perfectly reconstruct the input. In systems that progress deterministica ...
. It posits that any computation achievable by a reversible program can also be accomplished through a reversible program using only a structured combination of control flow constructs such as sequences, selections, and iterations. Any computation achievable by a traditional, irreversible program can also be accomplished through a reversible program, but with the additional constraint that each step must be reversible and some extra output. Furthermore, any reversible unstructured program can also be accomplished through a structured reversible program with only one iteration without any extra output. This theorem lays the foundational principles for constructing reversible algorithms within a structured programming framework.
For the Structured Program Theorem, both local[ and global methods of proof are known. However, for its reversible version, while a global method of proof is recognized, a local approach similar to that undertaken by Böhm and Jacopini][ is not yet known. This distinction is an example that underscores the challenges and nuances in establishing the foundations of reversible computing compared to traditional computing paradigms.
]
Implications and refinements
The Böhm–Jacopini proof did not settle the question of whether to adopt structured programming Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making specific disciplined use of the structured control flow constructs of selection ( if/then/else) and repet ...
for software development, partly because the construction was more likely to obscure a program than to improve it. On the contrary, it signalled the beginning of the debate. Edsger Dijkstra's famous letter, " Go To Statement Considered Harmful," followed in 1968.
Some academics took a purist approach to the Böhm–Jacopini result and argued that even instructions like break
and return
from the middle of loops are bad practice as they are not needed in the Böhm–Jacopini proof, and thus they advocated that all loops should have a single exit point. This purist approach is embodied in the Pascal programming language (designed in 1968–1969), which up to the mid-1990s was the preferred tool for teaching introductory programming classes in academia.[Roberts, E. 995br>Loop Exits and Structured Programming: Reopening the Debate]
" ACM SIGCSE Bulletin, (27)1: 268–272.
Edward Yourdon
Edward Nash Yourdon (April 30, 1944 – January 20, 2016) was an American software engineer, computer consultant, author and lecturer, and software engineering methodology pioneer. He was one of the lead developers of the structured analysis tec ...
notes that in the 1970s there was even philosophical opposition to transforming unstructured programs into structured ones by automated means, based on the argument that one needed to think in structured programming fashion from the get go. The pragmatic counterpoint was that such transformations benefited a large body of existing programs. Among the first proposals for an automated transformation was a 1971 paper by Edward Ashcroft and Zohar Manna.
The direct application of the Böhm–Jacopini theorem may result in additional local variables being introduced in the structured chart, and may also result in some code duplication. The latter issue is called the loop and a half problem in this context. Pascal is affected by both of these problems and according to empirical studies cited by Eric S. Roberts, student programmers had difficulty formulating correct solutions in Pascal for several simple problems, including writing a function for searching an element in an array. A 1980 study by Henry Shapiro cited by Roberts found that using only the Pascal-provided control structures, the correct solution was given by only 20% of the subjects, while no subject wrote incorrect code for this problem if allowed to write a return from the middle of a loop.[
In 1973, S. Rao Kosaraju proved that it's possible to avoid adding additional variables in structured programming, as long as arbitrary-depth, multi-level breaks from loops are allowed.][ Furthermore, Kosaraju proved that a strict hierarchy of programs exists, nowadays called the ''Kosaraju hierarchy'', in that for every integer ''n'', there exists a program containing a multi-level break of depth ''n'' that cannot be rewritten as program with multi-level breaks of depth less than ''n'' (without introducing additional variables).][ Kosaraju cites the multi-level break construct to the BLISS programming language. The multi-level breaks, in the form a ]leave ''label''
keyword were actually introduced in the BLISS-11 version of that language; the original BLISS only had single-level breaks. The BLISS family of languages didn't provide an unrestricted goto. The Java programming language
Java is a high-level, general-purpose, memory-safe, object-oriented programming language. It is intended to let programmers ''write once, run anywhere'' ( WORA), meaning that compiled Java code can run on all platforms that support Jav ...
would later follow this approach as well.
A simpler result from Kosaraju's paper is that a program is reducible to a structured program (without adding variables) if and only if it does not contain a loop with two distinct exits. Reducibility was defined by Kosaraju, loosely speaking, as computing the same function and using the same "primitive actions" and predicates as the original program, but possibly using different control flow structures. (This is a narrower notion of reducibility than what Böhm–Jacopini used.) Inspired by this result, in section VI of his highly-cited paper that introduced the notion of cyclomatic complexity, Thomas J. McCabe described an analogue of Kuratowski's theorem
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a Glossary of graph theory#Su ...
for the control-flow graphs (CFG) of non-structured programs, which is to say, the minimal subgraphs that make the CFG of a program non-structured. These subgraphs have a very good description in natural language. They are:
# branching out of a loop (other than from the loop cycle test)
# branching into a loop
# branching into a decision (i.e. into an if "branch")
# branching out of a decision
McCabe actually found that these four graphs are not independent when appearing as subgraphs, meaning that a necessary and sufficient condition for a program to be non-structured is for its CFG to have as subgraph one of any subset of three of these four graphs. He also found that if a non-structured program contains one of these four sub-graphs, it must contain another distinct one from the set of four. This latter result helps explain how the control flow of non-structured program becomes entangled in what is popularly called " spaghetti code". McCabe also devised a numerical measure that, given an arbitrary program, quantifies how far off it is from the ideal of being a structured program; McCabe called his measure essential complexity.[The original paper is For a secondary exposition see ]
McCabe's characterization of the forbidden graphs for structured programming can be considered incomplete, at least if the Dijkstra's D structures are considered the building blocks.
Up to 1990 there were quite a few proposed methods for eliminating gotos from existing programs, while preserving most of their structure. The various approaches to this problem also proposed several notions of equivalence, which are stricter than simply Turing equivalence, in order to avoid output like the folk theorem discussed above. The strictness of the chosen notion of equivalence dictates the minimal set of control flow structures needed. The 1988 JACM paper by Lyle Ramshaw surveys the field up to that point, as well proposing its own method. Ramshaw's algorithm was used for example in some Java decompiler
A decompiler is a computer program that translates an executable file back into high-level source code. Unlike a compiler, which converts high-level code into machine code, a decompiler performs the reverse process. While disassemblers translate e ...
s because the Java virtual machine
A Java virtual machine (JVM) is a virtual machine that enables a computer to run Java programs as well as programs written in other languages that are also compiled to Java bytecode. The JVM is detailed by a specification that formally descr ...
code has branch instructions with targets expressed as offsets, but the high-level Java language only has multi-level break
and continue
statements. Ammarguellat (1992) proposed a transformation method that goes back to enforcing single-exit.
Application to Cobol
In the 1980s IBM
International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...
researcher Harlan Mills oversaw the development of the COBOL Structuring Facility, which applied a structuring algorithm to COBOL
COBOL (; an acronym for "common business-oriented language") is a compiled English-like computer programming language designed for business use. It is an imperative, procedural, and, since 2002, object-oriented language. COBOL is primarily ...
code. Mills's transformation involved the following steps for each procedure.
#Identify the basic block
In compiler construction, a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit. This restricted form makes a basic block highly amenable to analysis. Compilers usually decom ...
s in the procedure.
#Assign a unique label
A label (as distinct from signage) is a piece of paper, plastic film, cloth, metal, or other material affixed to a container or product. Labels are most often affixed to packaging and containers using an adhesive, or sewing when affix ...
to each block's entry path, and label each block's exit paths with the labels of the entry paths they connect to. Use 0 for return from the procedure and 1 for the procedure's entry path.
#Break the procedure into its basic blocks.
#For each block that is the destination of only one exit path, reconnect that block to that exit path.
#Declare a new variable in the procedure (called L for reference).
#On each remaining unconnected exit path, add a statement that sets L to the label value on that path.
#Combine the resulting programs into a selection statement that executes the program with the entry path label indicated by L
#Construct a loop that executes this selection statement as long as L is not 0.
#Construct a sequence that initializes L to 1 and executes the loop.
This construction can be improved by converting some cases of the selection statement into subprocedures.
See also
*Structured programming Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making specific disciplined use of the structured control flow constructs of selection ( if/then/else) and repet ...
*Turing completeness
In computability theory, a system of data-manipulation rules (such as a model of computation, a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can b ...
References
Further reading
Material not yet covered above:
*
* {{cite book , doi = 10.1007/3-540-57785-8_128 , chapter=One binary horn clause is enough , volume=775 , date=1994 , pages=19–32 , first=Philippe , last=Devienne, title=Stacs 94 , series=Lecture Notes in Computer Science , isbn=978-3-540-57785-0 , citeseerx=10.1.1.14.537
Programming language theory
Models of computation
Theorems in computational complexity theory