1963年,当阿尔弗雷德·艾侯(Alfred Aho)和杰弗里·乌尔曼(Jeffrey Ullman)在普林斯顿大学研究生院开学第一天一同登记排队的时候,计算机科学仍然是一个陌生的新世界。
如今因为这两位学者的努力,几乎任何人都可以使用计算机并对计算机进行编程以执行新任务。
北京时间3月31日,ACM宣布将2020年图灵奖授予 Alfred Vaino Aho 和 Jeffrey David Ullman 二人,两位友谊持续半个世纪的学者将分享百万美元的奖金。
Aho是哥伦比亚大学计算机科学系名誉教授,Ullman是斯坦福大学计算机科学系的Stanford W. Ascherman教授。
据ACM官方公告, Alfred Vaino Aho和Jeffrey David Ullman的获奖理由为「创造了全球数百万编程人员使用的工具和教材」,奖项旨在表彰二人「推进编程语言实现的基础算法和理论,并在极具影响力的书籍中综述了这些研究成果。」
计算机软件是现代社会人类与科技互动的驱动器,每一个程序都运行在现实世界里——不论是在手机、汽车,还是网络公司内部的大型服务器。世界上的每一个程序都是人类使用高级语言编写,之后再编译成低级语言让计算机运行。这种将高级语言编译成计算机能够识别的低级语言的技术,在很大程度上要归因于 Aho 和Ullman。
从1967年在贝尔实验室共事开始,二人的合作持续几十年至今。Aho和Ullman奠定了编程语言的理论及实现和算法设计与分析的基础。二人通过技术贡献和极具影响力的教科书,在编程语言编译器领域做出了广泛深远的贡献;在算法设计和分析技术方面的早期合作,也为这一时期出现的计算机科学理论核心做出了重要贡献。
图灵奖是ACM于 1966 年设立的奖项,专门奖励对计算机事业作出重要贡献的个人,有「计算机界诺贝尔奖」之称,奖金为 100 万美元,由谷歌赞助。图灵奖的名称取自英国数学家艾伦·图灵(Alan M. Turing),他奠定了计算机的数学基础,也阐述了其局限性。
ACM主席Gabriele Kotsis说:「计算机编程的实践和日益发展的软件系统为过去五十年来大部分的技术进步奠定了基础。无数研究者和从业者为这些技术做出了贡献,其中Aho和Ullman的研究工作尤为重要,影响深远。他们帮助我们了解了算法的理论基础,并规划了编译器和编程语言设计方面的研究和实践课程。自20世纪70年代初以来,Aho和Ullman就一直是这一领域的思想领袖。到今天为止,他们的工作已经指导了几代开发者和研究人员。」
「Aho 和Ullman建立了关于算法、形式语言、编译器和数据库的基本思想,这对当今编程和软件领域的发展至关重要,」谷歌AI高级研究员和高级副总裁Jeff Dean补充道,「他们还阐明了这些学科之间的紧密联系。Aho 和Ullman引入了关键的技术概念,包括已经成为核心算法的具体算法。就计算机科学教育而言,他们的教材一直是培训学生、研究人员和从业者的黄金标准。」
横跨几十年的合作
在加入贝尔实验室之前,Aho和Ullman都在普林斯顿大学拿到了博士学位。1967年到1969年间,两人在贝尔实验室共事,开发了分析、编译编程语言的高效算法。
1969年,Ullman投身学术研究,在斯坦福大学拿到了教职;而Aho则在加入哥伦比亚大学之前在贝尔实验室工作了30年。尽管不在一个地方工作,两人的合作在几十年间并没有间断。在此期间,他们合著了不少论文、教科书,还引入了算法、编程语言、编译器、软件系统方面的新技术。
顺带一提,Jeffrey Ullman是谷歌联合创始人谢尔盖·布林的PhD导师。
那些影响深远的教材
Aho和Ullman两人共合著了9本影响深远的教材(包括初版和更新版本),其中最受欢迎的是《计算机算法的设计与分析》(1974)和《编译器设计原则》(1977)。
如果有人问「大家在计算机学习路上,都看过哪些神一般的书?」,大部分人的回答中肯定包含这两本。
《计算机算法的设计与分析》(1974)
本书由Aho、Ullman和1986年图灵奖得主John Hopcroft合著,被誉为该领域的经典著作,并且是十多年来计算机科学研究中被引用数量最多的书籍之一。当计算机科学还是一个新兴领域时,这本书就成为了全世界算法课程的标准教材。
在本书中,除了阐述他们对算法的研究贡献外,还介绍了如何将随机存储器(RAM)作为基本模型来分析递归关系算法的时间和空间复杂度。RAM模型还将独立的算法编成通用设计方法。书中介绍的RAM模型和通用算法设计构成了当今标准计算机科学课程的重要组成部分。
《编译器设计原则》(1977)
《编译器设计原则》由Aho和Ullman共同撰写,是一关于编译器技术的权威书籍,将形式语言理论和基于语法的编译技术集成到了编译器设计过程中。因为封面图片,这本书也通常被称为「龙书」,它清晰地列出了将高级编程语言转换为机器代码,模块化整个编译器构造的阶段。
这本书包含了作者对有效的词法分析技术、语法分析技术和代码生成技术所做的算法贡献。本书的最新版本《编译器:原理,技术和工具》(与Ravi Sethi和Monica Lam合著)于2007年出版,至今仍是有关编译器设计的标准教科书。
参考链接:https://amturing.acm.org/
https://www.nytimes.com/2021/03/31/technology/turing-award-aho-ullman.html