惰性编程和惰性求值
发布网友
发布时间：2022-04-25 15:00
共1个回答
热心网友
时间：2022-04-26 18:30
Scheme 中的简单惰性编程
惰性编程是这样一种技术：它可以将代码的求值延迟到需要结果值时再进行。例如，在 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 doesn't have to execute. It just returns
;;the value that was previously saved.
(display (force my-promise))
(newline)
;;This proces 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 (x[i] - 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 (x[i] - 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 的数字。什么？您不能对一个无穷列表进行操作？为什么不行呢？
实际上，可能与直观的感觉相反，如果无穷列表基于一定的生成规则 ，那么无穷列表可能比有穷列表存储起来占用的空间更少。在上面这个例子中，原始列表是基于 X[i] = (i + 1) * 5 这条规则生成的，其中 X[i] 是列表在索引 i 处的值。 X[i] 也可以使用其前一个值来表示：X[i] = X[i-1] + 5; X[0] = 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，这种形式的流很容易实现。 但是这种流可能会导致所执行的计算量比所希望的多，因为列表中的值都会进行计算。标准流是在 SRFI-40 中定义的，它解决了这些问题以及其他一些问题（更多细节请参看 参考资料）。
回页首
跳过转换变量
到目前为止，我们所有惰性求值的例子都要求在进行计算之前必须完全实现中间值。部分原因是由于我们正在解决的问题的需求所导致的，另外一部分原因则是由于 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 aren't 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))
(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 的所有优点。现在，由于乘法操作不管怎样都是一个相当快速的操作，因此这个完整的操作可能就有点浪费时间，不过它作为一个例子来说还是非常不错的。它对于执行代价更为昂贵的操作来说可以节省大量的时间，尤其是对于那些可能需要上下文开关或大量处理器资源的操作来说更是如此。
这种技术一种流行的用法是进行字符串的附加操作。它不用在每次进行附加操作时都分配新空间，而是只需要简单地维护一个需要进行连接的字符串列表。然后，当需要最终版本的字符串时，就只需要为这个新字符串分配一次空间。这样就节省了多个 malloc 调用，以及复制每个字符串的时间。
惰性求值
到现在为止，我们重点介绍的是非惰性语言中的惰性结构。然而，有些语言，例如 Haskell，会将一些惰性操作作为普通求值过程的一部分。这被称之为惰性求值。惰性求值中的参数直到需要时才会进行计算。这种程序实际上是从末尾开始反向执行的。它会判断自己需要返回什么，并继续向后执行来确定要这样做需要哪些值。基本上，每个函数都是使用对各个参数的 promise 来调用的。当计算需要值时，它就会执行 promise。由于代码只有在需要值时才会执行，因此这就称为按需调用。在传统编程语言中，传递的是值，而不是 promise，因此这就称为按值调用。
按需调用编程有几个优点。流是自动实现的。不需要的值永远也不会计算。然而，惰性程序的行为通常都很难预测。而在按值调用程序中，求值的顺序是可以预测的，因此任何基于时间或序列的计算都相当容易实现。在惰性语言中这就变得相当困难了，此时要描述具有明确顺序的事件就需要诸如 monads 之类的特殊结构。所有这些都使得与其他语言的交互变得十分困难。
有几种语言默认就会进行惰性编程，包括 Haskell 和 Clean。其他几种语言也有一些惰性版本，包括 Scheme、ML 等。
