An Expression Interpreter

Problem

The grammar comes first, before any parsing code. It uses the classic three-level structure, where * and / naturally get higher precedence than + and - — not because of any explicit rule, but simply because of the order in which the productions call each other.

expr   := term (('+' | '-') term)*
term   := factor (('*' | '/') factor)*
factor := NUMBER | IDENT | '(' expr ')' | '-' factor

The harder design question is not the grammar — it is what happens when a syntactically valid expression describes something semantically impossible: 1 / 0, or a variable that was never bound. Both are common enough in a calculator's real usage that "throw whatever the host happens to throw" is not good enough. A labeled failure that names which rule was broken will be more useful to a caller than a generic exception three frames away from the bad input.

Design as Contract

The AST is a closed union with four shapes, and nothing else is a legal expression:

union Expr
  Num(value: Real)
  Var(name: String)
  Bin_Op(op: String, left: Expr, right: Expr)
  Neg(operand: Expr)
end

The evaluator is a single match over that union, with a case for every constructor. This is exhaustive. The type checker enforces this — it's not just a convention someone has to remember to follow:

function eval_expr(e: Expr, env: Map[String, Real]): Real do
  match e of
    Num(value) then
      result := value
    Var(name) then
      result := lookup(env, name)
    Neg(operand) then
      result := 0.0 - eval_expr(operand, env)
    Bin_Op(op, left, right) then
      do
        ...
      end
  end
end

The moment a fifth expression shape is added to Expr — say, a function call — this match stops compiling until a Call(...) case is written. That is the same safety net Chapter 2's Task_Status union gave a two-state field; here it guards an AST that can grow arbitrarily and still never leave a case silently unhandled.

The semantic failures — division by zero, an unbound variable — are stated as preconditions on the two small functions that can actually violate them, not checked inline wherever they might come up:

function divide(a: Real, b: Real): Real
require
  non_zero: b /= 0.0
do
  result := a / b
end

function lookup(env: Map[String, Real], name: String): Real
require
  known: env.contains_key(name)
do
  result := env.get(name)
end

This is what "a caller gets a labeled failure" means concretely: a violated require names the clause that broke — non_zero, known — in the failure itself, which is strictly more information than a bare ArithmeticException or a null dereference would give the same caller, for the same mistake.

Build

Tokenizing is one regular expression, doing the whole job in a single pass — numbers (with or without a decimal point), identifiers, and the six punctuation characters this grammar needs, in one alternation:

function tokenize(text: String): Array[String] do
  let rx: Regex := create Regex.compile('\d+\.\d+|\d+|[A-Za-z_][A-Za-z0-9_]*|[+\-*/()]')
  result := rx.find_all(text)
end

Parser is recursive descent in its most direct form, one method per grammar production, each returning an Expr:

parse_expr(): Expr do
  result := parse_term()
  from
  until
    peek() /= "+" and peek() /= "-"
  do
    let op: String := advance()
    let rhs: Expr := parse_term()
    result := create Bin_Op.make(op, result, rhs)
  end
end

parse itself — the entry point — carries a postcondition that is easy to skip and cheap to keep: the whole token stream has to be consumed, or something was left over that the grammar never accounted for, which is exactly the kind of trailing-garbage input a hand-written parser can silently ignore if nobody thinks to check for it explicitly:

parse(): Expr
do
  result := parse_expr()
ensure
  consumed_everything: at_end()
end

Test

Eleven checks cover precedence, parentheses (including nested ones), unary minus, and variable lookup — the ordinary arithmetic surface — plus, deliberately, both contract-violation paths, caught with rescue rather than asserted to simply not crash:

let div_zero_failed: Boolean := false
do
  evaluate("1 / 0", empty_env)
rescue
  div_zero_failed := true
end
c.check("division by zero caught", "true", "" + div_zero_failed)

Testing that a contract violation is caught, by name, is a different assertion than testing that a program does not crash — it confirms the failure arrives through the channel this design promised it would (a labeled precondition), not through whatever the host happens to do when the underlying arithmetic misbehaves. calc_repl.nex uses the identical do ... rescue ... end pattern at its own boundary, turning the same violation into a one-line error: message instead of a crashed REPL session.

Takeaways

A contract violation tells you a promise was broken, not where the code that broke it actually lives. The two can be several calls apart, and mistaking a failure's location for the mistake's location costs real time in any codebase, not just this one. A check firing far from the actual defect is still the contract doing its job. It caught something a silent wrong answer would have let through unnoticed.

Chapter 5 leaves the single-threaded world both this project and the last two lived in, and asks what a contract has to say once more than one task can be touching the same program at once.