程序員們的啓蒙老師，終於拿圖靈獎了_風聞

邊策 夢晨 子豪 發自 凹非寺 量子位 報道 | 公眾號 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