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

求值策略中惰性求值的应用摘要：求值策略有很多种，本文先对每种求值策略加以简述，然后针对惰性求值进行详细分析，并通过9个实例来说明惰性求值的使用特点，最后总结其优缺点，分析实用性。关键字：求值策略;惰性求值;函数式编程;在计算机科学中，求值策略(Evaluation strategy)是确定编程语言中表达式求值的一组（通常确定性的）规则。重点的位于函数或算子上求值策略定义何时和以何种次序为函数的实际参数求值，什么时候把它们代换入函数，和代换以何种形式发生。经常用研究函数的形式系统演算来建模求值策略，这里它们通常叫做归约策略。求值策略分为两大基本类，基于如何处理函数的实际参数，分为严格的和非严格的。一个语言可以组合多种求值策略，例如C+组合了传值调用和传引用调用。多数语言对布尔表达式和if语句使用某种形式的非严格求值。1 各种求值策略简介首先，求值策略分三大部分，严格求值、非严格求值和非确定性策略。其中严格求值包括应用次序、传值调用、传引用调用和传复件-恢复调用，非严格求值包括正常次序、传名调用、传需求调用 、传宏展开调用，非确定性策略包括完全-归约、传预期调用、最优求值 。1.1 严格求值 (Strict evaluation)在“严格求值”中，给函数的实际参数总是在应用这个函数之前求值。在邱奇编码下，算子的热情求值映射到了函数的严格求值；为此严格求值有时叫做“热情求值”。多数现存编程语言对函数使用严格求值。1.1.1 应用次序 (Applicative order) “应用次序”(或“最左最内”)求值称呼函数的实际参数按可归约表达式的后序遍历从左至右的求值的策略。不像传值调用，应用次序求值尽可能的在应用函数之前归约函数体内的项。1.1.2 传值调用 (Call by value)“传值调用”求值是最常见的求值策略，用于广泛使用的语言如C和Scheme中。在传值调用中，求值实际参数表达式，并把结果值绑定到在函数中对应的变量上(通常通过避免捕获代换，或把值复制到新的内存区域中)。如果函数或过程能够把值赋到它的形式参数，则被赋值的只是局部复件，就是说，在调用者辖域内的传递入函数调用的任何东西在函数返回的时候都是未变更的。传值调用不是一个单一的求值策略，而是函数的实际参数在被传递给函数之前就被求值的求值策略家族。尽管使用传值调用的多数编程语言从左至右的求值函数的实际参数，某些语言(比如OCaml)从右至左的求值函数和它们的实际参数，而另一些语言(比如 Scheme 和 C) 未指定这种次序(尽管它们保证顺序一致性)。1.1.3 传引用调用 (Call by reference)在“传引用调用”求值中，传递给函数的是到它的实际参数的隐式引用而不是实际参数值自身。如果函数能够修改这样的形式参数，则任何改变对于调用者也是可见的。如果实际参数表达式是左值(L-value)，则使用它的地址。否则调用者构造一个临时对象并传递到这个对象的引用；在函数返回的时候丢弃这个对象。某些语言包含引用作为一级值的概念。例如ML语言有“ref”构造子；C+ 中的引用也显式的创建。在这些语言中，“传引用调用”可以用来传递一个引用值作为给函数的实际参数。在包含无限制指针替代或补充引用的语言(比如 C)中，“传地址调用”是传引用调用的变体，这里的引用是无限制指针。1.1.4 传复件-恢复调用 (Call by copy-restore) “传复件-恢复调用”、“传值-结果调用”或“传值-返回调用”(在Fortran社区中的术语)是传引用调用的特殊情况，即在传引用调用时，向被叫进程所传递的引用并非调用进程原有的引用，而是一个原有引用的复制，即被传递的引用与调用进程没有关系。传复件-恢复调用在这种情况下很重要：如果函数调用的一个形式参数，是可能被其他执行线程同时访问的引用。那么就把这个引用的内容复制到一个新创建的引用中，再将这个新创建的、与调用进程无关的引用传递给被叫进程。当被叫进程执行结束、调用返回的时候，再把这个新引用中更新过的内容复制回调用进程原来的引用中（“恢复”）。传值-返回调用的语义在两个或更多实际参数相互为别名的时候，也不同于传引用调用，就是说它们都指向了调用者环境中的同一个变量。在传引用调用下，写其中一个会影响另一个；传值-返回调用通过给函数以独自的复件来避免了这种情况，但没有规定调用者环境中的结果(依赖于哪个别名实际参数首先被复制回去)。当引用未初始化就传递给被调用者的时候，这种求值策略可以叫“传结果调用”。1.1.5 部分求值 (Partial evaluation)在“部分求值”中，求值可以延续到仍未被应用的函数体之内。求值不包含未绑定变量的任何子表达式，并且归约其实际参数值是已知的函数应用。在有副作用存在的时候，完全部分求值可能产生未预期的结果，支持部分求值的系统趋向只把它用于函数内“纯”表达式(没有副作用的表达式)。1.2 非严格求值 (Non-strict evaluation)在“非严格求值”中，不为函数的实际参数求值，除非它们在函数体内被用到了。在邱奇编码下，算子的惰性求值映射到了函数的非严格求值；为此，非严格求值有时也叫做“惰性求值”。布尔表达式在很多语言中使用惰性求值；在这种上下文中它通常叫做短路求值。条件表达式也通常使用惰性求值，但出于不同的原因。1.2.1 正常次序 (Normal order) “正常次序”(或“最左最外”)求值是总是归约的最外可归约式，在求值函数的实际参数之前应用函数的求值策略。它不同于传名调用，传名调用不进入未应用的函数体内求值。1.2.2 传名调用 (Call by name)在“传名调用”求值中，根本就给函数的实际参数求值 而是使用避免捕获代换把函数的实际参数直接代换入函数体内。如果实际参数在函数的求值中未被用到，则它永不被求值；如果这个实际参数使用多次，则它每次都被重新求值。传名调用求值超过传值调用求值的优点是传名调用求值在一个值存在的时候总是生成这个值，而传名调用可能不终止如果这个函数的实际参数是求值这个函数所不需要的不终止计算。反过来说，在函数的实际参数会用到的时候传名调用就非常慢了，这是因为实践中几乎总是要使用如thunk这样的机制。传名调用求值很少直接实现，但是经常用于程序和编程语言的理论性质的思考中。带有传名调用语义的现实世界中的语言趋向使用传需求调用求值。传名调用是ALGOL 60中的缺省求值。1.2.3 传需求调用 (Call by need) “传需求调用”是传名调用的记忆化版本，如果“函数的实际参数被求值了”，这个值被存储起来已备后续使用。在“纯”(无副作用)设置下，这产生同传名调用一样的结果；当函数实际参数被使用两次或更多次的时候，传需求调用总是更快。因为表达式的求值可能出现在计算内任意远的地方，使用传需求调用的语言一般不支持计算效果(比如mutation)除非通过使用Monad。这消除了其值变更先于它们的延迟求值的变量的任何未预期行为。Haskell是最周知的使用传需求调用求值的语言。1.2.4 传宏展开调用 (Call by macro expansion) “传宏展开调用”类似于传名调用，但是使用了文本代换而不是避免捕获代换。如果不小心的使用，宏代换可能导致变量捕获并导致不希望的行为。卫生宏通过检查并替换不是形式参数的阴影变量避免了这个问题。1.3 非确定性策略 (Nondeterministic strategies)1.3.1 完全 -归约 (Full -reduction)在“完全 -归约”下，任何函数应用都可以在任何时候归约(是避免捕获代换把函数的实际参数代换如函数内)。这甚至可以在未应用的函数体内进行。1.3.2 传预期调用 (Call by future) “传预期调用”(或“并行传名调用”)类似于传名调用，除了这个函数的实际参数的求值可能并行于函数体的求值(而非只在用到的时候)。两个执行线程在函数体的求值中需要这个实际参数的时候同步；如果这个实际参数永不用到，实际参数的线程可以杀死。1.3.3 最优求值 (Optimistic evaluation) “最优求值”是传需求调用的另一个变体，在其中为函数的实际参数部分求值占用一段时间(这可在运行时间调整)，此后求值退出使用传需求调用应用函数。这种方式避免了传需求调用的某些运行时间代价，而仍保持了想要的终止特征。1.4 其他求值策略1.4.1 远程求值在计算机科学中,远程求值泛指任何包括将可执行软件程序从客户端传输到服务计算机并在服务器上执行的技术。程序结束后，执行的结果被发送到客户端。 远程求值是属于移动代码和Web服务技术。远程求值的一个例子是网格计算：可执行任务被发送到网格中的一个特定计算机上。任务执行完成后，执行结果被发回到客户端。客户端接着需要将多个并发计算的子任务的不同结果组装成一个结果。1.4.2 短路求值最小化计算（Short-circuit evaluation，也叫做短路计算），是一种计算策略，表达式只有在取得最后值的时候，才会进行计算。这意味着在某些情况下它不需要计算一个表达式的所有部分。例子考虑以下使用C语言写的例子：int a = 0;if (a & myfunc(b) do_something();在这个例子中，最小化计算使得myfunc(b)永远不会被调用。这是因为a等于false，而false AND q无论q是什么总是得到false。这个特性允许两个有用的编程结构。首先，不论判别式中第一个子判别语句要耗费多昂贵的计算，总是会被执行，若此时求得的值为 false，则第二个子判别运算将不会执行，这可以节省来自第二个语句的昂贵计算。再来，这个结构可由第一个子判别语句来避免第二个判别语句不会导致运行时错误。例如对以下使用C语言写的例子而言，最小化计算可以避免对空指针进行存取。void * p = NULL;int ret;/* . */if(p & ret = func(p) ) /* 或者另一种更清晰的写法是if( (p != NULL) & (ret = func(p) ) */ /* . */* . */当使用最小化计算时，很重要的一点是得知表示式取值的顺序。某些编程语言中确保有一致的取值顺序。例如：C语言、Java、Perl、Python和Ruby等。它不过是下面语句的一种更加紧凑的表示形式罢了。if (cond_a) if (expensive_or_dangerous_cond_b) . 2 惰性求值2.1 惰性求值简介函数式语言的两大特性高阶函数与惰性求值，它们能够极大地促进模块化。下面我来重点介绍一下非确定求值，即惰性求值。惰性编程是一种将对函数或请求的处理延迟到真正需要结果时进行的通用概念。有很多应用程序都采用了这种概念，有的非常明显，有些则不太明显。从惰性编程的角度来思考问题，可以帮您消除代码中不必要的计算，也可以帮您重构程序以使之更加面向问题。惰性求值（Lazy Evaluation），又称懒惰求值、懒汉求值，是一个计算机编程中的一个概念，它的目的是要最小化计算机要做的工作。惰性求值是函数式语言的两大特性之一，它有两个相关而又有区别的含意，可以表示为“延迟求值”和“最小化求值”。除可以得到性能的提升外，惰性计算的最重要的好处是它可以构造一个无限的数据类型。有几种语言默认就会进行惰性编程，包括 Haskell 和 Clean。其他几种语言也有一些惰性版本，包括 Scheme、ML 等。这种程序实际上是从末尾开始，反向执行的。它会判断自己需要返回什么，并继续向后执行来确定要这样做需要哪些值。基本上，每个函数都是使用对各个参数的 promise 来调用的。当计算需要值时，它就会执行 promise。由于代码只有在需要值时才会执行，因此这就称为按需调用。在传统编程语言中，传递的是值，而不是 promise，因此这就称为按值调用。按需调用编程有几个优点。流是自动实现的。对于不需要的值，它永远都不会计算。然而，惰性程序的行为通常都很难预测。而在按值调用程序中，求值的顺序是可以预测的，因此任何基于时间或序列的计算都相当容易实现。在惰性语言中这就变得相当困难了，此时要描述具有明确顺序的事件就需要诸如monads之类的特殊结构。所有这些都使得与其他语言的交互变得十分困难。惰性求值的相反是及早求值，这是一个大多数编程语言所拥有的普通计算方式。惰性求值是一种延迟求值，特别用于函数式编程语言中。在使用惰性求值的时候，表达式不在它被绑定到变量之后就立即求值，而是在该值被取用的时候求值，也就是说，语句如x:=expression;(把一个表达式的结果赋值给一个变量)明显的调用这个表达式被计算并把结果放置到x中，但是先不管实际在x中的是什么，直到通过后面的表达式中到x的引用而有了对它的值的需求的时候，而后面表达式自身的求值也可以被延迟，最终为了生成让外界看到的某个符号而计算这个快速增长的依赖树。某些编程语言缺省延迟表达式的求值，另一些提供函数或特殊语法来延迟求值。在Miranda和Haskell中，缺省延迟函数实际参数的求值。在很多其他语言中，可以使用特殊语法明确悬置计算来延迟求值(比如Scheme的 delay 或 force)，更一般的通过把一个表达式包装在thunk中。表示这种明确延迟求值的对象叫做预期或承诺。延迟求值的一个好处是能够建立可计算的无限列表而没有妨碍计算的无限循环或大小问题。例如，可以建立生成无限斐波那契数列表的的函数(经常叫做“流”)。第n个斐波那契数的计算仅是从这个无限列表上提取出这个元素，它只强迫这个列表的前 n 个成员的计算。例如，在 Haskell 中，斐波纳契数的列表可以写为 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)在 Haskell 语法中，: 预备一个元素给列表，tail返回去掉第一个元素的一个列表，而zipWith使用一个特殊函数(这里是加法)来组合两个列表的对应元素生成第三个列表。假定编程者是仔细的，只有生成特定结果时需要某值，所需值才会被求出来。但是特定计算可能导致程序尝试求值无限数目的元素；例如，要求列表的长度或使用fold运算总和这个列表的元素将导致程序不能终止或耗尽内存。2.2 惰性求值应用举例惰性编程是这样一种技术：它可以将代码的求值延迟到需要结果值时再进行。例如，在 Scheme 中，惰性编程就是通过两个特殊的结构显式支持的。Scheme 的delay特殊表单接收一个代码块，它不会立即执行它们，而是将代码和参数作为一个promise存储起来。如果您force这个 promise 产生一个值，它就会运行这段代码。promise 随后会保存结果，这样将来再请求这个值时，该值就可以立即返回，而不用再次执行代码了。下面是一个说明delay和force如何一起工作的简单例子。清单 1. 使用 delay 和 force 的例子;The multiplication is saved but not executed(define my-promise (delay (* 5 6 7 8 9);Again, saved but not executed(define another-promise (delay (sqrt 9);Forces the multiplication to execute. Saves and returns the value(display (force my-promise)(newline);This time, the multiplication doesnt have to execute. It just returns;the value that was previously saved.(display (force my-promise)(newline);This produces an error, because the promise must be forced to be used(display (+ my-promise (force another-promise)这些结构的使用都非常简单，但是它们应该用来干什么呢？一般地，惰性编程常用于所调用的函数生成调用程序不需要的值的情况下。例如，假设有一个函数会计算一组数字的平均值、方差和标准差。下面是实现这些功能的一种方法：清单 2. 简单的统计计算(define (square x) (* x x)(define (calculate-statistics the-series) (let* ( (size (length the-series) (sum (apply + the-series) (mean (/ sum size) ;variance is the sum of (xi - mean)2 for all list values (variance (let* ( (variance-list (map (lambda (x) (square (- x mean) the-series) (/ (apply + variance-list) size) (standard-deviation (sqrt variance) (vector mean variance standard-deviation);Run the program(display (calculate-statistics (2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)(newline)现在假设我们希望只在特定条件下才会计算标准差，但是这个函数却早已花费了很多计算能力来计算标准差。有几种方法可以解决这个问题。您可以将其分割成几个单独的函数分别计算平均值、方差和标准差。不过，这样每个函数都必须重复计算平均值的过程。如果您同时需要这三个值，那么平均值就会被计算 3 次、方差会被计算 2 次、标准差会被计算 1 次。这中间有很多额外的不必要的工作。现在，您也可以要求将平均值传递给标准差函数，并强制用户为您调用平均值的计算函数。尽管这是可行的，但是这会产生一个非常可怕的 API：它的接口使用了太多特定于实现的内容。使用惰性求值的一种较好的方法是将计算延迟：清单 3. 利用惰性求值进行统计计算(define (square x) (* x x)(define (calculate-statistics the-series) (let* ( (size (delay (length the-series) (mean (delay (/ (apply + the-series) (force size) ;variance is the sum of (xi - mean)2 (variance (delay (let* ( (variance-list (map (lambda (x) (square (- x (force mean) the-series) (/ (apply + variance-list) (force size) (standard-deviation (delay (sqrt (force variance) (vector mean variance standard-deviation);Run the program(define stats (calculate-statistics (2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)(define mean (force (vector-ref stats 0)(define variance (force (vector-ref stats 1)(define stddev (force (vector-ref stats 2)(display (list mean variance stddev)(newline)在这个版本的calculate-statistics中，直到真正需要值时才会进行计算，并且同样重要的是，任何值都只会计算一次。如果您首先请求计算方差，它就会先计算平均值，并将其保存下来，然后再计算并保存方差。如果接下来您请求计算平均值，因为平均值已经计算出来了，所以只需要简单地返回该值即可。如果您接下来请求计算标准差，它就会使用保存过的方差值，并通过此值来计算标准差。现在不会执行任何不需要的计算，函数的接口也得到了很好的保留。在面向对象语言中，这种惰性编程方法也非常容易实现。在任何需要一组相关计算的地方，都可以创建一个类来保存中间值。构造函数接收所使用的初值，所有计算出来的值都被设置为空。这里不再使用 force，相反地，每个值都有一个 getter，它会检查该值是否为空；如果该值不为空，就执行计算。下面是 Java 语言中这种类的一个骨架：清单 4. Java 语言中惰性求值的形式化表示public class StatisticsCalculator private List the_series; private Double mean; private Integer size; private Double variance; private Double standard_deviation; public StatisticsCalculator(List l) the_series = l; public int getSize() if(size = null) size = the_series.size(); return size; public double getStandardDeviation() if(stddev = null) stddev = Math.sqrt(getVariance(); return stddev; . .这个类本身可以作为一个多值的 promise 使用，实例变量中保留了计算的结果。每个函数都会通过查看变量值是否为空来确定代码是否已经执行过了。如果变量在需要时尚未有值，就执行代码并保存计算结果。注意如果null也在该值的有效值范围内，那么就需要一个辅助标志来说明代码是否已经执行过了，而不能简单地查看该值是否为空。正如您所见，惰性编程技术可以用来为那些返回相关值的函数提供良好有效的 API。另外，在那些不直接支持惰性编程的语言中，惰性编程技术也可以通过类来实现。不确定列表假设您有一个由 5 的倍数组成的列表。现在您希望计算这个列表中所有数字的平方。最后，我们希望对计算结果进行遍历，并显示所有平方值小于 500 的数字。什么？您不能对一个无穷列表进行操作？为什么不行呢？实际上，可能与直观的感觉相反，如果无穷列表基于一定的生成规则，那么无穷列表可能比有穷列表存储起来占用的空间更少。在上面这个例子中，原始列表是基于Xi = (i + 1) * 5这条规则生成的，其中Xi是列表在索引i处的值。Xi也可以使用其前一个值来表示：Xi = Xi-1 + 5; X0 = 5。使用 Scheme 的force和delay，就可以构造一个基于这条规则的数值流：清单 5. 流的例子;This is the generative rule for the list. It returns a pair ;with the car being the next value, and the cdr being a promise ;for the next pair(define (my-generative-rule last-val) (let ( ;generative formula based on previous value (next-val (+ last-val 5) ;put the next value together with a promise for another one (cons next-val (delay (my-generative-rule next-val);Since the cdr is a promise of a pair, rather than a pair itself, ;we have our own functions for getting the car and cdr.(define (mystream-car the-stream) (car the-stream)(define (mystream-cdr the-stream) (force (cdr the-stream);Create our list(define multiples-of-five (cons 5 (delay (my-generative-rule 5);Display the fourth element of the list(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr multiples-of-five)(newline)现在，您希望计算所有数字的平方。要实现这种功能，需要一个函数从现有流和生成规则中创建一个新的流 这有点像map，只不过它是针对流进行的。函数如下：清单 6. 流的专用映射(define (mystream-map function the-stream) (cons ;The first value will be the function applied to the car (function (car the-stream) ;The remaining values will be stored in a promise (delay (mystream-map function (mystream-cdr the-stream)(define squared-stream (mystream-map (lambda (x) (* x x) multiples-of-five);Display the fourth element of this new list(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr squared-stream)(newline)现在，剩下的问题就是循环遍历该流，并打印结果值小于 500 的值：清单 7. 循环遍历流(let loop ( (remaining-stream squared-stream) (if (= (mystream-car remaining-stream) 500) #f (begin (display (mystream-car remaining-stream) (newline) (loop (mystream-cdr remaining-stream)显然，对于这种小程序来说，还有很多方法都可以更直接地实现这个目标。然而，即使在这个例子中，流也可以帮助我们较少地从实现角度来审视问题，而是更多地将问题当作一种抽象思想来看待。流让我们可以集中精力在问题上，而不是在实现上。流简化了与生成元素有关的算法的概念和实现。到目前为止，我们所讨论的流对于学习流背后的概念来说都非常有用。然而，实现却可能会经受大量缺陷的折磨。首先，在很多场合下流都可能需要一个终结器。这种实现却并没有提供这种机制。另外，此处给出的这种流称为odd stream，这种形式的流很容易实现。 但是这种流可能会导致所执行的计算量比所希望的多，因为列表中的值都会进行计算。到目前为止，我们所有惰性求值的例子都要求在进行计算之前必须完全实现中间值。部分原因是由于我们正在解决的问题的需求所导致的，另外一部分原因则是由于delay和force操作本身所带来的。例如，考虑下面的代码：(define val1 20)(define val2 30)(define val3 40)(define val4 0)(define val5 (delay (* val1 val2)(define val6 (delay (* val4 val3)(define val7 (* (force val5) (force val6)在这个例子中，我们知道答案是 0，这是因为我们知道 0 乘任何次都是 0。因此，尽管这看上去似乎是可以使用惰性求值的情况（因为我们正在试图减少不必要的计算），但实际上使用delay和force并不能给我们提供什么帮助。在这类情况下，为了不生成中间结果，需要一些特殊的惰性算法来延迟处理。我们需要实现对请求进行排队。然后，在请求最后结果时，它就可以在该队列中搜索那些可以帮助它对处理过程进行优化的值，然后使用这些值跳过对其他值的处理。在乘法的这个例子中，出现 0 就可以跳过所有的处理了。下面是一个特殊的delay/force对，专门适用于乘法计算：清单 8. 简单的专用 delay/force 对;This will simply use a list to keep track of the values to be multiplied(define (multiply-delay x y) (let ( ;convert to lists if they arent already (x-list (if (list? x) x (list x) (y-list (if (list? y) y (list y) ;append them together (append x-list y-list)(define (multiply-force mul-list) (let ( (has-zero? #f) (for-each (lambda (x) (if (eqv? 0 x) (set! has-zero? #f) #f) mul-list) (if has-zero? 0 (apply * mul-list)(define a (multiply-delay 23 54)(define b (multiply-delay 0 5)(define c (multiply-delay a b)(define d (multiply-delay c 55)(display (multiply-force d)(newline)然而，这个实现也有自己的问题。现在各个部分都不再是惰性的了，也不会再保存值了。为了实现一个优化，我们已经失去了原来的delay和force的优点。因此，我们不会保留一个所有参数的长列表，而是需要将它们放到各个 promise 中单独进行存放，这样我们就依然可以获得之前的优点。我们所需要的是一个说明该值是否已经计算的标记。如果该值已经计算过了，那么此处就只有一个不需要计算的元素了。否则，乘数和被乘数都会出现。新的代码如下：清单 9. 另外一个专用的惰性结构;Unevaluated promises will have the structure (delayed val1 val2);Evaluated promises will have the structure (forced result);Create an unevaluated promise(define (multiply-delay x y) (list delayed x y);Checks promises (and values) to see if they contain any zeros(define (has-zero promise) (if (pair? promise) (if (eq? (car promise) forced) ;check forced value (if (eqv? (cdr promise) 0) #t #f) ;check unforced value (if (or (has-zero (cadr promise) (has-zero (caddr promise) #t #f) ;Check scalar value (if (eqv? promise 0) #t #f);Attempts zero optimization, then defaults to regular delay/force behavior(define (multiply-force promise) (if (eq? (car promise) forced) ;if weve already been forced, return the value (cdr promise) ;otherwise, search for a zero (if (has-zero promise) (begin (set-car! promise forced) (set-cdr! promise 0) 0) (multiply-force-nonzero promise) ;This is for promises which are known to be free of zeros(define (multiply-force-nozero promise) (if (pair? promise) (if (eq? (car promise) forced) ;if the promise has been forced, just return the value (cdr promise) ;otherwise, compute the value, and convert this into a forced promise (begin (set-car! promise forced) (set-cdr! promise (* (multiply-force-nonzero (cadr promise) (multiply-force-nonzero (caddr promise) ;return the forced value (cdr promise) ;This is just a number, so return it promise)这个结构中有普通delay/force的所有优点。现在，由于乘法操作不管怎样都是一个相当快速的操作，因此这个完整的操作可能就有点浪费时间，不过它作为一个例子来说还是非常不错的。它对于执行代价更为昂贵的操作来说可以节省大量的时间，尤其是对于那些可能需要上下文开关或大量处理器资源的操作来说更是如此。这种技术一种流行的用法是进行字符串的附加操作。它不用在每次进行附加操作时都分配新空间，而是只需要简单地维护一个需要进行连接的字符串列表。然后，当需要最终版本的字符串时，就只需要为这个新字符串分配一次空间。