No.439 第13届图灵奖得主、程序流程图的发明者、自学成才的罗伯特·弗洛伊德

历届图灵奖得主通常具备高学历、高学位,且大多拥有博士学位,这并不足为奇。创新型人才需要深厚的文化底蕴和广泛的知识储备,因此接受良好的教育是理所当然的选择。然而,总会有一些例外。1978年图灵奖得主、斯坦福大学计算机科学系教授罗伯特·弗洛伊德就是这样一位“自学成才的计算机科学家”。

罗伯特·弗洛伊德于1936年6月8日出生在纽约。虽然他毕业于芝加哥大学,但并非数学或电气工程等与计算机直接相关的专业,而是文学,并于1953年获得文学士学位。20世纪50年代初期,美国经济不景气,就业竞争激烈,弗洛伊德作为一名文学专业毕业生,面临着就业困境。

在万般无奈之下,罗伯特只得暂时寻求一个栖身之所。四处寻觅之后,宾夕法尼亚州的西屋电气公司成了罗伯特的最终选择。这家电气设备制造商给了罗伯特一份非常基础的工作——基础到几乎对候选人没什么要求,那便是“计算机操作员”。虽然听起来似乎与计算机大有关联,实际上这份工作的职责仅仅是负责将程序员编写好的程序在卡片穿孔机(一个脱机的外部设备)上简单穿成卡片,然后把这些卡片叠放于读卡机器上就结束了。这样做的目的是为了补齐计算机的输入动作,以便运行程序。

在西屋电气公司担任计算机操作员后,他逐渐对计算机产生了浓厚兴趣,并决心深入研究。与这份工作十分相似的另一个岗位,是当时的打字机打字员,这两份工作有着异曲同工之妙——“你并不需要懂得机器怎么运作,在外面负责敲两下就可以了。”

可想而知,心高气傲的罗伯特并不满足于仅仅在这个机器的外面敲两下,他发誓要探明这个庞大机器背后的运作原理。

他利用值班空闲时间刻苦学习,并在白天回到母校听取相关课程,从而在1958年获得了理科学士学位,并逐渐由计算机门外汉转变为内行。

1956年,学有所成的罗伯特决心离开西屋电气公司,他尝试向芝加哥的装甲研究基金会(Armour Research Foundation,后文简称ARF)问询机会,ARF看向这个年轻的小伙子,虽然他脸上信心满满,但毕竟还是个文学学士,于是ARF又给罗伯特安排了一段时间的“计算机操作员”工作进行试炼,罗伯特并没有抱怨,而是在前期的工作中勤奋努力,并且时不时“恰巧”提出一些建设性的意见,ARF终于知道面前的这位纽约人是确实了解计算机知识的人才,于是马上给罗伯特提供了一份程序员的岗位。这是罗伯特的第一份程序员工作,也是他踏入计算机世界取得的第一次实际进展。

两年之后,学习之路未曾止步的罗伯特再次取得了芝加哥大学的理科学士学位,拥有双学士学位的他不仅知识存储更为丰富,加上日常不断的技术练习,对其他同事的不吝请教,更让他对计算机领域洞察得更为深刻,了解得更为透彻。

1962年,工作上越发出彩的罗伯特被联合电脑科技(Computer Associates,后文简称CA科技)看上,CA科技向其抛出了橄榄枝,聘请其为公司内部的分析员,罗伯特欣然接受,毕竟分析员的发展前景和薪资在当时都超过普通的程序员工作,更重要的是,去更高阶的平台,意味着罗伯特能看到计算机行业更深远的未来。

1965年,罗伯特的职业生涯再次履新,这次他重回了象牙塔,被卡内基-梅隆大学聘请为副教授,这一年,罗伯特刚刚29岁。

仅仅三年,罗伯特的平台再度升迁,这次他去到的是全世界最为知名的名校之一:斯坦福大学。需要知道的是,谷歌、雅虎,惠普等后续深刻改变世界的科技公司,其创始人中均有斯坦福毕业的校友身影。如此精英荟萃,藏龙卧虎的高等学府,罗伯特仅用了两年时间,便成为了正职教授…

如果说开挂的人生不需要解释,那么罗伯特职场上的一帆风顺似乎并不足以描绘他的行业造诣。

弗洛伊德能够迅速崭露头角的关键在于他的勤奋学习和深入研究。他在诸多计算机科学领域做出了创造性贡献,包括算法、程序设计语言的逻辑和语义、自动程序综合、自动程序验证以及编译器理论和实现等方面。其中,他于1962年成功开发了Algol 60编译器,成为世界上最早的之一,并率先引入了优化思想,使得编译生成的目标代码占用空间少、运行时间短。此外,他对语法分析进行了系统研究,首次提出了优先文法和限界上下文文法等概念,为自底向上的语法分析提供了解决方案。

在算法领域,弗洛伊德与威廉姆斯(J. Williams)在1964年共同发明了著名的堆排序算法——HEAPSORT。这一算法与英国学者霍尔(C. A. R. Hoare,1980年图灵奖获得者)发明的QUICKSORT齐名,被公认为高效的排序算法之一。此外,弗洛伊德还提出了以自己名字命名的求解最短路径的算法。这一算法基于动态规划的原理,设计简洁高效,在计算机科学中占有重要地位。

在程序设计方面,一个关键问题是如何表达和描述程序的逻辑以及验证程序的正确性。1967年,在美国数学会AMS举行的应用数学讨论会上,弗洛伊德发表了一篇引起轰动并产生深远影响的论文,名为“如何确定程序的意义”(Assigning Meanings to Programs)。这篇论文在程序逻辑研究的历史上具有重要意义,是继麦卡锡(J. McCarthy,1971年图灵奖获得者)在1963年提出用递归函数作为程序模型后的重大进展。麦卡锡提出的方法对一般程序,包括大型软件,都是行之有效的。然而,它存在一个不足之处,即对于许多以命令方式编写的软件,包括赋值语句、条件语句以及使用While实现循环的语句等,用递归定义的函数去证明其正确性并不方便。

为了解决这一问题,弗洛伊德在上述论文中提出了一种基于流程图的方法,即在每一弧线上放置一个“标记”(tag),也就是一个逻辑断言,保证只有当控制经过这个弧线时该断言才成立。弗洛伊德的主要贡献在于解决了基于这种标记的形式系统的细节,并证明了该系统的完备性,同时解决了如何证明程序终结的问题。此外,他引入了验证条件的概念,包括流程图的各组成部分(方框、圆框等)及其入口和出口处的标记。为了证明带标记的流程图的正确性,只需证明其中每个组成部分的验证条件成立即可。弗洛伊德提出的方法被称为“归纳断言法”(inductive assertion method)或前后断言法(pre- and post-assertion method)。在流程图的每个断点上加入的逻辑断言即为标记,表示程序执行经过该点时输入变量x和程序变量y之间应存在的关系,通常以谓词Pi(x, y)的形式表示。

虽然归纳断言法不能完全证明程序的正确性,因为它必须基于程序能够终结的前提,但由于弗洛伊德在论文中考虑了如何证明程序终结的问题,因此这一方法具有普遍意义。

在同年发表于《ACM学报》10月号上的另一篇论文中,弗洛伊德首次引入了“不确定性程序”(nondeterministic program)的概念。这类程序根据操作规则有多种操作可供选择,但只选择其中之一进行搜索。这对于人工智能问题的研究具有重要意义。

此外,弗洛伊德还与伊万斯(R. O. Evans)合作设计了一种特殊的程序设计语言——FPL(Floyd-Evans Production Language),用于编写计算机语言的语法分析程序。FPL是一种产生式语言,由一系列产生式(或归约式)组成。实际上,用FPL编写的程序可以插入语义子程序,构成一个完整的编译器。FP程序由以下5个部分组成:

  1. 标号(可选);
  2. 栈顶符号串;
  3. 前看符号串(或窗口符号串);
  4. 归约符号;
  5. 语义动作。

执行FP程序的方法是逐个检视各FP的第三部分。如果某个FP的第三部分与输入的前看符号串相匹配,则继续检视第四部分。如果第四部分非空,表示要进行归约,此时将实际的栈顶符号串替换为第四部分,并执行第五部分的动作。如果第四部分为空,则表示无需归约,直接执行第五部分的动作。

1978年,42岁的罗伯特受获图灵奖的嘉荣,这项号称计算机界的诺贝尔奖,在颁发给罗伯特的那一刻起,证明了整个计算机界对他的认可,证明了这个来自纽约的文科生,因为热爱计算机领域,即使通过自学,也能达成影响世界的伟大成就。

弗洛伊德在1978年12月4日的华盛顿ACM年会上接受了图灵奖,并发表了题为“程序设计的风范”(The Paradigms of Programming)的演讲。这篇演讲全文刊载于1979年8月的《ACM通讯》杂志(Communications of ACM)。在演讲中,弗洛伊德对结构化程序设计、递归协同例程、动态程序设计、基于规则的系统、状态转换机制等各种不同的程序设计风格进行了比较,并分享了自己在研究工作中如何根据具体情况应用不同风格的实例,给听众带来了启示。虽然时间已经过去了40多年,他的例子可能有些过时,但他的观点仍然是有效的。

弗洛伊德与高德纳工作很密切,他是高德纳的著作《计算机程序设计艺术》的主要评审,并且在书中被多次提及。很不幸的是,他于2001年去世,享年65岁。

0 0 投票数
文章评分
订阅评论
提醒

0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请您发表评论x
滚动至顶部