klambda解释器

2017-11-16

Shen语言号称是 write once, run anywhere。怎么做的呢？并是不将源代码编译成汇编或者二进制，而是编译到一个更简单的叫做klambda的语言，以下简称kl。kl扮演了一个虚拟机或者平台无关层的角色，但比较有意思的是：它是一个lisp语言。

kl是一个非常精简的lisp，几乎接近于lambda演算，大概有50多个系统函数，包括一些IO相关的。klambda存在的主要意义就是方便port，目前Shen语言已经有common lisp，elisp，C，F#，haskell，scheme等等很多的port了。Shen语言可以完全用kl实现，虽然Shen是用Shen语言写的，但它实现是将Shen语言编译到kl，运行在kl，编译到kl，如此完成自举。

kl比scheme还要精简许多。回头想想，scheme还是太复杂了，像call/cc的连续，卫生宏，这些其实都是很复杂的不好实现的feature。Shen暂时还没有Go的实现，想了解下kl的特性，所以用Go语言写了一个解释器。其实对于写过lisp解释器的人都是老生常谈的东西。

eval/apply

最基本的就是eval(exp, env)，常量直接返回；符号就去环境里面查找定义；调用就是将实参和形参绑定，在新的环境里面apply闭包；lambda就将表达式，参数和环境一起保存起来，生成闭包。

lisp1 vs lisp2

kl是类似lisp2的，它有一点很特殊的地方：符号求值得到的是符号本身：

(4-) aaa
aaa

我比较熟习scheme，但是scheme是lisp1的。实现这个feature的时候我玩了一点trick：对符号求值的时候，先到环境里面找，找得到就当变量，找不到直接返回该符号。

((lambda x x) 1)  // 返回1，因为x被当作变量
((lambda x y) 1)  // 返回符号y，因为y在环境里面找不到，当符号处理

然后函数和变量用了两个不同的namespace，其实也就是hash表啦。

(set *v* (lambda x x))
(value *v* 3)

变量使用变量的hash表，而函数使用函数的hash表。

(defun f (x) (+ x 1))

变量就用set和value，函数定义就用defun。像比如

(value f)
(*v* 1)

都会出错，混着用都是不行的。

partial apply和自动柯里化

kl语言规范要求，它必须是支持partial apply的。也就是说：

(5-) (+)
#

函数+本来需要两个参数，如果不提供，它会返回一个partial的函数。支持partial是很好的，比如可以这样写：

(0-) (map (+ 1) [1 2 3])
[2 3 4]

而不用像scheme那样写成：

> (map (lambda (x) (+ x 1)) '(1 2 3))
(2 3 4)

怎么实现呢？其实很容易，判断一个参数是否足够，如果不够，当前的部分参数保存到环境中，生成一个新的闭包返回。当这个闭包下次有足够参数了，再被调用的时候，就继续完成运算。比如

(defun (add x y) (+ x y))

发现参数不够，自动生成一个闭包返回：

(add x) => (lambda (y) (+ x y))

由解释器自动改写就行了。

实现尾递归

kl语言规范要求，必须实现尾递归优化，即执行尾调用的时候函数栈不会增长。Go语言是不支持尾递归的，在一门不支持尾递归的语言里面，实现这个feature需要一点技巧，这个技巧叫做蹦床(trampoline)。

先看一个例子：

(eval
  (eval
    (eval
      (eval
        (eval
          (eval

虽然Go语言有分段栈，但仍然是有大小限制的。如果是这样递归下去，栈就暴掉了。一般函数式语言才要求尾递归优化，因为函数式语言里面递归太重要了，并且喜欢用递归来实现循环。

蹦床是这样一个技术：

func eval(ctl Control) {
     ...
     ctl.Finish = false
     return
}
func trampoline() {
     for !ctl.Finish {
         eval(ctl)
     }
}

eval函数需要递归调的地方，改成设置好标记并return，把eval丢一个循环里面，然后判断标记了做相应的动作。由于eval在循环里面是有机会返回的，所以栈不会一直涨，如此实现尾递归。

其实partial和尾递归都还好，异常机制麻烦一点。kl里面有两个异常处理相关的东西：

(simple-error str)
(trap-error (exp xxx) (lambda x (handle x)))

前者会生成一个error对象，而trap-error则是一个特殊表，它先执行里面的表达式(exp xxx)，如果成功就直接返回，如果是error，由将error传给后面的exception handler去处理。

在异常处理这一点上，我觉得kl做法是对的。对比scheme，曾经觉得continuation高大上。现在仔细想想，虽然用continuation是可以实现所有异常机制，但是continuation太难实现了。异常处理属于corner case，所以比较麻烦，adhoc的东西麻烦一点也就那样了，而如果为了解决一个比较麻烦的东西，去实现更麻烦的continuation，这不是缘木求鱼么？

解释器里面的异常处理并不复杂，在前面有了尾递归的基础之后，做异常只需要改一个地方：

func eval(ctl Control) {
     ...
     ctl.Finish = exception
     return
}

标记一下异常，然后直接到trampoline去处理。

其实是整个上个周末花了二三天的时间撸的一个东西，结果有几个小坑，导致今天才勉强调通了。上代码。注意到这个项目名用的是shen-go而不是kl，其实还是有一点野心的。先写一个解释器熟习一下语言规范，后面考虑做字节码编译器，以及整合Go丰富的标准库。

想体验一下的同学可以这么玩：

go get github.com/tiancaiamao/shen-go/cmd/kl
cd $GOPATH/src/github.com/tiancaiamao/shen-go
$GOPATH/bin/kl -s shen.kl

Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 20.1
running under Go, implementation: gc
port 0.0.1 ported by Arthur Mao

(0.000000-) (define fact
        0 -> 1
        N -> (* N (fact (- N 1))))
fact

(1.000000-) (fact 5)
120.000000

更多细节就参见Shen的官网了。