ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# yamakanto's solution

## to Forth in the Python Track

Published at Sep 02 2020 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

Implement an evaluator for a very simple subset of Forth.

Forth is a stack-based programming language. Implement a very basic evaluator for a small subset of Forth.

Your evaluator has to support the following words:

• `+`, `-`, `*`, `/` (integer arithmetic)
• `DUP`, `DROP`, `SWAP`, `OVER` (stack manipulation)

Your evaluator also has to support defining new words using the customary syntax: `: word-name definition ;`.

To keep things simple the only data type you need to support is signed integers of at least 16 bits size.

You should use the following rules for the syntax: a number is a sequence of one or more (ASCII) digits, a word is a sequence of one or more letters, digits, symbols or punctuation that is not a number. (Forth probably uses slightly different rules, but this is close enough.)

Words are case-insensitive.

## Exception messages

Sometimes it is necessary to raise an exception. When you do this, you should include a meaningful error message to indicate what the source of the error is. This makes your code more readable and helps significantly with debugging. Not every exercise will require you to raise an exception, but for those that do, the tests will only pass if you include a message.

To raise a message with an exception, just write it as an argument to the exception type. For example, instead of `raise Exception`, you should write:

``````raise Exception("Meaningful message indicating the source of the error")
``````

## Running the tests

To run the tests, run `pytest forth_test.py`

Alternatively, you can tell Python to run the pytest module: `python -m pytest forth_test.py`

### Common `pytest` options

• `-v` : enable verbose output
• `-x` : stop running tests on first failure
• `--ff` : run failures from previous test before running other test cases

For other options, see `python -m pytest -h`

## Submitting Exercises

Note that, when trying to submit an exercise, make sure the solution is in the `\$EXERCISM_WORKSPACE/python/forth` directory.

You can find your Exercism workspace by running `exercism debug` and looking for the line that starts with `Workspace`.

For more detailed information about running tests, code style and linting, please see Running the Tests.

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### forth_test.py

``````import unittest

from forth import evaluate, StackUnderflowError

# Tests adapted from `problem-specifications//canonical-data.json` @ v1.7.1

class ForthTest(unittest.TestCase):
# Utility functions
def assertRaisesWithMessage(self, exception):
return self.assertRaisesRegex(exception, r".+")

class ParsingAndNumbersTest(ForthTest):
def test_numbers_just_get_pushed_onto_the_stack(self):
self.assertEqual(evaluate(["1 2 3 4 5"]), [1, 2, 3, 4, 5])

self.assertEqual(evaluate(["1 2 +"]), [3])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["+"])

def test_errors_if_there_is_only_one_value_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["1 +"])

class SubtractionTest(ForthTest):
def test_can_subtract_two_numbers(self):
self.assertEqual(evaluate(["3 4 -"]), [-1])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["-"])

def test_errors_if_there_is_only_one_value_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["1 -"])

class MultiplicationTest(ForthTest):
def test_can_multiply_two_numbers(self):
self.assertEqual(evaluate(["2 4 *"]), [8])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["*"])

def test_errors_if_there_is_only_one_value_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["1 *"])

class DivisionTest(ForthTest):
def test_can_divide_two_numbers(self):
self.assertEqual(evaluate(["12 3 /"]), [4])

def test_performs_integer_division(self):
self.assertEqual(evaluate(["8 3 /"]), [2])

def test_errors_if_dividing_by_zero(self):
# divide by zero
with self.assertRaisesWithMessage(ZeroDivisionError):
evaluate(["4 0 /"])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["/"])

def test_errors_if_there_is_only_one_value_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["1 /"])

class CombinedArithmeticTest(ForthTest):
self.assertEqual(evaluate(["1 2 + 4 -"]), [-1])

def test_multiplication_and_division(self):
self.assertEqual(evaluate(["2 4 * 3 /"]), [2])

class DupTest(ForthTest):
def test_copies_a_value_on_the_stack(self):
self.assertEqual(evaluate(["1 dup"]), [1, 1])

def test_copies_the_top_value_on_the_stack(self):
self.assertEqual(evaluate(["1 2 dup"]), [1, 2, 2])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["dup"])

class DropTest(ForthTest):
def test_removes_the_top_value_on_the_stack_if_it_is_the_only_one(self):
self.assertEqual(evaluate(["1 drop"]), [])

def test_removes_the_top_value_on_the_stack_if_it_is_not_the_only_one(self):
self.assertEqual(evaluate(["1 2 drop"]), [1])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["drop"])

class SwapTest(ForthTest):
def test_swaps_the_top_two_values_on_the_stack_if_they_are_the_only_ones(self):
self.assertEqual(evaluate(["1 2 swap"]), [2, 1])

def test_swaps_the_top_two_values_on_the_stack_if_they_are_not_the_only_ones(self):
self.assertEqual(evaluate(["1 2 3 swap"]), [1, 3, 2])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["swap"])

def test_errors_if_there_is_only_one_value_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["1 swap"])

class OverTest(ForthTest):
def test_copies_the_second_element_if_there_are_only_two(self):
self.assertEqual(evaluate(["1 2 over"]), [1, 2, 1])

def test_copies_the_second_element_if_there_are_more_than_two(self):
self.assertEqual(evaluate(["1 2 3 over"]), [1, 2, 3, 2])

def test_errors_if_there_is_nothing_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["over"])

def test_errors_if_there_is_only_one_value_on_the_stack(self):
with self.assertRaisesWithMessage(StackUnderflowError):
evaluate(["1 over"])

class UserDefinedWordsTest(ForthTest):
def test_can_consist_of_built_in_words(self):
self.assertEqual(evaluate([": dup-twice dup dup ;", "1 dup-twice"]), [1, 1, 1])

def test_execute_in_the_right_order(self):
self.assertEqual(evaluate([": countup 1 2 3 ;", "countup"]), [1, 2, 3])

def test_can_override_other_user_defined_words(self):
self.assertEqual(
evaluate([": foo dup ;", ": foo dup dup ;", "1 foo"]), [1, 1, 1]
)

def test_can_override_built_in_words(self):
self.assertEqual(evaluate([": swap dup ;", "1 swap"]), [1, 1])

def test_can_override_built_in_operators(self):
self.assertEqual(evaluate([": + * ;", "3 4 +"]), [12])

def test_can_use_different_words_with_the_same_name(self):
self.assertEqual(
evaluate([": foo 5 ;", ": bar foo ;", ": foo 6 ;", "bar foo"]), [5, 6]
)

def test_can_define_word_that_uses_word_with_the_same_name(self):
self.assertEqual(evaluate([": foo 10 ;", ": foo foo 1 + ;", "foo"]), [11])

def test_cannot_redefine_numbers(self):
with self.assertRaisesWithMessage(ValueError):
evaluate([": 1 2 ;"])

def test_errors_if_executing_a_non_existent_word(self):
with self.assertRaisesWithMessage(ValueError):
evaluate(["foo"])

class CaseInsensitivityTest(ForthTest):
def test_dup_is_case_insensitive(self):
self.assertEqual(evaluate(["1 DUP Dup dup"]), [1, 1, 1, 1])

def test_drop_is_case_insensitive(self):
self.assertEqual(evaluate(["1 2 3 4 DROP Drop drop"]), [1])

def test_swap_is_case_insensitive(self):
self.assertEqual(evaluate(["1 2 SWAP 3 Swap 4 swap"]), [2, 3, 4, 1])

def test_over_is_case_insensitive(self):
self.assertEqual(evaluate(["1 2 OVER Over over"]), [1, 2, 1, 2, 1])

def test_user_defined_words_are_case_insensitive(self):
self.assertEqual(evaluate([": foo dup ;", "1 FOO Foo foo"]), [1, 1, 1, 1])

def test_definitions_are_case_insensitive(self):
self.assertEqual(evaluate([": SWAP DUP Dup dup ;", "1 swap"]), [1, 1, 1, 1])

# Utility functions
def assertRaisesWithMessage(self, exception):
return self.assertRaisesRegex(exception, r".+")

if __name__ == "__main__":
unittest.main()``````
``````class StackUnderflowError(Exception):
def __init__(self, message=''):
super().__init__(message)

def evaluate(input_data, definitions=None, stack=None):
def parse(data):
res_list = []
for d in data:
res_list.append(definitions.get(d, [d]))
return [item for sublist in res_list for item in sublist]

if stack is None:
stack = []
if definitions is None:
definitions = {}
for line in input_data:
if line[:2] == ': ' and line[-2:] == ' ;':
words = line[2:-2].split(' ')
if words[0].isnumeric():
raise ValueError('Numbers can not be redefined.')
definitions[words[0].lower()] = parse(words[1:])
continue

args = line.split(' ')
for arg in args:
arg = arg.lower()
if arg in definitions:
stack = evaluate([' '.join(definitions[arg])], definitions, stack)
elif arg.isnumeric():
stack.append(int(arg))
elif arg == '+':
if len(stack) < 2:
raise StackUnderflowError('Stack must contain two values to perform addition.')
stack.append(stack.pop() + stack.pop())
elif arg == '-':
if len(stack) < 2:
raise StackUnderflowError('Stack must contain two values to perform subtraction.')
a = stack.pop()
b = stack.pop()
stack.append(b - a)
elif arg == '*':
if len(stack) < 2:
raise StackUnderflowError('Stack must contain two values to perform multiplication.')
stack.append(stack.pop() * stack.pop())
elif arg == '/':
if len(stack) < 2:
raise StackUnderflowError('Stack must contain two values to perform subtraction.')
a = stack.pop()
b = stack.pop()
stack.append(b // a)
elif arg == 'drop':
if stack:
stack.pop()
else:
raise StackUnderflowError('Empty stack.')
elif arg == 'dup':
if stack:
stack.append(stack[-1])
else:
raise StackUnderflowError('Empty stack.')
elif arg == 'over':
if len(stack) >= 2:
stack.append(stack[-2])
else:
raise StackUnderflowError('Stack does not contain the 2 elements needed for over.')
elif arg == 'swap':
if len(stack) >= 2:
stack[-1], stack[-2] = stack[-2], stack[-1]
else:
raise StackUnderflowError('Stack does not contain the 2 elements needed for swap.')
else:
raise ValueError(f'Argument \'{arg}\' not recognized')
return stack``````