Structured programming
Encyclopedia
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 loop
s - in contrast to using simple tests and jumps such as the goto
statement which could lead to "spaghetti code
" which was both difficult to follow and to maintain.
It emerged in the 1960s, particularly from work by Böhm and Jacopini, and a famous letter, "Go To Statement Considered Harmful", from Edsger Dijkstra
in 1968—and was bolstered theoretically by the structured program theorem
, and practically by the emergence of languages such as ALGOL
with suitably rich control structures.
A language is described as block-structured when it has a syntax for enclosing structures between bracketed keywords, such as an if-statement bracketed by
, or a code section bracketed by
- or the curly braces
and many later languages.
. Some of the languages initially used for structured programming languages include: ALGOL
, Pascal
, PL/I
and Ada
- but most new procedural programming languages since that time have included features to encourage structured programming, and sometimes deliberatly left out features that would make unstructured programming easy.
provides the theoretical basis of structured programming. It states that three ways of combining programs—sequencing, selection, and iteration—are sufficient to express any computable function
. This observation did not originate with the structured programming movement; these structures are sufficient to describe the instruction cycle
of a central processing unit
, as well as the operation of a Turing machine
. Therefore a processor is always executing a "structured program" in this sense, even if the instructions it reads from memory are not part of a structured program. However, authors usually credit the result to a 1966 paper by Böhm and Jacopini, possibly because Dijkstra cited this paper himself. The structured program theorem does not address how to write and analyze a usefully structured program. These issues were addressed during the late 1960s and early 1970s, with major contributions by Dijkstra, Robert W. Floyd, Tony Hoare, and David Gries
.
, an early adopter of structured programming, described his reaction to the structured program theorem:
Donald Knuth
accepted the principle that programs must be written with provability in mind, but he disagreed (and still disagrees) with abolishing the GOTO statement. In his 1974 paper, "Structured Programming with Goto Statements", he gave examples where he believed that a direct jump leads to clearer and more efficient code without sacrificing provability. Knuth proposed a looser structural constraint: It should be possible to draw a program's flow chart with all forward branches on the left, all backward branches on the right, and no branches crossing each other. Many of those knowledgeable in compiler
s and graph theory
have advocated allowing only reducible flow graphs.
Structured programming theorists gained a major ally in the 1970s after IBM
researcher Harlan Mills
applied his interpretation of structured programming theory to the development of an indexing system for the New York Times research file. The project was a great engineering success, and managers at other companies cited it in support of adopting structured programming, although Dijkstra criticized the ways that Mills's interpretation differed from the published work.
As late as 1987 it was still possible to raise the question of structured programming in a computer science journal. Frank Rubin did so in that year with a letter, "'GOTO considered harmful' considered harmful." Numerous objections followed, including a response from Dijkstra that sharply criticized both Rubin and the concessions other writers made when responding to him.
, COBOL
, and BASIC
, now have them.
A typical example of a simple procedure would be reading data from a file and processing it:
open file;
while (reading not finished) {
read some data;
if (error) {
stop the subprogram and inform rest of the program about the error;
}
}
process read data;
finish the subprogram;
The "stop and inform" may be achieved by throwing an exception, second return from the procedure, labelled loop break, or even a goto. As the procedure has 2 exit points, it breaks the rules of Dijkstra's structured programming. Coding it in accordance with single point of exit rule would be very cumbersome. If there were more possible error conditions, with different cleanup rules, single exit point procedure would be extremely hard to read and understand, very likely even more so than an unstructured one with control handled by goto statements.
Most languages have adopted the multiple points of exit form of structural programming.
C
allows multiple paths to a structure's exit (such as "continue", "break", and "return"), newer languages have also "labelled breaks" (similar to the former, but allowing breaking out of more than just the innermost loop) and exceptions.
s, have a number of states
that follow each other in a way that is not easily reduced to the basic structures. It is possible to structure these systems by making each state-change a separate subprogram and using a variable to indicate the active state (see trampoline
). However, some programmers (including Knuth) prefer to implement the state-changes with a jump to the new state.
Programming paradigm
A programming paradigm is a fundamental style of computer programming. Paradigms differ in the concepts and abstractions used to represent the elements of a program and the steps that compose a computation A programming paradigm is a fundamental style of computer programming. (Compare with a...
aimed on improving the clarity, quality, and development time of a computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
by making extensive use of subroutines, block structures and for
For loop
In computer science a for loop is a programming language statement which allows code to be repeatedly executed. A for loop is classified as an iteration statement....
and while loop
While loop
In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given boolean condition. The while loop can be thought of as a repeating if statement....
s - in contrast to using simple tests and jumps such as the goto
Goto
goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...
statement which could lead to "spaghetti code
Spaghetti code
Spaghetti code is a pejorative term for source code that has a complex and tangled control structure, especially one using many GOTOs, exceptions, threads, or other "unstructured" branching constructs. It is named such because program flow tends to look like a bowl of spaghetti, i.e. twisted and...
" which was both difficult to follow and to maintain.
It emerged in the 1960s, particularly from work by Böhm and Jacopini, and a famous letter, "Go To Statement Considered Harmful", from 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...
in 1968—and was bolstered theoretically by the structured program theorem
Structured program theorem
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...
, and practically by the emergence of languages such as ALGOL
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
with suitably rich control structures.
Low-level structure Programming
At a low level, structured programs are often composed of simple, hierarchical program flow structures. These are sequence, selection, and repetition:- "Sequence" refers to an ordered execution of statements.
- In "selection" one of a number of statements is executed depending on the state of the program. This is usually expressed with keywords such as
if..then..else..endifConditional statementIn computer science, conditional statements, conditional expressions and conditional constructs are features of a programming language which perform different computations or actions depending on whether a programmer-specified boolean condition evaluates to true or false...
,switchSwitch statementIn computer programming, a switch, case, select or inspect statement is a type of selection control mechanism that exists in most imperative programming languages such as Pascal, Ada, C/C++, C#, Java, and so on. It is also included in several other types of languages...
, orcaseSwitch statementIn computer programming, a switch, case, select or inspect statement is a type of selection control mechanism that exists in most imperative programming languages such as Pascal, Ada, C/C++, C#, Java, and so on. It is also included in several other types of languages...
.
- In "repetition" a statement is executed until the program reaches a certain state, or operations have been applied to every element of a collection. This is usually expressed with keywords such as
whileWhile loopIn most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given boolean condition. The while loop can be thought of as a repeating if statement....
,repeatDo while loopIn most computer programming languages, a do while loop, sometimes just called a do loop, is a control flow statement that allows code to be executed repeatedly based on a given Boolean condition. Note though that unlike most languages, Fortran's do loop is actually analogous to the for loop.The...
,forFor loopIn computer science a for loop is a programming language statement which allows code to be repeatedly executed. A for loop is classified as an iteration statement....
ordo..untilDo while loopIn most computer programming languages, a do while loop, sometimes just called a do loop, is a control flow statement that allows code to be executed repeatedly based on a given Boolean condition. Note though that unlike most languages, Fortran's do loop is actually analogous to the for loop.The...
. Often it is recommended that each loop should only have one entry point (and in the original structural programming, also only one exit point, and a few languages enforce this).
A language is described as block-structured when it has a syntax for enclosing structures between bracketed keywords, such as an if-statement bracketed by
if..fi as in ALGOL 68ALGOL 68
ALGOL 68 isan imperative computerprogramming language that was conceived as a successor to theALGOL 60 programming language, designed with the goal of a...
, or a code section bracketed by
BEGIN..END, as in PL/IPL/I
PL/I is a procedural, imperative computer programming language designed for scientific, engineering, business and systems programming applications...
- or the curly braces
{...} of CC (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
and many later languages.
Structured programming languages
It is possible to do structured programming in any programming language, though it is preferable to use something like a procedural programming languageProgramming 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....
. Some of the languages initially used for structured programming languages include: ALGOL
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
, Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
, PL/I
PL/I
PL/I is a procedural, imperative computer programming language designed for scientific, engineering, business and systems programming applications...
and Ada
Ada (programming language)
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
- but most new procedural programming languages since that time have included features to encourage structured programming, and sometimes deliberatly left out features that would make unstructured programming easy.
Theoretical foundation
The structured program theoremStructured program theorem
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...
provides the theoretical basis of structured programming. It states that three ways of combining programs—sequencing, selection, and iteration—are sufficient to express any 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...
. This observation did not originate with the structured programming movement; these structures are sufficient to describe the instruction cycle
Instruction cycle
An instruction cycle is the basic operation cycle of a computer. It is the process by which a computer retrieves a program instruction from its memory, determines what actions the instruction requires, and carries out those actions...
of a central processing unit
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
, as well as the operation of a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
. Therefore a processor is always executing a "structured program" in this sense, even if the instructions it reads from memory are not part of a structured program. However, authors usually credit the result to a 1966 paper by Böhm and Jacopini, possibly because Dijkstra cited this paper himself. The structured program theorem does not address how to write and analyze a usefully structured program. These issues were addressed during the late 1960s and early 1970s, with major contributions by Dijkstra, Robert W. Floyd, Tony Hoare, and David Gries
David Gries
David Gries is an American computer scientist at Cornell University, United States. He is currently Associate Dean for Undergraduate Programs in the College of Engineering. His research interests include programming methodology and related areas such as programming languages, programming...
.
Debate
P. J. PlaugerP. J. Plauger
P. J. Plauger is an author and entrepreneur.He has written and co-written articles and books about programming style, software tools, and the C programming language....
, an early adopter of structured programming, described his reaction to the structured program theorem:
- Us converts waved this interesting bit of news under the noses of the unreconstructed assembly-language programmers who kept trotting forth twisty bits of logic and saying, 'I betcha can't structure this.' Neither the proof by Böhm and Jacopini nor our repeated successes at writing structured code brought them around one day sooner than they were ready to convince themselves.
Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
accepted the principle that programs must be written with provability in mind, but he disagreed (and still disagrees) with abolishing the GOTO statement. In his 1974 paper, "Structured Programming with Goto Statements", he gave examples where he believed that a direct jump leads to clearer and more efficient code without sacrificing provability. Knuth proposed a looser structural constraint: It should be possible to draw a program's flow chart with all forward branches on the left, all backward branches on the right, and no branches crossing each other. Many of those knowledgeable in compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
s and graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
have advocated allowing only reducible flow graphs.
Structured programming theorists gained a major ally in the 1970s after 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...
applied his interpretation of structured programming theory to the development of an indexing system for the New York Times research file. The project was a great engineering success, and managers at other companies cited it in support of adopting structured programming, although Dijkstra criticized the ways that Mills's interpretation differed from the published work.
As late as 1987 it was still possible to raise the question of structured programming in a computer science journal. Frank Rubin did so in that year with a letter, "'GOTO considered harmful' considered harmful." Numerous objections followed, including a response from Dijkstra that sharply criticized both Rubin and the concessions other writers made when responding to him.
Outcome
By the end of the 20th century nearly all computer scientists were convinced that it is useful to learn and apply the concepts of structured programming. High-level programming languages that originally lacked programming structures, such as FORTRANFortran
Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
, 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....
, and BASIC
BASIC
BASIC is a family of general-purpose, high-level programming languages whose design philosophy emphasizes ease of use - the name is an acronym from Beginner's All-purpose Symbolic Instruction Code....
, now have them.
Exception handling
Although there is almost never a reason to have multiple points of entry to a subprogram, multiple exits are often used to reflect that a subprogram may have no more work to do, or may have encountered circumstances that prevent it from continuing.A typical example of a simple procedure would be reading data from a file and processing it:
open file;
while (reading not finished) {
read some data;
if (error) {
stop the subprogram and inform rest of the program about the error;
}
}
process read data;
finish the subprogram;
The "stop and inform" may be achieved by throwing an exception, second return from the procedure, labelled loop break, or even a goto. As the procedure has 2 exit points, it breaks the rules of Dijkstra's structured programming. Coding it in accordance with single point of exit rule would be very cumbersome. If there were more possible error conditions, with different cleanup rules, single exit point procedure would be extremely hard to read and understand, very likely even more so than an unstructured one with control handled by goto statements.
Most languages have adopted the multiple points of exit form of structural programming.
C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
allows multiple paths to a structure's exit (such as "continue", "break", and "return"), newer languages have also "labelled breaks" (similar to the former, but allowing breaking out of more than just the innermost loop) and exceptions.
State machines
Some programs, particularly parsers and communications protocolCommunications protocol
A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications...
s, have a number of states
State (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
that follow each other in a way that is not easily reduced to the basic structures. It is possible to structure these systems by making each state-change a separate subprogram and using a variable to indicate the active state (see trampoline
Trampoline (computers)
In computer programming, the word trampoline has a number of meanings, and is generally associated with jumps .- Low Level Programming :...
). However, some programmers (including Knuth) prefer to implement the state-changes with a jump to the new state.
See also
- Control flowControl flowIn computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
(more detail of high-level control structures) - Minimal evaluationMinimal evaluationShort-circuit evaluation, minimal evaluation, or McCarthy evaluation denotes the semantics of some Boolean operators in some programming languages in which the second argument is only executed or evaluated if the first argument does not suffice to determine the value of the expression: when the...
- Object-oriented programmingObject-oriented programmingObject-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
- Nassi–Shneiderman diagram
- Programming paradigmProgramming paradigmA programming paradigm is a fundamental style of computer programming. Paradigms differ in the concepts and abstractions used to represent the elements of a program and the steps that compose a computation A programming paradigm is a fundamental style of computer programming. (Compare with a...
s - Structured exception handling
- Structure chartStructure chartA Structure Chart in software engineering and organizational theory, is a chart which shows the breakdown of a system to its lowest manageable levels. They are used in structured programming to arrange program modules into a tree. Each module is represented by a box, which contains the module's name...
- Switch statementSwitch statementIn computer programming, a switch, case, select or inspect statement is a type of selection control mechanism that exists in most imperative programming languages such as Pascal, Ada, C/C++, C#, Java, and so on. It is also included in several other types of languages...
, a case of multiple GOTOs
External links
- BPStruct - A tool to structure concurrent systems (programs, process models)
- Notes on Structured Programming and Variation Analysis (Programming Wisdom Center)
- Algobuild: Free editor for structured flow charts and pseudo code (EN - IT)