Lua 的语言实现难度

谈到各种语言的实现,Lua 的 single-pass compiler 常被拿来说一番,似乎给人的印象是为性能牺牲了简洁。这个 compiler 的代码我一年前读过,做了些笔记。在复杂度方面,其实大体感觉比采用 explict AST 加单独的 code generating pass 的 compiler 并没高多少。在某些情况下,OP code generator 里晚些运行的步骤要为之前步骤已经生成的代码打 patch。主要集中在表达式计算结果的寄存器分配,以及分支语句跳转的目标地址上。

不过,为了 compiler 的实现简洁,Lua 还是「偷偷」地保留了一棵「语法树」。我并不是说像 FuncState 这样在 compile-time 按需生长的暂态树,而是一棵最终保留到运行时的常青树。它的结点为 struct Proto,表示源代码级别的 lexical scope function 的嵌套关系,也就是通常所说的 closure 定义。

在接触 Lua 实现之前,我最好奇的就是如何设计一个支持 closure 的指令集。看了 Lua 的实现之后,突然觉得有种「受骗」的感觉,因为对 closure 的处理明显不是用一般意义上的「指令」实现的。当时我还发了一条 Twitee 说「Lua 指令集要是做成真的 CPU 应该算是 extremely complex instruction set」。回头再想想,其实就是一个粗节点的 AST。所以 Lua VM 除了运行虚拟指令集,还混合了直接解释 AST 的方式。这点有效的控制了 compiler 的复杂度。

Lua 坚持采用手写的 single-pass compiler 的主要目的是满足作为「数据描述」语言的需求。这里有一个有趣的「迂回」。大多数「数据描述」语言其实并不需要 single-pass compiler 也能满足性能需求,因为它们的应用场景到 AST 为止,根本谈不上后面的 code generation —— AST 就是它们描述的数据,即 declarative 形式。但这也限制了这些语言的描述能力。Lua 通过 compile 舍弃了大多数 AST 信息,再运行 OP code 恢复和 AST 类似的数据结构。看似做了些「无用功」,但是最后的数据并不一定要和源代码的语法完全一致,灵活性远胜 declarative 形式的数据描述语言。

Lua 的 single-pass compiler 算是用一套 imperative language 的方案兼顾了大多数 declarative data expression 的需求。追求性能的同时,仍然保留了粗粒度 AST 降低实现复杂度。是个比较完美的折衷。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s


%d 博主赞过: