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

   明確なbegin式は, 評価すべき式の並びをunevに置き, continueをスタックに退避し, ev-sequenceへ行くことで評価する.

ev-begin
  (assign unev (op begin-actions) (reg exp))
  (save continue)
  (goto (label ev-sequence))

   入り口ev-sequenceとev-sequence-continueは, 並びの式を順に評価するループを形成する. 未評価の式のリストはunevに保存する. 各式を評価する前, 並びには評価すべき式がまだあるか調べる. そうであれば(unevにある)評価する式の並びと, これらをそこで評価しなければならない(envにある)環境を退避し, 式を評価すべくeval-dispatchを呼び出す. 退避した二つのレジスタは, この評価から戻った時, ev-sequence-continueで回復する.

   並びの最後の式は入り口ev-sequence-last-expで別に扱う. この後には評価すべき式がないので, eval-dispatchへ行く前にunevとenvを退避する必要はない. 並び全体の値は最後の式の値なので, 最後の式の評価の後は, (ev-beginかev-applicationが退避した)現在のスタックが保持している入り口から継続すること以外には, やるべきことはない. eval-dispatchがここに戻るよう, continueを設定し, continueをスタックから回復してその入り口から続行する代りに, eval-dispatchが式の評価後, その入り口へ続行するよう, eval-dispatchへ行く前にスタックからcontinueを回復する.

ev-sequence
  (assign exp (op first-exp) (reg unev))
  (test (op last-exp?) (reg unev))
  (branch (label ev-sequence-last-exp))
  (save unev)
  (save env)
  (assign continue (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-last-exp
  (restore continue)
  (goto (label eval-dispatch))

末尾再帰

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

   われわれの評価器は, 並びの最後の式を評価するのに, 情報をスタックに退避せず, 直接eval-dispatchへ行くので, 末尾再帰的である. つまり並びの最後の式は---それが, (手続き本体の最後の式であるif式がsqrt-iterの呼出しに変るsqrt-iterのような)手続き呼出しであっても---情報のスタックへのため込みを惹き起すことはない.26

   この場合, 情報の退避は不必要だという事実を利用しようと考えないなら, [超循環評価器の]eval-sequenceを並びの中のすべての式を同じように扱う---レジスタを退避し, 式を評価し, レジスタを回復すべく戻り, すべての式を評価するまでこれを繰り返す---実装をしたであろう.27

ev-sequence
  (test (op no-more-exps?) (reg unev))
  (branch (label ev-sequence-end))
  (assign exp (op first-exp) (reg unev))
  (save unev)
  (save env)
  (assign continue (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-end
  (restore continue)
  (goto (reg continue))

   これは並びを評価する前のプログラムへの小さい変更のように見える: 唯一の違いは並びの最後の式まで, 他と同様に退避回復サイクルをやることである. 解釈系はどの式にも同じ価値を与える. しかしこの変更は, 末尾再帰的実装では, 並びの最後の式の評価の後, (不要の)レジスタの退避を回復するために戻らなければならないので, 致命的である. これらの余分な退避は手続き呼出しの入れ子の間, たまる. 従ってsqrt-iterのようなプロセスは, 固定数のスペースを必要とするのではなく, 反復回数に比例するスペースを必要とする. この違いは重大である. 例えば末尾再帰では無限ループは, 手続き呼出し機構:

(define (count n)
  (newline)
  (display n)
  (count (+ n 1)))

25 5.1節でそういうプロセスをスタックのないレジスタ計算機でどう実装するか見た; プロセスの状態は, 固定個のレジスタに格納された.

26 ev-sequenceでの末尾再帰の実装は多くのコンパイラが行う周知の最適化技法の一つの変形である. 手続き呼出しで終る手続きのコンパイルでは, 呼出しを, 呼ばれた手続きの入り口へのジャンプで取り替えることが出来る. この戦略を, 本節でやったように解釈系に組み込むと, 言語全体で一様に最適化出来るようになる.

27 no-more-exps?を次のように定義出来る:

(define (no-more-exps? seq) (null? seq))

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