2020阿尔弗雷德-瓦诺-阿霍

shiyi18

阿尔弗雷德-瓦诺-阿霍
美国 - 2020
荣誉
因其在编程语言实现方面的基本算法和理论，以及在其极具影响力的著作中综合了这些成果和其他成果，培养了一代又一代的计算机科学家。

简短注释
参考文献
研究
主题
阿尔弗雷德-V-阿霍出生于安大略省北部的蒂明斯镇，但在多伦多长大。他的父亲是一名来自芬兰的移民木匠，母亲是一名秘书，来自亚利桑那州。父母都没有上过大学，但他们都非常重视阅读和音乐。阿霍从小就开始拉小提琴，曾在北多伦多学院的学校管弦乐队中表演，并终生坚持演奏[1]。

从 1959 年开始，阿霍在加拿大著名大学多伦多大学学习工程物理。这是一门要求特别高的课程，将工程学与严谨的数学和物理学结合在一起。他的第一次编程经历是在大学的 IBM 7094 主机上编写汇编语言。

1963 年，阿霍从多伦多大学毕业，进入普林斯顿大学攻读研究生。尽管普林斯顿大学有逻辑学家阿隆佐-丘奇（Alonzo Church）和博弈理论家奥斯卡-摩根斯特恩（Oskar Morgenstern）等教师，阿霍也曾向他们学习过课程，但几十年后普林斯顿大学才成立了计算机科学系。但在阿霍就读的电子工程系，有几位年轻教师正在建立计算机方面的教学和研究议程。其中约翰-霍普克罗夫特（John Hopcroft）本人就是未来的图灵奖获得者，他受邀教授该领域的一门课程。

阿霍记得，他和霍普克罗夫特第一次接触形式语言理论，是在他们的博士生杰弗里-乌尔曼（Jeffrey Ullman）在系统开发公司的西摩-金斯伯格（Seymour Ginsburg）研究小组度过了一个暑假之后。阿霍的博士论文是对新兴研究成果的贡献，该成果将形式语言理论的语法划分为一个层次，该层次由能够识别这些语法的自动机类别所定义。他的论文引入了索引语法这一新类别，它是对现有的无上下文语法概念的概括，并描述了一类新的自动机，他称之为能够识别这些语法的嵌套栈自动机[2]。

1967 年毕业后，阿霍加入贝尔实验室，成为其计算研究小组的成员。这在某种程度上是他在普林斯顿工作的自然延续：贝尔实验室的郊区园区离这里不远，乌尔曼最近刚受聘于贝尔实验室，霍普克罗夫特有时会利用暑假为贝尔实验室提供咨询。他加入的研究小组由道格-麦克罗伊（Doug McIlroy）领导，该小组在 20 世纪 70 年代开发出了后来的 Unix 操作系统和 C 编程语言。

与乌尔曼的合作

阿霍最为人熟知的是他与共同获奖人乌尔曼合作编写的教科书。两人在贝尔实验室做了三年的全职同事，但乌尔曼回到普林斯顿大学任教后，继续每周为贝尔工作一天。

他们对自动机理论与形式语言的交叉保持着浓厚的兴趣。在早期的一篇论文中，阿霍和乌尔曼展示了如何让克努特的 LR(k) 解析算法适用于技术上不符合 LR(k) 语法要求的简单语法。这项技术对阿霍和他在贝尔实验室的同事开发的 Unix 软件工具至关重要。这只是阿霍和乌尔曼对形式语言理论以及词法分析、语法分析、代码生成和代码优化的高效算法的众多贡献之一。他们开发了高效的数据流分析算法，利用了 "gotoless "程序的结构，这在当时刚刚成为一种规范。

他们早期在算法设计和分析技术方面的合作，为这一时期出现的计算机科学理论核心贡献了重要的方法。这些算法工作侧重于处理图、字符串和序列的基本方法，与他们对编程语言的研究紧密结合在一起。他们与约翰-霍普克罗夫特（John Hopcroft）合作的奠基之作《计算机算法的设计与分析》（The Design and Analysis of Computer Algorithms）于 1974 年出版，该书不仅为数十年来标准计算机科学课程中的算法教学，而且为展示和分析研究界开发的新算法创建了概念框架。除了纳入自己的成果，该书还将一系列不同的算法编入一套通用设计方法，包括分而治之、递归、动态编程和其他早已进入计算机科学家标准工具箱的方法。

阿霍和乌尔曼在 20 世纪 70 年代的另一个重要贡献是他们关于编程语言和编译器理论的著作。他们将自己对计算机语言的研究结集成两卷本的《解析、翻译和编译理论》丛书，于 1972-3 年出版。阿霍说，在这本书中，他们 "试图提炼自动机和语言理论的精髓，并将其应用于编译过程。我认为，这是将理论基础应用到计算机科学的一个重要实践领域的有趣示范之一"。这提供了 "一个可用于设计翻译过程算法的理论基础。更重要的是，人们可以构建工具，帮助构建编译器的组件"[3]。

这为他们于 1977 年出版的编译器技术权威教科书《编译器设计原理》奠定了基础。这本 "龙书"（因其彩色封面而得名）以及后来与拉维-塞西（Ravi Sethi）合著的版本，以及后来与塞西和莫妮卡-林（Monica Lam）合著的版本，成为了编译器设计领域的圣经。这些书清晰地列出了将高级编程语言转换为机器代码的各个阶段，将整个编译器构建过程模块化。

这对搭档还帮助正式确定了关系数据库的结构。关系数据库管理系统基于埃德加-科德（Edgar Codd）获得图灵奖的模型，其结构围绕着每条信息只应存储一次的理念。数据库查询指定了存储在不同表（或科德正式模型中的 "关系"）中的记录应如何重新组合。阿霍与乌尔曼和卡特里埃尔-贝里（Catriel Beeri）共同发表的关于 "无损连接 "的论文，为无冗余数据存储的 "正常形式 "研究带来了严谨性，并提供了一种方法来确定何时可以在不丢失信息的情况下将关系分解成更小的部分[4]。

对 Unix 的贡献

由于他在贝尔实验室的职位，阿霍得以将他和乌尔曼一直在写的关于编译器创建的许多想法付诸实践。Unix 操作系统最初是贝尔实验室两名程序员丹尼斯-里奇（Dennis Ritchie）和肯-汤普森（Ken Thompson）的一个草根项目，目的是复制在贝尔实验室退出创建 Multics 操作系统的麻烦项目后失去的交互式编辑和软件开发能力。官方为他们的新举措提供的支持并不多，但他们承诺，这将有助于实验室的出版和专利工作人员更有效地制作文件，而不是做出任何提供商业产品的宏伟承诺。这样，研究人员就可以根据自己的需要自由地进行系统开发，并测试软件开发的新方法。汤普森和里奇后来因开发 Unix 系统而分享了自己的图灵奖，Unix 系统是当今大多数广泛使用的操作系统的基础。

Unix 的主要特点之一就是人们常说的 "软件工具 "理念。它自然地源于 Unix 项目的特点：操作系统本身是由一个小团队开发的最小、高效和可移植的核心。Unix 项目组让个人和小组开发可重复使用的工具，每种工具都能高效地做好一件事，而不是让庞大的小组去开发复杂的程序来补充这个核心。为了完成某项任务，用户可以使用一种称为 "管道 "的独特机制，将这些程序的输入和输出串联起来。在 20 世纪 70 年代末和 80 年代，Unix 迅速成为学术和科学计算领域的主流平台，其魅力既来自于这些工具的集体力量，也来自于操作系统核心的强大功能。

阿霍在处理形式语言方面的深厚知识使他能够为这些工具中最重要的几个做出贡献。阿霍开发了一些算法，可以高效地查找与以正则表达式表示的简单规则相匹配的文本字符串。这些算法被集成到 Unix 工具 egrep 中，后来又被集成到词法分析器 lex 中，成为一系列工具的一部分，使编译器的开发变得更快、更容易。另一款名为 fgrep 的工具通过生成特殊用途的自动机，能够在一次通过输入时搜索多个关键字，从而以极快的速度搜索输入的关键字。这依赖于 Aho-Corasick 算法，该算法最初是由 Margaret J. Corasick 为一个书目项目发明的[5]。

Yacc 是 Yet Another Compiler 编译器的缩写，由 Steve Johnson 编写，用于实现 Aho 和 Ullman 研究的 LR(k) 解析技术。它根据待识别语言的语法描述自动生成解析器代码。阿霍回忆说，它的诞生是对使用人工技术为 C 语言开发解析器这一令人沮丧的经历的回应，而 C 语言是 Unix 项目的另一个产物："我有一块......很大的硬纸板，我通常在看电视的时候在上面进行项目集的构建，因为这是一项琐碎而又令人头疼的工作....。我把这块纸板交给史蒂夫-约翰逊（Steve Johnson），然后史蒂夫会把它编码到他的计算机程序中。过了一段时间，他开始对我感到沮丧，因为我无法做到百分之百的正确，于是他写了一个程序，将这种解析器构建技术自动化。就这样，Yacc 工具诞生了"[6]。

Unix AWK 工具以其创造者阿霍、（彼得）温伯格和（布莱恩）克尼根的名字命名，是一种基于阿霍处理正则表达式算法的专用编程语言。AWK 程序被定义为一组动作。程序按顺序读取输入内容，每当遇到与相应模式匹配的字符块时，就执行每条规则中定义的操作。阿霍的动机是制作一种语言，与其他 Unix 工具一起，可以快速创建非常简短的程序来处理文本文件中的数据。得益于 Unix 的灵活性及其管道机制，AWK 在处理和修改文本流方面找到了更多的用途。AWK 及其衍生工具至今仍在使用，不过近几十年来，Perl 已成为越来越受欢迎的替代工具。

哥伦比亚大学

1995 年，阿霍成为哥伦比亚大学计算机科学教授，并担任了两年的系主任。回忆起当时的决定，阿霍说："我当时在贝尔核公司管理着一个大约 200 人的组织。在学术界管理 25 个人会有多难？答案是难上加难。"[7] 他在哥伦比亚大学度过了职业生涯的余生，于 2018 年退休，但他仍与贝尔实验室保持联系，包括担任研究部高级经理的五年时间，为此他向哥伦比亚大学请了假。

在哥伦比亚大学，阿霍继续从事语言和编译器方面的工作，成立了该领域的研究小组，并教授一门很受欢迎的课程，要求学生设计、实现和记录自己的编程语言。他还致力于研究量子计算。他和乌尔曼还与新的合作者一起更新了编译方面的经典教科书，并编写了新的教科书《计算机科学基础》（1992 年），以理论和数学为基础介绍了计算机科学。

他给年轻人的建议是："数学永远学不完......无论你在哪个领域，都要学习基础知识，因为基础知识不会过时得太快......"。毕业后，尽量找一份与该领域最优秀的人共事的工作，因为你能从这些人身上学到很多东西，这样你就能为下一份工作做好准备"[8]。

作者：托马斯-海与 ACM 工作人员


[1] 本段以及简介其他部分的详细履历摘自 Hansen Hsu 与 ACM 合作于 2022 年 6 月 13 日为计算机历史博物馆对阿霍进行的口述历史访谈。

[2] AV Aho，《索引语法--无上下文语法的扩展》，《ACM 杂志》15 (4)，647-671。

[3] 迈克尔-S-马霍尼口述历史访谈，约 1989 年。https://www.princeton.edu/~hos/mike/transcripts/aho.htm

[4] Alfred V. Aho、Catriel Beeri、Jeffrey D. Ullman：关系数据库中的连接理论。ACM Trans.Database Syst.4(3):297-314 (1979).

[5] A.V. Aho & M.J. Corasick (June 1975)."Efficient string matching: An aid to bibliographic search".ACM 通信。18 (6):333-340.

[6] Michael S. Mahoney 的口述历史访谈，约 1989 年。https://www.princeton.edu/~hos/mike/transcripts/aho.htm

[7] Hansen Hsu 口述历史访谈，2022 年 6 月 13 日。

[8] Hansen Hsu 的口述历史访谈，2022 年 6 月 13 日。