On Control Structures


The Structured Program Theorem   (aka The Structure Theorem)

What is the difference between a novel and a book? They really aren't the same thing! A novel is a relatively long fictional prose story. A book is a bound collection of pages. A novel is often published as a book - but it can also exist on microfilm or be stored electronically. Thus a novel is an abstract entity, whereas a book is one concrete way of implementing that entity.

Control Logic Structures are similarly abstract. When we speak of the control logic structures of Sequence, Selection, and Repetition (illustrated below)
            Sequence         Sequence Flowchart
            Selection         Selection Flowchart
            Repetition         Repetition Flowchart
we are talking about flow of control abstractions. It is possible to have a program contain repetition logic, for example, even if the computer programming language it is coded in does not have any loop statements. (Such programming languages do exist! Happily, Python and C++ do have loop statements, which makes programming in them much easier.)

Why are these three control logic structures important? To explain fully, we first have to define the term proper program:

A Proper Program has the following four characteristics:
  1. has one entry point,
  2. has one exit point,
  3. contains no dead code, and
  4. contains no eternal loops.
Don't worry about the one entry/exit point stuff. No dead code means a program does not contain code that is inherently unreachable and thus unexecutable. No eternal loops means no loops that are designed to run forever.

Please do not get hung up on the adjective proper; this is a formal term and does not mean "good" or "desirable" - it simply means the program possesses the four characteristics given above. However we will argue that proper programs are probably the only programs we are interested in coding, at least in this course. A program that never ends is not very useful (it is hard to hand in the execution results) and why would we want to insert dead code into a program?

Now that we know the formal meaning of proper program, and that these are the types of programs we want to construct, we finally get to what is probably the most significant discovery in computer science, at least as far as programming is concerned: the Structured Program Theorem. The Structured Program Theorem was first proven in 1966 by two Italian computer scientists, Corrado Böhm and Giuseppe Jacopini. However it went virtually unnoticed until Edsger Dijkstra wrote a paper in 1968 about the theorem's practical consequences. The following version of the the Structured Program Theorem is based on Linger, Mills, and Witt (1975):

The Structured Program Theorem - Any proper program can be constructed using only three control logic structures: sequence, selection, and repetition.

The major value of the Structured Program Theorem is in its proof that only a small set of control logic structures, suitably composed, can build any program we are interested in constructing. This is as important to computer science, as Dalton's atomic theory (that all matter in the universe is composed of atoms) was to chemistry.

The term Structured Programming was originally coined to describe the style of programming where programs were designed and built using only this limited set of control logic structures. You have been doing structured programming since the beginning of the course. Previously, you have been introduced to the if statement that provides a concrete way of implementing the selection control logic structure. You have also seen the while statement that provides a concrete way of implementing the repetition control logic structure. Sequence is provided by just listing one statement after another. Consequently, you have learned enough Python so that, in theory, you are now able to write a program to solve any problem you will ever be given!

Of course, theory is one thing and practice is another. For example, in theory, if you can walk, you can travel by foot to Alaska. But in practice, issues of cost and convenience are very important. Although all proper programs can be built using just the control logic constructs of sequence, selection, and repetition, it is convenient to add two additional control logic structures to our toolkit: case and repeat-until. We shall consider these two new constructs and ways of implementing them in Python, in the following sections.



The Case Construct
The selection control logic structure involves selecting from among two alternative actions. In the selection flowchart, we saw that we required either Task A or Task B to be performed. (However, sometimes Task B is the null task, that is, do nothing.) Regardless of which of these two tasks was performed, the flow of control resumed at a common exit point. Because of this behavior, selection can also be called simple alternation or two-way alternation because there are only two alternatives.

However, many times in designing a program it is convenient to consider directing the flow of control among more than two alternatives. The case control logic structure, also called multiple alternation, involves selecting from multiple (more than two) alternative actions. For example, the following flowchart depicts a case control logic structure that increments different counters depending on the value of a code variable.

            Case         Case Flowchart

The Python if statement provides one concrete way of implementing the case control logic structure. The case flowchart logic above could be implemented with the following code: 

         if code==1:
             countA+=1
         else:
             if code==3:
                 countB+=1
             else:
                 if code==6:
                     countC+=1
                 else:
                     countX+=1

The indentation of the code above does a poor job, however, of revealing the inherent case logic. That is, the indentation does not clearly reveal that each incrementation is one of a set of mutually exclusive alternatives. The multiway if indentation scheme that also uses the elif keyword would reveal this much more clearly and compactly: 

         if code==1:
             countA+=1
         elif code==3:
             countB+=1
         elif code==6:
             countC+=1
         else:
             countX+=1

To emphasize to someone reading the code that the same value is being testing in each if statement, often the boolean expression (predicate) in the first if is shifted a little to the right so as to align with the following boolean expressions. Also, a Python comment can be appended to the else explaining the conditions under which the last alternative is executed. The code would then look like this: 

         if   code==1:
             countA+=1
         elif code==3:
             countB+=1
         elif code==6:
             countC+=1
         else:  #otherwise
             countX+=1



The Repeat-Until Construct
The repetition control logic structure is a looping control structure in which the loop condition is tested at the beginning of the loop. For this reason, we sometimes identify this as a zero or more times loop, because if the boolean expression representing the loop condition should initially evaluate to false, the contents of the loop will never be executed. As we have seen, the Python while statement directly implements the repetition control logic structure. (Because of this close association, it is not uncommon for the repetition control logic structure to be called the while control logic structure.)

However, many times in designing a program it is convenient to use a loop in which the condition is tested at the end of the loop. The repeat-until control logic structure is a looping construct that exhibits such behavior. For this reason, we sometimes identify this as a one or more times loop, because the boolean expression is not even evaluated until one iteration of the loop has occurred. The following flowchart graphically depicts the repeat-until control logic structure. Notice that the loop is exited when the loop condition evaluates to true.
            Repeat-Until         repeat-until Flowchart

Interestingly, Python does not have a statement that exactly implements this abstract control logic structure! Many languages, such as Pascal and Ada, do have statements that directly implement the repeat-until control logic structure; in fact, in Pascal the statement is called the repeat-until statement. So why bring this up to Python programmers? Simply to point out once again that a control logic structure as a concept is different from the statement(s) that may implement the structure.

The repeat-until loop is not commonly used. In the C programming language (used to implement UNIX), the repeat-until construct is typically implemented using something called a DO-WHILE statement. A survey of the UNIX operating system software revealed that of all the loops found in the code, only about 4% were DO-WHILE loops.





"Dangerous" semi-Structured Statements:    The BREAK and CONTINUE statements

The break statement
The break statement can appear inside while and for loops. Executing the break inside a loop interrupts the flow of control by immediately exiting the loop. That is, executing the break inside a loop causes the program to skip straight to the statement following the loop. Although the break statement exists in Python, the circumstances where it would make sense to use the break statement in a loop are uncommon and consequently the break statement should be used with extreme caution.

One justifiable use of the break statement is when trying to implement a repeat-until loop in Python. (Although recall that the Structured Programming Theorem implies that repeat-until loops are never strictly necessary.)

In the following examples, a count-down from 10 to 1 is printed. The code on the left is in Pascal--a langugage that has a repeat-until statement. The code on the right implements the same logic in Python using a combination of while, if, and break statements.

  Pascal code fragment     Python equivalent   
  . . .
  x := 10;
  repeat
      writeln(x);  
      x := x-1
  until x = 0;
  writeln('Done');

  . . .

  . . .
  x = 10
  while True:
      print(x)
      x = x-1
      if x==0:
          break
  print('Done')  
  . . .

The continue statement
Having a continue statement in a program is potentially worse than using a break. Executing a continue causes the program to skip to the next iteration of the loop. Essentially it causes the remainder of the loop body code to be skipped for this iteration. Thus in a while loop it means the condition test is executed immediately. When used in a FOR statement, the continue causes the update section to be executed immediately. The use of the continue (by good programmers) is very rare.

The usual circumstance warranting the use of a continue is when the part of the loop that follows is extremely complicated and deeply nested, so that adding an if statement to bypass this code and indenting another level would nest the program too deeply. Consider the following example: 

         for row in range(0, 1024):
             for col in range(0, 512):
                 if row==col:
                     continue
                 ... other loop body statement(s) ...
In this example, every time row equals col, the remaining statements in the (inner) loop body will be skipped.



CONCLUDING PEARL OF WISDOM: Do not use break or continue statements in your programs.
The Structured Program Theorem shows they are unnecessary and the experiences of many programmers suggest using them can significantly decrease a program's clarity and maintainability.



For more information, see