SICP 読み (315) 5.5 翻訳系

SICP scheme

冬休みに突入。大掃除ちょっとしかしてませんがへろへろ。昨晩の忘年会の影響大。スデに Dec 29 21:00 JST を過ぎようとしとりますが、頑張ってみます。

(compile '(* (factorial (- n 1)) n) 'val 'return)

これを評価。まず、operator をナニして次に operands な模様。

(compile * 'proc 'next)

で compile-variable 行き。これは

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

一発かな。以降が長い道程の始まりではないかと。あ、でも翻訳するだけだから楽か。

つづき

ヒトシ・マツモトのお蔭でスデに 23:00 JST を過ぎてます。(何
よく見りゃ alternative なブロックは三段なナニだな。と言いつつ死亡。明日はどんな一日になるのだろうか (を

次の日

よく考えたら再帰呼び出しになってても翻訳と評価は違うことにようやく気づく。入れ子になってるのが微妙ですが、最初の引数も application なので

(compile (factorial (- n 1)) 'val 'next)

あるいは operator の評価は

(compile factorial 'proc 'next)

なので

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

そしてこの式の operands も application 一発。なんか面倒臭いなぁ。operator が

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

で operands は

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

になるんかな。あとはクミアワセの世界なんですが、compile しなおしたのでもう一度ラベルなソレを整理しておく事にします。

make-label について

ええと、compile してるのは以下の式

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

なので適用される手続きとラベルの採番は順に

  • compile-definition
  • compile-lambda
    • entry1
    • after-lambda2
  • compile-if
    • true-branch3
    • false-branch4
    • after-if5
  • compile-application (predicate)
    • primitive-branch6
    • compiled-branch7
    • after-call8

で、今は alternative なソレを compile 中な訳か。

クミアワセ

(compile (- n 1) 'val 'next)

での proc-code と operand-codes は上記で準備完了してますので、とりあえず

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

なんですが、まず construct-arglist において code-to-get-last-arg に

(() (val)
 ((assign val (const 1))))

と 

((val) (argl)
 (assign argl (op list) (reg val)))

と append して以下

(() (val argl)
 ((assign val (const 1))
  (assign argl (op list) (reg val))))

でええのかな。compile-procedure-call は以下の引数か

(compile-procedure-call 'val 'next)

ここでラベルがナニ

  • primitive-branch9
  • compiled-branch10
  • after-call11

あとは apply-dispatch なナニですか。組み合わせの手続きが入れ子になってるからぱっと見凄い面倒です。ええと compile-proc-appl が戻すのは

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

になるとして compile-procedure-call を底から順にナニしていくと

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

が primitive-branch と append されて以下

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

次は先の compile-proc-appl が戻したソレと compiled-branch を append

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

これら二つが parallel で組み合わされて以下

((proc argl) (env proc val argl continue)
 (compiled-branch10
  (assign continue (label after-call11))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))
  primitive-branch9
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg argl))))

これが、

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

と after-call と append な模様。最終的には以下か

((proc argl) (env proc val argl continue)
 ((test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch9))
  compiled-branch10
  (assign continue (label after-call11))
  (assign val (op compiled-procedure-entry)
	  (reg proc))
  (goto (reg val))
  primitive-branch9
  (assign val
	  (op apply-primitive-procedure)
	  (reg proc)
	  (reg argl))
  after-call11))

これが

(compile (- n 1) 'val 'next)

が戻すリストになる訳でこれで factorial の引数の準備完了。一旦エントリ投入してメシを食いましょうね。