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

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

   factorialが呼び出される度に, 評価器は本体がif式であることを知り, 述語を取り出さなければならない. その後初めて述語を評価し, その値に従って振り分けることが出来る. 式(* (factorial (- n 1)) n)を, またはその部分式(factorial (- n 1))および(- n 1)を評価する度, 評価器はevalの中で場合分けを行い, 式が作用であることを知り, 演算子と被演算子を取り出さなければならない. この解析は高価である. それを繰り返し行うのは無駄である.

   構文解析が一回だけ実行されるよう配慮して, 評価器を遥かに効率よく変形することが出来る.28 式と環境をとるevalを二つに分ける. 手続きanalyzeは式だけをとる. これは構文解析を実施し, 解析された式を実行する時になすべき仕事をカプセル化した新しい手続き, 実行手続き(execution procedure)を返す. 実行手続きは引数として環境をとり, 評価を完成する. こうすると実行手続きが何回呼び出されても, 一つの式についてanalyzeは一回だけしか呼び出されないので, 仕事は節約になる.

   解析と実行を分離するとevalは

(define (eval exp env)
  ((analyze exp) env))

   analyzeを呼び出した結果は環境に作用させる実行手続きになる. analyze手続きは, われわれが振り分けた手続きが, 解析するだけで評価はしないという点以外は, 4.1.1節の元々のevalが実行するのと同じ場合分けである:

(define (analyze exp)
  (cond ((self-evaluating? exp) 
         (analyze-self-evaluating exp))
        ((quoted? exp) (analyze-quoted exp))
        ((variable? exp) (analyze-variable exp))
        ((assignment? exp) (analyze-assignment exp))
        ((definition? exp) (analyze-definition exp))
        ((if? exp) (analyze-if exp))
        ((lambda? exp) (analyze-lambda exp))
        ((begin? exp) (analyze-sequence (begin-actions exp)))
        ((cond? exp) (analyze (cond->if exp)))
        ((application? exp) (analyze-application exp))
        (else
         (error "Unknown expression type -- ANALYZE" exp))))

   自己評価式を扱う最も単純な構文解析手続きはこうだ. それは環境引数を無視し, 式を返す実行手続きを返す:

(define (analyze-self-evaluating exp)
  (lambda (env) exp))

   クォート式では, 実行フェーズではなく, 解析フェーズでクォート引用の本文を一回取り出すだけで, 多少の効率を得る.

(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env) qval)))

   変数の値の探索は, 環境を知ることに依存するので, 実行フェーズに行わなければならない.29

(define (analyze-variable exp)
  (lambda (env) (lookup-variable-value exp env)))

   analyze-assignmentもまた変数の実際の設定を, 環境が用意される実行まで延期する. しかし, assignment-value式が解析時に(再帰的に)解析出来るという事実は, assignment-value式は一回だけ解析されるので, 効率に大きく貢献する. 同じことは定義でも成り立つ.

(define (analyze-assignment exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze (assignment-value exp))))
    (lambda (env)
      (set-variable-value! var (vproc env) env)
      'ok)))

(define (analyze-definition exp)
  (let ((var (definition-variable exp))
        (vproc (analyze (definition-value exp))))
    (lambda (env)
      (define-variable! var (vproc env) env)
      'ok)))

   if式には解析時に述語, 帰結部および代替部を取り出し, 解析する.

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env)
      (if (true? (pproc env))
          (cproc env)
          (aproc env)))))

   lambda式の解析は, 効率に大きな利益をもたらす: lambdaの評価の結果の手続きが多数回作用されようとも, lambda本体は一回だけ解析される.

(define (analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (analyze-sequence (lambda-body exp))))
    (lambda (env) (make-procedure vars bproc env))))

   (beginやlambda式の本体の中のような)式の並びの解析はずっと複雑である.30 並びの中のそれぞれの式を解析し, 実行手続きを作り出す. これらの実行手続きを組み合せ, 環境を引数としてとり, 個々の実行手続きを環境を引数として順に呼び出す一個の実行手続きを作る.

(define (analyze-sequence exps)
  (define (sequentially proc1 proc2)
    (lambda (env) (proc1 env) (proc2 env)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc (car rest-procs))
              (cdr rest-procs))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence -- ANALYZE"))
    (loop (car procs) (cdr procs))))

   手続き作用を解析するには, 演算子と被演算子を解析し, (実際に作用させる手続きを得るために)演算子の実行手続きと, (実際の引数を得るために)被演算子の実行手続きを呼び出す実行手続きを構成する. 次にこれを4.1.1節のapplyに似たexecute-applicationへ渡す. execute-applicationはapplyとは, 合成手続きの手続き本体は既に解析してあるので, 更に解析する必要はないという点だけが異る. 解析はせず, 本体の実行手続きを拡張された環境に対して呼び出すだけである.

(define (analyze-application exp)
  (let ((pproc (analyze (operator exp)))
        (aprocs (map analyze (operands exp))))
    (lambda (env)
      (execute-application (pproc env)
                           (map (lambda (aproc) (aproc env))
                                aprocs)))))


(define (execute-application proc args)
  (cond ((primitive-procedure? proc)
         (apply-primitive-procedure proc args))
        ((compound-procedure? proc)
         ((procedure-body proc)
          (extend-environment (procedure-parameters proc)
                              args
                              (procedure-environment proc))))
        (else
         (error
          "Unknown procedure type -- EXECUTE-APPLICATION"
          proc))))

   新しい評価器は, 4.1.2, 4.1.3および4.1.4節のと同じデータ構造, 構文手続き, 実行時の支援手続きを使う.

問題 4.22

本節の評価器を拡張し, 特殊形式letが使えるようにせよ. (問題4.6参照)

問題 4.23

Alyssa P. Hackerはanalyze-sequenceがなぜそう複雑でなければならないか分らなかった. 他の解析手続きは, 4.1.1節の対応する評価手続き(またはeval節)の直截的な変換である. 彼女はanalyze-sequenceは

(define (analyze-sequence exps)
  (define (execute-sequence procs env)
    (cond ((null? (cdr procs)) ((car procs) env))
          (else ((car procs) env)
                (execute-sequence (cdr procs) env))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence -- ANALYZE"))
    (lambda (env) (execute-sequence procs env))))

   analyze-sequenceの二つの版を比較せよ. 例えば並びが一つの式しか持たない通常の場合(手続き本体がそうだが)を考えよ. Alyssaのプログラムが作った実行手続きはどういう仕事をするだろうか. 上の本文のプログラムの作った実行手続きはどうか. 二つの式を持つ並びについて, 二つの版はどう違うか.

問題 4.24

始めの超循環評価器と本節での版の速度を比較するため実験をいくつか設計して実行せよ. その結果を使い, いろいろな手続きでの解析と実行に使われる時間の割合を見積れ.

28 この技法は翻訳プロセスの中心部分であり, 5章で論じる. Jonathan Reesは1982年頃, これに似たTプロジェクト用のScheme解釈系を書いた (Reesおよび Adams 1982). Marc Feeley(1986) (Feeleyおよび Lapalme 1987も参照)は修士論文で, この技法を独立に発明した.

29 しかし構文解析の部分として実行出来る変数探索の重要な部分がある. 5.5.6節で示すように, 変数の値を見つけるべき環境構造での場所を決定することが出来, 変数に対応する見出しに対し環境を走査する必要を除去する.

30 式の並びの処理へのある洞察につていは問題4.23参照.

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