电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 惰性编程和惰性求值（1） [打印本页]

作者: look_w 时间: 2018-5-19 15:32 标题: 惰性编程和惰性求值（1）

Scheme 中的简单惰性编程惰性编程是这样一种技术：它可以将代码的求值延迟到需要结果值时再进行。例如，在 Scheme 中，惰性编程就是通过两个特殊的结构显式支持的。Scheme 的 delay 特殊表单接收一个代码块，它不会立即执行它们，而是将代码和参数作为一个 promise 存储起来。如果您 force 这个 promise 产生一个值，它就会运行这段代码。promise 随后会保存结果，这样将来再请求这个值时，该值就可以立即返回，而不用再次执行代码了。
下面是一个说明 delay 和 force 如何一起工作的简单例子。
清单 1. 使用 delay 和 force 的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

;;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 produces an error, because the promise must be forced to be used
(display (+ my-promise (force another-promise)))

这些结构的使用都非常简单，但是它们应该用来干什么呢？一般地，惰性编程常用于所调用的函数生成调用程序不需要的值的情况下。例如，假设有一个函数会计算一组数字的平均值、方差和标准差。下面是实现这些功能的一种方法：
清单 2. 简单的统计计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(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 - 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. 利用惰性求值进行统计计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

(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 - 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 语言中惰性求值的形式化表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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。另外，在那些不直接支持惰性编程的语言中，惰性编程技术也可以通过类来实现。

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)