英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

算法系统的综合

阿兰·J·珀利斯

卡内基理工学院

匹兹堡，宾夕法尼亚

引论

知识和智慧两者都扩展了人类的触及范围。知识导致了计算机，而智慧导致了筷子。遗憾的是，我们的协会过度地陷入前者，后者将需要等候更庄严的一天。

图灵的名望基于什么，而且这一名望将继续存在吗？他证明了一个定理，即对于一个一般的计算装置——后来称为图灵机——是否存在它不能计算的函数？我对此持怀疑态度。更为可能的是，它是基于他所发明和应用的模型的，即他的形式化机制。

这个模型已经引发了想像力，也引发了一代科学家的思索，他证明了导致这些理论的论证基础，他的模型已证明是如此有用，它生成的活动不仅在数学中分布，而且还传遍了很多技术部门。所采用的论证不总是形式化的，而且随之而来的建树不总是抽象的。确实，图灵机最丰硕的成果是可计算函数，即在计算和程序设计下可计算的函数的创建、研究以及计算。这并不奇怪，因为计算机所能计算的比我们还不知道如何确定的要多得多。

我确信，我们大家都同意，这个模型极有价值。历史将会饶恕我没有在我的这个演讲中去使人们注意图灵对于通用数字计算机的发展所做出的影响。数字计算机已经进一步加速了我们对计算理论和实践的涉入。

当然，由于图灵模型的出现，从而导致一些人开始关心计算机问题并使我们从他们的研究中获益。然而，我想只有一样东西能有和图灵的东西同样巨大的影响，这就是称为ALG0L的形式机制。许多人会立即表示反对，并指出我们中知道它和使用它的人太少了。虽然令人不快的情况曾经是这样，但问题并不在于此。ALGOL对于计算机科学研究发展的刺激是要紧的，而拥护者的数目无关紧要。ALGOL还激发我们的思维并且为我们提供论证的基础。

长期以来，我一直捉摸不透，为什么ALGOL是我们领域中这样一个有用的模型。也许各种原因是：

(a) 它的国际上的支持；

(b) 其语法在印刷中的描述的清晰性；

(c) 它把汇编和子程序程序设计的重要程序设计特征组合在一起的自然方式；

(d) 语言可自然地分解这一事实，使得人们可能会建议并且定义稍微广泛地对语言的一些部分修改，而不破坏其结构和记号的令人印象深刻的和谐性。短语“类似ALGOL”是有应予承认的意义的。它经常用于程序设计、语言学计算的论证中。ALGOL看起来是一个可持久的模型，甚至在手术之下仍然繁荣昌盛——因为它是可探索的、有弹性的或者是可截肢的；

( e) 事实上，它不适合于我们希望来编程的许多任务。

有一件事我是确信的，那就是ALG0L并不把它的魅力归功于它诞生的过程，即通过委员会起草。最近，当阐明对ALGOL的令人印象深刻的改进的同时，仅仅带来来自我们集体想像的一个缺陷。这些可能是对于ALG0L的改进，但它们作为模型并不成功。

自然地，我们应当进行和做出利用他们所提供的改进来纠正ALGOL的弱点，也应当想想为什么它们不能刺激我们创造性的能源。我们应当问为什么计算机科学的研究，乃至计算机的实践、工作，没有在它们的影响下大踏步前进？我不会装着我知道整个答案。但是我深信，它们的痴呆性的一个重要部分来自于我们专注于 ALGOL 的错误弱点上。

语言和数据结构的综合

我们知道，设计一种语言的目的是，用于简化通过重要的一类问题建立起来的无数个算法的表达问题。这个设计只有在经过某些改进后，在计算机上运行段时间后以及使用现存语言的程序员花费了相当数量的编制时间之后，当施加或者有可能施加对于这类问题的算法之后，才应当被实施。而后这种语言必须减少一组事务处理的费用来支付它的设计、维护和改进的费用。

后继的语言来自于各种各样的过程：

(a)对于在一种语言中的错误、疏忽或过剩东西的改正，揭示了一个自然的重新设计，它产生一种优良的语言。

(b)对于在一种语言中的错误、疏忽或过剩东西的改正,要求重新设计一种有用的语言。

(c) 由任何两种现存的语言通常可以建立起第三种语言，它(i)仍以集成的形式包含来自两者的设施，以及(ii)要求一个与集合的方法以及两者的评价规划相比不那么复杂的方法和评价规则。

有了上述想法，那么从何处开始综合一个后继模型，它将不仅通过机器来改进商业，而且还将把我们的注意力集中在计算本身的重要问题上面呢？

我相信，自然的出发点必须是对数据的组织和分类。这就是说，最低程度，如果不知道它的数据的本性，要建立一个算法是困难的。当我们试图以一种程序设计语言来表示一个算法时，在可以指望来做一个有用的计算之前，必须知道在该语言中算法对于数据的表示。

由于我们的后继语言是一个通用的程序设计语言，它应具有通用的数据结构。依赖于你是如何来考查这个问题的，它既不比你可能想像的更难也不更容易。这个东西应当如何来安排呢？让我们看看在已有的语言中我们做了些什么。其方法如下：

(a) 一些“原始”的数据结构，例如整数、实数、在类型上同簇的数组、表、串和文件，被定义到语言中。

(b) 在这些结构上，提供了一个“充分”的运算集合。例如算术的、逻辑的、摘取的、赋值的和组合的运算。

(c) 任何其他的数据结构都被认为是非原始的，因而必须借助于原始的形式来表示。在非原始的结构中，固有的组织由在原始数据上的运算明确地提供，例如通过实数算术运算来表达一个复数的实部和虚部之间的关系。

(d) 这些非原始数据结构的“充分”的运算集合被组织成为过程。

这个扩充过程不可以出错，每种程序设计语言必须允许它方便地使用，因为最终这总是被要求的。然而，如果这个扩充过程使用得太广泛，那么算法经常不能显示它们实际上具有的结构的清晰性。更糟的是，它们的执行就趋向于比需要的还慢。前一种弱点是由于对于这个算法而言，语言的设计是以错误方式进行的。后者的存在是由于在数据上的过分组织以及在执行期间要求管理，而它本可在算法执行之前就完成了。在两种情况下，变量都已由语法和计算规则在错误的时间中做了约束。

我想，大家都知道，我们的语言还没有足够的数据类型。可以肯定地说，在我们的后继模型中，不应当通过添加多一些例如有限分数的新类型和通用的“聚宝箱”结构来修补这个缺点。

在定义函数时的经验应当已经使我们知道该做什么：不要在通用的层次上来专注于完整的定义函数的集合，而应该在这种语言内提供结构，并提供在其有效的定义中以及在程序内使用函数时将遵循的控制。

因此，在后继模型中，应把注意力集中在提供定义数据结构的手段上。但仅这一点本身是不足够的。相伴随的运算的“充分”集合，在为之而描述数据结构的程序中， 还必须给出这些运算出现的上下文以及它们的计算规则。

对于数据结构必须提供的一些能力的清单将包括：

(a) 结构的定义；

(b) 把一个结构赋值给一个标识符，即给标识符以信息单元；

(c) 给定结构后，对于一些部分的命名规则；

(d) 对于附加到一个标识符的一些单元的赋值；

(e) 访问标识符所附属的单元的规则；

(f) 组合、复写和删除结构以及单元内容的规则。

在大多数语言中，现在肯定已经以有限的形式提供了这些能力，但是在它们的语法和计算规则内通常是以过于固定的方式来提供的。

我们知道，一种语言的设计者不可能把将驻留于结构中的信息量以及结构内所实施的数据量固定下来。必须允许每个程序自然选择来实现时间和存储之间的一个合意的平衡。我们知道，不存在表示数组或表结构，或串或文件或它们的组合的惟一方式。选择依赖于：

(a) 存取的频率；

(b) 结构变化中嵌入给定数据的频率，即把新记录结构附加到一个文件中或对数组设边界的频率；

(c) 在计算机存储要求中不必要的大块的费用；

(d) 在存取数据中不必要的时间的费用；

(e) 一个能有序增长的算法表示的重要性，使得结构的清晰性总是存在。

这些选择对于程序员来说是难以做出的，他们肯定不可能在设计层次中做出。

数据结构不可能凭空地创建出来。确实，我们习惯上使用的方法是使用具有固定原始数据结构的背景机器的方法。这些结构是通过实际计算机标识的那些，尽管就定义数据结构来说，背景机器可能是更抽象的。一旦选定了背景机器，由我们的定义所要求的额外结构就必须表示为数据，即作为一个结构的名称或指针。并非所有指针都访问同类型的结构，因为一个程序的段本身是结构，例如“(x)的过程标识符内容”这样的指针确立一类变量，这类变量的值都是过程名。

常数和变量

确实，一种语言的灵活性是由允许程序员在组成中或在执行中对它改变的程度来衡量的。语言中变化的系统发展在程序设计中是一个核心问题，因此在我们后继者的设计中也是核心问题。经验总是为我们提供从中可确立新变量定义的特殊情况。每个新经验都把我们的注意力集中在对于更大通用性的需要上。分时是我们的新经验之一，它有可能成为一个习惯。分时把我们的注意力集中到系统的管理上，以及由程序员在执行之前、执行之中和执行之后对文本的管理上。同程序的交互将逐渐变得更为灵活，因而我们的后继者不会使这难以实现。我们对会话程序设计的视野比快速围绕时间的转变以及方便的调试辅助包括更多：我们最感兴趣的程序决不会出错且决不是最终的。作为程序员，在希望提供会话式程序设计的一个适当模型之前，必须把新的程序设计同会话的程序设计分开。我坚持认为，新的要求是使语言中的变量成为以前当做固定的东西。现在我不指新的数据类，而是指其值是程序或程序的一部分、语法或语法的一部分以及控制方式的变量。

我们的大多数注意力都用在管理文件的系统发展上，它们改进了整个系统的管理。而在改进计算的管理方面的专注相对较少。前者可以在我们用来写程序的语言之外进行，而对于后者，必须在用来解决问题的程序设计语言内，改进对于可变化性的控制。

在一个程序的处理过程中，一段文本的出现可能是一次，但其执行可能多于一次。这导致了对标识出常量性和可变化性两者的需要。一般地使之具有变量的形式，而通过一个初始化过程使之成为常量，而且经常允许这个过程本身变成为受复制支配的。这个初始化过程是基本的，因而我们的后继者必须有处理它的方法性途径。

我们来考虑某些初始化的实例以及在 ALG0L 中的可变性：

1. 一个分程序的入口。在进入一个分程序入口时，声明进行初始化，但仅仅是对于标识符的某些性质。因此integer x初始化作为一个整数的性质，但不可能用来初始化在这个分程序范围内将改变的某些值。说明 procedure P( . . .);...;着重地初始化标识符P，但不可能在分程序中改变它。array A [l：n，1：m]被赋予一个初始化的结构，但不可能用来初始化其单元的值，或者用来改变附加到标识符A的结构。

(b) for语句。这些表达式，我将称它们为步进和直到成分不可能被初始化。

(c) 过程说明。这是过程标识符的初始化。在一个过程调用中，它的形式参数像过程标识符那样被初始化，而且它们甚至可以被初始化为值。然而，不同的调用建立对于形参标识符不同的初始化，而不是对于值的不同的初始化模式。

在ALGOL 中，曾经被认为，对于形式的约束和对于标识符值的约束允许的选择都是适当的。然而，如果我们考查对于形式赋值的运算、形式的计算以及初始化作为在一种语言中合理地确定的重要功能，就可以发现 ALGOL 是有局限性的，甚至在其可利用的选择方面是变幻莫测的。我们应当预期后继语言不会那样任意和有局限性。

举一个普通的例子。在for语句中，使用一个如value E的结构，其中E是一个表达式，作为一个步进成分，将表征表达式 E的初始化。value 是一类运算符，用以控制把值约束为一个形式。这个运算符的每一个应用附加有一个自然作用域。

我已经提到过，过程标识符通过说明而被初始化，于是把过程附加到标识符可以通过赋值而改变。我已提到借助于指针如何来实现这一点。当然，还有其他办法。最简单的办法是全然不改变标识符，而是有一个选择下标，它从一个集合中挑出一个过程来。初始化现在定义一个数组形式，例如，procedure array P[l:k] (,,...,) ; ... begin...end;begin...end ;调用P[J](,,...,)将选择第i个过程体来执行。或者，人们可以定义一个procedure switch P:= A,B,C，以及过程指定的表达式，使得上述调用将选择第Z个过程指定表达式来执行。上述方法对于某些应用来说过于静态，因此它们缺乏赋值的重要性质：即当一个赋值形式不再可存取时有能力来确定，使得它能另作别用；这种过程的一个可能应用，即被动态地赋值，是一个生成元。假设我们有一个过程，它用于计算(a)作为确定了整数N时某个函数(b)的一个近似值。现在一旦找到了，则仅仅对于不同的x值计算(a)感兴趣。于是我们可能希望来定义一个过程，它从(b)准备(a)。在其初始的执行中，这个过程或者对它本身赋值，或者对某个其他标识符赋值，计算(a)的过程赋值。随后对于该标识符的调用将仅仅产生这个生成的计算。这样一个动态赋值引起了一些有趣的可能性：

(a) 这个程序的某个存储可以作为第二个赋值的结果而被释放。

(b) 数据存储可以被赋值为其说明或定义被创建的过程标识符的own。

(c ) 初始调用能够修改得到的定义。例如，在初始调用中对于一个形式参数换名调用或赋值调用，都将影响所得到的定义的类型。

容易看出，我所论述的这一点对于对初始化，以及对于附加给标识符的形式和值的变化，是有必要附加统一方法的。这是计算过程的一个要求。因而，我们的后继语言对于指挥初始化的动作以及对于它的标识类的变化，必须具有一般的方法。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[428942]，资料为PDF文档或Word文档，PDF文档可免费转换为Word