🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of mandos9

mandos9's solution

to Forth in the Python Track

Published at Apr 17 2021 · 0 comments
Instructions
Test suite
Solution

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`


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])


class AdditionTest(ForthTest):
    def test_can_add_two_numbers(self):
        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):
    def test_addition_and_subtraction(self):
        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()
import re


OPERATION = re.compile(r"\d{1,}|[\+,\*,\-,\/]|dup|drop|swap|over")
NAMEDEF = re.compile(r": (\w+|\+|\*|\-|\/) (.+) ;")


class StackUnderflowError(Exception):
    pass


def dup(stack):
    try:
        a = stack.pop()
    except IndexError:
        raise StackUnderflowError("not enough input data for duplication.")
    stack.extend([a, a])


def drop(stack):
    try:
        stack.pop()
    except IndexError:
        raise StackUnderflowError("not enough elements to drop.")


def swap(stack):
    try:
        b = stack.pop()
        a = stack.pop()
    except IndexError:
        raise StackUnderflowError("not enough elements to swap")
    stack.extend([b, a])


def over(stack):
    try: 
        a = stack.pop()
        b = stack.pop()
    except IndexError:
        raise StackUnderflowError("not enought elements to go over")
    stack.extend([b, a, b])


def add(stack):
    try:
        b = stack.pop()
        a = stack.pop()
    except IndexError:
        raise StackUnderflowError("not enough elements to add")
    stack.append(a + b)


def mul(stack):
    try:
        b = stack.pop()
        a = stack.pop()
    except IndexError:
        raise StackUnderflowError("not enough elements to multiply")
    stack.append(a * b)


def sub(stack):
    try:
        b = stack.pop()
        a = stack.pop()
    except IndexError:
        raise StackUnderflowError("not enough elements to subtract")
    stack.append(a - b)


def floordiv(stack):
    try:
        b = stack.pop()
        a = stack.pop()
    except IndexError:
        raise StackUnderflowError("not enough elements to divide")
    stack.append(a // b)


OPERATIONS = {
    '+': add,
    '*': mul,
    '-': sub,
    '/': floordiv,
}
KEYWORDS = {
    'dup': dup,
    'drop': drop,
    'swap': swap,
    'over': over,
}

def clean(command):
    if '-' in command and ' -' not in command and len(command) > 1:
        return command.replace('-', '_')
    return ''.join(letter.lower() if letter != '-' else letter
                   for letter in command)


def evaluate(input_data):
    stack = []
    if not input_data:
        return stack
    input_data = [clean(command) for command in input_data]
    
    namespace = {}
    for datum in input_data:
        names = NAMEDEF.match(datum)
        if names:
            name, value = names.groups()
            if name.isdigit():
                raise ValueError("Cannot create a number as a variable name")
            if name in namespace:
                for nm, val in namespace.items():
                    if nm == name:
                        continue
                    namespace[nm] = val.replace(name, namespace[name])
                namespace[name] = value.replace(name, namespace[name])
            else:
                namespace[name] = value
            continue
        for name, val in namespace.items():
            datum = datum.replace(name, val)

        matches = OPERATION.findall(datum)
        if not matches and not names:
            raise ValueError("Variable is not defined")
        elif not matches:
            raise StackUnderflowError('input data is invalid')
        
        for elem in matches:
            if elem in OPERATIONS:
                OPERATIONS[elem](stack)
            elif elem in KEYWORDS:
                KEYWORDS[elem](stack)
            else:
               stack.append(int(elem))
    return stack

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?