SICP 読み (304) 5.5 翻訳系

SICP scheme

割込みが入らない限り、こっち対応ができそうな今日明日。(を

問題 5.31

昨晩の続き。最初の (f 'x 'y) の save/restore に着目した ev-application 以下の手続きが以下。コメントも付けておく。

  • contine が save
  • env が save (省略可)
  • unev が save (省略可)
  • f を eval (lookup)
  • unev が resotre (省略可)
  • env が restore (省略可)
  • proc が save
  • argl が save (省略可)
  • env が save (省略可)
  • unev が save (省略可)
  • 'x を eval (quoted)
  • unev が restore (省略可)
  • env が restore (省略可)
  • argl が resotre (省略可)
  • argl と unev を操作
  • argl が save (省略可)
  • 'y を eval (quoted)
  • argl が restore (省略可)
  • argl を操作
  • proc が restore
  • apply-dispatch に jmp

このパターンだと省略可なソレは余分と見て良いのだろうか。
次は ((f) 'x 'y) となっている。これは apply しないと無理。上記をコピペで整理してみる。

  • contine が save
  • env が save
  • unev が save
  • f を eval (application)
    • contine が save
    • env が save (省略可)
    • unev が save (省略可)
    • f を eval (lookup)
    • unev が resotre (省略可)
    • env が restore (省略可)
    • apply-dispatch に jmp (val に手続きが格納されるハズ)
  • unev が resotre
  • env が restore
  • proc が save
  • argl が save (省略可)
  • env が save (省略可)
  • unev が save (省略可)
  • 'x を eval (quoted)
  • unev が restore (省略可)
  • env が restore (省略可)
  • argl が resotre (省略可)
  • argl と unev を操作
  • argl が save (省略可)
  • 'y を eval (quoted)
  • argl が restore (省略可)
  • argl を操作
  • proc が restore
  • apply-dispatch に jmp

この場合、演算子が手続きになっているので演算子の評価時の env と unev の save/resotre は省けない。ただしその手続きの中の f の lookup におけるソレ達は省略可能。
次の (f (g 'x) y) は微妙。でもこれと次の (f (g 'x) 'y) は大差ないように思えるんですが、それは多分ダウトなんだろうな。

む

ってーか、presering のどれに当たるかってアナタ。例えば (f 'x 'y) は以下の命令列になるのでしょうか。直列にしちゃって良いのかどうか微妙ですがトライ。

ev-application
  (save continue)
  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-appl-did-operator))
;  (goto (label eval-dispatch))
ev-variable
  (assign val (op lookup-variable-value) (reg exp) (reg env))
  (goto (reg continue))
ev-appl-did-operator
  (restore unev)
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)
ev-appl-operand-loop
  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)
  (assign continue (label ev-appl-accumulate-arg))
;  (goto (label eval-dispatch))
ev-quoted
  (assign val (op text-of-quotation) (reg exp))
  (goto (reg continue))
ev-appl-accumulate-arg
  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))
  (goto (label ev-appl-operand-loop))
ev-appl-operand-loop
  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
ev-appl-last-arg
  (assign continue (label ev-appl-accum-last-arg))
;  (goto (label eval-dispatch))
ev-quoted
  (assign val (op text-of-quotation) (reg exp))
  (goto (reg continue))
ev-appl-accum-last-arg
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

これ seq1 だの seq2 だのをどう切り分けるか微妙ですが、save/restore の組で切り分けてみる。まず最初のブロックだと

ev-application
  (save continue)
  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-appl-did-operator))
;  (goto (label eval-dispatch))
ev-variable
  (assign val (op lookup-variable-value) (reg exp) (reg env))
  (goto (reg continue))
ev-appl-did-operator
  (restore unev)
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))

までになるか。そうすると seq1 は

  (assign unev (op operands) (reg exp))
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-appl-did-operator))
;  (goto (label eval-dispatch))
ev-variable
  (assign val (op lookup-variable-value) (reg exp) (reg env))
  (goto (reg continue))

で preserving に渡すレジスタのリストは (continue env unev) になる。あと seq2 は

  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))

になるのか。うーん、continue を相手にすべきかどうか微妙。(save continue) は範疇外と見ましょうね。てーかラベルとかも抹消で考えてみる。

ev-application
  (save continue)

  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))

  (assign val (op lookup-variable-value) (reg exp) (reg env))

  (restore unev)
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)

  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)

  (assign val (op text-of-quotation) (reg exp))

  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))

  (save argl)
  (assign exp (op first-operand) (reg unev))

  (assign val (op text-of-quotation) (reg exp))

  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

こんな形で直列にしてしまうと確かに continue の save は不要かも (を
そりゃ良いのですが、これ元でナニしてみるとこのセットと

  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))

  (assign val (op lookup-variable-value) (reg exp) (reg env))

  (restore unev)
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))

このセットと

  (save proc)

  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)

  (assign val (op text-of-quotation) (reg exp))

  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))

  (save argl)
  (assign exp (op first-operand) (reg unev))

  (assign val (op text-of-quotation) (reg exp))

  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

その中にある

  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)

  (assign val (op text-of-quotation) (reg exp))

  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))

と

  (save argl)
  (assign exp (op first-operand) (reg unev))

  (assign val (op text-of-quotation) (reg exp))

  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))

になりますでしょうか。これイキオイでヤってるとは言え、凄い量だな。

(f 'x 'y) の最初のセット

  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))

  (assign val (op lookup-variable-value) (reg exp) (reg env))

  (restore unev)
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))

これ seq1 は

  (assign unev (op operands) (reg exp))
  (assign exp (op operator) (reg exp))
  (assign val (op lookup-variable-value) (reg exp) (reg env))

で、 seq2 が

  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))

でレジスタなリストは (env unev) になります。レジスタの save/continue は不要なパターン。seq1 と seq2 をそのまま連結すれば stack な演算は略せる。

(f 'x 'y) の二番目のパターン

ってーかその中にあるソレを先に済ませた方が良いかも。まず三番目。

  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)

  (assign val (op text-of-quotation) (reg exp))

  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))

上記で言えば seq1 は

  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (assign val (op text-of-quotation) (reg exp))

で seq2 は

  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))

になりますでしょうか。これも save/restore 不要。

(f 'x 'y) の四番目のパターン

以下が二番目の中身のラスト

  (save argl)
  (assign exp (op first-operand) (reg unev))

  (assign val (op text-of-quotation) (reg exp))

  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))

seq1 は

  (assign exp (op first-operand) (reg unev))
  (assign val (op text-of-quotation) (reg exp))

で seq2 は

  (assign argl (op adjoin-arg) (reg val) (reg argl))

になりますが、これも quoted なソレなので save/restore 不要。

再度 (f 'x 'y) の二番目

中の式を最適化したソレと置き換えてみます。

  (save proc)

  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (assign val (op text-of-quotation) (reg exp))
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))

  (assign exp (op first-operand) (reg unev))
  (assign val (op text-of-quotation) (reg exp))
  (assign argl (op adjoin-arg) (reg val) (reg argl))

  (restore proc)
  (goto (label apply-dispatch))

これまたスッキリしてますな。上記の seq1 は

  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (assign val (op text-of-quotation) (reg exp))
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))

  (assign exp (op first-operand) (reg unev))
  (assign val (op text-of-quotation) (reg exp))
  (assign argl (op adjoin-arg) (reg val) (reg argl))

で seq2 は

  (goto (label apply-dispatch))

な模様。これって save/restore 不要に見えますがどうでしょ。