A Calculator
The second program is an interactive calculator. It reads expressions, one
per line, and prints their values. It knows the usual operators and their
precedence, parentheses, a few functions, and variables set with let.
Its interest lies in the parser: a set of mutually recursive functions,
nested inside one driver function, which report every error with
return … from, and so contain no error-handling code at all.
#The program25.1
Given this input:
1 + 2 * 3
(1 + 2) * 3
-2 ^ 2
2 ^ 3 ^ 2
let r = 1.5
pi * r ^ 2
sqrt(2) * sqrt(2)
1 / (r - 1.5)
2 * (3 + 4
sqrt(-1)
wings * 2
3 4
let = 5
2 * $
and this program, run as goose calc.goose < input.txt (or with no
redirection, to type expressions by hand):
import std;
import math;
import os;
import dictionary;
let NAME_MAX = 16;
let DEPTH_MAX = 200;
type Name = u8[..NAME_MAX];
type Vars = dictionary<Name, f64>;
fn is_digit(c: u8) -> bool { c >= '0' && c <= '9' }
fn is_letter(c: u8) -> bool {
(c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_'
}
fn is_name_byte(c: u8) -> bool { is_letter(c) || is_digit(c) }
// One line of input: `let name = expr`, or an expression. Returns
// the value and "", or 0.0 and a message saying what went wrong
// and where.
fn evaluate(src: const u8[:], vars: Vars&) -> f64, u8[] {
var pos = 0;
var depth = 0; // parentheses open
fn fail(at: i64, what: u8[:]) -> f64 {
let msg = str("column ", at + 1, ": ", what);
return 0.0, msg from evaluate;
}
fn byte() -> u8 { if pos < src.len { src[pos] } else { 0 } }
fn peek() -> u8 {
while byte() == ' ' { pos += 1; }
return byte();
}
fn here() -> i64 { peek(); pos }
fn eat(c: u8) -> bool {
if peek() != c { return false; }
pos += 1;
return true;
}
fn word() -> u8[:] {
let start = pos;
while is_name_byte(byte()) { pos += 1; }
if pos - start > NAME_MAX { fail(start, "name too long"); }
return src[start..pos];
}
fn number() -> f64 {
let start = pos;
while is_digit(byte()) || byte() == '.' { pos += 1; }
let v, ok = parse_flt(src[start..pos]);
return if ok { v } else { fail(start, "bad number") };
}
fn apply(at: i64, f: u8[:], x: f64) -> f64 {
if f == "abs" { return abs(x); }
if f == "sqrt" {
if x < 0.0 {
return fail(at, "sqrt of a negative number");
}
return sqrt(x);
}
if f == "ln" {
if x <= 0.0 {
return fail(at, "ln of a number <= 0");
}
return log(x);
}
return fail(at, str("no function called ", f));
}
// The grammar, one function per rule:
// sum = product (('+' | '-') product)*
// product = power (('*' | '/') power)*
// power = '-' power | atom ('^' power)?
// atom = number | name | name group | group
// group = '(' sum ')'
recursive fn sum() -> f64 {
var v = product();
loop {
if eat('+') { v += product(); }
else if eat('-') { v -= product(); }
else { return v; }
}
}
fn product() -> f64 {
var v = power();
loop {
if eat('*') { v *= power(); }
else if eat('/') {
let at = here();
let d = power();
if d == 0.0 {
return fail(at, "division by zero");
}
v /= d;
}
else { return v; }
}
}
recursive fn power() -> f64 {
if eat('-') { return -power(); }
let base = atom();
return if eat('^') { pow(base, power()) } else { base };
}
fn atom() -> f64 {
let c = peek();
let at = pos; // after the spaces
if eat('(') { return group(at); }
if is_digit(c) || c == '.' { return number(); }
if c == 0 { return fail(at, "unexpected end of line"); }
if !is_letter(c) {
return fail(at, str("unexpected ", src[at..at + 1]));
}
let n = word();
if eat('(') { return apply(at, n, group(at)); }
let v = vars.get(n);
if v { return v; }
return fail(at, str("unknown name ", n));
}
// After the '(' at position at: the sum, then ')'.
fn group(at: i64) -> f64 {
depth += 1;
if depth > DEPTH_MAX {
return fail(at, "too deeply nested");
}
let v = sum();
if !eat(')') { return fail(here(), "expected )"); }
depth -= 1;
return v;
}
fn statement() -> f64 {
var target: Name = "";
if is_letter(peek()) {
let start = pos;
if word() == "let" {
let at = here();
target = word();
if target.len == 0 {
return fail(at, "expected a name after let");
}
if !eat('=') { return fail(pos, "expected ="); }
} else {
pos = start;
}
}
let v = sum();
if peek() != 0 {
return fail(pos, "expected an operator");
}
if target.len > 0 { vars.insert(target, v); }
return v;
}
return statement(), "";
}
fn main() {
var vars = Vars {};
vars.insert("pi", PI);
var line: u8[>..] = [];
while read_line(line) {
if trim(line).len > 0 {
let v, err = evaluate(line, vars);
if err.len > 0 {
print("error: ", err);
} else {
print(v);
}
}
line.clear();
}
}
it prints:
7.0 9.0 -4.0 512.0 1.5 7.0685834705770345 2.0000000000000004 error: column 5: division by zero error: column 11: expected ) error: column 1: sqrt of a negative number error: column 1: unknown name wings error: column 3: expected an operator error: column 5: expected a name after let error: column 5: unexpected $
#One function per rule25.2
The parser is a recursive-descent parser: the grammar in the comment has five rules, and each rule is one function that returns the value of the text it matched. There is no syntax tree. Each function computes its value directly from the values of the parts it calls for:
Precedence comes from the order of the calls. sum asks product for its
operands, so * binds more tightly than +, and product asks power,
so ^ binds more tightly than *. Associativity comes from the shape of
each function. sum and product loop, folding each new operand into v,
which makes +, -, * and / associate to the left: 8 - 2 - 1 is
(8 - 2) - 1. power calls itself for its right operand, which makes ^
associate to the right, the convention in mathematics: 2 ^ 3 ^ 2 is
2 ^ 9, which is 512. And because the unary minus in power applies to a
whole power, -2 ^ 2 is -(2 ^ 2), which is -4.
#Nested functions instead of a parser object25.3
All the parsing functions are nested inside evaluate, and they share its
locals pos and depth and its parameters src and vars as free
variables. In C, they would be functions that all take a Parser *, and in
Rust, methods on a Parser struct. Here the state needs no type and no
parameter, and the functions are declared where they are used.
Nested functions are not closures (Chapter 5). They exist only at compile
time, and accessing pos from inside atom is an ordinary access to a
local of evaluate's frame. Nothing is allocated, and the functions
cannot escape evaluate.
#Marking the recursion25.3.1
Only two of the functions are recursive fn. The rule from Chapter 17 is
that the entry of each cycle of calls is marked. There are two cycles
here: sum → product → power → atom → group → sum, entered at
sum from statement, and power → power, entered at power from
product. Leave the keyword off sum, and the compiler names the cycle:
fn sum() -> f64 {
var v = product();
loop {
if eat('+') { v += product(); }
else if eat('-') { v -= product(); }
else { return v; }
}
}
error: recursive call cycle through sum, which is not declared `recursive fn` (§7.8)
#Errors from anywhere25.4
Every error is reported by a call to fail, which leaves the parse at once:
fn fail(at: i64, what: u8[:]) -> f64 {
let msg = str("column ", at + 1, ": ", what);
return 0.0, msg from evaluate;
}
The return … from evaluate ends the innermost running call of evaluate,
whatever is between: fail itself, atom, group, any number of nested
sums, and statement. evaluate's caller receives 0.0 and the
message, and main prints it. The functions in between have no error
paths of their own. They do not check results, propagate failures or
return bools, so each one reads as if errors could not happen.
fail is declared to return f64, although it never returns at all. That
lets it be used wherever a value is expected, as in
return if ok { v } else { fail(start, "bad number") } in number, and keeps every function's
result type its plain value.
The position of each error is the position where the problem starts: the
operand that was zero, the name that was unknown, or the end of the line
where a ) was missing. Each function records at before it calls
further, since by the time an error is found, pos has usually moved on.
#Where the data lives25.5
line, inmain, is one builder reused for every line of input.srcis a slice ofline, and every word is a slice ofsrc. Like the word counter, the parser copies nothing out of its input.- The error message is the only thing built per error. It is a
u8[]returned tomain, which prints it before the next line is read. - The variables are a
dictionary<Name, f64>, andNameisu8[..16].
That last point differs from the word counter, and for a good reason. The
counter's keys were slices of its one input buffer, which lived for the
whole program. Here, a key must outlive the line it was read from, because
line is cleared and refilled for every line. So the dictionary owns its
keys, as inline arrays of up to sixteen bytes, and insert copies the name
into its slot. The compiler would have rejected a dictionary<const u8[:],
f64> filled from line, since the next line.clear() would leave its
keys pointing at discarded bytes.
The capacity of Name explains the check in word. Storing a longer name
in a u8[..16] aborts the program:
type Name = u8[..16];
fn main() {
let word = "a_name_much_longer_than_sixteen";
var n: Name = word;
print(n);
}
goose runtime error: limited array capacity exceeded
For a calculator, an abort on a long name is the wrong behaviour, so
word reports an error instead.
#Limits25.6
The other guard is on depth. Each ( costs a few native stack frames,
and a recursion deeper than the native stack ends the program. It is a
clean abort, not a crash, but still not what a calculator should do with a
line of 100,000 parentheses. So group counts the open parentheses and
reports too deeply nested past 200. Any recursive parser that reads
untrusted input should have such a limit.
#Exercises25.7
-
Add the
%operator, with the same precedence as*and/. Should it be Euclidean, like Goose's integer%, or follow C'sfmod? -
Add functions of two arguments,
max(a, b)andmin(a, b). -
Make the calculator remember the last value it printed as
ans. -
Make an error message show the line with a
^under the column where the error was found.