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。

Lua vs. Python

2013/05/13

在《 Programming in Lua 》系列里谈了 Lua 的 stackless 实现。说到 stackless 设计,难免和 Python 的 stackful 实现比较一下。

以前总有一个疑惑。为什么 Python 既要采用 native thread,又要用 great-lock 将其变成实质上的协作式 thread。像 Lua 这样的 coroutine 不好么?现在知道了,非不为,不能也。既要尽量保证虚拟机的可移植性,又采用了非常依赖 CRT stack 的 stackful 设计,语言本身没有 synchronous primitive,不能应付真正的 preemptive 多线程。这种情况下,多线程加 big-lock 是唯一的折衷了。由此也知道了 Python 的 generator 为什么只允许在第一层函数中 yield,因为 stackful 设计不允许保存 call stack (说老实话,只允许在第一层函数中 yield 的 coroutine 不过是两个函数调来调去,在 C 里实现起来也不难)。Python 3.3 开始支持更宽松的 yields,不过实现的方式和 Lua 的 yields-in-C 差不多,作为基于虚拟机的语言是比较原始的手段。

拿 Lua 和 Python 做比较令人恍惚感觉正在比较 Objective-C 和 C++。Lua/Python 和 Objective-C/C++ 都是在共同基础上发展出来:后者扩展 C 语言;前者用 C 语言实现基于 byte-code 的虚拟机。它们都有理想的「标杆」:Objective-C/C++ 的标杆是 Smalltalk/Simula 等面向对象语言先驱;Lua/Python 是 Lisp 这样的高级动态语言先驱。努力的方向都是降低「标杆」过大的性能开销和简化「标杆」过于复杂 (或者过于精简) 的概念。Python 和 C++ 相对较早的尝试,都采用了比较低级的机制:C++ 用函数指针模拟成员函数;Python 依赖 CRT stack 直接实现 byte-code stack。这些「第一次」都没能「do things right」。后来的第二次尝试才作出了更妥当的取舍。

在《 The Art of UNIX Programming 》里指出了系统设计的「第二系统综合症 (second-system effect)」。乔布斯也提到过「第二个产品」的问题。在一个成功的系统上衍生的第二个系统有时会因为没有理解第一个系统成功的真正原因而失败。但是,如果还有机会的话,由此衍生的「第三系统」往往会做得更好。对于上面所说的语言发展来说,它们的基础 (C 语言) 和「标杆」是「第一系统」,第一次改进的尝试毁誉参半,而后来的「第三系统」更加出色。

Programming in Lua(五)- Coroutine, Lua Stack

2013/05/09

在《 Programming in Lua(三)- Yields in C 》里讨论了 Lua 虚拟机对 yields-in-C 及其 stack 的处理。当时还未读 Lua 虚拟机的实际代码,只根据语言的行为来推测,有些术语也不符合通常用法。最近从 Lua stack 的实现入手,发现了一些以前没想过的问题:为什么 resumes-in-C 从来不是问题?为什么有 lua_yieldk() 而没有对应的 lua_resumek()

首先从术语的标准化说起。《 Programming in Lua(三)- Yields in C 》里有多处这样的描述:

  • 「stack 上 ⋯⋯ 的执行层次」;
  • 「virtual stack 上的 Lua 部分的 stack」;
  • 「Lua stack 段」。

其中「执行层次」、「部分」、「段」这样的字眼应该替换为「stack frame」这个更常用的术语。线程运行时,stack 呈现两层意义。一是后入先出的简单线性结构;二是把此线性结构划分成与函数调用层次一一对应的若干段,这样的一段就被称为一个 stack frame。大多数语言的 runtime 或虚拟机中,stack frame 并无单独的数据结构表示。在 64-bit x86 的 C runtime (CRT) 中,每个 stack frame 的首项是上一层 stack frame 的最低地址 (base),称为 stored frame pointer (SFP),最顶层 stack frame base 存储在 %ebp 寄存器中 。即每次生成新的 stack frame 时,首先将 %ebp 寄存器入栈形成 SFP,然后把当前的 %esp 赋给 %ebp。通过这种方式让需要解析 stack frame 的程序 (比如 debugger) 得到所需信息。(SFP 并非一定存在,臭名昭著的 omit-frame-pointer 编译器优化会去掉 SFP,这时 debugger 只能借助额外存储的 symbols 来解析 stack frame。)

就需求本身来说,Lua stack 要解决的问题比 C 复杂的多,甚至比同为动态语言的 Python 更复杂。基于虚拟机的语言的 call stack 有两种可能的设计:一是借用虚拟机本身的 CRT stack。Byte-code 的函数调用指令对应虚拟机本身 native 代码的函数调用,虚拟机的 CRT stack 随 byte-code 函数调用的层次增加而增长。二是由虚拟机维护额外的 call stack 数据结构。Byte-code 的函数调用指令和其它指令一样,在虚拟机的同一个循环中完成,虚拟机的 CRT stack 不体现 byte-code 函数的调用层次。后者通常被称为 stackless 方案,前者暂且对应称为 stackful 方案。

Lua 是 embedded/extension 语言,byte code 的运行总会夹杂 C 函数。这些 C 函数的 call stack 在逻辑上是 byte-code 运行状态的一部分,实际上则间杂在 Lua 虚拟机的 CRT stack 中 (在涉及 Lua 的情况下讨论 CRT stack 时,要始终说明是虚拟机的 CRT stack 还是 C 函数的 call stack)。从这个角度来说,embedded/extension 语言更倾向于选择 stackful 设计。但 stackful 设计的固有缺陷在于 stack 结构是平台相关的,很难用跨平台的方式实现诸多功能,比如协作式多任务 (cooperative multi-threading),跟踪垃圾回收 (tracing-GC),lexical closure。尽管不是全部原因,Python 缺少诸多高级特性与其 stackful 实现有很大关系。

为了遵守 ANSI C 的跨平台性和更好的实现高级动态功能,Lua 采用了 stackless 实现。这给处理 C 代码的 call stack 带来了一些挑战。Lua 的 stack 存储在 struct lua_Statestack field 中,是一个 TValue* 的数组。其内容包括:

  • 函数指针。Proto* (Lua 函数) 或者 lua_CFunction (C 函数)。注意函数指针不是函数的返回地址。
  • 函数的参数和返回值。包括 Lua 和 C 函数之间传递的参数和返回值。
  • Lua 函数的局部变量。

在这个 stack 上缺少一些属于 call stack 的东西:

  • C 代码本身的 call stack。
  • 函数的返回地址。
  • Stack frame 信息,类似 SFP。

这是因为 Lua 采用了双 stack 结构。对应的 stack frame 信息存储在一个 struct CallInfo 链表中,每个节点对应一个 stack frame,它对 TValue* 数组 stack 的描述如下:

  • Field func 表示 stack frame 在 TValue* 数组上的起始位置 (之所以用 func 作为 field 名称是因为在 TValue* 数组上这个位置永远是函数指针),field top 表示结束位置。
  • Field union u 存储和函数类型相关的信息。Lua 函数信息存储在 u.l 中,C 函数在 u.c 中。
  • u.l.savedpc 表示函数的返回地址。这个值仅当 Lua 函数作为 caller 的情况有效。C 函数作为 caller 时,返回地址在 CRT stack 中。
  • 当 C 函数中发生 yield 时,CRT stack 被破坏,该 coroutine 下次被 resume 的执行地址由 u.c.k 来承担。详见《 Programming in Lua(三)- Yields in C 》。

这里值得多说一句,为什么在 C 函数中执行 yield 会破坏 CRT stack?上文说过,Lua 的设计主要是 stackless 方式,其具体实现是通过 luaV_execute() 中的循环执行 byte code,通过额外数据结构 (其实是双数据结构) 而非 CRT stack 来维护 call stack。但在 resume coroutine 时,luaV_execute() 间接地递归调用自己并在 callee 的循环中执行 resumed coroutine。也就是说由 CRT stack 来维护 coroutine 上下文切换。Yields 的机制是 longjmp 回到 luaV_execute() 函数递归调用自身的下一条指令 (虚拟机的 native 指令而非 byte-code 指令),同时把 CRT stack 恢复到 resume 前的状态。所以 yields-in-C 会破坏 C 函数的 call stack。

尽管 coroutine 涉及了对 CRT stack 的操作,但是和 error 一样,仅限于 ANSI C 支持的 longjmp,不会破坏 Lua 虚拟机的跨平台性。问题是,为什么 Lua 要在总体的 stackless 设计中制造这个 stackful 例外?首先退一步说,即使采用 stackless 方式实现 coroutine 切换,仅仅能避免在 yields-in-byte-code 中使用 longjmp,仍然无法避免在 yields-in-C 中使用 longjmp。这是因为,虽然不再有必要 longjmp 回到最近一次 resume 之处,但是仍然需要从 yield 之处回到最近的 Lua 虚拟机代码。不仅如此,stackless 方式还要给 resumes-in-C 引入类似的 longjmp (因为不再利用 CRT stack,所以 resumes-in-C 也必须立即回到 Lua 虚拟机代码),破坏调用 resume 的 C 函数的 call stack,给 resumes-in-C 加上同现在的 yields-in-C 一样的局限性。而现在的 stackful 方法则完全没有这方面的问题。这正是无需 lua_resumek() 的原因。Stackful coroutine 是一个非常巧妙的设计。

什么是寄存器

2013/04/06

寄存器 (register) 似乎是初学计算机结构的人多少有所了解的概念 —— 成本最高也是速度最快的存储单元。不过,有时事物还可以从完全不同的角度重新阐述一遍。这段时间在看 SICP 和 Lua 虚拟机,其中两个常被并列提及的概念是 stack-based 虚拟机和 reigster 虚拟机。即使在深入了解虚拟机理论前,也可以想像语言虚拟机结构不太可能与 CPU 硬件 register 有直接对应关系。「Register 虚拟机」这个名称引起我对 register 进行重新认识的兴趣。

接触虚拟机之前还考虑过另一个和 register 相关的问题。一般的常识是函数调用时的参数通过 stack 传递。但是很多编译器从 90 年代起就实现了一种优化:通过 CPU register 传递参数。这样做的优点固然显而易见,但同时引出新的疑问:原本用 stack 传递参数不仅解决了数据传递问题,也解决了多层嵌套的函数调用时上层数据的保存问题;而 register 数量有限,如何解决多层嵌套调用时的状态问题?答案其实也简单,当一个函数 A 调用另一个函数 B 时,那些正在存储 A 本身的参数或者 A 本身的局部变量的 register 如果又要被用于向 B 传递参数,那么这些 register 的内容在被更改为传递给 B 的参数之前会先被压入 stack,B 返回之后这些 register 的内容会从 stack 中恢复。也就是说,register 并不是替代 stack 的传参功能,而是对 stack 的使用延迟了一个调用层次。根据「局部性原理」延迟使用主存中的 stack 得到速度优化。

由此可见,register [1] 虽然经常被称为比主存更快的存储单元,但是它的作用并不是给任意用途的主存单元提供高速替代品,而是和 stack 这种特定用途的存储区域有更紧密的联系。若感觉如此得出结论过于仓促,可以再观察几个例子。比如说,操作系统进行线程切换时,需要切换当前 stack 以及 —— 所有 register 内容。看,register 就像 stack 的延展。我们可以说 register 是 stack 最顶一段的硬件加速机制。

接下来再看 Lua 虚拟机的实现,它的 VM register 就是实现在 VM stack [2] 上。也就是说,Lua 使用 VM stack 的方式其实和一般的 C 编译器产生的代码使用 CPU stack 的方式没有区别。那么究竟为何 Lua 之类的虚拟机区别于 stack-based 虚拟机而特地被称为 register 虚拟机呢?通过 stack-base 虚拟机的指令可以发现,这种虚拟机是基本严格按照后入先出的方式使用 stack,每条指令基本上只操作 stack top 的一两条数据。而 register 虚拟机只在大的调用层次上遵循后入先出,在每层函数运行中是完全随机地使用本层函数的 stack (即当前 stack-frame [3],函数返回地址部分除外)。

全新的 register 的本质定义是:可被随机访问的最顶层 stack-frame。由此可以看出,主流编译语言几乎都可以称为 register 虚拟机 [4] 实现,即使在使用 register 传参这个优化流行之前。CPU 的硬件 register 是对一般 register 的硬件优化。

脚注:

  1. 更确切地说是通用寄存器,general-purpose registers 。
  2. Lua 的 VM stack 和其虚拟机实现本身的 C runtime stack (或者说硬件 CPU 的 stack) 是分开的。
  3. 按照函数调用层次,stack 可以被看作一组 frame,每层函数调用占据一个 frame。
  4. 这里的「虚拟机」是真实的 CPU。

LEGO 与光剑

2013/03/28

永远不要低估的黑暗面。

Simulation 与 Infinite-Stream

2013/03/02

SICP 确实是本博大精深的书。读过前三章,即便不能领会作者的全部意图,单就其中几个例子也是值得借鉴的。第 3.3.5 节的「约束系统」就是一种我此前并不了解的用 imperative 方式实现 declarative kownledge 的初级方案。第 3.3.4 节的「电路模拟」系统则介绍了如何用「显式 schedule」方式模拟随时间变化的系统。

读到第 3.5.2 节的 infinite-stream 时,跟上作者的思路已略显吃力。以往对递归的理解包含三个要素:终止条件、调用自身、每次调用时减小问题的规模。Inifite-stream 则不同:没有终止条件、每次调用自身时问题规模保持不变、on-demand 解决问题中必要的部分而延迟其余部分。从 3.5.3 节开始,延迟解决的部分甚至不再是直接构建 lambda 函数而是调用 stream 本身。

SICP 的这个部分似乎体现了技术书籍的一个常见问题,即便经典也不例外 —— 作者认为显而易见而略过的东西耗费了读者大量脑力。如下图:

上图 (Figure 3.25) 是第 3.3.4 节对电路系统的示意图,下图 (Figure 3.32) 是第 3.5.3 节对 infinite-stream 的信号处理示意图 (该图的例子是对 input 的积分)。近似的表现形式让我对 Figure 3.32 的意义完全迷惑,因为 infinite-stream 并没有电路模拟那样的 schedule 机制,但具有自反馈和延迟求值。通过不时对 Figure 3.32 发呆,终于在一周后恍然大悟,这两个看似差不多的系统有完全相反的性质。Figure 3.25 的系统是「输入驱动」,系统的动作由左向右进行。而 Figure 3.32 是「输出牵引」,整个系统的动作从右向左引发。输出端像一个 signal puller,每当「需要」一个信号的时候,才会激发必要的输入端提供数值。

阅读 SICP 的另一个难点也是它强大之处。Peter Norvig 在 Amazon 上对此书的评价写道 (斜体为我划出):

But … you’re not looking for one more trick, rather you’re looking for a way of synthesizing what you already know, and building a rich framework onto which you can add new learning over a career.

SICP 是一个 framework。软件开发经验不多的人很难读懂,经验足够丰富的人则面临另一项挑战:如何把已知的东西归结到这个 framework 上。为了让 framework 尽可能通用和严密,SICP 用一些更形式化的词来替代软件业常用的「行话」。读者必须自己体会这些「奇怪」名词和日常所见的联系。例如高级动态语言中经常提及的「lexical scope」在 SICP 中只出现过两次 —— 前言中一笔带过,之后出现在很晚的章节。对 lexical scope 的详细阐述以「environment model」的名称在第 3.2 节中出现。

另一个最初难以理解,但和日常所见联系起来之后就显而易见的概念是 explicit-delay。在第 3.5.4 节中提出了一个解微分方程的 stream/signal-processing 系统,如下图所示。

其中 map 和 integral 的定义相互依赖 (上图的 code 片段中,integral 函数的 delayed-integrand 的传入实参就是 map 函数),所以 integral 中依赖 map 的参数必须设计为延迟取值。听起来很玄,不过你只要把「延迟求值」设想为 pass-by-reference (即传入的不是 map 函数的指针而是函数指针的地址,因为这个函数指针在 integral 被调用之后才被赋予合法值),把 force 想像成 dereference (也就是 C 里著名的 * 操作符) 就一目了然了。这与 C 语言里定义相互依赖的类型时用指针来代替实际类型没有本质区别。

读 SICP 的有两种可能的后果。一种是扩展了你的 mindset,而另一种可能是同事们从此听你在说一种别人完全不懂的语言 (也许从你在 SICP 上看到第一行 Lisp 代码的时候就就注定了这种结果)。

最近的收获

2013/02/18

最近工作非常忙碌。开发中的产品经历了重要的 milestone,又逢公司的 Tech Summit,在总部和其它地区的同事面前完成了自己的首次英语 presentation。工作之余则主要是「汲取」—— 读的东西比较多,总结的东西比较少。学完 Lua 之后再看 SICP,眼界开阔了不少。在 Amazon 上买了不少闲书,包括没有 Kindle 版的 GEB,今天终于到货了;物质方面也收获不少,去东海岸休闲了一番,顺道买了台 MacBook Pro with Retina Display。

Programming in Lua(四)- Nil 和 List

2012/12/22

粗浅地看,Lua 的 nil 很容易被等同于「无」。如下面这段代码:

function r_nil()
    return nil
end

function r()
    return
end

a = r_nil()
b = r()

print(a .. ", " .. b)  -->  nil, nil

尽管函数 r_nil()r() 的返回语句分别带有和不带有 nil,接受它们返回值的变量 ab 的值都是 nil。另一个例子是 nil 对 table 的作用。

tab_v = { attr1 = 1, attr2 = 2 }
for k,v in pairs(tab_v) do
    print(k .. ", " .. v)
end  -->  attr1, 1
     -->  attr2, 2

tab_v.attr1 = nil
for k,v in pairs(tab_v) do
    print(k .. ", " .. v)
end  -->  attr2, 2

将 table 的一个 field 赋值为 nil 不仅仅改变其值,而是让这个 field 本身消失了 (这个例子中是 field attr1)。

分析 nil 的实际含义可以从 Lua 的另一个比较特殊的概念 —— list 入手。List 的特殊性在于它不是 first-class 类型。「First-class」是动态语言中常被提及的概念。编程语言有越多的构成元素符合 first-class 标准,其概念模型就越一致、越简单。Lua 的基本数据类型 (包括 nil) 和函数都符合 first-class。满足 first-class 标准通常有四个要求:

  • 可以被赋值给变量;
  • 可以作为参数;
  • 可以作为返回值;
  • 可以作为数据结构的构成部分。( 注意 nil 并不完全符合这个要求,但是可以通过某个 field 的缺失来表示 nil。)

在《Programming in Lua, 2ed》的第 5.1 节提到 list 只能用于四种情形:

These lists appear in four constructions in Lua: multiple assignments, arguments to function calls, table constructors, and return statements.

List 有两种具体的表现形式,一种是用逗号分割的一组表达式,表示一个具体长度的 list;另一种是三个点构成的省略号 (...),表示其长度和内容不定。第二种表示方式不能用在 multiple assignments 的等号左方,也不能创建新 list,只能从函数的形式参数列表中获得。由此可以看出,list 不符合 first-class 标准:

  • 它的部分内容可以赋给几个变量,但本身不能作为整体赋给变量;
  • 它是参数列表的全部或一部分,但不是任何参数 (注意两者的区别);
  • 它不能作为数据结构的构成部分。注意,「...」不能作为 closure 的 upvalue。用 first-class function 存储 list 的方式行不通。

作为非 first-class 类型,list 无法被生命周期较长的数据结构存储。短期的完整传递 list 的内容只能利用函数调用/返回的方式:

function f_outer(...) -- important: f_out() must accept
                      -- "...".
end

f_outer(f_inner())
-- pass the list returned by f_inner() to
-- f_outer() as the latter's argument list

f_outer(1, 2, f_inner())
-- pass f_outer() a new list, which is "1, 2" appended
-- by f_inner()'s returned list

function f_caller(...)
   f_callee(...) -- pass argument list of f_caller()
                 -- to f_callee()

   return f()    -- pass list returned by f() to one
                 -- level up
end

另外还有一些反例:

function f_caller(...)
   a, b = ...   -- not pass a list, "a, b" is
                -- a different list of two elements
                -- obtained by adjusting the "...",
                -- and this list is very short-live,
                -- existing in this line only

   tab = {...}  -- not pass a list, tab won't
                -- have fields for nils in the "..."

   local function test(a, b)
   end
   test(...)    -- not pass a list, test()'s
                -- argument list accepts only the first
                -- two items of "..."

   for i in ... do  -- the "for" uses only the first
                    -- three elements in "..."
                    -- (two accepted by for internally,
                    -- and one received by i)
   end
end

List 会成为 Lua 中为数不多的非 first-class 类型是因为它实际代表了 stack 上的一段数据。一般只有动态分配的数据能作为 first-class 类型,操纵 stack 上的数据则只能通过函数调用的参数和返回值等有限的方式进行 (这也是因为 stack 在一定程度上代表了程序的 continuation)。不过在其它语言中,stack 的内容并没有被抽象为类似 list 这样可以被操作 (尽管不能像 first-class 类型那样自由地操作) 的概念。因为 Lua 提供了多返回值,鼓励可变参数以及参数/返回值和 table 的互相转化,特别是它著名的 C 接口就以 stack 为中心来设计,所以它有了独特的 list 概念来操作 stack。

如果在 Lua 中一定要将 list 和 first-class 混用怎么办呢?比如说,一个函数返回的 list 通常还是要存储在变量中,或者应用在某个表达式中。这是上面的反例代码中已经提及的机制 —— adjustment。Adjustment 并不是真的传递一个 list 的内容,而是用一个 list 的内容构建另一个新的 list。当新 list 的长度小于原 list,多余的值被丢弃,当新 list 长度大于原 list,就用 nil 补齐。

Lua 的 nil 担当了三种角色:

  • 一般的数据类型,通常标志某种特殊情况 (应用或算法本身的特殊情况,而非语言的特殊情况)。
  • Table field 的删除器。
  • List adjustment 的补全值。

Lua 的 nil 不代表「无」,反而恰恰起到了「有」的作用。在应用 adjustment 的情况下,我们往往用新 list 末尾的 nil 来判断原 list 的「无」。这个做法有一个缺陷:无法辩别原 list 末尾本来就确实含有的 nil。如果需要区别对待 list 结束和 list 本身含有 nil 这两种情况,既可以自行编写 C 代码来检测 stack,也可以使用 Lua 现成的 API select()。回到第一个例子,稍加修改就可以区别两种情况:

function r_nil()
    return nil
end

function r()
    return
end

a = select("#", r_nil())
b = select("#", r())

print(a .. ", " .. b)  -->  1, 0

下面是精确区别 list 结束的一个实际例子 —— 关于 stack 的递归终止条件。若希望一个函数对它的 argument list 中的每个参数执行 op() 操作:

function map_list(op, ...)
    if select("#", ...) == 0 then
        return
    else
        local a = ...
        return op(a), map_list(op,
                               sub_list(...))
    end
end

函数 sub_list() 返回的 list 是其接受的 argument list 去掉第一个元素。这个函数的实现如下 (如果用 C 语言来实现会更简单)。如果 op() 允许接受 nil 并且在此情况下返回有意义的值,或者 map_list() 接受的 list 在中间含有 nil,那么 map_list() 的递归终止条件就必须基于 select() 而不可以基于对 nil 的判断。

function sub_list(...)
    local list_start
    function list_start(start, ...)
        if start > select("#", ...) then
            return
        else
            return select(start, ...),
                   list_start(start + 1, ...)
        end
    end
    return list_start(2, ...)
end

List 是 Lua 中最不符合 first-class 的数据类型。但由于其不能作为变量但可以被函数的返回值构建的特性,List 反而可能是 Lua 中最纯粹的 functional programming  元素。放弃 table 而完全用 list 来编写 Lua 程序也许是把 Lua 转化为一种 FP 语言最简单的手段。