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

tomsemble's solution

to Forth in the Python Track

Published at Apr 07 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()
class StackUnderflowError(Exception):
    pass


def evaluate(input_data):
    operations = ["+","-","*","/","DUP","DROP","SWAP","OVER"]
    dict_ = {}
    for i in range(len(input_data)):
        for i2 in range(len(input_data)):
            input_list = input_data[i2].split()
            for item in input_list[2:-1]:
                if i2 != len(input_data)-1:
                    if item.upper() in dict_.keys(): 
                        a = input_data[i2].split()
                        b = "".join([" "+i for i in a[:2]])
                        c = "".join([" "+i for i in a[2:]])
                        c = c.replace(item, dict_[item.upper()])
                        input_data[i2] = b+c
        
        input_list = input_data[i].split()
        if input_list[0] == ":":
            input_2 = (input_data[i].replace(": "+input_list[1]+" ", "")).replace(" ;","")
            dict_[input_list[1].upper()] = input_2.upper()
            try:
                int(input_list[1])
            except: pass
            else: raise ValueError("cannot_redefine_numbers")
            print(dict_)
            continue
        
        if i == len(input_data)-1:
            input_list2 = input_data[i2].split()
            for item in input_list:
                if item.upper() in dict_.keys(): input_data[i] = input_data[i].replace(item, dict_[item.upper()])

            stack = []
            input_list = input_data[i].split()
            for item in input_list:
                if item.upper() not in operations and item.upper() not in dict_.keys():
                        stack.append(int(item))
                else:
                    #if item.upper() in dict_.keys(): item = dict_[item.upper()]
                    if len(stack) == 0: raise StackUnderflowError("cannot operate on a blank stack")
                    if len(stack) == 1 and (item.upper() not in operations[4:6]): raise StackUnderflowError("stack size insufficient for this operation")
                    if item == "+":
                        stack = [stack[-2] + stack[-1]]
                    if item == "*":
                        stack = [stack[-2] * stack[-1]]
                    if item == "-":
                        stack = [stack[-2] - stack[-1]]
                    if item == "/":
                        if stack[-1] == 0: raise ZeroDivisionError("divide by 0 illegal")
                        stack = [int(stack[-2] / stack[-1])]
                    if item.upper() == "DUP":
                        stack.append(stack[-1])
                    if item.upper() == "DROP":
                        stack = stack[:-1]
                    if item.upper() == "OVER":
                        stack.append(stack[-2])
                    if item.upper() == "SWAP":
                        stack = stack[:-2]+stack[-2:][::-1]
        return stack

a = evaluate([": foo 10 ;", ": foo foo 1 + ;", "foo"])
print(a)

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?