The structured program theorem is a result in programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

 theory. It states that every computable function

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...

 can be implemented in a programming language that combines subprograms in only three specific ways. These three control structures are

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

Computer scientists usually credit the theorem to a 1966 paper by Corrado Böhm

Corrado Böhm

Corrado Böhm , Professor Emeritus at the University of Rome "La Sapienza", is a computer scientist known especially for his contributions to the theory of structured programming, constructive mathematics, combinatory logic, lambda-calculus, and the semantics and implementation of functional...

 and Giuseppe Jacopini. However, David Harel

David Harel

David Harel is a professor of computer science at the Weizmann Institute of Science in Israel. Born in London, England, he was Dean of the Faculty of Mathematics and Computer Science at the institute for seven years.-Biography:...

 traced its origins to the 1946 description of the von Neumann architecture

Von Neumann architecture

The term Von Neumann architecture, aka the Von Neumann model, derives from a computer architecture proposal by the mathematician and early computer scientist John von Neumann and others, dated June 30, 1945, entitled First Draft of a Report on the EDVAC...

 and Stephen Kleene's normal form theorem

Kleene's T predicate

In computability theory, the T predicate, first studied by mathematician Stephen Cole Kleene, is a particular set of triples of natural numbers that is used to represent computable functions within formal theories of arithmetic...

.

The Böhm-Jacopini proof describes how to construct a structured flow chart from an arbitrary chart, using the bit

Bit

A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

s 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

Structured programming

Structured programming is a programming paradigm aimed on improving the clarity, quality, and development time of a computer program by making extensive use of subroutines, block structures and for and while loops - in contrast to using simple tests and jumps such as the goto statement which could...

 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

Edsger Dijkstra

Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...

'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.http://www.cse.buffalo.edu/~rapaport/111F04/greatidea3.html

Application to Cobol

In the 1980s IBM

IBM

International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...

 researcher Harlan Mills

Harlan Mills

Harlan D. Mills was Professor of Computer Science at the Florida Institute of Technology and founder of Software Engineering Technology, Inc. of Vero Beach, Florida . Mills' contributions to software engineering have had a profound and enduring effect on education and industrial practice. Since...

 oversaw the development of the COBOL Structuring Facility, which applied a structuring algorithm to COBOL

COBOL

COBOL is one of the oldest programming languages. Its name is an acronym for COmmon Business-Oriented Language, defining its primary domain in business, finance, and administrative systems for companies and governments....

 code. Mills's transformation involved the following steps for each procedure.

1. Identify the basic block
   Basic block
   In computing, a basic block is a portion of the code within a program with certain desirable properties that make it highly amenable to analysis. Compilers usually decompose programs into their basic blocks as a first step in the analysis process...
   
   s in the procedure.
2. Assign a unique label
   Label (programming language)
   A label in a programming language is a sequence of characters that identifies a location within source code. In most languages labels take the form of an identifier, often followed by a punctuation character . In many high level programming languages the purpose of a label is to act as the...
   
   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.
3. Break the procedure into its basic blocks.
4. For each block that is the destination of only one exit path, reconnect that block to that exit path.
5. Declare a new variable in the procedure (called L for reference).
6. On each remaining unconnected exit path, add a statement that sets L to the label value on that path.
7. Combine the resulting programs into a selection statement that executes the program with the entry path label indicated by L
8. Construct a loop that executes this selection statement as long as L is not 0.
9. 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.