Jan 4, 2017 - AI 创业的一点思考

Comments

2016 年 8 月,我从 Fitbit 离职创业,做一个用 AI 帮助程序员更好的写代码的公司。在过去的四个月里,通过无数的模型,产品和数据的迭代,加之和用户交谈,以及观察其他的创业者,我积累了一些想法,写下来抛砖引玉。

此 AI, 是名 AI, 非 AI.

这一波的 “AI” 创业热潮,准确的说应该是“深度学习算法”创业潮。人工智能本身是一个涵盖极大的领域,除了学习和表示(深度学习的主要领域)之外,还有推理,规划等等其他大量分支。普通人理解的人工智能,大多数都是“强人工智能”的范畴(一个可以完全代替人的智慧的机器)。而大量的创业公司都纷纷采用 .ai 做为域名后缀,实质上只是在“深度学习”这个子领域,解决一些特定的,以前只能靠人的智慧才能解决的问题。

就和 .com 时代一样,域名后缀的符号意义远大于实际意义。媒体,投资人和创业者都默默接受了 .ai 这个集体幻觉。总的来说,目前 AI 公司的井喷,是深度学习这项技术完成其技术扩散 (diffusion of innovations) 的体现。在 Google, Facebook 等技术领先企业的示范和大笔收购下,风险投资大量向 AI 倾斜。许多掌握机器学习和深度学习的人才,认识到深度学习可以用来解决一个具体的问题,也流动到创业公司开始创业。因为 AI 入门门槛很高,目前还是很容易从创业者的教育和工作经历来甄选到底一个公司做的是不是深度学习,还是挂羊头卖狗肉的。

深度学习的确“创造”了许多创业公司可以挑战的新问题

有许多了解和从事机器学习的人,并不觉得这一波的“深度学习”技术有多神奇。这是可以理解的,因为深度学习的主要技术 30 年前都齐备了,只是最近被某种魔法召唤出来。在我看,这一波的 AI 创业潮,不是泡沫,是对多年没有在工业界铺开的机器学习技术的复仇。过去的十多年中,我们经历了互联网时代,社交网络时代和移动时代。有了众多的站点,社交网络和应用。机器学习和云计算解决了许多问题,如搜索引擎,大数据处理,但仍有许多问题,如图像,视频,语音,自然语言的处理,都是传统的机器学习方法没有能很好解决的。深度学习的出现,使得解决这些问题成为了可能。

解决问题的工具进化后,以前大家没觉得是问题的(主要是解决不了),现在变成了问题。一个最简单的例子是自动驾驶。我在 Google 自动驾驶部门工作的时候,视觉系统还是用的传统的物体识别方法,有许多规则和边界情况要额外处理。汽车一方面需要额外引入其他传感器的数据做判断,另一方面需要不断分解自动驾驶问题为行人识别,自行车识别,信号识别等子问题。所有的子问题加起来,工程复杂度太高,创业公司是很难组建出一个能解决这个问题的团队的,而且所谓的“解决”,也不能达到商用的地步。拜深度学习所赐,如今从视觉信号,模仿人类驾驶行为,就可以做到高质量的巡航控制。这时候,自动驾驶问题就变成了一个创业公司可以挑战的问题。2016 年这个领域新闻一个接一个。Cruise 今年被 GM 收购,Comma.ai 获得了 A16Z 的投资等等,都是自动驾驶领域创业公司成功的例子。在许多的细分行业,这样被深度学习“创造”的新问题不胜枚举。然而,

想要成功,单解决一两个问题是不够的

深度学习是一项技术。这个黑科技可以作出更加准确的机器学习模型,但更好的模型仍然要通过产品落地。特别是创业公司,在没有相关平台支撑的条件下,解决一两个问题很难给用户带来实际价值。在技术史上,没有一家技术公司是依靠一个领先的机器学习模型就成功的。即便 Google 这个以 PageRank 为核心算法起家的技术公司,也是通过将技术包装成一个优秀的搜索引擎而落地的 (当年的 Yahoo! 甚至还看不上这个技术)。

这里面的原因,可以分成 To B 和 To C 两个方向来说。

目前深度学习所解决的问题,大部分都在图像,人脸,视频,文本等领域——因为深度模型大部分都是为解决这些问题而设计的。靠一两个深度学习专家,创业公司完全有实力去挑战如图像分类,语音识别等通用问题。然而,解决通用问题的门槛只有一个:只要跳过了这个门槛,前方就很难再建护城河了。对用户有价值的通用问题,特别是 To B 的通用问题,一定是对巨头有价值的。2016 年,Google 和 Microsoft 都发布了图像,语音识别等通用 API。一个明确的趋势是,云服务商正在把这些基于 AI 的服务做成平台的一部分。在同样的图像分类服务面前,巨头的服务一定比创业公司要廉价。如果没有巨大的先发优势。创业公司在这个方向很难抵抗云服务巨头的侵蚀。此外,把针对通用问题的机器学习模型,浅包装成一个 API,的确容易切入市场,但也容易被巨头和其他创业公司碾压。现在市场上有许多浅包装深度模型的公司,提供如“鉴定黄色图片”等服务。在我看来这些服务的可替代性太强,大家技术差别也不大,最终能胜出的,只会是一两家有先天优势的公司(比如云服务巨头,或者第一个进入市场的公司)。To B 的 AI 创业公司的挑战不在技术上,而在产品创新上。怎么制造差异化服务,让这个服务无可替代——这就看各家公司的想象力了。

在 To C 方向,2016 年许多创业公司都做了很多尝试。今年很火的 Prisma, 就是将风格迁徙神经网络运用到用户照片上,将照片转换成各种艺术家风格。Prisma 可以算是提供了一个杀手级的特性了。即便这样,创业公司想靠一个特性和巨头竞争也是不可能的。Prisma 不可能靠这一个特性取代 Instagram,即使 Instagram 没有这些人工智能的滤镜。原因很简单,IG 控制了移动时代的大量的用户群,因此 Prisma 制作的照片最终还要通过 Instagram 才能传播出去。To C 方向的先发优势是不可估量的:一旦用户形成使用习惯和网络效应,再好的 AI 产品也很难转化现有用户。其实这个问题困扰所有的公司。比如 Google 今年连续在 Gmail, Google Docs 里做了许多 AI 创新,还发布了 Allo 这个全新聊天工具。可是,大量用户依然用着 Office 和 Facebook Messenger。

说了这么多,好像很悲观。To B 和 To C 都困难重重的样子。其实机会还是非常多的,只是没有“AI = 创业机会”这样一个自动成立的等式而已。

AI 创业公司的优势

先说什么不是优势,或者护城河。其一,如果创业是凭借着一个“独特的算法或模型”,这个切入点是靠不住的。AI 创业已经过了 2014-2015 巨头为了收人而收购公司的阶段。目前投入到创业浪潮中的,都不大可能是当时巨头收漏了的。在这种大环境下,没有任何一项技术是别人不知道的,或者非常领先所有竞争对手的。目前宣称有独特模型和算法的,是把赌注押在一个特定的方法上,而和全世界的所有研究者竞争。目前来说这注定是无效的——谁也不知道明天 DeepMind 会公开什么黑科技,一下子超越了你的独特模型。或许在这个赛道上再走几年,有些公司的确能够领先其他。目前大家都在同样的起跑线上,模型或者算法的领先可以忽略不计。

其他,“把标准问题做到极致”既不是护城河,也不是竞争优势。如果回到 2012-2014 年,哪个创业公司能够用深度学习在 ImageNet 上刷出第一,肯定是立即像 DNNResearch 那样被巨头揽走。其中一个原因,是用深度学习的人太少了。现如今,世界上攻克标准问题的团队,百分之百都是用深度模型。当全世界的学术团队都来刷榜的时候,创业公司耗散精力去刷榜是不经济的。而且,刷榜要求的,许多时候是特定的工程技巧,未必能用到产品中。一个典型的例子是当年 Netflix 竞赛的第一名,它们的模型过于复杂,没法产品化,Netflix 最终也没有采用

在我看来,AI 创业,还是要落实在深入解决一个非标准(不能拿标准的深度学习模型一套就能用)的问题上。只有在非标准的问题上,切实的了解用户需求才变成可能。标准的问题,如图像识别,自动驾驶,可以说,最终产品的亮点大家都差不多,因此人工智能也就不自动成为一个亮点。在非标准的问题上深耕,无形中就构建了两个护城河:1,竞争对手需要花时间了解这个问题之后才能提出解决方案和产品;2,你比竞争对手先收集许多解决这个领域特定问题的数据,因此在同一时间节点上,你的模型永远领先对手几个月。这就像微软的搜索引擎或许使用的模型很先进,但因为没有足够的数据因此质量永远落后 Google 几个月一样。

最后的话

解决非标准的问题,需要的就不仅仅是 AI 人才。对特定行业的了解,痛点的把握,对用户的理解等等,往往比 AI 更加重要。在这一点上,AI 创业者可能会死磕模型和数据,或者只想着找最顶尖的 AI 研究者,而忘记了真正对用户有价值的东西。模型只是整个产品世界里很小的一部分。AI 创业公司不代表 AI 是唯一重要的事情,这一点算是我前面四个月学到的一点经验。

Oct 23, 2016 - 深度学习 Meetup 总结

Comments

前几天参加湾区同学技术沙龙组织的一次专门面向深度学习的 meetup。做了一些笔记如下。

这次活动的嘉宾包括 Google 的 Yonghui Wu (GNTM 系统一作),Kai Chen (Google Brain 早期成员,经典 Word2Vec 论文共同作者),Yuan Li (Google Research TLM),以及 Zhenghua Yu (VP, Bocom).

因为活动以问答形式展开,我也以问答形式记录。

Q1: 这几年深度学习方向有哪些很重要的突破?

Yuan 首先谈到了视觉领域的一些突破。实际上我们都知道引爆这轮深度学习热潮的,就是 2012 年把第二名甩出十几个百分点(以分类精度测量)的 AlexNet. 在 AlexNet 之后,视觉领域比较有代表性的几个网络是 Oxford VGG, GoogLeNet (Inception Module), ResNet 和最近的 InceptionResNet.

Yonghui 和 Kai 谈到了自然语言处理里的一些突破。大家熟知的 Word2Vec 以及后续的一些工作如 GloVe. Seq2seq 做为一个通用框架已经在自然语言处理领域四处开花,包括翻译,标注等一系列的自然语言处理任务都可以直接上 Seq2seq.

Q2: 还有哪些有趣的 AI 问题值得探究?

众多嘉宾都纷纷表示尽管这个领域现在 hype 很多,总的来说这个领域才刚刚开始,要研究的问题很多。在理论层面就有许多亟待解决的问题。在具体的应用层面,尽管翻译和语音识别等等问题看上去都已经解决,但开放式的对话问题仍然没有解决。从深入生活的应用来看,可以和人交流和帮助完成家居任务的机器人,可以做为医疗助手的人工智能,可以智能控制交通的调度系统等等都是很有趣的问题。Yuan 还提到了目前在视觉方向搭更大更深的网络已经不是潮流了,更多的分类标签,更加难的基准,如 MsCoCo,是现在众多研究者的发力方向。

Q3: 深度学习取得的进展更多是科学还是工程上的?

在这个问题上,Yonghui 非常具体的谈了他实现 GNMT 的经历。NMT 的构想,最早可以追溯到 Yoshua Bengio 的 Word Embedding 开山之作,A Neural Probabilistic Language Model。 之后,词嵌入技术,Seq2seq 框架,以及 Attention Model 等等一起,奠定了 NMT 的理论基础。然而,NMT 最早在基准数据上,效果是低于 Google Translate 所采用的 phrase-based translation 系统的。即便这样,NMT 代表了一种新的范式,可以用大量的数据来训练模型,提高翻译质量。

按照 Yonghui 的叙述,GNMT 系统是工程学的胜利:他们从一个研究性的系统开始,引入了深度学习工程上熟知的一些技术,比如 Attention Mechanism, word piece model, residual links。最终,将模型成功的放到了 Tensor Processing Unit 上而不显著损失模型精度。所有的这些,都应该是工程学的胜利。至于科学上的贡献,就是毫无疑问地证明了 NMT works.

Q4: 中美两国在深度学习的开展上有什么不同?

嘉宾都一致认为,深度学习方向上奠基性的工作还是在北美完成的。中国的深度学习开展还偏于应用层面。不过中国的优势是,真实应用的数据集比北美大而且获取成本低。或许中国在深度学习方向上可以出现一批在北美不会出现的应用。

Q5: 在深度学习工作上遇到过哪些坑?

Kai Chen 博士在这一点上举了一些具体的例子。比如,在 debug 模型时,将数据低维化,可视化,比如用 t-SNE 将数据映射到二维。另外,必要时要打开神经网络的黑盒子,让模型可解释。不可解释的模型往往也很难调试。Yu 博士则提到要规划数据采集。因为数据采集是一个费时费力的事情,要在一开始就规划好,控制好数据的噪音,并且争取一次收集足够的数据,因为二次采集时可能一些指标已经和第一次不一样。Yonghui 也提到了翻译模型里的一些失败情形,在这种情况下要知道模型的大致应用范围,使得模型在合适的工作条件下发挥作用。

Q6: 对转行做深度学习的建议

几位嘉宾都表示他们原本也不是从事深度学习方向工作的,都是最近几年进入这个领域的。因为深度学习领域有众多的开源框架,并且还在快速的发展中,几位嘉宾都表示现在进入对于初学者是最有利的,因为即使是深度学习的老手,也要天天跟踪最新的研究成果,以保持知识的及时更新。

Yuan 还举了一个非常经典的例子(其实是两个例子)。一个是 Christian Szegedy, 原本是数学家,从事逻辑电路的设计,后来转行从事深度学习,凭借在数学上的深厚功底,成为 GoogleLeNet 架构设计者。另一个例子是 Oxford VGG 研究组了。 2012 年他们的 Fisher Vector 方法被 AlexNet 打败,然而 2014 年他们推倒之前的一切工作,从头开始从事卷积网络研究,并一举赢的当年 ImageNet 两个分项的冠军

以上是我简要的笔记。通过参加这次以及其他的一些 meetup,我总的感觉是 Google 等大鳄在深度学习方面的人才和资源积累远在其他公司之前,原因和当年大数据时代 Google 领先行业一样:Google 要解决的问题和拥有的数据远比其他小公司多。不过话说回来,这轮 AI 浪潮带来的新问题很多,许多是 Google 不愿意做或者不屑于做的。希望这一波的 AI 浪潮能够让深度学习技术更加民主化,更多的 AI 技术能够被整个行业采用。


广告

最后毫不要脸地插一个广告: 我的创业公司, AI.codes, 致力于将人工智能技术应用于分析和预测计算机代码,目前发布了一个 IntelliJ 插件试用版,仅支持 Java。同时,欢迎有一定人工智能或编译器知识基础的同学加盟。目前公司处于起步阶段,股权等各项待遇在硅谷创业公司中绝对属优。不在湾区但对这个项目感兴趣的朋友也可以直接和我联系,我的邮件地址是 exu@ai.codes.


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) ,会让这种情况重新出现。