May 17, 2015 - 技术管理猪鸡-1 开篇

Comments

高效的秘密

我正式走上职业生涯是 2011 年秋天,完成了博士学业,踌躇满志地加入了 Google。当时,我的理想是做 Google 里生产率最高的软件工程师。为此,我列了一个高效工程师名单,看他们每天提交的代码是些什么,以从中学习高效的工作方法。这个名单里有 Jeff Dean, Sanjay Ghemawat, Rob Pike,还有一些 Google 内 7 级以上的工程师。因为 Google 内部源代码提交全部公开,我可以看到他们每天的工作内容。

很快,从读这些代码中我认识到了一点:人每天只有八个小时工作时间,谁都一样。其中能高效工作的时间绝对不超过4个小时。这些工程师编写的代码行数绝对不算多,但从事的项目影响大。比如 Pike,大部分时间花在了审查其他成员的 Go 代码上。而一个刚入行的 Golang 工程师,每天的任务就是写作 Go 的标准库,今天写 http 明天写 sort,写的比 Pike 多很多。考核时,高级工程师因为带领着高效团队,每季度 OKRs 上都有诸多亮点;而刚入行的工程师,只能报告一些比较琐碎的成就。

这个观察近乎于常识,然而对于当时的我来说是一个顿悟:做出 MapReduce 框架的和写琐碎 MapReduce 程序的工程师之间的差距并不是他们的工具和编程效率,也往往不是教育背景或者经验,而是他们各自的杠杆:所带领的团队。

问题是,没有人会给你这个杠杆。于是,我开始观察别人的杠杆是怎么搭建的。

运用常识

Google 的芝加哥 office 有两个技术领导:Brian Fitzpatrick 和 Ben Collins-Sussman。他们合写了一本书,叫做 Team Geek。近水楼台,我就拿了一本过来看。或许对于 Google 之外的人来说,这本书讲了许多有价值的东西,对于 Google 员工来说,基本上书里面说的就是公司每天实践的,因此读来觉得都是常识。这让我突然领悟到,其实所谓的团队工作,或许说白了就是正确地运用这些常识。

在实践中运用常识远比想像中的难。有一次在搏击课上,师傅让我和某个拿过法式拳击世界冠军的师兄对练。他手腿都很长,出拳又快,根本拿不到破绽。为了不被首轮打倒,我不得不满场跑着闪躲。躲着跑过师傅的时候,他就说了一句:“你只管出拳,不出拳永远赢不了点数”。其实这是每个学搏击的人都知道的常识,却因为一时的恐惧彻底忘了。做技术领导时也是一样,许多我们知道的常识性的东西,一旦遇到复杂情况,我们往往依赖于旧习惯和情绪反应,忘了要解决的问题,忘了运用常识做出正确的判断。

逐渐习得的管理技能

常识是可以习得的,因为每个人都有包容常识的心性。问题是,所谓常识,是名常识,实非常识。根本没有一本叫做“技术管理常识”的书,读完就事理无碍了。在领悟到技术管理其实是运用基本常识之前,我买了一大堆的关于技术管理的书,幻想能够博闻强记速成。想明白“习得”这一点,让我轻松了好多:这不是入学考试,慢慢积累最省时省事。就像练习武术一样,最强的斗士绝不是看书最多或者理论最强的,而是训练时间最长的。

我曾经也醉心于一些管理方法。比如说,Kanban 管理法是照搬了丰田在七十年代的高效率生产模式而提出的。06年第一次读这个管理方法的时候崇拜无比。到了2009年,丰田汽车在世界范围内发生了多起质量问题召回的事情,使我重新审视这个问题:任何管理方法都是为了解决某些类问题而催生的。问题变了,不管以前多么神奇的管理方法都会变得一地鸡毛,因为管理方法不能脱离要解决的问题。

也就是这个时候,我重温了温伯格的《技术领导之路》。这本书对于我来说最有价值的一点,是让我体会到尽管管理方法成千上万,归根到底需要一些“元方法”去支配。比如,书中提到了一个大家都明白的元方法:写日记。技术领导者每天写日记,记下每天的活动,反思一些事情。尽管写日记并不能直接解决技术管理上的难题,却打开了反思之门,也把许多事情前因后果连接起来。比如,通过在日记里反思一些会议的效率,我开始有意识地反思高效率的会议和低效率的会议的差别,并主导一些会议的日程。显然,真正的问题不是要不要设定议事日程(元方法),而是学会怎样设定一个特定会议的议事日程(解决问题的方法)。而后者,只能通过设定议事日程学到。

管理模型

我是一个理科生。理科生理解世界的第一工具是模型。世界过于复杂,人脑计算能力有限,只能付诸模型抽象简化。技术管理作为技术(工程学)和管理(自然科学)的横切点,自然免不了各种各样的模型。技术管理的模型本身多种多样。人月神话模型,人件模型,丰田模型,温伯格模型,Agile 模型,Lean 模型等等不可枚举。对于一个技术管理人员来说,幸运的是,所有的模型都是错的,所以即使不知道这些模型,也未必遗漏了什么重要的。不幸的是,有些模型的确比较有用,所以知道一些还是有好处的。

正因为此,我开始收集一些工作中积累的管理模型 (Pattern),像 GoF 的 Design Pattern 一样,列出要解决的问题,模型,和自己的实现。我收集了不少细碎的模型。有时候觉得过于细碎,不足为外人道也;有时候又觉得好像还是有些用处的。

就这样,在不断的写作懒惰症中过了三四年。直到最近,说来也巧,在检查一个 bug 的时候发现有某用户调用 Fitbit 的食物记录 API 中试图存下 “🐷🐔”,这提醒了我那个著名的 The Chicken and the Pig 笑话,以及我的好友 Tinyfool 一直开玩笑说我写的“编程猪和鸡番外篇”系列,促发了我写作“技术管理猪鸡”的想法。这一篇,算是一个很不正式的开头。

 

 

PS: 好友余晟翻译的温伯格的《技术领导之路》一书将要再版。这本书里包含了许多技术管理的“元方法”,以及作者提出的 MOI 管理模型(不幸的是这个模型比较有用)。推荐对技术管理(不仅限 IT 行业)有兴趣的读者购买。

 

Dec 3, 2014 - 编程珠玑番外篇-Q 协程的历史,现在和未来

Comments

本文原发于《程序员》2014年11月刊,发表时略有修改。 

计算机科学是一门应用科学,几乎所有概念都是为了理解或解决实际问题而生的。协程 (Coroutine) 的出现也不例外。协程的概念,最早可以追溯到写作 COBOL 语言编译器中的技术难题。

从磁带到协程

COBOL 是最早的高级语言之一。编译器则是高级语言必不可少的一部分。现如今,我们对编译器了解,已经到了可以把核心内容浓缩成一本教科书的程度。然而在六十年代,如何写作高效的语言编译器是那个时代绕不过的现实问题。比如,1960 年夏天,D. E. Knuth 就是利用开车横穿美国去加州理工读研究生的时间,对着 Burroughs 205 机器指令集手写 COBOL 编译器。最早提出“协程”概念的 Melvin Conway 的出发点,也是如何写一个只扫描一遍程序 (one-pass) 的 COBOL 编译器。众多的“高手”纷纷投入编译器书写,可见一门新科学发展之初也是筚路蓝缕

以现代眼光来看,高级语言编译器实际上是多个步骤组合而成:词法解析,语法解析,语法树构建,以及优化和目标代码生成等等。编译实质上就是从源程序出发,依次将这些步骤的输出作为下一步的输入,最终输出目标代码。在现代计算机上实现这种管道式的架构毫无困难:只需要依次运行,中间结果存为中间文件或放入内存即可。GCC 和 Clang 编译器,以及 ANTLR 构建的编译器,都遵循这样的设计。

在 Conway 的设计里,词法和语法解析不再是两个独立运行的步骤,而是交织在一起。编译器的控制流在词法和语法解析之间来回切换:当词法模块读入足够多的 token 时,控制流交给语法分析;当语法分析消化完所有 token 后,控制流交给词法分析。词法和语法分别独立维护自身的运行状态。Conway 构建的这种协同工作机制,需要参与者“让出 (yield)”控制流时,记住自身状态,以便在控制流返回时能够从上次让出的位置恢复(resume)执行。简言之,协程的全部精神就在于控制流的主动让出和恢复。我们熟悉的子过程调用可以看作在返回时让出控制流的一种特殊的协程,其内部状态在返回时被丢弃了,因此不存在“恢复”这个操作。

以现在眼光来看,编译器的实现并不必然需要协程。然而,Conway 用协程实现 COBOL 编译器在当时绝不是舍近求远。首先,从原理上来说,因为 COBOL 并不是 [本文原发于《程序员》2014年11月刊,发表时略有修改。 

计算机科学是一门应用科学,几乎所有概念都是为了理解或解决实际问题而生的。协程 (Coroutine) 的出现也不例外。协程的概念,最早可以追溯到写作 COBOL 语言编译器中的技术难题。

从磁带到协程

COBOL 是最早的高级语言之一。编译器则是高级语言必不可少的一部分。现如今,我们对编译器了解,已经到了可以把核心内容浓缩成一本教科书的程度。然而在六十年代,如何写作高效的语言编译器是那个时代绕不过的现实问题。比如,1960 年夏天,D. E. Knuth 就是利用开车横穿美国去加州理工读研究生的时间,对着 Burroughs 205 机器指令集手写 COBOL 编译器。最早提出“协程”概念的 Melvin Conway 的出发点,也是如何写一个只扫描一遍程序 (one-pass) 的 COBOL 编译器。众多的“高手”纷纷投入编译器书写,可见一门新科学发展之初也是筚路蓝缕

以现代眼光来看,高级语言编译器实际上是多个步骤组合而成:词法解析,语法解析,语法树构建,以及优化和目标代码生成等等。编译实质上就是从源程序出发,依次将这些步骤的输出作为下一步的输入,最终输出目标代码。在现代计算机上实现这种管道式的架构毫无困难:只需要依次运行,中间结果存为中间文件或放入内存即可。GCC 和 Clang 编译器,以及 ANTLR 构建的编译器,都遵循这样的设计。

在 Conway 的设计里,词法和语法解析不再是两个独立运行的步骤,而是交织在一起。编译器的控制流在词法和语法解析之间来回切换:当词法模块读入足够多的 token 时,控制流交给语法分析;当语法分析消化完所有 token 后,控制流交给词法分析。词法和语法分别独立维护自身的运行状态。Conway 构建的这种协同工作机制,需要参与者“让出 (yield)”控制流时,记住自身状态,以便在控制流返回时能够从上次让出的位置恢复(resume)执行。简言之,协程的全部精神就在于控制流的主动让出和恢复。我们熟悉的子过程调用可以看作在返回时让出控制流的一种特殊的协程,其内部状态在返回时被丢弃了,因此不存在“恢复”这个操作。

以现在眼光来看,编译器的实现并不必然需要协程。然而,Conway 用协程实现 COBOL 编译器在当时绝不是舍近求远。首先,从原理上来说,因为 COBOL 并不是](http://en.wikipedia.org/wiki/LL_parser) 型语法,即使现在我们也无法简单构建一个以词法分析为子过程的自动机。其次,当年计算机依赖于磁带存储设备,而磁带存储设备只支持顺序存储(设想一下随机访问带来的频繁的倒带和快进问题)。也就是说,依次执行编译步骤并依靠中间文件通信的设计是不现实的,各步骤必须同步前进。正是这样的现实局限和设计需要,自然催生了协程的概念。

自顶向下,无需协同

虽然协程是伴随着高级语言诞生的,它却没有能像子过程一样成为通用编程语言的基本元素。

从 1963 年首次提出到上个世纪九十年代,我们在 ALOGL, Pascal, C, FORTRAN 等主流的命令式编程语言中都没有看到原生的协程支持。协程只稀疏地出现在 Simula,Modular-2 (Pascal 升级版) 和 Smalltalk 等相对小众的语言中。协程作为一个比子进程更加通用的概念,在实际编程却没有取代子进程,这一点不得不说是出乎意外的。如果我们结合当时的程序设计思想看,这一点又是意料之中的:协程是不符合那个时代所崇尚的“自顶向下”的程序设计思想的,自然也就不会成为当时主流的命令式编程语言 (imperative programming) 的一部分。

正如面向对象的语言是围绕面向对象的开发理念设计一样,命令式编程语言是围绕自顶向下(top-down)的开发理念设计的。在自顶向下的理念指导下,程序被切分为一个主程序和大大小小的子模块,每一个子模块又可能调用更多子模块等等。C 家族语言的 main() 函数就是这种自顶而下思想的体现。在这种理念指导下,各模块形成层次调用关系,而程序设计就是制作这些子过程。在“自顶向下”这种层次化的理念下,具有鲜明层次的子过程调用成为软件系统最自然的组织方式,也是理所当然。相较之下,具有执行中让出和恢复功能的协程在这种架构下无用武之地。可以说,自上而下的设计思想从一开始就排除了对协程的需求。其后的结构化编程(Structural Programming) 思想,更是进一步强化了“子过程调用作为唯一控制结构”的基本假设。在这样的指导思想下,协程一直没有成为当时编程语言的一等公民。

尽管从提出到上世纪 90 年代,协程在编程语言中没有普遍成为一等公民,但作为一种易于理解的控制结构,协程的概念渗入到了软件设计的许多方面。在结构化编程思想一统天下之时, D. Knuth 曾经专门写过一篇 “Structured Programming with GOTO” 来为 GOTO 语句辩护。在他列出的几条 GOTO 可以方便编程且不破坏程序结构的例子中,有一个(例子7b)就是用 GOTO 实现协程控制结构。相比较之下,不用 GOTO 的“结构化”代码反而失去了良好的结构。当然,追求实际结果的工业界对于学界的这场要不要剔除 GOTO 的争论并不感冒。当时许多语言都附带了不建议使用的 GOTO 语句,显得左右逢源。这方面一个最明显的例子就是 Java:其语言本身预留了 goto 关键字,其编译器却没有提供任何的支持,可以说在 goto 这场争论中做足了中间派。

实践中,协程的思想频繁应用于任务调度和流处理上。比如,UNIX 管道就可以看成是众多命令间的协同操作。当然,管道的现代实现都是以 pipe() 系统调用和进程间的通信为基础,而非简单遵循协程的 yield/resume 语法。

许多协同式多任务操作系统,也可以看成协程运行系统。说到协同式多任务系统,一个常见的误区是认为协同式调度比抢占式调度“低级”,因为我们所熟悉的桌面操作系统,都是从协同式调度(如 Windows 3.2, Mac OS 9 等)过渡到抢占式多任务系统的。实际上,调度方式并无高下,完全取决于应用场景。抢占式系统允许操作系统剥夺进程执行权限,抢占控制流,因而天然适合服务器和图形操作系统,因为调度器可以优先保证对用户交互和网络事件的快速响应。当年 Windows 95 刚刚推出的时候,抢占式多任务就被作为一大买点大加宣传。协同式调度则等到进程时间片用完或系统调用时转移执行权限,因此适合实时或分时等等对运行时间有保障的系统。

另外,抢占式系统依赖于 CPU 的硬件支持。 因为调度器需要“剥夺”进程的执行权,就意味着调度器需要运行在比普通进程高的权限上,否则任何“流氓(rogue)”进程都可以去剥夺其他进程了。只有 CPU 支持了执行权限后,抢占式调度才成为可能。x86 系统从 80386 处理器开始引入 Ring 机制支持执行权限,这也是为何 Windows 95 和 Linux 其实只能运行在 80386 之后的 x86 处理器上的原因。而协同式多任务适用于那些没有处理器权限支持的场景,这些场景包含资源受限的嵌入式系统和实时系统。在这些系统中,程序均以协程的方式运行。调度器负责控制流的让出和恢复。通过协程的模型,无需硬件支持,我们就可以在一个“简陋”的处理器上实现一个多任务的系统。我们见到的许多智能设备,如运动手环,基于硬件限制,都是采用协同调度的架构。

协程的复兴和现代形式

编程思想能否普及开来,很大程度上在于应用场景。协程没有能在自顶向下的世界里立足,却在动态语言世界里大放光彩,这里最显著的例子莫过于 Python 的迭代器和生成器。

回想一下在 C 的世界里,循环的标准写法是 for (i = 0; i < n; ++i) { … }。 这行代码包含两个独立的逻辑, for 循环控制了 i 的边界条件, ++i 控制了 i 的自增逻辑。这行代码适用于 C 世界里的数组即内存位移的范式,因此适合大多数访问场景。到了 STL 和复杂数据结构的世界,因为许多数据结构只支持顺序访问,循环往往写成: for (i = A.first(); i.hasNext();i = i.next()) { … }

这种设计抽象出了一个独立于数据结构的迭代器,专门负责数据结构上元素访问顺序。迭代器把访问逻辑从数据结构上分离出来, 是一个常用的设计模式 (GoF 23个设计模式之一).我们在 STL 和 Java Collection 中也常常看到迭代器的身影。

在适当的时候,我们可以更进一步引入一个语法糖(脚注:这里牵涉到一个外部迭代器和内部迭代器的问题。限于篇幅不在此讨论)将循环写成: for i in A.Iterator() {func(i)}。

事实上,许多现代语言都支持类似的语法。这种语法抛弃了以 i 变量作为迭代指针的功能,要求迭代器自身能够记住当前迭代位置,调用时返回下一个元素。读者不难看到,这种架构就是我们在文章开始提到的语法分析器的架构。正因为如此,我们可以从协程的角度来理解迭代器:当控制流转换到迭代器上时,迭代器负责生成和返回下一个元素。一旦下一个元素准备就绪,迭代器就让出控制流。这种特殊的迭代器实现在 Python 中又被成为生成器。以协程的角度切入的的好处是设计大大精简。实际上,在 Python 中,生成器本身就是一个普通的函数,和普通函数的唯一不同是它的返回语句是协程风格的 yield。这里,yield 一语双关,既是让出控制流,也是生成迭代器的返回值。

以上我们仅仅讨论了生成器的最基本的特性。实际上,生成器的强大之处在于我们可以像 UNIX 管道一样串联起来,组成所谓的生成器表达式。如果我们有一个可以生成 1,2,3 … 的生成器 N,则 square = (i **2 for i in N) 就是一个生成平方数的生成器表达式。注意这里圆括号语法和 [本文原发于《程序员》2014年11月刊,发表时略有修改。 

计算机科学是一门应用科学,几乎所有概念都是为了理解或解决实际问题而生的。协程 (Coroutine) 的出现也不例外。协程的概念,最早可以追溯到写作 COBOL 语言编译器中的技术难题。

从磁带到协程

COBOL 是最早的高级语言之一。编译器则是高级语言必不可少的一部分。现如今,我们对编译器了解,已经到了可以把核心内容浓缩成一本教科书的程度。然而在六十年代,如何写作高效的语言编译器是那个时代绕不过的现实问题。比如,1960 年夏天,D. E. Knuth 就是利用开车横穿美国去加州理工读研究生的时间,对着 Burroughs 205 机器指令集手写 COBOL 编译器。最早提出“协程”概念的 Melvin Conway 的出发点,也是如何写一个只扫描一遍程序 (one-pass) 的 COBOL 编译器。众多的“高手”纷纷投入编译器书写,可见一门新科学发展之初也是筚路蓝缕

以现代眼光来看,高级语言编译器实际上是多个步骤组合而成:词法解析,语法解析,语法树构建,以及优化和目标代码生成等等。编译实质上就是从源程序出发,依次将这些步骤的输出作为下一步的输入,最终输出目标代码。在现代计算机上实现这种管道式的架构毫无困难:只需要依次运行,中间结果存为中间文件或放入内存即可。GCC 和 Clang 编译器,以及 ANTLR 构建的编译器,都遵循这样的设计。

在 Conway 的设计里,词法和语法解析不再是两个独立运行的步骤,而是交织在一起。编译器的控制流在词法和语法解析之间来回切换:当词法模块读入足够多的 token 时,控制流交给语法分析;当语法分析消化完所有 token 后,控制流交给词法分析。词法和语法分别独立维护自身的运行状态。Conway 构建的这种协同工作机制,需要参与者“让出 (yield)”控制流时,记住自身状态,以便在控制流返回时能够从上次让出的位置恢复(resume)执行。简言之,协程的全部精神就在于控制流的主动让出和恢复。我们熟悉的子过程调用可以看作在返回时让出控制流的一种特殊的协程,其内部状态在返回时被丢弃了,因此不存在“恢复”这个操作。

以现在眼光来看,编译器的实现并不必然需要协程。然而,Conway 用协程实现 COBOL 编译器在当时绝不是舍近求远。首先,从原理上来说,因为 COBOL 并不是 [本文原发于《程序员》2014年11月刊,发表时略有修改。 

计算机科学是一门应用科学,几乎所有概念都是为了理解或解决实际问题而生的。协程 (Coroutine) 的出现也不例外。协程的概念,最早可以追溯到写作 COBOL 语言编译器中的技术难题。

从磁带到协程

COBOL 是最早的高级语言之一。编译器则是高级语言必不可少的一部分。现如今,我们对编译器了解,已经到了可以把核心内容浓缩成一本教科书的程度。然而在六十年代,如何写作高效的语言编译器是那个时代绕不过的现实问题。比如,1960 年夏天,D. E. Knuth 就是利用开车横穿美国去加州理工读研究生的时间,对着 Burroughs 205 机器指令集手写 COBOL 编译器。最早提出“协程”概念的 Melvin Conway 的出发点,也是如何写一个只扫描一遍程序 (one-pass) 的 COBOL 编译器。众多的“高手”纷纷投入编译器书写,可见一门新科学发展之初也是筚路蓝缕

以现代眼光来看,高级语言编译器实际上是多个步骤组合而成:词法解析,语法解析,语法树构建,以及优化和目标代码生成等等。编译实质上就是从源程序出发,依次将这些步骤的输出作为下一步的输入,最终输出目标代码。在现代计算机上实现这种管道式的架构毫无困难:只需要依次运行,中间结果存为中间文件或放入内存即可。GCC 和 Clang 编译器,以及 ANTLR 构建的编译器,都遵循这样的设计。

在 Conway 的设计里,词法和语法解析不再是两个独立运行的步骤,而是交织在一起。编译器的控制流在词法和语法解析之间来回切换:当词法模块读入足够多的 token 时,控制流交给语法分析;当语法分析消化完所有 token 后,控制流交给词法分析。词法和语法分别独立维护自身的运行状态。Conway 构建的这种协同工作机制,需要参与者“让出 (yield)”控制流时,记住自身状态,以便在控制流返回时能够从上次让出的位置恢复(resume)执行。简言之,协程的全部精神就在于控制流的主动让出和恢复。我们熟悉的子过程调用可以看作在返回时让出控制流的一种特殊的协程,其内部状态在返回时被丢弃了,因此不存在“恢复”这个操作。

以现在眼光来看,编译器的实现并不必然需要协程。然而,Conway 用协程实现 COBOL 编译器在当时绝不是舍近求远。首先,从原理上来说,因为 COBOL 并不是](http://en.wikipedia.org/wiki/LL_parser) 型语法,即使现在我们也无法简单构建一个以词法分析为子过程的自动机。其次,当年计算机依赖于磁带存储设备,而磁带存储设备只支持顺序存储(设想一下随机访问带来的频繁的倒带和快进问题)。也就是说,依次执行编译步骤并依靠中间文件通信的设计是不现实的,各步骤必须同步前进。正是这样的现实局限和设计需要,自然催生了协程的概念。

自顶向下,无需协同

虽然协程是伴随着高级语言诞生的,它却没有能像子过程一样成为通用编程语言的基本元素。

从 1963 年首次提出到上个世纪九十年代,我们在 ALOGL, Pascal, C, FORTRAN 等主流的命令式编程语言中都没有看到原生的协程支持。协程只稀疏地出现在 Simula,Modular-2 (Pascal 升级版) 和 Smalltalk 等相对小众的语言中。协程作为一个比子进程更加通用的概念,在实际编程却没有取代子进程,这一点不得不说是出乎意外的。如果我们结合当时的程序设计思想看,这一点又是意料之中的:协程是不符合那个时代所崇尚的“自顶向下”的程序设计思想的,自然也就不会成为当时主流的命令式编程语言 (imperative programming) 的一部分。

正如面向对象的语言是围绕面向对象的开发理念设计一样,命令式编程语言是围绕自顶向下(top-down)的开发理念设计的。在自顶向下的理念指导下,程序被切分为一个主程序和大大小小的子模块,每一个子模块又可能调用更多子模块等等。C 家族语言的 main() 函数就是这种自顶而下思想的体现。在这种理念指导下,各模块形成层次调用关系,而程序设计就是制作这些子过程。在“自顶向下”这种层次化的理念下,具有鲜明层次的子过程调用成为软件系统最自然的组织方式,也是理所当然。相较之下,具有执行中让出和恢复功能的协程在这种架构下无用武之地。可以说,自上而下的设计思想从一开始就排除了对协程的需求。其后的结构化编程(Structural Programming) 思想,更是进一步强化了“子过程调用作为唯一控制结构”的基本假设。在这样的指导思想下,协程一直没有成为当时编程语言的一等公民。

尽管从提出到上世纪 90 年代,协程在编程语言中没有普遍成为一等公民,但作为一种易于理解的控制结构,协程的概念渗入到了软件设计的许多方面。在结构化编程思想一统天下之时, D. Knuth 曾经专门写过一篇 “Structured Programming with GOTO” 来为 GOTO 语句辩护。在他列出的几条 GOTO 可以方便编程且不破坏程序结构的例子中,有一个(例子7b)就是用 GOTO 实现协程控制结构。相比较之下,不用 GOTO 的“结构化”代码反而失去了良好的结构。当然,追求实际结果的工业界对于学界的这场要不要剔除 GOTO 的争论并不感冒。当时许多语言都附带了不建议使用的 GOTO 语句,显得左右逢源。这方面一个最明显的例子就是 Java:其语言本身预留了 goto 关键字,其编译器却没有提供任何的支持,可以说在 goto 这场争论中做足了中间派。

实践中,协程的思想频繁应用于任务调度和流处理上。比如,UNIX 管道就可以看成是众多命令间的协同操作。当然,管道的现代实现都是以 pipe() 系统调用和进程间的通信为基础,而非简单遵循协程的 yield/resume 语法。

许多协同式多任务操作系统,也可以看成协程运行系统。说到协同式多任务系统,一个常见的误区是认为协同式调度比抢占式调度“低级”,因为我们所熟悉的桌面操作系统,都是从协同式调度(如 Windows 3.2, Mac OS 9 等)过渡到抢占式多任务系统的。实际上,调度方式并无高下,完全取决于应用场景。抢占式系统允许操作系统剥夺进程执行权限,抢占控制流,因而天然适合服务器和图形操作系统,因为调度器可以优先保证对用户交互和网络事件的快速响应。当年 Windows 95 刚刚推出的时候,抢占式多任务就被作为一大买点大加宣传。协同式调度则等到进程时间片用完或系统调用时转移执行权限,因此适合实时或分时等等对运行时间有保障的系统。

另外,抢占式系统依赖于 CPU 的硬件支持。 因为调度器需要“剥夺”进程的执行权,就意味着调度器需要运行在比普通进程高的权限上,否则任何“流氓(rogue)”进程都可以去剥夺其他进程了。只有 CPU 支持了执行权限后,抢占式调度才成为可能。x86 系统从 80386 处理器开始引入 Ring 机制支持执行权限,这也是为何 Windows 95 和 Linux 其实只能运行在 80386 之后的 x86 处理器上的原因。而协同式多任务适用于那些没有处理器权限支持的场景,这些场景包含资源受限的嵌入式系统和实时系统。在这些系统中,程序均以协程的方式运行。调度器负责控制流的让出和恢复。通过协程的模型,无需硬件支持,我们就可以在一个“简陋”的处理器上实现一个多任务的系统。我们见到的许多智能设备,如运动手环,基于硬件限制,都是采用协同调度的架构。

协程的复兴和现代形式

编程思想能否普及开来,很大程度上在于应用场景。协程没有能在自顶向下的世界里立足,却在动态语言世界里大放光彩,这里最显著的例子莫过于 Python 的迭代器和生成器。

回想一下在 C 的世界里,循环的标准写法是 for (i = 0; i < n; ++i) { … }。 这行代码包含两个独立的逻辑, for 循环控制了 i 的边界条件, ++i 控制了 i 的自增逻辑。这行代码适用于 C 世界里的数组即内存位移的范式,因此适合大多数访问场景。到了 STL 和复杂数据结构的世界,因为许多数据结构只支持顺序访问,循环往往写成: for (i = A.first(); i.hasNext();i = i.next()) { … }

这种设计抽象出了一个独立于数据结构的迭代器,专门负责数据结构上元素访问顺序。迭代器把访问逻辑从数据结构上分离出来, 是一个常用的设计模式 (GoF 23个设计模式之一).我们在 STL 和 Java Collection 中也常常看到迭代器的身影。

在适当的时候,我们可以更进一步引入一个语法糖(脚注:这里牵涉到一个外部迭代器和内部迭代器的问题。限于篇幅不在此讨论)将循环写成: for i in A.Iterator() {func(i)}。

事实上,许多现代语言都支持类似的语法。这种语法抛弃了以 i 变量作为迭代指针的功能,要求迭代器自身能够记住当前迭代位置,调用时返回下一个元素。读者不难看到,这种架构就是我们在文章开始提到的语法分析器的架构。正因为如此,我们可以从协程的角度来理解迭代器:当控制流转换到迭代器上时,迭代器负责生成和返回下一个元素。一旦下一个元素准备就绪,迭代器就让出控制流。这种特殊的迭代器实现在 Python 中又被成为生成器。以协程的角度切入的的好处是设计大大精简。实际上,在 Python 中,生成器本身就是一个普通的函数,和普通函数的唯一不同是它的返回语句是协程风格的 yield。这里,yield 一语双关,既是让出控制流,也是生成迭代器的返回值。

以上我们仅仅讨论了生成器的最基本的特性。实际上,生成器的强大之处在于我们可以像 UNIX 管道一样串联起来,组成所谓的生成器表达式。如果我们有一个可以生成 1,2,3 … 的生成器 N,则 square = (i **2 for i in N) 就是一个生成平方数的生成器表达式。注意这里圆括号语法和](http://en.wikipedia.org/wiki/List_comprehension) 方括号语法的区别,square = [i **2 for i in N] 是生成一个具体的列表。我们可以串联这些生成器表达式,最终的控制流会在这些串联的部分间转换,无需我们写作复杂的嵌套调用。当然,yield 只是冰山的一角,现代的 Python 语言还充分利用了 yield 关键字构建了 yield from 语句,(yield) 语法等等,使得我们无困难的将协程的思想融入到 Python 编程中去。限于篇幅这里不再展开。

我们前面说过,协程的思想本质上就是控制流的主动让出和恢复机制。在现代语言里,可以实现协程思想的方法很多,这些实现间并无高下之分,所区别的就是是否适合应用场景。理解这一点,我们对于各种协程的分类,如半对称/对称协程,有栈与无栈协程等具体实现就能提纲挈领,无需在实现细节上纠结。

协程在实践中的实现方式千差万别,一个简单的原因,是协程本身可以通过许多基本元素构建。基本元素的选取方式不一样,构建出来的协程抽象也就有差别。比如, Lua 语言选取了 create, resume 和 yield 作为基本构建元素, 从调度器层面构建出所谓的“非对程”协程系统。而 Julia 语言绕过调度器,通过在协程内调用 yieldto 函数完成了同样的功能,构建出了一个所谓的对称协程系统。尽管这两个语言使用了同样的 setjmp 库,构造出来的原语却不一样。又比如,许多 C 语言的协程库都使用了 ucontext 库实现,这是因为 POSIX 本身提供了 ucontext 库,不少协程实现是以 ucontext 为蓝本实现的。这些实现,都不可避免地带上了 ucontext 系统的一些基本假设,比如协程间是平等的,一般带有调度器来协调协程等等(比如 libtask 实现,以及云风的 coroutine 库)。Go 语言的一个鲜明特色就是通道(channel)作为一级对象。因此,resume 和 yield 等在其他语言里的原语在 go 里都以通道方式构建。我们还可以举出许多同样的例子。这些风格的差异往往和语言的历史,演化路径,和要解决的问题相关,我们不必苛求他们的协程模型一定要如此这般。

总的来说,协程为协同任务提供了一种运行时抽象。这种抽象非常适合于协同多任务调度和数据流处理。在现代操作系统和编程语言中,因为用户态线程切换代价比内核态线程小,协程成为了一种轻量级的多任务模型。我们无法预测未来,但是可以看到,协程已经成为许多擅长数据处理的语言的一级对象。随着计算机并行性能的提升,用户态任务调度已经成为一种标准的多任务模型。在这样的大趋势下,协程这个简单且有效的模型就显得更加引人注目。

Jun 10, 2014 - 编程珠玑番外篇-P PostScript 语言里的珠玑

Comments

本文原发于《程序员》2014年6月刊,发表时略有修改。 

首位 ACM 图灵奖得主  Alan Perlis 曾说过:“如果一门编程语言不能影响你的思维,就没有学的必要’。尽管能通过这个严苛测试的语言稀稀朗朗,在我看来,PostScript 在这个测试中至少得 A。作为一个着重于平面出版应用的领域特定语言(DSL),PostScript 彻底地改变了桌面出版行业。除此之外,PostScript 还是一个设计简单但功能强大的编程语言,含有许多至今仍可以借鉴的珠玑。

PostScript 的领域对象和操作

作为针对桌面出版的文档描述语言,PostScript 的设计者力图要解决的核心问题,是如何设计一个灵活高效的语言,以操控桌面出版里各种各样的图形对象,并保证设备无关性。我们不妨戴上语言设计者的眼镜,来模拟一下这个过程。

我们面临的首要问题是如何来描述桌面出版里的种种复杂对象和操作。尽管任何平面出版物最终都是二维像素点的集合,我们并不希望这个语言局限于描述像素点的颜色。这个语言最好能够直接描述文字,线条,形状等设计师熟悉的对象。因为从根本上讲,如果我们要设计的描述语言没有足够的表达能力,不能够精简高效地表达图片,字体,形状,颜色等桌面出版领域的业务对象,这个语言将不可避免地“难用”。一般来说,把领域特定语言设计得“好用”,需要深厚的领域知识 (domain knowledge)。所幸的是, PostScript 的设计者们,原先在施乐 PARC 从事激光打印机控制语言设计,对于桌面出版可算驾轻就熟。因此,他们毫不费力地选取了  Bézier 曲线,矢量字体,绘图路径(Path) 等作为整个绘图系统的基本结构。在对这些对象的操作上,PostScript 选取了平移,旋转,放缩等仿射变换,加上路径操作和字体控制,构成了一个强大但规整的绘图系统。

PostScript 绘图系统的设计深刻影响了后来的许多矢量图形系统。举例说,如今计算机使用的矢量字体均采用 Bézier  曲线描述,即起源于 PostScript;如今几乎所有的矢量绘图语言都支持的“路径”,也起源于 PostScript。我们不在此详细展开这些领域对象选取背后的原因。对 PostScript 感兴趣的读者可以阅读 PostScript Language Tutorial & Cookbook (也称 Bluebook) 以了解 PostScript 的一些基本概念。

 

PostScript 的语言设计

基本领域对象确定后,我们就可以换上计算机语言设计者的帽子,力求设计出一个“灵活高效”和“设备无关”的语言来控制这些领域对象。设计目标落实为具体需求,包含以下三个。第一,语言本身要能够表达曲线,字体,图片,形状等等领域对象;如颜色,分页以及这些对象的平移旋转等操作,在语言里最好也都是一等公民,能够直接表达。第二,语言的表达能力要足够强大,最好是图灵完全的,以支持现实中灵活的需求。第三,语言要与设备无关,也就是说,语言将运行在一个虚拟机或解释器上,而非直接编译为二进制代码。考虑到我们要设计的语言是针对桌面出版的,最终还要加上一条:这个语言的语法和结构要足够简单,使得非编程专业人士也能使用。

有了需求的指导,我们不难理解 PostScript 所采取的设计:以一个易用的,图灵完全的语言作为蓝本,加入众多针对桌面出版的对象操作,并实现一个轻量的,与设备无关的解释器。事实上,PostScript 是以 FORTH 语言作为蓝本设计的。选取 FORTH 的主要原因,是因为它是一个轻量级的,基于栈虚拟机的语言。FORTH 的表达能力和易用性当时已经被实践所证明,因此借用它的基本控制语法就是一个很自然的选择。

 

逆波兰表示法和度量单位

逆波兰表示法是 FORTH 和 PostScript 等基于栈的语言的一个鲜明特点。在 ALGOL 家族语言中,3乘以4的一般写法是 3 * 4,即运算符中缀。PostScript 将运算符后缀,写作 “3 4 mul”。意思是将 3, 4 分别推入栈中,然后将乘法(multiply) 操作运用于两个栈顶元素(弹出),并将乘积结果入栈。FORTH 仍然采用 + * 等数学符号。PostScript 规范化了所有的操作符,一致采用 add, mul 等单词操作符来代替 +, * 等传统的中缀操作符。我们将稍后阐明规整化的优点。这里我们只需要了解一点: PostScript 程序本质上是一个后缀表达式。PostScript  没有所谓的语法,只有栈操作。如果非要说有语法,那就是逆波兰表示法。这一点非常类似于 LISP:所谓的语法,就是 S 表达式。

PostScript 允许以闭包定义新操作符,其中,闭包是放在 {} 中的后缀表达式。比如,“乘以3”这个操作可定义为: /mul3 { 3 mul } def。这里,/mul3 表示取 “mul3” 的符号值。{ 3 mul } 是一个闭包,而 def 将 mul3 这个符号,映射到 { 3 mul } 闭包。据此,4 mul3 即为 4 3 mul。

其实,从语法上来看,/mul3 { 3 mul } def 和 3 4 mul 并没有明显的不同:都是前两个操作元入栈,最后一个操作符进行运算。也就是说,PostScript 的栈是异构的,符号,数字和闭包都可以放入栈中。许多操作符如 if ,也依赖于栈上有一个布尔值和一个闭包。这种不在栈中区分代码和数据的设计,允许我们重写栈上的闭包。实际上我们可以证明这个特性等价于 LISP 里的宏 (Macro) 的表达能力,限于篇幅我们不仔细展开。

现在,我们从这个 mul3 这个平淡无奇的例子出发,定义一个英寸 (inch) 的操作符: /inch {72 mul} def。一眼看去,{72 mul} 是闭包,而 inch 是长度单位,两者毫不相干,为何强拉在一起? 原来,PostScript 的基本长度单位是 1/72 英寸,因此 5 inch 即为展开为 5 72 mul, 或者说 360 个基本单位。Inch 的定义使得我们可以书写 1.2 inch 2.3 inch moveto 这样直观的程序。

用闭包定义常用度量单位在 PostScript 中并不少见。对于从未接触过这种定义方法的读者来说,相信 inch 这个例子让人印象深刻,因为它昭示了度量单位的实质:度量单位是后缀闭包。比如我们说 10 美元的时候,已经在自觉或不自觉地将“美元”单位替换成 {汇率 mul} 闭包,换算成 60 人民币等。实际上,任何度量单位之所以能够被我们感知,都是因为我们脑中的一个潜在后缀闭包的作用。在摄氏度体系下的人对华式温度没有感觉,或者仅接触一定数量级范围内的人对大数字不敏感,都是一个原因:我们尚未建立一个将不熟悉的单位或数量级转化为可感知的单位或数量级的闭包。

 

PostScript 的运行时字典栈

除了基本控制语法外,PostScript 引入了对于图形处理很重要的两个基本数据结构:字典和数组。可以想像,存有一系列点的数组可以表达一个字符的轮廓,而字典可以很好地表达一套字体。不仅如此,通过字典栈这个概念,PostScript 具有了 FORTH 和其他栈语言所完全不具有的动态特性。我们仍然以一个例子说明。

我们定义一个求直角三角形斜边长度的操作 hyp,即 /hyp { dup mul exch dup mul add sqrt } def (这里 dup 表示重复栈顶元素,exch 表示交换栈顶两元素,sqrt为平方根,读者可以自行验证这个函数的正确性)。 这里, 3 4 hyp 得到 5。

对于解释器来说,我们新定义的 hyp 与 mul 并没有本质的不同(后缀表达式和规则化带来的便利)。解释器处理这些操作符时,无论是语言预先定义的还是用户定义的,不可避免的需要进行符号表查找。可能的区别仅是到不同的符号表里查找。进一步说,一个叫 inch 的符号在没有进行符号表查找之前,我们根本不能确定这究竟是一个变量,还是一个闭包。

为了一致地处理符号表的查找操作, PostScript 引入了字典栈 (dictionary stack) 的概念。字典栈是一个由解释器维护的栈,而栈中的元素则是作为符号表的字典。解释器启动后,系统字典 systemdict 中含有所有预定义操作符和变量,如 add, mul 等。用户字典 userdict 将涵盖自定义的操作符和变量。用户也可以随时建立新的字典插入字典栈中。

以字典方式存储符号表是容易理解的,可是为什么需要把这些字典加入“栈”中呢?原来,PostScript 是按栈的顺序在字典中寻找操作符的。假如定义 “/mul {add round} def”,则当前字典里的 mul 会被优先使用,而系统定义的 mul 不再可见。乍一看之下,这和面向对象语言里提到的运算符重载概念类似。实质上,PostScript 的设计灵活许多。

首先,因为字典栈的存在,每个运算符都自动有了作用域(预定义的运算符因为存在于 systemdict 中从而有全局作用域)。通过字典栈,我们可以实现其他语言中的 lambda 表达式或者 Java 中的匿名内部类。PostScript 的运算符本质上是动态作用域的,但因为字典栈的存在,我们可以轻松实现词法作用域,方法即是在作用域中临时定义一个字典,在字典中定义新的操作符,并将字典推入字典栈。这样,只要在作用域结束时弹出临时字典,操作符定义也随之撤销。许多 PostScript 程序都采用这种方法构建用户自定义操作符:用户可以局部重定义分页操作符 showpage 以进行页面计数,局部重定义错误处理操作符 handleerror 处理异常等等。

其次,字典栈巧妙地支持了局部变量。和闭包一样,局部变量的本质是有作用域的值。基于栈的语言对函数局部变量是不友好的,因为局部变量本身是对处理器寄存器的抽象,访问局部变量也是采取随机存取而非按栈顺序存取的方式。而栈机器本身不直接支持寄存器抽象。熟悉 JVM 的读者都知道,JVM 的 {a,i,l,f,d}{load,store} 系列指令,非常繁冗地支持局部变量数组和栈之间的转存。在字典栈中,局部变量有了优雅的解决方法:通过建立临时字典,我们可以在不引入复杂的转存操作下随机存取随机变量,而且局部变量的作用域得到了保障。比如,以下程序定义了一个叫做 localvariable 的局部变量,作用域仅限于 /sampleproc。而将 something 换成 {something} 闭包,即是一个局部的操作符定义。

 

/sample_proc

 { 1 dict begin % 定义一个大小为1的临时字典

/local_variable something def

    end   % begin end 之间为字典元素

    …   % 具体的函数定义

 } def

PostScript 和语言的 Annotation

因为 .ps 文件本质是一个程序而非文档,打印 PostScript 文件的过程实质上是调用 PostScript 解释器执行程序的过程。因为 PostScript 的图灵完全性,在 PostScript 程序执行完之前我们对文档的结构信息,比如一共多少页,文档有没有彩色元素等等结构化的信息一无所知。PostScript 设计于在桌面出版业未起步时,因此仅仅关心绘制控制,并未考虑到如何表示这些结构信息,这样的缺憾是可以理解的。HTML 语言也经过了这样的道路:早期引入 FONT BIG 这种纯展示标签,而如今最佳实践是将结构信息放入 HTML,而将格式信息交给 CSS。

因为 PostScript 的成功,越来越多的人希望作为桌面出版标准格式的 PostScript 能够包含文档结构信息。比方说,如果打印管理系统能够在将 PostScript 任务交给打印机之前知道文档的页数,就可以更好的调度打印任务,或者按页面收取费用等。这些关于文档的结构信息并不影响页面的展示,却是文档不可或缺的一部分。

为解决这个问题,PostScript 用户自发地定义了一种通过注释表示文档结构信息的方法。比如,在一个10页的文档开头加入 %%Pages: 10,每一页的开始加入 %% Page N 等等。因为是注释,PostScript 解释器可以选择忽略它,而其他程序则可以据此管理文档。许多桌面出版软件也采取这样的方法写入作者,创建日期等信息。在强大的需求和既定行业标准的驱动下,Adobe 终于决定标准化这些用来表征文档结构的注释,发布了一系列的“文档结构约定(Document Structuring Conventions)”。之所以叫约定,因为木已成舟,无法强行要求每个 PS 文档管理器或打印机都遵守标准。

DSC 使得静态结构检查变得可能。前文提到,PostScript 语法就一种——后缀表达式,静态语法检查并没有意义,而正确性检查却又非常难。引入文档结构约定后,我们就有条件检查一些约束,比如在宣称的描述一页的区块之内没有非法的分页操作等。DSC 不影响现有语言逻辑,却引入了新的语义正确性约束。

DSC 这种引入新的元信息以静态检查程序的语义正确性的思想非常有前瞻性。可惜的是,因为了解 PostScript 的人较少,这样的思想没能在其他语言中实现。Java 5.0 才正式引入了 annotation 的概念,用 @override 这样的标记帮助编译器检查方法多态。Python 2.2 引入 classmethod, instancemethod 等 decorator 以检查方法的定义,而 C++ 最近才正式支持 annotation。这些比程序本身要抽象的元信息,越来越多地成为了自动分析工具的帮手。在 Google,我们采用一套线程安全的标记以帮助编译器静态检查代码的线程安全性。所有的这些,都成了提升开发效率的好帮手。以文档标记等方式记录元信息的思想可以追溯到 D.E. Knuth 的文学编程 (Literate Programming),而 PostScript,是我所知的第一个以元信息约束程序语义的编程语言。

 

其他一些有趣的历史

PostScript 语言的历史很有趣也很能给人启发,限于篇幅我仅录几则。首先,PostScript 其实和 Smalltalk 很相似。因为同样出自于施乐 PARC 的研究,PostScript 语言风格受到 Smalltalk 影响很大。比如闭包的设计,if 和 repeat 语法的设计,几乎就是 Smalltalk 的翻版,仅在运算符顺序上有区别。

Adobe 的几位创始人从 PARC 独立出来后,最初力图开发一套打印机控制语言。熟悉这几位创始人的 Steve Jobs 认为,这个语言最重要的任务不是控制打印机,而是制作高品质文档。在 Jobs 的推动下, Adobe 开发了一套可以支持 Apple 当时正在开发的 LaserWriter 激光打印机产出高品质文档的语言: PostScript。从此,Adobe 这家毫不起眼的小公司一举成为桌面出版革命最大的受益者。

因为 PostScript 语言灵活复杂,解释 PostScript 语言需要强大的微处理器。为此,Apple LaserWriter 携带了一颗 12 MHz Motorola 68000 处理器。而同时期的,与之相连的 Machintosh 携带的是一颗 8MHz 的 Motorola 68000。打印机处理器比主机的强大,用现在的眼光看是不可思议。桌面出版的革命来得如此之快,需要的计算能力如此之大,是个人计算机行业所没有预见的。或许,未来的 3D 打印技术或量子传输技术 (Star Trek transporter) ,会让这种情况重新出现。

May 11, 2014 - 编程珠玑番外篇-O 中间语言和虚拟机漫谈

Comments

本文原发于《程序员》2014年3月刊

导言

编程语言的发展历史,总的来说,是一个从抽象机器操作逐步进化为抽象人的思维的过程。机器操作和人的思维如一枚硬币的两面,而语言编译器就像是个双面胶,将这两面粘在一起,保证编程语言源程序和机器代码在行为上等价。当然,人本身并不是一个完美的编译器,不能无错的将思维表达为高级语言程序,这种偏差,即Bug。因为编译器的帮助,我们可以脱离机器细节,只关心表达思维和程序行为这一面。

编程语言的发展日新月异。特别是随着对问题的深入理解,新的设计思想,语法构建和新的领域相关语言(DSL)层出不穷。而硬币的另一面似乎一直波澜不惊。这是自然的——无需关心底层架构的变化,或者目标代码生成优化等技术的进化,正是编译器带给我们的好处,因为这些细节和要解决的问题往往关系不大。

尽管所受的关注度不高,这些底层的技术一直在持续地进步。特别是这十年来,一场大的变革正在悄悄发生。这场变革,就是中间语言和虚拟机几乎成为了编程语言的标配——编译器不再以机器的CPU指令集作为编译目标,而是生成针对某种中间语言或虚拟机指令集的目标代码。这场变化是深刻的,它意味着编程语言的设计者自此完全脱离了具体硬件平台的束缚,语言如何设计和如何执行成为了两个完全正交的系统。这个变革大幅度降低了创造一个新语言的成本,一下子把我们推入了一个语言井喷的时代。

从抽象语法树到中间语言

熟悉编译器设计的读者都知道,编译的第一步是构建一个叫抽象语法树(AST)的数据结构 (脚注: 语法树这个概念来源于 LISP)。有了这样的数据结构后,解释器和编译器在此分野。以 AST为起点,解释器完全可以遍历语法树,递归执行每个子结点。IEEE POSIX (或称标准UNIX) 规定的 AWK 语言,其经典实现就是一个生成和遍历语法树的过程:

syminit();

compile_time = 1;

Node *winner ; /* root of parse tree */

yyparse(); /* generate parse tree */

if (errorflag == 0) {

compile_time = 0; /* switch to execution */

run(winner); /* execution of parse tree starts here */

}

Awk 这样的传统解释器的优点在于结构简单,开发便利。事实上许多领域专用语言都采取这种方式实现,如 PostScript, Matlab, R 等。

解释执行的缺点也是显而易见的。首要的一点就是每次执行都需要重新生成语法树。领域专用语言或许可以忍受每次零点几秒的重复解释过程,而对于可以开发大型应用的通用编程语言来说,这一点是致命的。每次重新生成语法树也意味着这样的语言难以用于资源受限系统,因为

语言本身语法结构复杂,布置一个解释模块的代价往往非常高昂。为了避免解释执行的这些弊端,传统的编译器致力于只解释一次,将通用语言的语法树,直接转变为目标机器的 CPU 指令。传统的 FORTRAN 和 C 编译器就是如此设计的。有些编程构建,如 C 语言中的 i++, 甚至是直接受 CPU 指令影响的产物。

上个世纪 80 年代后期,随着对程序效率优化和 LISP 机器的研究,研究者们认识到,其实传统的编译和解释并不是对立的概念。特别的,编程语言的语法树转变可以为一种中间指令格式。这种中间指令格式贴近机器指令,可以进行运行效率优化。传统的以生成目标指令的编译器,可以将中间语言简单转为机器指令。而解释器,也省却了多次的语法树生成,而直接解释相对简单的中间语言。

较早在中间语言上进行探索的是 MIT 的 LISP 机器。如 Thomas Knight,他的研究集中在如何在硬件上实现一个高效的 LISP 环境。显然,没有一个硅片可以直接运行 mapcar,但设计一个支持 mapcar 的中间语言并不困难,只需要支持一些基本的列表操作即可。这种设计思想影响了很多后来的系统。流行的 GCC 编译器,从结构上来说分前端和代码生成端两部分。连接两者的中间语言 RTL 的基本一些指令,都可以追溯到 LIPS 机器的指令集。

中间语言和虚拟机

中间语言可用于程序优化的原因是显而易见的:这种中间格式既贴近机器代码,又保存了原有程序的结构。程序优化并不是一门魔术。像循环展开,死代码消除等技术,都依赖于程序控制结构,而中间语言可以保持这样的控制结构。事实上,目前我们所知的编译优化技术,无一不是建立在结构分析之上。中间语言的出现让程序优化成为了一个独立的问题。原本单列的 C 程序优化, FORTRAN 程序优化如今统一归结为 RTL 程序优化。编译器前端可以千差万别支持许多语言,但负责优化和翻译为目标代码的后端均归为一个,就此一点,就大大简化了语言编译器的设计门槛。现如今,几乎没有一个语言设计者需要考虑如何生成高效目标代码了。

当然,中间语言的作用并不仅限于目标代码优化。如果我们把中间语言也当作一种语言的话,不难发现中间语言甚至比原语言更加普及。 比如,Java 虚拟机(JVM) 语言实际上是一个比 Java 语言成功许多倍的产品。JVM 存在于众多Java 语言不存在的地方。像 Jython, Scala 和 JRuby 这样的语言,均依赖于 JVM, 而非 Java 语言本身。

语言的虚拟机的本质,是一个可以运行中间语言的机器。 在实际硬件上,程序和数据是两个截然不同的概念;而对于虚拟机来讲,中间语言程序,只是虚拟机程序的输入数据罢了。这种将程序当作数据的处理方式,带来了我们熟知的许多虚拟机的优点,如跨平台特性,安全性等等。 因为程序即是数据,为虚拟机读取中间语言程序方便,其指令往往都是以字节为单位,故称为字节码 (bytecode)。 相比之下,计算机的 CPU 指令则可长度不一,也不一定占据整数个字节。

程序是数据这个特性使得虚拟机可以做到跨平台和沙箱安全;反过来,数据是程序又使得虚拟机可以用在一些意想不到的地方,使数据更加灵活。 目前通行的轮廓字体描述语言 TrueType 就是成功运用虚拟机来更加灵活地处理字体的一个例子。

TrueType 是一种采用数学函数描述字体的矢量字体。 矢量字体在理论上可以自由缩放。而实践中,因为显示器本质上是点阵的,所有的矢量字形都要经过栅格化 (rasterization) , 将矢量轮廓近似转化为像素点的透明度。 然而,这种近似并不是随意的。 以汉字 “中” 为例,为保证其对称美观,我们必须约束栅格化程序,保证任何时候左右两个竖线与中间一竖的距离相等,哪怕为此不惜将此字缩减或放宽一两个像素。 这类约束又被称作提示 (hinting)。 它对于字体至关重要—缺少提示的矢量字体在字形较小时不可避免地会出现失真,变形和锯齿等现象。 不难理解,本质上“提示”是一个以字体轮廓和字形大小为输入,以栅格数据为输出的程序。 因为此,TrueType 包含了一套虚拟机指令,方便字体设计者表达这种提示。 可以想象,如果没有这个虚拟机的存在,设计灵活的矢量字体是不可能完成的任务。 实际上,我们所见到的几乎所有的矢量字体文件,都是一个数据和程序的混合物。 从另一方面来说,每个字形都需要一个专门的“提示”,也从一个侧面说明了设计高质量的中文字体之难度。

基于栈,还是基于寄存器

凡提到虚拟机,绕不过去的第一个问题就是这个虚拟机是基于栈的,还是基于寄存器的(有些虚拟机,如 LISP 机器,可以同时有栈和寄存器)? 尽管这里“寄存器”和“栈”,都不一定直接对应到机器CPU的寄存器或者内存里的栈。这个问题之所以重要,因为它直接决定了虚拟机的应用场景。一般说来,基于栈的虚拟机结构相对简单,且更加适合资源受限系统。 比如上文我们说的 TrueType 虚拟机,结构简单,功能专一,就是基于栈的。

尽管所有的计算机的存储模型都是构建在图灵机的无穷纸带模型上,实践中所有语言都或多或少依赖于栈模型。特别的,函数调用就等价于栈的推入和弹入操作,其他操作均可抽象为对栈顶元素进行。相比之下,寄存器模型虽然贴近真实机器,却并不够直接:很少有高级语言直接制定寄存器如何分配的,因此编译器的作者需要考量寄存器分配问题。而基于栈的虚拟机的所有指令都可默认为对栈顶元素操作,结构简单,且暂时绕开了寄存器分配难题。

基于栈的虚拟机更加适合内存和 CPU 处理速度等方面有限的系统。同样的源程序,在目标代码的体积上,面向栈虚拟机上生成的代码更加小。这是容易理解的:基于栈的虚拟机的指令默认对栈顶元素操作,因此指令只需为 OP 格式,无需 OP Reg1, Reg2, Reg3 等额外指定寄存器。这个设计也绕开了指令解码问题。平均上说,基于寄存器的虚拟机生成的指令的体积比基于栈的要大。我们见到的许多基于栈的虚拟机,都是为资源受限系统设计的。JVM 的初衷是一个运行在电视机顶盒中的小系统,后来精简版本的 JVM 甚至可以放到智能卡上;Forth 语言的虚拟机是要用在计算机固件(Open Firmware),航空系统和嵌入式系统中;控制打印的 Postscript 是用于高品质打印机中。很显然,机顶盒,引导固件和打印机都是资源受限的系统,这些系统中的虚拟机,不约而同都是基于栈的。值得一提的是,因为实现简单,许多并非用于受限系统的通用语言的虚拟机也是基于栈的,如 Python, Ruby, .NET 的 CLR 等。

基于寄存器的虚拟机,是为性能所生。引入寄存器假设固然关上了用于资源受限系统的门,却也打开了一扇通向进一步性能优化的窗。栈虚拟机的一大缺点就是要不停地将操作数在堆和栈之间来回拷贝。比方说一个简单的三个参数的函数调用,在传递参数上就需要至少三次入栈和出栈操作,而在寄存器上只要指定三个寄存器即可。现代处理器提供的通用寄存器支持,本身就是为了减少这类值的来回拷贝。尽管有 Hotspot 这样的技术能够将一段栈虚拟机指令转化为基于寄存器的机器指令,可毕竟没有直接从支持寄存器的中间语言翻译直接。前面说过,保持程序的结构是优化的先决条件。失去了“指定三个值”这样的结构的栈虚拟机,需要运行时间接的推断这个操作。而直接指定这些访问结构,将值直接映射到 CPU 的寄存器,正是这类虚拟机运行效率高的要点所在。Android 的 Dalvik, Perl 的 Parrot 都是基于寄存器的虚拟机,而 LLVM 则是基于寄存器假设的中间语言。其中,为了让 Android 程序更加快的运行,Google 不惜放弃 JVM 的指令集,而选择将 JVM 指令转化为基于有限个寄存器的 Dalvik 指令集。 Parrot 和 LLVM 则更加自由一些,假设了无穷多个寄存器。无论是有限还是无限个寄存器,省却不必要的值拷贝是这类中间语言的最大优点。

JIT 和直接执行

JIT (Just-in-time) 是运行时的动态编译技术。不难看出,JIT 是针对中间语言的——将原语言的编译推迟到运行时并无意义,将中间语言的解释,部分转化为编译后的机器代码,则可以优化运行效率。JIT 之所以可行,一个基本假设是程序大多存在热点。D. E. Knuth 三十年前观察到的一个现象: 一段 FORTRAN 程序中不到 4% 的部分往往占用超过 50%的运行时间。因此,在运行时识别这样的热点并优化,可以事半功倍地提高执行效率。

按照 Jython 作者 Jim Hugunin 的观测, JIT 技术出现后,同样功能的程序,运行于 Java 虚拟机上的字节码和直接编译成二进制代码的 C 程序几乎一样快,有的甚至比 C 快。乍一看虚拟机比原生代码快,理论上是不可能的。而实践中,因为 JIT 编译器可以识别运行时热点做出特别优化。相比之下,静态编译器的代码优化并不能完全推断出运行时热点。而且,有些优化技术,如将虚函数调用静态化,只有在运行时才能做到。在对热点深度优化的情况下,JIT 比直接生成的机器代码执行效率高并不是一件神奇的事情。引入了 JIT 的,以 Python 书写的 Python 执行器 pypy, 运行速度要比以 C 实现的 CPython 解释器快一到五倍,就是 JIT 技术魅力的一个明证。

尽管 JIT 技术看上去很炫,实践中也能够做到几乎和原生二进制代码速度相近,我们必须承认,这只是一种补救相对慢的中间语言解释的一种措施罢了。设计语言平台时,设计者可能因为这样那样的原因而选择中间语言/虚拟机解决方案,或因为针对嵌入式系统(Java),或因为跨平台要求(Android Dalvik),或者仅仅因为设计者想偷懒不愿写一个从语言到CPU指令的编译器(Python/Ruby)。无论原因为何,当最初的原因已经不存在或不重要,而性能又成为重要考量的话,采用中间语言就显得舍近求远。JavaScript 引擎的进化就是一个生动的例子。

JavaScript 语言最初只是一种协助 HTML 完成动态客户端内容的小语言。Netscape 浏览器中的JS 引擎,最初只是一个简单的解释器。自2004 年 Google 发布 Gmail 之后, Ajax 技术的发展对 JS 引擎的速度提出了更高的挑战。JavaScript 引擎的速度被当成一个浏览器是否领先于对手的关键指标。在此情况下,众多浏览器厂商纷纷卷入了一轮 JS 引擎速度的军备竞赛。

最先挑起这场战争的是 Firefox, 目标是当时占据90%市场的 IE。Firefox 3 于2008年6月登场,其 JS 引擎 TraceMonkey 在栈虚拟机的基础上首次采用了 JIT 技术,在当时众多标准评测中超越了IE7。就在当月,WebKit 开发小组宣布了基于寄存器的 Squirrelfish 引擎,殊途同归,也是基于中间语言,尽管两者互相不兼容。

到9月,Google 发布了第一个版本的 Chrome 浏览器以及新的 JS 引擎: V8。V8一反使用中间语言的设计套路,力求将 JS 直接编译到本地代码。Google 毫不掩饰 V8 在标准评测上比其他浏览器快的结果,因此造成了 Firefox 和Safari 开发者对各自 JS 引擎速度评测的一场恶战。到了9月的时候,Firefox 和 Safari 各自的引擎都比6月份的结果快到 20%到60% 不等。 而 V8 也赢得了许多眼球,催生了之后的 Node.js 项目。

这场军备竞赛的一个结果,就是 V8 以外的引擎,也开始探索绕过中间语言从 JavaScript 直接生成二进制的可能性。SquirrelFish Extreme 就是自 Squirrelfish 衍生出来的一步本地代码的引擎。值得注意的是,尽管都是生成本地代码,V8 和 SquirrelFish Extreme 这样的编译器,并不是退回到传统的编译器技术上,因为他们已经吸收了许多对 JIT 编译器性能的研究成果。

就在我写这篇文章的时候,Google 正在将 Android 执行环境,从原来的 Dalvik 虚拟机,换成可以直接生成机器代码的 ART 架构。ART 负责在 App 安装后一次将跨平台的字节码分发格式,编译成原生机器代码。20 多年前,为了跨平台,Java 采取了虚拟机的设计方案。如今,中间语言的跨平台的部分依然保留,但作为已经不直接参与执行了。硬件的进步带来的中间语言和虚拟机设计的进化,是当时的设计者如何也想不到的事情了。

May 29, 2013 - 现代人的必备知识:药理学

Comments

人们常说,是药三分毒。我们感性地知道药物是有毒性的,但轮到生病的时候,多数人还是会寻求药物治疗,而把“是药三分毒”放在了一边,或者“相信”药物的效用超过了毒性。这种相信,大多数时候并不是出于我们的理性的判断,而是依赖于医生的判断,以往的经验,或者药物本身的说明书。

 

其实,作为一个现代人,我们完全有能力,也负有对自己和自己爱的人的责任,去了解药物的具体毒性,以理性地,正确地选择药物,从而走出感性地“是药三分毒”的认识,切实地了解药物的毒性。研究药物作用机理和毒性的知识的学科,叫做药理学(Pharmacology)。

 

药理学关心的是药物的结构,作用机理,代谢方式,毒性等等的知识。这些知识看上去名词一大堆,牵涉到化学,分子生物等若干领域,其实只要掌握了一些基本的概念,一个受过高中教育的人完全可以理解。事实上,在美国,药理学是护士培训的必修课。护士并不比大多数读者具有更多的生物,化学或者科学知识。

 

以一个很日常的例子说明一下药理学的作用。几乎所有人都用过的退烧药。常用的退烧药包含阿斯匹林 (Aspirin),布洛芬 (Ibuprofen),扑热息痛 (Paracetamol,国内又叫百服宁,必理通或者泰诺) 三种。现在请听两道题题:1)这三种药一天一次还是一天多次,如果多次,间隔多长为好?2)如果你同时有胃溃疡,或者肝功能不好,该选择哪种药物?读者要说了,我又不是医生,我哪儿知道?其实,如果你有一些基本的药理学知识,回答以上问题轻而易举。

 

药一天吃几次的问题,其实就是人体多长时间将药代谢掉的问题。在药理学里,我们用“半衰期(half life)”来衡量药物的代谢速度。如果你到英文维基百科上,分别输入 Asprin, Ibuprofen 和 Paracetamol,在右边的框里,很容易看到这三个药物的半衰期(300mg, 3.1-3.2小时,1.8-2小时和1-4小时)。人体对药物的代谢是非线性的,但从半衰期我们可以大致估计到在症状持续的情况下,这些药不可能在体内持续作用 24 小时。所以如果症状持续,我们可以一日多次服用。像扑热息痛,因为半衰期已经长达 4 小时,所以服药间隔最好要在 4 小时之上,这都是有药理学知识的人一眼看出的常识。再比如说,同样是抗生素,两颗阿红霉素(Azithromycin) 的半衰期长达68小时,而阿莫西林(Amoxicillin) 只有一个小时。所以你去药房拿药的时候,药剂师会给你几颗阿红霉素,或者一盒子阿莫西林。掌握药理学常识可以帮助我们理解这些药物之间的差别,并记得按时服药。

 

药理学还研究一个药物的代谢途径,比如,是通过肝脏,肾脏还是其他,具体的代谢通道是什么。有了一些基本的药理学知识,我们就知道如果一个人肝功能有损伤,则要避免通过肝代谢的药物。家里养猫的人可能都知道,Paracetamol 对猫有剧毒,原因就是 Paracetamol 是肝代谢的,而猫的肝恰恰没有代谢 Paracetamol 所需要的酶。又比如说,阿司匹林 和布洛芬在药理学上都属于NSAID 药物。NSAID 药物的一大副作用是能够导致消化道溃疡,所以有消化道溃疡前史的患者最好谨慎服用。总之,虽然这些药都是属于“退烧药”,通过药理学,我们可以详细探究这些药的异同。如果我们知道了一个药的代谢渠道,在通过简单的基因测序如 23andme 知道我们自身有无相应的酶来代谢这些药物,在选择药物的时候,就不会像猫一样盲目地把 Paracetamol 往嘴里送,也不会因为无知而莫名其妙地把所爱的人推向危险的境地。

 

言而总之,药理学知识可以帮助我们了解药物。现代药的说明书说白了是很严谨的药理学试验报告,而药理学知识就是读懂这个报告的钥匙。我相信药理学可以帮助我们更加科学和透明地选择和服用药物,让我们和我们所爱的人的生活更加美好。

 

这个世界上有很多所谓的“传统医学”,而且信徒还不少。不管这些传统医学多么博大精深,多么神奇,如果这些传统医学给我或者我所爱的人开的药没有药理学支持,那么我们作为一个现代的,理性的人,唯一可做的,而且是最负责的,就是拒绝这些药物。把这些药物往嘴里送,就是接受了“是药三分毒”,而且还不知道是哪三分。

PS: Coursera 上有  Fundamentals of Pharmacology 的公开课。我上过,受益无穷。