把编程变成更易表达的工作
约翰·巴科斯(John Backus)长期在IBM从事编程系统研究。1950年,他获得哥伦比亚大学数学硕士学位后加入IBM,早期工作涉及SSEC计算机,随后参与Speedcode与FORTRAN等系统。他于1963年成为IBM院士,1991年退休,2007年去世。
巴科斯关心的不只是让机器运行,而是减少人把问题翻译成机器指令的负担。FORTRAN面向科学计算中的公式、数组和重复运算,后来关于语言描述及函数式程序的工作,则从不同层次探索怎样清楚表达计算。这些成果有个人倡议,也有团队设计、实现及国际委员会合作,并非一个人独自创造了现代编程。
参考:[1]
FORTRAN的关键不仅是公式
1957年的团队论文将FORTRAN项目的开始记为1954年夏季,目标是在IBM 704上把接近数学表达的程序自动翻译为高效机器代码。困难不只是读懂公式:如果翻译结果远慢于手工代码,昂贵的机器时间可能抵消编程便利。编译优化因此是系统能否被采用的核心问题。
原论文举例说明,编译器可避免重复计算同一子表达式,并把平方运算实现为乘法。它还分析循环、控制流和索引寄存器使用。论文分别标出Lois Haibt负责的流分析和Sheldon Best负责的后续寄存器处理,将虚拟的索引需求映射到704的三个实际索引寄存器。巴科斯领导这项工作,但算法实现来自多位成员;论文的多作者署名正反映了这种分工。
参考:[2]
BNF描述语法,不代替编译器
巴科斯参与ALGOL 58和ALGOL 60的国际合作,并于1959年提出用于语言描述的形式记法。后来通称的巴科斯—诺尔范式(BNF),同时承认彼得·诺尔对记法的进一步贡献。它以规则说明一种语法成分可由哪些符号或其他成分组成,递归规则能够紧凑地描述长度不固定的表达式。
ALGOL 60修订报告由诺尔编辑,巴科斯与多位研究者共同署名。报告解释了元语言变量、定义符号和表示选择的竖线,并另行说明语言语义。由此可见,描述什么样的符号串合乎语法,与说明程序如何执行、如何生成高效代码,是相关却不同的任务;BNF名称也不是把整个形式语言理论归为个人成果的依据。
以函数组合探索程序代数
巴科斯获得1977年图灵奖,其获奖演讲整理成论文于1978年发表。论文批评传统语言过度围绕逐字处理和存储状态变化组织程序,提出以组合形式从已有函数构造更高层程序,并研究相应的代数规律。关注点不再只是怎样把原有程序编译得更快,还包括程序本身是否适合推理和变换。
这种函数级表达把程序作为可组合、可通过等式研究的对象,而不是一长串赋值步骤。巴科斯给出的FP系统是这条研究路线的具体方案,不代表全部函数式语言,也没有取消早于它的相关思想。把FORTRAN、BNF与FP并列考察,才能看出他分别在实现效率、语言定义和计算表达上提出的问题。
参考:[4]