本页使用了标题或全文手工转换

求值策略

维基百科,自由的百科全书
跳转至: 导航搜索
求值策略

及早求值
惰性求值
部分求值
远程求值
短路求值

计算机科学中,求值策略(Evaluation strategy)是确定编程语言表达式的求值的一组(通常确定性的)规则。重点典型的位于函数或算子上——求值策略定义何时和以何种次序求值给函数的实际参数,什么时候把它们代换入函数,和代换以何种形式发生。经常使用用来研究函数的形式系统λ演算来建模求值策略,这里它们通常叫做归约策略。求值策略分为两大基本类,严格的和非严格的,基于如何处理给函数的实际参数。一个语言可以组合多种求值策略;例如C++组合了传值调用和传引用调用。多数语言对布尔表达式和if语句使用某种形式的非严格求值。

严格求值 (Strict evaluation)[编辑]

在“严格求值”中,给函数的实际参数总是在应用这个函数之前求值。

邱奇编码下,算子热情求值映射到了函数的严格求值;为此严格求值有时叫做“热情求值”。多数现存编程语言对函数使用严格求值。

应用次序 (Applicative order)[编辑]

“应用次序”(或“最左最内”)求值称呼函数的实际参数按可归约表达式的后序遍历从左至右的求值的策略。不像传值调用,应用次序求值尽可能的在应用函数之前归约函数体内的项。

传值调用 (Call by value)[编辑]

“传值调用”求值是最常见的求值策略,用于广泛使用的语言如 CScheme 中。在传值调用中,求值实际参数表达式,并把结果值绑定到在函数中对应的变量上(通常通过避免捕获代换或把值复制到新内存区域中)。如果函数或过程能够把值赋值到它的形式参数,则被赋值的只是局部复件 -- 就是说,在调用者辖域内的传递入函数调用的任何东西在函数返回的时候都是未变更的。

传值调用不是一个单一的求值策略,而是函数的实际参数在被传递给函数之前就被求值的求值策略家族。尽管使用传值调用的多数编程语言从左至右的求值函数的实际参数,某些语言(比如 OCaml)从右至左的求值函数和它们的实际参数,而另一些语言(比如 Scheme 和 C) 未指定这种次序(尽管它们保证顺序一致性)。

传引用调用 (Call by reference)[编辑]

在“传引用调用”求值中,传递给函数的是到它的实际参数的隐式引用而不是实际参数值自身。如果函数能够修改这样的形式参数,则任何改变对于调用者也是可见的。如果实际参数表达式是左值(L-value),则使用它的地址。否则调用者构造一个临时对象并传递到这个对象的引用;在函数返回的时候丢弃这个对象。

某些语言包含引用作为一级值的概念。例如 ML 语言有“ref”构造子;C++ 中的引用也显式的建立。在这些语言中,“传引用调用”可以用来意味着传递一个引用值作为给函数的实际参数。

在包含无限制指针替代或补充引用的语言(比如 C)中,“传地址调用”是传引用调用的变体,这里的引用是无限制指针。

传复件-恢复调用 (Call by copy-restore)[编辑]

“传复件-恢复调用”、“传值-结果调用”或“传值-返回调用”(在 Fortran 社区中的术语)是传引用调用的特殊情况,即在传引用调用时,向被叫进程所传递的引用并非呼叫进程原有的引用,而是一个原有引用的复制,即被传递的引用与呼叫进程没有关系。传复件-恢复调用在这种情况下很重要:如果函数调用的一个形式参数,是可能被其他执行线程同时访问的引用。那么就把这个引用的内容复制到一个新建立的引用中,再将这个新建立的、与呼叫进程无关的引用传递给被叫进程。当被叫进程执行结束、调用返回的时候,再把这个新引用中更新过的内容复制回呼叫进程原来的引用中(“恢复”)。

传值-返回调用的语义在两个或更多实际参数相互是别名的时候也不同于传引用调用,就是说它们都指向了在调用者环境中的同一个变量。在传引用调用下,写其中一个会影响另一个;传值-返回调用通过给函数以独自的复件来避免了这种情况,但没有规定在调用者环境中的结果(依赖于哪个别名实际参数首先被复制回去)。

当引用未初始化就传递给被调用者的时候,这种求值策略可以叫“传结果调用”。

部分求值 (Partial evaluation)[编辑]

在“部分求值”中,求值可以延续到仍未被应用的函数体之内。求值不包含未绑定变量的任何子表达式,并且归约其实际参数值是已知的函数应用。在有副作用存在的时候,完全部分求值可能产生未预期的结果,支持部分求值的系统趋向只把它用于函数内“纯”表达式(没有副作用的表达式)。

非严格求值 (Non-strict evaluation)[编辑]

在“非严格求值”中,不求值给函数的实际参数,除非它们在函数体内实际上被用到了。

在邱奇编码下,算子的惰性求值映射到了函数的非严格求值;为此,非严格求值有时也叫做“惰性求值”。布尔表达式在很多语言中使用惰性求值;在这种上下文中它通常叫做短路求值。条件表达式也通常使用惰性求值,但出于不同的原因。

正常次序 (Normal order)[编辑]

“正常次序”(或“最左最外”)求值是总是归约的最外可归约式,在求值函数的实际参数之前应用函数的求值策略。它不同于传名调用,传名调用不进入未应用的函数体内求值。

传名调用 (Call by name)[编辑]

在“传名调用”求值中,根本就不求值给函数的实际参数 — 而是使用避免捕获代换把函数的实际参数直接代换入函数体内。如果实际参数在函数的求值中未被用到,则它永不被求值;如果这个实际参数使用多次,则它每次都被重新求值。(参见 Jensen设备。)

传名调用求值超过传值调用求值的优点是传名调用求值在一个值存在的时候总是生成这个值,而传名调用可能不终止如果这个函数的实际参数是求值这个函数所不需要的不终止计算。反过来说,在函数的实际参数会用到的时候传名调用就非常慢了,这是因为实践中几乎总是要使用如 thunk 这样的机制。

传名调用求值很少直接实现,但是经常用于程序和编程语言的理论性质的思考中。带有传名调用语义的现实世界中的语言趋向使用传需求调用求值。传名调用是 ALGOL 60 中的缺省求值。

传需求调用 (Call by need)[编辑]

“传需求调用”是传名调用的记忆化版本,如果“函数的实际参数被求值了”,这个值被存储起来已备后续使用。在“纯”(无副作用)设置下,这产生同传名调用一样的结果;当函数实际参数被使用两次或更多次的时候,传需求调用总是更快。

因为表达式的求值可能出现在计算内任意远的地方,使用传需求调用的语言一般不支持计算效果(比如 mutation)除非通过使用 Monad。这消除了其值变更先于它们的延迟求值的变量的任何未预期行为。

Haskell 是最周知的使用传需求调用求值的语言。

传宏展开调用 (Call by macro expansion)[编辑]

“传宏展开调用”类似于传名调用,但是使用了文本代换而不是避免捕获代换。如果不小心的使用,宏代换可能导致变量捕获并导致不希望的行为。卫生宏通过检查并替换不是形式参数的阴影变量避免了这个问题。

非确定性策略 (Nondeterministic strategies)[编辑]

完全 β-归约 (Full β-reduction)[编辑]

在“完全 β-归约”下,任何函数应用都可以在任何时候归约(是避免捕获代换把函数的实际参数代换如函数内)。这甚至可以在未应用的函数体内进行。

传预期调用 (Call by future)[编辑]

“传预期调用”(或“并行传名调用”)类似于传名调用,除了这个函数的实际参数的求值可能并行于函数体的求值(而非只在用到的时候)。两个执行线程在函数体的求值中需要这个实际参数的时候同步;如果这个实际参数永不用到,实际参数的线程可以杀死。

最优求值 (Optimistic evaluation)[编辑]

“最优求值”是传需求调用的另一个变体,在其中函数的实际参数部分的求值一段时间(这可在运行时间调整),此后求值退出使用传需求调用应用函数。这种方式避免了传需求调用的某些运行时间代价,而仍保持了想要的终止特征。

参见[编辑]

引用[编辑]