Writing C on paper

Read like a computer

Goal You can run a short C program by hand, one line at a time, and write down every value it uses.

When you write code on paper, nothing tells you that a line is wrong. Your only check is to run the program yourself, half in your head and half on the page. This is called a dry run: you act as the computer, with a pen, one line at a time.

A computer has no idea what your program is for. It does exactly what each line says, in order, and it remembers only what is stored in variables. A variable is a named place that holds a value. While you trace, do the same. Do what the line says, not what you meant it to say.

The tool is a trace table. A trace table has one column for each variable and one row for each line that runs. Build it in four steps.

1. Number the lines of the program in the margin, starting at 1.
2. Draw the table. The first column is Line. Then one column for each variable. The last column is Note, where you write what happened, for example "test is true", or what the program printed.
3. Run the program. Each time a line runs, add a row. Write the line number, then the value of every variable after that line has finished. Copy unchanged values down from the row above, so that every row can be read on its own.
4. Use two marks for a variable with no value. A dash (–) means the variable does not exist yet. A question mark (?) means it exists but nothing has been stored in it. A correct C program never reads a variable that still holds a question mark.

A loop line runs many times, so it gets many rows. For a for loop, add one row each time the computer reaches the test. Write the values after the update part (such as i++), and write the result of the test in Note. The last row of a loop is the visit where the test is false. The body does not run after it. A variable declared inside the for line, such as i, stops existing when the loop ends, so write a dash for it afterwards.

An if line gets one row. If its test is false, the next row is the first line after the closing brace of the if.

If the program calls a function, draw a second small table for that call, with columns for its parameters and its own variables. Number the calls (f#1, f#2). When the function returns, write the returned value in the Note column of the line that made the call.

#include <stdio.h>

int main(void) {
    int total = 0;
    for (int i = 1; i <= 4; i++) {
        if (i % 2 == 0) {
            total = total + i;
        }
    }
    printf("%d\n", total);
    return 0;
}

6

/* meant: run the body 3 times */
for (int i = 0; i <= 3; i++) {
    printf("*");
}

/* runs the body 3 times */
for (int i = 0; i < 3; i++) {
    printf("*");
}

double half = 7 / 2;

double half = 7 / 2.0;

int i = 3;
int a = i++;

int i = 3;
i++;
int a = i;

a = b;
b = a;

int t = a;
a = b;
b = t;

Draw memory

Goal You can draw the stack, the heap and static data for a C program at any line, with one fixed convention, and say what free changes in the picture.

A program with pointers cannot be understood from the code alone. You need a picture of where each value lives and which pointer points where. On paper, this picture is your trace table for pointers. If you draw it the same way every time, you will make far fewer slips.

C keeps values in three places. Draw them as three columns, each with a heading: Static data, Stack, Heap.

Static data holds what exists for the whole run: string literals such as "hi", and global variables. Text written as a string literal is read-only. Writing to it is an error.

The stack holds one frame for each function that is running right now. A frame is a box that holds that function's parameters and local variables. Draw main's frame first, at the top of the Stack column. Each call adds a new frame below it. When a function returns, cross its frame out. Everything inside it is gone.

The heap holds blocks that you ask for with malloc. A block lives until you call free on it. No function frame owns it.

Now the rules for drawing things.

1. A variable is a small box. Write its type and name beside it and its value inside, such as int n and 3. A variable with no value yet holds ?.
2. A pointer is a box too. Its value is an arrow. The arrow starts inside the box and ends at the thing it points at. Also write the target's label inside the box, so you can still read it when arrows cross.
3. Give every heap block a label: H1, H2, H3, in the order malloc is called. Write the label, the type and the size on top, such as H1 (int[3]). Draw each cell of a block as a box with its index: [0], [1], [2]. Real addresses change from run to run, so a drawing uses labels instead.
4. An assignment copies what is in the box. p = q copies the arrow, not the block. After int *q = p; there are two boxes with arrows and still one block.
5. A string is an array of char cells that ends with a cell holding '\0'. char s[] = "hi" makes a three-cell array inside the frame. char *t = "hi" makes a pointer inside the frame whose arrow ends in read-only text in Static data.

What free does to the drawing. free(p) frees the block that p points at. On the page, draw a large X over the block and write freed. Leave the arrow and the label in p alone, because free does not change p. Every pointer that still holds that label is now a dangling pointer: it points at memory you no longer own. Reading or writing through it is undefined behaviour, which means the language makes no promise about what the program does. Calling free twice on the same block is also undefined behaviour. After free(p), write p = NULL; and draw a slash through the box of p. NULL is a pointer value that points at nothing, and free(NULL) does nothing.

A leak is a block that was never freed and that no arrow reaches any more. At the last line of main, look at each block. If it has no X and no arrow into it, it leaked.

#include <stdio.h>
#include <stdlib.h>

int *make(int n) {
    int *a = malloc(n * sizeof(int));
    if (a == NULL) {
        return NULL;
    }
    for (int i = 0; i < n; i++) {
        a[i] = (i + 1) * 10;
    }
    return a;
}

int main(void) {
    int *p = make(3);
    if (p == NULL) {
        return 1;
    }
    int *q = p;
    q[1] = 99;
    /* A: draw the memory here */
    printf("%d %d %d\n", p[0], p[1], p[2]);
    free(p);
    p = NULL;
    /* B: draw the memory here */
    return 0;
}

10 99 30

int *q = p;

p [H1] ----> H1 (int[3]) | 10 | 20 | 30 |
q [H2] ----> H2 (int[3]) | 10 | 20 | 30 |

int *q = p;

p [H1] ----+
           v
           H1 (int[3]) | 10 | 20 | 30 |
           ^
q [H1] ----+

free(p);

p [NULL]
H1 (int[3]) | 10 | 20 | 30 |

free(p);

p [H1] ----> H1 (int[3]) FREED
             |  X  |  X  |  X  |
p is now dangling; write p = NULL

char *s = "hi";
s[0] = 'H';

char s[] = "hi";
s[0] = 'H';

int *bad(void) {
    int x = 5;
    return &x;
}

int good(void) {
    int x = 5;
    return x;
}

Syntax to memorise

Goal You can write the eight C skeletons below from memory, shortest first, with every semicolon and bracket in place.

Some code cannot be worked out on the spot. You must know its shape without looking. The eight shapes in this lesson are the ones C needs again and again. They are short enough to learn by heart. Learn them in this order, shortest first, and add the next one only when the last is solid.

1. Includes. 2. main. 3. A function. 4. A for loop. 5. A struct with typedef. 6. malloc with a NULL check, and free. 7. String functions. 8. printf specifiers.

How to memorise: cover the page and write the shape on paper. Compare it with the page, character by character. Tick it only when it is right with no peeking. Do it again tomorrow. A shape that you write correctly three days in a row is learned.

The program below contains all eight shapes, each marked with a comment such as (1). Read it once. Then cover it and write each shape on its own, in a few lines of your own paper.

String functions: the destination always comes first, like the left side of an equals sign. strcpy(dest, src) copies src into dest. strcat(dest, src) adds src to the end of dest. strncpy(dest, src, n) and strncat(dest, src, n) take a limit n as the last argument. Be careful: strncpy does not write the '\0' when src is n characters or longer. strcmp(a, b) returns 0 when the strings are equal, a negative number when a comes before b, and a positive number when a comes after b. Because 0 means equal, write strcmp(a, b) == 0. strlen(s) gives the length without the '\0'. The destination must already have room for the text and the '\0'.

printf specifiers: %d an int, %u an unsigned int, %ld a long, %zu a size_t (what strlen returns), %f a double, %.2f a double with two decimal places, %c one char, %s a string, %p a pointer, %x an unsigned int in hexadecimal, %% a percent sign. Each specifier needs one argument of the matching type, in the same order.

/* (1) includes */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* (5) struct with typedef */
typedef struct {
    char name[20];
    int score;
} Player;

/* (3) a function */
int add(int a, int b) {
    return a + b;
}

/* (2) main */
int main(void) {
    /* (4) for */
    int total = 0;
    for (int i = 0; i < 3; i++) {
        total = add(total, i);
    }

    Player p;
    strcpy(p.name, "Mia");
    p.score = total;

    /* (6) malloc, NULL check, free */
    int *a = malloc(3 * sizeof(int));
    if (a == NULL) {
        return 1;
    }
    for (int i = 0; i < 3; i++) {
        a[i] = i * 10;
    }

    /* (7) string functions */
    char word[20];
    strcpy(word, "hello");
    strcat(word, "!");
    if (strcmp(word, "hello!") == 0) {
        /* (8) printf specifiers */
        printf("%s %d %c %.2f %zu\n", p.name, p.score, word[0], 3.14159, strlen(word));
    }

    free(a);
    return 0;
}

Mia 3 h 3.14 6

char buf[10];
strcpy("hi", buf);

char buf[10];
strcpy(buf, "hi");

if (strcmp(a, b)) {
    printf("same\n");
}

if (strcmp(a, b) == 0) {
    printf("same\n");
}

printf("%d %s\n", 3.5, 'a');

printf("%f %c\n", 3.5, 'a');

int *a = malloc(3);

int *a = malloc(3 * sizeof(int));

Common handwriting mistakes

Goal You can read your own C answer a second time, as the compiler would, and catch the slips that would otherwise cost marks.

On a computer, the compiler stops you at the first missing semicolon. On paper, nobody stops you, and every one of these slips costs marks even though it has nothing to do with whether you understand the problem. So you must be your own compiler.

When your answer is finished, read it a second time. This time do not ask whether the logic is right. Ask only whether the form is right. Use this list, and tick each item with your pen.

1. Every statement ends with a semicolon. A struct definition ends with one too, after the closing brace.
2. Every ( [ { has its partner. Count the braces in pairs.
3. Every variable is declared, with a type, before you use it.
4. Every library function has its header.
5. = stores a value. == asks a question. Check every if and while.
6. Strings use double quotes. A single char uses single quotes.
7. Every printf specifier has an argument of the right type.
8. Array indexes run from 0 to n - 1. A string of n characters needs n + 1 cells.
9. A dot reaches a field of a struct. An arrow reaches a field through a pointer.
10. A for or while line has no semicolon after its round brackets.

Below are four pairs that cost the most marks. In each pair the first block is what people write, and the second block is the repair.

typedef struct {
    int x;
    int y;
} Point

for (int i = 0; i < 3; i++);
{
    printf("%d\n", i);
}

typedef struct {
    int x;
    int y;
} Point;

for (int i = 0; i < 3; i++) {
    printf("%d\n", i);
}

if (n = 0) {
    printf("empty\n");
}
char c = "a";

if (n == 0) {
    printf("empty\n");
}
char c = 'a';

Node *p = head;
printf("%d\n", p.value);
int n;
scanf("%d", n);

Node *p = head;
printf("%d\n", p->value);
int n;
scanf("%d", &n);

char s[3] = "abc";
if (s == "abc") {
    printf("same\n");
}

char s[4] = "abc";
if (strcmp(s, "abc") == 0) {
    printf("same\n");
}

Mark yourself

Goal You can mark your own paper answer honestly against a rubric, find where the marks went, plan tomorrow's practice, and write under time.

On paper, a page of writing can look finished and still be wrong. Marking yourself fixes that. You compare your answer with a rubric. A rubric is a list of lines, each worth a number of marks, each describing something that you can see in the answer. Be strict. The mark that counts is the one a stranger would give.

How to read a rubric, line by line.

1. Read one line. Ask: what exactly would I see in a correct answer?
2. Find that thing in your answer and touch it with the tip of your pen. If you can point to it, tick the line and write its marks. If you cannot point to it, the line is worth zero.
3. Do not give half marks for "nearly". Give part of a line only if the rubric says how it splits.
4. Check every path. A line such as "frees the block" is zero if one route through your code, for example an early return, skips the free.
5. Add up the lines. Write the total as marks out of the maximum on the page.

How to find where the marks went. Put each lost mark into one of four boxes. Idea: I did not know how to solve it. Recall: I knew, but could not remember the syntax or the function. Slip: a small mistake in something I did know, such as a missing semicolon or a wrong sign. Time: I ran out of time. Count each box. The biggest box tells you what to work on. Idea: reread the lesson. Recall: more cover-and-write practice. Slip: the compiler pass from the last lesson and a tiny test. Time: practise planning.

What to do the next day. First, rewrite the same answer on a blank page without looking. Second, do a different question of the same kind. Third, mark both again. Repeat after three days and after a week. When the biggest box changes, you are improving.

How to write under time.

1. Plan first. Use the first tenth of the time. Write the function header and three or four comment lines that name the steps. Do not skip this.
2. Leave a blank line between lines of code. You will need room to insert a line you forgot.
3. Name variables clearly: count, not c; head, not h. Clear names stop you from mixing up two variables.
4. Test with a tiny input, by hand. When the code is written, run it on the smallest case: one element, an empty string, n equal to 1. This takes a minute and finds most boundary errors.
5. Spend about one minute per mark. If you are stuck on a part, write a comment saying what you would do, move on, and come back.
6. Leave two minutes for the compiler pass.

On the Practice page, the questions of kind Write code have a Paper mode with a timer, a model answer and a rubric with tick boxes. Use it exactly like this lesson: write on paper, then mark.

#include <stdio.h>

/* A student's answer. It has one bug. */
int smallest(const int *a, int n) {
    int best = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < best) {
            best = a[i];
        }
    }
    return best;
}

int main(void) {
    int test[] = {5, 3, 8};
    printf("%d (expected 3)\n", smallest(test, 3));
    return 0;
}

0 (expected 3)

for (int i = 1; i < n - 1; i++) {
    if (a[i] < best) {
        best = a[i];
    }
}

for (int i = 1; i < n; i++) {
    if (a[i] < best) {
        best = a[i];
    }
}

int sum;
for (int i = 0; i < n; i++) {
    sum = sum + a[i];
}

int sum = 0;
for (int i = 0; i < n; i++) {
    sum = sum + a[i];
}

int total(const int *a, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = sum + a[i];
    }
    printf("%d\n", sum);
}

int total(const int *a, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = sum + a[i];
    }
    return sum;
}