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

2.1.1 例: 有理数の算術演算



有理数を使って算術演算をしたいとしよう. それらを足し, 引き, 掛けまた割り, また二つの有理数が等しいかのテストが出来たいと思う.

   分子と分母から有理数を作る方法があると仮定して始めよう. また有理数から分子や分母を取り出す(選択する)方法もあるとする. その上, 構成子と選択子は手続き

(make-rat n⟩  ⟨d)は分子が整数⟨n⟩, 分母が整数⟨d⟩の有理数を返す.

(numer x) 有理数⟨x⟩の分子を返す.

(denom x) 有理数⟨x⟩の分母を返す.

として使えるとする.

   ここでは強力な 合成の戦略: 希望的思考(wishful thinking)を使っている. 有理数がどう表現されているか. 手続きnumer, denommake-ratがどう実装されているかはまだ話していない. それでもこの三つの手続きがあれば, 次の式を使い, 足し, 引き, 掛け, 割り, 等価をテストすることが出来る:










   これらの式を手続きに表せる:


(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))


(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))


(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))


(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))


(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

   これで選択子と構成子numer, denommake-ratを使って定義した有理数に関する演算が出来た. しかしそれらはまだ定義していない. 分子と分母を糊づけにして, 有理数を作る方法が必要である.

データ抽象の具体的レベルが実装出来るよう, われわれの言語には, 基本的手続き consで構成される (pair)という合成構造がある. この手続きは二つの引数をとり, 二つの引数を部分として含む合成データオブジェクトを返す. 対があれば, その部分を基本的手続き car cdrで取り出すことが出来る.2 cons, carおよび cdrは次のように使うことが出来る:
(define x (cons 1 2))

(car x)
1

(cdr x)
2
対は基本データオブジェクトのように名前をつけたり操作したり出来ることに注意しよう. その上consは要素が対などであるような対を作るのにも使える:
(define x (cons 1 2))

(define y (cons 3 4))

(define z (cons x y))

(car (car z))
1

(car (cdr z))
3
2.2節でわれわれは, 対を組み合せる能力は, 対があらゆる複雑なデータ構造を作り出す, 万能部品として使われることに他ならないことを見る. 手続きcons, carcdrで実装される一種の合成データ要素, (pair)は, 唯一必要な糊である. 対で構成するデータオブジェクトを リスト構造の(list structured)データという.
有理数の表現
対は有理数システムを仕上げる自然な方法を提供する. 有理数を二つの整数: 分子と分母の対で表現しよう. するとmake-rat, numer denomは次のようにすぐに実装出来る:3

(define (make-rat n d) (cons n d))


(define (numer x) (car x))


(define (denom x) (cdr x))
また, 計算の結果を表示するため, 有理数を分子, 斜線, 分母と 印字する:4

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))
では, 有理数手続きをやってみよう.
(define one-half (make-rat 1 2))

(print-rat one-half)
1/2

(define one-third (make-rat 1 3))

(print-rat (add-rat one-half one-third))
5/6

(print-rat (mul-rat one-half one-third))
1/6

(print-rat (add-rat one-third one-third))
6/9

   最後の例で, われわれの有理数実装は, 有理数を既約にまでは簡約しないことが分る. make-ratを変更して, この点を改善しよう. 1.2.5節のようなgcd手続きがあって, 二つの整数の最大公約数が得られるなら, 対を構成する前に gcdを使い, 分子と分母を既約にまで, 簡約出来る.


(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))
そこで希望どおり,
(print-rat (add-rat one-third one-third))
2/3
となる. この修正は構成子make-ratの変更だけで実現出来, ( add-ratmul-ratのような)実際の演算を実装している手続きはいずれも変更していない.

問題 2.1


正負両方の引数を扱う改良版make-ratを定義せよ. make-ratは符号を正規化し, 有理数が正なら, 分子, 分母とも正, 有理数が負なら, 分子だけ負とする.



2 名前 consは「construct(構成する)」の意である. 名前 car cdr IBM 704でのLispの最初の実装からきた. この計算機のアドレス方式は記憶場所の「アドレス」と「デクレメント」が参照出来るようになっていた. carは「Contents of Address part of Register(レジスタのアドレス部)」, cdr(クダーと読む)は「Contents of Decrement part of Register(レジスタのデクレメント部)」を意味する.

3 選択子と構成子を定義するもう一つの方法は

(define make-rat cons)
(define numer car)
(define denom cdr)

最初の定義は名前make-ratを, 対を構成する基本的手続きのconsの値に対応づける. make-ratconsは同じ基本的構成子の名前となる.

選択子と構成子はこのように定義すると効率はよい: make-rat consを呼び出すのではなく, make-ratconsなのである. make-ratが呼び出された時, 二つではなく, 一つの手続きが呼び出される. ところがこうすると, 手続き呼出しをトレースしたり, 手続き呼出しにブレークポイントを設定したりの虫とりツールを使えなくする: make-rat が呼び出されたのは知りたいだろうが, consが呼び出されたすべては知りたくないであろう.

本書では, この形の定義は使わないことにした.

4 displayはデータを印字するSchemeの基本手続きである. Schemeの基本手続きnewlineは改行する. これらの手続きは有用な値は返さないので, 以下のprint-ratの使用例では, print-ratが印字するものだけを示し, print-ratの返す値を解釈系が印字するものは示さない.

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