战略规划对编程和重写中的缩减策略的影响

理论计算机科学电子笔记57（2001）网址：http://www.elsevier.nl/locate/entcs/volume57.html5页战略规划是一个可行的范式吗？PaulKlint1;2Centrum voor Wiskunde en Informatica（CWI）Kruislaan 413，1098 SJ Amsterdam荷兰摘要这篇关于编程和重写中的缩减策略研讨会（WRS'01）的讨论论文推测了主流编程和两个选定的应用领域中战略编程的可行性：定理证明和大规模编程。1引言从计算的早期开始，求值策略就在许多编程语言中扮演着重要的角色。在这篇讨论论文中，我将探讨“战略规划”的可行性，这是一种战略语言描述某些原子步骤必须执行的顺序的范式通常，策略语言包含像顺序组合、非确定性选择和重复这样的原语.原子步骤可以来自不同的范例，从单个重写步骤或函数到面向对象框架中的命令式语句或方法调用。将讨论以下问题：针对小型编程的编程语言评估策略取得了哪些成功，即，在单个组件的水平上构建程序？同样的问题，对于其他应用程序，如大型编程（即，由单个组件构建完整系统）和定理证明。对战略规划有何影响？1 邮箱：Paul.Klint@ cwi.nl2 http://www.cwi.nl/paulkc2001年由Elsevier Science B出版。V. CC BY-NC-ND许可下的开放访问。Klint22小程序设计2.1内心评价像汇编、Fortran和Cobol这样的史前语言都使用最内层（“渴望”）计算作为它们的执行模型。第一个提出与最内层求值略有偏差的通用语言是Algol 60Lisp的在Algol 60中，程序的按名称调用参数提供了与标准最内层求值顺序的偏差。在过程P的按值调用参数的情况下，实际参数的值只计算一次，并在P的主体的整个执行过程中使用。 注意，实际参数可以是复杂的表达式。在按名称调用的情况下，形式参数的值是通过在P中每次出现时计算实际参数表达式的值来确定的。 这很像最外层的评估。然而，由于在实际参数表达式中出现的变量可以在两次出现之间改变，因此连续的值不需要相同。Algol 60中按名调用的一个典型应用是连续计算不同参数值的表达式。这种技术，被称为詹森的设备，已被成功地用于数字应用。在Lisp中也存在类似的机制。一方面是引用的表达式（不应该被求值的程序片段），另一方面是显式的求值函数。通过结合这两种机制，可以实现非常复杂的评估命令。尽管按名呼叫是一种简单的机制，但它的分支在与命令式语言结合时，直到Algol60之后很久才变得清晰和Lisp的设计。 函数式语言中的包含更自然。2.2最外评价在更现代的时代，在光谱的另一端，像Haskell或Clean这样的函数式语言使用最外层（“懒惰”）评估作为执行模型。最外层求值的所声称的优点是表示nite数据结构的可能性（取n-nite列表的元素将仅检查前n个列表元素）和潜在的效率增益，因为不必要的计算将不被执行。一个众所周知的缺点是，在惰性语言中调试程序要困难得多，因为计算是以程序员不熟悉的顺序执行的。2.3回溯像SNOBOL 4这样的语言虽然不是主流，但在当时很流行，它有着截然不同的执行模型。它的应用领域是字符串处理，它的主要执行模型是模式导向执行。的Klint3模式匹配的执行基于回溯。SNOBOL 4模式提供了丰富的功能：原子操作，如匹配字符串或计算任意谓词。用于顺序组合、选择和重复的运算符。将匹配的子模式分配给变量的两种方法：立即分配（在匹配期间）和条件分配（在完全成功的匹配结束时）。立即和有条件地执行任意函数。在模式匹配过程中动态创建模式。人们可以用SNOBOL 4编写惊人的短程序来解决复杂的问题。另一种基于回溯的语言当然是Prolog。在纯Prolog中，回溯用于回答给定事实和规则集的查询。出于效率的原因，所有Prolog方言都包含一个cut操作符，可以用来引导回溯过程。当已知部分搜索空间不会产生答案时，可以使用cut运算符跳过该部分搜索空间。基于回溯的语言非常有表现力，但是程序中的控制权可能很难理解。有趣的是，这些基于回溯的执行模型已经被更有限的、声明性的机制所取代。在字符串匹配的情况下，基于解析器生成的声明性语法定义和实现已经接管。在逻辑编程的情况下，更多的控制范式正在尝试。2.4对战略规划的在实践中，只有基于最内部评价的评价模型才被使用。偏离内心评价的语言特征一直被认为是难易的。可能最成功的异常是if-then-else语句，它总是以最外层的方式进行计算。我们能从中学到什么？我至少有以下几点体会：最内部的求值是小规模编程中最自然的求值顺序。成 功的范例尽可能接近内心的评价。我只能推测为什么这些假设是正确的：程序设计语言教育强调内在的评价。在一种基于单一固定策略的语言中，人们通常可以忘记策略，而专注于原子操作。这使得程序的读取和编写更简单。人类的认知倾向于内心的评价。复杂评估策略的认知开销太大，Klint4原子操作太小。最内在的评价可以非常有效地实施。使用策略进行小规模编程是在所用策略的概念复杂性和原子操作的简单性之间进行平衡的行为。3其他应用策略和原子操作之间的不平衡只能在具有以下两个特征之一的应用程序中得到策略是应用程序本身的重要组成部分。原子步骤的复杂性相对较高。我现在将讨论两个不符合本说明的应用领域3.1定理证明在定理证明的情况下，给出公理和证明规则，问题是证明或反驳一个潜在的定理。应用证明规则的顺序是问题解决方案的重要组成部分，并且以策略（也称为“策略”）的形式表达这种顺序是非常自然的。这与自动定理证明（策略指导证明者）以及交互式定理证明（策略记录用户交互的结果）有关。一个单独的证明步骤也可能构成一个复杂的计算。3.2大规模编程在大型程序设计的情况下，问题是如何组合程序组件以形成完整的应用程序。这个问题可以从静态和动态两个角度来探讨。在前一种情况下，必须考虑静态导入关系、参数绑定等。在后一种情况下，要考虑组件的动态相互作用。这是所谓的协调语言的领域，其中某种形式的并发演算（-演算，ACP等）用于描述协作组件之间的协议。该应用领域恰好具有前面提到的特征：组件之间的协作协议（策略）是应用程序的重要组成部分。粒度高，即，组件（\actions”）执行语义上重要的任务。换句话说，理解与组件相关的协作协议不会像以前那样产生显著的认知开销Klint5for programming编程in the small小.令人惊讶的是，策略语言中的许多原语（顺序组合，选择，重复）与协调语言中的原语相同。策略语言中最突出的缺失是更面向流程的功能，如通信和动态流程创建。战略语言和协调语言的合并看起来像是一个有趣的研究领域。4结论在上述推测中，出现了以下问题：主流的编程语言是（而且可能会是）基于最内层的评估。战略规划不太可能成为主流模式，但可以找到自己的利基市场。策 略编程最有可能应用于其中策略是应用的基本方面和/或原子步骤的复杂性相对较高的应用领域。战略规划可以从协调语言的工作中获益。