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.
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
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
.
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
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
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
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
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.
Community comments
I really liked solving this one! ðŸ¥³