# yonim's solution

## to Forth in the Kotlin Track

Published at Mar 09 2019 · 1 comment
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")))
}
}``````
``````class ForthEvaluator {
private var dataStack = mutableListOf<Int>()
private var commandStack = mutableListOf<String>()

private val integerArithmeticCommands = mapOf(
"+" to { l: Int, r: Int -> l + r },
"-" to { l: Int, r: Int -> l - r },
"*" to { l: Int, r: Int -> l * r },
"/" to { l: Int, r: Int -> l / r }
)
private val stackManipulationCommands = mapOf(
"SWAP" to {swapTopTwoValsOnStack() },
)
private val userDefinedCommands = mutableMapOf<String, String>()
//    private val stackManipulationCommands = listOf("DUP", "DROP", "SWAP", "OVER")

fun evaluateProgram(inList: List<String>): List<Int>
{
inList.forEach { s ->
val inputAsList = s.split(' ')
if (inputAsList[0] == ":"){
defineUserAction(inputAsList)
}
else{
for (t in inputAsList.reversed()) {
val token = t.toUpperCase()
this.commandStack.push(token)
}
var token = commandStack.pop()
while (token != null){
token = token.toUpperCase()
when (token) {
in integerArithmeticCommands.keys -> doArithmetic(token)
in stackManipulationCommands.keys -> perform(token)
in userDefinedCommands.keys -> performUser(token)

else -> try {
val num = token.toInt()
dataStack.push(num)
} catch (e: NumberFormatException) {
// todo: exception
}
}
token = commandStack.pop()
}
}
}
return dataStack
}

private fun performUser(token: String) {
val userCommantList = userDefinedCommands[token]?.split(' ')

if (userCommantList != null) {
for (t in userCommantList.reversed()) {
var token = t.toUpperCase().dropLastWhile { it == ';' }
this.commandStack.push(token)
}
}
}

private fun defineUserAction(inputList: List<String>) {
var mnipulatedList = inputList.dropWhile { it == ":" }.dropLastWhile { it == ";" }
val key = mnipulatedList[0].toUpperCase()
userDefinedCommands[key] = mnipulatedList.drop(1).joinToString ( " " )
}

private fun perform(token: String) {
stackManipulationCommands[token]!!()
}

val v1 = dataStack.pop()
val v2 = dataStack.pop()

if (v1 == null || v2 == null ){
throw IllegalArgumentException("Overing requires that the stack contain at least 2 values")
}

dataStack.push(v2)
dataStack.push(v1)
dataStack.push(v2)
}

private fun swapTopTwoValsOnStack() {
val v1 = dataStack.pop()
val v2 = dataStack.pop()

if (v1 != null){
dataStack.push(v1)
}
if (v2 != null){
dataStack.push(v2)
}
else {
throw IllegalArgumentException("Swapping requires that the stack contain at least 2 values")
}
}

dataStack.pop()
}

val v = dataStack.pop()
if (v != null){
dataStack.push(v)
dataStack.push(v)
}
}

private fun doArithmetic(token: String){
val rhs = dataStack.pop()
val lhs = dataStack.pop()
if (rhs != null && lhs != null) {
dataStack.push( integerArithmeticCommands[token]!!(lhs, rhs) )
}
else {
throw Exception("No enough data in the stack")
}
}

private fun MutableList<Int>.push(e: Int) {
}

private fun MutableList<Int>.pop() : Int? {
val lastInd: Int = this.lastIndex
if (lastInd == -1){
return null
}
val toReturn = this[lastIndex]
this.removeAt(lastIndex)

}

private fun MutableList<String>.push(e: String) {
}

private fun MutableList<String>.pop() : String? {
val lastInd: Int = this.lastIndex
if (lastInd == -1){
return null
}
val toReturn = this[lastIndex]
this.removeAt(lastIndex)

}
}``````