Feb 4, 2020 - 我的量化哲学和策略

Comments

缘起

博客的老读者一看标题就会说,这是一篇和我博客文章风格迥异的文章。这篇的确是我所作。这是两年多的思考积累,写出来和大家分享。为了把我的思考轨迹讲清楚,先说一下我这几年的成长轨迹作为文章的起缘。

上次写文章还是 2017 年从事 AI 方向创业的时候写的——一晃三年了。上次的创业公司不算很成功,最后把 IP (知识产权) 卖给了一家公司。之后我在 Reddit 担任了两年的机器学习工程总监 (Director of Engineering)。从头建立了 Reddit 的机器学习研发团队,把 Reddit 的整个 Feed 系统算法化,个人化。帮公司在用户平均在线时间,广告投放点击率上实现了大于 50% 的质的飞跃。

这几年在人工智能领域的工作和创业,使我对整个深度学习的方向有了深刻的认识。我认为, GPU 上运行的深度学习框架是一个通用的计算平台,作用不仅限于机器学习。于是,业余时间,我开始尝试用 TensorFlow 这样的深度学习框架去解决一些非机器学习领域的问题。其中的一个领域,就是量化金融。

另一方面,三年里,我在职业和家庭人生这些方面都感到很满足很幸福。我有一个美好的家庭和一对健康成长的儿女。然而,这几年中,熟悉的朋友一个接一个肉身翻墙,国内发生的烦心事情越来越多。我还有父母和兄弟在国内,有时候不想关心国内信息也不可能。有天我在推特上说,“山河破碎,豺狼当道;麦秀粟离,沉郁悲呛”。一方面幸福平和,一方面沉郁悲呛,这样的心境于人于己都不健康。

某天我突然想到古人的 “国家不幸诗家幸,赋到沧桑句便工”,突然想通了。当年遗山老人没有高级金融工具,只能悲愤而做岐阳三首,成为一代诗家。如今我们所在的时代给予了我们许多表达和应对“沉郁悲呛”的方法。我的策略是用当今的数学物理和金融工具,以求“量化沧桑尽微力”。这样微弱的改变,总比躲进小楼成一统好一些。是为缘起。

大变局时代

这是一个大变局的时代。技术本身更快地创造和摧毁资本价值。熊彼得提出的创造性破坏每天都在加速。 30 年前,S&P 500 公司在榜单里待的时间平均是 33 年(出入榜很好地反映了价值和财富的创造和破坏),如今已经减少到 24 年,到 2027 年预测会继续减少到 12 年。 这方面例子比比皆是。如 Charles Schwab ,30 年前首先开创低价股票交易模式,破坏了当时的高价股票交易代理商,如今面对 Robinhood 这种免费交易对手的创造性破坏,也被迫推出免费股票交易。当年的创造性破坏者如今被新一代的公司创造性破坏。

我相信技术是经济增长的内生动力。技术的进步是非连续的,这意味着对财富的创造和破坏也是非连续的。刚刚过世的哈佛管理学教授 Clayton Christensen「创新者困境」 里描述了这种非连续性:行业领先的公司似乎忽然之间就被小公司超越。上面我们说到 S&P 500 榜单公司的平均寿命越来越短,其实是技术的破坏创造力越来越大的体验。

大变局也意味着大泡沫,一些公司看上去代表了新经济新技术,实际上内里全是泡沫,只是故事讲得好。所幸的是,物理学已经给我们指点了一套识别泡沫的方法。

大变局时代的物理金融方法

几十年前,我们还可以把技术当成外部变量来处理量化模型。随着技术对财富的加速创造和破坏,我们很难将技术排除在模型之外还能准确地计算资产价格。把技术纳入财富的创造和破坏模型,即抛弃传统的微观和宏观经济学的框架,拥抱复杂系统科学(物理学),拥抱非遍历经济学,拥抱内生经济模型。

用复杂系统(相变)的眼光来看金融市场——随着整个市场的自动化程度越来越高,相变也越来越频繁。这样频繁的相变意味着两点:

  • 第一,我们需要用复杂系统的数学物理方法来量化金融市场,而不是传统的随机游走理论。如「黑天鹅」的作者 Nassim Nicholas Taleb,一直在强调不要用随机游走的方法来量化市场。

  • 第二,传统的价值投资(以巴菲特为代表)可投资的领域在变小。巴菲特的投资哲学着力寻找那些高质量,未来一二十年有稳定增长的公司。但随着破坏性创造越来越频繁,这些股票越来越难找。事实也是如此,Berkshire Hathaway 如今手握大笔现金(总计 1280 亿美元),近四年来都没有出手任何大的投资标的,而是回购自己的股票支撑价值。

总的来说,新的内生经济增长方式决定了判断金融资产价值的方式要超越简单的未来现金流折现,因为未来现金流折现蕴含着连续性假设,而如今的未来是一个不连续的方程,尤其是在技术变革,动力转换和泡沫成长破碎的时候。这些非连续的事件正是可以让收益超过市场平均的机遇。

模型的业绩

通过去年一年的实际操作,结合上面说的物理方法,我认为我找到了一套行之有效的量化哲学和策略。我把这个方法很粗暴地命名为 “大跃进” / Great LEAPS。我自己管理的对冲基金也就暂且叫做大跃进基金。 命名后面的逻辑后面我再解释。

在阐述具体方法之前我讲一下我去年的成果。去年一年我总资产的年化收益约为 45%。 今年第一个月收益接近 14%。 所有收益均采用量化模型,而非基本面分析,技术分析等等。交易则由我手动执行。因为不是高频交易,手动执行和自动执行差别不大。

去年我最大部分收益来自于做空 NIO (蔚来汽车)。模型从它的股价大跃进里发现泡沫。我于 2019 年 1 月 19 日购买 N 手 2019 年 8 月 16 日到期的 PUT 期权,行权价格为 $14,购买价格为 $7.80/share。 至 2019 年 8 月 16 日,NIO 股价跌至 $2.96, 我以 $11.04/share 卖出,收益率为 146%。 其他操作收益不等,不占主要。

今年(2020年)第一个月我最大的收益来自 LK (瑞幸咖啡)。同样使用量化模型找到泡沫。我于 2020 年 1 月 10 日购买 N 手 2021 年 1 月 15 日到期的 PUT 期权,行权价格为 $35.00。购买价格为 $9.00。至今 LK 股价已跌落至 $31.36,而该期权价格升至 $13.40,如果今日卖出收益率为 148%。事实上,我基于基本面判断 LK 的真实股价为 $0。但这和模型无关,我在等待模型给出的另一个下跌窗口出手。

以上两例,尽管都和中概有关,但模型本身没有特别的给中概股权重。做空泡沫需要一定的勇气和耐心。比如做空蔚来的时候,著名做空机构香橼发布了一份做多的报告,我的总基金纸面上的损失达到了60%。但模型的威力是明显的,蔚来之后股价一路下跌。

随着中国经济的失速,这样的机会还有很多。在中国,增速的技术遇到了制度和人口结构变化,呈现出了独特的破坏式创造的风格。许多人主张做空中国(人民币,ETF,或者一些夕阳产业)。我的信念是这种笼统做空方式收益风险比过低。做空中国本身已经是一个有效市场,况且体制本身的行为很难在量化模型中刻画出来。

用深度学习的牛刀来屠量化金融的龙

上面我提到,大变局伴随的是物理的相变过程。然而,从短期趋势来说,发生的时间不可预测,也不可计算。这几天,许多做空 Tesla 的人都被其股价上扬震惊了。事实上,短期市场永远是一个难以预测的怪兽。短期要切准时间太难了。

然而,从中长期来看,我们有较好的预测相变的办法。比如, LPPLS 模型可以预测泡沫的破碎。然而,现有的模型优化手段非常粗糙(遗传算法),很难稳定收敛到一个可信的值。在这方面,华尔街和物理学家还没能普及更好的模型优化算法。其实更好的模型优化算法已经出现,即现有的深度学习框架。这里,并不是要用深度学习/神经网络本身来做量化金融,而是用深度学习领域的技术工具。这是一个非常独特的机遇,因为:

一方面传统的华尔街/量化公司已有一套完善的量化工具,但这些工具的模型表达和优化能力远不及 TensorFlow。另一方面,懂得 TensorFlow 这些工具的人目前都忙于做人工智能,还很少有人来捕捉量化金融的机会。TensorFlow 框架在量化金融上可以做许多事情。我觉得以后量化金融会逐步转移到这种全面的计算框架上来。我不怕写出来和大家分享这个“秘密”,因为目前能够把两者都玩转起来的能太少,我宁愿这样的人多一些才好。 同时,我认为未来几年,这个“秘密”武器有一定的先发优势,可以在一些模型上比它人获得更加好的结果和汇报。

对我来说,TensorFlow 和 GPU 可以用来预测和捕捉复杂系统的相变时刻。这样的预测必然是一种近似,而非科学预测。所以,问题是,有了相变(比如泡沫大概什么时候破碎)的信息,如何从金融市场中套利?知道信息本身只是10%的工作,用正确的工具来套利是 90% 的工作。

通过这一年的实践我找到了一个适合的金融工具,这个工具的名字叫 LEAPS,即长期期权。而在实践中,这是一个它山之石,长权短用,寻求高额回报。

LEAPS 工具

LEAPS 是一种特殊的期权,这种期权的过期日期往往在一年开外。因为美式期权的特点,意味着你有很长的时间来等待收益。当然,世界上没有便宜的午餐,长时间意味着更高的期权价格,也意味着小的 Theta 值。

做空并不是一件复杂的事情。然而,价格下行或许能立即发生,或许还要等几个月,或许半年内都不会发生。这正是许多做短期看空期权的人需要冒的风险,也是许多人倾家荡产的原因。在我看来,用短期期权去赌股价的上下,除非有额外的信息,否则真的是赌博。

在随机游走的假设下,LEAPS 本身也是公平的赌博。然而,当 LEAPS 和物理金融方法以及 TensorFlow 模型结合在一起,LEAPS 就有了一个新的维度: 用随机游走的量化模型计算出的期权价格 (现有的 LEAPS 定价策略),与用物理方法计算出的模型相比,在相变前期,后者能更加准确地刻画相变,更加符合金融市场的实际情况。方法本身没有好坏,差别在假设上。我相信,能够导出股价变化遵循 Power Law 分布的物理量化模型,比不能够导出 Power Law 的模型更加准确地捕捉相变。

一般专业交易者把 LEAPS 当成长期风险对冲工具。我的用法可以算是“直板横打”。我将 LEAPS 当成低风险的短期收益工具。以看空期权为例,在股价不变前提下,通过不断计算 LEAPS 的剩余价值,我可以控制时间流逝带来的折损。如果泡沫不破碎,则在其时间价值迅速贬值之前出售。如果等到泡沫破碎,则出售换取超额收益。当然,如果股价上涨,看空期权必然下跌,所幸的是,因为没有要紧的时间压力,你有选择等待的空间。

在这种策略下,收益不是从每日交易中得到,而是在等待中出现。这里的秘密是: Theta 函数随时间的变化是非线性的。在股价不变的前提下,LEAPS 前期的贬值极低,刨去市场无风险收益率,在前六个月几乎可以算是免费持有。

这里细节上还有一些有意思的东西,比如,依赖于 Hamiltonian Monte Carlo 方法,我们可以用 MCMC 和一套新的假设给 LEAPS 期权定价。一些原本不能做到的套利行为也可以在 TensorFlow + GPU 的帮助下完成。

结语

说到这里,我把这套对冲策略和基金命名为 Great LEAPS/大跃进 也就明白了。我的策略就是用量化的方法寻找那些看上去好像股价大跃进,其实内里土法炼钢的股票。找到后,用 LEAPS 策略套利。这套工具链和逻辑链能够成立,依赖于时代的机遇和泡沫,依赖于众多物理学家,数学家和机器学习工程师所构建的基础。

限于篇幅许多理论和实践没有一一展开。我一直相信,如果勤于思考的话,钱会来敲门。基于此,我宁愿写出来和人分享我的思考,希望更多的人知道模型和量化的力量。

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 4, 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 里都以通道方式构建。我们还可以举出许多同样的例子。这些风格的差异往往和语言的历史,演化路径,和要解决的问题相关,我们不必苛求他们的协程模型一定要如此这般。

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