程式員們的啟蒙老師,終於拿圖靈獎了
2021年04月02日08:24

原標題:程式員們的啟蒙老師,終於拿圖靈獎了

邊策 夢晨 子豪 發自 凹非寺

量子位 報導 | 公眾號 QbitAI

計算機領域的最高獎“圖靈獎”今年姍姍來遲。

美國計算機協會(ACM)公佈,獲得2020年圖靈獎殊榮的是哥倫比亞大學計算機科學名譽教授Alfred Aho與斯坦福大學計算機科學名譽教授Jeffrey Ullman。

根據官方公告,二位計算機科學家的獲獎理由是:表彰他們在編程語言實現的基礎算法和理論上做出的貢獻。他們還在其極富影響力的書籍中綜合了這些研究成果,這些著作教育了幾代計算機科學家。其中最負盛名的就是經典本科計算機教材“龍書”《編譯原理》。
圖靈獎通常被稱為“計算機界的諾貝爾獎”,獎金為100萬美元,由Google提供資金支援。

GoogleAI高級副總裁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)的導師,並曾在Google的技術顧問委員會任職。
△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

關注我們Facebook專頁
    相關新聞
      更多瀏覽