## to Forth in the Kotlin Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

#### Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code 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"))
}

}``````
``````interface ForthOperation {
val eval: (List<Int>) -> List<Int>
}

data class NumericOp(private val args: List<Int>) : ForthOperation {
override val eval: (List<Int>) -> List<Int> = { _ -> args }
}

enum class ForthOp(val token: String, override val eval: (List<Int>) -> List<Int>) : ForthOperation {
plus("+", {
require(it.size >= 2) { "Addition requires that the stack contain at least 2 values" }
it.dropLast(2) + (it.takeLast(2).sum())
}),
minus("-", {
require(it.size >= 2) { "Subtraction requires that the stack contain at least 2 values" }
val them = it.takeLast(2)
it.dropLast(2) + (them[0] - them[1])
}),
div("/", {
require(it.size >= 2) { "Division requires that the stack contain at least 2 values" }
require(it.last() != 0) { "Division by 0 is not allowed" }
val them = it.takeLast(2)
it.dropLast(2) + (them[0] / them[1])
}),
times("*", {
require(it.size >= 2) { "Multiplication requires that the stack contain at least 2 values" }
val them = it.takeLast(2)
it.dropLast(2) + (them[0] * them[1])
}),
dup("dup", {
require(it.isNotEmpty()) { "Duplicating requires that the stack contain at least 1 value" }
it + it.last()
}),
drop("drop", {
require(it.isNotEmpty()) { "Dropping requires that the stack contain at least 1 value" }
it.dropLast(1)
}),
swap("swap", {
require(it.size >= 2) { "Swapping requires that the stack contain at least 2 values" }
val them = it.takeLast(2)
it.dropLast(2) + listOf(them[1], them[0])
}),
over("over", {
require(it.size >= 2) { "Overing requires that the stack contain at least 2 values" }
it + (it.takeLast(2).min()!!)
}),
;

companion object {
fun find(op: String): ForthOperation? = values().find { op.equals(it.token, ignoreCase = true) }
}
}

class ForthEvaluator() {
fun evaluateProgram(code: List<String>): List<Int> {
val customOps = mutableMapOf<String, List<ForthOperation>>()

fun parseOps(args: List<String>): List<ForthOperation> = args.map { it.toIntOrNull() }.let {
if (it.contains(null)) args.mapNotNull { ForthOp.find(it) }
else listOf(NumericOp(it.filterNotNull()))
}

fun parse(s: String): List<Int> {
val tokens = s.split(" ")
return when {
tokens.size >= 2 && tokens.first() == ":" && tokens.last() == ";" -> {
val alias = tokens[1]
require(alias.none { it.isDigit() }) { "Cannot redefine numbers" }
val ops = parseOps(tokens.drop(2).dropLast(1))
customOps.put(alias, ops)
listOf()
}

else -> tokens.fold(listOf()) { acc, next ->
next.toIntOrNull().let {
if (it != null) acc + it
else {
val ops = customOps[next] ?: listOf(ForthOp.find(next))
if (ops.contains(null)) throw java.lang.IllegalArgumentException("""No definition available for operator "\$next"""")
ops.filterNotNull().fold(acc) { rem, op -> op.eval(rem) }
}
}
}
}
}

return code.flatMap { parse(it) }
}
}``````