『2.2 階層データ構造と閉包性』
まとめ
ここでは、consを用いて
(cons 1 (cons 2 (cons 3 (cons 4 nil))))
といった、「値を指すポインタ」と「別の対を指すポインタ」からなる連なりを表現させ、それによって「並び（Sequence）」を構成させる方法・利点を紹介している。
また上記のようなリストだけでなく、次のような木を表現させる手法も紹介している。
(cons (list 1 2) (list 3 4))
出てくるキーワードと、その説明は以下のとおり。
- 閉包性(closure property)
- あるデータが部品から出来ていて、その部品がまた部品からできている。という階層的・内部完結的な構造を持つこと
- この閉包性は、世間一般のクロージャ（データを束縛した手続き）とは指しているものが異なるので注意。本書では抽象代数の用語を使っている。
・・・集合の要素にある演算を作用させて得られた要素が、またその集合の要素であるなら、要素の集合はその演算の元で閉じている（＝閉包である）・・・
この節はとても長いしバリエーションに富んでいるので、取り組みがいのある内容だ。
各小節の内容
2.2.1 並びの表現
リストは「値を指すポインタ」と「別の対を指すポインタ」からなる対の連なりによって表現できる。たとえば
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
という入れ子になった対によって、1-4の値の集合が表現できる。
リストのポイントは、
- それぞれの対でcar部は値・cdr部は次の対へのポインタを表している
- 最後の対のcdr部はnil(*1)を指している
という点。で、これを簡単に表現するのが「list」という基本手続き。次の式は上のconsの鎖と同じことを表現している。
(list 1 2 3 4)
一般化すると次のとおり： (list <a1> <a2> ... <an>)
ずいぶんリストであることが分かりやすくなった。ちなみに「(list 4)」というように定義することもできるみたい。この場合は「(cons 4 nil)」としたのと同じ(*2)。
リスト演算
リストに対して演算を行う場合は、通常「cdrダウン」と「consアップ」の2手法がよく用いられる。
- 「cdrダウン」
- cdr部を再帰的に辿っていき、その時々のcar部を（必要ならば）順に評価していく方法。結果には要素を評価した結果が返る。
- 「consアップ」
- 「cdrダウン」によって得られる1つずつの要素を（演算を行った後で）再びconsによって組み立てていく方法。結果には再構築されたリストが返ってくる。
あと、問題2.20には手続きに任意個の引数を取る方法が書いてある。ここは一つずつ写経しよう。
まず最初は2個以上の引数を取る手続きの定義方法：
(define (f x y . z) <body>)
xとyには値（に限らないけれど）が入り、残りはリストとしてzに入る。引数が2個だけだった場合、zには空リスト(*3)が渡される。
そして、0個以上の引数にしたい場合は次の定義：
そして、0個以上の引数にしたい場合は次の定義：
(define (g . z) <body>)
にする。任意個の引数は全てzにリストとして渡される、というわけ。ちなみにlambdaで同じように書こうとした場合、fやgは
(define f (lambda (x y . z) <body>)) (define g (lambda (z <body>)))
になるとのこと。
リスト写像
「リストの各要素に対して、何かの式を適用した結果をリストとして返す」という手続きを実現するために使うmap手続きの紹介。mapはGaucheやguileの基本手続きとして用意されている。
- map
- ある変換をリストの各要素に作用させ、その結果をリストで返す。
mapは簡単な手続きだけど、自分のためにも写経しておく。
(define (map proc items)
(if (null? items)
()
(cons (proc (car items))
(map proc (cdr items)))))
リストのcar部をprocで評価して、その結果とcdr部のmapとで対を作るわけか。なるほどなるほど。
ここで思ったんだけど、mapは必ず要素の先頭から処理を行っているので、つまり実行順序があるということを保証したりはしてくれるのだろうか？いや、1.1.5 作用的順序で出てきた正規順序の評価モデルではmapを一度完全に展開してしまうので、順序を保証しているわけではないか。
常々思っているんだけど、関数型言語ではどうやって順序を説明するのだろう？
2.2.2 階層構造
リストは(1 2 3 4)というような単純な数列だけでなく、リストの要素がまたリストであるという、より一般化したデータ構造でも表現できる。
(define x (cons (list 1 2) (list 3 4)))
を評価した時の結果は、( (1 2) 3 4)となる。(car x)がリストであることに注目。
ちなみに最初上の定義を見たときに、「あれ？( (1 2) (3 4) )にはならないの？」とはまってしまった。これは(list 1 2)と(list 3 4)をconsによって対にしているからであって、疑問に思ったリストにするには
(define y (list (list 1 2) (list 3 4)))
としなければならない。
そして、本小節ではリストの長さを得たりその他各種操作を行う手続きを一般化したリスト構造でも適用するための方法・問題が紹介されている。
- pair?
- 引数が対であれば#tを返す。対のとき、()のときは#fを返す。
(define (count-leaves x)
(cond ((null? x) 0)
((not (pair? x)) 1)
(else (+ (count-leaves (car x))
(count-leaves (cdr x))))))
本書の62ページ脚注にもあるけれど、cond手続きでの条件分岐の並び順には注意が必要だ。空リスト()はnull?でも該当するし、(not (pair? x))にも該当するから。
リストを扱う処理を書く時のおまじないとして、
リストを扱う処理を書く時のおまじないとして、
- 空リストかどうかを調べる
- 対かどうかを調べる
という順番をしっかり覚えておいた方が良さそうだ。でもこれ、1.1.5 作用的順序で出てきた作用的順序に依存した評価だよなあ。正規順序の評価だったらどうするんだろう。
木の写像
map手続きは並びを扱うことが出来るのだけれど、再帰を含ませることで木構造に対しても抽象化の能力を得られる。これによって、mapが並びに対する演算の多くを実現できたように、木に対しての演算を抽象化できる、という説明。
(define (scale-tree tree factor)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree sub-tree factor)
(* sub-tree factor)))
tree))
木を掘り下げていき、その都度出てくるリストに対してfactorをかけているんだね。
2.2.3 公認インタフェースとしての並び
「公認インタフェース」というのは分かりづらい訳になってしまっているかもしれない。原文は「Conventional Interface」となっていて、つまり汎化されたインタフェースのことを表している。
以下の無関係に見えるソース2種類から抽象概念を抜き出し、それぞれをモジュール化する。そのことで順番の入れ替えや将来の変更に強くなるプロセスを作り上げることが大事だということを伝えている。
(define (sum-odd-squares tree) (cond ((null? tree) 0) ((not (pair? tree)) (if (odd? tree) (square tree) 0)) (else (+ (sum-odd-squares (car tree)) (sum-odd-squares (cdr tree))))))
(define (even-fibs n) (define (next k) (if (> k n) () (let ((f (fib k))) (if (even? f) (cons f (next (+ k 1))) (next (+ k 1)))))) (next 0))
これを
- enumerate （データの数え上げ）
- filter （データの抽出）
- map （処理の適用）
- accumulate （データの積み重ね）
という4つのブロックに分ける。するとプログラムはそれぞれ
| enumerate(tree) | → | filter(odd?) | → | map(square) | → | accumulate(+, ()) |
と
| enumerate(integer) | → | map(fib) | → | filter(even?) | → | accumulate(cons, ()) |
というプロセスに分割できるようになる。あとは各ブロックの処理を実装し、接続さえすれば良いわけだ。
思うに、これはSchemeのリストというデータ構造がしっかりしているから、各ブロックの順番がどのようになっても問題がないんだと思う。これが各モジュールで異なる型・出力を出すようにしているのであれば、色々と問題が発生するはず。
やはり、データフローダイアグラムとインタフェースは大事にしないとなあ、と思った。
やはり、データフローダイアグラムとインタフェースは大事にしないとなあ、と思った。
写像の入れ子
公認インタフェースの考え方を拡張し、ループの入れ子で実現する処理も行わせることが出来る。
「ループの入れ子」っていうのは、つまりCでいうところの
「ループの入れ子」っていうのは、つまりCでいうところの
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
array[i][j] = X;
みたいなもの。これを手続きの並びで表現することも出来るよ、という話。
ここで{1,2,3}のような順列の全ての組み合わせ（{1,2,3},{1,3,2},...）を出力する手続きが紹介されていて面白そうなので写経。
(define (permutations s) (if (null? s) (list s) (flatmap (lambda (x) (map (lambda (p) (cons x p)) (permutations (remove x s)))) s))) (define (remove item seq) (filter (lambda (x) (not (= x item))) seq))
gosh> (permutations '(1 2 3)) ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
えっと、色々が抽象化されてくると処理が追えなくなってきている・・・。
書籍にある生成の順番をこちらにも書いてみると、
- Sの各要素xに対し、集合S-x(＝xを除いたSの要素からなる集合のこと)の順列の並びを再帰的に生成する
- その並びの前にxを連結する
- これはSの各xについて、Sのxで始まる順列の並びを生成する
- すべてのxについてこの並びを組み合わせる
- Sの全ての順列の完成
となるとのこと。これが上記のソースによって行われているらしい。自分で作れって言われても難しいなあ。どうせこの後の演習で出てくるんだろうけれどさ。
2.2.4 例：図形言語
さあいよいよ見栄えのする節だ、と思っていたら問題発生。何と、うちのMac(Mac OSX10.3.9)では表示に必要なSLIBをビルドできない。
エラーメッセージを見てもちょっと理由が分からないし、困った。(*4)
エラーメッセージを見てもちょっと理由が分からないし、困った。(*4)
というわけで、この節は脳内インタープリタで進めていこうと思う。
高階演算
ここでのポイントになっているのは、図形言語の閉包性。
(wave)
も、
(define wave2 (beside wave (flip-vert wave))) (define wave4 (below wave2 wave2))
も、どれも画像を表示させるというペインタであり、どれも外から同じように使用できるという点が重要。デザインパターンでAdaptorパターンがあったけれど、あんなイメージかな。重ねても重ねてもインタフェースが変わらないという。いや、Compositeパターンか。
だから、抽象化がものすごく容易になる。出力を変えたいときに、手続きを呼ぶ側を変えなくても済むから。途中の処理だけ差し替えるというのもOK。
これまでもリストという同じインタフェースを返す手続きを沢山作ってきたように、小さなパーツの組み合わせを一貫したインタフェースのままで表現することは大事なんだね。
これまでもリストという同じインタフェースを返す手続きを沢山作ってきたように、小さなパーツの組み合わせを一貫したインタフェースのままで表現することは大事なんだね。
フレーム
図形言語を描く際に予め座標系を定義してあげることで、アフィン変換程度の変形が行えるという話。
ポイントは、図形を描く手続きに依存しないつくりになっていること。与えられたxy座標を適切に変換するだけの処理として実装することで、図形を描く手続きがどう変化しても対応できるようになっている。
ポイントは、図形を描く手続きに依存しないつくりになっていること。与えられたxy座標を適切に変換するだけの処理として実装することで、図形を描く手続きがどう変化しても対応できるようになっている。
一般的な設計では常套手段だ。
ペインタ
ペインタ、という図形描画を行う手続きに対して抽象化の考えを推し進め、フレームを与えることでその内部に沿った形で線分を書けるようになる。
ポイントとして、ペインタを手続きとして表現することで、他の描画処理と合成・混同できるようになることだ。
ここで、問題2.23でも出てきたfor-eachという手続きが使われている。この手続きはGaucheにも標準実装されていて、マニュアルには次のように書かれている。
| Function: for-each proc list1 list2 ... |
| [R5RS] 手続きprocをリストの各エレメントに対して順に適用します。procの結果は捨てられます。for-eachの戻り値は定義されていません。複数のリストが与えられた場合、一番短いリストが終了した時点でfor-eachは終了します。 → Gaucheリファレンスマニュアル：マッピング |
draw-lineという戻り値が必要ない（かつ副作用のある）手続きを使用しているから、mapを使えないんだね。なるほど。
頑健な設計のための言語レベル
これら図形言語を通して学んだことは、
- レベルに応じた部品を組み合わせて複雑さに対応する
- 各レベルは、その次のレベルの基本要素として扱うよう設計する
- 同じインタフェースを持つことで、組み合わせても外からは同じ使い方ができるようにする
を意識してデザインする、ということ。資料ではこれを「成層設計(Stratified design)」と呼んでいる。それにより、
- 仕様の小規模な変更は，一部の実装変更で対応できる
- できるだけ多くの階層で変更に対応できる（どのレベルの変更も許容できる）
というメリットが生まれるわけだ。とはいえ、そこまで頑健な設計にするのは相当難しいけれどね。実際には、当初は「絶対アリエナイ」と思っていた仕様変更が入ることはざらにあるわけで。
個人的には、この辺の完成は苦労することでしか身に付かないと思ってます。
