羅伯特·弗洛伊德

個人成就

弗洛伊德在同年發(fā)表于《ACM學(xué)報》（Journal of ACM)10月號上的另一篇論文中，還第一次把“不確定性”概念引入程序。所謂“不確定性程序”（non deterministic program）就是根據(jù)操作規(guī)則有多種操作可供選擇，而只選其中之一搜索下去的程序。這對人工智能問題的研究具有十分重要的意義。此外，弗洛伊德還和伊萬斯（R． 0．Evans，因設(shè)計世界上第一個類比推理程序Analogy而聞名于世的學(xué)者。Analogy是可以判定幾何圖形是否類似的人工智能程序）一起設(shè)計了一種稱為產(chǎn)生式語言的特殊的程序設(shè)計語言FPL(Floyd-Evans Production Language），用來編寫計算機語言的語法分析程序。之所以稱它為產(chǎn)生式語言，是因為用它編寫的程序由一系列產(chǎn)生式（或稱歸約式）組成。實際上，用 FPL編好語法分析程序以后，如果再插入語義子程序，就可以構(gòu)成一個完整的編譯器。用FPL語言編寫的程序簡稱PP程序，由以下5個部分按自左至右順序組成：⒈標(biāo)號（可有可無）；⒉棧頂符號串；⒊前看符號串（或稱窗口符號串）；⒋歸約符號；⒌語義動作。執(zhí)行一個PP程序的方法是：依次檢視各PP的第三部分。若某PP的第三部分和輸入的前看符號串一致，則進一步檢視此PP的第四部分，若非空，表示要進行歸約，此時把它的第二部分和當(dāng)前實際的棧頂符號串相比。如果能匹配上，則實行歸約，即刪去實際的棧頂符號串，用第四部分代替之，然后執(zhí)行第五部分的動作。若此PP的第四部分為空，表示當(dāng)前無歸約可做，直接執(zhí)行第五部分的動作即可。弗洛伊德是1978年12月4日在華盛頓舉行的ACM年會上接受圖靈獎的。他發(fā)表了題為“程序設(shè)計的風(fēng)范”（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è)計風(fēng)范進行了比較，并介紹了自己在研究工作中如何根據(jù)具體情況應(yīng)用不同風(fēng)范的例子，很給人以啟示。時間雖然已過去20多年，他的例子也許有些過時，但他的觀點至今仍然是有效的。