Session 16

This session takes a small program written earlier (a menu-driven bank balance in C), checks it against the structured programming paradigm, lists every construct that breaks the paradigm with a line reference, and rewrites it so that only sequence, selection and iteration remain. The rewritten program produces byte-for-byte the same output on the same input, which is how you prove the rewrite changed structure and not behaviour. Structured programming is the reason code from Session 13 can be reviewed, tested and changed at all.

Objectives

• State the three control structures of structured programming and the single-entry, single-exit rule.
• Recognise goto, jumps out of nested loops, mid-function return, and flag variables as violations, and say which rule each one breaks.
• Rewrite a working program using while, switch and if only, one entry and one exit per function.
• Prove behaviour is unchanged by running both versions on the same input.

Problem Statement

Session 16: Select a small portion of any program written by you. Check if the portion of code selected by you is having constructs that violate the structured programming paradigm. If yes, then rewrite the code to conform to structured programming paradigm. If no, check another portion of code.

Concept

The three structures

Bohm and Jacopini showed that any computable program can be written with only three control structures, each with one entry point and one exit point:

• Sequence: statements executed one after another.
• Selection: if, if-else, switch; choose one of several blocks, then continue after the block.
• Iteration: while, for, do-while; repeat a block while a condition holds, then continue after the loop.

A block built from these can be read top to bottom, and the state at any line depends only on the lines above it in that block. That property is what a code reviewer relies on.

What breaks the paradigm

break inside a switch and a loop-controlling boolean in the while condition are accepted in practice because they keep one exit per structure. The pure form avoids even those; this session uses them because C has no other way to leave a switch.

How to rewrite

1. Every goto loop becomes a while with a condition variable.
2. Every goto out of a nested loop becomes a loop condition that includes “not yet found”.
3. Every early return becomes an assignment to a status variable inside an if-else chain, with one return at the end.
4. Every flag tested far from where it was set is either deleted (the test moves next to the condition) or becomes the loop condition.
5. Repeated blocks under different labels become functions with one job each.

Code Selected for Review

The portion is the complete unstructured.c (86 lines): a bank balance program with a menu for deposit, withdraw, show balance and exit. Withdrawals are paid out in 500 and 200 rupee notes, so an amount that cannot be formed from those notes is refused. The program works; it was written quickly and never reviewed.

/*
 * unstructured.c
 * Menu-driven bank balance: deposit, withdraw, show balance, exit.
 * Withdrawals are paid out in 500 and 200 rupee notes only.
 * Works, but the control flow is built from goto, flags and early returns.
 */
#include <stdio.h>

int balance = 0;
int flag = 0;      /* 0 = nothing, 1 = notes found, 2 = error already printed */

/* Returns 0 on success, -1 bad amount, -2 insufficient funds, -3 no notes */
int withdraw(int amount)
{
    int fives, twos;
    if (amount <= 0)
        return -1;
    if (amount > balance)
        return -2;
    flag = 0;
    for (fives = amount / 500; fives >= 0; fives--) {
        for (twos = 0; twos * 200 <= amount; twos++) {
            if (fives * 500 + twos * 200 == amount) {
                flag = 1;
                goto found;
            }
        }
    }
found:
    if (flag != 1)
        return -3;
    balance -= amount;
    printf("Paid %d as %d x 500 and %d x 200\n", amount, fives, twos);
    return 0;
}

int main(void)
{
    int choice, amount, result;
menu:
    printf("\n1 Deposit  2 Withdraw  3 Balance  4 Exit\nChoice: ");
    if (scanf("%d", &choice) != 1)
        goto quit;
    if (choice == 1)
        goto deposit;
    if (choice == 2)
        goto withdraw;
    if (choice == 3)
        goto show;
    if (choice == 4)
        goto quit;
    printf("Invalid choice\n");
    goto menu;
deposit:
    printf("Amount: ");
    if (scanf("%d", &amount) != 1)
        goto quit;
    flag = 0;
    if (amount <= 0) {
        printf("Invalid amount\n");
        flag = 2;
    }
    if (flag == 2)
        goto menu;
    balance += amount;
    printf("Deposited %d\n", amount);
    goto menu;
withdraw:
    printf("Amount: ");
    if (scanf("%d", &amount) != 1)
        goto quit;
    result = withdraw(amount);
    if (result == -1)
        printf("Invalid amount\n");
    if (result == -2)
        printf("Insufficient balance\n");
    if (result == -3)
        printf("Amount cannot be paid in 500 and 200 notes\n");
    goto menu;
show:
    printf("Balance: %d\n", balance);
    goto menu;
quit:
    printf("Bye\n");
    return 0;
}

Violations Found

Every violation is one of four kinds: goto, jump out of a loop, mid-function return, or a flag carried across blocks. The rewrite has none of them.

Rewritten Program

/*
 * structured.c
 * Same bank balance program as unstructured.c, rewritten with only
 * sequence, selection (if, switch) and iteration (while). Every function
 * has one entry and one exit. No goto, no flags carried across blocks.
 */
#include <stdio.h>

#define NOTE_BIG   500
#define NOTE_SMALL 200

static int balance = 0;

/*
 * Finds how many 500 and 200 notes add up to amount.
 * Returns 1 and fills *big, *small when possible, else returns 0.
 */
static int split_notes(int amount, int *big, int *small)
{
    int found = 0;
    int fives = amount / NOTE_BIG;

    while (!found && fives >= 0) {
        int rest = amount - fives * NOTE_BIG;
        if (rest % NOTE_SMALL == 0) {
            *big = fives;
            *small = rest / NOTE_SMALL;
            found = 1;
        }
        fives--;
    }
    return found;
}

/* Returns 0 on success, -1 bad amount, -2 insufficient funds, -3 no notes */
static int withdraw(int amount)
{
    int status = 0;
    int big = 0;
    int small = 0;

    if (amount <= 0) {
        status = -1;
    } else if (amount > balance) {
        status = -2;
    } else if (!split_notes(amount, &big, &small)) {
        status = -3;
    } else {
        balance -= amount;
        printf("Paid %d as %d x %d and %d x %d\n",
               amount, big, NOTE_BIG, small, NOTE_SMALL);
    }
    return status;
}

static void deposit(int amount)
{
    if (amount <= 0) {
        printf("Invalid amount\n");
    } else {
        balance += amount;
        printf("Deposited %d\n", amount);
    }
}

static void report_withdraw(int result)
{
    switch (result) {
    case -1:
        printf("Invalid amount\n");
        break;
    case -2:
        printf("Insufficient balance\n");
        break;
    case -3:
        printf("Amount cannot be paid in 500 and 200 notes\n");
        break;
    default:
        break;
    }
}

int main(void)
{
    int running = 1;
    int choice;
    int amount;

    while (running) {
        printf("\n1 Deposit  2 Withdraw  3 Balance  4 Exit\nChoice: ");
        if (scanf("%d", &choice) != 1) {
            running = 0;
        } else {
            switch (choice) {
            case 1:
                printf("Amount: ");
                if (scanf("%d", &amount) != 1) {
                    running = 0;
                } else {
                    deposit(amount);
                }
                break;
            case 2:
                printf("Amount: ");
                if (scanf("%d", &amount) != 1) {
                    running = 0;
                } else {
                    report_withdraw(withdraw(amount));
                }
                break;
            case 3:
                printf("Balance: %d\n", balance);
                break;
            case 4:
                running = 0;
                break;
            default:
                printf("Invalid choice\n");
                break;
            }
        }
    }
    printf("Bye\n");
    return 0;
}

What changed and what did not

The prompts, messages, note-splitting rule and balance arithmetic are unchanged. The program is longer (125 lines against 86) because each job now lives in a named function with a comment, and because the switch has explicit break lines. Every function has exactly one return. There is no goto and no label. The only flags are running and found, and each is tested only in the while condition of the loop it controls.

Sample Run

Both programs were compiled with gcc -Wall (no warnings) and run on the same input sequence: deposit 1500, withdraw 300, withdraw 700, show balance, withdraw 900, deposit -50, choice 5, exit.

$ gcc -Wall -o unstructured unstructured.c
$ gcc -Wall -o structured structured.c
$ printf '1\n1500\n2\n300\n2\n700\n3\n2\n900\n1\n-50\n5\n4\n' > input.txt
$ ./unstructured < input.txt > a.out
$ ./structured < input.txt > b.out
$ diff a.out b.out && echo IDENTICAL
IDENTICAL

Interactive run of either program with the same choices:

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 1
Amount: 1500
Deposited 1500

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 2
Amount: 300
Amount cannot be paid in 500 and 200 notes

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 2
Amount: 700
Paid 700 as 1 x 500 and 1 x 200

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 3
Balance: 800

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 2
Amount: 900
Insufficient balance

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 1
Amount: -50
Invalid amount

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 5
Invalid choice

1 Deposit  2 Withdraw  3 Balance  4 Exit
Choice: 4
Bye

Viva Questions

• Q: Name the three control structures of structured programming. A: Sequence, selection and iteration, each with one entry and one exit.
• Q: Who proved that these three are enough? A: Bohm and Jacopini (1966); Dijkstra’s “Go To Statement Considered Harmful” (1968) argued for applying it.
• Q: Why is a goto out of a nested loop worse than a goto to the next line? A: It gives the loop a second exit, so the code after the loop cannot assume the loop condition became false, and the loop variables have two possible meanings.
• Q: Is break inside a switch a violation? A: Strictly it is a jump, but it is the only way to end a case in C and it always lands at the same join point, so it is accepted.
• Q: How did you remove the early returns from withdraw()? A: An if-else chain assigns a status variable and the function returns it once at the end.
• Q: How did you prove the rewrite is equivalent? A: Same compiler flags, same input file, diff of the two outputs is empty.
• Q: The structured version is 40 lines longer. Is that a cost? A: In line count yes; in reading time no, because each function can be understood alone and the menu loop is visible as a loop.
• Q: What is a flag variable and when is it acceptable? A: A variable whose only job is to steer control flow; it is acceptable when it is the condition of the loop it controls and is set nowhere else.

Common Mistakes

• Choosing code that has no violations and inventing some in the write-up. The manual says: if there are none, pick another portion.
• Listing “uses goto” as one violation. Each label and each jump breaks a specific rule; the table needs one row per construct with a line number.
• Rewriting by deleting the goto and leaving the logic broken. Run both versions on the same input and compare; if the outputs differ, the rewrite is wrong.
• Replacing goto with a flag that is set in five places and tested in one. That moves the spaghetti into data instead of removing it.
• Forgetting to explain why each construct violates sequence, selection or iteration. The table’s third column is the marks.

Session Summary

• The original code (unstructured.c) with line numbers.
• The violations table with line reference, construct, rule broken and rewrite for each row.
• The rewritten code (structured.c).
• The sample run showing identical output from both versions on the same input.