Scheme - レジスタ計算機での計算(計算機設計における抽象(Newton法を使った平方根を計算する計算機の設計))

計算機プログラムの構造と解釈
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.2(計算機設計における抽象)、問題 5.3を解いてみる。

その他参考書籍

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

問題 5.3

good-enough?とimprove演算は基本演算として使えると仮定した版。

平方根計算機のデータパス図。

レジスタ計算機言語による制御器の定義。

(controller
 sqrt-loop
   (assign x (op read))
   (assign guess (const 1.0))
 test-good-enough
   (test (op good-enough?) (reg guess) (reg x))
   (branch (label sqrt-done))
   (assign guess (op improve) (reg guess) (reg x))
   (goto (label test-good-enough))
 sqrt-done
   (perform (op print) (reg guess))
   (goto (label sqrt-loop)))

good-enough?とimprove演算を算術演算を使って展開した版。(abs、averageも展開)

計算機のデータパス図。

レジスタ計算機言語による制御器の定義。

(controller
 sqrt-loop
   (assign x (op read))
   (assign guess (const 1.0))
 test-good-enough
   (test (op <) (op -) (op *) (reg guess)
                              (reg guess)
                       (reg x)
                (const 0))
   (branch (label test-good-enough-<))
   (test (op <) (op -) (op *) (reg guess)
                              (reg guess)
                       (reg x)
                (const 0.001))
   (branch (label sqrt-done))
   (goto (label assign-guess))
 test-good-enough-<
   (test (op <) (op *) (op -) (op *) (reg guess)
                                     (reg guess)
                              (reg x)
                       (const -1)
                (const 0.001))
   (branch (label sqrt-done))
   (goto (label assign-guess))
 assign-guess
   (assign guess (op /) (op +) (reg guess)
                               (op /) (reg x)
                                      (reg guess)
                        (const 2))
   (goto (label good-enough)) 
 sqrt-done
   (perform (op print) (reg guess))
   (goto (label sqrt-loop)))