本文发表在 rolia.net 枫下论坛John Backus
Citation
For profound, influential, and lasting contributions to the design of practical high-level programming systems, notably through his work on FORTRAN, and for seminal publication of formal procedures for the specification of programming languages.
---------------------------------------------------------------------------
世界是复杂的,世界上的人和事更是处在瞬息万变之中,叫人捉摸不定。世界上第一个高级程序设计语言FORTRAN和最广泛流行的元语言BNF的发明人约翰.巴克斯 (John Warner Backus)获得1977年的图灵奖显然是绝对当之无愧和众望所归的。但是谁能想到,20岁之前的巴克斯却是个不爱学习、喜欢游荡的纨绔弟子,曾经被大学逐出门外呢?
巴克斯1924年12月3日生于美国的历史名城费城,其父是阿特拉斯火药公司的职工。当时工厂常常出事故,发生爆炸,产量也上不去,但是谁也找不出原因。老巴克斯是一个机灵的人,他分析问题极有可能与从德国进口的昂贵的温度计可能并不那么精确有关,于是说明公司派他远度大西洋去德国了解和学习温度计的制造工艺,最后带回了一批好的温度计,终于解决了工厂的安全作业难题,他自己也由一名普通员工被提升为公司的首席化学家。第一次世界大战期间,美国的军火企业都开足马生产,大捞了一把,老巴克斯也因此显赫一时。战后,由于他没有获得原来许诺给他的在杜邦公司的职务,愤而离开化工界、军火界、改做证券经纪人,也发了一笔大财。因此,童年和少年时代的巴克斯生活条件相当优越,过得无忧无虑。在东海岸特拉华湾的海滨城市威尔明顿度过童年以后,巴克斯就学于宾夕法尼亚州波茨敦市很有名望的希尔学校,但他不爱学习,只盼望暑假到新罕布什尔州的暑假学校,在那里可以划船、嬉戏、度过美好的时光,因此巴克斯的学习成绩从来就不及格,拖了两年才勉强毕业,于1942年进了弗吉尼亚大学。由于本来就不爱学习,加上第二次世界大战已经爆发,1941年12月7日日本偷袭珍珠港以后,美国正式宣布参战,巴克斯更是只等着应征入伍,不思学习,把大多数时间花在舞会上,每周只去上一节轻松的音乐欣赏课,终于被学校处分,扫地出门。1943年巴克斯参军入伍,在乔治亚洲服役,当了一名下士,率领一个防空小队。在部队组织的一次能力测试中,巴克斯不经意地显露出了他的聪明和才能,受到上级赏识,陆军决定送他上学深造。这样,当他的战友们都被送往二次大战的战场上去的时候,巴克斯却上了哈弗福德学院(Haverford College)的医学院预科。但巴克斯对医学不感兴趣,也不喜欢那里的人,觉得他们只会背书而不会思考。因此巴克斯只学了9个月的医学就离开了那里,转到哥伦比亚大学学习数学。经过这番磨练,巴克斯已经从混沌走向清醒,开始正经学习。1949年他取得学士学位。但毕业时,巴克斯对自己的未来仍然没有打算,不知道到哪里去,也不知道干什么好。幸好一个偶然的机会,他到IBM公司的计算中心参观,在那里见到了IBM早期的SSEC计算机(Selective Sequence Electronic Calculator)。SSEC是一台电子管计算机,几个大柜子占满了一间大屋子,到处是电子管和电缆、电线。由于程序必须通过穿孔纸带输入,机器的成千上万个电子机械部件又不可靠,经常出故障,因此机房里操作员、管理员、程序员们忙成一团,查线路的,查手册的,讨论和争论问题的……气氛忙乱而热烈。巴克斯当时并不了解SSEC还不是真正意义上的电子计算机,它连存储程序的存储器都没有,但看到现场的环境和气氛,立刻心里一亮:这正是他要找的工作!这正是适合他性格的富于挑战性的工作!第二天他便向IBM公司的主管提出求职申请,经过一次测试顺利通过,巴克斯从此开始在SSEC上的三年工作。
人们称巴克斯为“不知疲倦的发明家”。事实确实如此。进入IBM以后,巴克斯就全身心地投入工作。他接手的第一个较大的项目是计算“月历”,这是一个相当复杂而困难的问题,因为月历要能给出一年中任一时刻月亮所处的精确位置坐标,但巴克斯出色地完成了任务。接着,巴克斯和同事海尔里克(H. Herrick)一起又成功地开发出了一个叫Speedcoding的程序,用于浮点数运算。大家知道,浮点运算比定点运算复杂得多,浮点运算部件的设计与实现也困难得多,因此早期计算机大多没有浮点运算部件。但许多科学与工程计算问题又需要处理非常小的数或非常大的数,这怎么办呢?计算机的先驱冯.诺伊曼提出对定点数附以“比例因子”使这成为浮点数,从原则上解决了这个问题,但却给程序员出了难题:在不能确切知道计算的中间结果和最后结果的范围的情况下,如何设定比例因子?比例因子取小了,运算发生溢出;比例因子取大了,影响结果精度。这成了当时程序设计的一大难题。巴克斯和海尔里克的Speedcoding 成功地解决了这个难题,可以根据问题自动设置和调理比例因子,免除了程序员在这方面的麻烦。
月历程序和Speedcoding程序的成功奠定了巴克斯作为出色的程序员在公司的地位,赢得了同事的尊敬和上司的器重。但巴克斯是一个永远不满足于现状、总想变革现实的人。鉴于当时用机器语言也就是二进制代码0和1进行编程和调试程序所带来的种种弊端——效率低,难于检查和发现问题,不便于交流,以及由此而导致软件开发费用高昂,等等,经过深思熟虑,巴克斯于1953年向IBM的老板卡斯伯特.赫德(Cuthbert Hurd)提交了一个备忘录,建议设计一种接近人类语言的编程语言代替机器语言,以从根本上提高编程效率,降低编程费用。意想不到的是,巴克斯这一对计算技术的发展起了如此重大影响的历史性建议遭到了当时任IBM公司顾问的冯.诺伊曼的强烈反对。由于对程序设计的高昂费用和代价不太了解,冯.诺伊曼认为巴克斯的建议是没有必要的,也是不切实际的。好在赫德比较开明而有远见,虽然冯.诺伊曼的声望和地位远比巴克斯高,他还是支持了巴克斯,批准了巴克斯的计划,使Fortran的诞生成为可能。1957年4月,经过巴克斯和他的同事们的艰苦努力,Fortran(由“公式翻译器”,即formula translator各取前几个字母组合而成)的编译器第一次在西屋电气公司订购的704计算机上成功运行,标志着一个时代(机器语言编程时代)的结束,另一个时代(高级语言编程时代)的开始。Fortran 语言主要用于数值计算,它的特点是接近数学公式,简单易用,功能逐步扩大,如允许复型和双精度浮点运算,子程序定义机制,输入输出的格式说明,允许布尔表达式,函数和子例程名可以作为参数传递,等等。作为世界上第一个高级程序设计语言,它对其后出现的上千种高级程序设计语言都有或大或小的影响,它本身也经历了许多重大的变革,有许多版本。据不完全统计,从20世纪50年代诞生至今,Fortran共出现过90多个版本,其中曾经流行的主要版本有Fortran I,1958年推出的能处理子程序,并可与汇编语言相连的Fortran II,1962年问世的Fortran III,1966年推出第一个Fortran语言标准称为Fortran 66,20世纪70年代修订为Fortran 77,1991年ISO批准新的Fortran标准称为Fortran 90,等等。在Fortran 90中,又有如下一系列的扩充与改进:
(1) 数组运算机制;
(2) 改善了数值计算;
(3) 数据类型参数化,允许使用多种字符类型,满足各国字符处理的需要;
(4) 从6种内部数据类型中派生出用户定义的数据类型;
(5) 模块化数据与过程定义控制,提供了一种数据与过程包装的强有力的而又安全的形式;
(6) 指针机制,允许创建和操作动态数据结构;
(7) 增加自由形式的源程序形式;
(8) 提供了过程的递归调用机制;
(9) 提供了附加的控制结构,如do…end do, do while < condition>等。
此外,还有许多为了满足解特定问题的需要而对Fortran 加以补充或修改而形成的高级程序设计语言,其中比较著名的有美国阿姆斯研究中心计算流体动力学分部对Fortran进行逻辑扩充、在ILLIAC III计算机上实现的CFD语言(Computational Fluid Dynamics,即计算流体动力学语言),这个语言依赖于能够执行向量及标量指令的机器语言,是与机器有关的;code and go Fortran,这是对Fortran III的一种改进版本,主要为了快速编译和执行;CONTRAN语言(Control Translator),这是综合了Fortran III和ALGOL 60语言的许多特点而形成的高级语言;LRLTRAN (Lawrence Radiation Laboratory Translator,劳伦斯福射实验室翻译程序),这是著名的劳伦斯福射实验室根据其特定需要在CDC公司的STAR-100计算机(这是20世纪70年代中期推出的一种大型快速计算机,其中央处理器包含两条浮点流水线和用于处理十进制数和字符串的行部件,指令系统中有硬件宏指令,能处理向量、稀疏向量及行,有磁心存储器、页面调度的磁鼓和磁盘存储器三级存储器,有4至12个16位的输入输出通道和一个128位的直接快速存取通道,是当时典型的单指令流多数据流系统)上开发的一种基于Fortran,但具有向量运算、位和字节操作以及指针操作的高级语言,特别适合于科学计算和系统程序设计。另外,在宝来公司 (Burroughs)20世纪70年代为美国国防部用于弹道导弹防卫数据实时处理而研制的著名PEPE计算机系统(Parallel Element Processing Ensemble,并行单元处理组合,实际上就是由多达1 000个处理单元组成的多处理机并行计算机系统)中,其核心软件是一种称为PFOR的并行的Fortran语言。此外,还有适合于有理函数计算的ALTRAN,适合于处理向量与矩阵的VECTRAN,等等,无不都是在Fortran的基础上设计、开发出来的,都可以认为是Fortran家族的“始祖”。还应该特别指出的是,曾经出现的成百上千个高级程序设计语言,绝大多数自从出世就没有流行过;有许多则风行一阵以后就很快销声匿迹,而Fortran则至今常胜不衰,保持着强大的生命力,这说明了它设计与实现两方面都是成功的,附带说一句,冯.诺伊曼于1957年不幸英年早逝,没有看到Fortran正式投入使用,但这位出生在匈牙利的天才科学家后来意识到了自己在这件事上的错误,没有坚持反对巴克斯的计划。
基于Fortran的巨大成功,在1958年5月于苏黎世举行的一次国际性计算机会议上,决定成立一个委员会,以Fortran为基础,对它作进一步改进,以形成一种单一的、标准化的计算机高级程序设计语言。许多著名的计算机科学家都参加了这个委员会。它的工作成果就是Algol 58及随后的Algol 60等一系列版本。巴克斯也参加了这个委员会,而且对Algol融入了一些新概念、新思想、新功能,如局部变量、递归等由衷地感到高兴。但这时,基于开发Fortran的经验,巴克斯关注的重点已由定义语言本身转为如何清晰地描述和表达语言这个问题上,也就是要创建一个“元语言”(metalanguage)。经过不懈探索,1959年6月,在联合国教科文组织即UNESCO于巴黎召开的一个讨论程序设计语言的语法和语义的会议上,巴克斯在他提交的一篇论文中提出了如今众所周知的“巴克斯范式”BIF(Backus Normal Form)。巴克斯范式以递归方式描述语言中的各种成分,凡遵守其规则的程序就可保证语法上的正确性。BNF由于其简洁、明了、科学而被广泛接受,成为描述各种程序设计语言的最常用的工具。我们现在看到的各种程序设计语言文本中所给出的BNF,是Backus-Naur Form,即巴克斯-诺尔范式,也就是经丹麦数学家彼得.诺尔(Peter Naur)改进与完善过的巴克斯范式,实际上绝大多数又是经瑞士著名的计算机科学家沃思(N. Wirth)扩充过的巴克斯-诺尔(Peter Naur)改进与完善过的巴克斯范式,实际上绝大多数又是经瑞士著名的计算机科学家沃思(N. Wirth)扩充过的巴克斯-诺尔范式,即EBNF(Extended BNF)。沃思是1984年图灵奖获得者。
巴克斯范式的左部是一个非终结符,非终结符用尖括号括起。右部是由非终结符和终结符组成的一个任意符号串。具有相同左部的产生规则可以共用一个左部,各右部之间以竖直线“|”分开。例如定义“标识符”的一组BNF公式为:
<标识符>::= <字母>| <标识符> <字母>|<标识符><数字>
<字母>::=a|b|c|…|x|y|z
<数字>::=0|1|2|3|…|8|9
我们目前常用的高级程序设计语言都是所谓冯.诺伊曼型的语言,也就是而向过程的语言,是以“逐词逐句”的方式工作的。巴克斯后来致力于开发非冯.诺伊曼型的语言,也就是函数式语言 (functional language)。这种语言的主要成分是原始函数、函数型和定义函数。程序就是函数,程序作用在结构型数据上,产生结构型结果。用这种语言编写的程序结构清晰,便于使用代数方法研究程序的特性。巴克斯后来推出了一种名为FP的函数式程序设计系统成为函数式语言的典型代表。此外,巴克斯也是归约机(reduction machine)这一不同于冯.诺伊曼的新的计算机体系结构的首创者。1972年,巴克斯在其为IBM公司的所撰写的研究报告“归约语言及无变元的程序设计”(Reduction Languages and Variable Free Programming)一文中最早提出了归约的概念。归约的基本思想是在函数的计算过程中通过替换不停地修改计算目标,直到被计算的目标已经是最小单元为止。这种方式不再具有变元的概念,所有的目标均是通过计算获得的。这一过程与纯函数的递归计算过程的代入方法相接近,因而可以把对归约机的研究与函数式程序设计语言的研究结合在一起,归约机的结构中一般包括递归机构和替换机构,归约方式则分串归约和图归约两种,前者实现按值调用,后者实现按引用调用。在巴克斯论文发表以后,一批学者致力于归约机的研究与开发,相继推出了GMD(Berklin,1975)、Callular(北卡罗莱纳大学Mago,1979)、AMPS(R. M. Keller,1979)、 ALICE(J. Darlington, 1981)等一批各种类型的归纳机。其中以树结构的Cellular最引人注意。
巴克斯由于以上介绍的一系列重大成就而获得许多荣誉和奖励。除图灵奖外,1967年他获得IEEE的W. W. McDowell奖;1975年被授予美国全国科学奖章(National Medal of Science);1994年美国工程院授予他Charles Stark Draper奖。巴克斯是美国科学院院士,也是美国工程院院士。
巴克斯是在1977年10月17日于西雅图举行的ACM年会上接受图灵奖的。ACM评奖委员会主席萨梅特(J. E.Sammet)致词并授奖,巴克斯发表了演说,题为“程序设计能从冯.伊曼形式中解脱出来吗?函数式风格及其程序的代数”(Can Programming be Literated from the von Neumann Style? A Functional Style and Its Algebra of Programs),对他所开发的FP及其意义作了详细的介绍。演说全文刊载于Communications of ACM,1978年8月,613-641页,也可见《前20年的ACM图灵奖演说集》(ACM Turing Award Lectures——The First 20Years:1966-1985,ACM Pr.),63-130页。
巴克斯已于1991年退休。更多精彩文章及讨论,请光临枫下论坛 rolia.net
Citation
For profound, influential, and lasting contributions to the design of practical high-level programming systems, notably through his work on FORTRAN, and for seminal publication of formal procedures for the specification of programming languages.
---------------------------------------------------------------------------
世界是复杂的,世界上的人和事更是处在瞬息万变之中,叫人捉摸不定。世界上第一个高级程序设计语言FORTRAN和最广泛流行的元语言BNF的发明人约翰.巴克斯 (John Warner Backus)获得1977年的图灵奖显然是绝对当之无愧和众望所归的。但是谁能想到,20岁之前的巴克斯却是个不爱学习、喜欢游荡的纨绔弟子,曾经被大学逐出门外呢?
巴克斯1924年12月3日生于美国的历史名城费城,其父是阿特拉斯火药公司的职工。当时工厂常常出事故,发生爆炸,产量也上不去,但是谁也找不出原因。老巴克斯是一个机灵的人,他分析问题极有可能与从德国进口的昂贵的温度计可能并不那么精确有关,于是说明公司派他远度大西洋去德国了解和学习温度计的制造工艺,最后带回了一批好的温度计,终于解决了工厂的安全作业难题,他自己也由一名普通员工被提升为公司的首席化学家。第一次世界大战期间,美国的军火企业都开足马生产,大捞了一把,老巴克斯也因此显赫一时。战后,由于他没有获得原来许诺给他的在杜邦公司的职务,愤而离开化工界、军火界、改做证券经纪人,也发了一笔大财。因此,童年和少年时代的巴克斯生活条件相当优越,过得无忧无虑。在东海岸特拉华湾的海滨城市威尔明顿度过童年以后,巴克斯就学于宾夕法尼亚州波茨敦市很有名望的希尔学校,但他不爱学习,只盼望暑假到新罕布什尔州的暑假学校,在那里可以划船、嬉戏、度过美好的时光,因此巴克斯的学习成绩从来就不及格,拖了两年才勉强毕业,于1942年进了弗吉尼亚大学。由于本来就不爱学习,加上第二次世界大战已经爆发,1941年12月7日日本偷袭珍珠港以后,美国正式宣布参战,巴克斯更是只等着应征入伍,不思学习,把大多数时间花在舞会上,每周只去上一节轻松的音乐欣赏课,终于被学校处分,扫地出门。1943年巴克斯参军入伍,在乔治亚洲服役,当了一名下士,率领一个防空小队。在部队组织的一次能力测试中,巴克斯不经意地显露出了他的聪明和才能,受到上级赏识,陆军决定送他上学深造。这样,当他的战友们都被送往二次大战的战场上去的时候,巴克斯却上了哈弗福德学院(Haverford College)的医学院预科。但巴克斯对医学不感兴趣,也不喜欢那里的人,觉得他们只会背书而不会思考。因此巴克斯只学了9个月的医学就离开了那里,转到哥伦比亚大学学习数学。经过这番磨练,巴克斯已经从混沌走向清醒,开始正经学习。1949年他取得学士学位。但毕业时,巴克斯对自己的未来仍然没有打算,不知道到哪里去,也不知道干什么好。幸好一个偶然的机会,他到IBM公司的计算中心参观,在那里见到了IBM早期的SSEC计算机(Selective Sequence Electronic Calculator)。SSEC是一台电子管计算机,几个大柜子占满了一间大屋子,到处是电子管和电缆、电线。由于程序必须通过穿孔纸带输入,机器的成千上万个电子机械部件又不可靠,经常出故障,因此机房里操作员、管理员、程序员们忙成一团,查线路的,查手册的,讨论和争论问题的……气氛忙乱而热烈。巴克斯当时并不了解SSEC还不是真正意义上的电子计算机,它连存储程序的存储器都没有,但看到现场的环境和气氛,立刻心里一亮:这正是他要找的工作!这正是适合他性格的富于挑战性的工作!第二天他便向IBM公司的主管提出求职申请,经过一次测试顺利通过,巴克斯从此开始在SSEC上的三年工作。
人们称巴克斯为“不知疲倦的发明家”。事实确实如此。进入IBM以后,巴克斯就全身心地投入工作。他接手的第一个较大的项目是计算“月历”,这是一个相当复杂而困难的问题,因为月历要能给出一年中任一时刻月亮所处的精确位置坐标,但巴克斯出色地完成了任务。接着,巴克斯和同事海尔里克(H. Herrick)一起又成功地开发出了一个叫Speedcoding的程序,用于浮点数运算。大家知道,浮点运算比定点运算复杂得多,浮点运算部件的设计与实现也困难得多,因此早期计算机大多没有浮点运算部件。但许多科学与工程计算问题又需要处理非常小的数或非常大的数,这怎么办呢?计算机的先驱冯.诺伊曼提出对定点数附以“比例因子”使这成为浮点数,从原则上解决了这个问题,但却给程序员出了难题:在不能确切知道计算的中间结果和最后结果的范围的情况下,如何设定比例因子?比例因子取小了,运算发生溢出;比例因子取大了,影响结果精度。这成了当时程序设计的一大难题。巴克斯和海尔里克的Speedcoding 成功地解决了这个难题,可以根据问题自动设置和调理比例因子,免除了程序员在这方面的麻烦。
月历程序和Speedcoding程序的成功奠定了巴克斯作为出色的程序员在公司的地位,赢得了同事的尊敬和上司的器重。但巴克斯是一个永远不满足于现状、总想变革现实的人。鉴于当时用机器语言也就是二进制代码0和1进行编程和调试程序所带来的种种弊端——效率低,难于检查和发现问题,不便于交流,以及由此而导致软件开发费用高昂,等等,经过深思熟虑,巴克斯于1953年向IBM的老板卡斯伯特.赫德(Cuthbert Hurd)提交了一个备忘录,建议设计一种接近人类语言的编程语言代替机器语言,以从根本上提高编程效率,降低编程费用。意想不到的是,巴克斯这一对计算技术的发展起了如此重大影响的历史性建议遭到了当时任IBM公司顾问的冯.诺伊曼的强烈反对。由于对程序设计的高昂费用和代价不太了解,冯.诺伊曼认为巴克斯的建议是没有必要的,也是不切实际的。好在赫德比较开明而有远见,虽然冯.诺伊曼的声望和地位远比巴克斯高,他还是支持了巴克斯,批准了巴克斯的计划,使Fortran的诞生成为可能。1957年4月,经过巴克斯和他的同事们的艰苦努力,Fortran(由“公式翻译器”,即formula translator各取前几个字母组合而成)的编译器第一次在西屋电气公司订购的704计算机上成功运行,标志着一个时代(机器语言编程时代)的结束,另一个时代(高级语言编程时代)的开始。Fortran 语言主要用于数值计算,它的特点是接近数学公式,简单易用,功能逐步扩大,如允许复型和双精度浮点运算,子程序定义机制,输入输出的格式说明,允许布尔表达式,函数和子例程名可以作为参数传递,等等。作为世界上第一个高级程序设计语言,它对其后出现的上千种高级程序设计语言都有或大或小的影响,它本身也经历了许多重大的变革,有许多版本。据不完全统计,从20世纪50年代诞生至今,Fortran共出现过90多个版本,其中曾经流行的主要版本有Fortran I,1958年推出的能处理子程序,并可与汇编语言相连的Fortran II,1962年问世的Fortran III,1966年推出第一个Fortran语言标准称为Fortran 66,20世纪70年代修订为Fortran 77,1991年ISO批准新的Fortran标准称为Fortran 90,等等。在Fortran 90中,又有如下一系列的扩充与改进:
(1) 数组运算机制;
(2) 改善了数值计算;
(3) 数据类型参数化,允许使用多种字符类型,满足各国字符处理的需要;
(4) 从6种内部数据类型中派生出用户定义的数据类型;
(5) 模块化数据与过程定义控制,提供了一种数据与过程包装的强有力的而又安全的形式;
(6) 指针机制,允许创建和操作动态数据结构;
(7) 增加自由形式的源程序形式;
(8) 提供了过程的递归调用机制;
(9) 提供了附加的控制结构,如do…end do, do while < condition>等。
此外,还有许多为了满足解特定问题的需要而对Fortran 加以补充或修改而形成的高级程序设计语言,其中比较著名的有美国阿姆斯研究中心计算流体动力学分部对Fortran进行逻辑扩充、在ILLIAC III计算机上实现的CFD语言(Computational Fluid Dynamics,即计算流体动力学语言),这个语言依赖于能够执行向量及标量指令的机器语言,是与机器有关的;code and go Fortran,这是对Fortran III的一种改进版本,主要为了快速编译和执行;CONTRAN语言(Control Translator),这是综合了Fortran III和ALGOL 60语言的许多特点而形成的高级语言;LRLTRAN (Lawrence Radiation Laboratory Translator,劳伦斯福射实验室翻译程序),这是著名的劳伦斯福射实验室根据其特定需要在CDC公司的STAR-100计算机(这是20世纪70年代中期推出的一种大型快速计算机,其中央处理器包含两条浮点流水线和用于处理十进制数和字符串的行部件,指令系统中有硬件宏指令,能处理向量、稀疏向量及行,有磁心存储器、页面调度的磁鼓和磁盘存储器三级存储器,有4至12个16位的输入输出通道和一个128位的直接快速存取通道,是当时典型的单指令流多数据流系统)上开发的一种基于Fortran,但具有向量运算、位和字节操作以及指针操作的高级语言,特别适合于科学计算和系统程序设计。另外,在宝来公司 (Burroughs)20世纪70年代为美国国防部用于弹道导弹防卫数据实时处理而研制的著名PEPE计算机系统(Parallel Element Processing Ensemble,并行单元处理组合,实际上就是由多达1 000个处理单元组成的多处理机并行计算机系统)中,其核心软件是一种称为PFOR的并行的Fortran语言。此外,还有适合于有理函数计算的ALTRAN,适合于处理向量与矩阵的VECTRAN,等等,无不都是在Fortran的基础上设计、开发出来的,都可以认为是Fortran家族的“始祖”。还应该特别指出的是,曾经出现的成百上千个高级程序设计语言,绝大多数自从出世就没有流行过;有许多则风行一阵以后就很快销声匿迹,而Fortran则至今常胜不衰,保持着强大的生命力,这说明了它设计与实现两方面都是成功的,附带说一句,冯.诺伊曼于1957年不幸英年早逝,没有看到Fortran正式投入使用,但这位出生在匈牙利的天才科学家后来意识到了自己在这件事上的错误,没有坚持反对巴克斯的计划。
基于Fortran的巨大成功,在1958年5月于苏黎世举行的一次国际性计算机会议上,决定成立一个委员会,以Fortran为基础,对它作进一步改进,以形成一种单一的、标准化的计算机高级程序设计语言。许多著名的计算机科学家都参加了这个委员会。它的工作成果就是Algol 58及随后的Algol 60等一系列版本。巴克斯也参加了这个委员会,而且对Algol融入了一些新概念、新思想、新功能,如局部变量、递归等由衷地感到高兴。但这时,基于开发Fortran的经验,巴克斯关注的重点已由定义语言本身转为如何清晰地描述和表达语言这个问题上,也就是要创建一个“元语言”(metalanguage)。经过不懈探索,1959年6月,在联合国教科文组织即UNESCO于巴黎召开的一个讨论程序设计语言的语法和语义的会议上,巴克斯在他提交的一篇论文中提出了如今众所周知的“巴克斯范式”BIF(Backus Normal Form)。巴克斯范式以递归方式描述语言中的各种成分,凡遵守其规则的程序就可保证语法上的正确性。BNF由于其简洁、明了、科学而被广泛接受,成为描述各种程序设计语言的最常用的工具。我们现在看到的各种程序设计语言文本中所给出的BNF,是Backus-Naur Form,即巴克斯-诺尔范式,也就是经丹麦数学家彼得.诺尔(Peter Naur)改进与完善过的巴克斯范式,实际上绝大多数又是经瑞士著名的计算机科学家沃思(N. Wirth)扩充过的巴克斯-诺尔(Peter Naur)改进与完善过的巴克斯范式,实际上绝大多数又是经瑞士著名的计算机科学家沃思(N. Wirth)扩充过的巴克斯-诺尔范式,即EBNF(Extended BNF)。沃思是1984年图灵奖获得者。
巴克斯范式的左部是一个非终结符,非终结符用尖括号括起。右部是由非终结符和终结符组成的一个任意符号串。具有相同左部的产生规则可以共用一个左部,各右部之间以竖直线“|”分开。例如定义“标识符”的一组BNF公式为:
<标识符>::= <字母>| <标识符> <字母>|<标识符><数字>
<字母>::=a|b|c|…|x|y|z
<数字>::=0|1|2|3|…|8|9
我们目前常用的高级程序设计语言都是所谓冯.诺伊曼型的语言,也就是而向过程的语言,是以“逐词逐句”的方式工作的。巴克斯后来致力于开发非冯.诺伊曼型的语言,也就是函数式语言 (functional language)。这种语言的主要成分是原始函数、函数型和定义函数。程序就是函数,程序作用在结构型数据上,产生结构型结果。用这种语言编写的程序结构清晰,便于使用代数方法研究程序的特性。巴克斯后来推出了一种名为FP的函数式程序设计系统成为函数式语言的典型代表。此外,巴克斯也是归约机(reduction machine)这一不同于冯.诺伊曼的新的计算机体系结构的首创者。1972年,巴克斯在其为IBM公司的所撰写的研究报告“归约语言及无变元的程序设计”(Reduction Languages and Variable Free Programming)一文中最早提出了归约的概念。归约的基本思想是在函数的计算过程中通过替换不停地修改计算目标,直到被计算的目标已经是最小单元为止。这种方式不再具有变元的概念,所有的目标均是通过计算获得的。这一过程与纯函数的递归计算过程的代入方法相接近,因而可以把对归约机的研究与函数式程序设计语言的研究结合在一起,归约机的结构中一般包括递归机构和替换机构,归约方式则分串归约和图归约两种,前者实现按值调用,后者实现按引用调用。在巴克斯论文发表以后,一批学者致力于归约机的研究与开发,相继推出了GMD(Berklin,1975)、Callular(北卡罗莱纳大学Mago,1979)、AMPS(R. M. Keller,1979)、 ALICE(J. Darlington, 1981)等一批各种类型的归纳机。其中以树结构的Cellular最引人注意。
巴克斯由于以上介绍的一系列重大成就而获得许多荣誉和奖励。除图灵奖外,1967年他获得IEEE的W. W. McDowell奖;1975年被授予美国全国科学奖章(National Medal of Science);1994年美国工程院授予他Charles Stark Draper奖。巴克斯是美国科学院院士,也是美国工程院院士。
巴克斯是在1977年10月17日于西雅图举行的ACM年会上接受图灵奖的。ACM评奖委员会主席萨梅特(J. E.Sammet)致词并授奖,巴克斯发表了演说,题为“程序设计能从冯.伊曼形式中解脱出来吗?函数式风格及其程序的代数”(Can Programming be Literated from the von Neumann Style? A Functional Style and Its Algebra of Programs),对他所开发的FP及其意义作了详细的介绍。演说全文刊载于Communications of ACM,1978年8月,613-641页,也可见《前20年的ACM图灵奖演说集》(ACM Turing Award Lectures——The First 20Years:1966-1985,ACM Pr.),63-130页。
巴克斯已于1991年退休。更多精彩文章及讨论,请光临枫下论坛 rolia.net