# andre2w's solution

## to Forth in the Kotlin Track

Published at Feb 25 2019 · 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()
}

@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 testCanUseDifferentWordsWithSameName(){
assertEquals(
listOf(5,6),
forthEvaluator.evaluateProgram(listOf(": foo 5;", ": bar foo ;", ": foo 6 ;", "bar foo")))
}

@Ignore
@Test
fun testCanDefineWordThatUsesWordWithTheSameName(){
assertEquals(
listOf(11),
forthEvaluator.evaluateProgram(listOf(": foo 10;", ": foo foo 1 + ;", "foo")))
}

@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"))
}

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

@Ignore
@Test
fun testDropIsCaseInsensitive(){
assertEquals(
listOf(1),
forthEvaluator.evaluateProgram(listOf("1 2 3 4 DROP Drop drop")))
}

@Ignore
@Test
fun testSwapIsCaseInsensitive(){
assertEquals(
listOf(2,3,4,1),
forthEvaluator.evaluateProgram(listOf("1 2 SWAP 3 Swap 4 swap")))
}

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

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

@Ignore
@Test
fun testDefinitionsAreCaseInsensitive(){
assertEquals(
listOf(1,1,1,1),
forthEvaluator.evaluateProgram(listOf(": SWAP DUP Dup dup ;", "1 swap")))
}
}``````

### src/main/kotlin/ForthEvaluator.kt

``````import java.util.*
import kotlin.collections.HashMap

class ForthEvaluator {
private val userOperations = HashMap<String, List<Operation>>()

fun evaluateProgram(inputs: List<String>): List<Int> {
parseOperations(inputs)

return inputs.last()
.split(" ")
.map(String::toLowerCase)
.flatMap(this::toOperations)
.fold(Stack()) { acc, operation -> operation.execute(acc) }
}

private fun toOperations(it: String): List<Operation> {
return when {
userOperations.containsKey(it) -> userOperations[it]!!
else -> listOf(Operation.of(it))
}
}

private fun parseOperations(inputs: List<String>) {
inputs.filter(this@ForthEvaluator::isOperation)
.forEach(this@ForthEvaluator::parseOperation)
}

private fun parseOperation(it: String) {
val operation = parseRawOperation(it).split(" ", limit = 2)

require(operation[0] !in "1".."9") { "Cannot redefine numbers" }

val body = operation[1]
.split(" ")
.map { it.toLowerCase() }
.map { toOperations(it) }
.flatten()

userOperations[operation[0].toLowerCase()] = body
}

private fun isOperation(it: String) = it.startsWith(":")

private fun parseRawOperation(it: String) = it.replace(Regex(":|;"), "").trim()
}``````

### src/main/kotlin/Operations.kt

``````import java.util.*

sealed class Operation {

companion object {
fun of(input: String) : Operation {
return when (input) {
in "0".."9" -> Push(input.toInt())
"+" -> Sum
"-" -> Subtract
"*" -> Multiply
"/" -> Divide
"dup" -> Dup
"drop" -> Drop
"swap" -> Swap
"over" -> Over
else -> throw IllegalArgumentException("No definition available for operator \"\$input\"")
}
}
}

abstract fun execute(stack: Stack<Int>) : Stack<Int>
}

object Sum : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(stack.size > 1) { "Addition requires that the stack contain at least 2 values" }
return stack
}
}

object Subtract : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(stack.size > 1) { "Subtraction requires that the stack contain at least 2 values" }

val second = stack.pop()
return stack
}
}

object Multiply : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(stack.size > 1) { "Multiplication requires that the stack contain at least 2 values" }

return stack
}
}

object Divide : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(stack.size > 1) { "Division requires that the stack contain at least 2 values" }

val divisor = stack.pop()

if (divisor == 0)
throw IllegalArgumentException("Division by 0 is not allowed")

return stack
}
}

object Dup : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(!stack.isEmpty()) { "Duplicating requires that the stack contain at least 1 value" }

return stack
}

}

object Drop : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(!stack.isEmpty()) { "Dropping requires that the stack contain at least 1 value" }
stack.pop()
return stack
}

}

object Swap : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(stack.size > 1) { "Swapping requires that the stack contain at least 2 values" }

val first = stack.pop()
val second = stack.pop()

return stack
}

}

object Over : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
require(stack.size > 1) { "Overing requires that the stack contain at least 2 values" }

val last = stack.pop()
val secondToLast = stack.peek()

return stack
}
}

class Push(private val value: Int) : Operation() {
override fun execute(stack: Stack<Int>): Stack<Int> {
stack.push(value)
return stack
}
}``````