2.1 What is Structured Programming?

Computer languages have gone through many changes over the past 4 or 5 decades. The early languages were very primitive by today's standards. We are currently in what is known as the fourth generation of languages (often abbreviated as 4GL). The details of this history are way beyond the scope of this class. Instead, we'll focus on one revolution in the field that occurred in the late 1960's and early to mid 1970's. It was called "structured programming".

The fervor generated by this revolution was intense (for a brief history see Schach, Software Engineering with JAVA, Irwin, 1997). There were strong proponents in both camps. But in the end structured programming was adopted as the standard for a generation of programmers. We'll see in what follows that structured programming is important not just for its historical significance. The lessons learned in the revolution are important lessons that every computer science student must learn.

It should be noted that there have been other, more recent revolutions as well. The next big one was Object-Oriented-Programming (OOP), beginning in the late 1980's and early 1990's. OOP is the dominant paradigm of programming today. You will learn more about OOP in the course that follow CM111.

To understand the structured programming revolution, you need to imagine what the field of programming was like before. At this time high-level, third generation languages like COBOL and FORTRAN were dominant. These languages used statements that read like English words. For example, one could read data from a file using a statement called "READ". One could write to a file using a statement called "WRITE". The previous generation of languages were almost unreadable when compared to these high-level languages.

The battle over structured programming was not about what language to use. It was about how a language was used. Programmers always have choices to make while they are writing code. A simple example is the choice of names for variables. Good variable names help make your programs easier to understand later. Short or non-descriptive variable names make your programs more difficult to understand later.

Spaghetti Code

The core issue of structured programming was branching. A branch is a decision the program makes while it is running. For example, if variable A is greater than variable B do this. Otherwise do something else. Prior to structured programming almost all programming was done with the "GOTO" statement. Programs would read like "if A is greater than B then GOTO line X".

One GOTO is easy enough to understand. Even two GOTO's in a program would not be difficult to manage. But try to imagine a large program with hundreds of GOTO statements. Understanding the flow through the program can be difficult to impossible. It can be so complex that the term "spaghetti code" has been used to describe it. Often it was easier to rewrite someone else's program than it was to try to understand it.

Program Maintainability

So why is program readability so important? If a program works why do you ever need to look at it again?

The answer is that software is always being modified and improved. Sometimes software is modified because the needs of the organization that uses it change. Sometimes it is modified to add new features or make it easier to use. Sometimes it contains bugs that need to be fixed.

Software engineers are people that study software and its development. They take a scientific approach by defining ways to measure software characteristics and keeping track of trends in the industry. They have shown us that more time and money are spent on software maintenance than on software production. In fact it is nearly twice as much.

It typically costs twice as much effort to keep a program working for a long time than it does to write it in the first place!

This means that software should be written in such a way that it can be easily modified later. Readability is the first step. A program must be readable to be understandable. You should get into the habit of writing programs that others can easily understand.

Enter Structured Programming

Structured programming eliminated the GOTO statement and gave us "programming structures". These structures are standardized and very readable. When you see a structure you know exactly how the flow of the program will proceed. With the GOTO on the other hand, you could branch from any point in a program to any other point. Programming structures clearly showed what part of a program was conditional (executed only under certain conditions) and which parts were always executed.

During the structured programming revolution many academic papers were produced. One of the most important ones was by Bohm and Jacopini (sp?). In their work they showed that only three programming structures were needed to get rid of the GOTO statement and make programs more readable. The three structures are "sequence", "selection" and "repetition".

These concepts are so important that they each deserve a separate section in this chapter, which will follow almost immediately.

It is probably worth noting that real programs will include arbitrary combinations of these structures. For example selection and sequence are often included inside of repetition. Even with the complexity of combinations, programs that use structures are much more readable than unstructured programs.

Sequence can be represented as follows:

Step A
Step B
Step C
  .
  .
  .

2.3 Selection

The following examples illustrate the improved readability of programming structures versus GOTO statements. They are in a make believe language that resembles BASIC on an Apple II (vintage late 1970's).

Selection Using GOTO:

100 IF A <= B THEN GOTO 130
110 PRINT A
120 GOTO 140
130 PRINT B
140 CONTINUE

Not all languages use line numbers for branching. In many languages you define labels instead. Labels have the advantage that they don't need to be changed when the lines are renumbered. In fact, then line numbers are irrelevant.

Here's the same example using a programming structure instead of GOTO's:

100 IF A > B THEN
110   PRINT A
120 ELSE
130   PRINT B
140 ENDIF

Exclusive Selection

Sometimes selection is exclusive. This means that if one block is executed then other blocks are not executed even if their corresponding conditions are true. Thus, if one block is executed then all others are "excluded".

This idea can be illustrated with some simple examples. Consider the following:

If you need milk, then go to the grocery store. If you need gas, then go to the gas station.

Now consider the following:

Buy some 2% milk if they have it, otherwise get 1% or skim milk if they don't have 1%.

2.4 Repetition

To illustrate the improved readability of programming structures, look at the following examples carefully.

Repetition Using GOTO's:

100 COUNT = 1
110 IF COUNT > 10 THEN GOTO 150
120 PRINT COUNT
130 COUNT = COUNT + 1
140 GOTO 110
150 CONTINUE

100 FOR COUNT = 1 TO 10
110   PRINT COUNT
120 NEXT COUNT

Finite Repetition

Finite repetition is one class of repetition structures. It is used when the number of iterations of the loop is known before the loop starts. Typically a counter is used to count the iterations of the loop, as in the previous example of the FOR loop. Here's a real-world example of finite repetition:

Jump up in the air 8 times.

Ask your neighbor for a number between 1 and 10 and jump up in the air that many times.

Pre-test Repetition

Repetition always involves a test to see if the repetition should continue. In pre-test repetition the condition is tested before the body of the loop is executed. It is possible that the body of the loop is never executed even once. Consider the following example:

Take all the coins out of your pocket one-by-one and give them to your teacher.

Post-test Repetition

In post-test repetition the condition is tested after the body of the loop executes. In this case the body of the loop will always executed at least once. Here's an example:

Take a deck of playing cards. Put the deck in front of you face down. Keep turning cards over until you see an ace.

2.5 The Difference between Structured and Non-Structured Programs

Each block of steps has exactly one entry point and one exit point.

Contrast this with the spaghetti code that results with the indiscriminant use of GOTO statements. If each block has only one entry point and one exit point you can easily visualize the flow of control around and through that block. With GOTO's it is often very difficult to visualize the flow of control as it winds here and there through the program.

There is also a slightly weaker definition of structured programming. It still requires one entry point for each block of steps, but allows more than one exit point. This is an issue that is still debated, but a large number of programmers support using multiple exit points. Usually a block has a primary exit point that is taken when things go normally. The secondary exit points are typically used when things go wrong. For example, imagine a loop that reads a file and processes the data one line at a time. If the data on one line is incomplete, or inconsistent, you probably want to generate an error message and proceed on to the next line in the file. In other words, there's no point in continuing the block because the data can't be processed anyway. In this case allowing multiple exit points actually makes the program more readable.

The exact definition(s) of structured programming will continue to be debated. But the lessons for programmers are clear. Whatever you can do to make a program more readable and maintainable is good and probably worth doing. Here is a short list of some of those things. Some things you can do right away, and some probably won't make sense until you have more programming experience. But it's never to early to start developing good programming habits.

1. Use good, descriptive variable names.
2. Use programming structures. Never use the GOTO statement.
3. Use comments to make the organization of your program clearer.
4. Avoid unnecessary complexity.
5. Make your program modular (use functions to organize processing).
6. Design for reusability whenever possible.

2.6 Questions

2. What generation of languages does COBOL belong to?

3. What is the dominant programming paradigm today?

4. What is spaghetti code?

5. On average how much time is spent on program maintenance versus program development in production programs?

6. What advantage do programming structures have over an equivalent block of code with GOTO statements?

7. Do modern programming languages have GOTO statements?

8. What are the three types of programming structures?

9. What is the difference between exclusive and non-exclusive selection? Give an example of each.

10. What is meant by the term "finite repetition"?

11. What is the difference between "pre-test" and "post-test" repetition?

12. Can programming structures be combined? (For example, can repetition include selection or sequence within it?)

13. Compilers ignore indentation of program statements. So why is indentation used?

14. Compilers change variable names into addresses when a program is compiled. Why does it make any difference what variable names you use?