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

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))
 ;;; EC-Eval value:
ok

 ;;; EC-Eval input:
(factorial 5)
;;; EC-Eval value:
120

   評価器に翻訳したコードが扱える(例えば, 上のようにfactorial の呼出しを評価する)ようにするには, apply-kdispatch (5.4.1節)にあるコードを変更し, (合成手続きや基本手続きとも違う)翻訳した手続きを認識するようにし, 制御を翻訳したコードの入り口に直接飛び越すようにしなければならない:48

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


compiled-apply
  (restore continue)
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))

   評価器計算機を起動した時, 翻訳したプログラムが走らせられるよう, 評価器計算機の先頭にbranch命令を追加し, flagレジスタが設定してあれば, 計算機に新しい入り口へ行かせる.49

  (branch (label external-entry))      ; flagが設定してあれば分岐する
read-eval-print-loop
  (perform (op initialize-stack))
  ...

external-entry
  (perform (op initialize-stack))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (reg val))

   手続き定義を翻訳し, 翻訳したコードを実行し, 読込み-評価-印字ループを走らせる次の手続きが使えるので, 手続きを試すことが出来る. 翻訳したコードは, 結果をvalに置き, continueにある場所へ戻って欲しいので, 式を標的valと接続returnで翻訳する. 翻訳で出来た目的コードを, 評価器レジスタ計算機で実行可能な命令に変換するにはレジスタ計算機シミュレータ(5.2.2節)の手続きassembleを使う. 次にvalレジスタを初期化し, 命令のリストを指すようにし, 評価器が external-entryへ行くようflagを設定し, 評価器を起動する.

(define (compile-and-go expression)
  (let ((instructions
         (assemble (statements
                    (compile expression 'val 'return))
                   eceval)))
    (set! the-global-environment (setup-environment))
    (set-register-contents! eceval 'val instructions)
    (set-register-contents! eceval 'flag true)
    (start eceval)))

   5.4.4節の最後のようにスタックの監視が設定してあれば, 翻訳したコードのスタック使用を調べることが出来る.

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))

(total-pushes = 0 maximum-depth = 0)
 ;;; EC-Eval value:
ok

 ;;; EC-Eval input:
(factorial 5)
(total-pushes = 31 maximum-depth = 14)
;;; EC-Eval value:
120

解釈と翻訳

   解釈と翻訳の切替えは, 言語を新しい計算機へ 移植する別の戦略をもたらす. Lispを新しい計算機に実装したいとする. 戦略の一つは5.4節の積極制御評価器から始め, その命令を新しい計算機の命令へ翻訳する. 別の戦略は翻訳系から始め, 新しい計算機のコードを生成するように, コード生成器を変更する. この第二の戦略は, 元々のLispシステムで走っている翻訳系で任意のLispプログラムを最初に翻訳し, 実行時ライブラリの翻訳版と連結することで, それを新しい計算機で走らせるのを可能とする.53 もっとよいのは翻訳系自身を翻訳し, これを新しい計算機上で他のLispプログラムを翻訳するために走らせるのである.54 あるいは4.1節の解釈系の一つを翻訳し, 新しい計算機の上で走る解釈系を作ることも出来る.

問題 5.45

翻訳したコードの使うスタック演算を, 同じ計算に対する評価器の使うスタック演算と比べると, (スタック演算の総数を減らして)速度と(最大スタック深さを減らして)スペースの両方で翻訳系がスタックの使い方を最適化する程度を決めることが出来る. この最適化したスタックの使い方を, 同じ計算に対する特殊目的の計算機の性能と比べると, 翻訳系の品質のある種の表示が得られる.

a. 問題5.27は, 上に示した再帰的階乗手続きによるn!の計算で, 評価器が必要とするプッシュの回数と最大スタック深さをnの関数として決めよといった. 問題5.14は図5.11に示した特殊目的の階乗計算機で同じ計測をせよといった. 今度は翻訳したfactorialを使って同じ解析を行え.

   翻訳版のプッシュの回数の, 解釈版のプッシュの回数に対する比を求め, 最大スタック深さについても同じことを行え. n!を計算するのに使う演算の数と, スタック深さはnに線形なので, これらの比はnが大きくなるにつれ, 定数に近づく筈である. この定数は何か. 同様に特殊目的の計算機のスタック使用と解釈版の使用に対する比を求めよ.

   特殊目的のコード対解釈されるコードの比を, 翻訳するコード対解釈されるコードの比と比べよ. 手で加工した制御コードは, われわれの発達途上の万能目的の翻訳系の作ったものより遥かに優れているので, 特殊目的計算機は, 翻訳したコードよりも遥かに優れていることがわかる.

b. 性能において, 手で加工した版に近づくようなコードを生成するのを支援するような翻訳系の改良は何か.

問題 5.46

問題5.45のような解析を行い, 図5.12の特殊目的Fibonacci計算機を使った有効性と比較して, 木構造再帰のFibonacci手続き

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

  (assign compapp (label compound-apply))
  (branch (label external-entry))      ; flagが設定してあれば分岐する
read-eval-print-loop
  ...

;;; EC-Eval input:
(compile-and-run
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))
;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)
;;; EC-Eval value:
120

48 もちろん, 翻訳した手続きは, 解釈する手続き同様に(基本ではない)合成手続きである. 積極制御評価器で使った用語との整合性から, 本節では(翻訳に対し)解釈されるという意味に「合成」を使う.

49 評価器計算機が branchで始るので, 評価器計算機を起動する前に常にflagレジスタを初期化しなければならない. 計算機を通常の読込み-評価-印字ループから起動するためには

(define (start-eceval)
  (set! the-global-environment (setup-environment))
  (set-register-contents! eceval 'flag false)
  (start eceval))

(define (user-print object)
  (cond ((compound-procedure? object)
         (display (list 'compound-procedure
                        (procedure-parameters object)
                        (procedure-body object)
                        ')))
        ((compiled-procedure? object)
         (display '))
        (else (display object))))

   CやC++のような人気のプログラム言語の翻訳系は, 走っているコードにエラー検出演算を殆んど入れず, 出来るだけ高速で走らせる. その結果, エラー検出を陽に用意するのはプログラマに任せる. 困ったことに速度が制約でない危険なプログラムでも, 人々はこれを忘れ, そのプログラムは高速で危険な生涯を歩む. 例えば1988年にインターネットを麻痺させた悪名の 「ワーム」は, UNIX^TM操作系の, fingerデモンで入力バッファが溢れたかどうかの検出に関する欠陥をついたものである. (Spafford 1989参照)

53 もちろん解釈戦略でも翻訳戦略でも, 記憶割当て, 入出力および評価器や翻訳系の議論の中で「基本的」として来た各種の演算を, 新しい計算機用に実装しなければならない. この作業を最小にする戦略の一つは, これらの演算の出来るだけ多くをLispで書き, 新しい計算機に翻訳することである. ついにはすべては, 新しい計算機用にハンドコードした(ごみ集めや実際の計算機の基本命令の作用などの)小さいカーネルに集約される.

54 この戦略は翻訳した翻訳系を使い, プログラムを新しい計算機で翻訳したものが, 元々のLispシステムでそのプログラムを翻訳したものと同一かの検査など, 翻訳系の正しさの楽しいテストになる. 結果は微小な細部に極めて敏感なので, 相違の根源の追跡は面白いがいらいらもする.

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