Scheme - 翻訳系(preserving機構とスタック演算、組み合わせ)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.5(翻訳系)、翻訳系の概観、5.5.1(翻訳系の構造)、標的と接続、命令列とスタックの使用、問題 5.31.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 5.31.

実際に、

• env
• argl
• proc

を使って積極制御評価器の場合を書いてみて、それを翻訳系のpreserving機構で考えて余分なsaveとrestoreを探してみる。

(f 'x 'y)について。

;; 演算子の評価の前 … (1)
;;(save env)
;; 演算子の評価
;; 演算子(f)の評価の後
;;(restore env)
;;(assign proc (…))
;; (1)からここまでは次のようになるので余分
(assign proc (op lookup-variable-value) (const f) (reg env))
;; 被演算子列('x 'y)の評価の前
;; (save proc)
;; 被演算子('x)の評価前
;; (save env)
;; (save argl)
;; 被演算子('x)の評価後
;; (restore argl)
;; (restore env)
;; 最後の被演算子('y)の評価前
;; 最後の被演算子('y)の評価
;; 最後の被演算子('y)の評価後
;; 被演算子列('x 'y)の評価後
;; (restore proc)
;; ここまでも、被演算子x'、y'の評価はレジスタenv、argl、procを修正することは無いので余分
(apply …)

ということで、全てのsaveとrestoreが余分であり、翻訳系のpreserving機構で除くことが出来る。

((f) 'x 'y)について。

;; 演算子((f))の評価前
;; (save env) … (2)
;; 演算子((f))の評価
;; 演算子(f)の評価前 … (1)
;; (save env)
;; 演算子(f)の評価
;; 演算子(f)の評価後
;; (restore env) (2)からレジスタenvは修正されていないので不要
;; (assign proc (…))
;; (1)からここまでのsaveとrestoreは不要で次のようになる
(assign proc (op lookup-variable-value) (const f) (reg env))
;; 演算子((f))の評価後
;; (restore env) この(1), (2)からこのrestoreも不要
;; (assign proc (…)) ;; … (3)
;; 被演算子列('x 'y)の評価前
;; (save proc)
;; 被演算子('x)の評価前
;; (save env)
;; (save argl)
;; 被演算子の評価
;; (restore argl)
;; (restore env)
;; 最後の被演算子('y)の評価前
;; 最後の被演算子の評価
;; 最後の被演算子の評価後
;; 被演算子列('x 'y)の評価後
;; (restore proc) (3)以降にレジスタenv、argl、procを修正することは無いので余分
(apply …)

ということで、全てのsaveとrestoreは余分で翻訳系のpreserving機構で除ける。

(f (g 'x) y)について。

;; 演算子(f)の評価前
;; (save env) … (1)
;; 演算子(f)の評価
;; 演算子(f)の評価後
;; (restore env) (1)のsaveとこのsaveとrestoreは余分。次のようになる
(assign proc (op lookup-variable-value) (const f) (reg env))
;; 被演算子列((g 'x) y)の評価前
(save proc)
;; 被演算子(g 'x)の評価前
;; (save env) … (4)
(save argl)
;; 被演算子(g 'x)の評価
;; 演算子(g)の評価前
;; (save env) … (2)
;; 演算子(g)の評価
;; 演算子(g)の評価後
;; (restore env) … (2)のsaveとこのrestoreは余分。次のようになる
(assign proc (op lookup-variable-value) (const g) (reg env))
;; 被演算子列('x)の評価前
(assign argl …)
;; (save proc) … (3)
;; 最後の被演算子('x)の評価前
;; 最後の被演算子('x)の評価
;; 最後の被演算子('x)の評価後
;; 被演算子列('x)の評価後
;; (restore proc) … (3)のsaveとこのrestoreは、レジスタprocは修正されることが無いので余分。
;; 被演算子(g 'x)の評価後
(restore argl)
(assign argl …)
;; (restore env) … (4)のsaveとこのrestoreは、レジスタenvが修正されることは無いので余分。
;; 最後の被演算子(y)の評価前
;; 最後の被演算子(y)の評価
;; 最後の被演算子(y)の評価後
;; 被演算子列((g 'x) y)の評価後
(restore proc)

ということで、余分なものを除いて残ったのは、(save argl)と(restore argl)。

(f (g 'x) 'y)について。

;; 演算子(f)の評価前
;; (save env) …(1)
;; 演算子(f)の評価
;; 演算子(f)の評価後
;; (restore env) (1)のsaveとこのrestoreは余分。次のようになる
(assign proc (op lookup-variable-value) (const f) (reg env))
;; 被演算子列((g 'x) 'y)の評価前
(save proc)
;; 被演算子(g 'x)の評価前
;; (save env) … (4)
(save argl)
;; 被演算子(g 'x)の評価
;; 演算子(g)の評価前
;; (save env) … (2)
;; 演算子(g)の評価
;; 演算子(g)の評価後
;; (restore env) … (2)のsaveとこのrestoreは、余分。次のようになる
(assign proc (op lookup-variable-value) (const g) (reg env))
;; 被演算子列('x)の評価前
(assign argl …)
;; (save proc) … (3)
;; 最後の被演算子('x)の評価前
;; 最後の被演算子('x)の評価
;; 最後の被演算子('x)の評価後
;; 被演算子列('x)の評価後
;; (restore proc) … (3)のsaveとこのrestoreは、レジスタprocが修正されることはないので余分。
;; 被演算子(g 'x)の評価後
(restore argl)
(assign argl …)
;; (restore env) … (4)のsaveとこのrestoreは、レジスタenvが修正されることは無いので余分。
;; 最後の被演算子('y)の評価前
;; 最後の被演算子('y)の評価
;; 最後の被演算子('y)の評価後
;; 被演算子列((g 'x) 'y)の評価後
(restore proc)

ということで、preserving機構で余分なものを除いて残ったのは、(save argl)と(restore argl)。