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

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

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

跳过转换变量到目前为止，我们所有惰性求值的例子都要求在进行计算之前必须完全实现中间值。部分原因是由于我们正在解决的问题的需求所导致的，另外一部分原因则是由于 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 对

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

;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. 另外一个专用的惰性结构

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

;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 we've 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 的所有优点。现在，由于乘法操作不管怎样都是一个相当快速的操作，因此这个完整的操作可能就有点浪费时间，不过它作为一个例子来说还是非常不错的。它对于执行代价更为昂贵的操作来说可以节省大量的时间，尤其是对于那些可能需要上下文开关或大量处理器资源的操作来说更是如此。
这种技术一种流行的用法是进行字符串的附加操作。它不用在每次进行附加操作时都分配新空间，而是只需要简单地维护一个需要进行连接的字符串列表。然后，当需要最终版本的字符串时，就只需要为这个新字符串分配一次空间。这样就节省了多个 malloc 调用，以及复制每个字符串的时间。
惰性求值到现在为止，我们重点介绍的是非惰性语言中的惰性结构。然而，有些语言，例如 Haskell，会将一些惰性操作作为普通求值过程的一部分。这被称之为惰性求值。惰性求值中的参数直到需要时才会进行计算。这种程序实际上是从末尾开始反向执行的。它会判断自己需要返回什么，并继续向后执行来确定要这样做需要哪些值。基本上，每个函数都是使用对各个参数的 promise 来调用的。当计算需要值时，它就会执行 promise。由于代码只有在需要值时才会执行，因此这就称为按需调用。在传统编程语言中，传递的是值，而不是 promise，因此这就称为按值调用。
按需调用编程有几个优点。流是自动实现的。不需要的值永远也不会计算。然而，惰性程序的行为通常都很难预测。而在按值调用程序中，求值的顺序是可以预测的，因此任何基于时间或序列的计算都相当容易实现。在惰性语言中这就变得相当困难了，此时要描述具有明确顺序的事件就需要诸如 monads 之类的特殊结构。所有这些都使得与其他语言的交互变得十分困难。
有几种语言默认就会进行惰性编程，包括 Haskell 和 Clean。其他几种语言也有一些惰性版本，包括 Scheme、ML 等。
结束语有时候通过将求值运算延迟到需要值时进行，您可以对程序的速度进行优化，也可以将程序重构成一种更容易理解的形式。尽管惰性编程技术非常有价值，但却没有得到广泛实现，甚至也并不广为人知。您可以考虑将惰性编程技术作为一种贮备技能添加到自己的技能库中。

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