読者です 読者をやめる 読者になる 読者になる

mrasu’s blog

読んだ物の内容など

算機プログラムの構造と解釈(5章)

「計算機プログラムの構造と解釈(SICP)」の5章(最終章)です

レジスタを使用するような計算を実装します。
レジスタを使用するような表現法を再現し、
Lispで書かれたものをレジスタ表現に置き換えます。

つまり、「アセンブリ言語を入力としてLispを実行し、Lisp言語を入力としてアセンブリ言語に置き換える」ようなことをします。
(ただし、アセンブリ言語に似た言語を作るのであって、アセンブリ自体ではありません。)

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


5章 レジスタ計算機での計算

5.1 レジスタ計算機の設計

5.1.1 レジスタ計算機の記述言語

  1. 入力を識別するラベル
  2. 命令
    • test (cmp)
    • branch (jump if equal)
    • goto

を用意する。記法は、

(controller  
    test-b  
    (test (op = ) (reg b) (const 0))  
    (branch (label gcd-done))  
    (assign t (op rem) (reg a) (reg b))  
    (assign a (reg b))  
    (assign b (reg t))  
    (goto (label test-b))  
    gcd-done  
)  

と記述する(見た目はLispだが、アセンブリ的)。
外部へ影響がある演算をperfomとする

5.1.2 計算機設計における抽象

rem 演算がない場合以下が必要

(controller  
    test-b  
        (test (op =) (reg b) (const 0))  
        (branch (label gcd-done))  
        (assign t (reg a))  
    rem-loop  
        (test (op <) (reg t) (reg b))  
        (branch (label rem-done))  
        (assign t (op -) (reg t) (reg b))  
        (goto (label rem-loop))  
    rem-done  
        (assign a (reg b))  
        (assign b (reg t))  
        (goto (label test-b))  
    gcd-done  
)  

5.1.3 サブルーチン

サブルーチンを作成して、サブルーチンに飛び、元の場所へ戻る処理は、
単純なものなら、フラグを作って、呼び出し元と1対1にすればよい。
もっとやるなら、呼び出し元のアドレスをどこかへ記録すればいい。
が、記録場所が常に同じだと再帰ができない

5.1.4 再帰を実装するためのスタックの使用

スタックを作れば、呼び出し元や元の値を再現できる

(controller  
        (assign continue (label fact-done))  
    fact-loop  
        (test (op =) (reg n) (const 1))  
        (branch (label base-case))  
        (save continue)  
        (save n)  
        (assign n (op -) (reg n) (const 1))  
        (assign continue (label after-fact))  
        (goto (label fact-loop))  
    after-fact  
        (restore n)  
        (restore continue)  
        (assign val (op *) (reg n) (reg val))  
        (goto (reg continue))  
    base-case  
        (assign val (const 1))  
        (goto (reg continue))  
    fact-done  
)  

5.3 記憶の割り当てとごみ集め

5.3.1 ベクタとしてのメモリ

(vector-ref! <vector\> <n\>)  
(vector-set! <vector\> <n\> value\>)  

ができるモデル「ベクタ」を定義する。

基本リストは、
0. (assign <reg1> (op car) (reg <reg2>))は
(assign <reg1> (op vector-ref) (reg the-cars) (reg <regs2>))
0. (perform (op set-car!) (reg <reg1>) (reg <reg2>))は
(perform (op vector-set!) (reg the-cars) (reg <reg1>) (reg <reg2>))

スタックは、

  1. (save <reg>)は
    (assign <reg> (op cons) (reg <reg>) (reg the-stack))
  2. (restore <reg>)は
    (assign <reg> (op car) (reg the-stack))
    (assign the-stack (op cdr) (reg the-stack))

と表現できる

5.3.2 無限メモリの幻想の維持

ガーベッジコレクションすることもできる。
ストップアンドコピー法として、使っているものを順に新領域に移動し、移動されなかったものを削除すればよい。

5.4 積極制御評価器

5.4.1 積極制御評価器の中核

手続きを評価する前に、現在の状態を保存する必要があり、戻ってくる場所も保存する
手続きの引数もスタックに入れる。使用時には、それらを吐き出す

5.4.2 並びの評価と末尾再帰

再帰には、末尾再帰もあるので、それを判断できるとループにすることができる

5.5 翻訳系

Lispを入力として、上の気法を出力する