Interpreter Backend

1 Objective

• Classes for programming constructs
• Programming by object construction and composition
• Runtime evaluation of composed objects

2 Data

• Scalar types: String, numbers

• Aggregated types: List, dictionary, records

abstract class Data

All data values are going to instances of data.

object NullData: Data() {
    override fun toString(): String = "NULL"
}

NullData

NULL

class IntData(val value:Int): Data() {
    override fun toString(): String = "Int:$value"
}

IntData(12)

Int:12

class StringData(val value:String): Data() {
    override fun toString(): String = 
        if(value.length > 10) {
            "String:\"${value.substring(0, 10)}...\""
        } else {
            "String:\"$value\""
        }
}

StringData("Hello world, again and again")

String:"Hello worl..."

class BooleanData(val value:Boolean): Data() {
    override fun toString() = 
    "Boolean:${value}"
}

BooleanData(false)

Boolean:false

Challenge:

---

Can you implement:

• List
• Dictionary
• Record

as subclasses of Data

3 Runtime

The runtime is the environment in which the program can execute. It provides the following services:

• Storage of data. This is typically lookup table, known as the symbol table. The symbol table corresponds to the concept of scopes

• Access to hardware. Runtime provides function calls that allow controlled access to hardware such as filesystem and networking.

Runtime can make copy of itself when creating sub-scopes, or sandboxed environments.

class Runtime() {
    val symbolTable:MutableMap<String, Data> = mutableMapOf()
    fun subscope(bindings:Map<String, Data>):Runtime {
        val parentSymbolTable = this.symbolTable
        return Runtime().apply {
            symbolTable.putAll(parentSymbolTable)
            symbolTable.putAll(bindings)
        }
    }
    override fun toString():String =
        symbolTable.map { 
            entry -> "${entry.key} = ${entry.value}"
        }.joinToString("; ")
}

Runtime()
    .subscope(
        mapOf(
            "a" to IntData(42),
            "b" to StringData("Hello")
        )
    )

a = Int:42; b = String:"Hello"

4 Programming starts here…

Programming is instructing the runtime environment to perform certain tasks. We will cover each of the programming constructs and show how they are represented as classes and objects.

4.1 Expression

• All programs are expressions.
• All expressions evaluate to data.
• Expressions can read and modify the runtime environment.

abstract class Expr {
    abstract fun eval(runtime: Runtime): Data
}

object NullExpr: Expr() {
    override fun eval(runtime:Runtime): Data = NullData
}

4.2 Literals

class IntLiteral(val lexeme:String): Expr() {
    override fun eval(runtime:Runtime): Data
    = IntData(Integer.parseInt(lexeme))
}

IntLiteral("42").eval(Runtime())

Int:42

class StringLiteral(val lexeme:String): Expr() {
    override fun eval(runtime:Runtime): Data
    = StringData(lexeme)
}

StringLiteral("Hello world").eval(Runtime())

String:"Hello worl..."

class BooleanLiteral(val lexeme:String): Expr() {
    override fun eval(runtime:Runtime): Data
    = BooleanData(lexeme.equals("true"))
}

BooleanLiteral("true").eval(Runtime())

Boolean:true

4.3 Arithmetic operations

enum class Operator {
    Add,
    Sub,
    Mul,
    Div
}

class Arithmetics(
    val op:Operator,
    val left:Expr,
    val right:Expr
): Expr() {
    override fun eval(runtime:Runtime): Data {
        val x = left.eval(runtime)
        val y = right.eval(runtime)
        if(x !is IntData || y !is IntData) {
            throw Exception("cannot handle non-integer")
        }
        return IntData(
            when(op) {
                Operator.Add -> x.value + y.value
                Operator.Sub -> x.value - y.value
                Operator.Mul -> x.value * y.value
                Operator.Div -> {
                    if(y.value != 0) {
                        x.value / y.value
                    } else {
                        throw Exception("cannot divide by zero")
                    }
                }
                else -> throw Exception("Unknown operator")
            }
        )
    }
}

Arithmetics(
    Operator.Mul,
    IntLiteral("42"),
    IntLiteral("2")
)
.eval(Runtime())

Int:84

\[ 42 * 2 \]

Arithmetics(
    Operator.Mul,
    Arithmetics(
        Operator.Add,
        IntLiteral("20"),
        Arithmetics(
            Operator.Div,
            IntLiteral("10"),
            IntLiteral("5"),
        )
    ),
    IntLiteral("3")
)
.eval(Runtime())

Int:66

\[ (20 + (10/5)) * 3 \]

4.4 Accessing the scope

4.4.1 update symbol table

class Assign(val symbol:String, val expr:Expr): Expr() {
    override fun eval(runtime:Runtime): Data
    = expr.eval(runtime).apply {
        runtime.symbolTable.put(symbol, this)
    }
}

val expr = Assign(
    "x",
    Arithmetics(Operator.Add,
                IntLiteral("1"),
                IntLiteral("2"))
)
val runtime = Runtime()

println("Before: $runtime")
expr.eval(runtime)
println("After: $runtime")

Before: 
After: x = Int:3

x = 1 + 2

4.4.2 reading from symbol table

class Deref(val name:String): Expr() {
    override fun eval(runtime:Runtime):Data {
        val data = runtime.symbolTable[name]
        if(data == null) {
            throw Exception("$name is not assigned.")
        }
        return data
    }
}

Arithmetics(
    Operator.Mul,
    Deref("x"),
    IntLiteral("2"),
)
.eval(runtime)

Int:6

x * 2

4.5 Code blocks

class Block(val exprList: List<Expr>): Expr() {
    override fun eval(runtime:Runtime): Data {
        var result:Data = NullData
        exprList.forEach {
            result = it.eval(runtime)
        }
        return result
    }
}

Block(
    listOf(
        Assign("x", IntLiteral("42")),
        Assign("y", IntLiteral("2")),
        Assign("z",
               Arithmetics(
                   Operator.Mul,
                   Deref("x"),
                   Deref("y")
               )
        ),
        Deref("z")
    )
)
.eval(Runtime())

Int:84

x = 42
y = 2
z = x * 2
z

5 More expressions: Flow control constructs

enum class Comparator {
    LT,
    LE,
    GT,
    GE,
    EQ,
    NE,
}

class Compare(
    val comparator: Comparator,
    val left: Expr,
    val right: Expr
): Expr() {
    override fun eval(runtime:Runtime): Data {
        val x = left.eval(runtime)
        val y = right.eval(runtime)
        if(x is IntData && y is IntData) {
            return BooleanData(
                when(comparator) {
                    Comparator.LT -> x.value < y.value
                    Comparator.LE -> x.value <= y.value
                    Comparator.GT -> x.value > y.value
                    Comparator.GE -> x.value >= y.value
                    Comparator.EQ -> x.value == y.value
                    Comparator.NE -> x.value != y.value
                }
            )
        } else {
            throw Exception("Non-integer data in comparison")
        }
    }
}

Compare(
    Comparator.LT,
    IntLiteral("2"),
    IntLiteral("1")
)
.eval(Runtime())

Boolean:false

\[ 2 < 1 \]

5.1 If-else

class Ifelse(
    val cond:Expr,
    val trueExpr:Expr,
    val falseExpr:Expr
): Expr() {
    override fun eval(runtime:Runtime): Data {
        val cond_data = cond.eval(runtime)
        if(cond_data !is BooleanData) {
            throw Exception("need boolean data in if-else")
        }
        return if(cond_data.value) {
            return trueExpr.eval(runtime)
        } else {
            return falseExpr.eval(runtime)
        }
    }
}

Block(
    listOf(
        Assign("x", IntLiteral("2")),
        Assign("y", IntLiteral("1")),
        Ifelse(
            Compare(
                Comparator.LT,
                Deref("x"),
                Deref("y")
            ),
            StringLiteral("x < y"),
            StringLiteral("y < x")
        )
    )
)
.eval(Runtime())

String:"y < x"

x = 2
y = 1

if x < y:
    "x < y"
else:
    "y < x"

5.2 While loops

class While(val cond:Expr, val body:Expr): Expr() {
    override fun eval(runtime:Runtime): Data {
        var flag = cond.eval(runtime) as BooleanData
        var result:Data = NullData
        var iter:Int = 1_000_000
        while(flag.value) {
            result = body.eval(runtime)
            flag = cond.eval(runtime) as BooleanData
            if(iter == 0) {
                println("MAX_ITER reached")
                println(runtime)
                return NullData
            }
            iter --
        }
        return result
    }
}

Block(
    listOf(
        Assign("x", IntLiteral("0")),
        Assign("i", IntLiteral("0")),
        While(
            Compare(Comparator.LE, Deref("i"), IntLiteral("10")),
            Block(
                listOf(
                    Assign(
                        "x",
                        Arithmetics(Operator.Add, Deref("x"), Deref("i"))
                    ),
                    Assign(
                        "i",
                        Arithmetics(Operator.Add, Deref("i"), IntLiteral("1")
                        )
                    ),
                )
            )
        ),
        Deref("x")
    )
).
eval(Runtime())

Int:55

x = 0
i = 0
while i < 10:
    x = x + i
    i = i + 1
x

5.3 Function Declaration

class FuncData(
    val name: String,
    val params: List<String>,
    val body: Expr
): Data() {
    override fun toString()
    = params.joinToString(", ").let {
        "$name($it) { ... }"
    }
}

FuncData("add", listOf("i", "j"), NullExpr)

add(i, j) { ... }

class Declare(
    val name: String,
    val params: List<String>,
    val body: Expr
): Expr() {
    override fun eval(runtime:Runtime):Data
    = FuncData(name, params, body).also {
        runtime.symbolTable[name] = it
    }
}

val r = Runtime()
Block(listOf(
    Declare("add", listOf("x", "y"), NullExpr)
))
.eval(r)

r

add = add(x, y) { ... }

5.4 Invoke function

class Invoke(val name:String, val args:List<Expr>):Expr() {
    override fun eval(runtime:Runtime):Data {
        val func:Data? = runtime.symbolTable[name]
        if(func == null) {
            throw Exception("$name does not exist")
        }
        if(func !is FuncData) {
            throw Exception("$name is not a function.")
        }
        if(func.params.size != args.size) {
            throw Exception(
                "$name expects ${func.params.size} arguments "
                + "but received ${args.size}"
            )
        }
        
        val r = runtime.subscope(
            func.params.zip(args.map {it.eval(runtime)}).toMap()
        )
        return func.body.eval(r)
    }
}

Block(
    listOf(
        Assign("x", IntLiteral("10")),
        Assign("y", IntLiteral("20")),
        Declare("add",
                listOf("i", "j"),
                Arithmetics(Operator.Add, Deref("i"), Deref("j"))),
        Invoke("add",
               listOf(Deref("x"), Deref("y")))
    )
).eval(Runtime())

Int:30

x = 10
y = 20

def add(i, j):
    return i + j

add(x, y)