用Kotlin仿写解释器

动机

话说我已经忘了什么时候看的这篇博文了，但是从那以后确实就入坑了(说不清是什么坑)，感谢王垠
http://www.yinwang.org/blog-cn/2012/08/01/interpreter/

关于Kotlin

简单的说就是Java的改良版。更多特性，填了很多坑，代码还更精简。十分看好。关键是函数是第一公民啊 :D
这货也经常被形容为Android世界的Swift,可以看看后面的代码，是有点像。
丢个官网大家自己去看吧，还能在线试用 :D
这货是jetbrains开发出来的。和intellij兼容无限好。简直不要更爽，十分看好它的潜力。
（开脑洞的话，2年以内Kotlin爆炸式增长，Google收购JetBrains，Kotlin一统网页+安卓开发 （想多了））
http://www.kotlinlang.org/

关于这个解释器

逻辑完全是仿的博文里的那个。写的很矬很罗嗦。就当看个乐吧（然而并没有人会看......）

顺便再次推荐Programming Languages: Application and Interpretation(2nd)这本书。没看过这个的话我是想不出来怎么用静态语言去实现那一堆东西的。总之，这本书粗看一遍都收获巨大，仔细看的话，那还不飞上天啊。。。
书的主页
http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/

import java.util.*

val env0 = LinkedList<Pair<Expr.Symbol, RetValue>>()

sealed class Expr{
    class Symbol(val name:String):Expr()
    class Num(val num:Int):Expr()
    class Lambda(val arg:Symbol, val body:Expr):Expr()
    class App(val func:Expr,val arg:Expr):Expr()
    class ArithOp(val op:Char,val e1:Expr, val e2:Expr):Expr()
}

sealed class RetValue{
    class NumValue(val num: Int):RetValue()
    class Closure(val fundef:Expr.Lambda,
                  val env:LinkedList<Pair<Expr.Symbol, RetValue>>):RetValue()
}


fun ext_env(name: Expr.Symbol, value: RetValue, env: LinkedList<Pair<Expr.Symbol,RetValue>>)
        : LinkedList<Pair<Expr.Symbol, RetValue>> {
    var ret = env.clone() as LinkedList<Pair<Expr.Symbol, RetValue>>
    ret.push(Pair(name, value))
    return ret
}

fun lookup(symbol:Expr.Symbol, env: LinkedList<Pair<Expr.Symbol, RetValue>>):RetValue {
    for(p in env){
        if(symbol.name==p.first.name){
            return p.second
        }
    }
    val str = symbol.name

    throw UnknownError("Look up Failed,not fould $str in env $env")
}

fun interp1(exp:Expr,
            env: LinkedList<Pair<Expr.Symbol, RetValue>>) : RetValue {
    when (exp){
        is Expr.Symbol -> return lookup(exp, env)
        is Expr.Num -> return RetValue.NumValue(exp.num)
        is Expr.Lambda -> return RetValue.Closure(exp,env)
        is Expr.App -> {
            val appclosure = interp1(exp.func,env) as RetValue.Closure
            val argvalue = interp1(exp.arg,env)
            return interp1(appclosure.fundef.body,
                        ext_env(appclosure.fundef.arg,argvalue,appclosure.env))
        }
        is Expr.ArithOp -> {
            val v1 = interp1(exp.e1,env) as RetValue.NumValue
            val v2 = interp1(exp.e2,env) as RetValue.NumValue
            return when(exp.op){
                '+' -> RetValue.NumValue(v1.num+v2.num)
                '-' -> RetValue.NumValue(v1.num-v2.num)
                '*' -> RetValue.NumValue(v1.num*v2.num)
                '/' -> RetValue.NumValue(v1.num/v2.num)
                else -> throw UnknownError("Unexpected op"+exp.op)
            }
        }
    }
}

fun interp(exp: Expr):Int {
    val ret = interp1(exp,env0)
    when (ret){
        is RetValue.NumValue -> return ret.num
        is RetValue.Closure -> throw UnknownError("Unexpected Closure in interp with $exp")
    }
}



fun main(args: Array<String>) {
    fun drive(exp:Expr) {
        println(interp(exp))
    }
    drive(Expr.App(
            Expr.App(Expr.Lambda(Expr.Symbol("x"),
                        Expr.Lambda(Expr.Symbol("y"),
                            Expr.ArithOp('*',Expr.Symbol("x"),Expr.Symbol("y"))))
            ,Expr.Num(2))
          ,Expr.Num(3)))

    /*
((lambda (y)
     (((lambda (y)
         (lambda (x) (* y 2))) 3) 0)) 4)
*/
    drive(Expr.App(
            Expr.Lambda(Expr.Symbol("y"),
                    Expr.App(
                     Expr.App(
                      Expr.Lambda(Expr.Symbol("y"),
                              Expr.Lambda(Expr.Symbol("x"),
                                            Expr.ArithOp('*',Expr.Symbol("y"),Expr.Num(2))))
                     ,Expr.Num(3))
                    ,Expr.Num(0)))
            ,Expr.Num(4)))
}