羅伯特·弗洛伊德 - 基本信息
羅伯特·弗洛伊德 Robert W Floyd逝世 2001 年9月25日 （65歲）
研究領(lǐng)域 計(jì)算機(jī)科學(xué)
著名成就 弗洛伊德算法
研究機(jī)構(gòu) 卡內(nèi)基梅隆大學(xué) 斯坦福大學(xué)
獲獎(jiǎng) 圖靈獎(jiǎng)
羅伯特·弗洛伊德 - 概述
羅伯特·弗洛伊德（Robert W．Floyd；1936－），計(jì)算機(jī)科學(xué)家，圖靈獎(jiǎng)得主，前后斷言法的創(chuàng)始人。
歷屆圖靈獎(jiǎng)得主基本上都有高學(xué)歷、高學(xué)位，絕大多數(shù)有博士頭銜。這是可以理解的，因?yàn)閯?chuàng)新型人才需要有很好的文化素養(yǎng)，豐富的知識(shí)底蘊(yùn)，因而必須接受良好的教育。但事情總有例外，1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德就是一位“自學(xué)成才的計(jì)算機(jī)科學(xué)家”(a Self-Taught Computer Scientist)。
羅伯特·弗洛伊德 - 生平
弗洛伊德出生在美國紐約，14歲即完成高中學(xué)業(yè)，當(dāng)他1953年從芝加哥大學(xué)獲得文學(xué)學(xué)士學(xué)位時(shí)，年僅17歲，并于1958年在物理學(xué)獲得了第二個(gè)學(xué)士學(xué)位。
他在1960年代早期成為計(jì)算機(jī)操作員，并發(fā)表了許多出名的論文，并當(dāng)他27歲時(shí)，被任命為卡內(nèi)基梅隆大學(xué)的副教授，并于6年后成為斯坦福大學(xué)的正教授。此時(shí)他并沒有博士學(xué)位。
羅伯特·弗洛伊德 - 經(jīng)歷
弗洛伊德1936年6月8日生于紐約。說他“自學(xué)成才”并不是說他沒有接受過高等教育，他是芝加哥大學(xué)的畢業(yè)生，但學(xué)的不是數(shù)學(xué)或電氣工程等與計(jì)算機(jī)密切相關(guān)的專業(yè)，而是文學(xué)，1953年獲得文學(xué)士學(xué)位。20世紀(jì)50年代初期美國經(jīng)濟(jì)不太景氣，找工作比較困難，因?qū)W習(xí)文學(xué)而沒有任何專門技能的弗洛伊德在就業(yè)上遇到很大麻煩，無奈之中到西屋電氣公司當(dāng)了二名計(jì)算機(jī)操作員，在IBM650機(jī)房值夜班。我們知道，早期的計(jì)算機(jī)都是以批處理方式工作的，計(jì)算機(jī)操作員的任務(wù)就是把程序員編寫好的程序在卡片穿孔機(jī)(這是脫機(jī)的輔助外部設(shè)備)上穿成卡片，然后把卡片疊放在讀卡機(jī)上輸入計(jì)算機(jī)，以便運(yùn)行程序。因此，操作員的工作比較簡單，同打字員類似，不需要懂計(jì)算機(jī)，也不需要懂程序設(shè)計(jì)。但弗洛伊德畢竟是一個(gè)受過高等教育的人，又是一個(gè)有心人，干了一段操作員，很快對(duì)計(jì)算機(jī)產(chǎn)生了興趣，決心弄懂它，掌握它，于是他借了有關(guān)書籍資料在值班空閑時(shí)間刻苦學(xué)習(xí)鉆研，有問題就虛心向程序員請(qǐng)教。白天不值班，他又回母校去聽講有關(guān)課程。這樣，他不但在1958年又獲得了理科學(xué)士學(xué)位，而且逐漸從計(jì)算機(jī)的門外漢變成計(jì)算機(jī)的行家里手。1956年他離開西屋電氣公司，到芝加哥的裝甲研究基金會(huì)(Armour Research Foundation)，開始還是當(dāng)操作員，后來就當(dāng)了程序員。1962年他被馬薩諸塞州的Computer Associates公司聘為分析員。1965年他應(yīng)聘成為卡內(nèi)基—梅隆大學(xué)的副教授，3年后轉(zhuǎn)至斯坦福大學(xué)，1970年被聘任為教授。之所以能這樣快地步步高升，關(guān)鍵就在于弗洛伊德通過勤奮學(xué)習(xí)和深入研究，在計(jì)算機(jī)科學(xué)的諸多領(lǐng)域：算法，程序設(shè)計(jì)語言的邏輯和語義，自動(dòng)程序綜合，自動(dòng)程序驗(yàn)證，編譯器的理論和實(shí)現(xiàn)等方面都作出創(chuàng)造性的貢獻(xiàn)。其中包括：1962年，弗洛伊德完成了Algol 60編譯器的開發(fā)，成功投入使用，這是世界上最早的Algol 60編譯器之一，而且弗洛伊德在這個(gè)編譯器的開發(fā)中率先融入了優(yōu)化的思想，使編譯所生成的目標(biāo)代碼占用空間少，運(yùn)行時(shí)間短。弗洛伊德優(yōu)化編譯的思想對(duì)編譯器技術(shù)的發(fā)展產(chǎn)生了深刻的影響。隨后，他又對(duì)語法分析進(jìn)行了系統(tǒng)研究，大家現(xiàn)在熟知的優(yōu)先文法(precedence grammar)，限界上下文文法(bounded context grammar)等都是弗洛伊德在這個(gè)時(shí)期首先提出來的。優(yōu)先文法解決了自底向上的語法分析中的首要任務(wù)：如何找到“句柄”，也就是當(dāng)前需要進(jìn)行歸約的符號(hào)串。弗洛伊德通過對(duì)不同的符號(hào)定義不同的優(yōu)先級(jí)，解決了這個(gè)問題。
羅伯特·弗洛伊德 - 貢獻(xiàn)
弗洛伊德的主要貢獻(xiàn)包括弗洛伊德算法，能有效地發(fā)現(xiàn)圖的所有最短路徑；他的工作有詞法解析；他在一篇獨(dú)立發(fā)表的文章里引入了一個(gè)重要的概念——圖像渲染的誤差擴(kuò)散法，也被稱為弗洛伊德-斯坦伯格抖動(dòng)（但他區(qū)分了抖動(dòng)和擴(kuò)散）。
他一個(gè)顯著的成就是開創(chuàng)性地在程序驗(yàn)證中使用了邏輯斷言。在他1967年的論文《如何確定程序的意義》Assigning Meanings to Programs中首先提出，之后演化為霍爾邏輯。
弗洛伊德與高德納工作很密切，他是高德納的著作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的主要評(píng)審，并且在書中被多次提及。他與理查德·貝爾格（Richard Beigel）合著有《機(jī)器的語言：可計(jì)算和形式語言的介紹》The Language of Machines: an Introduction to Computability and Formal Languages。 [1]
弗洛伊德于1978年獲得圖靈獎(jiǎng)，并做“程序設(shè)計(jì)的風(fēng)范”（The Paradigms of Programming）的演講，圖靈獎(jiǎng)引文是： 在構(gòu)造高效、可靠性軟件方法學(xué)領(lǐng)域的顯著影響；在下列計(jì)算機(jī)科學(xué)重要分支的奠基性的貢獻(xiàn)：分析理論，編程語言語義，自動(dòng)程序驗(yàn)證，自動(dòng)程序綜合生成和算法分析。
羅伯特·弗洛伊德 - 上下文法
限界上下文文法則通過對(duì)上下文無關(guān)文法G中的兩個(gè)推導(dǎo)：
*S→βArβαγ
+S→δαε
進(jìn)行比較以確定α是否是δαε的句柄，以及產(chǎn)生方式A→α是否是唯一可進(jìn)行歸約的產(chǎn)生式。弗洛伊德經(jīng)過研究，給出其充分必要條件為：β和δ的最后m個(gè)符號(hào)相同，丁和o／的最初n個(gè)終結(jié)符相同。這樣一個(gè)上下文無關(guān)文法G就稱為(m，n)限界上下文文法。
在算法方面，弗洛伊德和威廉姆斯(J．Williams)在1964年共同發(fā)明了著名的堆排序算法HEAPSORT，這是與英國學(xué)者霍爾 (C.A.R.Hoare，1980年圖靈獎(jiǎng)獲得者)發(fā)明的QUICKSORT齊名的高效排序算法之一。此外還有直接以弗洛伊德命名的求最短路的算法，這是弗洛伊德利用動(dòng)態(tài)規(guī)劃(dynamic programming)的原理設(shè)計(jì)的一個(gè)高效算法。
在程序設(shè)計(jì)方面，計(jì)算機(jī)科學(xué)家非常關(guān)心的一個(gè)重要問題是如何表達(dá)和描述程序的邏輯，如何驗(yàn)證程序的正確性。1967年，在美國數(shù)學(xué)會(huì)AMS舉行的應(yīng)用數(shù)學(xué)討論會(huì)上，弗洛伊德發(fā)表了那篇引起轟動(dòng)并產(chǎn)生了深遠(yuǎn)影響的論文，即“如何確定程序的意義”(Assigning Meanings to Programs)。這篇論文在程序邏輯研究的歷史上，是繼麥卡錫(J．McCarthy，1971年圖靈獎(jiǎng)獲得者)在1963年提出用遞歸函數(shù)作為程序的模型這一方法以后最重大的一個(gè)進(jìn)展。麥卡錫倡導(dǎo)的方法對(duì)于一般程序，包括大型軟件確實(shí)是行之有效的，但它有一個(gè)不足，即對(duì)于許多以命令方式編寫的軟件，其中包括賦值語句，條件語句，用While實(shí)現(xiàn)循環(huán)的語句……對(duì)這樣的程序用遞歸定義的函數(shù)去證明其正確性就很不方便了。正是為了解決這個(gè)問題，弗洛伊德在上述論文中提出了一種基于流程圖的表達(dá)程序邏輯的方法。這個(gè)方法的主要特點(diǎn)就是在流程圖的每一弧線上放置一個(gè)“標(biāo)記”(tag)，也就是一個(gè)邏輯斷言，并且保證只要當(dāng)控制經(jīng)過這個(gè)弧線時(shí)該斷言一定成立。弗洛伊德的主要貢獻(xiàn)在于解決了基于這種標(biāo)記的形式系統(tǒng)的細(xì)節(jié)，證明了這種系統(tǒng)的完備性，解決了如何證明程序終結(jié)的問題。弗洛伊德還引入了驗(yàn)證條件的概念，包括流程圖的一個(gè)組成部分(方框、圓框等)及其人口和出口處的標(biāo)記。為了證明帶標(biāo)記的流程圖的正確性，只要證明其中每一組成部分的驗(yàn)證條件成立就行了。弗洛伊德提出的方法被叫做“歸納斷言法”(inductive assertion method)，或前后斷言法(pre·and post-assertion method)。在框圖每個(gè)斷點(diǎn)i上所加的邏輯斷言即標(biāo)記就叫i點(diǎn)的歸納斷言，說明程序執(zhí)行經(jīng)過此點(diǎn)時(shí)在各輸入變量x和各程序變量丁之間應(yīng)存在的關(guān)系，以謂詞Pi(x,y)的形式表示。若程序從斷點(diǎn)i經(jīng)過路段。到下一斷點(diǎn)j的驗(yàn)證條件以Ra(x，y)表示，丁的值在。上的變化以ha(x，y)表示，則只要能證明下式恒真：
（∨x）（∨y）[pi(x,y)∧Ra(x,y) Pj(x,ha(x,y))]
程序從i到j(luò)的部分正確性也就證明了。
雖然用歸納斷言法不能證明程序的完全正確性，因?yàn)樗仨氁猿绦蚰軌蚪K結(jié)為前提，但由于弗洛伊德在論文中同時(shí)也考慮了如何證明程序終結(jié)的問題，因此弗洛伊德的歸納斷言法也就有了普遍的意義。
弗洛伊德在同年發(fā)表于《ACM學(xué)報(bào)》(Journal of ACM)10月號(hào)上的另一篇論文中，還第一次把“不確定性”概念引入程序。所謂“不確定性程序”(non deterministic program)就是根據(jù)操作規(guī)則有多種操作可供選擇，而只選其中之一搜索下去的程序。這對(duì)人工智能問題的研究具有十分重要的意義。
此外，弗洛伊德還和伊萬斯(R． 0．Evans，因設(shè)計(jì)世界上第一個(gè)類比推理程序Analogy而聞名于世的學(xué)者。Analogy是可以判定幾何圖形是否類似的人工智能程序)一起設(shè)計(jì)了一種稱為產(chǎn)生式語言的特殊的程序設(shè)計(jì)語言FPL(Floyd-Evans Production Language)，用來編寫計(jì)算機(jī)語言的語法分析程序。之所以稱它為產(chǎn)生式語言，是因?yàn)橛盟帉懙某绦蛴梢幌盗挟a(chǎn)生式(或稱歸約式)組成。實(shí)際上，用 FPL編好語法分析程序以后，如果再插入語義子程序，就可以構(gòu)成一個(gè)完整的編譯器。用FPL語言編寫的程序簡稱PP程序，由以下5個(gè)部分按自左至右順序組成：
1．標(biāo)號(hào)(可有可無)；
2．棧頂符號(hào)串；
3．前看符號(hào)串(或稱窗口符號(hào)串)；
4．歸約符號(hào)；
5．語義動(dòng)作。
執(zhí)行一個(gè)PP程序的方法是：依次檢視各PP的第三部分。若某PP的第三部分和輸入的前看符號(hào)串一致，則進(jìn)一步檢視此PP的第四部分，若非空，表示要進(jìn)行歸約，此時(shí)把它的第二部分和當(dāng)前實(shí)際的棧頂符號(hào)串相比。如果能匹配上，則實(shí)行歸約，即刪去實(shí)際的棧頂符號(hào)串，用第四部分代替之，然后執(zhí)行第五部分的動(dòng)作。若此PP的第四部分為空，表示當(dāng)前無歸約可做，直接執(zhí)行第五部分的動(dòng)作即可。
羅伯特·弗洛伊德 - 獲獎(jiǎng)
弗洛伊德是1978年12月4日在華盛頓舉行的ACM年會(huì)上接受圖靈獎(jiǎng)的。他發(fā)表了題為“程序設(shè)計(jì)的風(fēng)范”(The Paradigms of Programming)的演說。演說全文刊于Communications of ACM，1979年8月，455-460頁，也可見《前20年的ACM圖靈獎(jiǎng)演說集》(ACM Turing Award Lectures——The First 20Years：1966—1985，ACM Pr．)，131—142頁。弗洛伊德在演說中對(duì)結(jié)構(gòu)化程序設(shè)計(jì)，遞歸協(xié)同例程(recursive coroutine)，動(dòng)態(tài)程序設(shè)計(jì)，基于規(guī)則的系統(tǒng)，狀態(tài)變換機(jī)制(state-transition mechanism)等各種不同程序設(shè)計(jì)風(fēng)范進(jìn)行了比較，并介紹了自己在研究工作中如何根據(jù)具體情況應(yīng)用不同風(fēng)范的例子，很給人以啟示。時(shí)間雖然已過去20多年，他的例子也許有些過時(shí)，但他的觀點(diǎn)至今仍然是有效的。