羅伯特·弗洛伊德 - 基本信息

羅伯特·弗洛伊德 Robert W Floyd

逝世  2001 年9月25日 （65歲）

研究領(lǐng)域  計算機科學

著名成就  弗洛伊德算法

研究機構(gòu)  卡內(nèi)基梅隆大學  斯坦福大學

獲獎  圖靈獎

羅伯特·弗洛伊德 - 概述

羅伯特·弗洛伊德（Robert W．Floyd；1936－），計算機科學家，圖靈獎得主，前后斷言法的創(chuàng)始人。

歷屆圖靈獎得主基本上都有高學歷、高學位，絕大多數(shù)有博士頭銜。這是可以理解的，因為創(chuàng)新型人才需要有很好的文化素養(yǎng)，豐富的知識底蘊，因而必須接受良好的教育。但事情總有例外，1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德就是一位“自學成才的計算機科學家”(a Self-Taught Computer Scientist)。

羅伯特·弗洛伊德 - 生平

弗洛伊德出生在美國紐約，14歲即完成高中學業(yè)，當他1953年從芝加哥大學獲得文學學士學位時，年僅17歲，并于1958年在物理學獲得了第二個學士學位。

他在1960年代早期成為計算機操作員，并發(fā)表了許多出名的論文，并當他27歲時，被任命為卡內(nèi)基梅隆大學的副教授，并于6年后成為斯坦福大學的正教授。此時他并沒有博士學位。

羅伯特·弗洛伊德 - 經(jīng)歷

弗洛伊德1936年6月8日生于紐約。說他“自學成才”并不是說他沒有接受過高等教育，他是芝加哥大學的畢業(yè)生，但學的不是數(shù)學或電氣工程等與計算機密切相關(guān)的專業(yè)，而是文學，1953年獲得文學士學位。20世紀50年代初期美國經(jīng)濟不太景氣，找工作比較困難，因?qū)W習文學而沒有任何專門技能的弗洛伊德在就業(yè)上遇到很大麻煩，無奈之中到西屋電氣公司當了二名計算機操作員，在IBM650機房值夜班。我們知道，早期的計算機都是以批處理方式工作的，計算機操作員的任務(wù)就是把程序員編寫好的程序在卡片穿孔機(這是脫機的輔助外部設(shè)備)上穿成卡片，然后把卡片疊放在讀卡機上輸入計算機，以便運行程序。因此，操作員的工作比較簡單，同打字員類似，不需要懂計算機，也不需要懂程序設(shè)計。但弗洛伊德畢竟是一個受過高等教育的人，又是一個有心人，干了一段操作員，很快對計算機產(chǎn)生了興趣，決心弄懂它，掌握它，于是他借了有關(guān)書籍資料在值班空閑時間刻苦學習鉆研，有問題就虛心向程序員請教。白天不值班，他又回母校去聽講有關(guān)課程。這樣，他不但在1958年又獲得了理科學士學位，而且逐漸從計算機的門外漢變成計算機的行家里手。1956年他離開西屋電氣公司，到芝加哥的裝甲研究基金會(Armour Research Foundation)，開始還是當操作員，后來就當了程序員。1962年他被馬薩諸塞州的Computer Associates公司聘為分析員。1965年他應(yīng)聘成為卡內(nèi)基—梅隆大學的副教授，3年后轉(zhuǎn)至斯坦福大學，1970年被聘任為教授。之所以能這樣快地步步高升，關(guān)鍵就在于弗洛伊德通過勤奮學習和深入研究，在計算機科學的諸多領(lǐng)域：算法，程序設(shè)計語言的邏輯和語義，自動程序綜合，自動程序驗證，編譯器的理論和實現(xiàn)等方面都作出創(chuàng)造性的貢獻。其中包括：1962年，弗洛伊德完成了Algol 60編譯器的開發(fā)，成功投入使用，這是世界上最早的Algol 60編譯器之一，而且弗洛伊德在這個編譯器的開發(fā)中率先融入了優(yōu)化的思想，使編譯所生成的目標代碼占用空間少，運行時間短。弗洛伊德優(yōu)化編譯的思想對編譯器技術(shù)的發(fā)展產(chǎn)生了深刻的影響。隨后，他又對語法分析進行了系統(tǒng)研究，大家現(xiàn)在熟知的優(yōu)先文法(precedence grammar)，限界上下文文法(bounded context grammar)等都是弗洛伊德在這個時期首先提出來的。優(yōu)先文法解決了自底向上的語法分析中的首要任務(wù)：如何找到“句柄”，也就是當前需要進行歸約的符號串。弗洛伊德通過對不同的符號定義不同的優(yōu)先級，解決了這個問題。

羅伯特·弗洛伊德 - 貢獻

弗洛伊德的主要貢獻包括弗洛伊德算法，能有效地發(fā)現(xiàn)圖的所有最短路徑；他的工作有詞法解析；他在一篇獨立發(fā)表的文章里引入了一個重要的概念——圖像渲染的誤差擴散法，也被稱為弗洛伊德-斯坦伯格抖動（但他區(qū)分了抖動和擴散）。

他一個顯著的成就是開創(chuàng)性地在程序驗證中使用了邏輯斷言。在他1967年的論文《如何確定程序的意義》Assigning Meanings to Programs中首先提出，之后演化為霍爾邏輯。

弗洛伊德與高德納工作很密切，他是高德納的著作《計算機程序設(shè)計藝術(shù)》的主要評審，并且在書中被多次提及。他與理查德·貝爾格（Richard Beigel）合著有《機器的語言：可計算和形式語言的介紹》The Language of Machines: an Introduction to Computability and Formal Languages。 [1]

弗洛伊德于1978年獲得圖靈獎，并做“程序設(shè)計的風范”（The Paradigms of Programming）的演講，圖靈獎引文是： 在構(gòu)造高效、可靠性軟件方法學領(lǐng)域的顯著影響；在下列計算機科學重要分支的奠基性的貢獻：分析理論，編程語言語義，自動程序驗證，自動程序綜合生成和算法分析。

羅伯特·弗洛伊德 - 上下文法

限界上下文文法則通過對上下文無關(guān)文法G中的兩個推導(dǎo)：

*S→βArβαγ

+S→δαε

進行比較以確定α是否是δαε的句柄，以及產(chǎn)生方式A→α是否是唯一可進行歸約的產(chǎn)生式。弗洛伊德經(jīng)過研究，給出其充分必要條件為：β和δ的最后m個符號相同，丁和o／的最初n個終結(jié)符相同。這樣一個上下文無關(guān)文法G就稱為(m，n)限界上下文文法。

在算法方面，弗洛伊德和威廉姆斯(J．Williams)在1964年共同發(fā)明了著名的堆排序算法HEAPSORT，這是與英國學者霍爾 (C.A.R.Hoare，1980年圖靈獎獲得者)發(fā)明的QUICKSORT齊名的高效排序算法之一。此外還有直接以弗洛伊德命名的求最短路的算法，這是弗洛伊德利用動態(tài)規(guī)劃(dynamic programming)的原理設(shè)計的一個高效算法。

在程序設(shè)計方面，計算機科學家非常關(guān)心的一個重要問題是如何表達和描述程序的邏輯，如何驗證程序的正確性。1967年，在美國數(shù)學會AMS舉行的應(yīng)用數(shù)學討論會上，弗洛伊德發(fā)表了那篇引起轟動并產(chǎn)生了深遠影響的論文，即“如何確定程序的意義”(Assigning Meanings to Programs)。這篇論文在程序邏輯研究的歷史上，是繼麥卡錫(J．McCarthy，1971年圖靈獎獲得者)在1963年提出用遞歸函數(shù)作為程序的模型這一方法以后最重大的一個進展。麥卡錫倡導(dǎo)的方法對于一般程序，包括大型軟件確實是行之有效的，但它有一個不足，即對于許多以命令方式編寫的軟件，其中包括賦值語句，條件語句，用While實現(xiàn)循環(huán)的語句……對這樣的程序用遞歸定義的函數(shù)去證明其正確性就很不方便了。正是為了解決這個問題，弗洛伊德在上述論文中提出了一種基于流程圖的表達程序邏輯的方法。這個方法的主要特點就是在流程圖的每一弧線上放置一個“標記”(tag)，也就是一個邏輯斷言，并且保證只要當控制經(jīng)過這個弧線時該斷言一定成立。弗洛伊德的主要貢獻在于解決了基于這種標記的形式系統(tǒng)的細節(jié)，證明了這種系統(tǒng)的完備性，解決了如何證明程序終結(jié)的問題。弗洛伊德還引入了驗證條件的概念，包括流程圖的一個組成部分(方框、圓框等)及其人口和出口處的標記。為了證明帶標記的流程圖的正確性，只要證明其中每一組成部分的驗證條件成立就行了。弗洛伊德提出的方法被叫做“歸納斷言法”(inductive assertion method)，或前后斷言法(pre·and post-assertion method)。在框圖每個斷點i上所加的邏輯斷言即標記就叫i點的歸納斷言，說明程序執(zhí)行經(jīng)過此點時在各輸入變量x和各程序變量丁之間應(yīng)存在的關(guān)系，以謂詞Pi(x,y)的形式表示。若程序從斷點i經(jīng)過路段。到下一斷點j的驗證條件以Ra(x，y)表示，丁的值在。上的變化以ha(x，y)表示，則只要能證明下式恒真：

（∨x）（∨y）[pi(x,y)∧Ra(x,y)  Pj(x,ha(x,y))]

程序從i到j(luò)的部分正確性也就證明了。

雖然用歸納斷言法不能證明程序的完全正確性，因為它必須以程序能夠終結(jié)為前提，但由于弗洛伊德在論文中同時也考慮了如何證明程序終結(jié)的問題，因此弗洛伊德的歸納斷言法也就有了普遍的意義。

弗洛伊德在同年發(fā)表于《ACM學報》(Journal of ACM)10月號上的另一篇論文中，還第一次把“不確定性”概念引入程序。所謂“不確定性程序”(non deterministic program)就是根據(jù)操作規(guī)則有多種操作可供選擇，而只選其中之一搜索下去的程序。這對人工智能問題的研究具有十分重要的意義。

此外，弗洛伊德還和伊萬斯(R． 0．Evans，因設(shè)計世界上第一個類比推理程序Analogy而聞名于世的學者。Analogy是可以判定幾何圖形是否類似的人工智能程序)一起設(shè)計了一種稱為產(chǎn)生式語言的特殊的程序設(shè)計語言FPL(Floyd-Evans Production Language)，用來編寫計算機語言的語法分析程序。之所以稱它為產(chǎn)生式語言，是因為用它編寫的程序由一系列產(chǎn)生式(或稱歸約式)組成。實際上，用 FPL編好語法分析程序以后，如果再插入語義子程序，就可以構(gòu)成一個完整的編譯器。用FPL語言編寫的程序簡稱PP程序，由以下5個部分按自左至右順序組成：

1．標號(可有可無)；

2．棧頂符號串；

3．前看符號串(或稱窗口符號串)；

4．歸約符號；

5．語義動作。

執(zhí)行一個PP程序的方法是：依次檢視各PP的第三部分。若某PP的第三部分和輸入的前看符號串一致，則進一步檢視此PP的第四部分，若非空，表示要進行歸約，此時把它的第二部分和當前實際的棧頂符號串相比。如果能匹配上，則實行歸約，即刪去實際的棧頂符號串，用第四部分代替之，然后執(zhí)行第五部分的動作。若此PP的第四部分為空，表示當前無歸約可做，直接執(zhí)行第五部分的動作即可。

羅伯特·弗洛伊德 - 獲獎

弗洛伊德是1978年12月4日在華盛頓舉行的ACM年會上接受圖靈獎的。他發(fā)表了題為“程序設(shè)計的風范”(The Paradigms of Programming)的演說。演說全文刊于Communications of ACM，1979年8月，455-460頁，也可見《前20年的ACM圖靈獎演說集》(ACM Turing Award Lectures——The First 20Years：1966—1985，ACM Pr．)，131—142頁。弗洛伊德在演說中對結(jié)構(gòu)化程序設(shè)計，遞歸協(xié)同例程(recursive coroutine)，動態(tài)程序設(shè)計，基于規(guī)則的系統(tǒng)，狀態(tài)變換機制(state-transition mechanism)等各種不同程序設(shè)計風范進行了比較，并介紹了自己在研究工作中如何根據(jù)具體情況應(yīng)用不同風范的例子，很給人以啟示。時間雖然已過去20多年，他的例子也許有些過時，但他的觀點至今仍然是有效的。