程序员们的启蒙老师，终于拿图灵奖了_风闻

边策 梦晨 子豪 发自 凹非寺 量子位 报道 | 公众号 QbitAI

计算机领域的最高奖“图灵奖”今年姗姗来迟。

美国计算机协会（ACM）公布，获得2020年图灵奖殊荣的是哥伦比亚大学计算机科学名誉教授Alfred Aho与斯坦福大学计算机科学名誉教授Jeffrey Ullman。

根据官方公告，二位计算机科学家的获奖理由是：表彰他们在编程语言实现的基础算法和理论上做出的贡献。

他们还在其极富影响力的书籍中综合了这些研究成果，这些著作教育了几代计算机科学家。其中最负盛名的就是经典本科计算机教材“龙书”《编译原理》。

图灵奖通常被称为“计算机界的诺贝尔奖”，奖金为100万美元，由谷歌提供资金支持。

谷歌AI高级副总裁Jeff Dean评价说：

Aho和Ullman建立了关于算法，形式语言，编译器和数据库的基础思想，这些思想对当今编程和软件领域的发展至关重要。

在计算机科学教育方面，他们的教科书已成为培训学生、研究人员和从业人员的黄金标准。

Aho和Ullman二人从1967年在贝尔实验室的合作开始，持续了几十年，为编程语言理论和实现以及算法设计和分析奠定了基础。

在加入贝尔实验室之前，Aho和Ullman都在普林斯顿大学获得了博士学位，他们从1967年到1969年在贝尔实验室一起工作。在贝尔实验室工作期间，他们的早期工作包括开发用于分析和翻译编程语言的高效算法。

1969年，Ullman开始了学术界的职业生涯，最终加入了斯坦福大学，而Aho在贝尔实验室工作了30年，之后才加入哥伦比亚大学。

尽管在不同的机构工作，Aho和Ullman仍保持了数十年的合作，在此期间，他们共同撰写了多部书籍和论文，并介绍了算法、编程语言、编译器和软件系统等新技术。

Alfred Aho

Aho于1941年出生于加拿大。本科就读于多伦多大学，在普林斯顿大学获得电气工程和计算机科学博士学位。

在贝尔实验室期间，Aho为Unix编写了egrep和fgrep工具，大大增强了正则表达式的功能和效率，并在各大Linux发行版中沿用至今。

Aho还与Peter Weinberger和Brian Kernighan合作开发了专门进行文本处理的脚本语言AWK。AWK的名字正是由三位开发者的姓氏首字母构成。

由Aho的正则表达式模式匹配算法衍生出的Lex & Yacc是当今许多编程语言编译器的基础。

Aho是美国国家工程学院、美国科学促进会、ACM与IEEE的会员，并于2003年获冯诺伊曼奖。

截至目前，他的论文总共被引用过8万5千多次，h指数为63。

Jeffrey Ullman

Jeffrey Ullman于1942年出生，于1963年从哥伦比亚大学毕业，获得工程数学理学学士学位，之后于1966年在普林斯顿大学获得电气工程博士学位。

此后他在贝尔实验室工作了数年，1969年到1979年成为普林斯顿大学教授，1979年后加入斯坦福大学。

1995年，他被选为ACM Fellow；2000年，他被授予高德纳奖；2010年，他被授予IEEE约翰·冯·诺依曼奖，获奖理由是“为自动机和语言理论领域奠定了基础，并为理论计算机科学做出了许多开创性的贡献”。

Ullman的研究领域包括数据库理论、数据集成、数据挖掘等，他还是是数据库理论领域的创始人之一，他教授的博士生在毕业后很多都成为领先的数据库理论家。

他还是Google的联合创始人之一谢尔盖·布林（Sergey Brin）的导师，并曾在谷歌的技术顾问委员会任职。

**△**Ullman和Brin在斯坦福，摄于2002年

除了与Aho合著经典的龙书外，他与1986年图灵奖得主John Hopcroft合著的《自动机理论、语言和计算导论》也是一本经典教材。

著作简介

Aho和Ullman在数十年的合作期间，将研究成果编成教材，共同撰写了九本极具影响力的书籍（包括第一版和后续版本）。

其中最著名的当属《计算机算法的设计和分析》（1974）和《编译器设计原理》（1977）。

**《计算机算法的设计和分析》**由Aho、Ullman和John Hopcroft合著，早在计算机科学刚兴起时，它就成为了全世界算法课程的标准教科书。

作为该领域的经典著作，是十多年来计算机科学研究中被引用最多的书籍之一。

除了将研究成果融入算法，书中还引入了随机存取机（RAM）作为基本模型，利用递推关系分析计算机算法的时空复杂度。

RAM模型将不同的单独算法，编码为通用设计方法，书中介绍的RAM模型和通用算法设计技术，现已成为标准计算机科学课程的一部分。

**《编译器设计原理》**被誉为编译原理三大经典之一，也是二人合著的最知名的计算机本科教材。

这本书还有一个更广为人知的名字——「龙书」，这一称呼是由其封面设计而来，从1977年的「绿龙书」升级到1986年的「红龙书」，再到2006年的「紫龙书」。

「绿龙书」封面上，骑士手拿长矛和标有“ LALR解析器生成器”、“语法制导翻译”的盾牌，骑着标有“数据流分析”的马。

书中探讨了编译器设计方面的若干重要课题，其中包括作者对词法分析、语法分析技术和代码生成的算法的研究成果。

将形式语言理论和语法制导翻译技术，集成到编译器设计过程中；清晰地阐述了将高级编程语言翻译成机器代码的各个阶段，将整个编译器建设事业模块化。

这本书的最新版本是《编译原理 技术和工具》（2006），也就是「紫龙书」，由Aho、Ullman、与Ravi Sethi和Monica Lam合著，至今仍是编译器设计的标准教科书。

△「红龙书」和「紫龙书」封面

对于「龙书」，无论是内容的全面性，还是理论与代码的结合，网友们都给出了高度评价。

“在看过大量资料后，回过来看这本书，发现其实这里都介绍了”

“既有深刻的理论，又有代码实现。”

不过，由于内容相对枯燥，尤其是「紫龙书」多达1009页，不少网友都感慨：想把它读完可太难了……

参考链接：

[1] https://amturing.acm.org/

[2]https://en.wikipedia.org/wiki/Alfred_Aho

[3] http://infolab.stanford.edu/~ullman/

[4]https://www.youtube.com/watch?v=rQtPndgbD-4