图灵奖第一位获得者：艾伦•佩利——算法的综合
导读：艾伦·佩利(Alan J．Perlis 1922年4月1日－1990年2月7日)，ALGOL语言和计算机科学的“催生者”，由于在ALGOL语言的定义和扩充上所作出的重大贡献，以及在创始计算机科学教育，使计算机科学成为一门独立的学科上所发挥的巨大作用而成为首届图灵奖当之无愧的获得者。本文是他获图灵奖的时候的演讲。当时大多数程序设计还是使用编码纸和穿孔卡片进行的。
引论
知识和智慧两者都扩展了人类的触及范围。知识导致了计算机，而智慧导致了筷子。遗感的是，我们的协会过度地陷入前者，后者将需要等候更庄严的一天。
图灵的名望基于什么，而且这一名望将继续存在吗？他证明了一个定理，即对于一个一般的计算装置——后来称为图灵机一—是否存在它不能计算的函数？我对此持怀疑态度。更为可能的是，它是基于他所发明和应用的模型的，即他的形式化机制。
这个模型已经引发了想象力，也引发了一代科学家的思索，他证明了导致这些理论的论证基础，他的模型已证明是如此有用，它生成的活动不仅在数学中分布，而且还传遍了很多技术部门。所采用的论证不总是形式化的，而且随之而来的建树不总是抽象的。确实，图灵机最丰硕的成果是可计算函数，即在计算和程序设计下可计算的函数的创建、研究以及计算。这并不奇怪，因为计算机所能计算的比我们还不知道如何确定的要多得多。
我确信，我们大家都同意，这个模型极有价值。历史将会饶恕我没有在我的这个演讲中去使人们注意图灵对于通用数字计算机的发展所做出的影响。数字计算机已经进一步加速了我们对计算理论和实践的涉入。
当然，由于图灵模型的出现，从而导致一些人开始关心计算机问题并使我们从他们的研究中获益。然而，我想只有一样东西能有和图灵的东西同样巨大的影响，这就是称为ALGOL的形式机制。许多人会立即表示反对，并指出我们中知道它和使用它的人太少了。虽然令人不快的情况曾经是这样，但问题并不在于此。ALGOL对于计算机科学研究发展的刺激是要紧的，而拥护者的数目无关紧要。ALGOL还激发我们的思维并且为我们提供论证的基础。
长期以来，我一直捉摸不透，为什么ALGOL是我们领域中这样一个有用的模型。也许个中原因是：
(a)它的国际上的支持；
(b)其语法在印刷中的描述的清晰性；
(c)它把汇编和子程序程序设计的重要程序设计特征组合在一起的自然方式；
(d)语言可自然地分解这一事实，使得人们可能会建议并且定义稍微广泛地对语言的一些部分修改，而不破坏其结构和记号的令人印象深刻的和谐性。短语“类似ALGOL”是有应予承认的意义的。它经常用于程序设计、语言学计算的论证中。ALGOL看起来是一个可持久的模型，甚至在手术之下仍然繁荣昌盛——因为它是可探索的、有弹性的或者是可截肢的；
(e)事实上，它不适合于我们希望来编程的许多任务。
有一件事我是确信的，那就是ALGOL并不把它的魅力归功于它诞生的过程，即通过委员会起草。最近，当阐明对ALGOL的令人印象深刻的改进的同时，仅仅带来来自我们集体想象的一个缺陷。这些可能是对于ALGOL的改进，但它们作为模型并不成功。
自然地，我们应当进行和做出利用他们所提供的改进来纠正ALGOL的弱点，也应当想想为什么它们不能刺激我们创造性的能源。我们应当问为什么计算机科学的研究，乃至计算机的实践、工作，没有在它们的影响下大踏步前进？我不会装着我知道整个答案。但是我深信，它们的痴呆性的一个重要部分来自于我们专注于ALGOL的错误弱点上。
语言和数据结构的综合
我们知道，设计一种语言的目的是，用于简化通过重要的一类问题建立起来的无数个算法的表达问题。这个设计只有在经过某些改进后，在计算机上运行一段时间后，以及使用现存语言的程序员花费了相当数量的编制时间之后，当施加或者有可能施加对于这类问题的算法之后，才应当被实施。而后，这种语言必须减少一组事务处理的费用来支付它的设计、维护和改进的费用。
后继的语言来自于各种各样的过程：
(a)对于在一种语言中的错误、疏忽或过剩东西的改正，揭示了一个自然的重新设计，它产生一种优良的语言。
(b)对于在一种语言中的错误、疏忽或过剩东西的改正，要求重新设计种有用的语言。
(c)由任何两种现存的语言通常可以建立起第三种语言，它(i)仍以集成的形式包含来自两者的设施，以及（ⅱ）要求一个与集合的方法以及两者的评价规划相比不那么复杂的方法和评价规则。
有了上述想法，那么从何处开始综合一个后继模型，它将不仅通过机器来改进商业，而且还将把我们的注意力集中在计算本身的重要向题上面呢？
我相信，自然的出发点必须是对数据的组织和分类。这就是说，最低程度如果不知道它的数据的本性，要建立一个算法是困难的。当我们试图以一种程序设计语言来表示一个算法时，在可以指望来做一个有用的计算之前，必须知道在该语言中算法对于数据的表示。
由于我们的后继语言是一个通用的程序设计语言，它应具有通用的数据洁构。依赖于你是如何来考查这个问题的，它既不比你可能想象的更难也不容易。这个东西应当如何来安排呢？让我们看看在已有的语言中我们做了些什么。
其方法如下：
(a) 一些“原始”的数据结构，例如整数、实数、在类型上同簇的数组表、串和文件，被定义到语言中。
(b)在这些结构上，提供了一个“充分”的运算集合。例如算术的、逻辑的、摘取的、赋值的和组合的运算。
(c)任何其他的数据结构都被认为是非原始的，因而必须借助于原始的形式来表示。在非原始的结构中，固有的组织由在原始数据上的运算明确地提供，例如通过实数算术运算来表达一个复数的实部和虚部之间的关系。
(d)这些非原始数据结构的“充分”的运算集合被组织成为过程。
这个扩充过程不可以出错，每种程序设计语言必须允许它方便地使用，因为最终这总是被要求的。然而，如果这个扩充过程使用得太广泛，那么算法经常不能显示它们实际上具有的结构的清晰性。更糟的是，它们的执行就趋向于比需要的还慢。前一种弱点是由于对于这个算法而言，语言的设计是以错误方式进行的。后者的存在是由于在数据上的过分组织以及在执行期间要求管理，而它本可在算法执行之前就完成了。在两种情况下，变量都已由语法和计算规则在错误的时间中做了约束。
我想，大家都知道，我们的语言还没有足够的数据类型。可以肯定地说，在我们的后继模型中，不应当通过添加多一些例如有限分数的新类型和通用的“聚宝箱”结构来修补这个缺点。
在定义函数时的经验应当已经使我们知道该做什么：不要在通用的层次上来专注于完整的定义函数的集合，而应该在这种语言内提供结构，并提供在其有效的定义中以及在程序内使用函数时将遵循的控制。
因此，在后继模型中，应把注意力集中在提供定义数据结构的手段上。但仅这一点本身是不足够的。相伴随的运算的“充分”集合，在为之而描述数据结构的程序中，还必须给出这些运算出现的上下文以及它们的计算规则。
对于数据结构必须提供的一些能力的清单将包括：
(a)结构的定义；
(b)把一个结构赋值给一个标识符，即给标识符以信息单元；
()给定结构后，对于一些部分的命名规则；
(d)对于附加到一个标识符的一些单元的赋值；
(e)访问标识符所附属的单元的规则；
(f)组合、复写和删除结构以及单元内容的规则。
在大多数语言中，现在肯定已经以有限的形式提供了这些能力，但是在它们的语法和计算规则内通常是以过于固定的方式来提供的。
我们知道，一种语言的设计者不可能把将驻留于结构中的信息量以及结构内所实施的数据量固定下来。必须允许每个程序自然选择来实现时间和存储之间的一个合意的平衡。我们知道，不存在表示数组或表结构，或串或文件或它们的组合的唯一方式。选择依赖于：
(a)存取的频率；
(b)结构变化中嵌入给定数据的频率，即把新记录结构附加到一个文件中或对数组设边界的频率；
(c)在计算机存储要求中不必要的大块的费用：
(d)在存取数据中不必要的时间的费用；
(e)一个能有序增长的算法表示的重要性，使得结构的清晰性总是存在。
这些选择对于程序员来说是难以做出的，他们肯定不可能在设计层次中做出。
数据结构不可能凭空地创建出来。确实，我们习惯上使用的方法是使用具有固定原始数据结构的背景机器的方法。这些结构是通过实际计算机标识的那些，尽管就定义数据结构来说，背景机器可能是更抽象的。一旦选定了背景机器，由我们的定义所要求的额外结构就必须表示为数据，即作为一个结构的名称或指针。并非所有指针都访问同类型的结构，因为一个程序的段本身是结构，例如“(x)的过程标识符内容”这样的指针确立一类变量，这类变量的值都是过程名。
常数和变量
确实，一种语言的灵活性是由允许程序员在组成中或在执行中对它改变的程度来衡量的。语言中变化的系统发展在程序设计中是一个核心问题，因此在我们后继者的设计中也是核心问题。经验总是为我们提供从中可确立新变量定义的特殊情况。每个新经验都把我们的注意力集中在对于更大通用性的需要上。分时是我们的新经验之一，它有可能成为一个习惯。分时把我们的注意力集中到系统的管理上，以及由程序员在执行之前、执行之中和执行之后对文本的管理上。同程序的交互将逐渐变得更为灵活，因而我们的后继者不会使这难以实现。我们对会话程序设计的视野比快速围绕时间的转变以及方便的调试辅助包括更多：我们最感兴趣的程序决不会出错且决不是最终的，作为程序员，在希望提供会话式程序设计的一个适当模型之前，必须把新的程序设计同会话的程序设计分开。我坚持认为，新的要求是使语言中的变量成为以前当做固定的东西。现在我不指新的数据类，而是指其值是程序或程序的一部分、语法或语法的一部分以及控制方式的变量。
我们的大多数注意力都用在管理文件的系统发展上，它们改进了整个系统的管理。而在改进计算的管理方面的专注相对较少。前者可以在我们用来写程序的语言之外进行，而对于后者，必须在用来解决问题的程序设计语言内，改进对于可变化性的控制。
在一个程序的处理过程中，一段文本的出现可能是一次，但其执行可能多于一次。这导致了对标识出常量性和可变化性两者的需要。一般地使之具有变量的形式，而通过一个初始化过程使之成为常量，而且经常允许这个过程本身变成为受复制支配的。这个初始化过程是基本的，因而我们的后继者必须有处理它的方法性途径。
我们来考虑某些初始化的实例以及在ALGOL中的可变性：
(a)一个分程序的入口。在进入一个分程序入口时，声明进行初始化，但仅仅是对于标识符的某些性质。因此integer x初始化作为一个整数的性质，但不可能用来初始化在这个分程序范围内将改变的某些值。说明procedure P(·)；···；着重地初始化标识符P，但不可能在分程序中改变它。
Array A[1：n,1：m被赋予一个初始化的结构，但不可能用来初始化其单元的值，或者用来改变附加到标识符A的结构。
(b) for语句。这些表达式，我将称它们为步进和直到成分，不可能被初始化。
(c)过程说明。这是过程标识符的初始化。在一个过程调用中，它的形式参数像过程标识符那样被初始化，而且它们甚至可以被初始化为值。然而，不同的调用建立对于形参标识符不同的初始化，而不是对于值的不同的初始化模式。
在ALGOL中，曾经被认为，对于形式的约束和对于标识符值的约束允许的选择都是适当的。然而，如果我们考查对于形式赋值的运算、形式的计算以及初始化作为在一种语言中合理地确定的重要功能，就可以发现ALGOL是有局限性的，甚至在其可利用的选择方面是变幻莫测的。我们应当预期后继语言不会那样任意和有局限性。
举一个普通的例子。在for语句中，使用一个如value E的结构，其中E
是一个表达式，作为一个步进成分，将表征表达式E的初始化。Vaue是一类
运算符，用以控制把值约束为一个形式。这个运算符的每一个应用附加有一个
自然作用域。
我已经提到过，过程标识符通过说明而被初始化，于是把过程附加到标识符可以通过赋值而改变。我已提到借助于指针如何来实现这一点。当然，还有其他办法。最简单的办法是全然不改变标识符，而是有一个选择下标，它从一个集合中挑出一个过程来。初始化现在定义一个数组形式，例如，procedure array P[l:k](f1,f2,..,fi);…begin…end;…;begin…end；调用P[j](a1，a2，·…，aj)将选择第i个过程体来执行。或者，人们可以定义一个procedure switch p：=A，B，C，以及过程指定的表达式，使得上述调用将选择第讠个过程指定表达式来执行。上述方法对于某些应用来说过于静态，因此它们缺乏赋值的重要性质：即当一个赋值形式不再可存取时有能力来确定，使得它能另作别用；这种过程的一个可能应用，即被动态地赋值，是一个生成元。假设我们有一个过程，它用于计算(a)(N)作为确定了整数N时某个函数(b)fx)= )的一个近似值。现在一旦找到了 (N),则仅对于不同的x值计算(a)感兴趣。于是我们可能希望来定义一个过程，它从(b)准备(a)。在其初始的执行中，这个过程或者对它本身赋值，或者对某个其他标识符赋值，计算(a)的过程赋值。随后对于该标识符的调用将仅仅产生这个生成的计算。这样一个动态赋值引起了一些有趣的可能性：
(a)这个程序的某个存储可以作为第二个赋值的结果而被释放。
(b)数据存储可以被赋值为其说明或定义被创建的过程标识符的own。
(c)初始调用能够修改得到的定义。例如，在初始调用中对于一个形式参数换名调用或赋值调用，都将影响所得到的定义的类型。
容易看出，我所论述的这一点对于对初始化，以及对于附加给标识符的形式和值的变化，是有必要附加统一方法的。这是计算过程的一个要求。因而，我们的后继语言对于指挥初始化的动作以及对于它的标识类的变化，必须具有一般的方法。
在会话式程序设计语言中，我们希望实现的动作之一是能对数据值和正文进行系统的或有控制的修改，以便与调试中出现的非系统的修改相区别。这种动作的实现显然意味着正文的某些部分被理解为变量。我们再次通过说明、初始化和赋值实现这一点。因此，在一个分程序的头部，我们可以写声明
real x,s;
arithmetic expression t,u;
在伴随的正文中，s：=x+t;的出现使得算术表达式的值被赋给t：例如通过被加到x的值和把结果赋作为s的值。我们发现，t可以被输人和存储为一个形式。操作+仅在已经应用适当的转换函数之后才能完成，表达式的部分翻译是在经典的“翻译时间”完成的这个事实不应吓住我们。这恰好是以系统的方法来开始面对部分翻译的问题的时候。可以作为变量的正文的自然部分就是由语言的语法单位所标识的。
对于程序未经事先考虑的变化的安排会稍微困难一些。这里的主要问题是原始正文中要加以改变的部分的标识，以及实际上被计算的正文在翻译过程中如何找出它的对应部分。说起来容易，解释地执行原来的正文即可。但是只有通过处于翻译和解释之间的中间解，才能找到令人满意的费用的平衡。我将在下一部分中表达一个观点，当每个程序要求它时，它对实现这个平衡可能会提供某些启示。
数据结构和语法
尽管表结构和递归控制在我们的后继语言中将不起中心作用，但对于LISP却是起很大作用的。这种语言在程序员当中引起了争论，且经常出于同一特征而受到谴责和赞扬。在这里我只想说一点，和我所知道的其他语言相比，它的描述以更多的清晰性简洁地揭示出了语言定义的适当成分。LISP的描述不仅包括它的语法，还包括它的语法表示为语言的数据结构，而且也把环境数据结构表示为语言的数据结构。实际上该描述对后来的描述设置了障碍，但不是以任何基本的方式。从以前的描述中有可能给出对计算过程的描述，因为一个LISP程序使用一些原始函数。而对于其他语言，这个描述的完备性是可能的，但般不认为它是定义描述的一部分。
对ALGOL的考查表明，对于表示ALGOL的正文说来，它的数据结构是不适当的，至少不是以适合于语言的计算方案的描述方式。关于描述ALGOL程序的环境数据结构，它的不适当性，我们也可以给出同样的评述我们的后继语言实现适合于表示语法和环境的处理数据结构的平衡，我把这一点当成是关键性的，以便计算过程可以在语言中明确地表述。
为什么给出这样一个描述是重要的呢？是不是仅仅为了给语言附加“封闭性”的优雅性质，才使得自举可被组织？绝对不是。它是有能力进行会话或计算的程序设计系统的系统构造的关键。
程序设计语言具有语法和一组计算规则，通过把程序表示为计算规则可对之应用的数据而把它们联系起来。这个数据结构是内部的或针对语言语法的计算。为了人们的通信，我们以外部语法来编写程序。我们把该外部语法固定下来。一般假定内部语法与翻译程序及机器密切关，因而它在文献中从未被描述通常存在一个翻译过程，它把正文从一个外部语法表示转换成一个内部语法表示。实际上，内部描述中的变化与执行计算规则的机器相比，更为基本地同计算规则本身相关联。计算规则的选择以关键性方式同语言变量的约束时间相关。
这指出了在正文改变情况下有用地组织计算的方法。由于内部数据结构反映了被处理正文的可变化性，让翻译过程选择语法的适当内部表示，而且让一个通用的计算程序以选定的语法结构为基础选择特定的计算规则。因此，必须在外部语法中给出指出变量的提示。例如，arithmetic expression t；real u,v；以及语句u:=v/3*t;指出对于v/3和t的值不同内部语法的可能性。应当指出，t的特性非常像一个ALGOL的形式参数。然而，对于赋值的要求较少。我想，这仅仅指出，形式-实际的赋值同封闭的子程序的概念无关，而且它们已经以确定初始化的范围的方式在过程构造中被统一起来。
在事先未考虑到的变化情况下，内部语法结构的知识使得正文变化时，最少数量的重新翻译和计算规则的改变成为可能。
由于人们要在某种语言中完全考察和构造数据结构以及计算规则，因而它
在源语言本身中是合理的。人们可以把其字符串是在源语言允许的那些子集的
一个内部语法定义为翻译的目标。这样一个语法，如果选择为接近机器代码，
则可通过非常像一个机器的规则来计算。
虽然我已随便地谈了附加于语言的标识符的可变化性，但对于控制的变化性，我还什么都没说。实际上我们没有一个描述控制的方法，所以不能说明它的体制。应当期望我们的后继语言有像ALGOL那样多的控制类型，甚至还多些，并行操作是正在被研究的一类控制。另一种是刚刚在语言中出现的分布式控制。我将称之为监控。进程A连续地监控进程B，使得B达到一个状态时，A通过干扰来控制这个进程未来的活动。在A内的控制可以写为when P then S；P是在测试之下，在某个定义的范围内总是存在的一个谓词。每当P为真时，在监视之下的计算被中断，而且执行S。我们希望在一个动作已被执行且它可能使P为真时，通过测试P来机械化这个控制，反之却不然。因此我们在定义语言、环境以及计算规则时，包括了在执行期间可加以监控的状态。从这些原始状态开始，其他的东西可以通过程序设计来构造，通过这些原始状态的点知识，连接在可能点处的测试的安排甚至可以在定义一个程序中的谓词之前就完成了。那样，无须干扰程序本身，就能对程序查错。
语法的变化
在单个语言的范围内，可能会有惊人数量的变化性。而且经验告诉我们，变化的需要将对语言本身的变化施加逐渐增加的压力。设计者不可能预先处理这些变化的精确性质，因为它们是对于尚未解决的问题有待写出程序的结果。具有讽刺性的是，正是最有用和最成功的语言，最多地受到这个变化压力的支配。幸而，预期较早一类的改变是稍微可预测的。因此，在科学计算中，数的表示和算术是变化的，但表达式的性质不变，除非通过操作数和操作符而变
来自于这些源的语法中的改变十分容易处置。事实上，在语言中，算术表达式的语法和计算规则还未定义。取而代之的是，在语言中提供语法和计算规则，以便对算术表达式的定义进行程序设计，并且来设置这样的定义的作用域。
在这种持续一个晚上的语言游戏中，惟一的实际困难是计算规则的详细说明。它们必须小心给出。例如，在引进矩阵的算术运算中，矩阵表达式的求值应当小心使用临时存储单元而不要实施不必要的迭代。
在使用定义时所应用的一种自然技术以语言X开始，它将定义考虑为把语法扩大成语言X'的语法并且把计算规则给定为一个归约过程，这个过程把X'中的任何正文归约为X中等价的东西。
还应说明，语法的变化要求语法的一个表示，宜于作为X本身的一个数据结构。
结论
程序设计语言是围绕着变量来构造的—一它的运算、控制以及数据结构。由于这些概念对于所有程序设计都是共同的，因此通用语言必须专注于它们有序的发展。虽然我们归功于图灵的抽样模型，这个模型也专注于重要的概念，但我们应毫不犹豫地对更复杂的机器和数据进行运算。程序员决不应当满足于那样的语言，它允许他们对每一件事情进行程序设计，但却很容易编写毫无兴趣的东西。我们的进步是通过在有效性和通用性之间实现的平衡来测定的。由于涉及的计算变化——它确实在变——的本质，即语言变化的适当描述，我们的重点在转移。我感到，我们的后继者模型将显示这样的一个变化。计算机科学是一个不安定的婴儿，它的进步既在很大程度上依赖于观点的转变，也在很大程度上依赖于我们当前概念的有序发展。
这里介绍的概念无一是新的；但它们却往往被忘却。
我愿感谢协会为我提供第一个图灵奖演讲的特权。在结束这个演讲时有没有比说下列话更好的方式呢？即如果图灵今天在我们中间，那么他将在有不同的命名的演讲中阐述不同的观点。
版权声明
本文由苏运霖翻译，原书由ROBERT L. ASHENHURST著，版权属于原作者，仅用于学术分享