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):
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.
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 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.
Structured programming is frequently stated as
The Reversible Structured Program Theorem is an important concept in the field of reversible computing. 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.
The BöhmâÂÂJacopini proof did not settle the question of whether to adopt structured programming for software development, partly because the construction was more likely to obscure a program than to improve it. On the contrary, it signaled 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 <code>break</code> and <code>return</code> 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.
Edward Yourdon 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 is 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 <code>leave label</code> 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 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 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:
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. 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 decompilers because the Java virtual machine code has branch instructions with targets expressed as offsets, but the high-level Java language only has multi-level <code>break</code> and <code>continue</code> statements. Ammarguellat (1992) proposed a transformation method that goes back to enforcing single-exit.
In the 1980s, IBM researcher Harlan Mills oversaw the development of the COBOL Structuring Facility, which applied a structuring algorithm to COBOL code. Mills's transformation involved the following steps for each procedure.
This construction can be improved by converting some cases of the selection statement into subprocedures.