Normal Order (Lazy) Evaluation

十九课

Applicative Order & Normal Order

之前,我们已经了解了一个 Scheme 解释器的重要组件以及组件之间的关系。当我们已经熟悉的 Scheme evaluator 接受到一个 application expression时,它会首先 evaluate application 中的 sub-expression,再把各个 sub-expression 的结果传入 application 表达式的 procedure,进而执行这个 procedure 得到最终结果,这种 evaluation 的方式被称为 Applicative Order。但实际上至少还有另一种 evaluation 的方式,就是推迟 sub-expression 的 evaluation 过程,先把 sub-expression 代入到 application expression,直到某个阶段必须要获取 sub-expression 的值时才去 evaluate sub-expression。总结如下:

  • Applicative Order: 在 evaluate expression 前先 evaluate sub-expression

  • Normal Order: 只在需要的时候 evaluate sub-expression

举例

> ; applicative order
> (define (foo x)
    (write-line "inside foo")
    (+ x x))

> (foo (begin (write-line "eval arg") 222))
eval arg
inside foo
=> 444

> ; normal order
> (define (foo x)
    (write-line "inside foo")
    (+ x x))
> (foo (begin (write-line "eval arg") 222))

; => (begin (write-line "inside foo")
;      (+ (begin (write-line "eval arg") 222)
;         (begin (write-line "eval arg") 222)))
inside foo
eval arg
eval arg
=> 444

可以看见,如果用 Normal Order,sub-expression 在最后要执行 <procedure +> 的时候才被 evaluate,因此 "inside foo" 比 "eval arg" 更早被打印出来。但由于 sub-expression 被延迟 evaluate,它被执行了两次,显然这对 Normal Order 的 evaluation 方式来说是劣势。自然的,有两个疑问需要解决:

  • Normal Order 的好处是什么?

  • 怎么解决 Normal Order 带来的多次 evaluation?

  • 如何改变我们的 Scheme 解释器去实现 Normal Order Evaluation ?(接下来先解决)

Normal Order Scheme Interpreter

为了让 Scheme 解释器执行 Normal Order Evaluation,我们需要做出以下几个改动:

  1. 改变 apply 逻辑

    • 记录 env: 因为 arguments (sub-expressions) 的 evaluation 被推迟,那么它们的 evaluation environment 就需要被记录

    • 记录 delayed arguments 的数据结构

  2. 支持 actual value 和 delayed value

  3. if 表达式

改变 apply 逻辑

(define (l-apply procedure arguments env)          ; env
  (cond (primitive-procedure? procedure)
        (apply-primitive-procedure
          procedure
          (list-of-arg-values arguments env)))     ; list-of-arg-values
        ((compound-procedure? procedure)
         (l-eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             (list-of-delayed-args arguments env)  ; list-of-delayed-args
             (procedure-environment procedure))))
         (else (error "Unkown proc" procedure))))

; 对应使用 apply 的地方也要改动
(define (l-eval exp env)
  (cond ((self-evaluating? exp) exp)
        ; ...
        ((application? exp
         (l-apply (actual-value (operator exp) env)
                  (operands exp)
                  env))
        (else (error "Unkown expression" exp))))

主要有三处变化:

  • env: 上文提过,为了推迟 evaluation ,需要记录相应的环境

  • list-of-arg-values: 当执行 primitive-procedure 的时候,强制 evaluate 所有 delayed arguments

  • list-of-delayed-args: 将 arguments 和 env 打包起来,在之后随时可以强制 evaluate

首先我们看一下 list-of-arg-values 和 list-of-delayed-args 的实现

(define (actual-value exp env)
  (force-it (l-eval exp env)))

(define (list-of-arg-values exps env)
  (if (no-operands? exps) '()
    (cons (actual-value (first-operand exps) env)
          (list-of-arg-values (rest-operands exps)
                              en))))

(define (list-of-delayed-args exps env)
  (if (no-operands? exp) '()
    (cons (delay-it (first-operand exps) env)
          (list-of-delayed-args (rest-operands exps)
                                env))))

thunk - promise to do an evaluation

以下几个词都与 thunk 同义:

  • delayed value

  • promise to do an evaluation

  • promise to return a value when needed, i.e. forced

延用 data driven programming 的风格,我们可以利用 tagged list 来表示 thunk:

(define (delay-it exp env) (list 'thunk exp env))
(define (thunk? obj) (tagged-list? obj 'thunk))
(define (thunk-exp thunk) (cadr thunk))
(define (thunk-env thunk) (caddr thunk))

(define (force-it obj)
  (cond ((thunk? obj)
         (actual-value (thunk-exp obj)
                       (thunk-env obj)))
        (else obj)))

If expression

一些特殊表达式也需要修改,如 if 的 condition 必须要有 actual-value 才可以判断下一步是 consequence 还是 alternative:

(define (l-eval-if exp env)
  (if (true? (actual-value) (if-predicate exp) env))
      (l-eval (if-consequent exp) env)
      (l-eval (if-alternative exp) env)))

以上,我们完成了对 Scheme 解释器的 evaluator 改造,现在它已经从 Applicative Order 变成了 Normal Order。

Memo-izing evaluation

在 Applicative Order & Normal Order 一节中,我们观察到,Normal Order 由于推迟 sub-expression 的 evaluation,而把 sub-expression 替换到 application expression 的相应位置,同时带来了重复计算 (re-evaluation) 的情况,本节我们介绍如何利用 Memo-izing Thunks 来避免重复计算。

Memo-izing Thunk 的原理再简单不过,计算一次以后就把结果记下来,下次用到的时候再拿出来即可。

具体示意图如下:![](/assets/Screen Shot 2018-04-13 at 11.26.08 PM.jpg)

需要注意的是,为了使用 thunk 的所有地方都能立即看到 thunk 被 evaluate 过,这里使用 mutation 把 thunk 编程 evaluated-thunk:

(define (evaluated-thunk? obj)
  (tagged-list? obj 'evaluated-thunk))
(define (thunk-value evaluated-thunk)
  (cadr evaluated-thunk))

(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result (actual-value (thunk-exp obj)
                                     (thunk-env obj)))))
            (set-car! obj 'evaluated-thunk)
            (set-car! (cdr obj) result)
            (set-cdr! (cdr obj) '())
            result))
        ((evaluated-thunk? obj) (thunk-value obj))
        (else obj))

Normal Order And Language Design (pros and cons)

Language Design Choice 和人生中的每一个选择一样,都是 trade-off,选择 Normal Order 的 trade-off 如下:

  • pros:只在必要的时候计算

  • cons:

    1. 可能造成重复计算

    2. 不确定计算发生的时间

Memo-izing evaluation 似乎可以解决 cons1,但有时候我们希望 expression 每次都被重新计算。因此解决 Normal Order 的 cons 的本质在于让程序员来决定什么时候 evaluate expression,举例如下:

(lambda (a (b lazy) c (d lazy-memo)) ;...)
  • a、c: applicative order

  • b: 每次需要的时候都重新计算

  • d: 只计算一次就记住结果

(define (first-variable var-decls) (car var-decls))
(define (rest-variables var-decls) (cdr var-decls))
(define declaration? pair?)

(define (parameter-name var-decl)
  (if (pair? var-decl) (car var-decl) var-decl))

(define (lazy? var-decl)
  (and (pair? var-decl)
       (eq? 'lazy (cadr var-decl))))

(define (memo? var-decl)
  (and (pair? var-decl)
       (eq? 'lazy-memo (cadr var-decl))))

; 需要一直支持 value, lazy, lazy-memo 的 delay-it
(define (delay-it decl exp env)
  (cond ((not (declaration? decl))
         (l-eval exp env))
        ((lazy? decl)
         (list 'thunk exp env))
        ((memo? decl)
         (list 'thunk-memo exp env))
        (else (error "unkown declaration:" decl))))

; 以及新的 force-it
(define (force-it obj)
  (cond ((thunk? obj)                     ; eval, but don't remember it
         (actual-value (thunk-exp obj)
                       (thunk-env obj)))
        ((memoized-thunk? obj)            ; eval and remember
         (let ((result (actual-value (thunk-exp obj)
                                     (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           (set-car! (cdr obj) result)
           (set-cdr! (cdr obj) '())
           result))
        ((evaluated-thunk? obj) (thunk-evalue obj))
        (else obj)))

; 修改 l-apply
(define (l-apply procedure arguments env)          
  (cond (primitive-procedure? procedure)
        (apply-primitive-procedure
          procedure
          (list-of-arg-values arguments env)))     
        ((compound-procedure? procedure)
         (l-eval-sequence
           (procedure-body procedure)
           (let ((params (procedure-parameters procedure)))
             (extend-environment
               (map parameter-name params)                  ; 取出参数名
               (list-of-delayed-args params arguments env)  ; 把参数的设置 (actual value、lazy、lazy-memo) 传递下去
               (procedure-environment procedure)))))
         (else (error "Unkown proc" procedure))))

(define (list-of-delayed-args var-decls exps env)
  (if (no-operations? exps)
      '()
      (cons (delay-it (first-variable var-decls)
                      (first-operand exps)
                      env)
            (list-of-delayed-args
              (rest-variables var-decls)
              (rest-operands exps)
              env))))

现在我们的 Scheme Evaluator 已经支持自由定义参数的计算方式:actual value、lazy 以及 lazy-memo。

Streams

有了 Normal Order Scheme Evaluator,我们就可以从另一个角度来看待系统。以前,我们有这些方法来理解系统:

  • 把系统看作是一个 procedure,main procedure 里面可以分成 init、start、finish procedures,而这些 procedures 还可以继续被细化。这时候系统就是一个在规定时间执行规定命令的个体。

  • 把系统看作是一个容器,容器内部有不同种类、不同数量的对象,这些对象互相交流、改变状态,所有对象的状态集合就是系统的状态,系统的使用者可以从中获取自己想要的信息。

还有另外一种理解:

  • 把系统看作是时间轴上的一组状态,系统中的每个对象按时间顺序连续地输出自己的状态,从而系统能够随时知道自己的整体状况。

这里 “按时间顺序连续地输出自己的状态” 就是 Streams。

Stream Abstraction

; message passing style
(define (cons-stream x (y lazy-memo))
  (lambda (msg)
    (cond ((eq? msg 'stream-car) x)
          ((eq? msg 'stream-cdr) y)
          (else (error "unkown stream msg" msg)))))

(define (stream-car s) (s 'stream-car))
(define (stream-cdr s) (s 'stream-cdr))

; normal style
(define (cons-stream x (y lazy-memo)
  (cons x y))
(define stream-car car)
(define stream-cdr cdr)

stream 由两个部分组成,当前的值,和未来值的 promise,也可以理解成一个特殊的 pair,示意图如下:

![](/assets/Screen Shot 2018-04-13 at 11.27.02 PM.jpg)

有了它,我们可以只计算需要的部分。假设我们需要 1 - 100000000 之间的第 100 个素数,通常会这么做:

(list-ref
  (filter (lambda (x) (prime? x))
          (enumerate-interval 1 100000000))
  99)

以上代码首先会遍历 1 - 100000000 之间的所有整数,找到所有素数,再从中取第 100 个素数。显然在这里我们做了很多额外的计算。我们也可以按需去获取 1 - 100000000 之间的整数,一旦找到第 100 个素数立即停止:

(define (stream-interval a b)
  (if (> a b)
      the-empty-stream
      (cons-stream a (stream-interval (+ a 1) b))))

(stream-ref
  (stream-filter (lambda (x) (prime? x))
                 (stream-interval 1 100000000))
  99)

(define (stream-filter pred stream)
  (if (pred (stream-car stream))
      (cons-stream (stream-car stream) 
                   (stream-filter pred (stream-cdr stream)))
      (stream-filter pred 
                     (stream-cdr stream))))

既然我们只计算自己想要的数据,那么就可能存在无限大小的数据结构

例1: ones

定义 ones 为每个元素都为 1 的无限序列

(define ones (cons-stream 1 ones))
(stream-car (stream-cdr ones)) ; => 1

ones 的结构如下:

![](/assets/Screen Shot 2018-04-13 at 11.27.20 PM.jpg)

如果没有 normal order:

(define ones (cons 1 ones)) ; => error, ones undefined

因为在 procedure body 中执行 (cons 1 ones) 时 ones 尚未被定义,因此抛错;而在 normal order 的情况下,(cons-stream 1 ones) 被执行时,ones 是 lazy 的,因此不会抛错。

例2:add-stream

也可以把两个无限序列相加:

(define (add-stream s1 s2)
  (cond ((null? s1) '())
        ((null? s2) '())
        (else (cons-stream
                (+ (stream-car s1) (stream-car s2))
                (add-streams (stream-cdr s1)
                             (stream-cdr s2)))))

(define ints
  (cons-stream 1 (add-streams ones ints)))

; ones:  1 1 1 1 1 ...
; ints:  1 2 3 4 5 ...

例3:revisit primes

还有一种找素数的方法,就是从 2 开始,找到下一个整数,就忽略所有能被该整数整除的整数:

(define (sieve str)
  (cons-stream
    (stream-car str)
    (sieve (stream-filter
             (lambda (x)
               (not (divisible? x (stream-car str))))
             (stream-cdr str)))))

(define primes
  (sieve (stream-cdr ints)))

例4:integration

(define (integral integrand init dt)
  (define int
    (cons-stream
      init
      (add-streams (stream-scale dt integrand)
                   init)))

(integral ones 0 2)
; =>    0 -> 2 -> 4 -> 6 -> 8
; Ones: 1    1    1    1    1
; Scale:2    2    2    2    2

参考

Last updated