forth-kata-cpp

Forth Kata

Instructions

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.

Reference

Forth runs on an imaginary machine having only a stack (virtually infinite) of values. All instructions modify this stack in a way. Some instructions require the stack to have at least a certain amount of values.

Numbers

Minimum required values on the stack: 0

Numbers just push the given value on the stack.

23   // Stack is [23]
42   // Stack is [42, 23]
1337 // Stack is [1337, 42, 23]

+, -, *, /

Minimum required values on the stack: 2

The arithmetic instructions all take the top 2 values from the stack, calculate the result, and then put the result on the stack.

Example:

23 // Stack is [23]
42 // Stack is [42, 23]
+  // Stack is [65]

For - and / the order is relevant.

23 // Stack is [23]
42 // Stack is [42, 23]
-  // Stack is [19]

4  // Stack is [4, 19]
64 // Stack is [64, 4, 19]
/  // Stack is [16, 19]

DUP - Duplicate the top value on the stack

Minimum required values on the stack: 1

1337 // Stack is [1337]
DUP  // Stack is [1337, 1337]

DROP - Remove the top value from the stack

Minimum required values on the stack: 1

1337 // Stack is [1337]
DROP // Stack is []

SWAP - Swap the two top values on the stack

Minimum required values on the stack: 2

23   // Stack is [23]
42   // Stack is [42, 23]
SWAP // Stack is [23, 42]

OVER - Duplicate the second to top value on the stack

Minimum required values on the stack: 2

23   // Stack is [23]
42   // Stack is [42, 23]
OVER // Stack is [23, 42, 23]