colintheshots's solution

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

}``````
``````class ForthEvaluator {
private val userDefinedMap = mutableMapOf<String, List<Token>>()

fun evaluateProgram(program: List<String>) : List<Int> {
val tokenLines : List<List<Token>> = program.map { line ->
val tokens = line.split("\\s".toRegex())
tokens.map { token ->
when (token) {
in Regex("^\\d+\$") -> Num(Integer.parseInt(token))
in Regex("[-]") -> Operation(Op.SUBTRACT)
in Regex("[*]") -> Operation(Op.MULTIPLY)
in Regex("[/]") -> Operation(Op.DIVIDE)
in Regex("DUP", RegexOption.IGNORE_CASE) -> Operation(Op.DUP)
in Regex("DROP", RegexOption.IGNORE_CASE) -> Operation(Op.DROP)
in Regex("SWAP", RegexOption.IGNORE_CASE) -> Operation(Op.SWAP)
in Regex("OVER", RegexOption.IGNORE_CASE) -> Operation(Op.OVER)
in Regex(";") -> Operation(Op.DEFINE)
else -> Word(token)
}
}
}
val expression = mutableListOf<Token>()

tokenLine.forEach { token ->
}
evalExpression(expression)
}.flatMap { x -> x }
}

private fun evalExpression(expression: List<Token>): List<Int> {
return when {
expression.isEmpty() -> emptyList()
expression.last() is Word -> {
val word = (expression.last() as Word).word
if (userDefinedMap.containsKey(word)) {
userDefinedMap[word]?.let { evalExpression(expression.dropLast(1).plus(it)) } ?: emptyList()
}
else
throw IllegalArgumentException("No definition available for operator \"\$word\"")
}
expression.last() is Operation -> {
val op = expression.last() as Operation
val operands = expression.dropLast(1)
if (userDefinedMap.containsKey(op.operation.name)) {
userDefinedMap[op.operation.name]?.let { evalExpression(expression.dropLast(1).plus(it)) } ?: emptyList()
} else when (op.operation) {
require(operands.size > 1) {"Addition requires that the stack contain at least 2 values"}
val second = (operands.last() as Num).number
val first = operands.dropLast(1)
val firstNum = if (first.last() is Num) {
first.last().toInt()
} else {
evalExpression(first)[0]
}
listOf(firstNum + second)
}
Op.SUBTRACT -> {
require(operands.size > 1) {"Subtraction requires that the stack contain at least 2 values"}
val second = (operands.last() as Num).number
val first = operands.dropLast(1)
val firstNum = if (first.last() is Num) {
first.last().toInt()
} else {
evalExpression(first)[0]
}
listOf(firstNum - second)
}
Op.MULTIPLY -> {
require(operands.size > 1) {"Multiplication requires that the stack contain at least 2 values"}
val second = (operands.last() as Num).number
val first = operands.dropLast(1)
val firstNum = if (first.last() is Num) {
first.last().toInt()
} else {
evalExpression(first)[0]
}
listOf(firstNum * second)
}
Op.DIVIDE -> {
require(operands.size > 1) {"Division requires that the stack contain at least 2 values"}
val second = (operands.last() as Num).number
val first = operands.dropLast(1)
val firstNum = if (first.last() is Num) {
first.last().toInt()
} else {
evalExpression(first)[0]
}
require(second != 0) {"Division by 0 is not allowed"}
listOf(firstNum / second)
}
Op.DUP -> {
require(operands.isNotEmpty()) {"Duplicating requires that the stack contain at least 1 value"}
val value = operands.last()
val dupedNum = (value as? Num)?.number ?: (evalExpression(operands))[0]
evalExpression(operands.dropLast(1)) + listOf(dupedNum, dupedNum)
}
Op.DROP -> {
require(operands.isNotEmpty()) {"Dropping requires that the stack contain at least 1 value"}
evalExpression(operands.dropLast(1))
}
Op.SWAP -> {
require(operands.size > 1) {"Swapping requires that the stack contain at least 2 values"}
evalExpression(operands.dropLast(2).plus(operands.takeLast(2).reversed()))
}
Op.OVER -> {
require(operands.size > 1) {"Overing requires that the stack contain at least 2 values"}
evalExpression(operands.plus(operands[operands.size - 2]))
}
Op.DEFINE -> {
require(operands.size > 2)
require(operands[1] !is Num) {"Cannot redefine numbers"}
val name = when (operands[1]) {
is Word -> (operands[1] as Word).word
is Operation -> (operands[1] as Operation).operation.name
else -> throw IllegalArgumentException("Illegal user defined type")
}
userDefinedMap.put(name, operands.drop(2))
emptyList()

}
}
}
expression.all { it is Num } -> expression.map { number ->
number.toInt()
}
else -> throw IllegalArgumentException()
}
}
}

sealed class Token
class Num(val number: Int) : Token()
class Operation(val operation: Op) : Token()
class Word(val word: String) : Token()
enum class Op {
ADD, SUBTRACT, MULTIPLY, DIVIDE, DUP, DROP, SWAP, OVER, DEFINE
}

fun Token.toInt(): Int = (this as Num).number
operator fun Regex.contains(text: String) : Boolean = this.matches(text)``````