Structured program theorem

From Wikipedia, the free encyclopedia

The structured program theorem is a result in programming language theory. It states that every computable function can be implemented in a programming language that combines subprograms in only three specific ways. These three control structures are

Executing one subprogram, and then another subprogram (sequence)
Executing one of two subprograms according to the value of a boolean variable (selection)
Executing a subprogram until a boolean variable is true (iteration)

Computer scientists usually credit the theorem 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 notorious 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. [1]

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.

[edit] References

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).
Harel, David (1980). "On Folk Theorems". Communications of the ACM 23.
Dijkstra, Edsger (1968). "Go To Statement Considered Harmful". Communications of the ACM 3 http://www.acm.org/classics/oct95/.