[ 目次, 前節, 次節, 索引 ]

5.1.2 計算機設計における抽象

われわれは, 実際は非常に複雑な「基本的」演算を含むように計算機を定義することがよくある. 例えば5.4節や5.5節で, Schemeの環境操作を基本的として扱う. そういう抽象は, 計算機の部分の細部が無視出来, 設計の他の部分に注力出来るため, 貴重である. しかし複雑さの多くを隠したという事実は, 計算機の設計が非現実的であることを意味しない. われわれは複雑な「基本演算」を, いつでももっと簡単な基本演算で取り替えることが出来る.

   GCD計算機を考えよう. 計算機にはレジスタaとbの内容の剰余を計算し, 結果をレジスタtに代入する命令がある. GCD計算機を, 基本的な剰余演算を使わずに構成しようと思えば, 引き算のようなより単純な演算を使って剰余を計算する方法を規定しなければならない. 実際このようにして剰余を見つけるScheme手続きを書くことが出来る. 

(define (remainder n d)
  (if (< n d)
      n
      (remainder (- n d) d)))
こうしてGCD計算機のデータパスで, 剰余の演算を引き算と比較テストで取り替えることが出来る. 図5.5は改善した計算機のデータパスと制御器を示す. GCD制御器の定義の命令
(assign t (op rem) (reg a) (reg b))
は図5.6に示すループを含む命令列で取り替える.



図5.5 改善GCD計算機のデータパスと制御器

(controller
 test-b
   (test (op =) (reg b) (const 0))
   (branch (label gcd-done))
   (assign t (reg a))
 rem-loop
   (test (op <) (reg t) (reg b))
   (branch (label rem-done))
   (assign t (op -) (reg t) (reg b))
   (goto (label rem-loop))
 rem-done
   (assign a (reg b))
   (assign b (reg t))
   (goto (label test-b))
 gcd-done)
図5.6 図5.5のGCD計算機の制御器の命令列


問題 5.3

1.1.7節で述べたNewton法を使い, 平方根を計算する計算機を設計せよ. 
(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))
good-enough?とimprove演算は基本演算として使えると仮定して始めよ. 次にこれらを算術演算を使って展開する方法を示せ. sqrt計算機のそれぞれの版を, データパス図を描き, レジスタ計算機言語で制御器の定義を書くことで記述せよ.


[ 目次, 前節, 次節, 索引 ]