Scheme编译到汇编

By guenchi at 2017-12-13 • 0人收藏 • 221人看过

http://www.zenlife.tk/scheme-to-assemble.md


本文将描述如何一步步将scheme编译成汇编代码。这些编译过程其实对于其它高级语言都是同样适用的。

为了方便描述,这里挑选了scheme的子集,只选择了if begin set! lambda let这几个关键字。条件,循环,分支都是可以用这些关键字实现的。简单起见,基本数据类型也假设只有整数。

汇编有什么?寄存器,赋值,跳转指令。从scheme生成汇编代码,就是将条件、循环、分支消除,将变量变成寄存器。

闭包变换

closure-convert将函数提升到全局,消除闭包。

(let ([a 3])
    (lambda () (+ a 1)))

这里就是一个闭包,a是自由变量。经过闭包变换,lambda被变成了code表,闭包使用closure表生成:

(program ([f$1 (code (a) ()
                (+ a 1))])
    (let ([a 3])
        (closure f$1 a)))

一个闭包对象包含了代码,以及自由变量。这里分别是f$1和a。

去掉let

remove-let将let表去掉,并引入了locals表。

(let ([a 3] [b 5])
    (+ a b))

被变化为:

(locals (a b)
    (set! a 3)
    (set! b 5)
    (+ a b))

简化结构

remove-complex-opera将嵌套的操作扁平化。事实上,到目前为止if begin set!以及函数调用都是可能相互嵌套的,一个语言的结构可能十分复杂,比如说:

(locals (a b c d e f w)
    (set! a (if b (begin c (set! d 6) (f e (+ d 1))) w)))

可以引入一些中间变量,在不改变语义条件下,将代码结构进行简化。

(locals (a b c d e f w t1 t2 t3)
    (begin
        (if b
            (set! t1
                (begin c
                        (set! d 6)
                        (set! t2 (+ d 1))
                        (set! t3 (f e t2))
                        t3))
            (set! t1 w))
        (set! a t1)))

看起来还是挺复杂,举个更简单的例子吧:

(f (+ a b))

会被变成

(set! t (+ a b))
(f t)

简化之后,每次都只执行一步的操作。

调用协议

impose-calling-convertions执行函数调用协议。具体的,包括准备函数现场,进入函数调用,函数返回。

(program ([f$1 (code () (a b) (+ a b))])
    (f$1 5 6))

准备函数现场,(f$1 5 6)会被改写,只有参数的进栈出栈,以及跳转:

(set! in0 5)
(set! in1 6)

in0和in1分别是栈上的位置,用于传递参数。进入函数后会先从它们(栈上位置)获取参数。

(code ()
    (locals (a b)
        (set! a in0)
        (set! b in1)
        (+ a b)))

寄存器分配

assign-registers要将变成分配到对应的寄存器中。

(code ()
    (locals (a b t)
        (set! a in0)
        (set! b in1)
        (set! t (+ a b)
        (+ t 1))))

假设这里为a b t分配的寄存器分别是rbx rcx rdx,则经过寄存器分配后:

(code ()
        (set! rbx in0)
        (set! rcx in1)
        (set! rdx (+ rbx rcx)
        (set! rax (+ rdx 1))))

这里是把返回值放到了rax中。

去掉if

看似离汇编代码越来越近了。其实由于有if的嵌套的存在,还是可能有复杂的结构的。我们需要remove-if这个过程。它将去掉if,引入等价的跳转语句。

(program
    ([f$1 (code ()
        (if a (if b c d) e))]))

被改成

(program
    ([f$1 (code ()
        (if a (jump t$1) e))
     [t$1 (code () (if b c d))]]))

添加了一些跳转的标记,在if里面不会再存在嵌套的结构。

扁平化

flatten-program是会将代码拉平。现在的代码中,我们有一个全局的program字段,里面有很多的code段代码。

(program
        ([f$1 (code ()
            (if a (jump t$1) e))
        [t$1 (code () (if b c d))]]))

扁平化之后,就基本上等价于汇编了:

(program
    f$1
    (if a (jump t$1))
    e
    t$1
    (if b c d)
)

总结

scheme编译成汇编的过程,就是一步步的把if lambda set以及嵌套结构、变量全都去掉,从而将高级语言转化为汇编语言。让我们回头看一遍:

  1. 闭包变换--去掉了lambda

  2. 引入局部变量和locals表--去掉了let

  3. 简化结构以及调用协议--去掉了函数调用以及复杂的嵌套语句

  4. 寄存器分配--去掉了变量

  5. 去掉if

本文只不为了说清楚这个过程,把很多细节都简化了。存在赋值时其实不能直接做闭包变换的;string等数据类型也需要更多的处理;scheme很有特点的连续在这里也没有涉及;运行时更是很大的一块。


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...