(define (registers-needed s) (if (symbol? s) '() (car s))) (define (registers-modified s) (if (symbol? s) '() (cadr s))) (define (statements s) (if (symbol? s) (list s) (caddr s)))を使い, また与えられた列が与えられたレジスタを必要とするか, 修正するかを決めるのに述語
(define (needs-register? seq reg) (memq reg (registers-needed seq))) (define (modifies-register? seq reg) (memq reg (registers-modified seq)))を使う. これらの述語と選択子を使って, 翻訳系を通じて使う各種の命令列組合せ手続きが実装出来る.
基本の組合せ手続きはappend-instruction-sequencesである. これは引数として逐次に実行される任意個の命令列をとり, すべての列の文を連結した文を持つ命令列を返す. 微妙な点は, 結果の列が必要とする, または修正するレジスタを決めることである. 結果の列はいずれかの列が修正するレジスタを修正する; それは, 第一の列が走る前に初期化する(第一の列が必要とするレジスタ)と, 他の列のいずれかが必要とし, それに先行する列が初期化しない(修正しない)レジスタを必要とする.
列は一時に二つappend-2-sequencesで連結する. これは二つの命令列seq1 とseq2をとり, その文がseq1の文にseq2の文が続き, その修正するレジスタがseq1かseq2のいずれかが修正するレジスタで, その必要とするレジスタがseq1の必要とするレジスタと, seq2が必要とするレジスタでseg1が修正しないものである命令列を返す. (集合演算を使えば, 必要なレジスタの新しい集合は, seq1が必要とする集合と, seq2が必要とするレジスタとseq1が修正するレジスタの差集合の和集合である.) 従って append-instruction-sequencesは次のように実装する.
(define (append-instruction-sequences . seqs)
(define (append-2-sequences seq1 seq2)
(make-instruction-sequence
(list-union (registers-needed seq1)
(list-difference (registers-needed seq2)
(registers-modified seq1)))
(list-union (registers-modified seq1)
(registers-modified seq2))
(append (statements seq1) (statements seq2))))
(define (append-seq-list seqs)
(if (null? seqs)
(empty-instruction-sequence)
(append-2-sequences (car seqs)
(append-seq-list (cdr seqs)))))
(append-seq-list seqs))
この手続きは, 2.3.3節で述べた(順序づけられない)集合表現に似ている, リストで表現した集合を操作する単純な演算を使う:
(define (list-union s1 s2)
(cond ((null? s1) s2)
((memq (car s1) s2) (list-union (cdr s1) s2))
(else (cons (car s1) (list-union (cdr s1) s2)))))
(define (list-difference s1 s2)
(cond ((null? s1) '())
((memq (car s1) s2) (list-difference (cdr s1) s2))
(else (cons (car s1)
(list-difference (cdr s1) s2)))))
次に重要な命令列組合せ手続きpreservingはレジスタのリストregsと逐次に実行する二つの命令列seq1とseq2をとり, seq1の文にseq2の文が続いた文を持ち, seq1が修正するがseq2が必要とするregsにあるレジスタを守るためseq1の前後に適切なsaveとrestore命令をつけた命令列を返す. これを実現するため, preservingはまず必要なsaveとseq1の文と必要なrestoreの列を作る. この列はseq1が必要とするレジスタに加えて, 退避回復するレジスタを必要とし, seq1が修正するレジスタから退避回復するレジスタを除いたものを修正する. 次にこの拡張した列とseq2を通常の方法で連結する. 次の手続きは, 保存するレジスタのリストを渡り歩きながら, この戦略を再帰的に実装する:42
(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)))))
別の列組合せ手続きtack-on-instruction-sequenceはcompile-lambdaが手続き本体を他の列に連結するのに使う. 手続き本体は組み合せた列の一部として実行すべく「展開する」のではないから, そのレジスタの使用は, それが埋め込まれれる列のレジスタの使用には影響しない. 従って手続き本体を他の列に付加する時, その必要とし, 修正するレジスタの集合は無視する.
(define (tack-on-instruction-sequence seq body-seq) (make-instruction-sequence (registers-needed seq) (registers-modified seq) (append (statements seq) (statements body-seq))))
compile-ifとcompile-procedure-callはテストに続く二つの選択的枝を連結するのにparallel-instruction-sequencesという特別な組合せ手続きを使う. 二つの枝は決して逐次には実行しない; テストのその時の評価により, ある枝か, 他の枝に進む. そのため第二の枝が必要とするレジスタは, 組み合せた列では, 第一の枝で修正してもなお必要とする.
(define (parallel-instruction-sequences seq1 seq2)
(make-instruction-sequence
(list-union (registers-needed seq1)
(registers-needed seq2))
(list-union (registers-modified seq1)
(registers-modified seq2))
(append (statements seq1) (statements seq2))))
42
preservingは
appendを三つの引数で呼び出すことに注意しよう. 本書に示したappendの定義は二つの引数しか受け入れないが,
Schemeは標準的に任意個の引数をとるappend手続きを用意する.