Aizu SICP 第10,11回
一回一回の読書会が短めだったため二つ分です。
第 10 回から 2 章に入りました。2 章は P231 までと長めですがここも面白そうな話題が多いです。
P84 2 章 データを用いた抽象化の構築 ~ P 99 練習問題 2.6 までやりました。
読書会について
読書会にあたって slack の Thread を利用しているのだが、コードなどを共有しようとするとかなり場所を取る上、コードのハイライトなどができない (そういう意図で使うことを想定していないと思うので当たり前なのだが) ため、コードの共有には Gist などを利用するべきだろうかと考え中。
2 データを用いた抽象化の構築
ここからは焦点が手続きからデータに移って行く。
なぜプログラミング言語に複合データが必要なのでしょうか。その理由は、複合手続きが必要である理由と同じです。プログラムを設計する概念レベルを引き上げ、設計のモジュール性を高め、言語の表現力を強くしたいからです。 手続きを定義できることによって基本演算よりも高い概念レベルで手続きを扱 えるようになるように、複合データオブジェクトを構築できることによって、言語の基本データオブジェクトよりも高い概念レベルでデータを扱えるようになります。
(Page 85).
今更だが、この本では、抽象性が高いものが扱えるほど良いプログラミング言語であるという前提がある。少しそれについて考えてみると、ここでも言っている通り、それによって単純に言語の表現力が強くなるという点では良いのだが、抽象性が上がることによって発生する弊害というものありはする。
例えば単純な例として、抽象度が高い言語を使っていると言語の裏でどのようなことが行われているのかというのが見えにくくなることがある。ただ、自分としても基本的には抽象度は高い方が良いだろうということには賛成である。というのも抽象度が高い言語というのは抽象度をあえて低くした状態で書ける。つまり大は小を兼るということであり、まずはとりあえず抽象度が低い状態で書いていき、抽象度を上げた方が良いと思ったタイミングで抽象度を上げることができる。最初から抽象度が高い状態でプログラミングをすることは (特に、書きながら考えているような時などのプログラムの仕様が明確でない場合) 難しい上に無駄になって辛いことが多い。
したがって両方を兼るという意味で、プログラミング言語は抽象度が高い (表現力が強い) 方が良いと言って良さそうだと思った。
プログラムの中のデータオブジェクトをどうやって表すかを扱う部分と、データオブジェクトをどうやって使う かを扱う部分とを分離するという汎用的なテクニックは、データ抽象化 (data abstraction) と呼ばれる強力な設計手法です。
(Page 85~86).
抽象化という単語についてだが、データをどのように表現するかとそれをどう使うかを分離すること、ここを指してデータ抽象化と呼ぶらしい。そう言われると、手続きの抽象化というのも、それがどう実装されているかとそれをどう使うかを分離することを指していることがわかった (しかし P88 の 2.1 ですぐにこれについて言及されているが、そこでも「手続き抽象化」というような単語は表れない。そもそもそれこそが手続きであるとも言えるかもしれない)。また、
ここでは、データ抽象化によって、プログラムの部品間に適切な抽象化の壁 (abstraction barrier) を建てられるようになるというこ とを見ていきます。
(Page 87).
この抽象化の壁というのも、データ抽象化が指す境界線を指しているように考えられる。
具体的には、データ主導プログラミング (data-directed programming) というテクニックを導入します。これは、それぞれのデータ表現を独立して設計し、それらを加法的 (additively) に (つまり、修正なしに) 組み合わせられるようにするものです。
(Page 88).
最初は総称関数をイメージしたが多分それだろう。2 章の後半で表れるようだ。
2.1 データ抽象化入門
データ抽象化についてもう少し詳しく書かれている。
2.1.1 例: 有理数の数値演算
まずは、分子と分母から有理数を構築する方法はすでに持っていると仮定しましょう。
(Page 89).
さらっと書かれていたが、これができるかどうかが抽象化が上手く働いているかの基準になりそうだ。まだ実装が無い状態でも、それがどのように実装されているかという詳細を気にする必要はないという抽象化の特性により、そもそもそれが存在していなくとも、それを使う手続きの実装時に (実際には動かないという以外の) 不都合は生じない。そしてこれを指して
ここでは、プログラムを合成していくうえでの強力な戦略である希望的思考 (wishful thinking) を使っています。有理数をどうやって表現するのか、numer, denom, make-rat という手続きをどう実装するのか、まだ何も言っていません。 それでも、もしこれらの手続きを持っていたとすると、足し算、引き算、かけ 算、割り算、等価性のテストは、次のような関係を使って実行できます。
(Page 89).
というように希望的思考 (wishful thinking) と呼ぶようだ。
練習問題 2.1
(define (make-rat n d) (let* ([abs-n (abs n)] [abs-d (abs d)] [g (gcd abs-n abs-d)] [sign (if (> (* n d) 0) 1 -1)]) (cons (* sign (/ abs-n g)) (/ abs-d g))))
if は式なので (Lisp では基本的に全てが式であるので) どこでも使える。
読書会の疑問に cond と if の使い分けについて疑問があがった。基本的に三分岐以上の場合は cond を、二分岐の場合は if、一分岐 (真また偽の時だけある処理をすること) の場合は when や unless を用いる。
2.1.2 抽象化の壁
一般的に、データ抽象化の底にある考え方は、それぞれのデータオブ ジェクトの型に対して、それさえあればその型に対するどんな演算も行えるような基本演算セットを特定し、その後はデータを操作するのにそれらの演算し か使わないようにするというものです。
(Page 93).
上の単純な例を引き続き使って、有理数パッケージを設計するにあたって、gcd を実行するタイミングを構築時にするか選択時にするかを最初の段階で決められないとします。この場合、データ抽象化という方法を使うことによって、その決定を後回しにしつつ、システムのほかの部分の開発を進めるということができるようになります。
(Page 95).
ここでも基本的に抽象化は良いものとして言われているが、問題が起こることを予期して抽象化を行うことのコストと、その問題が実際に起こることによるコストを考えると、どちらを取ればよいのかというのは本当に難しいように思う。
例えば、この後の cons の実装例のように、有理数のデータを lambda を使うことになるかもしれない、ということを想定して、現在のペアで実装されている有理数へのアクセッサーとして car や cdr の別名としてのアクセッサーを用意することは、明かに過剰な心配に思える。なので単に car と cdr をそのままアクセッサーとして使っても良いのではないかとも考えられるだろうと思ってしまう。しかし、それとは逆に単に別名を与えるだけで抽象化の壁を構築できるならばしておくべきではないかとも考えられるというのもある。
このようなバランスを考慮することは現在あたっている問題によって変わり、経験や勘が占める部分が大きいように思え、とても難しいところだなあと思った。
練習問題 2.2
(define (make-point x y) (cons x y)) (define (point-x point) (car point)) (define (point-y point) (cdr point)) (define (make-segment start-point end-point) (cons start-point end-point)) (define (start-segment seg) (car seg)) (define (end-segment seg) (cdr seg)) (define (midpoint access-f point1 point2) (/ (+ (access-f point1) (access-f point2)) 2)) (define (midpoint-segment seg) (let* ([start-point (start-segment seg)] [end-point (end-segment seg)] [mid-x (midpoint point-x start-point end-point)] [mid-y (midpoint point-y start-point end-point)]) (make-point mid-x mid-y)))
練習問題 2.3
矩形を表すために二点によって長方形が構成されているとした。
(define (make-rec point-a point-b) (cons point-a point-b)) (define (start-point rect) (car rect)) (define (end-point rect) (cdr rect)) (define (points-diff x-or-y p1 p2) (abs (- (x-or-y p1) (x-or-y p2)))) (define (periphery rect) (let ([sp (start-point rect)] [ep (end-point rect)]) (* 2 (+ (points-diff point-x sp ep) (points-diff point-y sp ep))))) (define (area rect) (let ([sp (start-point rect)] [ep (end-point rect)]) (* (points-diff point-x sp ep) (points-diff point-y sp ep))))
2.1.3 データとは何か
一般的に、データというものは、何らかのセレクタとコンストラクタの集合に加え、それらが有効な表現となるために満たさなければならないと規定された条件によって定義されるものと考えることができます。5
(Page 96).
つまりデータというのはこれさえ満たせればなんでも良いということになる。条件によって定義されるものとのことだが、この定義というものは基本的にセレクタとコンストラクタの定義に対する条件であるように思える。そうであるならばデータというのは条件付き手続きの集合というように見ていいのだろうか。
5 意外なことに、この考え方は厳密に定式化することが非常に難しいものです。
(Page 96).
面白そうな話題であるので今度ちゃんと調べてみたい。
(define (cons- x y) (define (dispatch m) (cond ((= m 0) x) ((= m 1) y) (else (error "Argument not 0 or 1: CONS" m)))) dispatch) ;; これは以下のようにした方がわかりやすい気がする。 (define (cons- x y) (lambda (m) (cond ((= m 0) x) ((= m 1) y) (else (error "Argument not 0 or 1: CONS" m)))))
これは、今の段階ではただの面白い考え方のように思えるかもしれませんが、手続きによるデータの表現というものは、私たちのプログラミングのレパートリーの中で中心的な役割を果たしています。このプログラミングスタイルはよくメッセージパッシング (message passing) と呼ばれ、第 3 章でモデル化とシミュレーションの問題を扱う際には、これを基本的な道具として使うことになります。
(Page 98).
自信が無いのだが (cons 3 2) という手続きによって作られる以下のようなデータがあるとき、
(lambda (m) (cond ((= m 0) 3) ((= m 1) 2) (else (error "Argument not 0 or 1: CONS" m))))
これに対してメッセージ 0 を送ると 3 が返り、メッセージ 1 を送ると 2 が返ってくる。これを指してメッセージパッシングと呼べると考えていいのだろうか。
追記：
(define (cons- x y) (lambda (m) (cond ((equal? m :car) x) ((equal? m :cdr) y) (else (error "Argument not 0 or 1: CONS" m))))) gosh> ((cons- 3 4) :car) 3 gosh> ((cons- 3 4) :cdr) 4
こうすると Smalltalk っぽくなってよりメッセージパッシング感が出た。
練習問題 2.4
(define (cons- x y) (lambda (m) (m x y))) (define (car- z) (z (lambda (p q) p)))
展開してみる。
(car- (cons- 2 3)) ;; (car- (lambda (m) (m x y))) ;; ((lambda (m) (m x y)) (lambda (p q) p)) ;; ((lambda (p q) p) x y) ;; x
正しく x が取り出せる。cdr については car と同じようにすればよい。
(define (cdr- z) (z (lambda (p q) q)))
練習問題 2.5
(define (cons- x y) (* (expt 2 x) (expt 3 y))) (define (car-cdr pair base) (let loop [(pair pair) (count 0)] (if (= (modulo pair base) 0) (loop (/ pair base) (+ count 1)) count))) (define (car- pair) (car-cdr pair 2)) (define (cdr- pair) (car-cdr pair 3))
car-cdr では名前付き let と呼ばれるものを利用している。
練習問題 2.6
頭がごちゃごちゃになっていたので宿題