Structured program theorem
||This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (June 2011)|
The structured program theorem, also called Böhm-Jacopini theorem, is a result in programming language theory. It states that a given class of algorithms can compute any computable function if those algorithms combine subprograms in only three specific ways. In other words, any algorithm can be expressed using only three control structures. They are
- Executing one subprogram, and then another subprogram (sequence)
- Executing one of two subprograms according to the value of a boolean expression (selection)
- Executing a subprogram until a boolean expression is true (iteration)
The theorem is credited to a 1966 paper by Corrado Böhm and Giuseppe Jacopini. However, David Harel traced its origins to the 1946 description of the von Neumann architecture and Stephen Kleene's normal form theorem.
The Böhm-Jacopini proof describes how to construct a structured flow chart from an arbitrary chart, using the bits in an extra integer variable to keep track of information that the original program represents by the program location. This construction was based on Böhm's programming language P′′. 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 signalled the beginning of the debate. Edsger Dijkstra's famous letter, "Go To Statement Considered Harmful," followed in 1968. Subsequent proofs of the theorem addressed practical shortcomings of the Böhm-Jacopini proof with constructions that maintained or improved the clarity of the original program.
Application to Cobol
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.
- Identify the basic blocks in the procedure.
- Assign a unique label 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.
Note that this construction can be improved by converting some cases of the selection statement into subprocedures.
- (English) The Böhm–Jacopini Theorem is False, Propositionally
- Ashcroft, Edward; and Zohar Manna (1971). "The translation of go to programs to 'while' programs". Proceedings of IFIP Congress.
- Bohm, Corrado; and Giuseppe Jacopini (May 1966). "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules". Communications of the ACM 9 (5): 366–371. doi:10.1145/355592.365646.
- Harel, David (1980). "On Folk Theorems". Communications of the ACM 23 (7): 379–389. doi:10.1145/358886.358892.
- Dijkstra, Edsger (1968). "Go To Statement Considered Harmful". Communications of the ACM 11 (3): 147–148. doi:10.1145/362929.362947. http://www.acm.org/classics/oct95/