求值策略中惰性求值的应用

《求值策略中惰性求值的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求值策略中惰性求值的应用摘要：求值策略有很多种，本文先对每种求值策略加以简述，然后针对惰性求值进行详细分析，并通过9个实例来说明惰性求值的使用特点，最后总结其优缺点，分析实用性。关键字：求值策略;惰性求值;函数式编程;在计算机科学中，求值策略(Evaluationstrategy)是确定编程语言中表达式求值的一组（通常确定性的）规则。重点的位于函数或算子上——求值策略定义何时和以何种次序为函数的实际参数求值，什么时候把它们代换入函数，和代换以何种形式发生。经常用研究函数的形式系统λ演算来建模求值策略，这里它们通常叫做归约策略。求值策略分为两大基本类，基于如何处理函数的实际参数，

2、分为严格的和非严格的。一个语言可以组合多种求值策略，例如C++组合了传值调用和传引用调用。多数语言对布尔表达式和if语句使用某种形式的非严格求值。1各种求值策略简介首先，求值策略分三大部分，严格求值、非严格求值和非确定性策略。其中严格求值包括应用次序、传值调用、传引用调用和传复件-恢复调用，非严格求值包括正常次序、传名调用、传需求调用、传宏展开调用，非确定性策略包括完全β-归约、传预期调用、最优求值。1.1严格求值(Strictevaluation)在“严格求值”中，给函数的实际参数总是在应用这个函数之前求值。在邱奇编码下，算子的热情求值映射到了函数的严格求值；为此严格求值有时

3、叫做“热情求值”。多数现存编程语言对函数使用严格求值。1.1.1 应用次序(Applicativeorder)“应用次序”(或“最左最内”)求值称呼函数的实际参数按可归约表达式的后序遍历从左至右的求值的策略。不像传值调用，应用次序求值尽可能的在应用函数之前归约函数体内的项。1.1.2传值调用(Callbyvalue)“传值调用”求值是最常见的求值策略，用于广泛使用的语言如 C 和 Scheme 中。在传值调用中，求值实际参数表达式，并把结果值绑定到在函数中对应的变量上(20/20通常通过避免捕获代换，或把值复制到新的内存区域中)。如果函数或过程能够把值赋到它的形式参数，则被赋值

4、的只是局部复件，就是说，在调用者辖域内的传递入函数调用的任何东西在函数返回的时候都是未变更的。传值调用不是一个单一的求值策略，而是函数的实际参数在被传递给函数之前就被求值的求值策略家族。尽管使用传值调用的多数编程语言从左至右的求值函数的实际参数，某些语言(比如 OCaml)从右至左的求值函数和它们的实际参数，而另一些语言(比如Scheme和C)未指定这种次序(尽管它们保证顺序一致性)。1.1.1传引用调用(Callbyreference)在“传引用调用”求值中，传递给函数的是到它的实际参数的隐式引用而不是实际参数值自身。如果函数能够修改这样的形式参数，则任何改变对于调用者也是可

5、见的。如果实际参数表达式是左值(L-value)，则使用它的地址。否则调用者构造一个临时对象并传递到这个对象的引用；在函数返回的时候丢弃这个对象。某些语言包含引用作为一级值的概念。例如 ML 语言有“ref”构造子；C++中的引用也显式的创建。在这些语言中，“传引用调用”可以用来传递一个引用值作为给函数的实际参数。在包含无限制指针替代或补充引用的语言(比如C)中，“传地址调用”是传引用调用的变体，这里的引用是无限制指针。1.1.2传复件-恢复调用(Callbycopy-restore)“传复件-恢复调用”、“传值-结果调用”或“传值-返回调用”(在 Fortran 社区中的术语

6、)是传引用调用的特殊情况，即在传引用调用时，向被叫进程所传递的引用并非调用进程原有的引用，而是一个原有引用的复制，即被传递的引用与调用进程没有关系。传复件-恢复调用在这种情况下很重要：如果函数调用的一个形式参数，是可能被其他执行线程同时访问的引用。那么就把这个引用的内容复制到一个新创建的引用中，再将这个新创建的、与调用进程无关的引用传递给被叫进程。当被叫进程执行结束、调用返回的时候，再把这个新引用中更新过的内容复制回调用进程原来的引用中（“恢复”）。传值-返回调用的语义在两个或更多实际参数相互为别名的时候，也不同于传引用调用，就是说它们都指向了调用者环境中的同一个变量。在传引用

7、调用下，写其中一个会影响另一个；传值-返回调用通过给函数以独自的复件来避免了这种情况，但没有规定调用者环境中的结果(依赖于哪个别名实际参数首先被复制回去)。20/20当引用未初始化就传递给被调用者的时候，这种求值策略可以叫“传结果调用”。1.1.1 部分求值(Partialevaluation)在“部分求值”中，求值可以延续到仍未被应用的函数体之内。求值不包含未绑定变量的任何子表达式，并且归约其实际参数值是已知的函数应用。在有副作用存在的时候，完全部分求值可能产生未预期的结果，支持部分求值的