Skip to content

Forth

Evaluate a small subset of Forth: integer arithmetic, DUP, DROP, SWAP and OVER, and words the program defines with : name ... ;.

Adapted from Exercism’s problem specification (MIT). Listed under Parsing & Validation.

// FILE: forth.nomi
//# An evaluator for a small subset of Forth: integer arithmetic, four stack
//# words, and words the program defines.

/// Why a program cannot run.
pub enum Error
    EmptyStack
    OnlyOneValue
    DivideByZero
    IllegalOperation
    UndefinedOperation
end

/// One step a word runs: push a number, or one of the built-in words.
enum Op
    Push Int
    Add
    Subtract
    Multiply
    Divide
    Dup
    Drop
    Swap
    Over
end

/// The words every program starts with, each the steps it runs. A program's
/// own definitions are added to these, and may replace them.
once builtins: Map<String, List<Op>> = {
    "+"    => [.Add],
    "-"    => [.Subtract],
    "*"    => [.Multiply],
    "/"    => [.Divide],
    "dup"  => [.Dup],
    "drop" => [.Drop],
    "swap" => [.Swap],
    "over" => [.Over],
}

/// The stack, bottom first, after running each line of `instructions` in
/// turn.
pub fn evaluate(instructions: List<String>) -> Result<List<Int>, Error>
    tokens =
        instructions
        |> Iter.flat_map(String.words)
        |> Iter.map(String.lowercase)
        |> Iter.to_list()

    stack = run([], builtins, tokens)?

    stack
    |> Iter.reverse()
    |> Ok()
end

/// Runs `tokens` on `stack`, top first, with the words defined so far.
fn run(
    stack:  List<Int>,
    words:  Map<String, List<Op>>,
    tokens: List<String>,
) -> Result<List<Int>, Error>
    case tokens
        [] ->
            Ok(stack)

        [":", name, ..rest] ->
            if String.to_int(name) |> Maybe.is_some() then return Err(.IllegalOperation)

            body = rest |> Iter.take_while(&(&1 != ";")) |> Iter.to_list()
            after = rest |> Iter.drop(Iter.count(body) + 1) |> Iter.to_list()

            ops =
                body
                |> Iter.map(&resolve(words, &1))
                |> Result.collect()?

            run(
                stack,
                Map.put(
                    words,
                    name,
                    ops
                    |> Iter.flatten()
                    |> Iter.to_list(),
                ),
                after,
            )

        [word, ..rest] ->
            ops = resolve(words, word)?
            stack = execute(stack, ops)?
            run(stack, words, rest)
    end
end

/// The steps `word` runs: a number pushes itself, and any other word runs
/// the steps it was defined with when it was defined.
fn resolve(words: Map<String, List<Op>>, word: String) -> Result<List<Op>, Error>
    if Some(n) = String.to_int(word) then return Ok([.Push(n)])

    Map.get(words, word) |> Maybe.to_result(.UndefinedOperation)
end

fn execute(stack: List<Int>, ops: List<Op>) -> Result<List<Int>, Error>
    case ops
        []           -> Ok(stack)
        [op, ..rest] -> execute(apply(stack, op)?, rest)
    end
end

/// `stack`, top first, after one step.
fn apply(stack: List<Int>, op: Op) -> Result<List<Int>, Error>
    case (op, stack)
        (.Push(n), _)               -> Ok([n, ..stack])
        (_, [])                     -> Err(.EmptyStack)
        (.Dup, [a, ..rest])         -> Ok([a, a, ..rest])
        (.Drop, [_, ..rest])        -> Ok(rest)
        (_, [_])                    -> Err(.OnlyOneValue)
        (.Swap, [b, a, ..rest])     -> Ok([a, b, ..rest])
        (.Over, [b, a, ..rest])     -> Ok([a, b, a, ..rest])
        (.Add, [b, a, ..rest])      -> Ok([a + b, ..rest])
        (.Subtract, [b, a, ..rest]) -> Ok([a - b, ..rest])
        (.Multiply, [b, a, ..rest]) -> Ok([a * b, ..rest])
        (.Divide, [b, a, ..rest])   -> divide(a, b) |> Result.map(&[&1, ..rest])
    end
end

/// `a / b`, or `DivideByZero` when `b` is 0.
fn divide(a: Int, b: Int) -> Result<Int, Error>
    if b == 0 then Err(.DivideByZero) else Ok(a / b)
end

// FILE: forth_test.nomi
import forth.{self, Error}

test "parsing and numbers"
    cases: List<(String, List<String>, Result<List<Int>, Error>)> = [
        ("numbers just get pushed onto the stack", ["1 2 3 4 5"],      Ok([1, 2, 3, 4, 5])),
        ("pushes negative numbers onto the stack", ["-1 -2 -3 -4 -5"], Ok([-1, -2, -3, -4, -5])),
    ]

    subtests cases, (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "addition"
    [
        ("can add two numbers",                            ["1 2 +"],   Ok([3])),
        ("errors if there is nothing on the stack",        ["+"],       Err(Error.EmptyStack)),
        ("errors if there is only one value on the stack", ["1 +"],     Err(.OnlyOneValue)),
        ("more than two values on the stack",              ["1 2 3 +"], Ok([1, 5])),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "subtraction"
    [
        ("can subtract two numbers",                       ["3 4 -"],    Ok([-1])),
        ("errors if there is nothing on the stack",        ["-"],        Err(Error.EmptyStack)),
        ("errors if there is only one value on the stack", ["1 -"],      Err(.OnlyOneValue)),
        ("more than two values on the stack",              ["1 12 3 -"], Ok([1, 9])),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "multiplication"
    [
        ("can multiply two numbers",                       ["2 4 *"],   Ok([8])),
        ("errors if there is nothing on the stack",        ["*"],       Err(Error.EmptyStack)),
        ("errors if there is only one value on the stack", ["1 *"],     Err(.OnlyOneValue)),
        ("more than two values on the stack",              ["1 2 3 *"], Ok([1, 6])),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "division"
    [
        ("can divide two numbers",                         ["12 3 /"],   Ok([4])),
        ("performs integer division",                      ["8 3 /"],    Ok([2])),
        ("errors if dividing by zero",                     ["4 0 /"],    Err(Error.DivideByZero)),
        ("errors if there is nothing on the stack",        ["/"],        Err(.EmptyStack)),
        ("errors if there is only one value on the stack", ["1 /"],      Err(.OnlyOneValue)),
        ("more than two values on the stack",              ["1 12 3 /"], Ok([1, 4])),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "combined arithmetic"
    cases: List<(String, List<String>, Result<List<Int>, Error>)> = [
        ("addition and subtraction",    ["1 2 + 4 -"], Ok([-1])),
        ("multiplication and division", ["2 4 * 3 /"], Ok([2])),
        ("multiplication and addition", ["1 3 4 * +"], Ok([13])),
        ("addition and multiplication", ["1 3 4 + *"], Ok([7])),
    ]

    subtests cases, (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "dup"
    [
        ("copies a value on the stack",             ["1 dup"],   Ok([1, 1])),
        ("copies the top value on the stack",       ["1 2 dup"], Ok([1, 2, 2])),
        ("errors if there is nothing on the stack", ["dup"],     Err(Error.EmptyStack)),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "drop"
    [
        ("removes the top value on the stack if it is the only one", ["1 drop"], Ok([])),
        ("removes the top value on the stack if it is not the only one", ["1 2 drop"], Ok([1])),
        ("errors if there is nothing on the stack", ["drop"], Err(Error.EmptyStack)),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "swap"
    [
        (
            "swaps the top two values on the stack if they are the only ones",
            ["1 2 swap"],
            Ok([2, 1]),
        ),
        (
            "swaps the top two values on the stack if they are not the only ones",
            ["1 2 3 swap"],
            Ok([1, 3, 2]),
        ),
        ("errors if there is nothing on the stack",        ["swap"],   Err(Error.EmptyStack)),
        ("errors if there is only one value on the stack", ["1 swap"], Err(.OnlyOneValue)),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "over"
    [
        ("copies the second element if there are only two", ["1 2 over"], Ok([1, 2, 1])),
        ("copies the second element if there are more than two", ["1 2 3 over"], Ok([1, 2, 3, 2])),
        ("errors if there is nothing on the stack", ["over"], Err(Error.EmptyStack)),
        ("errors if there is only one value on the stack", ["1 over"], Err(.OnlyOneValue)),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "user-defined words"
    [
        ("can consist of built-in words", [": dup-twice dup dup ;", "1 dup-twice"], Ok([1, 1, 1])),
        ("execute in the right order",    [": countup 1 2 3 ;", "countup"],         Ok([1, 2, 3])),
        (
            "can override other user-defined words",
            [": foo dup ;", ": foo dup dup ;", "1 foo"],
            Ok([1, 1, 1]),
        ),
        ("can override built-in words",     [": swap dup ;", "1 swap"], Ok([1, 1])),
        ("can override built-in operators", [": + * ;", "3 4 +"],       Ok([12])),
        (
            "can use different words with the same name",
            [": foo 5 ;", ": bar foo ;", ": foo 6 ;", "bar foo"],
            Ok([5, 6]),
        ),
        (
            "can define word that uses word with the same name",
            [": foo 10 ;", ": foo foo 1 + ;", "foo"],
            Ok([11]),
        ),
        ("cannot redefine non-negative numbers",    [": 1 2 ;"],  Err(Error.IllegalOperation)),
        ("cannot redefine negative numbers",        [": -1 2 ;"], Err(.IllegalOperation)),
        ("errors if executing a non-existent word", ["foo"],      Err(.UndefinedOperation)),
    ]
    |> subtests (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end

test "user-defined words: only defines locally"
    assert forth.evaluate([": + - ;", "1 1 +"]) == Ok([0])
    assert forth.evaluate(["1 1 +"]) == Ok([2])
end

test "case-insensitivity"
    cases: List<(String, List<String>, Result<List<Int>, Error>)> = [
        ("DUP is case-insensitive",  ["1 DUP Dup dup"],          Ok([1, 1, 1, 1])),
        ("DROP is case-insensitive", ["1 2 3 4 DROP Drop drop"], Ok([1])),
        ("SWAP is case-insensitive", ["1 2 SWAP 3 Swap 4 swap"], Ok([2, 3, 4, 1])),
        ("OVER is case-insensitive", ["1 2 OVER Over over"],     Ok([1, 2, 1, 2, 1])),
        (
            "user-defined words are case-insensitive",
            [": foo dup ;", "1 FOO Foo foo"],
            Ok([1, 1, 1, 1]),
        ),
        ("definitions are case-insensitive", [": SWAP DUP Dup dup ;", "1 swap"], Ok([1, 1, 1, 1])),
    ]

    subtests cases, (description, instructions, expected), description
        assert forth.evaluate(instructions) == expected
    end
end
  • The program is one list of lower-cased tokens, every line’s words in order, so a definition is read the same wherever it falls and case never matters again.
  • A word means a list of Op steps (Push(n), Add, Dup, …), and the dictionary is a Map<String, List<Op>> that starts as builtins, each built-in word one step. A definition resolves its body against the dictionary as it stands and stores the steps, so a later redefinition of a word it uses changes nothing, and : foo foo 1 + ; reads the old foo. Built-in words are entries like any other, so overriding swap or + needs no special case.
  • run walks the tokens with list patterns, [":", name, ..rest] for a definition and [word, ..rest] for anything else, and threads the stack and the dictionary through its own recursion. Each step can fail, so execute is a recursive function with ? rather than an Iter.reduce, whose state would have to be a Result.
  • The stack is a List<Int> with its top first, so every built-in is one list pattern. apply matches the step and the stack as a tuple, (op, stack): an empty stack and a stack of one are an arm each before the arms that need two values, and the compiler checks the case covers every step and stack.
  • Errors are an Error enum, one variant per canonical message.
  • A number cannot be redefined: a definition whose name String.to_int reads is IllegalOperation. String.to_int reads -1 too, so negative numbers push themselves, as the canonical data asks, though its prose says a number is digits only.
  • Each canonical group is a test named by the group’s description, holding one subtests table; several groups share row descriptions such as “errors if there is nothing on the stack”. “only defines locally” runs two programs, so it is a test of its own.