examples/calculator/

# The evaluator, the tree simplifier, and the one function that puts the whole
# pipeline together. It names both modules below it, and this is the file where
# the rule earns its keep: `parse.expression(@p)` says where the recursion lives
# without opening another file, and so does `lex.tokenize`.

use lex
use parse

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_TRAILING_TOKENS: str
    "trailing_tokens"

constant ERR_UNKNOWN_NAME: str
    "unknown_name"

## Evaluator

# The value bound to a name, with a decent message if absent.
function lookup(env: {str: i64}, name: str) -> i64?
    if env[name].is_err()
        return fail(code: ERR_UNKNOWN_NAME, msg: "undefined variable: " + name)
    return ok(env[name].must())

function sum_of(children: [parse.Expr], env: {str: i64}) -> i64?
    tot: i64 @= 0

    for c in children
        tot @ tot + evaluate(c, env)?

    return ok(tot)

function product_of(children: [parse.Expr], env: {str: i64}) -> i64?
    tot: i64 @= 1

    for c in children
        tot @ tot * evaluate(c, env)?

    return ok(tot)

# The value of the tree. Fails on the first unknown name.
function evaluate(e: parse.Expr, env: {str: i64}) -> i64?
    return match e
        .num n      => ok(n.v)
        .variable x => env.lookup(x.name)
        .sum s      => s.children.sum_of(env)
        .product q  => q.children.product_of(env)

# Every name appearing in the tree, with repetitions.
function names_used(e: parse.Expr) -> [str]
    return match e
        .num _      => []
        .variable x => [x.name]
        .sum s      => names_of(s.children)
        .product q  => names_of(q.children)

function names_of(children: [parse.Expr]) -> [str]
    out: [str] @= []

    for c in children
        for n in c.names_used()
            out @ out.push(n)

    return out

## Interface

# From text to result, in one call.
function calculate(text: str, env: {str: i64}) -> i64?
    ts = lex.tokenize(text)?
    p: parse.Parse @= parse.Parse(ts: ts, pos: 0)
    tree = parse.expression(@p)?

    if !parse.parse_at_end(p)
        return fail(code: ERR_TRAILING_TOKENS, msg: "leftover input at the end")
    return evaluate(tree, env)

test "precedence and parens"
    empty: {str: i64} = {}
    assert calculate("2 + 3 * 4", empty).must() == 14
    assert calculate("(2 + 3) * 4", empty).must() == 20
    assert calculate("2 * 3 * 4", empty).must() == 24

test "variables from the environment"
    env = {"x": 10, "y": 4}
    assert calculate("x * y + 2", env).must() == 42

test "errors reach the top"
    empty: {str: i64} = {}

    match calculate("2 +", empty)
        .ok _  => assert false
        .err e => assert e.code == parse.ERR_UNEXPECTED_END

    match calculate("z + 1", empty)
        .ok _  => assert false
        .err e => assert e.code == ERR_UNKNOWN_NAME

    match calculate("(2 + 3", empty)
        .ok _  => assert false
        .err e => assert e.code == parse.ERR_UNCLOSED_PAREN

test "values are always copies"
    a = [1, 2, 3]
    b: [i64] @= a
    b @ b.push(4)
    assert a.len() == 3
    assert b.len() == 4

## Simplifier

# Simplify the tree: `x * 1` becomes `x`, `x + 0` becomes `x`.
#
# Bottom-up: every child is simplified before the node itself, so
# `(x + 0) * 1` collapses in one pass. A node whose children all vanish
# collapses to the identity it was built around — an empty `sum` is 0 and an
# empty `product` is 1, which is the same rule `sum_of` and `product_of` use for
# an empty list.
function simplify(e: parse.Expr) -> parse.Expr
    return match e
        .num _      => e
        .variable _ => e
        .sum s      => rebuild(kept: keep_sum(s.children), zero: true)
        .product q  => rebuild(kept: keep_product(q.children), zero: false)

# The children of a sum that survive: each simplified, and the literal zeroes
# dropped because adding one changes nothing.
function keep_sum(children: [parse.Expr]) -> [parse.Expr]
    out: [parse.Expr] @= []

    for child in children
        one = simplify(child)

        if !is_literal(e: one, v: 0)
            out @ out.push(one)

    return out

# The same for a product, dropping the ones.
function keep_product(children: [parse.Expr]) -> [parse.Expr]
    out: [parse.Expr] @= []

    for child in children
        one = simplify(child)

        if !is_literal(e: one, v: 1)
            out @ out.push(one)

    return out

# Is this node exactly the literal `v`?
function is_literal(e: parse.Expr, v: i64) -> bool
    return match e
        .num n      => n.v == v
        .variable _ => false
        .sum _      => false
        .product _  => false

# One child left is that child; none left is the operation's identity.
function rebuild(kept: [parse.Expr], zero: bool) -> parse.Expr
    if kept.len() == 1
        return kept[0]

    if kept.len() == 0
        if zero
            return .num(v: 0)
        return .num(v: 1)

    if zero
        return .sum(children: kept)
    return .product(children: kept)

# The lexer: text in, tokens out. It names nothing outside itself, which is why
# it is the first module — a module with no `use` line is the base case of the
# whole graph.

## Tokens

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_UNKNOWN_CHAR: str
    "unknown_char"

variant Token
    num
        v: i64
    name
        s: str
    plus
    times
    lparen
    rparen

# Text and position. Travels through the lexer as `@`.
record Lex
    text: str
    pos: i64

function at_end(l: Lex) -> bool
    return l.pos >= l.text.len()

function here(l: Lex) -> u8
    return l.text[l.pos]

function advance(@l: Lex)
    l.pos @ l.pos + 1

function is_digit(c: u8) -> bool
    return c >= '0' && c <= '9'

function is_letter(c: u8) -> bool
    return c >= 'a' && c <= 'z'

# Reads an integer, consuming it.
function read_number(@l: Lex) -> i64
    v: i64 @= 0

    while !l.at_end() && l.here().is_digit()
        v @ v * 10 + to_i64(l.here() - '0').must()
        advance(@l)

    return v

# Reads an identifier, consuming it.
function read_name(@l: Lex) -> str
    start = l.pos

    while !l.at_end() && l.here().is_letter()
        advance(@l)

    return l.text.slice(from: start, to: l.pos)

# Splits the text into tokens. Fails on the first unknown character.
function tokenize(text: str) -> [Token]?
    l: Lex @= Lex(text: text, pos: 0)
    out: [Token] @= []

    while !l.at_end()
        c = l.here()

        if c == ' '
            advance(@l)
        else if c.is_digit()
            out @ out.push(.num(v: read_number(@l)))
        else if c.is_letter()
            out @ out.push(.name(s: read_name(@l)))
        else if c == '+'
            out @ out.push(.plus)
            advance(@l)
        else if c == '*'
            out @ out.push(.times)
            advance(@l)
        else if c == '('
            out @ out.push(.lparen)
            advance(@l)
        else if c == ')'
            out @ out.push(.rparen)
            advance(@l)
        else
            return fail(code: ERR_UNKNOWN_CHAR, msg: "at position " + l.pos.to_str())

    return ok(out)

test "tokenizes numbers, names and symbols"
    ts = tokenize("12 + xy * (3)").must()
    assert ts.len() == 7
    assert ts[0] == .num(v: 12)
    assert ts[1] == .plus
    assert ts[2] == .name(s: "xy")

test "tokenize rejects the unknown"
    match tokenize("2 $ 3")
        .ok _  => assert false
        .err e => assert e.code == ERR_UNKNOWN_CHAR

# The parser: tokens in, a tree out. It names `lex`, and every name it takes
# from there is written qualified — `lex.Token` in a signature, `lex.Token` in a
# field. The case patterns stay bare (`.num n`), because which variant a case
# belongs to comes from context and not from where the variant was declared.

use lex

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_EXPECTED_FACTOR: str
    "expected_factor"

constant ERR_UNCLOSED_PAREN: str
    "unclosed_paren"

constant ERR_UNEXPECTED_END: str
    "unexpected_end"

## Syntax tree

# A tree node. Children live in an array, which is the language's
# only indirection: that is what makes the recursive type finite.
variant Expr
    num
        v: i64
    variable
        name: str
    sum
        children: [Expr]
    product
        children: [Expr]

# Tokens and position. Travels through the parser as `@`.
record Parse
    ts: [lex.Token]
    pos: i64

function parse_at_end(p: Parse) -> bool
    return p.pos >= p.ts.len()

function parse_here(p: Parse) -> lex.Token
    return p.ts[p.pos]

function parse_advance(@p: Parse)
    p.pos @ p.pos + 1

## Parser
#
# Recursive descent. The four functions call each other; declaration
# order does not matter, so mutual recursion needs no forward
# declarations — and that holds across modules too, since the whole
# program is one compilation.

# A number, a name, or a parenthesised expression.
function factor(@p: Parse) -> Expr?
    if p.parse_at_end()
        return fail(code: ERR_UNEXPECTED_END, msg: "the expression ends too soon")

    t = p.parse_here()
    parse_advance(@p)

    return match t
        .num n                   => ok(.num(v: n.v))
        .name x                  => ok(.variable(name: x.s))
        .lparen                  => group(@p)
        .plus | .times | .rparen => fail(code: ERR_EXPECTED_FACTOR, msg: "found an operator")

# An expression followed by its closing paren.
function group(@p: Parse) -> Expr?
    inner = expression(@p)?

    if p.parse_at_end()
        return fail(code: ERR_UNCLOSED_PAREN, msg: "missing closing paren")

    if p.parse_here() != .rparen
        return fail(code: ERR_UNCLOSED_PAREN, msg: "missing closing paren")
    parse_advance(@p)
    return ok(inner)

# A product of one or more factors.
function term(@p: Parse) -> Expr?
    first = factor(@p)?
    children: [Expr] @= [first]

    while !p.parse_at_end() && p.parse_here() == .times
        parse_advance(@p)
        children @ children.push(factor(@p)?)

    if children.len() == 1
        return ok(first)
    return ok(.product(children: children))

# A sum of one or more terms.
function expression(@p: Parse) -> Expr?
    first = term(@p)?
    children: [Expr] @= [first]

    while !p.parse_at_end() && p.parse_here() == .plus
        parse_advance(@p)
        children @ children.push(term(@p)?)

    if children.len() == 1
        return ok(first)
    return ok(.sum(children: children))

# The calculator — design.md's appendix program, and M-generics-library's acceptance criterion:
# it compiles, it runs, its tests pass.
#
# One difference from the appendix, and it is deliberate on both sides. There the
# `simplify` function is a `???` under a "## To do" heading, because §4.16's hole
# is a form the document has to demonstrate somewhere. Here it is written, because
# a program with a hole produces no binary by design and this one has to run.
# Everything else is the appendix verbatim; `resolve/tests/acceptance.rs` and
# `types/tests/acceptance.rs` still read design.md's copy, so the two are checked
# by different things and neither is a copy nobody looks at.
#
# What it exercises: a recursive variant through `[Expr]`, a hand-written
# tokeniser and recursive-descent parser, `T?` with `?` propagation, a map as an
# environment, a user-declared generic, and seven `test` blocks.

## Calculator
#
# **Lexer**, **parser** and **evaluator** for arithmetic expressions
# with variables. A compiler in miniature.
#
# Grammar, increasing precedence:
#
#     expression := term ('+' term)*
#     term       := factor ('*' factor)*
#     factor     := number | name | '(' expression ')'

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_EXPECTED_FACTOR: str
    "expected_factor"

constant ERR_TRAILING_TOKENS: str
    "trailing_tokens"

constant ERR_UNCLOSED_PAREN: str
    "unclosed_paren"

constant ERR_UNEXPECTED_END: str
    "unexpected_end"

constant ERR_UNKNOWN_CHAR: str
    "unknown_char"

constant ERR_UNKNOWN_NAME: str
    "unknown_name"

## Generic library

# Applies `f` to every element, in order. Named `apply` rather than `map`
# because `map` is a built-in name and no file may redeclare one (panel 015);
# the point here is generics, and any name demonstrates them.
function apply<A, B>(xs: [A], f: (function(A) -> B)) -> [B]
    out: [B] @= []

    for x in xs
        out @ out.push(f(x))

    return out

# Reduces the sequence to one value, from the left. `fold` is a built-in name
# too, so this one is `reduce`.
function reduce<A, B>(xs: [A], initial: B, f: (function(B, A) -> B)) -> B
    acc: B @= initial

    for x in xs
        acc @ f(acc, x)

    return acc

function plus(a: i64, b: i64) -> i64
    return a + b

test "generics work across types"
    assert [1, 2, 3].apply(double) == [2, 4, 6]
    assert [1, 2, 3, 4].reduce(0, plus) == 10

function double(n: i64) -> i64
    return n * 2

## Tokens

variant Token
    num
        v: i64
    name
        s: str
    plus
    times
    lparen
    rparen

# Text and position. Travels through the lexer as `@`.
record Lex
    text: str
    pos: i64

function at_end(l: Lex) -> bool
    return l.pos >= l.text.len()

function here(l: Lex) -> u8
    return l.text[l.pos]

function advance(@l: Lex)
    l.pos @ l.pos + 1

function is_digit(c: u8) -> bool
    return c >= '0' && c <= '9'

function is_letter(c: u8) -> bool
    return c >= 'a' && c <= 'z'

# Reads an integer, consuming it.
function read_number(@l: Lex) -> i64
    v: i64 @= 0

    while !l.at_end() && l.here().is_digit()
        v @ v * 10 + to_i64(l.here() - '0').must()
        advance(@l)

    return v

# Reads an identifier, consuming it.
function read_name(@l: Lex) -> str
    start = l.pos

    while !l.at_end() && l.here().is_letter()
        advance(@l)

    return l.text.slice(from: start, to: l.pos)

# Splits the text into tokens. Fails on the first unknown character.
function tokenize(text: str) -> [Token]?
    l: Lex @= Lex(text: text, pos: 0)
    out: [Token] @= []

    while !l.at_end()
        c = l.here()

        if c == ' '
            advance(@l)
        else if c.is_digit()
            out @ out.push(.num(v: read_number(@l)))
        else if c.is_letter()
            out @ out.push(.name(s: read_name(@l)))
        else if c == '+'
            out @ out.push(.plus)
            advance(@l)
        else if c == '*'
            out @ out.push(.times)
            advance(@l)
        else if c == '('
            out @ out.push(.lparen)
            advance(@l)
        else if c == ')'
            out @ out.push(.rparen)
            advance(@l)
        else
            return fail(code: ERR_UNKNOWN_CHAR, msg: "at position " + l.pos.to_str())

    return ok(out)

test "tokenizes numbers, names and symbols"
    ts = tokenize("12 + xy * (3)").must()
    assert ts.len() == 7
    assert ts[0] == .num(v: 12)
    assert ts[1] == .plus
    assert ts[2] == .name(s: "xy")

test "tokenize rejects the unknown"
    match tokenize("2 $ 3")
        .ok _  => assert false
        .err e => assert e.code == ERR_UNKNOWN_CHAR

## Syntax tree

# A tree node. Children live in an array, which is the language's
# only indirection: that is what makes the recursive type finite.
variant Expr
    num
        v: i64
    variable
        name: str
    sum
        children: [Expr]
    product
        children: [Expr]

# Tokens and position. Travels through the parser as `@`.
record Parse
    ts: [Token]
    pos: i64

function parse_at_end(p: Parse) -> bool
    return p.pos >= p.ts.len()

function parse_here(p: Parse) -> Token
    return p.ts[p.pos]

function parse_advance(@p: Parse)
    p.pos @ p.pos + 1

## Parser
#
# Recursive descent. The four functions call each other; declaration
# order does not matter, so mutual recursion needs no forward
# declarations.

# A number, a name, or a parenthesised expression.
function factor(@p: Parse) -> Expr?
    if p.parse_at_end()
        return fail(code: ERR_UNEXPECTED_END, msg: "the expression ends too soon")

    t = p.parse_here()
    parse_advance(@p)

    return match t
        .num n                   => ok(.num(v: n.v))
        .name x                  => ok(.variable(name: x.s))
        .lparen                  => group(@p)
        .plus | .times | .rparen => fail(code: ERR_EXPECTED_FACTOR, msg: "found an operator")

# An expression followed by its closing paren.
function group(@p: Parse) -> Expr?
    inner = expression(@p)?

    if p.parse_at_end()
        return fail(code: ERR_UNCLOSED_PAREN, msg: "missing closing paren")

    if p.parse_here() != .rparen
        return fail(code: ERR_UNCLOSED_PAREN, msg: "missing closing paren")
    parse_advance(@p)
    return ok(inner)

# A product of one or more factors.
function term(@p: Parse) -> Expr?
    first = factor(@p)?
    children: [Expr] @= [first]

    while !p.parse_at_end() && p.parse_here() == .times
        parse_advance(@p)
        children @ children.push(factor(@p)?)

    if children.len() == 1
        return ok(first)
    return ok(.product(children: children))

# A sum of one or more terms.
function expression(@p: Parse) -> Expr?
    first = term(@p)?
    children: [Expr] @= [first]

    while !p.parse_at_end() && p.parse_here() == .plus
        parse_advance(@p)
        children @ children.push(term(@p)?)

    if children.len() == 1
        return ok(first)
    return ok(.sum(children: children))

## Evaluator

# The value bound to a name, with a decent message if absent.
function lookup(env: {str: i64}, name: str) -> i64?
    if env[name].is_err()
        return fail(code: ERR_UNKNOWN_NAME, msg: "undefined variable: " + name)
    return ok(env[name].must())

function sum_of(children: [Expr], env: {str: i64}) -> i64?
    tot: i64 @= 0

    for c in children
        tot @ tot + evaluate(c, env)?

    return ok(tot)

function product_of(children: [Expr], env: {str: i64}) -> i64?
    tot: i64 @= 1

    for c in children
        tot @ tot * evaluate(c, env)?

    return ok(tot)

# The value of the tree. Fails on the first unknown name.
function evaluate(e: Expr, env: {str: i64}) -> i64?
    return match e
        .num n      => ok(n.v)
        .variable x => env.lookup(x.name)
        .sum s      => s.children.sum_of(env)
        .product q  => q.children.product_of(env)

# Every name appearing in the tree, with repetitions.
function names_used(e: Expr) -> [str]
    return match e
        .num _      => []
        .variable x => [x.name]
        .sum s      => names_of(s.children)
        .product q  => names_of(q.children)

function names_of(children: [Expr]) -> [str]
    out: [str] @= []

    for c in children
        for n in c.names_used()
            out @ out.push(n)

    return out

## Interface

# From text to result, in one call.
function calculate(text: str, env: {str: i64}) -> i64?
    ts = tokenize(text)?
    p: Parse @= Parse(ts: ts, pos: 0)
    tree = expression(@p)?

    if !p.parse_at_end()
        return fail(code: ERR_TRAILING_TOKENS, msg: "leftover input at the end")
    return evaluate(tree, env)

test "precedence and parens"
    empty: {str: i64} = {}
    assert calculate("2 + 3 * 4", empty).must() == 14
    assert calculate("(2 + 3) * 4", empty).must() == 20
    assert calculate("2 * 3 * 4", empty).must() == 24

test "variables from the environment"
    env = {"x": 10, "y": 4}
    assert calculate("x * y + 2", env).must() == 42

test "errors reach the top"
    empty: {str: i64} = {}

    match calculate("2 +", empty)
        .ok _  => assert false
        .err e => assert e.code == ERR_UNEXPECTED_END

    match calculate("z + 1", empty)
        .ok _  => assert false
        .err e => assert e.code == ERR_UNKNOWN_NAME

    match calculate("(2 + 3", empty)
        .ok _  => assert false
        .err e => assert e.code == ERR_UNCLOSED_PAREN

test "values are always copies"
    a = [1, 2, 3]
    b: [i64] @= a
    b @ b.push(4)
    assert a.len() == 3
    assert b.len() == 4

# Simplify the tree: `x * 1` becomes `x`, `x + 0` becomes `x`.
#
# Bottom-up: every child is simplified before the node itself, so
# `(x + 0) * 1` collapses in one pass. A node whose children all vanish
# collapses to the identity it was built around — an empty `sum` is 0 and an
# empty `product` is 1, which is the same rule `sum_of` and `product_of` use for
# an empty list.
function simplify(e: Expr) -> Expr
    return match e
        .num _      => e
        .variable _ => e
        .sum s      => rebuild(kept: keep_sum(s.children), zero: true)
        .product q  => rebuild(kept: keep_product(q.children), zero: false)

# The children of a sum that survive: each simplified, and the literal zeroes
# dropped because adding one changes nothing.
function keep_sum(children: [Expr]) -> [Expr]
    out: [Expr] @= []

    for child in children
        one = simplify(child)

        if !is_literal(e: one, v: 0)
            out @ out.push(one)

    return out

# The same for a product, dropping the ones.
function keep_product(children: [Expr]) -> [Expr]
    out: [Expr] @= []

    for child in children
        one = simplify(child)

        if !is_literal(e: one, v: 1)
            out @ out.push(one)

    return out

# Is this node exactly the literal `v`?
function is_literal(e: Expr, v: i64) -> bool
    return match e
        .num n      => n.v == v
        .variable _ => false
        .sum _      => false
        .product _  => false

# One child left is that child; none left is the operation's identity.
function rebuild(kept: [Expr], zero: bool) -> Expr
    if kept.len() == 1
        return kept[0]

    if kept.len() == 0
        if zero
            return .num(v: 0)
        return .num(v: 1)

    if zero
        return .sum(children: kept)
    return .product(children: kept)

## Program

function main()
    env = {"x": 10, "y": 4}

    cases = [
        "2 + 3 * 4"
        "(2 + 3) * 4"
        "x * y + 2"
        "z + 1"
        "2 +"
    ]

    for c in cases
        match calculate(c, env)
            .ok v  => print(c, " = ", v)
            .err e => print(c, " -> ", e.code, ": ", e.msg)