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

5.2.3 命令の実行手続きの生成

アセンブラは命令の実行手続きを生成すべくmake-execution-procedureを呼び出す. 4.1.7節の評価器のanalyze手続きと同様に, これは適切な実行手続きを生成するため, 命令の型に従って振分けを行う.


(define (make-execution-procedure inst labels machine
                                  pc flag stack ops)
  (cond ((eq? (car inst) 'assign)
         (make-assign inst machine labels ops pc))
        ((eq? (car inst) 'test)
         (make-test inst machine labels ops flag pc))
        ((eq? (car inst) 'branch)
         (make-branch inst machine labels flag pc))
        ((eq? (car inst) 'goto)
         (make-goto inst machine labels pc))
        ((eq? (car inst) 'save)
         (make-save inst machine stack pc))
        ((eq? (car inst) 'restore)
         (make-restore inst machine stack pc))
        ((eq? (car inst) 'perform)
         (make-perform inst machine labels ops pc))
        (else (error "Unknown instruction type -- ASSEMBLE"
                     inst))))

レジスタ計算機言語の命令の型ごとに, 適切な実行手続きを構築する生成プログラムがある. これらの手続きの細部が, レジスタ計算機言語での各命令の構文と意味を決める. 4.1.2節の評価器でやったように, レジスタ計算機の式の細い構文を一般の実行機構から分離するため, データ抽象を使い構文手続きで命令の部分を取り出し, 分類する.

`assign`命令

make-assign手続きはassign命令を扱う:


(define (make-assign inst machine labels operations pc)
  (let ((target
         (get-register machine (assign-reg-name inst)))
        (value-exp (assign-value-exp inst)))
    (let ((value-proc
           (if (operation-exp? value-exp)
               (make-operation-exp
                value-exp machine labels operations)
               (make-primitive-exp
                (car value-exp) machine labels))))
      (lambda ()                ; assignの実行手続き
        (set-contents! target (value-proc))
        (advance-pc pc)))))

make-assignは選択子


(define (assign-reg-name assign-instruction)
  (cadr assign-instruction))


(define (assign-value-exp assign-instruction)
  (cddr assign-instruction))

を使い, assign命令から目標のレジスタ名(命令の第二要素)と値の式(命令を形成する式のリストの残り)を取り出す. レジスタ名は, 目標のレジスタオブジェクトを作るべくget-registerで探す. 値の式は値が演算の結果ならmake- operation-expに, それ以外ならmake-primitive-expに渡す. (次に示す)これらの手続きは, 値の式を構文解析し, その値の実行手続きを作る. これは value-procという引数なしの手続きで, シミュレーション中にレジスタに代入する実際の値を得るために評価される. レジスタ名の探索と, 値の式の構文解析は, 命令がシミュレートされる度ではなく, アセンブリ時に一回だけ行うことに注意しよう. この省力は, 実行手続きを使う理由であり, 4.1.7節の評価器で, プログラム解析を実行から分離して得た省力と直接に対応する.

make-assignが返す結果は, assign命令の実行手続きである. この手続きを(計算機モデルのexecute手続きで)呼び出すと, 目標のレジスタの内容を, value-procを評価して得られる結果に設定する. それから手続き


(define (advance-pc pc)
  (set-contents! pc (cdr (get-contents pc))))

を走らせ, pcを次の命令へと進める. advance-pcはbranch とgotoを除き, すべての命令の通常の終了である.

`goto`命令

make-testはtest命令を同様に扱う. テストすべき条件を規定する式を抜き出し, そのための実行手続きを生成する. シミュレーション時には, 条件に対する手続きが呼び出され, 結果がflagレジスタに代入され, pcが進められる:


(define (make-test inst machine labels operations flag pc)
  (let ((condition (test-condition inst)))
    (if (operation-exp? condition)
        (let ((condition-proc
               (make-operation-exp
                condition machine labels operations)))
          (lambda ()
            (set-contents! flag (condition-proc))
            (advance-pc pc)))
        (error "Bad TEST instruction -- ASSEMBLE" inst))))


(define (test-condition test-instruction)
  (cdr test-instruction))

branch命令に対する実行手続きは, flagレジスタの内容を調べ, pcの内容を(分岐する時)分岐目的地へ設定するか(分岐しない時) pcを進めるかする. branch命令で指示される行き先はラベルでなければならず, make-branchはこれを強要することに注意しよう. またラベルはアセンブリ時に探すので, branch命令をシミュレートする度でないことにも注意しよう.


(define (make-branch inst machine labels flag pc)
  (let ((dest (branch-dest inst)))
    (if (label-exp? dest)
        (let ((insts
               (lookup-label labels (label-exp-label dest))))
          (lambda ()
            (if (get-contents flag)
                (set-contents! pc insts)
                (advance-pc pc))))
        (error "Bad BRANCH instruction -- ASSEMBLE" inst))))


(define (branch-dest branch-instruction)
  (cadr branch-instruction))

goto命令は, 行き先がラベルとしてかレジスタとして指定出来る点と, 調べるべき条件がない---pcは常に新しい行き先へ設定する---点を除き, 分岐命令と似ている.


(define (make-goto inst machine labels pc)
  (let ((dest (goto-dest inst)))
    (cond ((label-exp? dest)
           (let ((insts
                  (lookup-label labels
                                (label-exp-label dest))))
             (lambda () (set-contents! pc insts))))
          ((register-exp? dest)
           (let ((reg
                  (get-register machine
                                (register-exp-reg dest))))
             (lambda ()
               (set-contents! pc (get-contents reg)))))
          (else (error "Bad GOTO instruction -- ASSEMBLE"
                       inst)))))


(define (goto-dest goto-instruction)
  (cadr goto-instruction))

その他の命令

スタック命令saveとrestoreは指示されたレジスタでスタックを使い, pcを進めるだけである:



(define (make-save inst machine stack pc)
  (let ((reg (get-register machine
                           (stack-inst-reg-name inst))))
    (lambda ()
      (push stack (get-contents reg))
      (advance-pc pc))))



(define (make-restore inst machine stack pc)
  (let ((reg (get-register machine
                           (stack-inst-reg-name inst))))
    (lambda ()
      (set-contents! reg (pop stack))    
      (advance-pc pc))))


(define (stack-inst-reg-name stack-instruction)
  (cadr stack-instruction))

make-performが扱う命令の最後の型は, 実行すべき働きに対して実行手続きを生成する. シミュレーション時に働きの手続きが実行され, pcが進められる:


(define (make-perform inst machine labels operations pc)
  (let ((action (perform-action inst)))
    (if (operation-exp? action)
        (let ((action-proc
               (make-operation-exp
                action machine labels operations)))
          (lambda ()
            (action-proc)
            (advance-pc pc)))
        (error "Bad PERFORM instruction -- ASSEMBLE" inst))))


(define (perform-action inst) (cdr inst))

部分式の実行手続き

reg, labelまたはconst式の値は, レジスタへの代入(make-assign)や演算(次のmake-operation-exp)への入力で必要になる. 次の手続きはシミュレーション時にこれらの式の値を作る実行手続きを生成する:


(define (make-primitive-exp exp machine labels)
  (cond ((constant-exp? exp)
         (let ((c (constant-exp-value exp)))
           (lambda () c)))
        ((label-exp? exp)
         (let ((insts
                (lookup-label labels
                              (label-exp-label exp))))
           (lambda () insts)))
        ((register-exp? exp)
         (let ((r (get-register machine
                                (register-exp-reg exp))))
           (lambda () (get-contents r))))
        (else
         (error "Unknown expression type -- ASSEMBLE" exp))))

reg, labelおよびconst式の構文は


(define (register-exp? exp) (tagged-list? exp 'reg))


(define (register-exp-reg exp) (cadr exp))


(define (constant-exp? exp) (tagged-list? exp 'const))


(define (constant-exp-value exp) (cadr exp))


(define (label-exp? exp) (tagged-list? exp 'label))


(define (label-exp-label exp) (cadr exp))

で決る.

assign, performおよびtest命令は, (regおよびconst式の規定する)いくつかの被演算子に対する(op式の規定する)機械演算の作用を含むかも知れない. 次の手続きは「演算式」---演算と被演算子の式を含むリスト---に対する実行手続きを命令から作る.


(define (make-operation-exp exp machine labels operations)
  (let ((op (lookup-prim (operation-exp-op exp) operations))
        (aprocs
         (map (lambda (e)
                (make-primitive-exp e machine labels))
              (operation-exp-operands exp))))
    (lambda ()
      (apply op (map (lambda (p) (p)) aprocs)))))

演算式の構文は


(define (operation-exp? exp)
  (and (pair? exp) (tagged-list? (car exp) 'op)))


(define (operation-exp-op operation-exp)
  (cadr (car operation-exp)))


(define (operation-exp-operands operation-exp)
  (cdr operation-exp))

で決る. 演算式の扱いは, 各被演算子について実行手続きを生成するという点で, 4.1.7節の評価器のanalyze- application手続きによる手続き作用の扱いと非常によく似ていることを見よう. シミュレーション時には, 被演算子手続きを呼び出し, その結果の値へ演算をシミュレートするScheme手続きを作用させる. シミュレーション手続きは, 計算機の演算表から演算名で探して見つける:


(define (lookup-prim symbol operations)
  (let ((val (assoc symbol operations)))
    (if val
        (cadr val)
        (error "Unknown operation -- ASSEMBLE" symbol))))

問題 5.9

上の機械演算の扱いは定数やレジスタの内容の他ラベルにも演算することを許す. 式の処理の手続きを修正し, 演算はレジスタと定数にだけ使えるという条件を強要するようにせよ.

問題 5.10

レジスタ計算機命令に新しい構文を設計し, シミュレータがその新しい構文を使えるように修正せよ. 本節の構文手続き以外のシミュレータ部分を変更せず, 新しい構文を実装出来るか.

問題 5.11

5.1.4節でsaveとrestoreを紹介した時

(save y)
(save x)
(restore y)

のように最後に退避したのではないレジスタを回復しようとすると, 何が起きるかは規定しなかった. restoreの意味にはいくつかの正当な可能性がある.

a. (restore y)は, どのレジスタから値が来たかに関係なく, スタックに退避した最後の値をyに置く. これはわれわれのシミュレータの振舞いである. この振舞いが5.1.4節(図5.12)のFibonacci計算から一命令を除去するのに使えることを示せ.

b. (restore y)は, スタックに退避した最後の値を, それがyから退避された時だけ, yに置き, それ以外はエラーとする. シミュレータをこのように振舞うよう修正せよ. スタックに値と一緒にレジスタ名を置くよう, saveを変更しなければならない.

c. (restore y)は, yの後, 他のどのレジスタが退避され, 回復されていなくても, yから退避した最後の値をyに置く. シミュレータをこう振舞うように修正せよ. レジスタ毎に別のスタックを対応させなければならない. initialize-stack演算にすべてのレジスタスタックを初期化させなければならない.

問題 5.12

与えられた制御器で計算機を実装する時に必要なデータパスを決めるのを助けるため, シミュレータを使うことが出来る. アセンブラを拡張し, 次の情報を計算機モデルに格納するようにせよ:

• (assign, gotoなどの)命令の型で, 格納されたすべての(異なる)命令のリスト;

• 入り口を保持するのに使った(異る)レジスタのリスト (goto命令の参照するレジスタである.);

• save, restoreされる(異る)レジスタのリスト;

• 各レジスタに対し, (異る)代入元のリスト(例えば図5.11の階乗計算機で, レジスタvalの元は(const 1)と((op *) (reg n) (reg val))である.)

計算機のメッセージパッシングインターフェースを拡張し, これらの新しい情報にアクセス出来るようにせよ. 解析プログラムをテストするため, 図5.12のFibonacci計算機を定義し, 構成したリストを調べよ.

問題 5.13

make-machineの引数としてレジスタリストを要求するのでなく, 制御器の命令列を使って計算機の持つレジスタを決めるようにシミュレータを修正せよ. make-machineであらかじめレジスタを割り当てる代りに, 命令のアセンブリ中に, 初めて見る度に, レジスタを割り当てることが出来る.

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

5.2.3 命令の実行手続きの生成

assign命令

goto命令

その他の命令

部分式の実行手続き

`assign`命令

`goto`命令