Lua 的语言实现难度

2016/06/10

谈到各种语言的实现,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 降低实现复杂度。是个比较完美的折衷。

合理的肮脏

2016/05/11

2016-05-10-AutoBodyShop

上班时因为没及时换 lane,所以选了另一条路,经过一个整形喷漆的修车场。场外停满等待修理的车,每辆身上都有些变形和漆面擦落。整个环境充斥着萧条的气氛。

当然,在商业环境讲求效率的标准下,我们被教导了要「学会用正确的方式看待『整洁』」。

It took me a couple of months … before I realized what they meant. In the bakery, clean meant no dough on the machines. Clean meant no fermenting dough in the trash. Clean meant no dough on the floors.

Clean did not mean the paint on the ovens was nice and white. Painting the ovens was something you did every decade, not every day. Clean did not mean no grease. In fact there were a lot of machines that needed to be greased or oiled regularly and a thin layer of clean oil was usually a sign of a machine that had just been cleaned.

类似的视角并不限于商业。例如,我们都希望住进有专门车库的房子。不仅仅为了存放车辆,更是希望一些爱好的副产品远离起居室。在明亮的起居室欣赏飞机模型的时候,车库里存放着一张不必每天收拾的工作台,上面散布喷漆的污渍。

如果这种「合理的肮脏」均分在每个人的生活中,不仅是应该的,甚至是完美的点缀。可是在从微观到宏观的层面上,最优效率的组织方式都是类似的 —— 这是上面 Joel 的 blog 里毫不费力的用面包房来为后文的代码组织做类比的合理性所在。在某个层面上,合理的肮脏所跨越的范围必然覆盖到某些人群绝大部分生活空间。像上面的修车场附近的居民区,对他们来说,打开窗户就能看到,走出房门就会接触到的修车场并不像一个享受爱好之后就可以离开的车库。我写这篇 blog 的原因正是联想到类似的情形在地区和国家的层次上,对于在「车库」里的人来说,生活并不是那么愉快。

Functional UI Programming

2016/01/13

最近挤出些时间来看 Haskell 和 Functional Reactive Programming。由于主要工作领域和兴趣都是 user interface,所以就一知半解地写写用 FP 实现 UI 的想法。关于这方面入门者的困惑很多,我觉得有两个主要原因,第一是 FP 社区本身对 UI 领域投资不多;第二是比较熟悉 FP 的人谈及 UI 的时候必然会提到,而且往往只提到 FRP。这第二点让人产生传统的 model-view-controller 不适合 FP 的错觉。

Model-View-Controller Recap

谈论 FRP 前先回顾一下在我本人经历中占主导地位的传统 MVC 模式 [1]。这种模式中的 V 是 stateless view。从 model 发送到 view 的唯一通知是「model 发生了(详情不知的)改变」。Stateless view 可以天然的被看作 FP 意义上的函数,参数是 model,输出是整个或部分 UI 的 bitmap(或者说是 render 系统的 render command 序列)。

这个模式下的 controller 和 model 也都几乎可以看作函数。如果采用 FP 模式,model 不能是保存状态的「对象」[2],而是变成一个 immutable 文档的列表。这样做并没有初看上去那么复杂:现代基于文档的 app 都要支持 undo/redo,所以如今的 model 已然无论如何要花力气实现文档列表(这个序列里的新文档通常是对旧文档进行 copy on write 得到,如果 FP compiler/runtime 实现得当应该可以达到同样效果)。

如上所述,我的最初感觉是传统 MVC 能够并不费力的和 FP 模式吻合,所以一再听到熟悉 FP 的人说 FRP 是 FP 在 UI 领域的主流甚至唯一解决方案让我有点惊讶,怀疑是否之前的想法过于简单化。

控件化 UI

上文谈到「传统 MVC」时所说的 view 其实和大多数人脑中的稍微有些不一样。很多 UI 是由现成的控件 (toolkit control) 组合而成。而传统 MVC 的 view 是指由 render 系统生成的一块 bitmap。举例来说,直接基于 Cocoa 和 MFC 的 NSView 和 CView 实现的 custom view 更符合 stateless view 的特性。如果你的 app 里没有 custom view,而是完全由 built-in control 组合而成,那么最外层的 container view 接受 model 之后的输出就不是 render command 序列,而是把整体的 model 分成不同部分来更新 inner view 的 model。在《MVC:用来打破的原则》的最后一节谈到了这种嵌套 MVC 结构。

控件化 UI 让很多程序员产生了一种「错觉」,就是 MVC 里的 view 的行为不是 render bitmap,而是把 model 的某部分同步到某个 property 上去。而 view 也变成了需要维护自身状态的对象。其实这只是看问题的角度不同。当你要自己实现足够复杂的 custom view,例如一个 editable canvas 时,仍然要回到基本的 stateless view 模式。经常写 custom view 的人处理大量 controls 的时候也把 controls 的更新看作 container view 的一种 render 行为而非数据的同步。

Functional Reactive

这时回来看 Functional Reactive Programming,它是更符合控件化 UI 的一种解决方案。FRP 所构建的 DAG 的末端和 control 相联的 event 或者 behavior 是和这个 control 自身的 model/proprty 的粒度直接对应。当整个 app 没有一个统一的 model 而仅仅用 controls 自身的 model 集合来维护所有状态的情况下,FRP 的 DAG 解决了这个 model 集合的同步问题,从而构建了一个 virtual global model。在传统 MVC 里经常提到 model 要负责 data integrity,DAG 正是实现这个任务的一个特定的形式化方法。

基于这个分析,可以总结关于 FRP 的三个结论。第一,FRP 解决了离散的 model 集合的同步问题,这只是 MVC 中 M 的部分。把 FRP 看作一个 UI 解决方案是忽略了 built-in control 所做的 render 工作。FRP 是一个 model 同步方案。

第二,可以通过在 app 中保持一个集中化的 model 来避免使用 FRP 的 DAG。集中化的 model 更符合传统的 MVC,从而也可以通过 stateless view 来采用 FP 模式。但这不代表构建集中化的 model  就一定是更好的做法。因为在控件化 UI 里强行采用 stateless view 模式意味着蛮力复制很多没有变化的数据。如果 FRP 的理论足够扎实,它的 DAG 似乎是更优雅的方法。而且即便真的采用了集中化的 model,仍然可以在内部采用类似 DAG 的方式来保证 data integrity。

第三,当 UI 中的某个 view 足够复杂而无法由 built-in control 来实现的时候,至少在这个部分必须回到传统的 MVC 模式。所以 FRP 和传统 MVC 实际是在 UI 实现里互相补充的两个部分。倾向于哪一个的决定往往更多地取决于系统性能等等非架构因素,而并非由系统的架构硬性决定,也不是和 programming paradigm 绑定的。

脚注:

  1. 关于这方面我写过几篇 blog()。
  2. 《MVC:用来打破的原则》里说过,model 其实有「反对象」的特性。

怎么做 Code Review

2015/10/04

Code review 是人人都明白要做的东西,不过做得得心应手的不多。好的实践要解决两个问题:第一是发现 code 的问题;第二是把问题正确传达给所有参与者 (reviewers) 。

通常说 code review 工具就会提到 GitHub 的 pull request,或者 Code Collaborator。这些工具解决的是第二个问题。比如说怎么知道其他 reviewers 是否已经提出相同的问题。或者 author 对某个 reviewer 提出的问题是否有了回应,refine 的对不对。诸如此类问题,不能说不重要。但只是 code review 的两方面之一。交流问题的前提是发现问题。眼光局限于上述这些工具,就是以为大家在一起聊着聊着问题就被发现了。问题绝不是靠盯着 pull request 或者 Code Collaborator 的 change list 页面看看就能自然而然地被发现。哪怕仅仅是两三行改动也需要放到整个 code base 中去检验。最好的 review 环境是既有清晰的 code change visualization,又能在整个 code base 里进行检索,还可以自由地运行修改前后的 code。PR 和 CL 提供了不错的 visualization,但缺少对后两点的支持。

所以 code review 的第一步是要把修改后的整个 code base,而不仅仅是修改本身的 visualization,共享给 reviewers。这种共享不但要让 reviewers 拿到 code change,还要能「玩起来」—— 能编译,能运行,能加入自己的修改来验证建议。

Git 这样的提供 cheap branch 的版本系统很容易做到这种共享。而 Perforce 的 branch 很 expensive,通常是几个人的 sub-team 共享同一个 branch。所以早先用 Perforce 的团队做 code review 往往就走马观花了。其实大概五年前推出的 shelve 功能就是专门为了 code review 设计的。Perforce 的 pending change list 相当于只有一个临时 commit 的没有历史纪录的 short live branch,同样能提供类似 rebase 的功能。Shelve 则提供了共享这个临时 branch 的能力。

共享问题解决之后,回头看 visualization 的问题。Perforce 在 branching 方面的弱点反而让 visualization 略显容易,因为缺乏历史纪录,所以大多数 IDE 都能自动把 shelved change list 唯一的选择 —— uncommited vs. committed 进行不错的可视化。而面对 Git 就比较头疼,因为 code author 在自己的 branch 里可以想怎么搞就怎么搞,开三五个 sub-branch 然后 merge,或者从别人的 branch merge 乃至 cherry pick 都算是 common practice。其实解决的方法也很简单,在本地做一个 uncommitted merge,然后 review 这个 merge。

最后多说一句闲话,Git 实践多了会发现 uncommitted merge 的用处不限于 code review。比如说,当 repo 里的 branch 很多的时候,在 SourceTree GUI 里看 logs 的时候会选择某一个 branch 而不是 all branches。如果这时还想对比另一个 branch 的情况就可以做一个 uncommitted merge。不过我还没想到把这个 trick 推广到两个以上 branches 的方法。

搬家

2015/09/23

来美国将近两年,一直住在同一个小区的 apartment 里。上个月终于买下了新房。之后就陆陆续续打包搬运。这是搬家前一周的景象。Apartment 里一直堆满了打包的东西。儿子在新家里看书。

一直到上周六,是在 apartment 的最后一晚。

感谢这间 apartment 承载了我在美国的最初时光。

不用 Lisp 学 Lisp

2015/03/22

发布上一篇 blog 一周后我离开北京来到了美国,当时没想到这一篇会隔了这么久才动笔。写 blog 一直是在 wordpress.com 上 draft 和发布,然后再复制到 techsingular.net 上。所以之前还在想搬来后写作条件也许会大大改善(因为 wordpress.com 众所周知的原因)。没想到一拖就是一年多。期间还两次忘记给 techsingular.net 的域名和主机续费。多亏杜超和 @mozetianxing 提醒。感谢大家一直关注。

大概两个月前开始有再写 blog 的想法。但中断这么久后一时不知道说点儿什么。或者说想写的还不少,不知从什么开始。这次终于动笔源自在 Twitter 上和张克炎 (@keyanzhang) 关于《 Lisp in Small Pieces 》的讨论。

另外说起「写作条件大大改善」,wordpress.com 的 editor 确实改进了不少。techsingular.net 的主机商也给免费升级了空间。Wordpress 升级到了 4.1.1。一年多真是很长的时间。

学编程语言理论的一个有意思的途径是读关于 Lisp 的书。但我并不想花精力摆弄任何一个 Lisp 的实现,更不要说先得从许多选择中挑一个。所以几年前就尝试在完全不安装 Lisp 环境的前提下读《 Structure and Interpretation of Programming Language 》。更确切地说,我的计划是在整个过程中用 Lua 逐步构建环境。现在看来这个计划很成功。SICP 中的 Scheme 代码都能简单对应为 Lua 代码。最后的小成果是用 Lua 写的 Scheme evaluator

当时的版本非常简单,不仅没有 macro,也没有著名的 first-class continuation (call/cc) 。我当然希望加上更复杂的 feature,离开北京前就开始看《 Lisp in Small Pieces 》(LiSP) 和《 The Little Scheme 》。不过这两个计划很快被搁置了。部分原因是大搬迁的影响。还有部分原因是兴趣转到了理解 Lua VM 本身的实现。因为 Lua 和 Scheme 如此类似,它的 VM 实现又非常简洁,特别是和 C 的交互部分做得比任何语言都好,所以对 Lisp 的兴趣很大程度上转化成对 Lua VM 的研究。几个月前恢复阅读 LiSP 后才意识到还有很大一部分原因是这本书的行文常常误导读者,没有不断改错的毅力实在读不下去。

在网上搜索对《 Lisp in Small Pieces 》的评价得到的几乎都是溢美之词。一本面向小众读者的专业书在 Amazon 上得到 12 个五星评价,不能不说这本书相当出色,覆盖了极广的知识、例子代码很详尽。但是它的问题也很严重,而网上一面倒的正面评价让我花了很长时间才确信阅读时遇到的很多困难并非自己的原因。简单的说,这本书犯了很多论文和教科书经常犯的错误 —— 证明推导时经常来个「显而易见」。它倒是很少在字面上出现「显而易见」,而是犯更隐蔽的等价错误:举例和结论之间经常有很多缺环  (gap)。

比如第 3.6.2 节 Tail Recursion 后半部分讲如何在 begin sequence 结束时省掉 continuation。这本来没什么问题。问题在于此节前半部分大幅以 fact (阶乘)函数举例。这个例子在多个层次上都有问题。首先是前文里有两个 fact 函数的例子:普通递归风格和 CPS 风格的。这无疑增加了读者误解的几率。

第二层问题是,普通风格的 fact 函数根本不是 tail-recursion。CPS 风格的虽然是 tail-recursion(而且也确实是文中用到的例子),但与其相关的 continuation 有两种:一是 CPS 风格代码每个函数的参数 k,二是 CPS 风格的代码和任何代码一样也有自己的 continuation。一般提到 CPS 时通常讨论第一种 continuation。第二种 continuation 几乎不会提及 —— 因为 CPS 风格代码都是 tail-call,可以说本身根本没有 continuation。《 Lisp in Small Pieces 》却反其道行之。用 CPS 风格代码举例,讨论的却不是参数 k,而是 (fact n k) 函数本身代码的 continuation。读到这里的时候,我先是花了好久都搞不懂要说什么。搞懂了之后又不明白作者为什么非要举这个例子。尽管这节后半部分的结论没问题,evaluator 代码的 tail-call 优化很简洁,但用来开篇的例子糟糕到不行。

接下来是一个同样糟糕的例子,引起了和 @keyanzhang 的讨论。在第 3.7 节 Partial Continuation 里有一个例子。

第一眼看上去,我很怀疑这段代码是否能按照文中所示返回 3 和 4。但我没有标准的 Lisp 环境,只有自己实现的还没有 REPL 的 evaluator。运行上面的代码的结果是死循环。所以我把问题发到了 Twitter 上。@keyanzhang 回复说他的运行结果如下,看起来和 LiSP 类似:

这就比较尴尬了…… 当初决定用 Lua 学 Lisp 时最大的顾虑是出了问题只能硬想,没有真正的 Lisp 环境用来参考。现在果然遇到了。不过话说回来,如果只用标准的 Scheme 环境,也许这个问题实验一下就过去了。现在有了真正的 Scheme 运行结果和我的 evaluator 的差异,问题可能出在两个地方:我的 evaluator 实现不对,或者又是一个《 Lisp in Small Pieces 》的行文问题。有过 fact 函数的例子,我比较怀疑是后者。第一,在第 3.1.5 节曾经有用 call/cc 模拟 goto 的例子,用那个例子来对比,这里的 (foo 3) 明显像 infinite loop。第二,和书上简单的代码片段不同,@keyanzhang 的例子是在 REPL 中。

经过痛苦的思考,终于发现正是 REPL 的原因。REPL 在每次收到 Enter 之后都用新的 bottom continuation 调用一次 evaluator,而不是调用一次 evaluator 运行所有代码。所以 REPL 中 (foo 3) 不是前面代码的 continuation,也就打破了 infinite loop。本来一直懒得给自己的 evluator 写一个 REPL,想通了这次困扰好几天的问题,立刻就写了一个。这回的结果终于和书上一致了。其实,无论是 @keyanzhang 的例子还是我最后的 REPL 结果都和原文并不一致,也不可能一致。

通过这两三年断断续续、磕磕绊绊的经历,说明熟悉编程的人完全可以只用 Lua 来学 Lisp。为什么要这么大费周章呢?下载一个 Racket、使用 Emacs 或者其它 Lisp 环境很难吗?因为我更喜欢 no-drill 的方式 —— 尽量用接近工作的环境来学习,不喜欢摆弄最终在产品中用不到的玩具。我们很少有人能在工作中用到 Lisp,大多数人学 Lisp 是希望借鉴思想。另一方面,Lua 已经在借鉴 Scheme 方面实践的很好,由于其 embedable/extendable 的特点又很容易在各种真正的生产环境中采用。所以希望研究 Lisp 所体现的编程思想,也可以尝试不安装任何 Lisp 环境。

Lua 的垃圾回收

2013/10/27

这篇 blog 是最近研究 Lua 垃圾回收 (Gabage Collector) 的笔记整理。研究 Lua 虚拟机源代码的完整笔记已经放到 GitHub 上。以后会不断更新。

GC 类型

很多关于 Lua 虚拟机源代码的文章往往危言耸听地把 GC 称作最难理解的部分,建议放到最后研究。我习惯用「深度优先」方式理解问题,很难说服自己完全不研究一个模块的内部,除非其接口文档非常正式,而且与系统其它部分相对隔绝。Lua GC 的接口虽然比较清晰,但也没有正式文档,并且不是单步 stop-the-word GC [1],其状态和虚拟机其它部分有很多关联。

研究 Lua GC 的第一个收获是 GC 方式的细致分类。首先 Lua GC 属于 root-tracing 这个大类。「Tracing」指通过对象之间的引用关系检查对象的 reachability,以是否 reachable 作为回收对象的标准。「Root」指 reachability 的源头,一般指全局变量 [2] 和当前 thread 的 stack。Root-tracing GC 一般采用 mark-and-sweep 策略。在 trace 阶段给所有 reachable 对象打一个 mark,然后进入 sweep 阶段,将没有 mark 的对象回收。最简单的实现是把 trace 和 sweep 两个阶段整个作为原子化过程,执行中不允许虚拟机执行 OP_CODE [3],这就是 stop-the-world GC。更为复杂的策略是把内存中的对象按照生命周期长度分成「代 (generation)」,每次仅对一代对象进行 mark-and-sweep 操作。而且对每代进行操作的频度不同,叫做 generational GC。如果设计合理,这种策略可以及时回收临时变量 [4] 又避免了对生命周期很长的对象进行过多不必要的 trace 和 mark。

为了实现的简洁,Lua 直到 5.1 都没有 generational GC。5.2 版本实现了这个策略,但是缺省处于关闭状态,而且设计者一再声明是一个实验性的功能,将来可能移除。目前 Lua 采取的策略是把 trace 和 sweep 两个阶段分成很多小片段,在执行各个片段之间允许虚拟机执行 OP_CODE。其代价是 GC 无法在一个周期中识别出所有 unreachable 对象,导致部分 unreachable 对象只有到下次「GC 周期」才能被回收。这种把 trace/sweep 分成多个片段的方式称为 incremental GC。

周期和步骤

既然提到了「GC 周期」,就先把一个周期的完整步骤 [5] 列出来:

  • Pause-设置 GC 的基本初始状态,特别是 root-tracing 中的 root;
  • Propagate-主要实现 mark-and-sweep 中的 trace 阶段;
  • Atomic-实现从 trace 阶段转到 sweep 阶段中不能被打断的原子化部分;
  • Sweep-string-实现 sweep 阶段中为 string 优化的部分;
  • Sweep-userdata-实现 sweep 阶段中对 userdata 的处理;
  • Sweep-Sweep 阶段的主要实现。

这些步骤的入口和跳转的逻辑在 singlestep() 函数中实现。

再说说 collectable value 的「颜色」概念。Lua 中需要被 GC 回收的 value 被称为 collectable value [6] ,其共有属性由 struct GCheader 实现,其中 field marked 表示一个 value 的「颜色」。Field marked 的 bit 0 和 bit 1 表示颜色是否为 white,bit 3 表示颜色是否为 black。但是一个 value 的颜色并不仅仅由 marked 决定。为了不引起混淆,我们把仅仅由 field marked 决定的颜色称为「marked 颜色」,把所有因素共同决定的颜色称为 value 的「颜色状态」。Lua 虚拟机的全局标志 global_State::currentwhite 用来解释 marked 的 bit 0 和 bit 1 哪个表示 current-white,另一个 bit 表示 other-white。

新创建 value 初始被置为「current-white 状态」。

Lua GC 的 trace 阶段对应于「propagate 步骤」,每次执行时搜索到的 reachable value 的 marked 颜色被设为「black」。这些 value 中有一部分 —— 比如 table 和 function —— 可以再引用其它 value  ( table 通过 key-value,function 通过 upvalue ) 。一个可以引用其它 value 的 reachable value 的 marked 颜色刚刚变为 black 之后,它自己会被放到一个称为 gray-list 的链表中。这种 marked 颜色为 black 且处于 gray-list 中的 value 被视为「gray 状态」。

在一次 propagate 「片段」中,Lua GC 会把片段开始前就已经存在于 gray-list 中的全部或者一部分 gray value 取出 (使它们成为真正的「black 状态」),把它们直接引用的 value 置为 black 状态 (如果是简单的不会引用其它 value 的类型,比如 string) 或者 gray 状态。一旦 value 处于 black 状态 ( marked 颜色为 black 并且不在 gray-list 中) ,在当前 GC 周期中就不再被检查。具体代码中这些工作由两个函数实现:

  • propagatemark()-将 gray-list 头部的 value 取出变成 black 状态,把它引用的其它 value 变成 gray 状态或 black 状态。这个函数代表 root-tracing GC 中的 trace;
  • markvalue()markobject()-接受一个表示 value 的参数,把这个 value 变成 gray 或者 black 状态。它实现的概念是 mark-and-sweep 中的 mark。

这两个函数相互配合实现 trace 过程 [7]:propagatemark() 直接调用 markvalue() / markobject() 来扩散 value 的 black 状态,markvalue() / markobject() 向 gray-list 中添加 value 来影响后续的 propagatemark() 调用。函数 propagatemark() 每次进行 trace 起点是 gray-list。上文提到过 root-tracing GC 的 root 是全局变量和各个 thread stack。关联这种「root」到 gray-list 的任务由 pause 步骤完成。Pause 步骤的实现主要在函数 restartcollection() 中,代码如下。

其中的 markobject(g, g->mainthread) 将 main-thread 放入 gray-list (即代码中的 g->gray)。在 Lua 中,全局变量存储在 main-thread 的 upvalue table _ENV 中。把 main-thread 放入 gray-list 就完成了对 root 的准备工作 —— 把全局变量,thread stack 与 gray-list 关联起来。至此我们简单讨论了 value 的颜色状态以及 pause/propagate 两个步骤。接下来看其它 GC 步骤。

函数 propagatemark() 不断从 gray-list 中取出 value,期间 markvalue() / markobject() 也会添加一些 value,不过最终 gray-list 会被取空,这时 Lua GC 进入 atomic 步骤。Atomic 步骤主要由两个函数实现:atomic() 和 entersweep() 。上图是 atomic() 函数的代码。在这个函数中 GC 把虚拟机中的所有 thread 以及一些已经处于 black 状态的 value 重新置于 gray 状态 (见 atomic() 函数中对 retraversegrays() 函数的调用及其前后的代码) ,随后进行数次不会被打断的 non-incremental trace (调用 propagateall() )。这几次临近 sweep 阶段前最后的 non-incremental trace —— 也可以叫做 atomic trace 确保所有 current-white value 都是 unreachable value。

即使到了这一步,Lua GC 也并未完全把 value 的 reachability 和颜色状态严格对应起来。Atomic 步骤确保的只是从 current-white 到 unreachable 的单方向对应。反方向并不成立,即 unreachable value 并不一定都处于 current-white 状态,因为有些 black value 在被 mark 之后才变成 unreachable 状态。这不影响 GC 的正确性,只是这些 unreachable value 要等到下个 GC 周期才能得到回收。这就是 incremental GC 的取舍:每次中断 OP_CODE 运行的时间都不长,但是一个「GC 周期」不能确保所有垃圾完全回收干净。

Atomic 步骤中的 trace 过程完成之后,atomic() 函数会修改 g->currentwhite (上图倒数第三行) 。 这就是上文说过的用来解释 collectable value 的 marked field 中 bit 0 和 bit 1 意义的 flag。这次修改令所有 current-white value 立即转到 other-white 状态。至此,为 sweep 阶段所做的准备已经基本完成。Sweep 阶段的主要任务是回收 other-white 状态的 value,又称为 dead value。

这里还有一个例外:atomic() 函数中调用的 separateobefnz() 函数把所有被 __gc mark [8] 过的 dead value 放到 g->tobefnz 链表中。Sweep 阶段不回收这些 value,而是留待下次 GC 周期一开始调用它们的 __gc meta-method,之后把它们作为普通的没有 __gc mark 的 value 常规处理。这是因为 dead value 的 __gc meta-method 有可能把它自己重新赋给 其它变量,使其恢复 reachable 状态,这种现象叫做「resurrection」。Lua GC 不能用 mark-and-sweep 检测 resurrection 现象,否则 mark-and-sweep 算法会变成无限递归过程。Lua GC 采用的方法虽然 ad-hoc 但是也算取舍得当:一是定义了「__gc mark」这个概念,缩小了 __gc meta-method 起作用的范围 [9]。二是在当前 GC 周期中不回收 __gc marked value。在下一个 GC 周期中这些 value 失去「__gc marked」资格 (除非它们再次在代码中被显式的 __gc mark) 后再做普通处理。本文一开始说过,很多讲 Lua 虚拟机的资料建议尽量推迟对 GC 的研究,也是因为 Lua GC 在简单的 mark-and-sweep 算法上添加了很多特殊情况的处理。

如果在 atomic 步骤执行的 non-incremental trace 耗时太长,就会影响 Lua 虚拟机执行 OP_CODE 的性能。因为之前的 propagate 步骤已让大部分 reachable value 处于 black 状态。此时需要 trace 的只是各个 thread 被置为 black 状态之后新创建的 value。这时有一个疑问,因为 thread 被置为 black 的时间点在一次 GC 周期中并不是非常靠后 [10],那么 atomic trace 处理的 value 是否会非常多?有两个因素保证这个担心是不必要的:

  • 在 atomic 阶段真正要被处理的 value 实际上少于「thread 被置为 black 状态之后新创建的 value」。因为在 thread 被置为 black 状态之后创建的 value 中有一部分还被 gray-list 中的其它 value 引用,这样的 value 在 propagate 阶段就会被 trace。
  • 那些在 thread 被置为 black 之后新创建的,而且没有被其它 gray value 引用的 value,大多仅被 stack 上的 local 变量引用。到了 atomic 阶段,这些 local 变量中很多已经离开了自己声明的 block,相应的 value 处于 unreachable 状态 [11]。所以 atomic trace 不会处理它们。到了后面的 sweep 阶段,因为它们处于 other-white 状态,会被回收。

接下来,atomic 步骤的 entersweep() 函数会把所有 collectable value 放入几个 sweep-list 链表。然后 sweep 阶段的几个步骤会遍历这些链表,回收其中的 dead value,把其中的 black value 变为 current-white 状态留待下个 GC 周期处理。因为 value 颜色状态的复杂逻辑已经在 trace 阶段处理完毕,sweep 阶段的逻辑比较简单,只需要注意一次回收的时间不能打断 OP_CODE 的运行太久。

内存分配

上面讨论的主要是内存的 trace 和 mark,简单的提了一下 sweep。还有一个方面没有涉及,就是在 GC 的每次运行片段之间 Lua OP_CODE 的执行所创建的新 value 如何影响 GC 的状态。上文只简单提了「新创建的 value 被标记为 current-white」。实际上,current-white value 总要有其它 value (称为「referrer」) 去引用它 (否则就让它一直 current-white 下去,直到 atomic 步骤变成 other-white 然后被 sweep 回收就好了) ,还可能随时增加新的 referrer。如果这些 referrer 是 current-white 或者 gray 状态,处理起来比较简单:只要等到 GC 去 trace 这些 referrer 就好。可对于 black 状态的 referrer,如果不做额外处理,GC 就不会再次 trace 它们,那么它们后来引用的 current-white value 就不能反应正确的 reachability 状态。

所以处于 black 状态的 referrer 和其它的 current-white value 建立新的引用关系时,涉及两种处理:

  • 如果该 referrer 引用其它 value 的关系比较复杂,Lua 虚拟机会调用 luaC_barrierback(),把这个 referrer 加回到 gray-list 中。
  • 如果该 referrer 引用其它 value 的关系比较简单,Lua 虚拟机会调用 luaC_barrier(),把新被引用的 current-white value 置为 gray 或者 black 状态。

这两个方法 ——  luaC_barrierback() 和 luaC_barrier() 是 Lua 虚拟机的其它部分和 GC 进行显式交互的主要接口。

此时还遗留了一个问题:local 变量和 thread。理论上来说,一个新创建 value 如果只赋给 local 变量,那么它是被当前 thread 通过 Lua stack 引用,也应调用上面的两个 barrier 函数之一进行处理。但前文说过 local 变量的生命周期不长,不值得每次给它们赋值时都把当前 thread 重新放回 gray-list 或者把赋值的 current-white value 立即置为 gray 状态。Lua GC 对这个问题的处理是给 thread 一个特殊的颜色状态:当 thread 从 gray-list 中被取出的时候,它被放到一个 gray-again-list 链表中,该链表在 atomic 步骤的 retraversegrays() 被放回 gray-list 由 atomic trace 处理。

由此可以看出 Lua GC 对临时变量的处理节省了 CPU,但是大大增加了它们在内存中存活的时间。这也是 Lua 在有大量临时变量的应用中占用内存比较多的原因。同时,过多的临时变量没有及时没识别出来,最后势必也会加重 sweep 阶段的 CPU 负担。所以 Lua 目前也在考虑如何利用和改进刚刚加入的 generational GC。

脚注:

  1. 后文说明。
  2. 从 Lua 5.2 开始,严格意义上 Lua 不再有全局变量。全局变量是 top-level chunk 的 upvalue _ENV 的属性。这个细节在后面讨论「pause 步骤」的时候会提到。
  3. Lua 的术语,相当于 Java 的 byte-code。
  4. 严格地说,这里的「临时变量」是指「只被临时变量引用的对象」。下文有多处描述类似。
  5. 本文把 mark-and-sweep GC 的两个大步骤 —— trace 和 sweep 称为「阶段」。把 Lua 的 incremental GC 实现的六个状态称为「步骤」。其中 Lua GC 的最后一个步骤也叫做 sweep,不要和「sweep 阶段」混淆。每个步骤并不是原子化执行,而是分成「片段」多次完成。
  6. 前文泛指 GC 讨论时用了「对象」这个名词。因为 Lua 不是单纯的面向对象语言,所以后文采用《Programming in Lua》中的术语:在 Lua 中,赋给变量的东西叫做「value」。Lua 的 value 有九种类型:nil, boolean, number, string, table, function, userdata, thread。其中 string, table, function, userdata, 和 thead 是 collectable value。
  7. Mark-and-sweep GC 中的 trace 阶段是 mark and propagate mark。其它类型的 root-tracing GC 的 trace 操作不一定如此,比如 copy-and-sweep GC 的 trace 阶段执行的是拷贝对象。
  8. __gc mark」是指给一个 value 设置 meta-table 时,后者就包含 __gc meta-method。给一个 value 已有的 meta-table 添加 __gc 方法并不是「__gc mark」,所加的方法也不会被 Lua GC 调用。
  9. 其它 meta-method 只要在相应的 meta-event 出现时存在,就会被调用。而 __gc 必须在设定 meta-table 时就存在才会被 GC 调用。
  10. 考虑到上文所说,只要 Lua Registry 中的 value 和 meta-table 被 trace 完毕,Lua GC 就会去 trace main-thread。这时只要 main-thread 的 upvalue 和 stack 上的 value 被置为 gray 状态,main-thread 就会完全变 black。
  11. 唯一引用它们的地方 —— stack,已经 shrink 回不再包含它们的状态。

Visual Basic Multi-Paradigm

2013/10/11

在软件业和计算机学术界有人「痴迷于」函数式编程 (functional programming) ,认为 imperative 编程是软件质量的「evolution dead end」。也许函数式编程可以通过某种方式 (比如 functional in small, OO in large) 体现其价值,但「痴迷 (obssesed)」状态大都没有太好的结果,更不用说在痴迷的基础上对 everything else 加以危言耸听。

为什么函数式编程处在有人痴迷但是又被边缘化的矛盾现状?很难做出严格的论证。不过最近帮朋友改进其公司财务报表工具的经历很有启发。他公司的「财务报表工具」其实很原始,之前就是手工用 Excel 计算,我的「改进」是写了两个根据原始数据表格自动生成总结报表的 Visual Basic for Application 程序。这个改进不大,但确实把这项任务每月两天的工作量变成了 20 分钟。程序本身只需 10 秒钟,因为写得比较粗糙,人工检查并且处理特殊情况需要另外 20 分钟。所以,Excel 可能是这个星球上最伟大的计算平台 —— 除了它那个不能 pause 的 debugger 导致一旦有死循环就必须 kill Excel。

在我义务帮忙之前,公司里另一个使用 Excel 多年的非程序员高手也曾想解决这个问题。顺便说一下,他的职务是财务副总监,所以对于义务帮忙这件事情我没感到太掉价。「非程序员 Excel 高手」就是对除 VBA 以外的所有 Excel 功能非常精通的人。他周末加班制作基于 Excel 公式的自动化工具。结果是可悲的,每次打开他的工具,Excel 会僵死两分钟,使用者需要掌握复杂的使用规则,好几个小时的培训,表格里满是专为存储中间结果用的 cells,甚至可以说整个表格结构都是为了机器处理而不是人阅读设计的。

其实我一度羡慕那些熟练掌握 Excel 公式的高手。为 Excel 写 VBA 总有种在 Unix 里批量拷贝文件不用 shell script 而去写 C 程序的感觉。「Excel 公式」难道不是更 native 的 Excel 手段吗?直到这次,我遇到了:

  • 复杂到处理月度报表程度的问题;
  • 编写 VBA 程序解决这个问题的经历;以及
  • 看了可怜的公式高手的方案。

我突然明白了,VBA vs. 公式正是 imperative 编程与函数式编程的 paradigm 差别。很久以来,Excel 都是一个 multi-paradigm 的计算环境。更有趣的是,它首先是一个函数式环境,而随后增加的高级功能 —— VBA 才是学术谜们不喜欢的 imperative 编程方式。

为什么有些人对函数式编程寄予厚望。也许不是因为学术痴迷,而是简因为「函数式」的的确确是更容易被理解的概念。哪个用户会不理解 Excel 公式呢?在 cell 里写上一行「=sum(c1:c10)」就全齐了!而 VBA 是什么可怕的东西 (还有那个弱智 debugger) ?但 Excel 公式这种看似简单而且可以无穷组合的工具,实际上在适用问题的复杂度方面不能 scale。VBA 方案的代码量会随着问题的复杂度线性增长,基于公式方案的表格复杂度则会指数增长。VBA 方案并非完美,不过也许只是还缺一个更好的 debugger 而已,一如 imprative 编程。

Closure 与 Unbound 变量

2013/09/08

大凡了解或编写过简单 Lisp 解释器的人都知道 unbound 变量这个概念。如下面这段代码 [1],对其中用 lambda 创建的匿名函数来说,balance 就是一个 unbound 变量。(对于 make-withdraw 函数来说,balance 是 bound 变量。)

Unbound 变量的求值通过 Environment Model 来定义 [2]。程序运行时的 environment 由 frame 构成。每当一个函数被调用执行时,解释器会创建新 frame,称为当前代码的 execution frame [3];定义新函数时当前 execution frame 作为被定义函数的 associated frame,当前被执行函数的 associated frame 作为被定义函数的 associated frame 的 enclosing frame。所有的 bound 变量(局部变量)都在当前 execution frame 中定义。在当前 execution frame 中未定义的变量的取值要到 enclosing frame 中去查找,被称为 unbound 变量。

Environment Model 是一个很容易理解的简单概念模型,但直接将其对应到具体实现中会导致一些问题。所以基本上只有用于教学练习目的的解释器才会直接采用这种模型。这样的一个结果是,很多从未了解过解释器理论仅是使用动态语言编程的人并不了解这个概念模型,只知道和具体实现比较接近的术语 —— closure 和 lexical scope。但是,因为比较接近底层实现,closure 和 lexical scope 概念体现的实现方面的意义掩盖了其语意本质,成了高级动态语言中很难理解的部分。理解这两个术语需要了解它们对 Enviornment Model 做出了什么取舍。

在原本的 Enviornment Model 中,unbound 变量的求值要根据运行时的 enclosing frame 一路向上查找,性能开销很大。从名称上可以看出,lexical scope 则是一个静态机制,源代码的静态结构 (lexical scope) 完全决定了 unbound 变量的取值来源 [4]。Lexical scope 消除运行开销,代价是语言能力稍许弱化。从概念本身来说,定义一个函数并不等同于定义一个 nested 函数 [5]。完全可以把被定义函数本身的代码和该函数「被定义」的位置分离开,让 lexical-scope 和函数的定义不再有对应关系。一种典型的方法是 load 另一个源文件(或者一个表示代码的字符串),比如 Lisp 的 eval 和 Lua 的 load。目前主流动态语言中的 lexical scope 则完全是静态机制,只支持同一源文件中的 nested 函数定义。如 Lua 的 load 之类的动态机制不支持 unbound 变量。所以,严格地说,大多数动态语言的 closure 并不是和 Enviornment Model 一模一样的。

另一个有趣的问题是 lexical scope 为什么又被称为 closure。直接采用 Environment Model 的简单解释器大多由高级动态语言编写,所以可以直接利用 hosting 语言的高级特性。比如前面提到过的(脚注 [3])execution frame 借助 hosting 语言的 runtime stack 来实现被解释语言的 call stack,而且依靠 hosting 语言的内存管理机制来管理 frame 的生命周期。当一个 frame 不再是当前的 execution frame 时,它的生命周期完全取决于是否还有以其作为 associated frame 的函数存在。这种判断往往直接利用 hosting 语言的 GC 完成。这种 hosting 语言本身高度抽象化的实现中是不必有字面上和「closure」相关的概念的。

工业级别的解释器一般用没有 GC 的静态语言实现,显式的实现被解释执行代码的 call stack,函数没有直接对应的 associated frame,仅在逻辑上将 upval [6] 对应到 call stack 中的变量。如果 nested 函数可以作为返回值从定义它的 nesting 函数中传出,就会出现 upval 的生命周期长于对应的 on-stack 变量的情况。所以,当一个函数返回时 —— 也就是当前的 call stack frame 被销毁时,若其中有 on-stack 变量对应到 nested 函数的 upval,它们(或者它们的 references)必须被拷贝到解释器中维护 nested 函数本身的数据结构中。这种操作称为 upval 的「closing」,也就是「closure」名称的由来。因为一般来说只有可以作为函数返回值的 first-class function 才会需要 closing 操作,所以 closure 对应的全称是 first-class function with lexical scope。

脚注:

  1. 摘自《Structure and Interpretation of Computer Program》(SICP)。
  2. Environment Model 的概念同样来自 SICP,见第 3.2 章。
  3. Execution frame 实际构成了程序运行的 call stack。但是在基本的 Environment Model 中,这些 frame 之间没有显式联系,真正的 call stack 由解释器维护。直接采用 Environment Model 的解释器一般比较简单,近似或者就是一个递归求值器 (recursive evaluator),所以 call stack 由解释器本身的 runtime stack 来维护。
  4. 大多数高级动态语言都编译为 byte code 运行。所以,类似静态语言,可以说这是「compile-time」机制。
  5. 全局函数也是「global scope」中的 nested 函数。
  6. 由于 lexical scope 和 Environment Model 意义并不完全相同,所以这里改用 Lua 的术语「up value (upval) 」而不再使用 Environment Model 的术语「unbound 变量」。

Programming in Lua(六)-Continuation

2013/07/14

在之前的 blog 中 () 讨论了 Lua C APIs 的 continuation 概念。可以说 Lua continuation 的 VM 实现和 APIs 设计是「inevitable and perfect design」,一个支持 coroutine 的 embeded/extendable 语言就得这么设计。但是前几篇 blog 还没有完全解释 continuation 如何在整个 coroutine 机制中起作用。

图 6-1 是 Lua VM 运行时的 stack 的示例。Lua VM 是 stackless 设计,图中 Lua stack 和 C runtime stack (CRT stack) 并立,两者 stack frame 的对应关系已被标出。橙色部分表示  CRT stack 上一些 Lua VM 维护自身状态的函数,无法明确对应于 Lua stack 上的具体 frame。 此外还要注意几点:

  • Lua stack 是 dual-stack,stack frames 和 stack entries 分别存储在 struct lua_State 中的 CallInfo 链表和 TValue* 数组中。图上只画出了 Lua stack frames,而且没有画成链表形式,没有画出 Lua stack entries。但不妨碍讨论问题。
  • 为了简化图示,Lua VM 的一些次要函数没有在 CRT stack 上被画出,虽然在实际代码执行中它们会出现在 CRT stack 上。
  • 图中,「CallInfo (Lua)」表示 Lua 函数的 stack frame,「CallInfo (C)」表示 Lua 调用的 C 函数的 stack frame。不管有多少「CallInfo (Lua)」,只要它们在 Lua stack 上的位置是连续的,中间不存在「CallInfo (C)」,对应到 CRT stack 上都是一级 luaV_execute()。这就是 stackless 的意义。
  • C 函数本身的执行不论有多少层函数调用,Lua stack 上都只有一个「CallInfo (C)」。当然 C 函数可以通过 lua_*call* [1] 来间接地调用另一 C 函数,这时 Lua stack 上会出现相邻的多个「CallInfo (C)」。但本文不涉及这种情形。

接下来看看两个 stack 在运行中如何增长和恢复:

  • luaV_execute() 取到一条 OP_CALL 指令的时候,会调用 luaD_precall(),该函数调用 next_ci() 增长 Lua stack。如果被调用的是 Lua 函数,CRT stack 保持不变。
  • luaV_execute() 取到一条 OP_RETURN 指令的时候,会调用 luaD_postcall(),该函数会恢复调用前的 Lua stack。注意只有 Lua 函数才有 OP_RETURN 指令,C 函数只是简单返回并且恢复 CRT stack。
  • 如果 luaD_precall() 发现被调用的是 C 函数,它会调用该函数,并在其返回之后调用 luaD_postcall() 来恢复调用前的 Lua stack 状态。
  • 在 C 函数中通过 lua_*call* API 调用 Lua 函数时,lua_*call* 会间接地调用 luaD_precall(),该函数会调用 next_ci() 来增长 Lua stack。并且会调用 luaV_execute() 运行被调用的 Lua 函数。此时 CRT stack 上会出现多个 luaV_execute() frame。只有在两种情况下 CRT stack 上出现多级 luaV_execute() frame,这是一种情况,另一种情况是 coroutine,下面说明。除此之外,CRT stack 不会出现多个 luaV_execute() frame。
  • 如果一个 Lua 函数是被 C 函数直接调用的,它返回的时候执行它的 luaV_execute() 也会返回 [2]。这时作为 caller 的 C 函数会继续运行。

接下来考虑加入 coroutine 之后的情形。首先考虑只有 Lua 函数的情况 [3]。图 6-2 中,最初只有一个属于 main thread 的 Lua stack (在图的左下方)。在 main thread 中创建一个 coroutine,并且对其调用 coroutine.resume()coroutine.resume() 调用 luaV_execute(),这时 CRT stack 上有两层 luaV_execute(),分别对应 main thread 和 coroutine。由于最顶层 luaV_execute() 的参数是 coroutine 的 struct lua_State,「当前的」Lua stack 从 main thread 切换为 coroutine。注意,Lua 并没有显式的数据结构表示「当前的」thread,处于 CRT stack 顶端的 luaV_execute() 所对应的就是当前的 thread 和 Lua stack [4]。

在 coroutine 中发生 yield 时 Lua VM 会调用 longjmp() 回到原来 lua_resume() 执行的地方,导致 CRT stack 恢复为 resume 时的状态,从而恢复执行 main thread 对应的 luaV_execute()。如果不出现 C 函数调用 Lua 函数的情况,而且 yield 始终发生在 Lua 函数中,那么 coroutine 的切换就是简单的调用  luaV_execute() 和 longjmp()

现在考虑在 coroutine 中调用 C 函数。图 6-3 显示了在 coroutine 中 Lua 函数调用了一个 C 函数,后者又调用了 Lua 函数的情况。

如果此时调用 coroutine.yield()longjmp() 会恢复 CRT stack (灰色阴影部分被销毁),C 函数的 callstack 将丢失。如果 main thread 再次 resume coroutine 之后,stack 如图 6-4。

这时的问题在于如何处理 coroutine 中的「CallInfo (C)」。两个原因决定了这个 C 函数的状态无法恢复。第一,原来的 CRT stack frames 已经在 yield 过程中丢失;第二,此时的 luaV_execute() 是由 resume 调用的,而不是原来的 lua_*call*(),所以顶层 luaV_execute() 无法返回到 C 函数中正确的代码位置。

这时 continuation 开始发挥作用。上文提到过,两种情况会导致在 CRT stack 上出现多级 luaV_execute():一是从 C 函数中调用 Lua 函数, luaD_precall() 调用 luaV_execute();二是 resume。两者的不同之处在于,前者调用的 luaV_execute() 返回之后, luaD_precall() 在进行一些简单处理之后也会返回;而后者调用的 luaV_execute() 返回之后会调用 unroll() 函数进入一个循环 [5]。在循环中,会检查当前 Lua stack 顶端是否为「CallInfo (C)」,如果是的话,会调用这个 CallInfou.c.k field。这个 field 就是 lua_callk()/lua_pcallk() 接受的 continuation 参数 [6][7]。

图 6-5 表示 continuation 起作用的情形。和图 6-4 相比,coroutine Lua stack 顶端两个「CallInfo (Lua)」消失了,其对应的 Lua 函数已经返回。由于接下来的 Lua stack 顶端是「CallInfo (C)」,所以最顶层的 luaV_execute() 返回。然后 resume() 调用 unroll(),后者再调用 stack 顶端的 CallInfou.c.k。此时 coroutine 在 CRT stack 上暂时没有对应的 luaV_execute(),等到 continuation 函数执行结束返回后,unroll() 中的循环会再调用 luaV_execute() 运行 coroutine 中剩下的 Lua 代码。如图 6-6 所示。unroll() 中的循环会不断检查 Lua stack 中的 frames [8],相应的执行 continuation 函数或者调用 luaV_execute() 运行 Lua 函数。所以在 coroutine 中不论有多少层 C 到 Lua 函数的调用,只要每次都提供正确的 continuation,就可以保证正确的 coroutine 切换。

由此可见,continuation 是专门为 coroutine 设计的概念。运行在 main thread 中的代码从 C 函数中调用 Lua 函数不用提供 continuation。

脚注:

  1. 本文用 lua_*call*() 来表示 lua_call(), lua_pcall(), lua_callk(), lua_pcallk() 一族 APIs。
  2. 一个 .lua 文件被调入 VM 之后被视为一个 Lua 函数。
  3. Lua 程序在运行时会经常调用 C 函数,不过这些 C 函数往往会很快返回。所以通常在 yield 时 Lua stack 上不会有「CallInfo (C)」存在。
  4. 对于一个 Lua VM 来说,始终只有一个 CRT stack。
  5. 这个不同仅仅针对经过至少一次 yield 之后被重新 resume 的 coroutine。lua_Statestatus field 标示了一个 coroutine 是第一次被 resume 还是被 yield 之后重新 resume。
  6. 实际上,在 yield 时 Lua VM 会检查被破坏的 CRT stack 部分对应的所有「CallInfo (C)」是否拥有 continuation 函数,如果没有就会抛出 error。
  7. 本文讨论的 yield 发生在 Lua 函数中 (stack 上有 C 函数,但是不处于顶端)。如果 yield 发生在 C 函数中,情况类似,只不过使用的是 lua_yieldk() 而不是 lua_callk()/lua_pcallk()
  8. 当然 unroll() 不会到检查每一个 frame。luaV_execute() 的一次执行就会「吃掉」Lua stack 顶端所有连续的「CallInfo (Lua)」frame。

关注

每发布一篇新博文的同时向您的邮箱发送备份。