the compiler for skime — from bottom up

July 9, 2008 – 11:47 pm

最近有空的时候也都在折腾 skime 的 VM ,虽然主要集中在 VM 上,但是写测试代码十分麻烦,每次添加一些辅助功能,最后猛然发现一个编译器的原型已经完成了。我仍然在尝试这种编程方式——并非一开始就把所有的东西都设计好,而是对一些简单的 case ,采用最简单的方法构建出一个可以运行的原型,再通过原型进行扩充。到目前为止似乎都感觉挺好的,因为许多东西都是万事开头难,有了一个大致框架之后剩下的事情就要简单多了,而且原型作为一个快速的可行性尝试也是很不错的。

在刚做出一个 VM 样子的时候,要测试必须手工写字节码,全是数字,写起来非常麻烦,而且一开始指令集也时常有改动,指令的 opcode 也跟着变动,改起来非常麻烦,于是我写了一个简单的 encoder ,从 opcode 的名字到数值进行转换,也算是方便了一些,测试代码可以这样写了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
proc = Procedure()
proc.bytecode = encode(["push_local", 0,
                        "push_1",
                        "equal",
                        "goto_if_true", 18,
                        "push_1",
                        "push_local", 0,
                        "minus",
                        "call", 0, 1,
                        "push_local", 0,
                        "multiply",
                        "goto", 19,
                        "push_1",
                        "ret"])

但是这样还是很不方便,在写 goto 等语句的时候跳转的地址要手工计算,而且代码一改又得更改,非常麻烦。而且,push_local 等指令都是直接指定局部变量的 index 的,非常不直观。于是我又加了一个 Generator ,这是一个稍微高级一些的用于生成字节码的接口,可以自动处理跳转的地址、 局部变量、常量等。于是测试代码变成了这样(这是一个经典的递归计算阶乘的函数,除了最开始的硬编码的字节码,后面的测试例子都是递归的阶乘函数):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
gs = Generator(parent=vm.ctx)
gs.def_local('fact')
g = gs.push_proc(args=['n'])
gs.emit('make_lambda')
gs.emit('set_local', 'fact')
gs.emit('push_literal', 5)
gs.emit('push_local', 'fact')
gs.emit('call', 1)
 
g.emit('push_local', 'n')
g.emit('push_1')
g.emit('test_equal')
g.emit('goto_if_true', 'ret_1')
g.emit('push_1')
g.emit('push_local', 'n')
g.emit('minus')
g.emit('push_local_depth', 1, 'fact')
g.emit('call', 1)
g.emit('push_local', 'n')
g.emit('push_local_depth', 2, '*')
g.emit('call', 2)
g.emit('goto', 'ret')
g.def_label('ret_1')
g.emit('push_1')
g.def_label('ret')
g.emit('ret')
 
script = gs.generate()

这里的 Generator 其实做了不少事情,在作用域中生成子作用域时会返回一个新的 Generator ,用于生成子作用域的代码。作用域在编译的时候是串联起来的,引用外层作用域的变量也由 Generator 自动进行查找。然而这其实还是没有跳出字节码的范围。像 Scheme 这样更加偏向函数编程的语言用这种看起来非常“命令式”的字节码表示出来似乎有些别扭。

一方面也是为了测试这种命令式的字节码和函数式编程风格结合在一起的可行性,我决定先添加一些 Scheme 代码到字节码的转换的功能进行测试。然而虽然 Scheme 代码的结构很简单,却也并不是一下子就可以写一个解析器出来,所以源数据选择了结构化的 sexp 而不是平坦的源文件字符串。我把这个过程叫做编译,于是测试代码变成了这个样子:

1
2
3
4
5
6
7
8
9
sexp = [sym("begin"),
        [sym("define"), sym("fact"),
         [sym("lambda"), [sym("n")],
          [sym("if"), [sym("="), sym("n"), 0],
           1, [sym("*"), sym("n"),
               [sym("fact"), [sym("-"), sym("n"), 1]]]]]],
        [sym("fact"), 5]]
sexp = list2cons(sexp)
script = compiler.compile(sexp, vm.ctx)

其实在 Scheme 中也是如此,把字符串转换为 sexp 的过程称为 read ,在其他语言中通常称为 parse ,并且得到的结果通常是一颗抽象语法树 (AST) ,不过在 Scheme 中 sexp 是最基本的数据结构,Scheme 的代码本身也是这样的结构,而且其实 sexp 也可以被看作是一颗语法树。因为 Scheme 代码本身也是 sexp 形式的,所以对 sexp 进行求值成为 eval ,中间可能会有一个可选的 compile 过程。

不过用 Python 代码来描述 Scheme 的 sexp 并不是特别方便,可以看到在上面的例子中我用了一个 ad hoc 的 list2cons 函数来进行 listcons 的转换,从而避免了写一大堆嵌套的 cons ,然而还是到处都是 sym 的字样,如果是像 Ruby 那样有内置的 Symbol 类型应该会看起来稍微干净一些。

但是既然已经做到这一步了,我便又加了一些代码,写了一个简单的递归下降式的解析器,于是终于可以直接测试 Scheme 代码啦!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vm = VM()
compiler = Compiler()
 
code = """
(begin
  (define fact (lambda (n)
                 (if (= n 0)
                   1
                   (* n (fact (- n 1))))))
  ; compute 5!
  (fact 5))
"""
 
sexp = Parser(code).parse()
script = compiler.compile(sexp, vm.ctx)
vm.run(script)
 
print vm.ctx.pop()

再回头一看,发现自底向上一路上来,由于有底层的支持,上层的构建工作其实都比较顺畅。然而这样顺畅的“from bottom up”的方式似乎也强求不得,许多时候从最底层开始做的话往往会做出功能不全的接口或者违背 You Arent Gonna Need It 的原则。总之没有什么语言、模式是万能的银弹了,选择合适的工具也是程序员的一门艺术啊。 :D 或者说是运气?

Post a Comment