现在我们很难想象，曾经有段时间，在编程中使用递归的实用性甚至是可能性是受到怀疑的。然而，这种现象在1960年左右的编程社区中是真实的。创造了Algol 60的委员会也甚至在这个问题上存在分歧。递归如何进入编程语言是一个阴谋和误解的故事。当我读Gauthier van den Hove的优秀硕士论文[11]时，我第一次知道了这个故事。这也是[12]中第3章的主题。
在20世纪50年代末，成立了一个委员会，他们致力于设计一种通用的、与机器无关的编程语言。在当时，这样一种语言并不是多余的奢侈品：程序员们使用的编程系统由硬件制造商提供，这些编程系统甚至没有在不同的模型间进行统一。Fortran语言是第一个例外，但它在当时仍然依赖于单一制造商。Lisp语言预示这某些事情的到来：与机器无关且不依赖于制造商。这就是Algol想要做的，但后来有更多的官方介入：在联合国教科文组织的主持下成立的IFIP（国际信息处理联合会）资助了Algol。
McCarthy刚刚从他的Lisp项目中获得成功，他热衷于将递归作为一种优雅的方式让计算机做它们最擅长的事：每次重复代码并做适当的修改。事实上，在最开始的Lisp语言中没有迭代，因此添加线性表中所有元素的唯一方法是写一个递归定义的函数。作为Algol 委员会的成员，McCarthy提出让递归成为新语言的一个特征的可能性。这个提案被更紧迫的问题所排挤。结果在1960年的前几个月，当报告最终敲定时，大家在递归问题上并没有达成共识。
这里有充足的理由来反对。目前还不清楚它是否能实现：该委员会中的德国派认为，像Lisp解释器这样古怪的实验研究对于可靠、高效的编译器而言，并不是一个鼓舞人心的例子。但委员会成员Naur和van Wijngaarden赞同McCarthy的观点，他们认为递归是一个太诱人的机会，不容错过。Van Wijngaarden一直怂恿他的搭档Edsger W. Dijkstra，谁赞成递归，谁就可能给他们提供新的、尚未发表的实现递归的想法。
Naur是编辑Algol报告最终版本的委员会成员。二十年后，Naur想起它来，如下[1]：
编程语言概念的最后一个重大的变化是允许递归程序激活。这如下发生。 [...] 大约在2月10日， [...] 我接到了A. van Wijngaarden的电话，通话的人同时还有E.W. Dijkstra。他们指出在报告草案中缺少一个重要的定义，即程序标识符在声明中出现的意义不同于它出现在赋值语句的左边部分。他们还明确表示，通过描述的规则防止递归激活会使情况变得复杂，因为递归有可能通过程序及其参数间接激活。他们建议在5.4.4节增加一个句子来澄清此事：“在程序中任何其他程序标识符的出现都表示程序的激活”。尽管考虑到这个问题随后带来麻烦的风险，我被这个建议的大胆和简单所迷住，并决定这样做。
结果发现在这个问题上确实存在麻烦。一些委员会成员已经被骗批准这个最终版本的报告，报告中包含一个后期加入的容易被忽略的内容，这在与委员们期望相反的方向上试图解决争论。委员会成员F.L. Bauer通过将语言中增加的递归视为“阿姆斯特丹阴谋”[1, 附录5]来表明自己的抗议。
Dijkstra在2001年接受采访时明确表明，这不是Bauer部分的偏执[2]：
递归是很重要的一步。它偷偷摸摸的被介绍。ALGOL-60报告草案在十二月最后一周被发布。我们研究它，并意识到递归调用虽然没有被说明，但已被允许。我打电话给Peter Naur—打到哥本哈根是我的第一个国际电话，我永远不会忘记这种兴奋！—并给他口头提供了一个建议，而他在报告中包含了这个建议。这个建议是这样的，“在程序中任何其他程序标识符的出现都表示程序的激活。”基本上就是这个情况。这个句子被暗中插入。并且所有人，包括没有看到这句话的人，可以说都不得不同意这个报告。这就是递归是如何被明确列入的过程。
但是，是什么原因Bauer没有实现而Dijkstra实现了递归？事实上，“递归”意味着什么呢？仔细看看Naur和Dijkstra对上述的说明，结果显示Naur说“递归程序激活”，这是一个运行时的概念；而Dijkstra说“递归”，这可以解释为源程序的属性。
这里有一些澄清“递归”含义的尝试。
- 它有可能在执行一个程序时被调用，这使得存在一个先前调用的激活记录。
- 可能通过调用被命名为形式参数的程序，直接或间接地调用自身。
- 间接通过调用未命名形式参数的程序，直接或间接地调用自身。
Naur想的是第一个含义，而Dijkstra想到的可能是第二个含义。
当Algol委员会中的Bauer派发现他们是阿姆斯特丹阴谋的受害者时，删除有问题的句子，这似乎是定义他们的首选版Algol的一件简单事情。他们发现这并不能消除递归。至少根据第一个含义不是递归。而这正是他们想要去掉的，因为他们希望静态分配程序的激活记录。
公布的Algol-60报告通过一些努力重新定义语言：SMALGOL [3], ECMA子集 [4], 和SUBSET Algol [5]。这些人基于他们的期望而联合，共同禁止那些需要动态分配程序激活记录的方案。所有这三种语言都一致删除了Algol-60报告5.4.4节中的最后一句。他们一致认为，对于消除递归这是不够的，在这个方向上他们进行了不同的尝试。例如，在Algol-60报告中最后添加了4.7.5.6节：
不调用程序本身，在执行任何程序中的语句和给实参赋值期间，可能发生通过名字调用相应形参的情况。在表达式赋值的期间，这也会发生在程序内部声明中。
据我所知，Algol-60报告中没有这句话。但定义子集的人像我一样为他们提供了一个替代的表达：
不要写递归程序。不要使用递归程序。
正如Dijkstra已经预见到的，他们应该加入：
不要尝试对程序的参数做任何偷偷摸摸的事情。
这样Algol 60失去了它的一大成就：对实施者和使用者而言的一个单一文件。
对递归而言的一种有效治疗是消除嵌套程序声明并要求程序在第一次调用前声明。我们看看这个，例如在C中，它已经被描述为“荣耀的汇编语言”，更重要的是被Bauer派视为注重效率的典范成果。具有讽刺意味的是，这个效率典范的设计者认为在动态分配程序激活记录或允许程序调用自身两个方面都没有问题。无需修改，在调用前声明的要求将消除相互递归的可能性。因为这不会带来动态激活记录的问题，Ritchie放宽了之前使用定义的规则，允许程序头部的冗余声明。以冗余的预先声明为代价，程序员能在C中定义相互递归的程序。
当然，我们不能责备Bauer派，因为后来的人没有在这个领域的经验。有趣的是，在1960年确实存在知识表明，当有人想要有吸引力的Algol程序机制时，避免动态分配的需要是多么困难。这个程序机制与20世纪30年代以来众所周知的lambda演算类似。根据当前的标准，Algol-60报告是一个及其紧凑的文件。但与lambda演算的定义相比，它有些相形见拙。例如，在[6]中，lambda演算被定义86行，分布在10个定义中。很明显，在这个紧凑的定义中，lambda演算不允许递归函数的定义。然而在1935年，lambda演算的表达至少已经发现有两个版本的Y组合子。而这个组合子使得递归函数可能在lambda 演算中定义。
一旦有人有一个简单而通用的函数定义机制时，对于避免递归是多么困难，lambda演算是另一个例子。同样，我们不能责备Bauer派不知道这些事情。事实上，直到20世纪60年代，出版了如[7]这样的书籍，使用递归的Y组合子才变得家喻户晓。
这是一个安全的假设，阿姆斯特丹阴谋的肇事者并不知道。那为什么他们如此肯定他们是在正确的道路上呢？我们知道，就其中的一个策划者E.W. Dijkstra而言，他在1961年10月出版了数学中心的报告MR34“与机器无关的编程语言的设计”。在这篇报告中，Dijkstra当时考虑到相关性，提出了语言设计的一般原则，在我看来，今天仍然适用。一个安全的假设是，在一年之前，他已经确信这些原则。这些原则的普遍性使他有可能运用知识实现Y组合子，并随后获得有效实现动态分配程序激活记录的经验。
在被引用最多的一篇论文中， F.P. Brooks [9]将有着狂热追随者的编程系统或语言与一系列无聊却尽管可能有用，但没有狂热追随者的项目进行对比。他指出，前者是由个人创建的，后者是由委员会创建的。他的言外之意是委员会设计的东西一定要归到无聊的类别下。为了概念上的完整性，Brooks指明了区分的标准。因为委员会设计的东西一般被认为必定没有概念上的完整性，Brooks将Algol 60放在后一类中。
通过Dijkstra，我从第二种观点中走出来，并发现这一点[10, 第4页]：
然后60年代与一个绝对的奇迹，即ALGOL 60，一起开始。这是一个奇迹，因为，一方面这种编程语言已经被一个委员会设计出来，而另一方面它的优点是那样的突出，在回顾中，它已经被认为是“大多数继承者中的一个重大的进步”(C. A. R. Hoare)。
奇迹是怎样发生的？对于Algol委员会这样一个拥有各种成员的委员会而言，它引人注目地超越理想状态，然后撰写出简明、完整的文档，并在概念的完整性上描述了一门语言，其优点得到Brooks的高度赞赏。这一切怎么可能呢？
答案是这有一个酝酿期，我估计它开始于1955年10月在达姆施塔特举办的自动计算国际研讨会。几位发言者提出需要一种通用的、与机器无关的算法语言。委员会的第一个继承者开始做这项工作。他在美国接触并寻找志同道合的人。这是一个欧洲/美国的联合委员会，他们在苏黎世会面，并商定这样的语言标准。他们的文档制作得足够详细，以便该语言标准值得被称为Algol 58。
这个报告的公布引起了语言进一步发展的兴趣。Peter Naur是加入Algol委员会的新成员之一。Algol 58是需要进一步发展的。许多新的想法被提出来。在一些方面，委员会超前的超越了现有最先进的理念和他们自己的理解力。
同时，委员会陷入困境。尽管Naur是新成员，他看到了结构化讨论方式的需求，并创建了Algol会刊。他开始以语言定义的形式统一成果。他为了语法定义研究了Backus的形式主义，并将其应用在新语言不堪重负的语法清单上。为了赶上在1960年1月巴黎举办的最终设计会议上上交报告，他及时准备好了它。他没有时间来准备政治。
Bauer1978年的回忆[1, 第41页]:
… 解释了巴黎ALGOL-60会议上一个奇怪的事件 … 在巴黎会议的开始，Peter Naur交给他们一份他的18页的报告草案，这让他们很惊讶。Peter Naur并没有被委托做这件事，这是一个既成事实。因此，如果他写的这个报告草案被“选”为讨论的基础，这听起来充满诗意；而在Peter Naur已经获得这种优势之后，该委员会只是被迫这么做。同样，他自动成为了编辑；这只是一个邀请他的礼貌问题。由于有一些担心，他会利用这个位置在语言上发挥他自己的一些影响力（发生的事情的确如此，正如他表示的），这种发展被一些委员会成员认为是非常不健康的。
换句话说，一些委员会成员真的生气了。在接下来的一页：
但是，应当提到，不仅委员会成员之中存在怀疑态度，而且当编辑随意修改会议的结果时，成员们无奈地表示没有谁可以做些什么。为了忠诚度，他被吞噬了。
然而，Bauer写道：
在另一方面，尽管六天巴黎会议的时间进度非常紧迫，这样的情况对获得报告完成的草稿有一定的帮助。
这就解释了奇迹：在经过了Algol计划的创造、探索和挣扎阶段后，新人出现了并接管了它。前辈隐约意识到，那个人拯救了这个计划，但他曾经受到伤害。Bauer可能永远不会原谅Naur；尽管上述引用写于1978年，在事情发生之后很久。对我而言，他们表明在某种程度上，Algol 60这个“奇迹”是Naur创造的。
致谢
直到最近我才意识到在递归和同一程序的多条激活记录的可能性之间的区别。同样，我认为Peter Naur只是Algol委员会中的一个成员，而他恰好正是个编辑。只是因为Gauthier van den Hove好心的给我看了一些他的研究成果，我才了解到这里有引人入胜的故事。van den Hove先生最近发表了他的文章http://www.fibonacci.org/GHE7.3.pdf。非常感谢Paul McJones在一些方面的帮助。
参考文献
[1] “The European Side of the Last Phase of the Development of Algol 60″ by P. Naur; page 3. ACM SIGPLAN Notices 13(8), pp. 13– 44 (1978)
[2] Oral History interview conducted by Philip L. Frana on August 2, 2001, Austin, Texas. OH 330, Charles Babbage Institute, University of Minneapolis.
[3] “Smalgol-61″, G.A. Bachelor, J.R.H. Dempster, D.E. Knuth, and J. Speroni, eds. Comm. ACM 4(11), pp. 499–502 (1961).
[4] “ECMA subset of Algol 60″ Comm. ACM 6(10), pp. 595–597 (1963).
[5] “Report on SUBSET Algol 60″ Comm. ACM 7(10), pp. 626–628 (1964).
[6] Introduction to Combinators and Lambda Calculus by G.R. Hindley and J.P. Seldin. Cambridge University Press, 1986.
[7] Denotational Semantics by Joseph Stoy.
[8] also Annual Review in Automatic Programming vol.3, Richard Goodman, ed., pp 27 — 42, Pergamon Press 1963.
[9] “No Silver Bullet: Essence and Accidents of Software Engineering” by F.P. Brooks. Computer, 20 (4), pp. 10–19 (1987).
[10] “Computing Science: Achievements and Challenges” by E.W. Dijkstra. ACM SIGAPP Applied Computing Review 7 (2), pp. 2–9, 1999.
[11] Edsger Wybe Dijkstra: First Years in Computing Science (1951–1968) by Gauthier van den Hove. MSc thesis, University of Namur, 2009.
[12] The Dawn of Software Engineering: from Turing to Dijkstra by Edgar Daylight. Lonely Scholar, 2012.
相关文章
递归是如何进入编程的？，首发于博客 - 伯乐在线。