Aho和Ullman斩获2020年度图灵奖
2021-04-04 21:30:54 阿炯

2021年3月31日,国际计算机协会(ACM)正式宣布将2020年图灵奖授予哥伦比亚大学计算机科学名誉教授Alfred Vaino Aho和斯坦福大学计算机科学名誉教授Jeffrey David Ullman,以表彰他们在编程语言实现(programming language implementation)领域基础算法和理论方面的成就。


两位编程语言大佬


Alfred Vaino Aho是哥伦比亚大学的Lawrence Gussman荣誉教授。他于1995年加入哥伦比亚大学计算机科学系。在加入哥伦比亚大学之前,Aho曾在贝尔实验室担任计算科学研究副总裁,在该实验室工作了30多年。Aho毕业于多伦多大学,之后获得了普林斯顿大学电气工程/计算机科学的硕士学位和博士学位。

他是美国国家工程学院、美国艺术与科学学院和加拿大皇家学会的会员。他同时也是ACM、IEEE、贝尔实验室和美国科学发展协会的会员。

Aho荣获过数不胜数的荣誉,包括IEEE约翰•冯•诺依曼奖章和NEC C&C基金会C&C奖等等大奖。


Jeffrey David Ullman是斯坦福大学 W. Ascherman名誉教授,同时也是Gradiance Corporation的CEO,该公司是一个包含各种计算机科学主题的在线学习平台。

Ullman是ACM会员、美国国家工程学院、美国国家科学院和美国艺术与科学学院的会员。他获得过的荣誉包括EEE冯诺依曼奖章、NEC C&C基金会C&C奖,Donald E. Knuth奖和ACM Karl V. Karlstrom杰出教育家奖。

在这个世界上运行着的每个程序,从手机、汽车上的程序,到在大型Web公司内部的大型服务器中运行的程序,都是由人类使用高级编程语言编写、然后编译为较低级的代码交给机器汇编执行。这些编译技术很多都源于Aho和Ullman两人。

回顾 Aho 和 Ullman 的合作生涯,发现这二人的缘起始于人才辈出的贝尔实验室。进入贝尔实验室之前,Aho 和 Ullman 均在普林斯顿大学获得了博士学位,此后二人于 1967 年在贝尔实验室首次合作,早期工作主要是开发用于分析和翻译编程语言的高效算法。不过,这段共事并没有持续很久。1969 年 Ullman 离开了贝尔实验室,开始学术界的职业生涯并最终加入斯坦福大学,而 Aho 也在贝尔实验室工作了 30 多年后的 1995 年后加入了哥伦比亚大学计算机科学系。尽管二人在不同机构任职,但彼此均获得了卓越成就。此外,这数十年间,Aho 和 Ullman 的合作并未停止,他们将研究成果整理成文,共同撰写了许多书籍与论文,介绍有关算法、编程语言、编译器和软件系统的新兴技术。

Aho和Ullman共同撰写了九本有影响力的书(包括第一版和后续版本),他们最著名的两本书包括:

(1)《计算机算法设计与分析》(1974)


这本书由Aho、Ullman和John Hopcroft(1986年图灵奖得主)合著,被认为是该领域的经典著作,并且是十多年来计算机科学研究中被引用最多的书籍之一。

在计算机科学仍是一个新兴领域时,它已成为全世界算法课程的标准教科书。除了将自己的研究成果纳入算法之外,《计算机算法的设计和分析》还引入了随机存取机(RAM)作为使用递归关系分析计算机算法的时空复杂度的基本模型。RAM模型还将不同的单独算法编码为通用设计方法。

(2)《编译程序设计原理》(1977)


由Aho和Ullman共同撰写的这本有关编译器技术的权威书籍将形式语言理论和基于语法的翻译技术集成到了编译器设计过程中,由于其封面设计,通常被称为“龙书”。

这本书清晰地列出了将高级编程语言转换为机器代码,模块化整个编译器构造。书中囊括了作者对词法分析高效技术、语法分析技术和代码生成做出的算法贡献。


编译器:连接人类语言和计算机语言

1963年,当Alfred Aho和Jeffrey Ullman在普林斯顿大学研究生院开学的第一天在登记线等候时相遇时,计算机科学仍然是一个陌生的新世界。

使用计算机需要一组深奥的技能,通常只供受过训练的工程师和数学家使用。但是今天,部分归功于Aho和Ullman的工作,几乎任何人都可以使用计算机并对计算机进行编程以执行新任务。在这个世界上运行着的每个程序,从手机、汽车上的程序,到在大型Web公司内部的大型服务器中运行的程序,都是由人类使用高级编程语言编写、然后编译为较低级的代码交给机器汇编执行。


在计算机中,编译器是一种计算程序,它将以编程语言或计算机语言(源语言)编写的源代码转换为另一种计算机语言(目标语言,通常具有称为目标代码或机器代码的二进制形式)。转换源代码的最常见原因是创建可执行程序。用高级编程语言编写的任何程序都必须先编译成目标代码,然后才能执行,因此所有使用这种语言的程序员都必须使用编译器或解释器。因此,编译器对现代程序员来说至关重要、不可缺少。对编译器的改进可能会带来可执行程序中的大量功能改进。

早期计算机的软件主要是用汇编语言编写的。直到在不同类型的CPU上重用软件的收益变得足够大,人们才开始编写编译器,并发明了高级编程语言。对于程序员来说,使用高级编程语言通常通常会更有效率,并且用高级语言编写的程序可以在不同类型的计算机上重用。即便如此,编译器还是需要一段时间才能建立起来,因为它们生成的代码性能不如手写汇编语言,它们本身就使开发项目望而生畏。

早期计算机的内存容量非常有限,在实现编译器时也产生了许多技术问题。在1950年代末,人们首次提出了与机器无关的编程语言。随后,人们开发了几种实验编译器。第一个实现的编译器由Grace Hopper于1952年为A-0编程语言编写,然而该系统起着加载器或链接器的作用,而不是现代的编译器概念。现代意义上的第一个自动编码和编译器由Alick Glennie于1952年在曼彻斯特大学为Mark 1计算机开发。


编译器无可比拟的作用

编译器是将高级语言程序解释成为计算机所需的详细机器语言指令集的程序。


电脑不会说英语、普通话、德语、西班牙语或其他任何人类语言。尽管Siri和Alexa可能会出现,但是计算机和其他小工具都是他们自己的二进制语言(我们无法理解的语言)的母语。这意味着,如果要编程计算机,则必须说计算机的语言。一个编译器是一个翻译。它将命令转换为计算机可以理解的“ 1”和“ 0”。同一编译器甚至可以生成两种类型的翻译,以及两者之间的各种版本。

通俗来讲,编译器是一种特殊的程序,它可以把以特定编程语言写成的程序变为机器可以运行的机器码。我们把一个程序写好,这时我们利用的环境是文本编辑器。这时我程序把程序称为源程序。在此以后程序员可以运行相应的编译器,通过指定需要编译的文件的名称就可以把相应的源文件(通过一个复杂的过程)转化为机器码了。

一个现代编译器的主要工作流程:
源代码 (source code) → 预处理器 (preprocessor) → 编译器 (compiler) → 目标代码 (object code) → 链接器(Linker) → 可执行程序 (executables),最后打包好的文件就可以给电脑去判读运行了。

而对源代码的控制意味着商业控制。大多数公司都将其源代码保密,就像可口可乐保护其配方一样。他们,而且只有他们,才能将其程序从源代码编译为不同芯片所需的目标代码。这使公司可以控制程序的运行位置和运行方式。Microsoft保留了Windows 10的源代码控制权,这意味着只有Microsoft可以决定可以运行Windows 10的芯片类型(哪种微处理器ISA)。Apple可以控制MacOS的源代码,依此类推。你和我不能只在我们想要的任何计算机上运行Windows或MacOS,因为我们无法对其进行编译。


合作出版的书籍就有 9 本(包括第一版和后续版本):

1. The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing. (1972)

2. The Theory of Parsing, Translation, and Compiling, Vol. 2, Compiling. (1973)

3. The Design and Analysis of Computer Algorithms. (1974 )

4. Principles of Compiler Design.(1977)

5. Data Structures and Algorithms.(1983)

6. Compilers: Principles, Techniques, and Tools. (1986)

7. Foundations of Computer Science.(1992)

8. Foundations of Computer Science, C Edition. (1995)

9. Compilers: Principles, Techniques, and Tools, Second Edition. (2007)

其中最广为流传,也对计算机领域影响最深的是两本(上文亦有所提及):《计算机算法设计与分析(The Design and Analysis of Computer Algorithms)》(1974),以及绰号“龙书”的《编译程序设计原理(Principles of Compiler Design)》(1977)‍。

由 Aho,Ullman 和 John Hopcroft 合著的《计算机算法设计与分析》,被视为领域的经典著作,也是这些年来计算机科学研究中被引用最多的书籍之一。彼时计算机科学尚且还是一个新兴领域,《计算机算法设计与分析》这本书就成为了全世界算法课程的标准教科书。该书还引入了随机存取机(RAM)作为使用递归关系分析计算机算法的时空复杂度的基本模型,如今已成为标准计算机科学课程的组成部分。如果说《计算机算法设计与分析》为最初的算法领域引入标准,那么“龙书”就教会了我们如何控制计算机。

如今各种高级程序语言的简洁易懂,取代了最原始的机器语言的晦涩繁琐,其中编译器——将这些高级语言指令转换成处理器真正理解的机器代码,功不可没。而用于现代编程语言的大部分编译器技术,都源于 Aho 和 Ullman,“龙书”也正是二人将对此的研究成果汇成书籍,成为了编译领域无可替代的经典著作,启蒙了国内外数代开发者。Ullman 自己都说:“从许多方面来说,那些教科书,尤其是龙书,为计算机科学带来了很多新人。”

“龙书”不仅是国外许多著名高等院校和科研机构的标准教材,对中国计算及教育界也有重大影响,是许多大学计算机专业本科生和研究生编译原理与技术课程的教材,也成为了诸多计算机技术人员必读的专业书籍之一。这其中就包括 Swift 之父——Chris Lattner。身为编译器大神的 Chris,在硕博生涯靠着钻研“龙书”逐渐成为大牛。因此,后来在做 Clang 项目时,Chris 以影响他最大的“龙书”为灵感,为项目选定了“龙”的图标。


自 1977 年初版“龙书”在计算机领域影响颇深后,接下来的几十年中“龙书”也在不断升级:

1977 年,也就是第一版《计算机算法设计与分析》发行,由于封面是骑士与一只绿色的龙,因此被人称为“龙书”或“绿龙书”;

1986 年,Aho 和 Ullman ,再加上 Ravi Sethi,在原基础上进行升级,书名改为《Compilers: Principles, Techniques and Tools》,封面依旧是龙与骑士,但龙的颜色变为红色,因此这本书被称为“龙书二”或“红龙书”;

2006 年,在原基础上又增加了一位作者 Monica S. Lam,“龙书”再次升级,名字沿用《Compilers: Principles, Techniques and Tools》,但封面的龙变为紫色,这本书便被叫做“紫龙书”。

“紫龙书”的新增作者 Monica S. Lam 曾在 2015 年接受过 CSDN 的专访,或许与 Aho 和 Ullman 愿意将研究成果献给世人的初衷一样,她表示:“技术可以改变一切,而我所向往的世界就是人人都可以当创造者,生产者。”


在公布 Aho 和 Ullman 荣获 2020 图灵奖之后,许多业界知名人士予以庆贺与肯定。

谷歌 AI 大神 Jeff Dean 发推特祝贺:“我在研究生院上编译课的时候,用了'龙书'作为教材,这给成千上万的计算机科学家带来了美好的回忆。”

Jeff Dean 还表示:“Aho 和 Ullman 建立了关于算法、编译器和数据库的基本思想,这些思想对当今编程和软件领域的发展至关重要。”

哥伦比亚工程学院院长 Mary C. Boyce 说:“我代表哥伦比亚工程学院向 Aho 教授表示祝贺。图灵奖是计算机科学领域中最负盛名的奖项,Aho 在工业和学术界都有杰出的职业生涯,而图灵奖正确地表彰了 Aho 在编程语言方面的开创性贡献。”

斯坦福大学校长 Marc Tessier-Lavigne 也肯定道:“Aho 和 Ullman 为我们对基本算法以及编程语言设计和实现的理解做出了突破性贡献。他们的工作使现代计算机软件为我们的世界提供了动力,并且深刻影响了数代计算机程序员。”

Aho 和 Ullman 本人也对这次的获奖感到荣幸与开心。

“获得这一享有盛誉的奖项令我感到荣幸和谦卑。我很高兴 ACM 通过这个奖项肯定了在编程语言的设计和实现中抽象和算法的根本性和重要性。”Aho 说。Ullman 则幽默回应:“我能说什么?我可以快乐地死去了。获得图灵奖是我没想到的,我和 Aho 所做的贡献通常不会获得图灵奖,但能以这样的方式得到认可是一种莫大的荣誉。”


本文总结自互联网。