Chapter 24

A Word Counter

The first program reads a text file and prints the words that occur most often in it, with their counts. It is a classic small program because it touches files, strings, a hash table and sorting, and in a language with a garbage collector it is about ten lines long. In C it is several pages, mostly memory management. The Goose version is about sixty lines, and none of them manage memory.

#The program24.1

Given this file, geese.txt:

The goose that lays the golden eggs is not a goose you should cook.
A goose is a goose, said the farmer, and the farmer's wife agreed:
"Don't cook the goose." So the goose stayed, and the eggs kept coming,
and the farmer kept the eggs, and the goose kept the farmer honest.

the program, run as goose words.goose -- geese.txt 6, prints the six most common words:

import std;
import os;
import dictionary;

struct Count { word: const u8[:], n: i64 }
type Counts = dictionary<const u8[:], i64>;

fn is_word_byte(c: u8) -> bool {
    (c >= 'a' && c <= 'z') || c == '\''
}

// Counts the words of text into counts, and returns how many
// there were. A word is a run of letters and apostrophes, and
// text must be lower case.
fn count_words(text: const u8[:], counts: Counts&) -> i64 {
    var total = 0;
    var i = 0;
    while i < text.len {
        while i < text.len && !is_word_byte(text[i]) { i += 1; }
        let start = i;
        while i < text.len && is_word_byte(text[i]) { i += 1; }
        if i > start {
            counts.update(text[start..i], 0) { it += 1; };
            total += 1;
        }
    }
    return total;
}

// The entries of counts, most frequent first, and
// alphabetically on a tie.
fn ranked(counts: Counts&) -> Count[>..] {
    var out: Count[>..] = [];
    counts.each() { w, n => out.push(Count { word: w, n: n }); };
    sort(out) { a, b =>
        a.n > b.n || (a.n == b.n && compare(a.word, b.word) < 0)
    };
    return out;
}

fn main() {
    let a = args();
    guard a.len >= 2 else {
        print("usage: words file [how-many]");
        exit(2);
    }
    var top = 10;
    if a.len >= 3 {
        let n, ok = parse_int(a[2]);
        guard ok && n > 0 else {
            print("not a count: ", a[2]);
            exit(2);
        }
        top = n;
    }
    var text: u8[>..] = [];
    guard read_file(a[1], text) else {
        print("cannot read ", a[1]);
        exit(1);
    }
    to_lower(text);

    var counts = Counts {};
    let total = count_words(text, counts);
    let list = ranked(counts);
    print(total, " words, ", counts.count, " different");
    for c in list[..min(top, list.len)] {
        var line: u8[>..] = [];
        format_int(line, c.n, 10, 5, ' ');
        format(line, "  ", c.word);
        print(line);
    }
}

53 words, 24 different
   11  the
    7  goose
    4  and
    3  a
    3  eggs
    3  farmer

The rest of the chapter goes through the decisions in it.

#One buffer, no copies24.2

The program reads the whole file into one grow-only array, text, and lowers its case in place. After that, no byte of the input is copied again. A word is a slice of text, a dictionary key is a slice of text, and so is the word field of every Count:

· " d o n ' t · c o o k start i text[start..i] is the key: no copy skipped letters and apostrophes make a word; everything else separates words
The scanner keeps two positions. The bytes between them are a word, and the slice is the dictionary key.

This is the shape that Goose favours: one large owner, and many small views into it. The views are cheap (a pointer and a length each), and the compiler knows what each one points into. If you tried to keep list after text was gone, for example by returning it from a function that owned text, the program would not compile.

count_words takes text as const u8[:]. It only reads the text, and the dictionary's key type is const u8[:] too, so the slices it stores are read-only views. Chapter 18 explains why a dictionary keyed by string slices uses the const form.

#Counting with update24.3

counts.update(text[start..i], 0) { it += 1; };

update looks the key up once, inserts 0 if the key is missing, and runs the block on a reference to the value. The obvious alternative, a get followed by an insert when the key is missing, hashes the word twice for every new word. More importantly, the block form is the one that the borrow rules make easy: the reference it cannot outlive the block, so it cannot be held across the next insertion, which might move the table.

#Ranking24.4

ranked copies the entries into a Count[>..] and sorts it with a block comparing two entries. Each Count is a slice and a count, three machine words, so sorting moves small fixed-size values around. The words themselves stay where they are in text.

The function returns an array whose elements refer into text, which it never sees: it only has counts. The compiler treats the result as rooted in its argument, counts, and so in everything that counts may refer into. That is the "inferred roots" rule of Chapter 8, and it is what keeps list from outliving text. It is also conservative, as the next section shows.

sort is unstable, so the comparator breaks ties itself, alphabetically. Without that, the order of a, eggs and farmer above, which all occur three times, would depend on the hash table's layout.

#The output loop24.5

Each line of output is built in a fresh builder, with format_int padding the count to five columns. It is tempting to make one builder before the loop and clear it each time round, as you would in C. The compiler refuses:

    let list = ranked(counts);
    var line: u8[>..] = [];
    for c in list[..min(top, list.len)] {
        line.clear();
        format_int(line, c.n, 10, 5, ' ');
        format(line, "  ", c.word);
        print(line);
    }

error: cannot clear line: the for loop at words.goose:67 iterates list[..min(top, list.len)], whose elements may refer into line (§5.1)

The words in list came out of a dictionary, by way of a function. The compiler knows they are views of byte arrays that belong to main, but no longer which ones, so it assumes they might be views of any of them, line included. Clearing line while the loop could still be reading such a word would leave the word pointing at discarded bytes, so the clear is rejected. In this program no word points into line, but the check errs on the side of safety. The fix costs nothing to speak of: a builder made inside the loop is a stack pointer moved forward, and the end of each iteration moves it back.

#Errors and exit codes24.6

The program handles three failures: no file name, a count that is not a positive number, and a file it cannot read. In each case it prints a message and calls exit with a non-zero code, which ends the program immediately. Since exit never returns, the compiler treats the rest of a guard's else as unreachable, which is what lets the guard stand in front of code that uses text or n.

A library function would not exit. It would return a bool or use return … from, as the calculator in the next chapter does. In main, of a program this small, exiting is the right thing.

#How fast is it?24.7

Built with goose build, on the machine this book was tested on, the program counted a 51 MB file of 8 million words, about 150,000 of them different, in under 0.4 seconds. Nearly all of that is the scanning and the hashing. The allocations, of which there are only a handful in the whole run, do not show up at all.

#Exercises24.8

  1. Make the counter ignore words of one or two letters.

  2. Print, after the table, the number of words that occur exactly once.

  3. Change count_words so that it takes u8[:] instead of const u8[:]. What else has to change?

  4. Make the program read from standard input when it is given no file name, using read_stdin from os.