Structured program theorem

The structured program theorem, also called the Böhm–Jacopini theorem, is a result in programming language theory. It states that a class of control-flow graphs (historically called flowcharts in this context) can compute any computable function 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, a programming paradigm which eschews goto commands and exclusively uses subroutines, sequences, selection and iteration. The theorem is typically credited to a 1966 paper by Corrado Böhm and Giuseppe Jacopini. 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 [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.