Structured program theorem

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): ; Sequence: Executing one subprogram, and then another subprogram ; Selection: Executing one of two subprograms according to the value of a boolean expression ; Iteration: Repeatedly executing a subprogram as long as a boolean expression is true 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. (blue) and flow charts (green)|thumb|center|700px

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): Sequence: Executing one subprogram, and then another subprogram Selection: Executing one of two subprograms according to the value of a boolean expression Iteration: Repeatedly executing a subprogram as long as a boolean expression is true 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. (blue) and flow charts (green)|thumb|center|700px]] p := 1 while p > 0 do if p = 1 then perform step 1 from the flowchart p := resulting successor step number of step 1 from the flowchart (0 if no successor) end if if p = 2 then perform step 2 from the flowchart p := resulting successor step number of step 2 from the flowchart (0 if no successor) end if ... if p = n then perform step n from the flowchart p := resulting successor step number of step n from the flowchart (0 if no successor) end if end while Donald Knuth criticized this form of the proof, which results in pseudocode like the one above, by pointing out that the structure of the original program is completely lost in this transformation. Similarly, Bruce Ian Mills wrote about this approach that "The spirit of block structure is a style, not a language. By simulating a von Neumann machine, we can produce the behavior of any spaghetti code within the confines of a block-structured language. This does not prevent it from being spaghetti." ==Further reading==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366490702 under CC BY-SA 4.0; modifications have been made.