John Backus的函数式编程项目的历史 [草稿]

# John Backus 的 FP 语言历史 来源：https://softwarepreservation.computerhistory.org/FP/ 计算机历史博物馆软件保护小组 (https://softwarepreservation.computerhistory.org/) ## John Backus 函数式编程项目的历史 ## \*\*\*\*\* 草稿 \*\*\*\*\* Paul McJones paul@mcjones\.org https://mcjones.org/dustydecks/ 最后修改于 2026 年 7 月 18 日 ## 摘要 John Backus 从 1969 年之前开始探索一系列应用式、函数式和函数级语言，一直持续到 1991 年退休。本项目的目标是保存这项研究中幸存下来的材料，并将其置于背景中。非常感谢任何评论、建议以及额外材料的捐赠。 ## 目录 - 致谢 (https://softwarepreservation.computerhistory.org/FP/#acknowledgements) - 软件危机 (https://softwarepreservation.computerhistory.org/FP/#crisis) - 启动项目 (https://softwarepreservation.computerhistory.org/FP/#launch) - 另一位助手 (https://softwarepreservation.computerhistory.org/FP/#assistant) - 图灵讲座 (https://softwarepreservation.computerhistory.org/FP/#turing) - 完善代数 (https://softwarepreservation.computerhistory.org/FP/#algebra) - FL 团队 (https://softwarepreservation.computerhistory.org/FP/#FL) - 他人的实现 (https://softwarepreservation.computerhistory.org/FP/#impl) - 评估 (https://softwarepreservation.computerhistory.org/FP/#assess) - 参考文献 (https://softwarepreservation.computerhistory.org/FP/#refs) - 相关资源 (https://softwarepreservation.computerhistory.org/FP/#related_resources) ## 致谢 - John Backus 于 1974 年雇用了我，并在 2004 年给了我一些历史材料。 - Scott Baden 提供了他的 "DFT → FFT transformation in FP" 副本。 - Edoardo S. Biagioni 提供了他的 FPC 源代码以及关于 Gyula A. Magó 的 FFP 机器项目的信息。 - Dines Bjørner 提供了他与 John Backus 合作的信息。 - Will Partain 提供了关于 Gyula A. Magó 的信息。 - Barry Rosen 允许发布 [Rosen1974a (https://softwarepreservation.computerhistory.org/FP/#Rosen1974a),b (https://softwarepreservation.computerhistory.org/FP/#Rosen1974b)]。 ## 软件危机 在 1960 年代末，“软件危机”成为频繁讨论的话题。计算机在速度和内存容量方面变得强大得多，价格也降低了，但随着雄心增长，许多编程项目遭受成本超支、进度延误和可靠性差的问题。1968 年和 1969 年两次北约赞助的软件工程会议引起了人们对这些问题的关注，并作为讨论解决方案的初始论坛，解决方案包括形式化方法、设计方法论和管理技术。 尽管 John Backus 没有参加这些会议，但它们与他长期以来的愿望——简化编程任务——产生了共鸣。他在 Speedcoding 和 FORTRAN 项目中取得了早期成功。特别是 FORTRAN 彻底改变了面向数值编程的任务，在许多情况下，允许科学家和工程师编写的程序在性能上媲美甚至超过专业程序员——Backus 有时称他们为“祭司阶层”——编写的程序。在 FORTRAN 之后，他参与了 Algol 项目，并于 1963 年被任命为 IBM Fellow，这给了他选择任何问题的灵活性。然后他花了几年时间研究四色猜想 (https://en.wikipedia.org/wiki/Four_color_theorem)（现为定理）。但大约在 1967-1969 年间，Backus 决定再次尝试解决编程问题： > “我当时只是试图思考某种真正更高层次的编程，不像 Fortran 那么困难。问题是，函数式编程的想法，‘组合形式’之类的东西，来得相当容易。但试图让它成为一个真正完整的系统，能够处理所有其他你无法在该语言中表达的问题，就变得非常混乱和棘手。” [Booch2007 (https://softwarepreservation.computerhistory.org/FP/#Booch2007)] ## 启动项目 有几年，Backus 基本上是独自研究这个新想法。Ted Codd 与他短暂咨询过，但没有持续 [Booch2007]。1969 年末，Dines Bjørner 开始与他合作，首先解释了 lambda 演算和 Curry 的组合逻辑的细节，然后基于“有限状态树变换器”语义为 Backus 的语言（当时称为 RedSys）编写了一个解释器（用 PL/I）[Bjørner2025 (https://softwarepreservation.computerhistory.org/FP/#Bj%C3%B8rner2025),1972 (https://softwarepreservation.computerhistory.org/FP/#Bj%C3%B8rner1972)]。Bjørner 与 Backus 合作到 1972 年，然后分道扬镳；Bjørner 后来与 Ted Codd 合作 [Bjørner2025 (https://softwarepreservation.computerhistory.org/FP/#Bj%C3%B8rner2025)]，[BjørnerEtAl1973 (https://softwarepreservation.computerhistory.org/FP/#Bj%C3%B8rnerEtAl1973)]。 Backus 的第一篇出版物是 1972 年的研究报告，题为“Reduction languages and variable-free programming”；该报告感谢了 Bjørner “编写了一个减少 Red 项的程序，用于测试本文中的一些运算符。” [Backus1972a (https://softwarepreservation.computerhistory.org/FP/#Backus1972a)] 这份报告介绍了一系列面向表达式的语言，其语义由简单的重写规则给出。主打语言称为 Red（reduction 的缩写），大小与 Pure Lisp [McCarthy1960] 相似，但程序员不是通过描述对形式参数的影响来定义函数，而是从一组基本函数出发，使用函数组合运算符以及一组组合形式（此处称为‘修饰符’）来构建函数。每个函数接受一个（隐式）参数，该参数可以是一个序列。这导致了一种有些类似于 APL“单行程序”的编程风格，Backus 后来将 APL 视为灵感来源。在 1972 年期间，Phil Summers（当时可能还是耶鲁大学的研究生实习生，后来成为 IBM 研究员）用 Lisp 对 Red 进行了实验性实现 [Summers1972 (https://softwarepreservation.computerhistory.org/FP/#Summers1972)]。 这第一份报告对于 Red 的定位相当温和，他更多地将其视为一个形式系统，而非实用的编程语言。1973 年，他提交了一篇论文，并在第一届 ACM 编程语言原理会议上发表 [Backus1973a, c]。该论文完善了语言的层次结构，将一个整理过的 Red 版本作为核心，并得出结论：“希望这项工作能催生出一类新型编程语言的语义理论，这类语言具有简单到足以进行严格数学处理的公理基础。” 1973 年期间，Backus 进行了巡回演讲，在全国各地的大学和研究实验室举办了 14 场讲座 [Backus1973d (https://softwarepreservation.computerhistory.org/FP/#Backus1973d)]。他作为 IBM Fellow 的年度报告描述了当年在语言框架和 Red 语言上的工作，并提出了两个主张 [Backus1974a (https://softwarepreservation.computerhistory.org/FP/#Backus1974a)]： 1. “简单的、整体实体的编程语言，与传统的复杂的、逐字的编程语言相比，有潜力大幅降低编程成本。 2. 当前清理和扩展传统编程语言概念的努力没有这种潜力；……实际上，它们将继续增加语言的复杂性，而不解决逐字问题，就像过去 15 年一样，从而实际上增加编程成本及其所需的专业知识。（因此，PL/I 比 Fortran 复杂大约 10 倍，执行效率更低，而在表达能力上仅强 20-30%。）” 他总结道：“如果上述两个主张有任何真实性，那么研究部门应该自问，它是否已经陷入了一种舒适但错误的编程语言正统观念。我相信它应该重新评估在计算机科学和编程方面的重点和目标；至少 IBM 的计算机科学家应该意识到，降低编程成本比任何其他技术成就更能帮助 IBM 的增长。” 为了支持这些主张，他引入了“冯·诺伊曼瓶颈”这一说法——传统计算机逐字处理的本质——并认为这延续到了传统编程语言的设计中，导致了它们的低效和复杂性。 IBM 沃森研究中心自动编程小组经理 Patricia Goldberg 负责回应 Backus [Goldberg1974 (https://softwarepreservation.computerhistory.org/FP/#Goldberg1974)]。她同意降低编程成本的关键性、超越“PL/I 类型”语言的需求、APL 的重要性，以及在各个领域发现聚合操作的重要性。但她指出：“然而，我并不确信我们应该完全放弃显式存储和赋值操作符的概念。”她指出了 IBM 正在进行的非冯·诺伊曼框架的工作，以及将这些整合到有用编程系统中的尝试。Backus 回应时强烈重申，IBM 研究部门需要研究语言框架，目标是定义一个支持丰富定义的非常简单的框架 [Backus1974b (https://softwarepreservation.computerhistory.org/FP/#Backus1974b)]。 ## 另一位助手 尽管研究管理层的反应冷淡，Backus 还是坚持了下来。在他 1973 年的年度报告的“1974 年计划”部分，Backus 曾提到：“如果时间和助手允许，我希望开始研究 Red 语言的优化解释器。”他放出风声，有意招聘某人与其合作，而当时在 IBM 圣何塞研究所工作的 Jim Gray 知道我在寻找固定工作，便将我介绍给了 Backus。我曾于 1972 年在加州大学伯克利分校听过他的一场讲座，并注册了他的邮件列表，因此我收到并至少部分消化了他的两份研究报告。我还从事过 Snobol4 (https://www.mcjones.org/CAL_SNOBOL/) 和 APL (https://doi.ieeecomputersociety.org/10.1109/MAHC.2026.3652780) 的解释器工作。在接下来的大约 15 个月里，我与 Backus 合作改进语言并探索实现思路，包括用 Lisp 和一些实验性解释器，以及 Mcg——一种由 W. H. Burge 设计的类似于 ISWIM 的语言 [Burge1968 (https://softwarepreservation.computerhistory.org/FP/#Burge1968)]。我加入后不久，在部门内做了一个简短的报告 [McJones1974b (https://softwarepreservation.computerhistory.org/FP/#McJones1974b)]，并撰写了一份技术报告“A Church-Rosser Property of Closed Application Languages”[McJones1975 (https://softwarepreservation.computerhistory.org/FP/#McJones1975)]。在此期间，Backus 和我探索了 Red 语言的一系列微小变体——参见 [Backus1974b (https://softwarepreservation.computerhistory.org/FP/#Backus1974b)] 到 [Backus1975b (https://softwarepreservation.computerhistory.org/FP/#Backus1975b)]。程序代数（首次在 [Backus1974a] 中提及）和状态变换建模的工作也开始了。感觉到语言仍在变动，且重点更多放在形式化方法而非实际实现上，我最终转向了 System R (https://bitsavers.org/pdf/dec/tech_reports/SRC-TN-1997-018.pdf) 关系数据库项目。 \*\*\*\*\* 是否包含我的一些 Red 求值器？ 在此期间，一些大学的研究人员基于 Backus 的想法开始了项目。 Klaus Berkling 在德国 GMD 开始了基于归约机器的设计工作，该机器受 [Backus1973c (https://softwarepreservation.computerhistory.org/FP/#Backus1973c)] 的影响；据说这是第一个实际实现的归约机器 [Berkling1975 (https://softwarepreservation.computerhistory.org/FP/#Berkling1975)]，[Kluge1983 (https://softwarepreservation.computerhistory.org/FP/#Kluge1983)]。此外，北卡罗来纳大学的 Gyula A. Magó 启动了 FFPM 项目 [Magó1976 (https://softwarepreservation.computerhistory.org/FP/#Mag%C3%B31976)]。[Partain1989 (https://softwarepreservation.computerhistory.org/FP/#Partain1989)] 描述了这些以及其他的图归约机器。 ## 图灵讲座 John Backus 获得了 1977 年 ACM 图灵奖，以表彰他“为实用的高级编程系统设计做出了深刻、有影响且持久的贡献，特别是通过他在 FORTRAN 上的工作，以及在编程语言规范的形式化程序方面发表了开创性著作。”他的获奖演讲“Programming Can Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs”发表在《Communications of the ACM》上，所有 ACM 会员均收到 [Backus1978b (https://softwarepreservation.computerhistory.org/FP/#Backus1978b)]。他论证道： > “传统编程语言变得日益庞大，但并未变强。其最底层的内在缺陷使它们既臃肿又虚弱：它们继承了共同祖先——冯·诺伊曼计算机的原始逐字编程风格；语义与状态转换紧密耦合；将编程划分为表达式世界和语句世界；无法有效利用强大的组合形式从现有程序构建新程序；以及缺乏有用的数学属性来推理程序。” 他提出的替代方案是一种“非形式化的”函数式编程语言 FP（以及相关的“形式化”版本 FFP）、一个函数式程序代数，以及一个用于建模历史敏感系统的应用式状态转换（AST）框架。FP 包含一组用于处理数字、原子和序列的基本函数，以及一组用于从简单函数构造更复杂函数的组合形式。以下是一个矩阵乘法的示例函数： > **Def MM ≡ (ααIP) ○ (αdistl) ○ distr ○ [1st, trans ○ 2nd]** **○** 表示函数组合，而 **α** 将一个函数应用于序列的每个元素。**MM** 期望一对兼容的矩阵，每个矩阵表示为行序列。从右向左阅读，括号中的函数对第二个矩阵进行转置，同时保持第一个矩阵不变。**distr** 将转置后的第二个矩阵的副本与第一个矩阵的每一行配对。**αdistl** 将 **distl** 应用于每个这样的对，从而得到一个行对序列的序列。**ααIP** 将 **IP**（内积）应用于每个这样的对，从而生成所需的矩阵乘积。 注意只提到了函数，从未提及它们应用于的数据项（变量或常量）。（有一种组合形式用于从数据值创建常量值函数。）这后来被称为无点风格。Backus 认为这对 FP 的简洁性和强大功能贡献巨大。 Backus 指出的传统语言的问题之一是其复杂性以及由此导致的规范化和证明其属性方面的困难。相比之下，Backus 展示了一个用于 FP 的程序代数，可用于展示程序等价性，例如在将程序转换为更高效的形式时。该代数基于源自组合形式属性的恒等式，例如： **[f1, ..., fN] ○ g ≡ [f1 ○ g, ... fN ○ g]** **αf ○ [g1,**