Structured programming language

01From jumps to blocks

The first programs were written with jumps: “if such-and-such happens, go to line 340.” They worked, but beyond a certain size nobody could follow the thread, because any line could be reached from any other. In 1968 Edsger Dijkstra published a letter with a title that became famous, Go To Statement Considered Harmful: the unrestricted jump makes it impossible to reason about a program.

Structured programming is the answer: write everything with the three structures of Böhm and Jacopini, each with a single entry and a single exit, and split the problem into functions that can be understood, tested and reused separately. The program reads from top to bottom and each block can be replaced by a black box.

02From source to executable, hands-on

The gcc compiler lets you stop at each stage. It is worth doing once to lose the fear of error messages, which tell you at which stage they failed:

gcc -E hello.c -o hello.i     # preprocess only: see what is left of the #include lines
gcc -S hello.c -o hello.s     # compile to assembly
gcc -c hello.c -o hello.o     # assemble: object code
gcc hello.o -o hello          # link with the standard library
gcc -Wall -Wextra -std=c11 hello.c -o hello   # all in one, with warnings

03Types and expressions: what C does without warning

In C every expression has a type, and the type decides the operation. 7 / 2 is an integer division and gives 3, because both operands are integers; 7.0 / 2 gives 3.5. The result does not depend on where it is stored: double x = 7 / 2; stores 3.0, because the division was done first.

When types are mixed, C applies the usual arithmetic conversions: types smaller than int are promoted to int, and in an operation between two different types the “smaller” one is converted to the “larger” one. The best-known trap:

int a = -1;
unsigned int b = 1;
if (a < b)                      // false!
    printf("logical");

When an int is compared with an unsigned int, −1 is converted to unsigned and becomes 4,294,967,295 (with 32 bits), which is greater than 1. The bits did not change: the reading changed, exactly as in number systems.

There is a surprise in the table: & has lower precedence than ==. That is why if (x & 0x08 == 0) does not do what it seems to; write if ((x & 0x08) == 0). When in doubt, use parentheses.

04Control structures in C

In C any nonzero value is true. break exits the loop or the switch and continue jumps to the next iteration: they break the single-exit rule, but in a controlled way, and they are accepted when they simplify things. goto exists; in structured code it is only tolerated for leaving several nested levels when an error occurs.

05Functions and parameter passing

A function is an algorithm with a name, inputs (parameters) and an output (return value). In C all parameters are passed by value: the function receives a copy and cannot modify the original variable. To let it do so, you pass the variable’s address, a pointer:

void swap(int *p, int *q)
{
    int aux = *p;       // what is at address p
    *p = *q;
    *q = aux;
}
...
swap(&x, &y);    // the addresses of x and y are passed

For the same reason scanf("%d", &n) takes &: it needs to know where to write. Pointers are covered in complex data containers.

06The call stack: where local variables live

How can a function have “its own” n if it calls itself? Each call creates in memory a frame (also called a stack frame) with its parameters, its local variables and the address to which it must return. Frames are stacked: the last one in is the first one out. On return, the frame is discarded and its variables cease to exist. Follow the execution of a recursive factorial:

07Programs in several files

A structured program grows split into modules: a .c file with the code and a .h file with what the rest of the program needs to know about it, namely the prototypes, types and constants.

/* resistors.h — the interface: what the module offers */
#ifndef RESISTORS_H        // guard against double inclusion
#define RESISTORS_H
double parallel(const double r[], int n);
double series(const double r[], int n);
#endif

/* resistors.c — the implementation: how it does it */
#include "resistors.h"
static int has_short(const double r[], int n);   // private to the module
...

It is compiled with gcc main.c resistors.c -o calc. Separating interface from implementation allows changing the how without touching whoever uses the module: it is the same idea as layered abstraction, at the scale of a program.

08Standard input and output

scanf returns how many items it managed to read. A robust program checks it: if (scanf("%lf", &r) != 1) means that the user typed something that is not a number.

09In the lab

10Common mistakes

• = instead of == inside an if.
• A semicolon after the for: for (i = 0; i < n; i++); runs an empty loop.
• Forgetting the & in scanf: the program writes to an arbitrary address.
• Unintended integer division: 1/2 * x is always 0.
• Uninitialized local variables: they are not zero; they hold whatever was on the stack.
• Using %d for a double or %f for an int: it prints garbage without warning.

11Self-assessment

12Further reading

• Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language. 2nd ed. (Spanish edition, “El lenguaje de programación C”), Prentice Hall Hispanoamericana, 1991. By the creators of the language. Brief, dense and with exercises that teach you to think in C.
• Harvey M. Deitel and Paul J. Deitel. Cómo programar en C/C++ y Java. 4th ed., Pearson Educación, 2004 (in Spanish). Step by step, with a great many complete examples and good practices.
• Luis Joyanes Aguilar and Ignacio Zahonero Martínez. Programación en C. Metodología, algoritmos y estructura de datos. 2nd ed., McGraw-Hill, 2005 (in Spanish). Connects the pseudocode of the previous topic with the language, in Spanish.
• K. N. King. C Programming: A Modern Approach. 2nd ed., W. W. Norton, 2008. The best modern C textbook: rigorous about the standard and very clear.
• Edsger W. Dijkstra. Go To Statement Considered Harmful. Communications of the ACM, 11(3), 1968. A page and a half that changed the way people program.