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
endok parsing and numbers (2 cases)
ok addition (4 cases)
ok subtraction (4 cases)
ok multiplication (4 cases)
ok division (6 cases)
ok combined arithmetic (4 cases)
ok dup (3 cases)
ok drop (3 cases)
ok swap (4 cases)
ok over (4 cases)
ok user-defined words (10 cases)
ok user-defined words: only defines locally
ok case-insensitivity (6 cases)
test result: ok. 55 passed, 0 failed
How it’s written
Section titled “How it’s written”- 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
Opsteps (Push(n),Add,Dup, …), and the dictionary is aMap<String, List<Op>>that starts asbuiltins, 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 oldfoo. Built-in words are entries like any other, so overridingswapor+needs no special case. runwalks 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, soexecuteis a recursive function with?rather than anIter.reduce, whose state would have to be aResult.- The stack is a
List<Int>with its top first, so every built-in is one list pattern.applymatches 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 thecasecovers every step and stack. - Errors are an
Errorenum, one variant per canonical message. - A number cannot be redefined: a definition whose name
String.to_intreads isIllegalOperation.String.to_intreads-1too, 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
subteststable; 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.