Structured programming is a
programming 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...
aimed on improving the clarity, quality, and development time of a
computer programA 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
forIn 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 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....
s - in contrast to using simple tests and jumps such as the
gotogoto 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 codeSpaghetti 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 DijkstraEdsger 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 theoremThe 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
ALGOLALGOL 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..endifIn 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...
, switchIn 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...
, or caseIn 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
whileIn 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....
, repeatIn 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...
, forIn 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....
or do..untilIn 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 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 is a procedural, imperative computer programming language designed for scientific, engineering, business and systems programming applications...
- or the curly braces
{...} of
CC 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 languageA 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:
ALGOLALGOL 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...
,
PascalPascal 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/IPL/I is a procedural, imperative computer programming language designed for scientific, engineering, business and systems programming applications...
and
AdaAda 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 theoremThe 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 functionComputable 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 cycleAn 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 unitThe 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 machineA 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 GriesDavid 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 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 KnuthDonald 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
compilerA compiler is a computer program that transforms source code written in a programming language into another computer language...
s and
graph theoryIn 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
IBMInternational 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 MillsHarlan 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 is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
,
COBOLCOBOL 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
BASICBASIC 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.
CC 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 protocolA 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
statesIn 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
trampolineIn 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 flow
In 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 evaluation
Short-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 programming
Object-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 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...
s
- Structured exception handling
- Structure chart
A 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 statement
In 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