nil
The base class to represent all forms of data.
abstract class Data
Create some forms of data.
class IntData(val value: Int): Data() {
override fun toString(): String
= "Int($value)"
}
IntData(42)
class BoolData(val value: Boolean): Data() {
override fun toString(): String
= if(value) {
"yes"
} else {
"no"
}
}
BoolData(true)
Create a class to represent scopes, which are also known as contexts.
class Context(): HashMap<String, Data>() {
constructor(parent: Context): this() {
this.putAll(parent)
}
}
Create the base class to represent all forms of expressions.
Bold objective
Everything will be expressions.
abstract class Expr {
abstract fun eval(scope:Context): Data
}
Helper function to evaluate expressions for us.
fun run(program: Expr) {
try {
val data = program.eval(Context())
println("=> ${data}")
} catch(e: Exception) {
println("[err] ${e}")
}
}
Data literals
42class IntLiteral(val value: Int): Expr() {
override fun eval(scope:Context): Data
= IntData(value)
}
// Use the IntLiteral to write a small program
IntLiteral(42).eval(Context())
Support standard binary arithmetics on integers
42 + 1(20 + (11*2)) + 1enum class Op {
Add,
Sub,
Mul,
Div
}
class Arithmetic(
val op: Op,
val left: Expr,
val right: Expr): Expr() {
override fun eval(scope: Context): Data {
val x = (left.eval(scope) as IntData).value
val y = (right.eval(scope) as IntData).value
return IntData(
when(op) {
Op.Add -> x + y
Op.Mul -> x * y
Op.Sub -> x - y
Op.Div -> x / y
}
)
}
}
// Use BinaryOp to implement 42 + 1
Arithmetic(Op.Add, IntLiteral(42), IntLiteral(1))
.eval(Context())
// Use BinaryOp to implement (20 + (11*2)) + 1
Arithmetic(Op.Add,
Arithmetic(Op.Add,
IntLiteral(20),
Arithmetic(Op.Mul,
IntLiteral(11),
IntLiteral(2))),
IntLiteral(1))
.eval(Context())
Binding as an expression.
x = 42class Bind(val name: String, val expr: Expr): Expr() {
override fun eval(scope: Context): Data {
val data = expr.eval(scope)
scope[name] = data
return data
}
}
// Use bind to update scope with x=42
val scope = Context()
println("> $scope")
Bind("x", IntLiteral(42)).eval(scope)
println("> $scope")
Dereference symbol value as an expression.
xclass Deref(val name: String): Expr() {
override fun eval(scope: Context): Data {
val data: Data? = scope[name]
if(data == null) {
throw Exception("Variable ${name} does not exist.")
} else {
return data
}
}
}
run(Deref("x"))
Block is a list of expressions. Its result is the result of the last expression.
x = 42
y = 1
x + yclass Block(val exprList: List<Expr>): Expr() {
override fun eval(scope: Context): Data {
var result: Data = IntData(0)
exprList.forEach {
result = it.eval(scope)
}
return result
}
}
// Run multiple expressions in a single block
val program = Block(listOf(
Bind("x", IntLiteral(42)),
Bind("y", IntLiteral(1)),
Arithmetic(Op.Add, Deref("x"), Deref("y"))
))
run(program)
Comparison expression
enum class Comparator {
LT, // <
LE, // <=
GT, // >
GE, // >=
EQ, // ==
NE, // !=
}
class Compare(
val cmp: Comparator, val left: Expr, val right: Expr
): Expr() {
override fun eval(scope: Context): Data {
val x = (left.eval(scope) as IntData).value
val y = (right.eval(scope) as IntData).value
return BoolData(
when(cmp) {
Comparator.LT -> x < y
Comparator.LE -> x <= y
Comparator.GT -> x > y
Comparator.GE -> x >= y
Comparator.EQ -> x == y
Comparator.NE -> x != y
}
)
}
}
run(
Compare(
Comparator.EQ,
IntLiteral(42),
IntLiteral(1)
)
)
IfElse as an expression
x = 42
y = 1
if(x < y) {
x - y
} else {
x + y
}class IfElse(
val cond: Expr,
val trueExpr: Expr,
val falseExpr: Expr
) : Expr() {
override fun eval(scope: Context): Data {
val condData = cond.eval(scope)
val flag = (condData as BoolData).value
return if(flag) {
trueExpr.eval(scope)
} else {
falseExpr.eval(scope)
}
}
}
// Use IfElse to implement the code
Block(listOf(
Bind("x", IntLiteral(42)),
Bind("y", IntLiteral(1)),
IfElse(
Compare(Comparator.LT,
Deref("x"),
Deref("y")),
Arithmetic(Op.Sub,
Deref("x"),
Deref("y")),
Arithmetic(Op.Add,
Deref("x"),
Deref("y"))
)
)).eval(Context())
The while loop is similar to IfElse:
sum = 0
i = 0
loop i < 1000 {
sum = sum + i
i = i + 1
}
sumclass Loop(val cond: Expr, val body: Expr) : Expr() {
override fun eval(scope: Context): Data {
val MAX_ITER = 10000
var flag = cond.eval(scope) as BoolData
var result:Data = IntData(0)
var counter = 0
while(flag.value && counter < MAX_ITER) {
result = body.eval(scope)
counter += 1
flag = cond.eval(scope) as BoolData
}
if(counter == MAX_ITER) {
throw Exception("Did you forget to stop your loop? ${MAX_ITER}")
}
return result
}
}
sum = 0
i = 0
loop i < 1000 {
sum = sum + i
i = i + 0
}
sumval program = Block(listOf(
Bind("sum", IntLiteral(0)),
Bind("i", IntLiteral(0)),
Loop(
// Condition
Compare(
Comparator.LT,
Deref("i"),
IntLiteral(1000)
),
// Body
Block(listOf(
Bind("sum", Arithmetic(Op.Add, Deref("sum"), Deref("i"))),
Bind("i", Arithmetic(Op.Add, Deref("i"), IntLiteral(1)))
)),
),
Deref("sum")
))
run(program)
We need a FuncData which will describe a function declaration.
class FuncData(
val name: String,
val parameters: List<String>,
val body: Expr
): Data() {
override fun toString(): String {
val params = parameters.joinToString(",")
return "${name}($params)"
}
}
FuncData(
"add3",
listOf("i", "j", "k"),
Arithmetic(Op.Add,
Deref("i"),
Arithmetic(Op.Add, Deref("j"), Deref("k"))))
Function declaration, similar to binding.
add = function(i,j,k) {
i + j + k
}class Declare(
val funcname: String,
val parameters: List<String>,
val body: Expr
): Expr() {
override fun eval(scope: Context): Data {
val f = FuncData(funcname, parameters, body)
scope[funcname] = f
return f
}
}
Function invocation
add(10, 20, 30)class Invoke(
val funcname: String,
val args: List<Expr>
): Expr() {
override fun eval(scope: Context): Data {
val f:Data? = scope[funcname]
if(f == null) {
throw Exception("Function {$funcname} does not exist.")
}
if(!(f is FuncData)) {
throw Exception("${f} is not a function.")
}
if(f.parameters.size != args.size) {
throw Exception("${f} expects ${f.parameters.size} arguments.")
}
val childscope = Context(scope)
f.parameters.zip(
args,
fun (parameter, arg) {
childscope[parameter] = arg.eval(scope)
})
return f.body.eval(childscope)
}
}
i = 10
x = 20
function add3(i,j,k) {
i + j + k
}
add3(1,2,3)
ival program = Block(
listOf(
// x = 10
Bind("i", IntLiteral(10)),
// y = 20
Bind("x", IntLiteral(20)),
// declaration
Declare("add3",
listOf("i", "j", "k"),
Arithmetic(Op.Add,
Deref("i"),
Arithmetic(Op.Add, Deref("j"), Deref("k")))),
// invoke the function
Invoke("add3", listOf(
Deref("i"),
Deref("x"),
Deref("x"),
)),
)
)
run(program)
Use loop to implement sum.
function sum(n) {
i = 1
total = 0
while i <= n {
total = total + i
i += 1
}
total
}
sum(1000)val program = Block(
listOf(
Declare("sum", listOf("n"),
Block(
listOf(
Bind("i", IntLiteral(1)),
Bind("total", IntLiteral(0)),
Loop(
Compare(
Comparator.LE,
Deref("i"),
Deref("n")
),
Block(
listOf(
Bind("total",
Arithmetic(Op.Add,
Deref("total"),
Deref("i"))),
Bind("i",
Arithmetic(Op.Add,
Deref("i"),
IntLiteral(1)))))
),
Deref("total")
)
)),
Invoke("sum", listOf(IntLiteral(3)))
)
)
run(program)
Use recursion to implement sum.
function sum_recur(n) {
if n == 0 {
0
} else {
sum_recur(n-1) + n
}
}
sum_recur(1000)val program = Block(
listOf(
Declare("sum_recur",
listOf("n"),
IfElse(
Compare(
Comparator.EQ,
Deref("n"),
IntLiteral(0)
),
IntLiteral(0),
Arithmetic(
Op.Add,
Invoke("sum_recur", listOf(
Arithmetic(Op.Sub, Deref("n"), IntLiteral(1))
)),
Deref("n")
)
)),
Invoke("sum_recur", listOf(IntLiteral(3)))
)
)
run(program)