[ 目次, 前節, 次節, 索引 ]

   基本的考えは, 手続きを作用させる時, どの引数は評価し, どれは遅延するかを解釈系が決めなければならないということである. 遅延引数は評価しない; その代りそれは サンク(thunks)というオブジェクトに変換する.34 サンクは式が必要とする時, 作用の時に評価されていたかのように引数の値を生じるのに必要な情報を持っていなければならない. 従ってサンクは引数の式と手続き作用が評価された環境を含んでいなければならない.

   サンクの中の式を評価するプロセスを 強制(forcing)という.35 一般にサンクは値が必要になった時にだけ強制される: つまりサンクの値を使おうとする基本手続きに渡された時; 条件式の述語の値である時; 手続きとして作用させられる演算子の値である時である. 可能な選択の一つは, 3.5.1節の遅延オブジェクトでやったようにサンクを メモ化(memoize)するかどうかである. メモ化するとサンクが初めて強制される時, 計算した値を格納する. その後の強制は計算を繰り返すことなく, 単に格納した値を返すだけである. 多くの作用でより効率的であるから, われわれは解釈系にメモ化させよう. しかしそこにはむずかしい考察もある.36

評価器の修正

   evalの application?節は

((application? exp)
 (apply (actual-value (operator exp) env)
        (operands exp)
        env))

   式の実際の値が必要になった時には, 式の値がサンクならそれを強制するため, 単なるevalの代りに

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

   applyの新版も4.1.1節のものと殆んど同じである. 相違はevalが評価していない被演算子の式を渡していることである: (ストリクトな)基本手続きに対しては, 基本手続きを作用させる前に引数をすべて評価する; (ノンストリクトな)合成手続きに対しては, 手続きを作用させる前にすべての引数を遅延させる.

(define (apply procedure arguments env)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure
          procedure
          (list-of-arg-values arguments env)))  ; 変更した
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment
           (procedure-parameters procedure)
           (list-of-delayed-args arguments env) ; 変更した
           (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

(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)
                                env))))


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

   評価器で変更すべき他の場所はifの扱いである. そこでは述語が真か偽かテストする前に述語の値を得るため, evalの代りにactual-valueを使う必要がある:

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

   最後にdriver-loop手続き(4.1.4節)を変更し, 遅延した値が読込み-評価-印字ループに戻ってきたら, 印字の前に強制されるように, evalの代りにactual-valueを使うようにする. また, これが遅延評価器であることを示すため, 促進記号を変える:

(define input-prompt ";;; L-Eval input:")
(define output-prompt ";;; L-Eval value:")


(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output
           (actual-value input the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

   これらの変更を施すと, 評価器を起動しテストが出来る. 4.2.1節で論じたtry式の評価は成功し, 解釈系が遅延評価を実行していることを示している:

(define the-global-environment (setup-environment))

(driver-loop)

;;; L-Eval input:
(define (try a b)
  (if (= a 0) 1 b))
;;; L-Eval value:
ok

;;; L-Eval input:
(try 0 (/ 1 0))
;;; L-Eval value:
1

サンクの表現

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

   式と環境を包み込む簡単な方法の一つは, 式と環境を含むリストを作ることである. そこでサンクを次のように作り出す:

(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))

   実際, 解釈系に欲しいのは, これではなく, メモ化されたサンクである. サンクが強制された時, 格納された式を値に取り替え, 既に評価されたと認識出来るようにthunkのタグを変えて評価されたサンクに転換する. 37

(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)  ; expをその値で置き換える
           (set-cdr! (cdr obj) '())     ; 不要なenvを忘れる
           result))
        ((evaluated-thunk? obj)
         (thunk-value obj))
        (else obj)))

(define count 0)

(define (id x)
  (set! count (+ count 1))
  x)

(define w (id (id 10)))

;;; L-Eval input:
count
;;; L-Eval value:
⟨応答⟩

;;; L-Eval input:
w
;;; L-Eval value:
⟨応答⟩

;;; L-Eval input:
count
;;; L-Eval value:
⟨応答⟩

(define (square x)
  (* x x))

;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
⟨応答⟩

;;; L-Eval input:
count
;;; L-Eval value:
⟨応答⟩

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (actual-value (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

(define (for-each proc items)
  (if (null? items)
      'done
      (begin (proc (car items))
             (for-each proc (cdr items)))))

;;; L-Eval input:
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88
;;; L-Eval value:
done

(define (p1 x)
  (set! x (cons x '(2)))
  x)

(define (p2 x)
  (define (p e)
    e
    x)
  (p (set! x (cons x '(2)))))

(define (f a (b lazy) c (d lazy-memo))
  ...)

34 サンク(thunk)という用語はAlgol 60の名前呼びの実装を議論していた非公式な作業グループが発明した. 彼らは式(「についての考え(シンク)」)の解析の殆んどは翻訳時に出来ることを知った; そこで実行時には式はすでに「シンクされて(サンク)」いる (Ingerman他 1960).

35 これは3章でストリームを表現する時に説明した, 遅延オブジェクトに対する forceの使い方と類似している. ここでやろうとしていることと, 3章でやったことの重要な違いは, 遅延と強制を評価器に作り込み, これを言語を通じて一様かつ自動的にしようとしていることである.

36 メモ化と組み合せた遅延評価は, 名前呼び(call-by-name)引数渡しに対して, 必要呼び (call-by-need)引数渡しということがある. (Algol 60が導入した 名前呼びはメモ化しない遅延評価と似ている.) 言語設計者としてわれわれは評価器をメモ化するようにも, しないようにも, またプログラマの選択にすることにでも出来る(問題4.31). 3章から期待するように, この選択は代入のある場合には, 微妙で混乱した問題を惹き起す. (問題4.27と4.29参照) Clinger(1982)のすぐれた論文は, ここに生じた混乱の多くを明確化しようとしている.

37 式の値が計算されると, サンクからenvを消すことに注意しよう. そうしても解釈系の返す値には違いがない. しかしスペースを節約するのに役立つ. いまや不要になったサンクからのenvへの参照を除去すると, 5.3節で論じるように, この構造は ごみ集め(garbage collected)され, スペースは再生されるからである.

   同様に3.5.1節のメモ化した遅延オブジェクト中の不要な環境を, その値を格納した後でmemo-procに(set! proc '())のようなことをさせ(delayが評価された環境を含んでいる)手続きprocを捨て, ゴミ集めさせることが出来た.

38 この問題は遅延評価と副作用の間の相互作用が非常に紛わしくなり得ることを示す. これは3章の議論から期待出来るものである.

[ 目次, 前節, 次節, 索引 ]