Avatar of artemkorsakov

artemkorsakov's solution

to Forth in the C# Track

Published at Jun 13 2019 · 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.

Hints

  • To parse the text, you could try to use the Sprache library. You can also find a good tutorial here.

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit Forth.cs

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

ForthTest.cs

// This file was auto-generated based on version 1.7.0 of the canonical data.

using System;
using Xunit;

public class ForthTest
{
    [Fact]
    public void Parsing_and_numbers_numbers_just_get_pushed_onto_the_stack()
    {
        Assert.Equal("1 2 3 4 5", Forth.Evaluate(new[] { "1 2 3 4 5" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Addition_can_add_two_numbers()
    {
        Assert.Equal("3", Forth.Evaluate(new[] { "1 2 +" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Addition_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "+" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Addition_errors_if_there_is_only_one_value_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "1 +" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Subtraction_can_subtract_two_numbers()
    {
        Assert.Equal("-1", Forth.Evaluate(new[] { "3 4 -" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Subtraction_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "-" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Subtraction_errors_if_there_is_only_one_value_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "1 -" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Multiplication_can_multiply_two_numbers()
    {
        Assert.Equal("8", Forth.Evaluate(new[] { "2 4 *" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Multiplication_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "*" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Multiplication_errors_if_there_is_only_one_value_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "1 *" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Division_can_divide_two_numbers()
    {
        Assert.Equal("4", Forth.Evaluate(new[] { "12 3 /" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Division_performs_integer_division()
    {
        Assert.Equal("2", Forth.Evaluate(new[] { "8 3 /" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Division_errors_if_dividing_by_zero()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "4 0 /" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Division_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "/" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Division_errors_if_there_is_only_one_value_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "1 /" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Combined_arithmetic_addition_and_subtraction()
    {
        Assert.Equal("-1", Forth.Evaluate(new[] { "1 2 + 4 -" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Combined_arithmetic_multiplication_and_division()
    {
        Assert.Equal("2", Forth.Evaluate(new[] { "2 4 * 3 /" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Dup_copies_a_value_on_the_stack()
    {
        Assert.Equal("1 1", Forth.Evaluate(new[] { "1 dup" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Dup_copies_the_top_value_on_the_stack()
    {
        Assert.Equal("1 2 2", Forth.Evaluate(new[] { "1 2 dup" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Dup_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "dup" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Drop_removes_the_top_value_on_the_stack_if_it_is_the_only_one()
    {
        Assert.Equal("", Forth.Evaluate(new[] { "1 drop" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Drop_removes_the_top_value_on_the_stack_if_it_is_not_the_only_one()
    {
        Assert.Equal("1", Forth.Evaluate(new[] { "1 2 drop" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Drop_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "drop" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Swap_swaps_the_top_two_values_on_the_stack_if_they_are_the_only_ones()
    {
        Assert.Equal("2 1", Forth.Evaluate(new[] { "1 2 swap" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Swap_swaps_the_top_two_values_on_the_stack_if_they_are_not_the_only_ones()
    {
        Assert.Equal("1 3 2", Forth.Evaluate(new[] { "1 2 3 swap" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Swap_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "swap" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Swap_errors_if_there_is_only_one_value_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "1 swap" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Over_copies_the_second_element_if_there_are_only_two()
    {
        Assert.Equal("1 2 1", Forth.Evaluate(new[] { "1 2 over" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Over_copies_the_second_element_if_there_are_more_than_two()
    {
        Assert.Equal("1 2 3 2", Forth.Evaluate(new[] { "1 2 3 over" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Over_errors_if_there_is_nothing_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "over" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Over_errors_if_there_is_only_one_value_on_the_stack()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "1 over" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_can_consist_of_built_in_words()
    {
        Assert.Equal("1 1 1", Forth.Evaluate(new[] { ": dup-twice dup dup ;", "1 dup-twice" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_execute_in_the_right_order()
    {
        Assert.Equal("1 2 3", Forth.Evaluate(new[] { ": countup 1 2 3 ;", "countup" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_can_override_other_user_defined_words()
    {
        Assert.Equal("1 1 1", Forth.Evaluate(new[] { ": foo dup ;", ": foo dup dup ;", "1 foo" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_can_override_built_in_words()
    {
        Assert.Equal("1 1", Forth.Evaluate(new[] { ": swap dup ;", "1 swap" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_can_override_built_in_operators()
    {
        Assert.Equal("12", Forth.Evaluate(new[] { ": + * ;", "3 4 +" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_can_use_different_words_with_the_same_name()
    {
        Assert.Equal("5 6", Forth.Evaluate(new[] { ": foo 5 ;", ": bar foo ;", ": foo 6 ;", "bar foo" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_can_define_word_that_uses_word_with_the_same_name()
    {
        Assert.Equal("11", Forth.Evaluate(new[] { ": foo 10 ;", ": foo foo 1 + ;", "foo" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_cannot_redefine_numbers()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { ": 1 2 ;" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void User_defined_words_errors_if_executing_a_non_existent_word()
    {
        Assert.Throws<InvalidOperationException>(() => Forth.Evaluate(new[] { "foo" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Case_insensitivity_dup_is_case_insensitive()
    {
        Assert.Equal("1 1 1 1", Forth.Evaluate(new[] { "1 DUP Dup dup" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Case_insensitivity_drop_is_case_insensitive()
    {
        Assert.Equal("1", Forth.Evaluate(new[] { "1 2 3 4 DROP Drop drop" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Case_insensitivity_swap_is_case_insensitive()
    {
        Assert.Equal("2 3 4 1", Forth.Evaluate(new[] { "1 2 SWAP 3 Swap 4 swap" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Case_insensitivity_over_is_case_insensitive()
    {
        Assert.Equal("1 2 1 2 1", Forth.Evaluate(new[] { "1 2 OVER Over over" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Case_insensitivity_user_defined_words_are_case_insensitive()
    {
        Assert.Equal("1 1 1 1", Forth.Evaluate(new[] { ": foo dup ;", "1 FOO Foo foo" }));
    }

    [Fact(Skip = "Remove to run test")]
    public void Case_insensitivity_definitions_are_case_insensitive()
    {
        Assert.Equal("1 1 1 1", Forth.Evaluate(new[] { ": SWAP DUP Dup dup ;", "1 swap" }));
    }
}

Forth.cs

using System;
using System.Collections.Generic;
using System.Linq;

public static class Forth
{
    public static string Evaluate(string[] instructions)
    {
        var stack = new Stack<int>();
        var commands = new Commands();

        foreach (var instruction in instructions)
        {
            if (instruction.StartsWith(":"))
            {
                var newCommand = GetNewCommand(instruction.ToUpper());
                commands.AddCommand(newCommand);
            }
            else
            {
                stack = commands.Execute(stack, instruction.ToUpper().Split(" "));
            }
        }

        return string.Join(' ', stack.Reverse());
    }

    /**
     * ": word-name definition ;"
     */
    private static string[] GetNewCommand(string definition)
    {
        if (!definition.EndsWith(";"))
        {
            throw new InvalidOperationException($"Unknown definition - {definition}");
        }

        var members = definition.TrimStart(':').TrimEnd(';').Trim().Split(' ');
        if (members.Length < 2)
        {
            throw new InvalidOperationException($"Unknown definition - {definition}");
        }

        if (Commands.IsNumber(members[0]))
        {
            throw new InvalidOperationException("Cannot redefine numbers");
        }

        return members;
    }
}

IForthCommand.cs

using System;
using System.Collections.Generic;
using System.Linq;

internal enum ForthCommand
{
    ADD, SUB, MUL, DIV, DUP, DROP, SWAP, OVER
}

internal interface IForthCommand
{
    Stack<int> Execute(Stack<int> stack);
}

internal class NamesCommand : IForthCommand
{
    internal string[] Names { get; }

    internal NamesCommand(string[] names)
    {
        Names = names;
    }

    public Stack<int> Execute(Stack<int> stack)
    {
        throw new NotImplementedException();
    }
}

internal class ForthCommandClass : IForthCommand
{
    internal ForthCommand Forth { get; }

    internal ForthCommandClass(ForthCommand forth)
    {
        Forth = forth;
    }

    public Stack<int> Execute(Stack<int> stack)
    {
        return Commands.Execute(stack, Forth);
    }
}

internal class StackCommand : IForthCommand
{
    internal Stack<int> StackInts { get; }

    internal StackCommand(Stack<int> stackInts)
    {
        StackInts = stackInts;
    }

    public Stack<int> Execute(Stack<int> stack)
    {
        foreach (var item in StackInts.Reverse())
        {
            stack.Push(item);
        }
        return stack;
    }
}

Commands.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

public class Commands
{
    private Dictionary<string, IForthCommand> commands = new Dictionary<string, IForthCommand>
    {
        { "+", new ForthCommandClass ( ForthCommand.ADD) },
        { "-", new ForthCommandClass ( ForthCommand.SUB ) },
        { "*", new ForthCommandClass ( ForthCommand.MUL ) },
        { "/", new ForthCommandClass ( ForthCommand.DIV ) },
        { "DUP", new ForthCommandClass ( ForthCommand.DUP ) },
        { "DROP", new ForthCommandClass ( ForthCommand.DROP ) },
        { "SWAP", new ForthCommandClass ( ForthCommand.SWAP ) },
        { "OVER", new ForthCommandClass ( ForthCommand.OVER ) }
    };
    private static readonly Regex regex = new Regex("^\\d+$");

    public static bool IsNumber(string str) => regex.IsMatch(str);

    public void AddCommand(string[] members)
    {
        var commandName = members[0];
        var commandNames = members.Skip(1).ToArray();
        var stack = new Stack<int>();
        try
        {
            stack = Execute(stack, commandNames);
            commands[commandName] = new StackCommand(stack);
        }
        catch (Exception)
        {
            commands[commandName] = new NamesCommand(commandNames);
        }
    }

    public Stack<int> Execute(Stack<int> stack, string[] names)
    {
        foreach (var name in names)
        {
            stack = Execute(stack, name);
        }
        return stack;
    }

    private Stack<int> Execute(Stack<int> stack, string name)
    {
        if (IsNumber(name))
        {
            stack.Push(int.Parse(name));
            return stack;
        }

        var command = GetCommand(name);
        if (command is NamesCommand namesCommand)
        {
            return Execute(stack, namesCommand.Names);
        }
        return command.Execute(stack);
    }

    private IForthCommand GetCommand(string name)
    {
        if (commands.ContainsKey(name))
        {
            return commands[name];
        }

        throw new InvalidOperationException($"No definition available for operator \"{name}\"");
    }

    internal static Stack<int> Execute(Stack<int> stack, ForthCommand forthCommand)
    {
        switch (forthCommand)
        {
            case ForthCommand.ADD:
                return Add(stack);
            case ForthCommand.SUB:
                return Sub(stack);
            case ForthCommand.MUL:
                return Mul(stack);
            case ForthCommand.DIV:
                return Div(stack);
            case ForthCommand.DUP:
                return Dup(stack);
            case ForthCommand.DROP:
                return Drop(stack);
            case ForthCommand.SWAP:
                return Swap(stack);
            case ForthCommand.OVER:
                return Over(stack);
            default:
                throw new InvalidOperationException($"No definition available for operator \"{forthCommand}\"");
        }
    }

    private static Stack<int> Add(Stack<int> stack)
    {
        if (stack.Count < 2)
        {
            throw new InvalidOperationException("Addition requires that the stack contain at least 2 values");
        }

        var res = stack.Pop() + stack.Pop();
        stack.Push(res);
        return stack;
    }

    private static Stack<int> Sub(Stack<int> stack)
    {
        if (stack.Count < 2)
        {
            throw new InvalidOperationException("Subtraction requires that the stack contain at least 2 values");
        }

        var res = stack.Pop();
        res = stack.Pop() - res;
        stack.Push(res);
        return stack;
    }

    private static Stack<int> Mul(Stack<int> stack)
    {
        if (stack.Count < 2)
        {
            throw new InvalidOperationException("Multiplication requires that the stack contain at least 2 values");
        }

        var res = stack.Pop() * stack.Pop();
        stack.Push(res);
        return stack;
    }

    private static Stack<int> Div(Stack<int> stack)
    {
        if (stack.Count < 2)
        {
            throw new InvalidOperationException("Division requires that the stack contain at least 2 values");
        }

        var divider = stack.Pop();
        if (divider == 0)
        {
            throw new InvalidOperationException("Division by 0 is not allowed");
        }

        var res = stack.Pop() / divider;
        stack.Push(res);
        return stack;
    }

    private static Stack<int> Dup(Stack<int> stack)
    {
        if (stack.Count == 0)
        {
            throw new InvalidOperationException("Duplicating requires that the stack contain at least 1 value");
        }

        var res = stack.Peek();
        stack.Push(res);
        return stack;
    }

    private static Stack<int> Drop(Stack<int> stack)
    {
        if (stack.Count == 0)
        {
            throw new InvalidOperationException("Dropping requires that the stack contain at least 1 value");
        }

        stack.Pop();
        return stack;
    }

    private static Stack<int> Swap(Stack<int> stack)
    {
        if (stack.Count < 2)
        {
            throw new InvalidOperationException("Swapping requires that the stack contain at least 2 values");
        }

        var prev = stack.Pop();
        var prevprev = stack.Pop();
        stack.Push(prev);
        stack.Push(prevprev);
        return stack;
    }

    private static Stack<int> Over(Stack<int> stack)
    {
        if (stack.Count < 2)
        {
            throw new InvalidOperationException("Overing requires that the stack contain at least 2 values");
        }

        var prev = stack.Pop();
        var res = stack.Peek();
        stack.Push(prev);
        stack.Push(res);
        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?