罗伯特·弗洛伊德

个人成就

弗洛伊德在同年发表于《ACM学报》（Journal of ACM)10月号上的另一篇论文中，还第一次把“不确定性”概念引入程序。所谓“不确定性程序”（non deterministic program）就是根据操作规则有多种操作可供选择，而只选其中之一搜索下去的程序。这对人工智能问题的研究具有十分重要的意义。此外，弗洛伊德还和伊万斯（R． 0．Evans，因设计世界上第一个类比推理程序Analogy而闻名于世的学者。Analogy是可以判定几何图形是否类似的人工智能程序）一起设计了一种称为产生式语言的特殊的程序设计语言FPL(Floyd-Evans Production Language），用来编写计算机语言的语法分析程序。之所以称它为产生式语言，是因为用它编写的程序由一系列产生式（或称归约式）组成。实际上，用 FPL编好语法分析程序以后，如果再插入语义子程序，就可以构成一个完整的编译器。用FPL语言编写的程序简称PP程序，由以下5个部分按自左至右顺序组成：⒈标号（可有可无）；⒉栈顶符号串；⒊前看符号串（或称窗口符号串）；⒋归约符号；⒌语义动作。执行一个PP程序的方法是：依次检视各PP的第三部分。若某PP的第三部分和输入的前看符号串一致，则进一步检视此PP的第四部分，若非空，表示要进行归约，此时把它的第二部分和当前实际的栈顶符号串相比。如果能匹配上，则实行归约，即删去实际的栈顶符号串，用第四部分代替之，然后执行第五部分的动作。若此PP的第四部分为空，表示当前无归约可做，直接执行第五部分的动作即可。弗洛伊德是1978年12月4日在华盛顿举行的ACM年会上接受图灵奖的。他发表了题为“程序设计的风范”（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页。弗洛伊德在演说中对结构化程序设计，递归协同例程（recursive coroutine），动态程序设计，基于规则的系统，状态变换机制（state-transition mechanism）等各种不同程序设计风范进行了比较，并介绍了自己在研究工作中如何根据具体情况应用不同风范的例子，很给人以启示。时间虽然已过去20多年，他的例子也许有些过时，但他的观点至今仍然是有效的。