27. rpn, twice
Chapter 26’s comparison was close, because both columns were writing the same four-line machine. This one is not close, and the reason is structural: K&R §4.3 has to build a stack before it can build a calculator, and it has to build a way to report failure before it can build either.
rpn reads expressions in reverse Polish notation — operands first,
operator last, no parentheses and no precedence — and prints each answer.
2 3 + is 5. 5 1 2 + 4 * + 3 - is 14. It is the smallest program that
needs a stack, which is why Ritchie’s chapter 4 uses it, and it is the
smallest program with an interesting error surface, which is why we do.
27.1 A stack and a switch
Here is the twin’s machinery: the stack, and the flag that is this section’s whole subject.
/* rpn --- a reverse-Polish calculator.
*
* An ORIGINAL implementation, written after the manner of Kernighan and
* Ritchie, "The C Programming Language", 2nd ed., section 4.3. The
* getop/push/pop division of labor and the getch/ungetch pushback pair
* are their teaching shape; the code below is ours, and no listing from
* that book is reproduced here. See PERMISSIONS.md.
*
* The side-by-side's subject is the error path. `pop` has to return a
* double, and every double is a legitimate answer, so an empty stack
* returns 0.0 and sets a flag the caller is trusted to consult. The
* flag is the whole safety mechanism, and nothing enforces it.
*/
#include <stdio.h>
#include <stdlib.h> /* atof */
#include <ctype.h>
#define MAXOP 100 /* biggest operand or operator */
#define NUMBER '0' /* signal that a number was found */
#define MAXVAL 100 /* maximum depth of the value stack */
#define BUFSIZE 100 /* depth of the character pushback */
static int getop(char s[]);
static void push(double f);
static double pop(void);
static int getch(void);
static void ungetch(int c);
static int sp = 0; /* next free stack position */
static double val[MAXVAL]; /* the value stack */
/* The error flag. Set by push on overflow, by pop on underflow, by
* ungetch on pushback overflow, and by main on division by zero.
* Consulted by hand, at end of expression, because nothing else will. */
static int broken = 0;
static void push(double f)
{
if (sp < MAXVAL)
val[sp++] = f;
else {
fprintf(stderr, "rpn: stack full, cannot push %g\n", f);
broken = 1;
}
}
/* Returns 0.0 on underflow --- indistinguishable from a pushed zero. */
static double pop(void)
{
if (sp > 0)
return val[--sp];
fprintf(stderr, "rpn: stack empty\n");
broken = 1;
return 0.0;
}
static int buf[BUFSIZE]; /* characters read ahead of the parser */
static int bufp = 0; /* next free slot in buf */
static int getch(void)
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
static void ungetch(int c)
{
if (bufp >= BUFSIZE) {
fprintf(stderr, "rpn: pushback buffer full\n");
broken = 1;
} else
buf[bufp++] = c;
}
Find the value that means two things. pop has to return a double,
every double is a legitimate answer, and an empty stack has no double
to give — so it returns 0.0 and sets broken. Push a literal zero and
pop it back and you get 0.0 with broken clear; pop an empty stack and
you get 0.0 with broken set. The value is the same value. The
difference between “the answer is zero” and “there was no answer” lives
in a separate global that the caller is trusted to consult, and main
consults it once, at the end of the line, because that is the only place
consulting it is cheap.
The C twin’s own comment says it plainly: “the flag is the whole safety mechanism, and nothing enforces it.” That is not a criticism of Ritchie. In 1978 there was no second thing to return.
The tokenizer and the dispatch:
/* Read the next operator or numeric operand. */
static int getop(char s[])
{
int i, c;
while ((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
if (!isdigit(c) && c != '.' && c != '-')
return c; /* not a number */
i = 0;
if (c == '-') { /* a sign, or the operator */
c = getch();
if (!isdigit(c) && c != '.') {
ungetch(c);
return '-';
}
s[++i] = (char) c;
}
if (isdigit(c))
while (isdigit(s[++i] = c = getch()))
;
if (c == '.') /* collect a fractional part */
while (isdigit(s[++i] = c = getch()))
;
s[i] = '\0';
if (c != EOF)
ungetch(c);
return NUMBER;
}
int main(void)
{
int type;
double op2;
char s[MAXOP];
while ((type = getop(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 == 0.0) {
fprintf(stderr, "rpn: division by zero\n");
broken = 1;
break;
}
push(pop() / op2);
break;
case '\n': /* end of an expression */
if (broken || sp < 1) {
printf("error\n");
} else {
printf("%.4g\n", pop());
}
sp = 0;
broken = 0;
break;
default:
fprintf(stderr, "rpn: unknown command %s\n", s);
broken = 1;
break;
}
}
return 0;
}
getop is 28 lines of code, and every one of them is about the fact that
C’s input is a stream of characters with no lookahead: to know whether -
is a sign or an operator you have to read the next character, and to
un-read it you have to have built ungetch, which needs buf, bufp,
and a second overflow path into broken. Hold that number — 28 — for
§27.3.
Run it, and watch two different problems arrive as the same word:
$ ./rpn
5
14
$ ./rpn
error
error
rpn: division by zero
rpn: stack empty
rpn: stack empty
Two lines of input, four diagnostics, and on standard output the word
error twice with nothing to distinguish the division by zero from the
empty stack. And rpn: stack empty appears twice for one empty line,
because + pops twice.
27.2 The operand stack as a List
The wolf column has no §27.2 machinery, and that is the section:
fn main() -> !int {
var stack = List[int]()
(mut stack).push(2)
(mut stack).push(3)
let b = (mut stack).pop() else { return 1 }
let a = (mut stack).pop() else { return 1 }
print("{a + b} {stack.len}")
0
}
$ lupin stack.lu
5 0
MAXVAL, sp, val[], the bounds test in push, the “stack full”
message: none of it is written, because List grew a buffer in chapter 5
and indexing has been checked since chapter 5 as well. That is 20 lines of
the C twin gone, and one line of wolf replaced them.
One thing did change shape. pop on a List returns int ! {none} —
the value, or the tag that says there was nothing there — so the compiler
will not let the two cases be one value. else { return 1 } above is
handling the empty case; it is not decoration, and there is no spelling
that skips it.
Wolf’s stack holds int, where the C’s holds double. That is a
decision, not an accident, and it is the chapter’s one substantive
divergence from the twin: it costs us 7 2 / as a fraction, and §27.4
comes back to what it buys.
27.3 Parse errors as payload-carrying tags
A token is a number or it is not, and when it is not, the useful thing to report is which token:
struct Bad { token: str }
fn number(tok: str) -> int ! {NotNumber(Bad)} {
let body = tok.strip_prefix("-") else tok
if body.is_empty() { return NotNumber(Bad { token: tok }) }
var n = 0
for b in body.bytes() {
if b < 48 || b > 57 { return NotNumber(Bad { token: tok }) }
n = n * 10 + (b - 48)
}
if tok.starts_with("-") { 0 - n } else { n }
}
fn is_operator(tok: str) -> bool {
if tok.len != 1 { return false }
let b = tok.bytes()[0]
b == 43 || b == 45 || b == 42 || b == 47
}
NotNumber(Bad) is a tag with a payload — a variant of the error row that
carries a Bad alongside it, and Bad holds the token that failed. That
is the whole answer to §27.1’s problem. Wolf does not need a flag beside
the value because the failure is a value, in a row the signature spells
out, and it does not need a second call to find out what went wrong
because the tag brought the evidence.
Two other things in those eighteen lines are worth a sentence.
strip_prefix("-") else tok is the sign handling, and it needs no
lookahead and no pushback buffer: words() already cut the input into
tokens, so a - that is a sign is a byte inside a token and a - that is
an operator is a token of its own. getop’s 28 lines were paying for the
absence of that split. The wolf equivalent — number and is_operator
together — is 15 lines of code, and 10 of them are number.
n = n * 10 + (b - 48) is that digit loop, written out by hand. It is
also the one place a reader may reasonably expect a library call, and
there is not one: the digits are scanned from the byte view, 48 is the
byte for 0, and the loop rejects anything outside 0–9 with the tag.
It earns its page anyway, because it is the same arithmetic atof is
doing and it is checked — wolf’s * and + trap on overflow in every
profile, so a fourteen-digit token cannot quietly become something else,
which is a thing atof will do to you at 17 digits without a word.
27.4 The operator dispatch as a match
The evaluator, and the calculator is finished:
fn eval(line: str) -> int ! {NotNumber(Bad), Unknown(Bad), Empty, DivZero} {
var stack = List[int]()
for tok in line.words() {
if !is_operator(tok) {
(mut stack).push(number(tok)?)
} else {
if stack.len < 2 { return Empty }
let b = (mut stack).pop() else { return Empty }
let a = (mut stack).pop() else { return Empty }
let r = match tok.bytes()[0] {
43 => a + b,
45 => a - b,
42 => a * b,
47 => {
if b == 0 { return DivZero }
a / b
},
_ => return Unknown(Bad { token: tok }),
}
(mut stack).push(r)
}
}
if stack.len != 1 { return Empty }
(mut stack).pop() else { return Empty }
}
The dispatch is a match over the operator’s byte, and here is the place
the C column is plainly better: Ritchie writes case '+':, and this
column writes 43, with the character in a comment. A one-character
literal is not part of what a wolf program can say, so the arms name the
bytes and the reader trusts the comments. It is four small losses of
clarity in a program that gains elsewhere, and it is the sharpest thing
the C wins in this whole part.
What the match gets right is the rest of it. Every arm produces the
value of r, so there is no assignment to forget; 47 guards its divisor
and returns DivZero from inside the arm; and the _ arm returns
Unknown(Bad { token: tok }) — with the token — so an unrecognized
operator arrives at the caller identifiable rather than merely
unwelcome.
if stack.len < 2 { return Empty } before the two pops is the C’s sp < 1 test, moved to where it can do something about it. The C tests at the
end of the line, so by then two pops have already happened and two
stack empty messages have already been printed. This test happens before
the operator is applied, so an underflowing expression produces one
report, which is the number of things that went wrong.
Now the driver:
fn main() -> !int {
let script = """
2 3 +
5 1 2 + 4 * + 3 -
7 0 /
4 x *
+
"""
for line in script.lines() {
let v = eval(line) else |err| {
match err {
NotNumber(e) => print("error: `{e.token}` is not a number"),
Unknown(e) => print("error: `{e.token}` is not an operator"),
Empty => print("error: the stack does not hold two operands"),
DivZero => print("error: division by zero"),
}
continue
}
print("{v}")
}
0
}
match err over the row is exhaustive, so a fifth failure tag added to
eval tomorrow is a compile error here today rather than a silent fall
through to a default. And each arm can say what happened, because each tag
knows:
$ lupin rpn.lu
5
14
error: division by zero
error: `x` is not a number
error: the stack does not hold two operands
Set the two error columns beside each other. The C prints error, twice,
and puts three unattributed complaints on standard error. Wolf prints
which error, and for the bad token it prints the token. Neither program
is longer for it — the C’s broken flag, its four fprintfs and its
end-of-line test cost more lines than the row and the four match arms.
The measurement, whole programs:
$ wc -l samples/contrast/rpn.c samples/projects/rpn/rpn.lu
151 samples/contrast/rpn.c
67 samples/projects/rpn/rpn.lu
Code lines only — comments and blanks removed — 120 against 63. Not quite
half. The three places the lines went are the three sections above: the
stack machinery the standard library already has (34 lines of C, 1 of
wolf), the pushback tokenizer that words() makes unnecessary (28 lines
of C, 15 of wolf including the hand-rolled digit scan), and the error
plumbing (a global flag, four sites that set it, one site that reads it,
against a row and a match).
One last accounting on the int stack. It costs 7 2 / as a fraction,
and that is the whole of what it costs on the four expressions this chapter
runs; both columns print the same five lines. What it buys is the next
section, because integer arithmetic over text it was handed is the one
thing both wolf implementations do identically, byte for byte, and CI
checks that claim on this file every time it runs.
27.5 Develop interpreted, ship compiled
Every transcript in this chapter so far has been lupin. Here is the same
file, built:
$ wolf build rpn.lu && ./rpn
warning[W0603]: the mark `Empty` is spelled CapCase
--> ./rpn.lu:20:60
|
20 | fn eval(line: str) -> int ! {NotNumber(Bad), Unknown(Bad), Empty, DivZero} {
| ^^^^^ reads as if there were data to destructure
|
= note: payload-free marks are lowercase bare words (`none`, `eof`, `parse`); CapCase is the
reader's signal that a payload waits inside.
warning[W0603]: the mark `DivZero` is spelled CapCase
--> ./rpn.lu:20:67
|
20 | fn eval(line: str) -> int ! {NotNumber(Bad), Unknown(Bad), Empty, DivZero} {
| ^^^^^^^ reads as if there were data to destructure
|
5
14
error: division by zero
error: `x` is not a number
error: the stack does not hold two operands
Two of those are the compiler’s opinion about our spelling, not about our
program: Empty and DivZero carry no payload, and the convention is that
a mark with nothing inside it is a lowercase bare word. Read them, decide,
and note that the binary was built either way — a warning is advice with a
code, and its code is how you look it up or turn it off. The explanatory
note arrives once per code and the second warning does without it, which is
the compiler declining to say the same paragraph twice.
Same source, same five lines, no flag and no configuration. This is the two-implementation story of §1.2 arriving at the point where it pays: you edit and run under the interpreter, where the loop from a saved file to an answer is one process start, and you build the binary when you want the binary. Neither implementation is a preview of the other, and the way you find out they agree is that the book’s CI runs both of them on every program in this part and compares the bytes.
It does not always work out that way, and the honesty rule applies to the
tools as well as to the languages. Chapter 26’s count runs only as a
binary: fs_read_text and read_line are the compiled column’s, and the
interpreter has no filesystem — deliberately, because a machine whose job
is to be a reference implementation would rather decline an effect than
mock one. Chapter 28’s wordtree runs only under the interpreter. rpn
is the program in the middle, and the reason it is the one that runs both
ways is that it does nothing but arithmetic on text it was given.
Exercise 27-1 (fingers · lupin) — Add % to the dispatch. Then
predict what your arm does for 7 0 % before you run it, and say whether
you had to write anything the / arm did not already show you.
Exercise 27-2 (comprehension · lupin) — eval returns Empty for
both an underflowing operator and an expression that leaves two values on
the stack. Predict the output for the three lines 3 +, 3 4, and 3 4 + 5, and then argue whether one tag for two situations is the same mistake
§27.1 accused the C of making.
Exercise 27-3 (extension · lupin) — Give Empty a payload: which
operator ran out of operands, and how many it found. You will have to
change the row, the two returns, and one match arm — say what told you
each one.
Exercise 27-4 (comprehension · lupin) — Feed it 007 and -0 and
- 3. Predict all three results before running, then explain which of the
three is handled by strip_prefix and which by words().
Exercise 27-5 (spelunking · the C twin) — Take a census of
broken in rpn.c: count the places that can set it and the places that
read it, and write down the line numbers. Then take the same census of the
wolf column’s failure surface — where a tag can be produced, and where one
is handled. Say what the two ratios tell you.
Exercise 27-6 (extension · lupin) — Add two stack words that are not
operators: dup duplicates the top value, swap exchanges the top two.
Neither touches number or the match. Predict what 7 2 swap -
evaluates to before you run it.
Exercise 27-7 (design) — Wolf’s stack holds int and K&R’s holds
double. Argue the other choice: what would the wolf column have to give
up to work in f64, what would it gain, and where in this chapter would
the text have to change?
Exercise 27-8 (design) — Sketch the REPL: read a line, evaluate it,
print the answer, and stop at end of input. read_line() returns
str ! {eof, io, utf8}, so name the loop’s exit condition, and then say
what the calculator would have to remember between lines for x 3 + to
mean anything — and what shape that memory wants to be.