設計と実現

それぞれの手続きの実現について考えてゆきます。

式(make-rat

a b

⁾ を評価すれば 、分子が

a

^で分母が

b

である有理数が作られ、返され るものとします²。式 (is-rat?

r

^{) を評価すると、}

r

^{が有理数ならば真 #tを、そうでな}

ければ偽 #fが返されるものとします。以上のことを考えると、有理数データの中には、

有理数であることの印

分子

分母

1もちろん 、ここに挙げているものが絶対的なものではありません。実習

14

では 、違った手続き群を示 しています。

2ratは、

rational

^{を表しています。}

の

3

つが必要であることが分ります。

ここでは有理数データを、有理数であることの印

(

^{記号 rat}

)

、与えられた分子と分母を、

リストとして表現する実現方法を採ります。これに従った手続き make-rat は、次のよう になります。

(define (make-rat a b) (list 'rat a b))

上の手続きの中で、ratの前に ' が付いています。これは引用符

(quote)

^{と呼ばれるも}

のでした。これがないと ratは変数として使われてしまい、記号 rat をリストの中に入 れる、ということができません。

次に、与えられたデータが有理数データの判定をする手続きを考えます。有理数データ ど うかは、リストの第一要素が記号 ratであるかど うかで判別します。リストの第一要素 を取り出す

Scheme

^{手続きは car}であることを思い出せば 、手続きis-rat?は以下のよう にすればいいでしょう。

(define (is-rat? r) (eq? (car r) 'rat))

手続きeq?は、与えられた

2

つの引数が同一のものかど うかを調べるものでした。これに より、リストの第一要素が印 ratと等しいか判定しています。

Scheme

^でこれら

2

つの手続きを定義してから、実行してみます。

> (define r1 (make-rat 1 3))

| 1/3

^を作る

#<unspecified>

> (is-rat? r1)

| r1

^{は有理数データですか}

?

#t

|

^そうです

こんどは、有理数データでないものを引数に与えて、is-rat? が正しく機能するか調べ てみましょう³。

> (is-rat? 10)

ERROR: car: Wrong type in arg1 10

|

^{エラーが生じた}

!

許されていないデータ型に対して car を行った 、とエラーメッセージに出ています。

is-rat? の定義をもう一度見てみれば 、引数 r がリストかど うかを確認せず、いきなり

carを行なっています。

3数学的な意味では

10 = 10

⁼

1

^{なので 、}

10

は有理数であるといえます。ですが計算機上では 、

10

^には

「有理数型の印」がないために、有理数の数ではないと考えます。

上の例のように 、数などに対して car を実行するとエラーになります。そのため、前 もってデータがリストかど うかを調べるようにしないといけません。与えられたデータが リストかど うかを調べるには、手続き list? を使います。

手続き is-rat? を次のように改良します。これはどんな引数に対しても、エラーを起

こさずに動作します。

(define (is-rat? r) (and (list? r)

(eq? (car r) 'rat)))

上のプログラムでは、特殊形式andが出てきています。これは、与えられた式を順に評 価してゆき、評価結果が #fのものが現れたらそこで実行をやめて #fを返します。もしす べての引数の評価結果に#f のものがなければ 、一番最後の引数の評価結果が andの値と なります⁴。

以上で有理数を作る手続きと、データが有理数かど うかを判定する手続きができました。

今度は有理数に対する演算手続きに移ります。有理数

r

^{1 と}

r

² に対する演算は、次のよう に定められます。

[

^加算

] r

¹

+ r

²

= r

^1の分子

r

^2の分母

+ r

^1の分母

r

^2の分子

r

^1の分母

r

^2の分母

[

^減算

] r

^1,

r

²

= r

^1の分子

r

^{2の分母 ,}

r

^1の分母

r

^2の分子

r

^1の分母

r

^2の分母

[

^乗算

] r

¹

r

²

= r

^1の分子

r

^2の分子

r

^1の分母

r

^2の分母

[

^除算

] r

¹

=r

²

= r

^1の分子

r

^2の分母

r

^1の分母

r

^2の分子

これらの手続きを作る前に 、有理数デ ータの分子部分 、分母部分を取り出す手続き rat-num、rat-den を作ります⁵。リスト

s

^の第

i

番目の要素をとり出す手続きとして 、

(list-ref

s i

⁾があるのでこれを使うことにします。

(

なお、リストの一番最初の要素は

第

0

^{番目になります。}

)

これらの手続きを作るとき、与えられたデータが有理数型かど う かのチェックを忘れてはいけません。与えられたデータが有理数型なら分子あるいは分母 部分を抜き出して返すものとし 、そうでなければエラーとします。エラーとするには、手

続きerrorを使います。この手続きerrorは、引数に与えられた式を表示してプログラム

の実行を強制中断します。

(

^{手続きerrorは}

Scheme

処理系に依存した手続きです。この手 続きを使用するときは、使っている処理系のマニュアルを参照してください。

)

rat-num

,

^rat-den は、それぞれ次のようになります。

4ここで、左から「順に」評価をしてゆく、というのが大事な点です。引数すべてを評価してから、その 結果をandに渡すと、引数に

10

を与えるとまた同じエラーになってしまします。

5分子、分母のことを英語ではそれぞれ

numerator, denominator

^{といいます。}

(define (rat-num r) (if (is-rat? r)

(list-ref r 1)

(error "rat-num - not rational number"))) (define (rat-den r)

(if (is-rat? r) (list-ref r 2)

(error "rat-den - not rational number")))

error の引数で rat-num - not rational numberとしているのは、どの手続きの中で何 が原因でエラーが起きたかを分かるようにするためのものです。

ではこれらを試してみます。

> (define r (make-rat 1 3))

#<unspecified>

> (rat-num r) 1

> (rat-den r) 3

> (rat-den 10)

Error: rat-num - not rational number

>

これらを使って加算を行なう手続き rat:+ を作ります。もちろんこの手続きの中でも、

引数が有理数であるかど うかをチェックしないといけません。有理数の加算の定義に従う と、次のような手続きになります。

(define (rat:+ r1 r2)

(if (and (is-rat? r1) (is-rat? r2)) (make-rat

(+ (* (rat-num r1) (rat-den r2)) (* (rat-den r1) (rat-num r2))) (* (rat-den r1) (rat-den r2)))

(error "rat:+ - not rational number"))) このプログラムは、次のような構造をしています

:

(define (rat:+ r1 r2)

(if ^h r1 r2ともに有理数データか

?

ⁱ

(make-rat

h 分子の計算ⁱ

h 分母の計算ⁱ )

hエラーとするⁱ ))

まず最初に、

2

^{つの引数r1 と r2}がともに有理数データかど うか調べています。もしそう なら、 分子と分母を加算の定義にしたがってそれぞれ計算し 、make-rat の引数に与えて あらたな有理数を作っています。もし

2

つの引数のいずれかが有理数データでなければ 、

error によってエラーとし 、実行を中断します。

では、これを実行してみましょう。

> (define r (make-rat 1 3))

| 1/3

#<unspecified>

> (define s (make-rat 2 5))

| 2/5

#<unspecified>

> (define t (rat:+ r s))

| t = 1/3 + 2/5

#<unspecified>

> (rat-num t)

|

^分子は

11

11

> (rat-den t)

|

^分母は

15

15

ちゃんと

1 = 3 + 2 = 5 = 11 = 15

が計算されていることが分かります。

有理数の減算を行なうプログラムも同様にして作れます

:

(define (rat:- r1 r2)

(if (and (is-rat? r1) (is-rat? r2)) (make-rat

(- (* (rat-num r1) (rat-den r2)) (* (rat-den r1) (rat-num r2))) (* (rat-den r1) (rat-den r2)))

(error "rat:- - not rational number")))

このプログラムが正しく動くかど うかは、各自でチェックしてみて下さい。

5.1.2 ^まとめ

本実習で作った有理数計算手続き群を振り返ってみます。まず、以下のような手続き群 を作りました。

分子と分母から、有理数データを生成する手続き

有理数製造手続き

. ........

. ......

. ......

. ......

. .....

........ . .....

....... .......

. ......

. ......

. ......

. ......

. .

. ... . .. .... . .. .... . . . . . . . . . . . . . . . . . . . .

. ... ........

. .......

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. ..........

......

...

.....

. ..

....

...

.....

. ...........

.... . ... .. . . . .. ... . . . ... . . . .. ... .... . ............

.....

..

...

. .

. ..

. ...

. .

...

. .

. . ..

..

...

. . ..

. ................

. ..............

.......

. ...

. . .

. ..

. .

. .

.

. . .

. .

.

. .

. . .

.

. .

. . .

.

. .

.

. . . .

. .

. .

. . . .

. . .

. . . . .

. . . .

. . . .

. . . .

. . . .

. . .

. .

. . .

. .

. .

.

. .

.

. . .

. .

. .

. .

.

. .

. .

.

. . .

.

. . .

.

. .

. .

.

. . .

. . . .

. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . .

. . . . .

. . . .

. . . .

. . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . ... ... . .. ....

分子

a

分母

b

^{make-rat 有理数}

a=b

..

. ......

. ......

. ......

. .......

......

. ......

. .....

........

......

. ......

. ......

. ......

. .......

. .................... . . . . . . . . . . . . . . . . . .

分母取り出し手続き 有理数

a=b

^{....................................................................................................................................}

. .. ........

...... . . . . . . . . . . . . . . . . . . . . .

. ......

...... . ....... . . . . . . . . . . . . . . . . . ....

. .. .... . .. .... . . . . . . . . . . . . . . . . . . . . ..

. . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. .

. rat-num

rat-den

分子

a

分母

b

分子取り出し手続き

. . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . ... .............

. .....

. ..

. ...

...

. ...

. ....

....

. .......

. .. .... .... . . . .. . . . ... .. . .. .. ... . . .. ..... ......

.....

. ....

...

..

...

. . .

. ..

..

...

..

. ...

. ..

..

. .......

.....................

..........

. . ...

. ...

..

....

.

. .

.

. . .

. .

.

. . .

.

. .

. .

. .

. .

. .

. . .

. .

. .

. .

. . . . .

. . . .

. . . .

. . . .

. . . . .

. . .

. . .

. . .

. .

. . . .

.

. .

.

. .

. .

. .

.

. ..

.

. . .

.

. .

. .

.

. .

. .

. .

. .

. .

.

. . . . .

. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . . .

. . . . .

. . . .

. . . . .

. . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. ... . . .

図

5.1:

有理数データとアクセス手続き

有理数データから分子と分母を取り出す、複合的なデータへのアクセスをする手続き

与えられたデータが有理数型かど うかを判定する手続き

次に、これらを組み合わせて、有理数型のデータに対する各種演算をする手続きを作りま した。

本実習で採用した、印、分子、分母をリストにして保持する、という具体的な実現方法 は、手続きmake-rat

,

^rat-num

,

^rat-den

,

^is-rat? によって完全に隠されています。その ため、具体的な実現方法を知らなくても、有理数に関する計算ができます。

別の見方をすれば 、make-rat

,

^rat-den

,

^rat:+などを使っている限り、データの実現方 法を変えてしまっても大丈夫です。データや手続きがどのような形で実現されているかが 大切なのではなく、重要なのはその機能と性質で、データに対してどのような手続きが用 意されていて、それらがどのような働きをするか、ということです。手続き群を改良する 人の立場でいえば 、手続きの呼び出し側から見た手続きの振舞いが以前のものと同じなら、

どのように変更してもかまいません。

以上の考え方はデータ抽象

(data abstraction)

と呼ばれます。データ抽象ではデータが 実現されている方法を隠し 、データへのアクセスするための手続きを提供します。そして、

その手続きでしかデータへのアクセスを許しません。データを抽象化することにより、デー タの具体的な実現法には依存しなくても済みます。このようなデータ抽象によるデータ型 を抽象データ型

(abstract data type)

と呼びます。また、データの詳細な内部構造を見え なくすることを、情報隠蔽

(information hiding)

^{といいます。}

本実習で作成したプログラムでは、データとデータへアクセスするための手続きが一体 となってはいません。言い替えれば 、新たにつくり出されたデータ型を使ったプログラム を書くときに、使うデータ型とそれに対応した手続きをすべて把握しておき、適切な手続 きを呼び出すようにしなくてはいけません。取り扱うデータ型の数が少ないときはあまり 問題は生じませんが 、データ型の数が膨大になってくると、それぞれのデータ型に対応し

た手続きの名前を記憶しておくことは難しく、間違ったプログラムを書いてしまう可能性 が多くなります。

これを解決する方法として、「手続きにデータを渡す」のではなく、「データに指令を送 る」方法があります。この方法なら、違うデータに対しても同一の指令を送ることができ、

しかもその振舞いをデータごとに違ったものにすることができます。この方法はメッセー ジ伝達

(message passing)

と呼ばれますが 、詳しいことは後の実習で学びます。

練習問題

1.

有理数同士の乗算を行なう手続き rat:*を作りなさい。

2.

^関数

f

^を、

f ( r ) = r + r

²

+ r

^{3 とします。}

(

^ただし

r

^{は有理数とします。}

)

^{この関数を}

計算する手続き fを、rat:+ と rat:* を使って作りなさい。

3.

有理数同士の除算を行なう手続き rat:/を作りなさい。

4.

有理数の逆数を計算する手続き rat:inv を作りなさい。

5.

^{手続き display や write}を使って有理数データを表示すると、(rational-number

11 15) のようになってしまいます。これだと美しいとはいえませんし 、内部のデー

タ構造が表示されるために好ましくありません。そこで、11/15 のように分数形式 で表示する手続きrat:print を作りなさい。

(

^ヒント

:

^{display あるいは write を}

使います。

)

6.

引数として与えられた有理数が 、約分可能かど うかを調べる手続き reducible? を 作りなさい。もし約分可能であれば真#t を返し 、そうでなければ偽#fを返すもの とします。

(

^ヒント

: a

^と

b

との最大公約数を求めるには、手続き (gcd

a b

^{) を使い}

ます。

)

7.

引数に与えられた有理数を約分した有理数を返す手続きrat:reduceを作りなさい。

8.

もし分母が負ならば 、分母を正にして分子の符号を反転するよう、手続きrat:reduce を改造しなさい。

9.

本実習で作った演算手続きでは、計算結果が約分されていません。各演算手続きが計 算結果を約分するよう、それぞれの手続きを変更しなさい。

10. 2

つの有理数の加算を行なう過程を、順を追って表示しようと思います。与えられた

2

^{つの有理数を}

r

^{1 と}

r

^{2 とし 、}

(1)

^{最初に与えられた}

2

つの有理数を表示し 、

(2)

^必

要ならば通分を行なってその結果を表示し 、

(3) r

¹

+ r

² の計算結果を表示します。さ らに

(4)

約分可能でならそのことを表示して、約分した結果を表示します。以上のこ

ドキュメント内 Copy Free \Scheme " Copy Free \Scheme " 2 (2a) (2b) (2c) 3 (3a) (The Internet) (3b) (6a) (6b) (6c) (6d) Scheme (ページ 98-107)