examples/rpn/

# Reverse Polish, evaluated on a stack — the shortest program in this corpus
# whose failures are all interesting.
#
# Corpus and regression material (CLAUDE.md §9). It closes no measured form
# gap; `examples/calculator/` already parses infix. What this adds is the
# opposite shape: no grammar, no precedence, no parentheses, and therefore
# nothing to get wrong except the STACK — which is where every RPN bug is.
# The three ways it breaks are all arity mistakes, and none of them is a
# syntax error, so a language that only checked syntax would accept all
# three.
#
# WHY IT IS WORTH A PROGRAM. `spec:155` makes integer division by zero an
# ABORT, not a failure — so an evaluator that reads `4 0 /` from user input
# must check before it divides, or the process ends. That is one line, it is
# easy to leave out, and leaving it out is invisible until somebody types a
# zero. The check is here and it has its own case.

variant Token
    number
        value: i64
    plus
    minus
    times
    divide

function tokens_of(text: str) -> [Token]?
    out: [Token] @= []

    for word in split_words(text)
        one = token_of(word)?
        out @ out.push(one)

    return ok(out)

function token_of(word: str) -> Token?
    if word == "+"
        return ok(.plus)

    if word == "-"
        return ok(.minus)

    if word == "*"
        return ok(.times)

    if word == "/"
        return ok(.divide)
    return ok(.number(value: number_of(word)?))

# A number, read by hand because the language ships no `str` to `i64`: the
# conversions in `spec:62-68` all go the other way. Nine lines, and the sign
# is the half a first draft forgets.
function number_of(word: str) -> i64?
    if word.len() == 0
        return fail(code: "empty", msg: "an empty word is not a number")
    negative: bool @= false
    total: i64 @= 0
    digits: i64 @= 0
    first: bool @= true

    for ch in word.chars()
        if first && ch == "-"
            negative @ true
            first @ false
            continue
        first @ false
        d = digit_of(ch)?
        total @ total * 10 + d
        digits @ digits + 1

    if digits == 0
        return fail(code: "not_a_number", msg: "`" + word + "` has no digits in it")

    return if negative
        ok(0 - total)
    else
        ok(total)

function digit_of(ch: str) -> i64?
    digits = "0123456789"
    i: i64 @= 0

    while i < 10
        if digits.slice(from: i, to: i + 1) == ch
            return ok(i)
        i @ i + 1

    return fail(code: "not_a_digit", msg: "`" + ch + "` is not a digit")

function split_words(text: str) -> [str]
    out: [str] @= []
    piece: str @= ""

    for ch in text.chars()
        if ch == " "
            if piece.len() > 0
                out @ out.push(piece)
            piece @ ""
        else
            piece @ piece + ch

    if piece.len() > 0
        out @ out.push(piece)

    return out

function evaluate(text: str) -> i64?
    stack: [i64] @= []

    for one in tokens_of(text)?
        match one
            .number n => stack @ stack.push(n.value)
            .plus | .minus | .times | .divide =>
                if stack.len() < 2
                    return fail(code: "too_few", msg: "an operator with fewer than two numbers under it")
                right = stack[stack.len() - 1]
                left = stack[stack.len() - 2]
                stack @ stack.slice(from: 0, to: stack.len() - 2)
                stack @ stack.push(applied(one, left: left, right: right)?)

    if stack.len() == 0
        return fail(code: "empty", msg: "nothing to evaluate")

    if stack.len() > 1
        return fail(code: "too_many", msg: "numbers left over: an operator is missing")

    return ok(stack[0])

function applied(op: Token, left: i64, right: i64) -> i64?
    return match op
        .plus  => ok(left + right)
        .minus => ok(left - right)
        .times => ok(left * right)
        .divide =>
            # `spec:155`: integer division by zero ABORTS. A program reading
            # its input from anywhere must check first, or a typed zero ends
            # the process rather than producing a diagnostic.
            if right == 0
                fail(code: "divide_by_zero", msg: "cannot divide by zero")
            else
                ok(left / right)
        .number _ => fail(code: "not_an_operator", msg: "a number is not an operator")

function main()
    for one in ["3 4 +", "3 4 + 2 *", "5 1 2 + 4 * + 3 -", "-7 3 /", "7 -3 /"]
        print(one + " = " + evaluate(one).must().to_str())

    # The three arity failures, none of which is a syntax error.
    print(evaluate("3 +").is_err())
    print(evaluate("3 4").is_err())
    print(evaluate("").is_err())

    # And the one the abort rule forces a check for.
    print(evaluate("4 0 /").is_err())
    print(evaluate("4 0 x").is_err())

test "the ordinary case, and the one everybody uses as an example"
    assert evaluate("3 4 +").must() == 7
    assert evaluate("3 4 + 2 *").must() == 14
    assert evaluate("5 1 2 + 4 * + 3 -").must() == 14
    assert evaluate("2").must() == 2

test "the four operators mean what they mean, and order is not commutative"
    assert evaluate("7 3 -").must() == 4
    assert evaluate("3 7 -").must() == 0 - 4
    assert evaluate("7 3 /").must() == 2
    assert evaluate("3 7 /").must() == 0
    assert evaluate("7 3 *").must() == 21

test "division truncates toward zero, on both signs"
    # `spec:156` says so, and an RPN evaluator is where a reader meets it.
    assert evaluate("-7 3 /").must() == 0 - 2
    assert evaluate("7 -3 /").must() == 0 - 2
    assert evaluate("-7 -3 /").must() == 2

test "dividing by zero is a failure and not an abort"
    # The whole reason `applied` has a branch: without it the process ends.
    assert evaluate("4 0 /").is_err()
    assert evaluate("0 0 /").is_err()
    assert !evaluate("4 2 /").is_err()

test "the three arity failures are three different codes"
    # Too few numbers under an operator.
    assert evaluate("3 +").is_err()
    assert evaluate("+").is_err()

    # Numbers left over, which means a missing operator.
    assert evaluate("3 4").is_err()
    assert evaluate("1 2 3 +").is_err()

    # Nothing at all.
    assert evaluate("").is_err()
    assert evaluate("   ").is_err()

test "a word that is neither a number nor an operator fails"
    assert evaluate("3 4 x").is_err()
    assert evaluate("hello").is_err()
    assert evaluate("3 4.5 +").is_err()
    assert evaluate("- +").is_err()

test "a negative number is a number and a minus is an operator"
    # The one ambiguity RPN has, and it is resolved by position: a `-` with
    # digits after it is a number, a `-` alone is an operator.
    assert evaluate("-3").must() == 0 - 3
    assert evaluate("-3 -4 +").must() == 0 - 7
    assert evaluate("3 -4 -").must() == 7
    assert number_of("-42").must() == 0 - 42
    assert number_of("42").must() == 42
    assert number_of("-").is_err()

test "reading a number by hand agrees with itself on the boundaries"
    assert number_of("0").must() == 0
    assert number_of("-0").must() == 0
    assert number_of("1000000").must() == 1000000
    assert number_of("").is_err()
    assert number_of("1a").is_err()
    assert number_of("a1").is_err()