26. count, twice
Everything in this book so far has been a chapter teaching a feature. This part is programs, and it teaches nothing new. Every construct in it has already appeared; what has not appeared is a whole program with a name, a binary, and somebody’s actual work to do.
Three of these builds stand beside the C programs they descend from. You read the same tool twice — once in the manner Kernighan and Ritchie wrote it, once in wolf — and the rule for those two columns is stated here, once, and then obeyed without further announcement:
Where wolf is shorter or safer, we show it and measure it. Where wolf is
longer, clumsier, or gives something up, we say so on the page, in the
same voice. Line counts come from wc, and when a claim is about lines
the numbers are printed. A side-by-side that only ever flatters one column
is an advertisement, and this part would rather be useful.
The C in these chapters is ours. The programs are folklore — a word
counter, a calculator, a word-frequency tree have each been written ten
thousand times — but the listings in The C Programming Language belong
to their authors, so nothing here is copied from that book. Each twin is
an original implementation written in the manner of a named section, it
compiles under cc -std=c99 -Wall -Werror, and it runs against declared
cases in CI, exactly as the wolf half does. A contrast you cannot run is a
rumour about another language.
26.1 The tool, twice
count reports three numbers per file — lines, words, bytes — and a total
when there is more than one file. It is wc, and it is the right first
project for one reason: the interesting part is four lines long, so
neither column can hide behind its scaffolding.
The four lines are a state machine. Walking through text, you are either inside a word or between words, and a word count is the number of times you cross from between to inside. K&R §1.5–1.6 uses that machine to introduce the idea that a program can carry state in a variable; we use it to compare two languages, which is a heavier load, so it helps that the machine itself is beyond argument.
Here is what both columns produce, from the same two files. one.txt
holds two lines — the wolf runs and the moon watches — and two.txt
holds alone:
2 6 31 one.txt
1 1 6 two.txt
3 7 37 total
Identical output is the point of the exercise. Every difference between the two programs is therefore a difference in how, never in what, and the comparison has nowhere to hide.
26.2 Ritchie’s state machine
The C twin, whole, in four pieces. First the header and the two names the machine is made of:
/* count --- lines, words, and bytes, per file and in total.
*
* An ORIGINAL implementation, written after the manner of Kernighan and
* Ritchie, "The C Programming Language", 2nd ed., sections 1.5-1.6. The
* character loop and the IN/OUT word-state machine are their teaching
* shape; the code below is ours, and no listing from that book is
* reproduced here. See PERMISSIONS.md.
*
* Two conventions in here are the side-by-side's whole subject:
* - the state machine is spelled as two #defines and an int;
* - failure is a sentinel int, and the caller has to remember to look.
*/
#include <stdio.h>
#define IN 1 /* inside a word */
#define OUT 0 /* between words */
Two #defines and an int. That is the state machine: state holds IN
or OUT, and the type system has no opinion about which values are
allowed in it, because in 1978 there was no cheap way to give it one.
Next, the numbers, and then the machine itself:
/* Three numbers, so a struct: chapter 1 would have used three globals,
* but a per-file row and a running total need two of them at once. */
struct tally {
long lines;
long words;
long bytes;
};
/* Count one open stream into *t.
*
* Returns 0, or -1 if the stream errored. This is the sentinel-int
* convention: the value -1 carries no detail, it shares a type with
* every legitimate answer, and nothing in the signature obliges the
* caller to test it. */
static int count(FILE *fp, struct tally *t)
{
int c, state;
state = OUT;
t->lines = 0;
t->words = 0;
t->bytes = 0;
while ((c = getc(fp)) != EOF) {
++t->bytes;
if (c == '\n')
++t->lines;
if (c == ' ' || c == '\n' || c == '\t')
state = OUT;
else if (state == OUT) {
state = IN;
++t->words;
}
}
return ferror(fp) ? -1 : 0;
}
Read the comment above count and then read its signature. The function
answers two questions — what are the three numbers, and did the read
succeed — and it answers them through two different channels: the
numbers go out through a pointer, and the verdict comes back as an int
that is 0 or -1. Nothing in int count(FILE *, struct tally *)
obliges a caller to look at the return value. Nothing warns a caller who
does not. -1 shares its type with every legitimate answer, and the
compiler is satisfied either way. That is the sentinel-int convention,
and it is the second of the two conventions this twin is built from.
The rest is presentation, arithmetic, and main — the argument handling,
the opening, the error reporting, the totalling:
static void row(const struct tally *t, const char *name)
{
printf("%8ld%8ld%8ld %s\n", t->lines, t->words, t->bytes, name);
}
static void add(struct tally *total, const struct tally *t)
{
total->lines += t->lines;
total->words += t->words;
total->bytes += t->bytes;
}
int main(int argc, char *argv[])
{
struct tally t, total;
FILE *fp;
int i, files, failed;
total.lines = 0;
total.words = 0;
total.bytes = 0;
failed = 0;
files = 0;
if (argc == 1) { /* no names: the stream is stdin */
if (count(stdin, &t) < 0) {
fprintf(stderr, "count: error reading standard input\n");
return 1;
}
row(&t, "-");
return 0;
}
for (i = 1; i < argc; ++i) {
if ((fp = fopen(argv[i], "r")) == NULL) {
fprintf(stderr, "count: cannot open %s\n", argv[i]);
failed = 1;
continue;
}
if (count(fp, &t) < 0) {
fprintf(stderr, "count: error reading %s\n", argv[i]);
failed = 1;
} else {
row(&t, argv[i]);
add(&total, &t);
++files;
}
fclose(fp);
}
if (files > 1)
row(&total, "total");
return failed;
}
Compiled and run on the two files, it prints what §26.1 promised:
$ ./count one.txt two.txt
2 6 31 one.txt
1 1 6 two.txt
3 7 37 total
Give it a name that will not open, and the sentinel reaches the exit status — the convention working exactly as designed:
$ ./count nope.txt
count: cannot open nope.txt
$ echo $?
1
Two conventions, then, and we hold both of them up against wolf: the state machine spelled as untyped integers, and failure spelled as a value that is indistinguishable from success.
26.3 The same machine as a match
The wolf column starts with the machine and nothing else:
struct Tally { lines: int, words: int, bytes: int }
fn tally(text: str) -> Tally {
var t = Tally { lines: 0, words: 0, bytes: 0 }
var inword = false
for b in text.bytes() {
t.bytes += 1
if b == 10 { t.lines += 1 }
match b {
32 | 9 | 10 => { inword = false },
_ => {
if !inword {
inword = true
t.words += 1
}
},
}
}
t
}
The state is inword, a bool, and the transition is a match over the
byte. 32 | 9 | 10 is one arm with three patterns — space, tab, newline
— and _ is every other byte, which is to say every byte that is part of
a word. Set that arm beside the C’s else if (state == OUT): the two
programs do the same work, and the difference is that inword cannot
hold 2.
Wire it to some text and print a row:
fn row(t: Tally, name: str) {
print("{t.lines:>8}{t.words:>8}{t.bytes:>8} {name}")
}
fn main() -> !int {
row(tally("the wolf runs\nthe moon watches\n"), "one.txt")
0
}
{t.lines:>8} is chapter 2’s format spec doing the job C’s %8ld does,
and the two produce the same eight columns:
$ wolf build tally.lu && ./tally
2 6 31 one.txt
The first measurement
Now the comparison, and the first honest answer of the part. The C’s
count function runs from its comment to its closing brace in 21 lines.
The wolf tally function runs 19.
That is a wash, and it is a wash for a reason worth sitting with: it is
the same machine. Wolf did not shorten the loop, because the loop was
never long — K&R’s chapter-1 counter is one of the tightest pieces of
teaching code anyone has written, and a language claiming to improve on it
by fourteen lines would be lying about something. What wolf changed is one
type: int state became bool inword, and a family of mistakes stopped
being expressible. That is the whole trade on this page, and it buys no
lines.
The lines come later, and they come from the parts of the C that are not the machine.
26.4 Per file, and a total
Reading a file is one call, and it is a call that can fail:
fn main() -> !int {
fs_write_text("one.txt", "the wolf runs\n")?
let text = fs_read_text("one.txt") else |_| { return 1 }
print("{text.trim()}")
0
}
$ wolf build read.lu && ./read
the wolf runs
fs_read_text hands back a str or one of four failure tags, and its
signature says which four. Write a wrapper whose row is narrower than the
truth, and the compiler does the arithmetic:
struct Tally { lines: int, words: int, bytes: int }
fn count_file(name: str) -> Tally ! {not_found} {
let text = fs_read_text(name)?
Tally { lines: 0, words: 0, bytes: text.len }
}
fn main() -> !int {
let t = count_file("one.txt") else |_| { return 1 }
print("{t.bytes}")
0
}
error[E0602]: this can also fail with `denied`, `io`, `utf8`, which `count_file`'s row does not include
--> ./s2.lu:7:16
|
6 | fn count_file(name: str) -> Tally ! {not_found} {
| ---------------------- the receiving row is declared here
7 | let text = fs_read_text(name)?
| ^^^^^^^^^^^^^^^^^^^ the missing tags escape here
|
= note: rows compose by union: `?` re-tags errors into the wider row by injection — there is no
conversion to write, only tags to admit.
help: extend the row with `denied`, `io`, `utf8`
|
6 | fn count_file(name: str) -> Tally ! {not_found, denied, io, utf8} {
|
Set that against the C, where count returning -1 and main
forgetting to test it is a program that compiles, links, ships, and
prints wrong numbers. A row is not documentation about what can go wrong.
It is the thing the compiler checks.
Take the advice in its shortest form. -> !Tally means “or whatever this
body can fail with, composed for me”, and the wrapper becomes two lines:
struct Tally { lines: int, words: int, bytes: int }
fn count_file(name: str) -> !Tally {
let text = fs_read_text(name)?
Tally { lines: 0, words: 0, bytes: text.len }
}
fn main() -> !int {
fs_write_text("one.txt", "the wolf runs\n")?
let t = count_file("one.txt")?
print("{t.bytes}")
0
}
$ wolf build wide.lu && ./wide
14
Now the whole program: the machine from §26.3, that wrapper with the real
tally in it, row, and a loop over the names.
struct Tally { lines: int, words: int, bytes: int }
fn tally(text: str) -> Tally {
var t = Tally { lines: 0, words: 0, bytes: 0 }
var inword = false
for b in text.bytes() {
t.bytes += 1
if b == 10 { t.lines += 1 }
match b {
32 | 9 | 10 => { inword = false },
_ => {
if !inword {
inword = true
t.words += 1
}
},
}
}
t
}
fn count_file(name: str) -> !Tally {
tally(fs_read_text(name)?)
}
fn row(t: Tally, name: str) {
print("{t.lines:>8}{t.words:>8}{t.bytes:>8} {name}")
}
fn main() -> !int {
fs_write_text("one.txt", "the wolf runs\nthe moon watches\n")?
fs_write_text("two.txt", "alone\n")?
var names = List[str]()
(mut names).push("one.txt")
(mut names).push("two.txt")
var total = Tally { lines: 0, words: 0, bytes: 0 }
var files = 0
var failed = 0
var i = 0
while i < names.len {
let name = names[i]
i += 1
let t = count_file(name) else |_| {
eprint("count: cannot open {name}")
failed = 1
continue
}
row(t, name)
total.lines += t.lines
total.words += t.words
total.bytes += t.bytes
files += 1
}
if files > 1 { row(total, "total") }
failed
}
Four things in that loop are worth naming.
else |_| { … continue } is the C’s continue after a failed fopen,
and it sits in the one place a reader looks for it: attached to the call
that failed. There is no flag to set and no second place to check it.
eprint puts the complaint on standard error and print puts the rows on
standard output, which is what the C does and what a tool that gets piped
into another tool has to do.
failed is main’s last expression, so a name that will not open leaves
the exit status at 1 — the same contract the C’s return failed gives,
reached without a sentinel, because a process’s exit status genuinely is
an integer and always was.
And the two fs_write_text calls at the top write the two files the
program counts. Both columns count the same bytes or the comparison is a
story instead of a measurement, so the wolf column carries its own copy of
them; the C’s come from the case file that asserts its runs. Those two
lines are the price of a self-contained program, and §26.5 charges us for
them.
Build it and run it:
$ wolf build count.lu && ./count
2 6 31 one.txt
1 1 6 two.txt
3 7 37 total
Three rows, eight-column fields, byte-for-byte what the C printed in §26.2. The two columns are the same tool.
26.5 Where wolf is not shorter
The measurement, on the whole programs:
$ wc -l samples/contrast/count.c samples/projects/count/count.lu
106 samples/contrast/count.c
57 samples/projects/count/count.lu
Blank lines and comment-only lines removed — because the C carries a twelve-line attribution header the wolf file has no reason to have — that is 76 lines of C against 52 lines of wolf. A third off, which is a real number and a smaller one than the folklore about safe languages predicts.
Where those 24 lines went is the honest part, and half the answers have nothing to do with safety.
The arithmetic helper the C needs, wolf does not. add in the C twin
is six lines that add three fields to three fields. The wolf version
writes three += at the call site, because there is nothing to be careful
about. Six lines against three, and it is the kind of saving that adds up
to very little.
The C’s main is 38 lines of code; wolf’s is 27. That eleven-line gap
is almost entirely the two-channel return convention: the C has to declare
struct tally t, pass its address, test the result, and keep a failed
flag that the error path sets and the success path must not disturb. The
wolf loop gets a Tally or a handler, and there is nowhere for a third
state to live.
Now the other direction, which is where this part earns its opening rule.
Ritchie’s program takes its file names from the command line. Ours holds
them in a list. That is four lines of push against one for (i = 1; i < argc; ++i), and this listing loses the exchange. Wolf has a command
line — env_args() hands it back as a List[str], and chapter 30’s
program is built on it — so those four lines are a choice this chapter
made and not a limit it ran into. The choice buys one thing: a binary you
can build and run before you have written a file for it to count, which is
worth having in the part’s first project and worth nothing afterward. The
C’s one line still does more than four of ours, because it takes any
number of names, from a shell, with globbing, in a pipeline. When you
build this tool for yourself rather than for a chapter, take the names
from env_args() and delete the two fs_write_text calls with them.
Ritchie’s program counts a file of any size. Ours reads the file into
memory first. getc in a loop touches one byte at a time and needs no
more room than the three counters; fs_read_text hands back the whole
file as a str. On the files in this chapter that difference is 37 bytes
and does not matter. On a forty-gigabyte log it is the difference between
a program and a crash. Wolf spells the other shape too — fs_open,
fs_read with a byte budget, fs_close — and this program does not use
it, because the whole-file read is one call and the chapter is about the
state machine. When you count something enormous, remember which column
you copied.
So: shorter by a third, with a state machine that cannot hold 2 and a
failure that cannot be ignored, against two costs — the input surface and
the memory profile — that anybody shipping this tool would have to pay
attention to. That is the shape of every comparison in this part. The next
two are more lopsided in wolf’s favour, and neither of them is lopsided
because wolf is a better language than C. They are lopsided because C’s
chapter 4 and chapter 6 spend their pages on stacks and on malloc, and
wolf spends those pages on nothing at all.
Exercise 26-1 (fingers · wolf) — Build count as printed and run
it. Then put a tab in the middle of one.txt’s first line and predict all
three numbers before running it again.
Exercise 26-2 (comprehension · lupin) — tally counts a word every
time it crosses from between to inside. Predict lines, words, and
bytes for the text "a b\n\nc" — two spaces, a blank line, no
trailing newline — and name which of the three people get wrong:
struct Tally { lines: int, words: int, bytes: int }
fn tally(text: str) -> Tally {
var t = Tally { lines: 0, words: 0, bytes: 0 }
var inword = false
for b in text.bytes() {
t.bytes += 1
if b == 10 { t.lines += 1 }
match b {
32 | 9 | 10 => { inword = false },
_ => {
if !inword {
inword = true
t.words += 1
}
},
}
}
t
}
fn main() -> !int {
let t = tally("a b\n\nc")
print("{t.lines:>8}{t.words:>8}{t.bytes:>8} -")
0
}
Exercise 26-3 (extension · wolf) — Give count a bytes-only mode: a
second row function that prints the byte column alone, and a bool at the
top of main that chooses between them. Then say what the same option
costs in the C twin, and count the lines.
Exercise 26-4 (comprehension · wolf) — Narrow count_file’s row to
Tally ! {not_found, denied} and predict the diagnostic’s code and the
tags it names, before running it. Then write the full row out by hand and
check that it and -> !Tally accept the same program.
Exercise 26-5 (spelunking · wolf) — Add a third name that does not
exist, run the program, and read the exit status. Then read the E0602
note above in full and explain, in two sentences, why the C’s -1 needs a
convention and a row does not.
Exercise 26-6 (design) — count reads each file whole. Sketch the
version that does not: fs_open, a loop of fs_read over fixed-size
chunks, and a state machine that survives across chunk boundaries. Name
the one thing that gets harder, and say whether you would pay one call to
avoid it.