程序员们的启蒙老师,终于拿图灵奖了
边策 梦晨 子豪 发自 凹非寺
量子位 报道 | 公众号 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
— 完 —
本文系网易新闻•网易号特色内容激励计划签约账号【量子位】内容,未经账号授权,禁止随意转载。
原标题:《程序员们的启蒙老师,终于拿图灵奖了》
阅读原文
- 标签:赵丽颖机场照
- 编辑:杨保录
- 相关文章
-
男子20年收藏万余件红色文献:想筹建史料馆传承下去
陕西西安。姜小平20年收藏各类红色文献万余件,含建党初期的《新青年》,名人的入党申请等。他说…
-
车主投诉B180奔驰天冷就无法发动,4S店:在技术上无法避免
6月9日,半岛网记者接到潍坊市民刘先生反映,称他在潍坊高新区北海路高架桥南侧路东星吉奔驰4S店购…
- 小宝宝尾随爸爸爬梯子,踩空瞬间爸爸一把抓住
- 年轻人的第一只机器狗,只要1.6万
- 来自火星的旅拍:祝融号传图回家,我国火星探测圆满成功
- 广州越秀:10日对11条街道开展新一轮全员核酸检测
- 国际观察:拜登来了,“很受伤”的欧洲会全盘买账吗?