SICP 読み (311) 5.5 翻訳系

いちいちリハビリが必要なあたり、微妙。
直前エントリでは

(preserving '(proc continue)
	    (construct-arglist operand-codes)
	    (compile-procedure-call target linkage))

の途中の construct-arglist が完了したあたりだったはず。ちなみに target は val で linkage は next との事。ちなみに construct-arglist が戻すのは

'((env val) (proc argl)
  ((assign val (const 1)) 
   (assign argl (op list) (reg val))
   (assign val (op lookup-variable-value) (const n) (reg env))
   (assign argl (op cons) (reg val) (reg argl))))

という事になっている模様。一応出力されている命令列と合致はしている。

compile-procedure-call

で、これですか。allcode なソースには_applying procedures_とある。ch5-eceval.scm の apply-dispatch にあたる部分を吐き出すナニと見て間違いないはず。
ちんたらやってんじゃなぇ、って自分でも思うんですが中々時間が取れません (当たり前
てーかこれって引数でしか出力が変化しないのかな? ざっくりなソレは大体同じである模様。ラベルは 308 なエントリで言うと連番は 11 から開始なので

• primitive-branch11
• compiled-branch12
• after-call13

としてまず最初に出てくる instruction-seq は以下か

((proc) () ((test (op primitive-procedure?) (reg proc))
	    (branch (label primitive11))))

これと append されるのは後で見る compile-proc-appl の出力と

((proc argl) (val) (primitive-branch11
		    (assign val
			    (op apply-primitive-procedure)
			    (reg proc)
			    (reg env))))

上記の instruction-seq と、あと after-call13 というラベル。ここで seq が二つ以上な append が出てくるのか。もう少しで条件式を評価する部分の compile が完了するのかな。

compile-proc-appl

この手続きは cond で条件によって処理が分かたれているのが分かる

• target が val で linkage が return 以外
• target が val 以外で linkage が return 以外
• target が val で linkage が return
• target が val 以外で linkage が return

という 4 パターン。ちなみに一番下の条件は error で異常終了な模様。return するなら target は val だろ、というのは確かに大前提。
で、ここに渡されている引数としては target は val で linkage はラベルの after-call13 という事になります。最初の条件にマッチ。なので

((proc) (env proc val argl continue)
 ((assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))))

という instruction-seq が戻る形になりますな。これで一連の手続きが吐き出す instruction-seq は分かったんですが、くっつけるのがこれまたゴウな話で。

くっつける手続き

ちょうど良いのでざくっと眺めてみる。

• parallel は全部足してしまう感じ
• tack-on は statements のみ足して needed とか modified は最初の seq のソレだけ使う
• append は statements と modified は単純 append だけど needed については seq1 の needed に seq2 の needed から seq1 の modified を引いたナニを足す感じ。意図についてはまだ微妙な理解
• preserving は渡されたレジスタなリストの要素が seq2 の needed と seq1 の modified の両方に存在する場合には seq1 の statements に save/restore を付加。レジスタを順にたぐっていって、リストの末端に到達したら単純に append する形

これを前提としてそれぞれの instruction-seq をくっつけてみます。ええと、compile-procedure-call での target は val で linkage は next のはず。まず一番深い部分からいくと

        (append-instruction-sequences
         primitive-branch
         (end-with-linkage linkage
          (make-instruction-sequence '(proc argl)
                                     (list target)
           `((assign ,target
                     (op apply-primitive-procedure)
                     (reg proc)
                     (reg argl)))))))

の部分か。そしてようやく

(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)))

の意図を理解。ラベルだったら、という事ですか。成程ねー。で、話を元に戻すと end-with-linkage な戻りは linkage が next なので

((proc argl) (val)
 ((assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))))

で、これが primitive-branch と append される。これは単純に以下になるだけ。

((proc argl) (val)
 (primitive-branch11
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))))

次は上記の式が compile-proc-appl の戻りと append されて最後にラベルと append されるんですが、compile-proc-appl の戻りを再度

((proc) (env proc val argl continue)
 ((assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))))

ええと、append のルールとしては needed が微妙なのか。seq1 は直上なので

(proc)

は鉄板。これに union するのは (proc argl) - (env proc val argl continue) なのでナシになりますな。あとは単純 append ってコトは以下??

((proc) (env proc val argl continue)
 ((assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))
  primitive-branch11
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))))

なんとなく良い感じ。最後に append なラベルは compiled-branch という事で、って手続き見直してみたら違うぞ。(とほほほほ
どっからヤリ直せば良いのでしょうか。

いやはや

compiled-branch と compile-proc-appl の戻りを先に append する模様。なので

((proc) (env proc val argl continue)
 (compiled-branch12
  (assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))))

と

((proc argl) (val)
 (primitive-branch11
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))))

が parallel 結合される訳ですね。parallel は単純に append するだけだったはず。なので以下か

((proc argl) (env proc val argl continue)
 (compiled-branch12
  (assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))
  primitive-branch11
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))))

うむ。当ってそげ。最後に上記と

((proc) () ((test (op primitive-procedure?) (reg proc))
	    (branch (label primitive11))))

と after-call なラベルが append で終了してくれ。まず最初に以下のナニになる。

((proc argl) (env proc val argl continue)
 (compiled-branch12
  (assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))
  primitive-branch11
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))
  after-call13))

で、test なソレと append される。needed は

(proc)

に (proc argl) - () になるんでこれは全部か。あとは単純にナニなので以下で良いのかなぁ。

((proc argl) (env proc val argl continue)
 ((test (op primitive-procedure?) (reg proc))
  (branch (label primitive11))
  compiled-branch12
  (assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))
  primitive-branch11
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))
  after-call13))

一応合っている。これが p-code にセット、という事で宜しいのでしたっけ??
や、違うや。これと compile-application の proc-code と preserving されるんだ。てーか、proc-code は何処へやら。って 310 なエントリの先頭にありました。以下。

'((env) (proc)
  ((assign proc
	   (op lookup-variable-value)
	   (const =)
	   (reg env))))

あ、違う。まず construct-arglist な出力と preserving するんだ。出力は 310 によれば以下

'((env val) (proc argl)
  ((assign val (const 1)) 
   (assign argl (op list) (reg val))
   (assign val (op lookup-variable-value) (const n) (reg env))
   (assign argl (op cons) (reg val) (reg argl))))

一応繋がってる感じ。ええと preserving はレジスタ一覧と seq1 の modified と seq2 の needed がナニ、だったよな。最初の preserving で渡されているレジスタなリストは

(proc continue)

になっている模様。seq1 の modified は

(proc argl)

で seq2 の needed は

(proc argl)

って全部じゃん。いや proc か。でも proc は modify されてないぞ (これは出力されたアセンブラの命令列を見て怪しいと判断しております)。construct-arglist が微妙なのかなぁ。

見直し

ブログって便利だなぁ。微妙なソレを一発ツモ (と思われる)。記述としては

(preserving '(argl)
	    '((env) (proc) 
	      ((assign val (op lookup-variable-value) (const n) (reg env))))
	    '((val argl) (argl) 
	      ((assign argl (op cons) (reg val) (reg argl)))))

の出力が微妙と思われます。いや違うな上記の時点でスデに違う。n とか 1 を評価する時点で

((env) (proc) 
 ((assign val (op lookup-variable-value) (const n) (reg env))))

って書いてるな。

(compile n 'val 'next)

は

((env) (val)
 ((assign val (op lookup-variable-value) (const n) (reg env))))

じゃねぇか。だからはしょってしまいますが、construct-arglist な出力は以下のはず。

((env val) (val argl)
 ((assign val (const 1)) 
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value) (const n) (reg env))
  (assign argl (op cons) (reg val) (reg argl))))

これ、needed なリストも微妙だな。再考が必要と思われます。

construct-arglist 再考

ええと operand-codes は以下のはず。

(((env) (val) ((assign val (op lookup-variable-value) (const n) (reg env))))
 ((env) (val) ((assign val (const 1)))))

面倒なのでざっくり書くと

(preserving 
 '(env)
 (append-instruction-sequences
  ((env) (val) ((assign val (op lookup-variable-value) (const n) (reg env))))
  ((val) (argl) ((assign argl (op list) (reg val)))))
 (preserving 
  '(argl)
  ((env) (val) ((assign val (const 1))))
  ((val argl) (argl)
   (assign argl (op cons) (reg val) (reg argl)))))

が construct-arglist の戻りになるはず。(はしょり杉
最初の append がどんな instruction-seq をヒリ出すかとゆーと

((env) (val argl)
 ((assign val (op lookup-variable-value) (const n) (reg env))
  (assign argl (op list) (reg val))))

かいな。次の preserving は単純 append で OK な模様、なので

((env argl) (val argl)
 ((assign val (const 1))
  (assign argl (op cons) (reg val) (reg argl))))

で良いのかな。さらに上記二つを env で preserving なんですがこれも単純 append にになる、ので以下か

((env) (val argl)
 ((assign val (op lookup-variable-value) (const n) (reg env))
  (assign argl (op list) (reg val))
  (assign val (const 1))
  (assign argl (op cons) (reg val) (reg argl))))

やっぱ違ってましたな。
これと

((proc argl) (env proc val argl continue)
 ((test (op primitive-procedure?) (reg proc))
  (branch (label primitive11))
  compiled-branch12
  (assign continue (label after-call13))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))
  primitive-branch11
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg env))
  after-call13))

これを (proc continue) で preserving した後に

'((env) (proc)
  ((assign proc
	   (op lookup-variable-value)
	   (const =)
	   (reg env))))

と (env continue) で preserving される、という事になるはず。この状況だと save/restore な対象は現時点で env のみですがこの後に、なんだとゆー事にします。時間が無いのでとりあえずエントリ投入。つづきは別途追記予定。