@uents blog

Code wins arguments.

SICP 読書ノート#79 - 5.5 翻訳系(4) (pp.362-366)

SICP Scheme

いよいよ最後のセクション。練習問題はやってないです。

5.5.7 翻訳したコードと評価器のインターフェース

(compile)でコンパイルしたコードを積極制御評価器で動作させる。

いつものように、まずはRacketで動かせるようにした。

https://github.com/uents/sicp/tree/master/ch5.5.7-interfacing-compiler-to-evaluator

評価器のトレースを有効にして、かんたんな手続きをコンパイルしてみる。

eceval-compiler.scm<feff>> (eceval 'trace-on)

eceval-compiler.scm<feff>> (compile-and-go '(define (add1 x) (+ x 1)))
'(label = controller)
'(inst = (assign compapp (label compound-apply)))
'(inst = (branch (label external-entry)))
'(label = external-entry)
'(inst = (perform (op initialize-stack)))
'(inst = (assign env (op get-global-environment)))
'(inst = (assign continue (label print-result)))
'(inst = (goto (reg val)))
'(inst = (assign val (op make-compiled-procedure) (label entry1) (reg env)))
'(inst = (goto (label after-lambda2)))
'(label = after-lambda2)
'(inst = (perform (op define-variable!) (const add1) (reg val) (reg env)))
'(inst = (assign val (const ok)))
'(inst = (goto (reg continue)))
'(label = print-result)
'(inst = (perform (op print-stack-statistics)))
'(total-pushes = 0 max-depth = 0 curr-depth = 0)
'(inst = (perform (op announce-output) (const ";;; EC-Eval value:")))

;;; EC-Eval value:
'(inst = (perform (op user-print) (reg val)))
ok

;; (snip ...)
  • (assign val (op make-compiled-procedure) (label entry1) (reg env)))で 戻り先はentry1となるよう手続きをコンパイルし、その実体をvalに格納
  • (perform (op define-variable!) (const add1) (reg val) (reg env)))で コンパイル済みの手続きをadd1という変数に束縛
  • valに'okを格納してREPLに戻る

といった流れ。

次に、コンパイル済みの手続きを実行してみる。 出だしの処理はこれまで見てきた内容と同じなので詳細は割愛するが、 ev-application以降の処理で procとarglに手続きと引数が格納され、apply-dispatchへジャンプする

;;; EC-Eval input:
(add1 5)

'(inst = (assign env (op get-global-environment)))
'(inst = (assign continue (label print-result)))
'(inst = (goto (label eval-dispatch)))
'(label = eval-dispatch)

;; (snip ...)

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

apply-dispatchからこのセクションで追加したcompiled-applyへジャンプ。 さらに先程のentry1へとジャンプする。

'(label = apply-dispatch)
'(inst = (test (op primitive-procedure?) (reg proc)))
'(inst = (branch (label primitive-apply)))
'(inst = (test (op compound-procedure?) (reg proc)))
'(inst = (branch (label compound-apply)))
'(inst = (test (op compiled-procedure?) (reg proc)))
'(inst = (branch (label compiled-apply)))
'(label = compiled-apply)
'(inst = (restore continue))
'(inst = (assign val (op compiled-procedure-entry) (reg proc)))
'(inst = (goto (reg val))) ;;=> ここで`entry1`へジャンプ

すでにprocにはコンパイル済みの手続き (この場合はCompound Procedureのような複合手続き)が格納されているため、 それに対してarglの非演算子を適用する。

返り値はvalに格納され、REPLへと戻る。

'(label = entry1)
'(inst = (assign env (op compiled-procedure-env) (reg proc)))
'(inst = (assign env (op extend-environment) (const (x)) (reg argl) (reg env)))
'(inst = (assign proc (op lookup-variable-value) (const +) (reg env)))
'(inst = (assign val (const 1)))
'(inst = (assign argl (op list) (reg val)))
'(inst = (assign val (op lookup-variable-value) (const x) (reg env)))
'(inst = (assign argl (op cons) (reg val) (reg argl)))
'(inst = (test (op primitive-procedure?) (reg proc)))
'(inst = (branch (label primitive-branch3)))
'(label = primitive-branch3)
'(inst = (assign val (op apply-primitive-procedure) (reg proc) (reg argl)))
'(inst = (goto (reg continue)))
'(label = print-result)
'(inst = (perform (op print-stack-statistics)))
'(total-pushes = 5 max-depth = 3 curr-depth = 0)
'(inst = (perform (op announce-output) (const ";;; EC-Eval value:")))

;;; EC-Eval value:
'(inst = (perform (op user-print) (reg val)))
6

;; (snip ...)

細かくは理解できていないけど、targetとlinkageをうまく使うことで、 積極制御評価器とコンパイル済みコードを繋ぐことができる。

解釈と翻訳

まとめるとこんな感じでしょうか。

  • 解釈系と翻訳系の利点の違い

    • 解釈系(インタプリタ)はプログラムの実行ステップが 抽象化によって構成されているので、 対話的なプログラミングやデバッグに優れている。(§4.1や§5.4で見た通り)
    • 翻訳系(コンパイラ)はプログラムの実行ステップが、 機械語によって構成されているので、ずっと高速に実行でき、 高レベルの抽象化の壁を超えた最適化も行える。(§5.5で見た通り)

  • 異なるマシンアーキテクチャへの言語の移植戦略

    • 大きくは2つの戦略に分かれる
      1. 積極制御評価器をベースにして、新しいマシン命令に置き換える
      2. 翻訳系をベースにして、新しいマシンコードを生成するよう ジェネレータを作り替える
    • 2つ目の戦略の場合、元のLispシステムで動くコンパイラをコンパイルして それをコンパイル済みの実行時ライブラリとリンクすることで、 どんなLispプログラムでも実行できるようになる

§4の超循環評価器から§5かけて、処理系の中へ中へと入っていくと、 様々な観点でインタプリタとコンパイラの本質が浮き彫りになって理解が深まる。

というわけで、やっと読み終わりました。最後にまとめたいと思います。

※「SICP読書ノート」の目次はこちら