Forth

Forth

Hard

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.

To complete this exercise, you need to create the data type ForthState and implement the following functions:

  • emptyState returns an empty ForthState.
  • evalText evaluates an input Text, returning the new state.
  • toList returns the current stack as a list, with the element on top of the stack being the rightmost (last) element.

You will find a dummy data declaration and type signatures already in place, but it is up to you to define the functions and create a meaningful data type, newtype or type synonym.

Edit via GitHub The link opens in a new window or tab
Haskell Exercism

Ready to start Forth?

Sign up to Exercism to learn and master Haskell with 107 exercises, and real human mentoring, all for free.