計算機プログラムの構造と解釈第二版

4.1.1 評価器の中核

評価プロセスは二つの手続き: evalとapplyの間の相互作用として記述出来る.

図4.1 eval-applyの輪は計算機言語の本質を見せる

eval

evalは引数として式と環境をとる. 式を分類して評価を振り分ける. evalは評価すべき式の構文の型の場合分けの構造とする. 手続きを一般的に保つため, 式の型の決定を抽象的に表現し, 式の型の特定の表現には関与しない. 式の各型にはそれをテストする述語と要素を選択する抽象手段がある. この 抽象構文(abstract syntax)は同じ評価器を使いながら, 別の構文手続きの集りがあれば, 言語の構文の変更が出来ることを見るのを容易にする.

基本式

• 数値のような自己評価式に対してevalは式それ自身を返す.

• evalは値を得るため, 環境で変数を探す必要がある.

特殊形式

• クォート式に対して, evalはクォートされている式を返す.

• 変数への代入(または変数の定義)は変数に対応づける新しい値を計算するため, evalを再帰的に呼び出す必要がある. 変数の束縛を修正し(または作り出し)て環境を修正する.

• if式は, 述語が真なら帰結式を評価し, そうでなければ代替式を評価するよう, 要素式の特別な処理を必要とする.

• lambda式はlambda式が指定したパラメタと本体を, 評価の環境とともに詰め合せ, 作用可能な手続きへ変換する必要がある.

• begin式は, 要素式の並びを現れる順に評価する必要がある.

• condによる場合分けはif式の入れ子に変換してから評価する.

組合せ

• 手続き作用に対して, evalは組合せの演算子部分と被演算子部分を再帰的に評価する必要がある. 結果の手続きと引数はapplyに渡され, それが実際の作用を扱う.

evalの定義は次の通り:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))

分り易さのため, evalはcondを使った場合分けとして実装してある. この欠点は, われわれの手続きは識別可能な型しか扱えず, evalの定義を編集せずには新しい型が追加出来ないことである. Lispの殆んどの実装では, 式の型による振分けはデータ主導の流儀で行われている. これにより利用者はeval自身の定義を修正することなく, evalに認識可能な式の新しい型を追加することが出来る. (問題4.3参照)

apply

applyは二つの引数, 手続きと, 手続きを作用させる引数のリストをとる. applyは手続きを二つに場合分けする: 基本演算を作用させるのに, apply-primitive-procedureを呼び出す; 合成手続きは手続きの本体を構成する式を順に評価して作用させる. 合成手続きの本体の評価における環境は, 手続きによって持ち込まれた基本の環境を, 手続きのパラメタと手続きを作用させようとする引数を束縛するフレームへ拡張して構成する. applyの定義は次の通り:


(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

手続きの引数

evalが手続き作用を評価する時, 手続きを作用させる引数のリストを作り出すため, list-of-valuesを使う. list-of-valuesは引数として組合せの被演算子をとり, 各被演算子を評価し, 対応する値のリストを返す:5


(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values (rest-operands exps) env))))

条件式

eval-ifはif式の述語部を与えられた環境で評価する. 結果が真なら, eval-ifは帰結部を評価し, そうでなければ代替部を評価する:


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

eval-ifでのtrue?は被実装言語と実装言語の間の接続の問題を明確にする. if-predicateは被実装言語で評価され, 従ってその言語の値を返す. 解釈系の述語true?はその値を, 実装言語のifでテスト出来る値に変換する. 真の値の超循環表現は, 基底のSchemeのそれと同じでないかも知れない.6

並び

eval-sequenceは, applyが手続き本体中の要素式の並びの評価に, またevalがbegin式中の要素式の並びの評価に使う. 引数として式の並びと環境をとり, 現れる順に式を評価する. 返す値は最後の式の値である.


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

代入と定義

次の手続きは変数への代入を扱う. 代入する値を見つけるためにevalを呼び出し, 変数と結果の値をset-variable-value!に渡し, 指示した環境に設定させる.


(define (eval-assignment exp env)
  (set-variable-value! (assignment-variable exp)
                       (eval (assignment-value exp) env)
                       env)
  'ok)

変数の定義も同じように扱う.7


(define (eval-definition exp env)
  (define-variable! (definition-variable exp)
                    (eval (definition-value exp) env)
                    env)
  'ok)

ここでは代入や定義の値として記号okを返すようにした.8

問題 4.1

超循環評価器が被演算子を左から右へ評価するか, 右から左へ評価するかわれわれには分らない. 評価順は基盤のLispから引き継いでいる. list-of-valuesのconsの引数が左から右へ評価されるなら, list-of-valuesも被演算子を左から右へ評価する; consの引数が右から左へ評価されるなら, list-of-valuesも被演算子を右から左へ評価する.

基盤のLispの評価の順と無関係に被演算子を左から右へ評価するlist-of-valuesを書け. また被演算子を右から左へ評価するlist-of-valuesを書け.

5 evalの中のapplication?節はmapを使用(し, operandsがリストを返すよう要求)する方が, list-of-values手続きをわざわざ書くより簡単だったかも知れない. ここでmapを使わなかったのは, 評価器は, それが扱う言語に高階手続きがあったとしても, 高階手続きを使わずに実装出来(る, 従って高階手続きを持たない言語ででも書け)るという事実を強調するためである.

6 この場合, 被実装言語と実装言語は同じである. true?の意味を熟考すれば, 物質を乱用せずに意識を拡大する. [麻薬常習者との連想]

7 殆んどの場合正しく動くがdefineの実装は内部定義の扱いにある微妙な問題を無視している. この問題が何であり, いかに解決すべきかを, 4.1.6節で見よう.

8 defineとset!を説明した時述べたように, これらの値はSchemeでは実装依存である---つまりどういう値を返すかは実装者が選んでよい.

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