Control structures: selection, loops and guarded commands

Control structures determine which statement the program executes and when. In theory very little is needed for this: Böhm and Jacopini (1966) showed that every algorithm can be written with sequence, selection and a pretest logical loop; no goto is needed. The reason languages offer more than this is writability and readability. On exams, switch/loop outputs and language design differences are asked most.

Golden rules:

1. In a switch, without break you fall into the cases below.
2. In the C/Java for loop the condition is re-evaluated before every iteration.
3. while runs 0 times, do-while at least 1 time.
4. continue skips the iteration but the update (i++) still runs.
5. In a guarded command, if more than one guard is true, the choice is nondeterministic.

Selection

Two-way selection

Design questions: what can be the type of the condition expression? Is the then/else part a single statement or a block? How is the meaning of nested selection determined?

• C89 and C++ accept an arithmetic expression as the condition (0 is false). Java and C# require a boolean.
• Dangling else: if (a) if (b) s1; else s2; which if does the else belong to? Java, C, C++, C#: the nearest unmatched if. Perl requires curly braces on every branch; Python determines it with indentation, Ruby and Ada with end / end if.

int y = 7;
if (y > 5)
    if (y > 10) System.out.println("big");
    else System.out.println("medium");

medium

Multiple-way selection: switch

int t = 0;
for (int k = 0; k < 5; k++) {
    switch (k % 3) {
        case 0: t += 1;          // no break: falls into case 1
        case 1: t += 10; break;
        default: t += 100;
    }
}
System.out.println(t);

142

k   k%3   what runs           t
0   0     +1, +10 (fell)      11
1   1     +10                 21
2   2     default +100        121
3   0     +1, +10             132
4   1     +10                 142

Writing empty cases one after another (case 1: case 2:) is allowed in every language. Multiple-way selection can always be written with nested else if too; in Python elif, and match since Python 3.10.

Counter-controlled loops

The loop variable is controlled by a start, end and step value (loop parameters). Design questions:

1. What are the type and scope of the loop variable?
2. Can the loop variable or parameters be changed in the body, does it affect the number of iterations?
3. Are the parameters evaluated once or on every iteration?
4. Is the value of the variable defined after the loop ends?

int n = 10, iters = 0;
for (int i = 0; i < n; i++) { n--; iters++; }
System.out.println(iters + " " + n);

5 5

Recipe for translating a C/Java for into a while (as in operational semantics):

e1;
while (e2) {
    body;
    e3;
}

Difference: the scope of a variable declared at the start of the for is limited to the loop; in the while version it remains outside. Also, a continue in the body goes to e3 in a for, but skips e3 in this translation.

Logically-controlled loops

int a = 10, w = 0, d = 0;
while (a < 10) { w++; a++; }          // pretest
a = 10;
do { d++; a++; } while (a < 10);      // posttest
System.out.println(w + " " + d);

0 1

A pretest (while) may never run the body; a posttest (do-while) runs it at least once. Java has no opposite of the posttest loop; Pascal’s repeat ... until stops when the condition becomes true.

User-located exit: break and continue

int count = 0;
outer:
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= 4; j++) {
        if (j == 3) continue outer;
        if (i == 3) break outer;
        count++;
    }
}
System.out.println(count);

4

• break: exits the innermost loop (or switch).
• continue: skips the rest of that iteration, the loop continues.
• Labeled break/continue: Java, C#, Perl (last/next). Not in C.
• A continue inside a switch applies not to the switch but to the nearest loop.

A labeled break is the “controlled” form of goto: it jumps only out of a loop, to a known point.

Iterator-based loops

They traverse the elements of a data structure in the structure’s own order: Java for (int v : arr), C# foreach, Python for x in seq, JavaScript for (const x of arr).

int[] arr = {1, 2, 3};
for (int v : arr) { v *= 2; }
System.out.println(arr[0] + arr[1] + arr[2]);

6

v is a copy of the element on each iteration. To change the array you need an indexed loop.

goto

The most powerful and most dangerous control statement. Unrestricted goto kills readability: the reader cannot know where control came from. Dijkstra wrote “Go To Statement Considered Harmful” in 1968. Java, Python and Ruby have no goto. C# allows goto, its most legitimate use being goto case inside a switch. The principle of structured programming: every structure has a single entry and (if possible) a single exit.

Guarded commands (Dijkstra, 1975)

Purpose: to make verification easier during development. There are two constructs.

Selection:

if <guard1> -> <stmt1>
[] <guard2> -> <stmt2>
...
fi

All guards are evaluated. If more than one is true, one is chosen nondeterministically. If none is true, there is a run-time error.

if x >= y -> max := x
[] y >= x -> max := y
fi

When x = y both guards are true, and whichever is chosen the result is the same. The programmer does not have to decide “which should I choose in case of equality?”

Loop:

do q1 > q2 -> swap(q1, q2)
[] q2 > q3 -> swap(q2, q3)
[] q3 > q4 -> swap(q3, q4)
od

On each iteration one of the true guards is chosen; it ends when none remains true. At the end it is certain that q1 ≤ q2 ≤ q3 ≤ q4. Even if you try all possible choice paths one by one from the start 4, 3, 2, 1, all end at 1, 2, 3, 4. Also the greatest common divisor:

do x > y -> x := x - y
[] y > x -> y := y - x
od                      x = 18, y = 12 → 6

Common mistakes

int t = 0;
for (int k = 0; k < 5; k++) {
    switch (k % 3) {
        case 0: t += 1;
        case 1: t += 10; break;
        default: t += 100;
    }
}
System.out.println(t);

int count = 0;
outer:
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= 4; j++) {
        if (j == 3) continue outer;
        if (i == 3) break outer;
        count++;
    }
}
System.out.println(count);

int sum = 0;
for (int i = 1; i <= 10; i++) {
    if (i % 3 == 0) continue;
    sum += i;
}
System.out.println(sum);

int a = 10, w = 0, d = 0;
while (a < 10) { w++; a++; }
a = 10;
do { d++; a++; } while (a < 10);
System.out.println(w + " " + d);

int n = 10, iters = 0;
for (int i = 0; i < n; i++) { n--; iters++; }
System.out.println(iters + " " + n);

int[] arr = {1, 2, 3};
for (int v : arr) { v *= 2; }
System.out.println(arr[0] + arr[1] + arr[2]);

String s = "b";
switch (s) {
    case "a": System.out.print("A");
    case "b": System.out.print("B");
    case "c": System.out.print("C"); break;
    default: System.out.print("D");
}

int y = 7;
if (y > 5)
    if (y > 10) System.out.println("big");
    else System.out.println("medium");

if x >= y -> max := x
[] y >= x -> max := y
fi

do q1 > q2 -> swap(q1, q2)
[] q2 > q3 -> swap(q2, q3)
[] q3 > q4 -> swap(q3, q4)
od

int z = 100, steps = 0;
while (true) {
    z /= 3;
    steps++;
    if (z < 5) break;
}
System.out.println(steps + " " + z);