# uzilan's solution

## to Forth in the Kotlin Track

Published at Oct 15 2018 · 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.

## Submitting Incomplete Solutions

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

### ForthEvaluatorTest.kt

``````import org.junit.Before
import org.junit.Ignore
import org.junit.Rule
import org.junit.Test
import org.junit.rules.ExpectedException
import kotlin.test.assertEquals

class ForthEvaluatorTest {

@Rule
@JvmField
var expectedException: ExpectedException = ExpectedException.none()

private lateinit var forthEvaluator: ForthEvaluator

@Before
fun setUp() {
forthEvaluator = ForthEvaluator()
}

@Ignore
@Test
fun testNumbersAreJustPushedOntoTheStack() {
assertEquals(
listOf(1, 2, 3, 4, 5),
forthEvaluator.evaluateProgram(listOf("1 2 3 4 5")))
}

@Ignore
@Test
assertEquals(
listOf(3),
forthEvaluator.evaluateProgram(listOf("1 2 +")))
}

@Ignore
@Test
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Addition requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("+"))
}

@Ignore
@Test
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Addition requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("1 +"))
}

@Ignore
@Test
fun testTwoNumbersCanBeSubtracted() {
assertEquals(
listOf(-1),
forthEvaluator.evaluateProgram(listOf("3 4 -")))
}

@Ignore
@Test
fun testErrorIfSubtractionAttemptedWithNothingOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Subtraction requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("-"))
}

@Ignore
@Test
fun testErrorIfSubtractionAttemptedWithOneNumberOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Subtraction requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("1 -"))
}

@Ignore
@Test
fun testTwoNumbersCanBeMultiplied() {
assertEquals(
listOf(8),
forthEvaluator.evaluateProgram(listOf("2 4 *")))
}

@Ignore
@Test
fun testErrorIfMultiplicationAttemptedWithNothingOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Multiplication requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("*"))
}

@Ignore
@Test
fun testErrorIfMultiplicationAttemptedWithOneNumberOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Multiplication requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("1 *"))
}

@Ignore
@Test
fun testTwoNumbersCanBeDivided() {
assertEquals(
listOf(4),
forthEvaluator.evaluateProgram(listOf("12 3 /")))
}

@Ignore
@Test
fun testThatIntegerDivisionIsUsed() {
assertEquals(
listOf(2),
forthEvaluator.evaluateProgram(listOf("8 3 /")))
}

@Ignore
@Test
fun testErrorIfDividingByZero() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Division by 0 is not allowed")

forthEvaluator.evaluateProgram(listOf("4 0 /"))
}

@Ignore
@Test
fun testErrorIfDivisionAttemptedWithNothingOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Division requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("/"))
}

@Ignore
@Test
fun testErrorIfDivisionAttemptedWithOneNumberOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Division requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("1 /"))
}

@Ignore
@Test
assertEquals(
listOf(-1),
forthEvaluator.evaluateProgram(listOf("1 2 + 4 -")))
}

@Ignore
@Test
fun testCombinedMultiplicationAndDivision() {
assertEquals(
listOf(2),
forthEvaluator.evaluateProgram(listOf("2 4 * 3 /")))
}

@Ignore
@Test
fun testDupCopiesTheTopValueOnTheStack() {
assertEquals(
listOf(1, 1),
forthEvaluator.evaluateProgram(listOf("1 DUP")))
}

@Ignore
@Test
fun testDupParsingIsCaseInsensitive() {
assertEquals(
listOf(1, 2, 2),
forthEvaluator.evaluateProgram(listOf("1 2 Dup")))
}

@Ignore
@Test
fun testErrorIfDuplicatingAttemptedWithNothingOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Duplicating requires that the stack contain at least 1 value")

forthEvaluator.evaluateProgram(listOf("dup"))
}

@Ignore
@Test
fun testDropRemovesTheTopValueOnTheStackIfItIsTheOnlyOne() {
assertEquals(
emptyList(),
forthEvaluator.evaluateProgram(listOf("1 drop")))
}

@Ignore
@Test
fun testDropRemovesTheTopValueOnTheStackIfItIsNotTheOnlyOne() {
assertEquals(
listOf(1),
forthEvaluator.evaluateProgram(listOf("1 2 drop")))
}

@Ignore
@Test
fun testErrorIfDroppingAttemptedWithNothingOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Dropping requires that the stack contain at least 1 value")

forthEvaluator.evaluateProgram(listOf("drop"))
}

@Ignore
@Test
fun testSwapSwapsTheTopTwosValueOnTheStackIfTheyAreTheOnlyOnes() {
assertEquals(
listOf(2, 1),
forthEvaluator.evaluateProgram(listOf("1 2 swap")))
}

@Ignore
@Test
fun testSwapSwapsTheTopTwosValueOnTheStackIfTheyAreNotTheOnlyOnes() {
assertEquals(
listOf(1, 3, 2),
forthEvaluator.evaluateProgram(listOf("1 2 3 swap")))
}

@Ignore
@Test
fun testErrorIfSwappingAttemptedWithNothingOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Swapping requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("swap"))
}

@Ignore
@Test
fun testErrorIfSwappingAttemptedWithOneNumberOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Swapping requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("1 swap"))
}

@Ignore
@Test
fun testOverCopiesTheSecondElementIfThereAreOnlyTwo() {
assertEquals(
listOf(1, 2, 1),
forthEvaluator.evaluateProgram(listOf("1 2 over")))
}

@Ignore
@Test
fun testOverCopiesTheSecondElementIfThereAreMoreThanTwo() {
assertEquals(
listOf(1, 2, 3, 2),
forthEvaluator.evaluateProgram(listOf("1 2 3 over")))
}

@Ignore
@Test
fun testErrorIfOveringAttemptedWithNothingOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Overing requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("over"))
}

@Ignore
@Test
fun testErrorIfOveringAttemptedWithOneNumberOnTheStack() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Overing requires that the stack contain at least 2 values")

forthEvaluator.evaluateProgram(listOf("1 over"))
}

@Ignore
@Test
fun testUserDefinedOperatorsCanConsistOfBuiltInOperators() {
assertEquals(
listOf(1, 1, 1),
forthEvaluator.evaluateProgram(listOf(": dup-twice dup dup ;", "1 dup-twice")))
}

@Ignore
@Test
fun testUserDefinedOperatorsAreEvaluatedInTheCorrectOrder() {
assertEquals(
listOf(1, 2, 3),
forthEvaluator.evaluateProgram(listOf(": countup 1 2 3 ;", "countup")))
}

@Ignore
@Test
fun testCanRedefineAUserDefinedOperator() {
assertEquals(
listOf(1, 1, 1),
forthEvaluator.evaluateProgram(listOf(": foo dup ;", ": foo dup dup ;", "1 foo")))
}

@Ignore
@Test
fun testCanOverrideBuiltInWordOperators() {
assertEquals(
listOf(1, 1),
forthEvaluator.evaluateProgram(listOf(": swap dup ;", "1 swap")))
}

@Ignore
@Test
fun testCanOverrideBuiltInArithmeticOperators() {
assertEquals(
listOf(12),
forthEvaluator.evaluateProgram(listOf(": + * ;", "3 4 +")))
}

@Ignore
@Test
fun testCannotRedefineNumbers() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("Cannot redefine numbers")

forthEvaluator.evaluateProgram(listOf(": 1 2 ;"))
}

@Ignore
@Test
fun testErrorIfEvaluatingAnUndefinedOperator() {
expectedException.expect(IllegalArgumentException::class.java)
expectedException.expectMessage("No definition available for operator \"foo\"")

forthEvaluator.evaluateProgram(listOf("foo"))
}

}``````
``````import java.util.Stack

class ForthEvaluator {

private val queue = Stack<Int>()
private val userDefinedOperators = mutableMapOf<String, List<String>>()

fun evaluateProgram(input: List<String>): List<Int> {
input.forEach {
when {
it.startsWith(":") -> parseUserDefinedOperator(it)
else -> parseOperators(it.split(" "))
}
}
return queue.toList()
}

private fun parseOperators(operations: List<String>) {
operations.forEach {
val value = it.toIntOrNull()
when (value) {
null -> parseOperator(it)
else -> queue.push(value)
}
}
}

private fun parseOperator(operator: String) {
val lowerCaseOperator = operator.toLowerCase()
if (userDefinedOperators.containsKey(lowerCaseOperator)) {
runUserDefinedOperator(lowerCaseOperator)
} else {
when (lowerCaseOperator) {
"-" -> subtract()
"*" -> multiply()
"/" -> divide()
"dup" -> duplicate()
"drop" -> drop()
"swap" -> swap()
"over" -> over()
else -> throw IllegalArgumentException("No definition available for operator \"\$operator\"")
}
}
}

queue.push(queue.pop() + queue.pop())
}

private fun subtract() {
requireNumberOfValues("Subtraction", 2)
val subtrahend = queue.pop()
val minuend = queue.pop()
queue.push(minuend - subtrahend)
}

private fun multiply() {
requireNumberOfValues("Multiplication", 2)
queue.push(queue.pop() * queue.pop())
}

private fun divide() {
requireNumberOfValues("Division", 2)
val denominator = queue.pop()
require(denominator != 0) { "Division by 0 is not allowed" }
val numerator = queue.pop()
queue.push(numerator / denominator)
}

private fun duplicate() {
requireNumberOfValues("Duplicating", 1)
queue.push(queue.peek())
}

private fun drop() {
requireNumberOfValues("Dropping", 1)
queue.pop()
}

private fun swap() {
requireNumberOfValues("Swapping", 2)
val last = queue.pop()
val lastButOne = queue.pop()
queue.push(last)
queue.push(lastButOne)
}

private fun over() {
requireNumberOfValues("Overing", 2)
val last = queue.pop()
val lastButOne = queue.peek()
queue.push(last)
queue.push(lastButOne)
}

private fun requireNumberOfValues(operation: String, number: Int) {
require(queue.size >= number) {
val maybePlural = if (number == 1) "" else "s"
"\$operation requires that the stack contain at least \$number value\$maybePlural"
}
}

private fun parseUserDefinedOperator(definition: String) {
val split = definition.split(" ")
val userDefinedOperator = split[1].toLowerCase()
require(userDefinedOperator.toIntOrNull() == null) { "Cannot redefine numbers" }
val operators = split.subList(2, split.size - 1)
userDefinedOperators[userDefinedOperator] = operators
}

private fun runUserDefinedOperator(operator: String) {
userDefinedOperators[operator]?.let { parseOperators(it) }
}
}``````