Class 8 — Thursday, September 17

Arrays: a hundred numbers under one name, and what C does when you ask for the hundred-and-first.

1 Two dates, before anything else

A4 goes out today and is due Wednesday, September 23.

Midterm Part 1 is Tuesday, September 29, the whole period. It is programming, on these machines, open book. The page says what is on it — read it this weekend, not on the 28th.

2 Predict-then-run

Before anything is on the screen, and without notes. In your Brightspace Journal:

(a) In Java or Python, you have an array or a list with 5 things in it, and you ask for item number 5. What happens? Number 6?

(b) The same thing in C. What do you think happens?

Two minutes. A guess counts, and “I don’t know, but I’d bet on …” counts.

Then this goes on the screen, and we run it together:

#include <stdio.h>

int main() {
    int a[5] = {10, 20, 30, 40, 50};
    printf("a[4] is %d\n", a[4]);
    printf("a[5] is %d\n", a[5]);
    printf("a[6] is %d\n", a[6]);
    printf("a[7] is %d\n", a[7]);
}

We compile it with gcc -Wall, look at what the compiler says about it, run it, and then run it again several times without recompiling.

3 The name for it: UNDEFINED BEHAVIOR (a.k.a. UB)

It means the language specification declines to say what happens and the implementation (the compiler) can decide arbitrarily; the answer can also depend on the machine and on whatever happened to be in memory. This is a bad place to be in with real code.

The Java specification does answer the question — it throws ArrayIndexOutOfBoundsException, every time, on every machine. Similarly with Python.

Important consequence:

“It worked when I ran it” is not evidence that a program is correct.

You have just watched one binary, on one machine, with nothing recompiled in between, print a different answer on two runs.

This does not stop at arrays in C: pretty much every topic in this course provides “opportunities” to get into UB.

4 The three facts about a C array

Here’s an array declaration:

#define SIZE 10   // capitalised, because it is a constant

int scores[SIZE];
  1. The size is fixed when you declare it, and it never changes.
  2. The positions are 0 to 9. There is no position 10.
  3. The array does not know how long it is. No scores.length, no len(scores). If code needs the length, a variable has to carry it.

The loop over one is always this shape, and the < is doing real work:

for (int i = 0; i < SIZE; i++) {
    printf("%d\n", scores[i]);
}

5 The ladder

Note: If you have been stuck for three minutes, put your hand up.

Pairs, one keyboard between two people. The person not typing reads this page out loud and says what to type next, and you swap who types at every rung.

Work in a new directory. Call it whatever you like.

5.1 Rung 1 — ten numbers in, two answers out

A file called stats.c. It declares int values[10], reads ten numbers into it, then prints the sum and the largest.

Reading into a position looks like this — note the &, which is there for the same reason it has always been there with %d:

scanf("%d", &values[i]);

Typing ten numbers every time you test gets old fast. Put them in a file instead, one per line, and feed it in:

./stats < input.txt

Done when ./stats < input.txt prints a sum and a largest that you have checked by hand.

5.2 Rung 2 — the average, which is not what you first write

Add the average. Write it the obvious way first:

printf("average: %d\n", sum / 10);

Run it on ten numbers whose true average is not a whole number. Look at what it printed.

Then fix it. %f instead of %d, and the division has to produce a real number rather than throwing the fraction away — (double) sum / 10 is one way to say that.

Done when the average has a decimal point in it and the number is right.

5.3 Rung 3 — a function that reaches back into main

Two functions, above main:

void print_all(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void double_all(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = arr[i] * 2;
    }
}

Then, in main, after everything else:

print_all(values, 10);
double_all(values, 10);
print_all(values, 10);

Done when the second line of output is the first one doubled — and you have noticed that this is not what swap did in A3.

Food for thought: is it how arrays in Java/Python work when passed to functions?

5.4 Rung 4 — a word, and where it stops

A new file, word.c. It reads one word and prints its length twice: once with strlen, and once with a loop you write.

#include <stdio.h>
#include <string.h>

#define SIZE 100

int main() {
    char word[SIZE + 1];  // note +1
    printf("word: ");
    scanf("%100s", word); // we have to re-type the size here again, sadly

    int len = 0;
    while (word[len] != '\0') {
        len++;
    }

    printf("strlen says %d, my loop says %d\n", (int) strlen(word), len);
}

Type it in rather than pasting it, and look at two things while you do.

There is no & in front of word. Every scanf before today had one.

The loop stops at '\0', a single character whose value is zero. It is on the end of every string in C, it is why "hello" takes six bytes rather than five, and it is the only way strlen could possibly know where to stop — nobody told it a length.

Done when the two numbers agree for hi, for hello, and for a word you type with twenty letters in it.

6 If you have already finished

6.1 Uppercase it, in place

Write void shout(char s[]), which turns every lowercase letter of s into its uppercase version by changing the array itself. It takes no length — '\0' is the length.

if (s[i] >= 'a' && s[i] <= 'z') {
    s[i] = s[i] - 'a' + 'A';
}

That line only works because a char is a number. Print 'a' and 'A' with %d instead of %c and look at the two values.

6.2 Go hunting for the other array

Put a second array right next to the first one, and print something from it so the compiler does not warn that it is unused:

int a[5] = {10, 20, 30, 40, 50};
int b[5] = {77, 77, 77, 77, 77};
printf("b[0] is %d\n", b[0]);

Now go looking for b through a. Print a[i] for i running from -8 up to 10, with the index beside each value, and find the 77s.

Do not assume they are above a. They may be below it, at negative indices, and which side they land on is not something the language promises — it is whatever your compiler happened to do with the stack today.

6.3 Ask the compiler again, twice

Plain gcc -Wall said nothing about any of this. Try these two:

gcc -Wall -O2 offend.c -o offend

-O2 turns on the optimiser. Read what it now says about a[5]. It knew the whole time. It just does not go looking unless it is already analysing your program for other reasons — which is a strange and slightly upsetting thing to learn about your compiler.

gcc -Wall -fsanitize=address offend.c -o offend

Then run it. This one checks at run time, and instead of a number you get a diagnosis with a name for what you did — it turns undefined behavior back into an error message, which is the thing C gave up in exchange for speed. Programs built this way run several times slower, which is why it is not the default — but it is the tool you reach for when a C program is misbehaving and you cannot see why.

7 Then the book’s exercises for this week’s reading

This runs in the browser and marks itself. Nothing is collected.

8 Before you leave

A4 is out. Read the box near the top that says what to get to first if the week runs out on you — it names three steps and gives the reason for each, and it is a better plan than whatever you would pick at eleven at night.

The directory you have been working in is worth keeping. Copy it somewhere you can get at from another seat — these machines keep your files, but they keep them on this machine, and next Tuesday you may not be in this chair.