SICP 読み (330) 5.5 翻訳系

SICP scheme

三連休だがしかし自習。色々あってどこにも行けず。

問題 5.37

基本的に instruction-sequence の中にある needed だの modified だのというソレは 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)))))
	      )))

みたいな乱暴なコトしても良いのでしょうが、もう少しお行儀良く直してみるか。

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

微妙。この方が良さげ。

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

これも微妙かなぁ。ぶっちゃけどれでも良いのでしょうが、試験してみる_単純な式_って微妙だなぁ。とりあえず preserving を呼び出している手続きを列挙してみると

  • end-with-linkage
  • compile-assignment
  • compile-definition
  • compile-if
  • compile-sequence
  • compile-application
    • construct-arglist
    • code-to-get-rest-args

って end-with-linkage は色々なソレが呼び出しているな。

  • self-evaluating
  • quoted
  • variable
  • assignment
  • definition
  • lambda
  • apply

ですか。ってコトは

(compile 1 'val 'return)

なんかでも save/restore してしまうのか。これはどうなんだろう。ちなみにデフォルトの評価器だと以下の statement が出てきた。

((assign val (const 1))
 (goto (reg continue)))

これ、assign の上下に save/restore が付くのか。試験してみたら付いてます。ちなみに使っている preserving は一番上のソレです。これは凄くウザいな。で

(compile '(define a 1) 'val 'return)

してみたら、出るわ出るわ。

((save continue) 
 (save env) 
 (save continue) 
 (assign val (const 1)) 
 (restore continue) 
 (restore env) 
 (perform (op define-variable!) (const a) (reg val) (reg env)) 
 (assign val (const ok)) 
 (restore continue) 
 (goto (reg continue))))

冗長。ちなみにデフォルト評価器では以下

((assign val (const 1)) 
 (perform (op define-variable!) (const a) (reg val) (reg env)) 
 (assign val (const ok)) 
 (goto (reg continue))))

当たり前ですが save/restore はゼロ。上記の define のケースだと

  • 最初に get-value-code にセットする compile (variable の end-with-linkage) で continue の save/restore が追加
  • get-value-code と perform-assign が env で preserving されるので env の save/restore が追加
  • 最後に end-with-linkage されて continue の save/restore が追加

という事になっているワケですか。