2020年图灵奖获得者阿尔弗雷德·瓦伊诺·阿霍（Alfred V. Aho）报道

Alfred V. Aho 出生于安大略省北部的蒂明斯镇，但在多伦多长大。他的父亲是来自芬兰的移民木匠，他的母亲是一名秘书，来自亚利桑那州。父母都没有上过大学，但他们重视阅读和音乐。Aho 从小就开始拉小提琴，与北多伦多学院的学校管弦乐队一起演奏，并在他的一生中一直继续演奏。

从 1959 年开始，Aho 在加拿大顶尖大学多伦多大学学习工程物理学。这是一门要求特别高的课程，将工程与严格的数学和物理相结合。他的第一次编程经验是在大学的 IBM 7094 大型机上编写汇编语言。

1963 年，Aho 从多伦多毕业，并进入普林斯顿大学攻读研究生。几十年后，普林斯顿才有了计算机科学系，尽管有逻辑学家 Alonzo Church 和博弈论家 Oskar Morgenstern 等教师，Aho 都曾从他们那里学习课程。但是，Aho 就读的电气工程系的几位年轻教职员工正在制定计算机方面的教学和研究议程。其中包括约翰·霍普克罗夫特 （John Hopcroft），他本人也是未来的图灵奖得主，他被要求教授该地区的一门课程。

Aho 记得，他和 Hopcroft 第一次接触到形式语言理论，这成为他们的主要研究领域，是在博士生 Jeffrey Ullman 与系统开发公司的 Seymour Ginsburg 研究小组度过了一个夏天之后。Aho 的博士论文是对新兴工作的贡献，该工作将形式语言理论的语法分类为由能够识别它们的自动机类定义的层次结构。他的论文引入了索引语法的新类别，这是对现有上下文无关语法概念的推广，并描述了一类他称之为嵌套堆栈自动机的新型自动机，它们能够识别它们。

1967 年毕业后，Aho 加入了贝尔实验室，成为其计算研究小组的成员。在某种程度上，这是他在普林斯顿工作的自然延续：郊区的贝尔实验室校园不远，乌尔曼最近在那里被聘用，霍普克罗夫特有时会在暑假为贝尔实验室提供咨询。他加入的小组由 Doug McIlroy 领导，主要因其在 1970 年代发展成为 Unix作系统和 C 编程语言的发展而被人们记住。

与 Ullman 合作

Aho 最出名的是他与他的共同获奖者 Ullman 一起编写的教科书。两人在贝尔实验室工作了三年的全职同事，但在回到普林斯顿大学担任教员后，Ullman 继续每周为贝尔工作一天。

他们对自动机理论与形式语言的交叉点保持着兴趣。在一篇早期的论文中，Aho 和 Ullman 展示了如何使 Knuth 的 LR（k） 解析算法与技术上不满足 LR（k） 语法要求的简单语法一起工作。这项技术对于 Aho 和他在贝尔实验室的同事开发的 Unix 软件工具至关重要。这只是 Aho 和 Ullman 对形式语言理论和发明用于词汇分析、语法分析、代码生成和代码优化的高效算法的众多贡献之一。他们开发了用于数据流分析的高效算法，该算法利用了“gotoless”程序的结构，这在当时刚刚成为常态。

他们在算法设计和分析技术方面的早期联合工作为这一时期出现的计算机科学理论核心提供了关键方法。由于专注于处理图形、字符串和序列的基本方法，这项算法工作与他们对编程语言的研究紧密结合。他们与 John Hopcroft 合作的奠基性著作《计算机算法的设计与分析》于 1974 年出版，该书不仅为几十年来在标准计算机科学课程中教授算法创造了概念框架，还为展示和分析研究界开发的新算法创造了概念框架。除了整合自己的结果外，这本书还将一系列不同的算法编纂成一组通用设计方法，包括分而治之、递归、动态编程和其他早已进入计算机科学家标准工具箱的方法。

Aho 和 Ullman 在 1970 年代的另一个重要贡献来自他们关于编程语言和编译器理论的书籍。他们将对计算机语言的研究收集成一个两卷本的系列文章《解析、翻译和编译理论》，于 1972 年 3 月出版。Aho 说，在这本书中，他们“试图提炼自动机和语言理论的精髓，并将其应用于编译过程。而且，我认为这是将理论基础置于计算机科学的一个重要实践领域的有趣示范之一。这提供了“可用于设计翻译过程算法的理论基础。而且，更重要的是，人们可以构建工具来帮助构建编译器的组件。

这为他们于 1977 年出版的编译器技术权威教科书 Principles of Compiler Design 奠定了基础。这本“龙之书”（以其彩色封面而得名）及其随后由 Ravi Sethi 以及后来由 Sethi 和 Monica Lam 合作的版本成为编译器设计的圣经。这些书清楚地列出了将高级编程语言转换为机器代码的各个阶段，从而将整个编译器构建企业模块化。

这对搭档还帮助正式确定了关系数据库的结构。关系数据库管理系统基于 Edgar Codd 获得图灵奖的模型，其结构是围绕每条信息只应存储一次的理念构建的。数据库查询指定应如何重新组合存储在不同表中的记录（或 Codd 的正式模型中的“关系”）。Aho 与 Ullman 和 Catriel Beeri 一起发表的关于“无损连接”的论文为无冗余数据存储的“范式”研究带来了严谨性，并提供了一种确定何时可以在不丢失信息的情况下将关系分解为更小组件的方法。

对 Unix 的贡献

多亏了他在贝尔实验室的职位，Aho 能够将他和 Ullman 一直在撰写的有关编译器创建的许多想法付诸实践。Unix作系统最初是贝尔实验室的两位程序员 Dennis Ritchie 和 Ken Thompson 的一个草根项目，旨在复制当实验室退出创建 Multics作系统的困境项目时，他们失去的交互式编辑和软件开发能力。分配给他们的新计划的官方支持适度，是合理的，因为它承诺这将帮助实验室的出版和专利工作人员更有效地制作文档，而不是任何交付商业产品的宏伟承诺。这使得研究人员可以自由地塑造系统的开发以满足自己的需求，并测试新的软件开发方法。Thompson 和 Ritchie 后来分享了他们自己的图灵奖，以表彰他们在 Unix 方面的工作，Unix 是当今大多数广泛使用的作系统的基础。

Unix 的关键特征之一是通常被称为 “软件工具” 的理念。它自然而然地源于 Unix 项目的特点：作系统本身是一个由小团队开发的最小、高效、可移植的核心。Unix 小组没有组建大型团队来构建复杂的程序来补充这一核心，而是让个人和小组开发可重用的工具，每个人都能出色有效地完成一件事。为了完成特定任务，用户将使用一种称为“管道”的独特机制将这些程序的输入和输出链接在一起。Unix 在 1970 年代末和 1980 年代迅速成为学术和科学计算的主导平台，它的吸引力来自这些工具的集体力量和作系统核心的稳健性。

Aho 对形式语言处理的深入了解使他能够为这些工具中几个最重要的工具做出贡献。Aho 开发了算法来有效地定位与简单规则匹配的文本字符串，以正则表达式表示。这些算法被合并到 Unix 工具 egrep 中，后来被合并到词法分析器 lex 中，这是一组工具的一部分，这些工具使编译器的开发变得更快、更容易。另一个工具 fgrep 通过生成专用自动机来快速搜索输入中的关键字，该自动机能够在一次输入中搜索多个关键字。这依赖于 Aho-Corasick 算法，该算法以其在 Margaret J. Corasick 运营的书目项目中的原始发明而得名。

Yacc 代表 Yet Another Compiler 编译器，由 Steve Johnson 编程，用于实现 Aho 和 Ullman 研究的 LR（k） 解析技术。它根据要识别的语言的语法描述自动生成解析器代码。

Aho 回忆说，它的创建是为了应对使用手动技术为 C 语言开发解析器的挫败经历，这是 Unix 项目的另一个产品：“我有一个......我通常在看电视的时候，在上面进行成套物品的构建，因为这是一项如此微不足道且令人麻木的任务......我把这块纸板交给了 Steve [Johnson]，然后 Steve 会把它编码到他的计算机程序中。过了一段时间，他对我感到非常沮丧，以至于我无法百分之百正确地理解它，他编写了一个程序来自动化这种解析器构造技术。这就是 Yacc 工具的诞生方式。

Unix AWK 工具以其创建者 Aho、（Peter） Weinberger 和 （Brian） Kernighan 的名字命名，是一种基于 Aho 算法的专用编程语言，用于处理正则表达式。AWK 程序被定义为作集。程序按顺序读取其 Importing，每当遇到与相应模式匹配的字符块时，执行每个规则中定义的作。

Aho 的动机是产生一种语言，与其他 Unix 工具一起，允许快速创建非常短的程序来处理文本文件中包含的数据。由于 Unix 的灵活性及其管道机制，AWK 在处理和修改文本流方面发现了更多用途。AWK 及其衍生物今天仍在使用，尽管近几十年来 Perl 已成为越来越受欢迎的替代方案。

哥伦比亚大学

1995 年，Aho 成为哥伦比亚大学的计算机科学教授，开始担任了两年的系主任。回忆起那个决定，Aho 说：“我在 Bellcore 管理着一个大约有 200 人的组织。在学术界管理 25 个人有多难？而答案要困难得多。他在哥伦比亚度过了余下的职业生涯，于 2018 年退休，尽管他保留了与贝尔实验室的联系，包括担任高级研究经理五年，为此他从哥伦比亚大学请假。

在哥伦比亚大学，Aho 继续研究语言和编译器，在该领域建立了一个研究小组，并教授一门受欢迎的课程，要求学生设计、实现和记录自己的编程语言。他还从事量子计算方面的工作。除了与新的合著者一起更新他们的经典编译教科书外，他和 Ullman 还编写了一本新教科书 Foundations of Computer Science （1992），该书介绍了基于理论和数学的计算机科学。

他对年轻人的建议是“你永远不能学太多数学......学习您所在的任何领域的基础知识，因为基础知识不会很快过时......当你毕业时，尝试找到一份与该领域最优秀的人一起工作的工作，因为你从这些人那里学到了很多东西，然后你就会为下一份工作做好充分准备。