Sign up Log in
Avatar of yonim

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
    fun testTwoNumbersCanBeAdded() {
        assertEquals(
                listOf(3),
                forthEvaluator.evaluateProgram(listOf("1 2 +")))
    }

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

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

    @Ignore
    @Test
    fun testErrorIfAdditionAttemptedWithOneNumberOnTheStack() {
        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
    fun testCombinedAdditionAndSubtraction() {
        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(
            "DUP"  to {duplicateStackHead() },
            "DROP" to {dropStackHead() },
            "SWAP" to {swapTopTwoValsOnStack() },
            "OVER" to {duplicateSecondValToStackHead() }
            )
    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]!!()
    }

    private fun duplicateSecondValToStackHead() {
        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")
        }
    }

    private fun dropStackHead() {
        dataStack.pop()
    }

    private fun duplicateStackHead() {
        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) {
        this.add(e)
    }

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

        return toReturn
    }

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

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

        return toReturn
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of yonim
yonim
Solution Author
commented 271 days ago

Does not pass one or two of the tests as I did not understand what the program should to in these cases.

Cancel

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?