SICP 読書ノート#77 - 5.5 翻訳系(2) (pp.343-360)

前回に続き翻訳系のセクションを読み進めて行きました。

5.5.2 式の翻訳

defineやset!などの特殊形式のコンパイルの話。ざっと読んだ。

5.5.3 組み合わせの翻訳

主に手続き適用のコンパイルの話。簡単にまとめると、

compile-applicationでは、演算子と非演算子がそれぞれコンパイルされ、 compile-procedure-callを呼び出す
compile-procedure-callでは、targetに返り値を格納し、実行後はlinkageに戻る、手続き適用の実行コードが生成される
手続き適用の実行コード生成の処理の本体である complie-proc-applでは、 targetがvalか否か、linkageがreturnか否か、で 4通りのコードのいずれかを生成する

個人的には、超循環評価機でもそうだったが、非演算子が評価・集約され演算子手続きに適用される振る舞いを見ると、JavaScriptの arguments[]やarguments.calleeはきっとこれなんだろうなあと、勝手に腑に落ちました。

5.5.4 命令列の組み合わせ

命令シーケンスのコンパイルの話。

要は、append-instruction-sequencesなどで命令シーケンスを連結し、 preservingで余分なスタック退避を取り除いている、ということだと思うが、処理の細かい点まで理解しようとすると結構むずかしい。

ただ、これらの手続きの出力結果としてどういうコードを生成するかがより重要だと思うので、細部は置いといて先へ進みます。

それと、脚注に結構おもしろいことが書いてあった。訳文を非公式SICP(真鍋版)より引用。

コンパイラに末尾再帰のコードを生成させるというのは素直な考え方のように思えるかもしれません。しかし、C言語やPascalを含め、一般的な言語ではこれを行わず、そのためこれらの言語では反復プロセスを手続き呼ひ出しだけで表現することはできません。これらの言語で末尾再帰が難しいのは、それらの実装ではスタックをリターンアドレスを格納するのに使うだけでなく、手続きの引数や局所変数を格納するためにも使っているからです。この本で記述されているSchemeの実装は、引数と変数をメモリに入れ、ガベージコレクションの対象にしています。変数と引数にスタックを使う理由は、ほかのところでガベージコレクションを使わない言語では、そうすることによってガベージコレクションが必要なくなり、またそれがより効率的たと一般に信じられているということです。実際のところ、高機能なLisp コンパイラは、末尾再帰を壊さずに引数のためにスタックを使うことかてきます。 (snip..) また、そもそもスタック割り当てはガベージコレクションより効率的なのかというところにも議論がありますが、この問題の詳細はコンピュータアーキテクチャの細部によるようです (snip..)

こうやって処理系を内部を追っていくと、末尾再帰やガベージコレクションを持つ・持たないの戦略の違いがわかってとても良い。

5.5.5 翻訳したコードの例

compileでSchemeのソースコードをコンパイルすると、どういったオブジェクトコードが生成されるか、という話。前に問題5.31、5.32で試してきたような内容。

問題 5.37

preservingで行っている不要なスタックの退避・復元を取り除くと、生成するコードはどう変化し、不要なスタック演算は何かを特定せよ、という問題。

preservingから不要なスタック演算を省く処理を削除する。

 (define (preserving regs seq1 seq2)
   (if (null? regs)
      (append-instruction-sequences seq1 seq2)
      (let ((first-reg (car regs)))
-      (if (and (needs-register? seq2 first-reg)
-               (modifies-register? seq1 first-reg))
            (preserving (cdr regs)
             (make-instruction-sequence
              (list-union (list first-reg)
                          (registers-needed seq1))
              (list-difference (registers-modified seq1)
                               (list first-reg))
              (append `((save ,first-reg))
                      (statements seq1)
                      `((restore ,first-reg))))
-           seq2)
-          (preserving (cdr regs) seq1 seq2)))))
+            seq2))))

問題 5.31の(f (g 'x) y)をコンパイルしてみる。

'((env continue)
  (env proc argl continue val)
  ((save continue)
   (save env)
   (save continue)
   (assign proc (op lookup-variable-value) (const f) (reg env))
   (restore continue)
   (restore env)
   (restore continue)
   (save continue)
   (save proc)
   (save env)
   (save continue)
   (assign val (op lookup-variable-value) (const y) (reg env))
   (restore continue)
   (assign argl (op list) (reg val))
   (restore env)
   (save argl)
   (save continue)
   (save env)
   (save continue)
   (assign proc (op lookup-variable-value) (const g) (reg env))
   (restore continue)
   (restore env)
   (restore continue)
   (save continue)
   (save proc)
   (save continue)
   (assign val (const x))
   (restore continue)
   (assign argl (op list) (reg val))
   (restore proc)
   (restore continue)
   (test (op primitive-procedure?) (reg proc))
   (branch (label primitive-branch1))
   compiled-branch2
   (assign continue (label after-call3))
   (assign val (op compiled-procedure-entry) (reg proc))
   (goto (reg val))
   primitive-branch1
   (save continue)
   (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
   (restore continue)
   
   ;; snip...

おお！元々のpreservingでは一切出なかったenvへのスタックの退避・復元が、 envから変数を探索する度に実行されることがわかる。問題 5.31でenvの退避・復元が出なかった理由の予想はどうやら当たっていたみたい。

次は「5.5.6 文面アドレス」から。

@uents blog

Code wins arguments.