Structured programming
From Wikipedia, the free encyclopedia
Structured programming can be seen as a subset or subdiscipline of procedural programming, one of the major programming paradigms. It is most famous for removing or reducing reliance on the GOTO statement (also known as "go to").
Historically, several different structuring techniques or methodologies have been developed for writing structured programs. The most common are
- Dijkstra's structured programming, where the logic of a program is a structure composed of similar sub-structures in a limited number of ways. This reduces understanding a program to understanding each structure on its own, and in relation to that containing it, a useful separation of concerns.
- A view derived from Dijkstra's which also advocates splitting programs into sub-sections with a single point of entry, but is strongly opposed to the concept of a single point of exit.
- Data Structured Programming, which is based on aligning data structures with program structures. This approach applied the fundamental structures proposed by Dijkstra, but as constructs that used the high level structure of a program to be modeled on the underlying data structures being processed. There are at least 3 major approaches to data structured program design proposed by Jean-Dominique Warnier, Michael Jackson and Ken Orr.
Most people mean one of the two latter when they use the term structured programming, and that is what this article will discuss.
Contents |
[edit] Overview
[edit] Low-level structure
At a low level, structured programs are composed of simple, hierarchical program flow structures. These are regarded as single statements, and are at the same time ways of combining simpler statements, which may be one of these structures, or primitive statements such as assignments or procedure calls. The three types of structure identified by Dijkstra were concatenation, selection, and repetition.
"Concatenation" refers to a sequence of statements executed in order.
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..endif, switch, or case.
In "repetition" a statement is executed until the program reaches a certain state or applied to every element of a collection. This is usually expressed with keywords such as while, repeat, for or do..until. 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.
Some languages, such as Dijkstra's original Guarded Command Language, emphasise the unity of these structures with a syntax which completely encloses the structure, as in if..fi. In others, such as C, this is not the case, which increases the risk of misunderstanding and incorrect modification.
[edit] High-level structure
Coders should break larger pieces of code into shorter subroutines (functions, procedures, methods, blocks, or otherwise) that are small enough to be understood easily. In general, programs should use global variables sparingly; instead, subroutines should use local variables and take arguments by either value or reference. These techniques help to make small isolated pieces of code easier to understand without having to understand the whole program at once.
[edit] Design
Structured programming is often (but not always) associated with a "top-down" approach to design. In this way designers map out the large scale structure of a program in terms of smaller operations, implement and test the smaller operations, and then tie them together into a whole program.
[edit] 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 language. Since about 1970 when structured programming began to gain popularity as a technique, most new procedural programming languages have included features to encourage structured programming (and sometimes have left out features that would make unstructured programming easy). Some of the better known structured programming languages are Pascal, C, PL/I, and Ada.
[edit] History
[edit] Theoretical foundation
The structured program theorem 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.
[edit] Debate
P. J. Plauger, 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.
In 1967 a letter from Dijkstra appeared in Communications of the ACM with the heading "Go to statement considered harmful." The letter, which cited the Böhm and Jacopini proof, called for the abolishment of GOTO from high-level languages in the interest of improving code quality. This letter is usually cited as the beginning of the structured programming debate.
Although, as Plauger mentioned, many programmers unfamiliar with the theorem doubted its claims, the more significant dispute in the ensuing years was whether structured programming could actually improve software's clarity, quality, and development time enough to justify training programmers in it. Dijkstra claimed that limiting the number of structures would help to focus a programmer's thinking, and would simplify the task of ensuring the program's correctness by dividing analysis into manageable steps. In his 1969 Notes on Structured Programming, Dijkstra wrote:
- When we now take the position that it is not only the programmer's task to produce a correct program but also to demonstrate its correctness in a convincing manner, then the above remarks have a profound influence on the programmer's activity: the object he has to produce must be usefully structured.
- …In what follows it will become apparent that program correctness is not my only concern, program adaptability or manageability will be another… 1
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 compilers 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.
[edit] 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 FORTRAN, COBOL, and BASIC, now have them. It is difficult to find a programming educator who accepts the arbitrary use of GOTO statements by students.
As a programmer gains experience, he or she may find it easier to understand certain violations of the strict structured programming idea, and several programming languages in widespread use provide restricted jump statements and exception handling for use in these situations. The major industry languages (with the major exception of Java) also retain the GOTO statement for jumps within a procedure, and it remains widely used. Although Dijkstra succeeded in making structured programming the educational standard, he did not succeed in making it a strict requirement.
[edit] Common deviations
[edit] 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. On the other hand, structural programming without such a rule would result in very clean and readable code.
Most languages have adapted 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.
[edit] State machines
Some programs, particularly parsers and communications protocols, 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. However, some programmers (including Knuth) prefer to implement the state-changes with a jump to the new state.
[edit] See also
- Unstructured programming (contrast)
- Programming paradigms
- Control flow (more detail of high-level control structures)
- Structured exception handling
- Minimal evaluation
[edit] References
- Edsger Dijkstra, Notes on Structured Programming, pg. 6
- Böhm, C. and Jacopini, G.: Flow diagrams, Turing machines and languages with only two formation rules, CACM 9(5), 1966.
- Michael A. Jackson, Principles of Program Design, Academic Press, London, 1975.
