Avatar of murdho

murdho's solution

to Forth in the Crystal Track

Published at Feb 23 2019 · 1 comment
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.

Setup

Follow the setup instructions for Crystal here:

http://exercism.io/languages/crystal

More help installing can be found here:

http://crystal-lang.org/docs/installation/index.html

Making the Test Suit Pass

Execute the tests with:

$ crystal spec

In each test suite all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by changing pending to it.

Submitting Incomplete Solutions

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

forth_spec.cr

require "spec"
require "../src/*"

describe "Forth" do
  it "numbers just get pushed onto the stack" do
    Forth.evaluate("1 2 3 4 5").should eq([1, 2, 3, 4, 5])
  end

  pending "can add two numbers" do
    Forth.evaluate("1 2 +").should eq([3])
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("+")
    end
  end

  pending "errors if there is only one value on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("1 +")
    end
  end

  pending "can subtract two numbers" do
    Forth.evaluate("3 4 -").should eq([-1])
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("-")
    end
  end

  pending "errors if there is only one value on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("1 -")
    end
  end

  pending "can multiply two numbers" do
    Forth.evaluate("2 4 *").should eq([8])
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("*")
    end
  end

  pending "errors if there is only one value on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("1 *")
    end
  end

  pending "can divide two numbers" do
    Forth.evaluate("12 3 /").should eq([4])
  end

  pending "performs integer division" do
    Forth.evaluate("8 3 /").should eq([2])
  end

  pending "errors if dividing by zero" do
    expect_raises(Exception) do
      Forth.evaluate("4 0 /")
    end
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("/")
    end
  end

  pending "errors if there is only one value on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("1 /")
    end
  end

  pending "addition and subtraction" do
    Forth.evaluate("1 2 + 4 -").should eq([-1])
  end

  pending "multiplication and division" do
    Forth.evaluate("2 4 * 3 /").should eq([2])
  end

  pending "copies a value on the stack" do
    Forth.evaluate("1 dup").should eq([1, 1])
  end

  pending "copies the top value on the stack" do
    Forth.evaluate("1 2 dup").should eq([1, 2, 2])
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("dup")
    end
  end

  pending "removes the top value on the stack if it is the only one" do
    Forth.evaluate("1 drop").should eq([] of Int32)
  end

  pending "removes the top value on the stack if it is not the only one" do
    Forth.evaluate("1 2 drop").should eq([1])
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("drop")
    end
  end

  pending "swaps the top two values on the stack if they are the only ones" do
    Forth.evaluate("1 2 swap").should eq([2, 1])
  end

  pending "swaps the top two values on the stack if they are not the only ones" do
    Forth.evaluate("1 2 3 swap").should eq([1, 3, 2])
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("swap")
    end
  end

  pending "errors if there is only one value on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("1 swap")
    end
  end

  pending "copies the second element if there are only two" do
    Forth.evaluate("1 2 over").should eq([1, 2, 1])
  end

  pending "copies the second element if there are more than two" do
    Forth.evaluate("1 2 3 over").should eq([1, 2, 3, 2])
  end

  pending "errors if there is nothing on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("over")
    end
  end

  pending "errors if there is only one value on the stack" do
    expect_raises(Exception) do
      Forth.evaluate("1 over")
    end
  end

  pending "can consist of built-in words" do
    Forth.evaluate(": dup-twice dup dup ;1 dup-twice").should eq([1, 1, 1])
  end

  pending "execute in the right order" do
    Forth.evaluate(": countup 1 2 3 ;countup").should eq([1, 2, 3])
  end

  pending "can override other user-defined words" do
    Forth.evaluate(": foo dup ;: foo dup dup ;1 foo").should eq([1, 1, 1])
  end

  pending "can override built-in words" do
    Forth.evaluate(": swap dup ;1 swap").should eq([1, 1])
  end

  pending "can override built-in operators" do
    Forth.evaluate(": + * ;3 4 +").should eq([12])
  end

  pending "cannot redefine numbers" do
    expect_raises(Exception) do
      Forth.evaluate(": 1 2 ;")
    end
  end

  pending "errors if executing a non-existent word" do
    expect_raises(Exception) do
      Forth.evaluate("foo")
    end
  end

  pending "DUP is case-insensitive" do
    Forth.evaluate("1 DUP Dup dup").should eq([1, 1, 1, 1])
  end

  pending "DROP is case-insensitive" do
    Forth.evaluate("1 2 3 4 DROP Drop drop").should eq([1])
  end

  pending "SWAP is case-insensitive" do
    Forth.evaluate("1 2 SWAP 3 Swap 4 swap").should eq([2, 3, 4, 1])
  end

  pending "OVER is case-insensitive" do
    Forth.evaluate("1 2 OVER Over over").should eq([1, 2, 1, 2, 1])
  end

  pending "user-defined words are case-insensitive" do
    Forth.evaluate(": foo dup ;1 FOO Foo foo").should eq([1, 1, 1, 1])
  end

  pending "definitions are case-insensitive" do
    Forth.evaluate(": SWAP DUP Dup dup ;1 swap").should eq([1, 1, 1, 1])
  end
end

src/forth.cr

require "string_scanner"
require "./stack"

class Forth
  PARSING_ITER_LIMIT = 1000
  ASSIGNMENT_REGEX   = /\:(.*?)\;/
  NON_WORD_REGEX     = /\s|$/
  NUMBER_REGEX       = /^\d+$/

  getter stack = Stack.new
  getter assignments = {} of String => Array(String)

  def self.evaluate(instructions : String)
    new(instructions).evaluate
  end

  def initialize(@instructions : String); end

  def evaluate
    scanner = StringScanner.new(@instructions)

    PARSING_ITER_LIMIT.times do |i|
      break if scanner.eos?

      if assignment = scanner.scan(ASSIGNMENT_REGEX)
        process_assignment(assignment)
        next
      end

      word = scanner.scan_until(NON_WORD_REGEX)

      if word
        process_word(word.strip)
      else
        raise "Unexpected Nil word occurred"
      end

      raise "Parsing reached a hard limit" if i + 1 == PARSING_ITER_LIMIT
    end

    stack.to_a
  end

  def process_assignment(assignment)
    re_match = assignment.match(ASSIGNMENT_REGEX)
    unless re_match && re_match[1]?
      raise "Assigment failure, invalid format: #{assignment}"
    end

    pieces = re_match[1].strip.split(" ")

    name = pieces[0].downcase
    if name =~ NUMBER_REGEX
      raise "Assignment cannot redefine numbers: #{assignment}"
    end

    body = pieces[1..-1].map(&.downcase)
    assignments[name] = body
  end

  def process_word(word)
    word = word.downcase

    case word_type(word)
    when :custom
      assignments[word].each { |w| process_word(w) }
    when :numeric
      stack.push(word.to_i)
    when :add
      stack.pop_n_push(2) { |vals| vals[0] + vals[1] }
    when :subtract
      stack.pop_n_push(2) { |vals| vals[0] - vals[1] }
    when :multiply
      stack.pop_n_push(2) { |vals| vals[0] * vals[1] }
    when :divide
      stack.pop_n_push(2) { |vals| vals[0] / vals[1] }
    when :duplicate
      val = stack.pop[0]
      stack.push(val, val)
    when :drop
      stack.pop
    when :swap
      a, b = stack.pop(2)
      stack.push(b, a)
    when :over
      a, b = stack.pop(2)
      stack.push(a, b, a)
    else
      raise "Unknown word: '#{word}'"
    end
  end

  def word_type(word)
    case word
    when custom_definition
      :custom
    when NUMBER_REGEX
      :numeric
    when "+"
      :add
    when "-"
      :subtract
    when "*"
      :multiply
    when "/"
      :divide
    when "dup"
      :duplicate
    when "drop"
      :drop
    when "swap"
      :swap
    when "over"
      :over
    end
  end

  def custom_definition
    ->(word : String) { assignments.has_key?(word) }
  end
end

src/stack.cr

class Stack
  @array = [] of Int32

  def pop(n = 1)
    vals = @array.pop(n)
    raise IndexError.new if vals.size < n

    vals
  end

  def push(*vals)
    @array.push(*vals)
  end

  def pop_n_push(n = 1, &block)
    push(yield(pop(n)))
  end

  def to_a
    @array
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of murdho
Solution Author
commented 291 days ago

I really liked solving this one! 🥳

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?