Structured Program Theorem

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

1. Executing one subprogram, and then another subprogram (sequence)
2. Executing one of two subprograms according to the value of a boolean expression (selection)
3. 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.