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

eval-dispatch
  (test (op self-evaluating?) (reg exp))
  (branch (label ev-self-eval))
  (test (op variable?) (reg exp))
  (branch (label ev-variable))
  (test (op quoted?) (reg exp))
  (branch (label ev-quoted))
  (test (op assignment?) (reg exp))
  (branch (label ev-assignment))
  (test (op definition?) (reg exp))
  (branch (label ev-definition))
  (test (op if?) (reg exp))
  (branch (label ev-if))
  (test (op lambda?) (reg exp))
  (branch (label ev-lambda))
  (test (op begin?) (reg exp))
  (branch (label ev-begin))
  (test (op application?) (reg exp))
  (branch (label ev-application))
  (goto (label unknown-expression-type))

単純式の評価

ev-self-eval
  (assign val (reg exp))
  (goto (reg continue))

ev-variable
  (assign val (op lookup-variable-value) (reg exp) (reg env))
  (goto (reg continue))

ev-quoted
  (assign val (op text-of-quotation) (reg exp))
  (goto (reg continue))

ev-lambda
  (assign unev (op lambda-parameters) (reg exp))
  (assign exp (op lambda-body) (reg exp))
  (assign val (op make-procedure)
              (reg unev) (reg exp) (reg env))
  (goto (reg continue))

手続き作用の評価

   作用の評価を始めるには, 演算子を評価し, 後になって評価された被演算子に作用させられる手続きを作る. 演算子を評価するには, それをexpレジスタに移し, eval-dispatchへいく. 演算子を評価する時のenv レジスタの環境はすでに正しいものである. しかし後で被演算子を評価する時にそれを必要とするので, envを退避する. また被演算子も取り出してunevに置き, これをスタックに退避する. また演算子を評価した後, eval-dispatchがev-appl-did-operatorから再開出来るようcontinueを設定する. しかしまずは制御が作用の後, どこから継続するか制御器に伝えるcontinueの古い値を退避する.

ev-application
  (save continue)
  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-appl-did-operator))
  (goto (label eval-dispatch))

   演算子部分式の評価から戻ると, 組合せの被演算子の評価と, arglに保持したリストへの結果の引数の蓄積に進む. まず未評価の被演算子と環境を回復する. arglを空リストに初期化する. 次に演算子を評価して得た手続きをprocレジスタに代入する. 被演算子がなければ, 直接apply-dispatchへ行く. それ以外はprocをスタックに退避し, 引数評価ループを始める.22

ev-appl-did-operator
  (restore unev)                  ; 被演算子
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))         ; 演算子
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)

   引数評価ループの各サイクルはunevのリストの被演算子を評価し, 結果をarglに蓄積する. 被演算子を評価するには, それをexpレジスタに置き, 引数蓄積フェーズから実行を再開するようにcontinueを設定してからeval-dispatchへ進む. しかしまずこれまで蓄積した(arglにある)引数, (envにある)環境と(unevにある)評価すべき残りの引数を退避する. 最後の被演算子の評価は特別で, ev-appl-last-argが扱う.

ev-appl-operand-loop
  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)
  (assign continue (label ev-appl-accumulate-arg))
  (goto (label eval-dispatch))

   被演算子が一つ評価されると, 値はarglにあるリストへ蓄積される. 次に引数がunevの未評価のリストから外され, 引数評価から続行する.

ev-appl-accumulate-arg
  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))
  (goto (label ev-appl-operand-loop))

   最後の引数の評価は特別に扱う. 環境や未評価被演算子は最後の被演算子の評価後は必要ないので, eval-dispatchへ行く前にそれらを退避することはない. そこで評価からは特別な入り口 ev-appl-accum-last-argへ戻り, それが引数リストを回復し, 新しい引数を蓄積し, 退避した手続きを回復し, 作用を実行しに行く.23

ev-appl-last-arg
  (assign continue (label ev-appl-accum-last-arg))
  (goto (label eval-dispatch))
ev-appl-accum-last-arg
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

   引数評価ループの細部は, 解釈系が組合せの被演算子を評価する順(つまり左から右か右から左か---問題3.8参照)を決める. この順は超循環評価器では, それを実装する基盤のScheme の制御構造を継承するので, 決らなかった.24 (ev- appl-operand-loopがunevから次々と被演算子の取出しに使う)first-operand選択子がcarとして, またrest- operands選択子がcdrとして実装されるので, 積極制御評価器では, 組合せの被演算子を左から右の順で評価することになる.

手続き作用

apply-dispatch
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-apply))
  (test (op compound-procedure?) (reg proc))  
  (branch (label compound-apply))
  (goto (label unknown-procedure-type))

   基本手続きのそれぞれは, 引数をarglから取り, 結果をvalに置くよう実装してあると仮定する. 計算機が基本手続きをどう扱うか規定するには, 制御器命令の列が基本手続きを実装するよう, またprimitive-applyがprocの内容で識別した基本手続きの命令へ振り分けるよう準備しなければならない. われわれは, 基本手続きの細部より, 評価処理の構造に関心があるので, いまはそうではなく, procの手続きをarglの引数に作用させるapply-primitive-procedure演算を使うことにする. 5.2節のシミュレータで評価器をシミュレートする目的には, 4.1.4節の超循環評価器でやったように, 作用を実行するのに基盤のSchemeを呼び出す手続きapply-primitive-procedureを使う. 基本手続き作用の値を計算してから, continueを回復し, 指示された入り口へ進む.

primitive-apply
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
  (restore continue)
  (goto (reg continue))

   合成手続きの作用は, 超循環評価器と全く同様に行う. 手続きのパラメタを引数に束縛するフレームを構成し, 手続きが持ち込んだ環境を拡張するのにこのフレームを使い, この拡張された環境で, 手続きの本体となる式の並びを評価する. 次の5.4.2節に述べるev-sequenceが並びの評価を扱う.

compound-apply
  (assign unev (op procedure-parameters) (reg proc))
  (assign env (op procedure-environment) (reg proc))
  (assign env (op extend-environment)
              (reg unev) (reg argl) (reg env))
  (assign unev (op procedure-body) (reg proc))
  (goto (label ev-sequence))

   compound-applyは解釈系でenvレジスタに新しい値を代入する唯一の場所である. 超循環評価器と同様に, 手続きの持ち込んだ環境と, 引数リストと束縛される変数の対応するリストから, 新しい環境を構成する.

20 われわれの制御器では, 振分けはtestとbranchの列として書いてある. 別のやり方として連続したテストの実行を避けるためと新しい式の型の定義に備えるため, データ主導風に書くことが出来たかも知れない. (実際のシステムは恐らくそうなっているであろう.) Lispを走らせるように設計した計算機は, そういうデータ主導振分けを効率よく実行するdispatch-on-type命令を恐らく持っているであろう.

21 これはアルゴリズムを, Lispのような手続き言語から, レジスタ計算機言語へ変換する時重要で微妙な点である. 必要なものだけ退避するのに対し, もう一つの方法として, 各再帰呼出しの前に(valを除く) すべてのレジスタを退避することが出来る. これを フレームスタック (framed-stack)流という. これはうまくいくが, 必要以上のレジスタを退避するであろう; これはスタック演算が高価なシステムでは重要な考察となろう. その内容が後で必要でないレジスタを退避するのはまた, 普通ならごみ集めされ, スペースの再利用に解放する不要なデータを保持することになる.

22 4.1.3節の評価器データ構造手続きに, 引数リストを操作する次の二つの手続きを追加する:

(define (empty-arglist) '())

(define (adjoin-arg arg arglist)
  (append arglist (list arg)))

(define (last-operand? ops)
  (null? (cdr ops)))

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