Scheme - レジスタ計算機での計算(再帰を実装するためのスタックの使用、二重再帰(再帰的べき乗、反復的べき乗))

計算機プログラムの構造と解釈
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.1(レジスタ計算機の設計)、5.1.4(再帰を実装するためのスタックの使用)、二重再帰、問題 5.4を解いてみる。

その他参考書籍

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

問題 5.4

a. 再帰的べき乗を実装するレジスタ計算機を規定。

制御器の命令列。

(controller
   (assign continue (label expt-done))
 expt-loop
   (test (op =) (reg n) (const 0))
   (branch (label base-case))
   (save continue)
   (save n)
   (assign n (op -) (reg n) (const 1))
   (assign continue (label after-expt))
   (goto (label expt-loop))
 after-expt
   (restore n)
   (restore continue)
   (assign val (op *) (reg b) (reg val))
   (goto (reg continue))
 base-case
   (assign val (const 1))
   (goto (reg continue))
 expt-done)

データパス図。

b. 反復的べき乗を実装するレジスタ計算機を規定。

制御器の命令列。

(controller
   (assign product (const 1))
 expt-loop
   (test (op =) (reg n) (const 0))
   (branch (label expt-done))
   (assign n (op -) (reg n)
                    (op *) (reg b)
                           (reg product))
   (assign product (op *) (reg b) (reg product))
   (goto (label expt-loop))
 expt-done)

データパス図。