[SICP] SICP第2章読了
第2章の最後の課題は残しているが、読了した。データの抽象化の威力をまざまざと見せられた。
なんといってもこの章のクライマックスの多項式の演算プログラム。
データの型およびClojureでいうマルチメソッドのシステムを自前で用意して、実にエレガントに解いてみせる。これがポリモーフィズムの真価かと。
多項式の係数が多項式の場合も、全く特別扱いする必要なく、再帰的に処理できてしまう。美しい！
取り扱う問題が数学の問題なので、泥臭い部分がなくて済んでしまうのかもしれない。
しかし教科書としてはこれがいい。整理しやすく記憶に残る。データの抽象化とポリモーフィズムがどういうケースで生きるかイメージに残るから応用しやすい。
mapのループをforで表現する
前回（mapと再帰で木構造を扱う - Programmer's Note）は、mapと再帰で木構造を扱う処理を書いたが、mapはシーケンスを順になめていく高階関数であって、いわゆるコレクションを扱うfor文と変わらない。 Clojureにもforマクロは用意されていて、かなり表現力が高い。
前回のscale-tree関数は、
(defn scale-tree [tree factor] (map (fn [sub-tree] (if (coll? sub-tree) (scale-tree sub-tree factor) (* sub-tree factor))) tree))
だが、これをforを使って書き直すと以下になる。
(defn scale-tree [tree factor] (for [item tree] (if (coll? item) (scale-tree item factor) (* item factor))))
処理内容がだいぶ読みやすくなった。mapは汎用性が高く利点はあるが、無名関数の定義(fn [..] ..)が入る分コードが煩雑になり読みにくくなる。
Schemeなどだと無名関数はいわゆるlambda関数なので、表記が(lambda (...) ..)でさらに読みにくい。
forの場合は、扱うコレクションと各要素を代入する変数が一緒に、要素に対する処理の手前に置かれるので、コードを追いやすい。
プログラムの可読性はシンタックスがもろに効いてくることを実感させられる。
さて、SICPにはmapを使った以下のような例（練習問題）が出てくる。
(defn unique-pairs [n] (reduce concat (map (fn [i] (map (fn [j] (list i j)) (range 1 i))) (range 1 (inc n)))))
これは、1 <= j < i <= nのiとjのペアの集合を作る関数だ。
実行結果は以下のようになる。
(unique-pairs 6) ;-> ((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4) (6 1) (6 2) (6 3) (6 4) (6 5))
このコードはmapを二重に使っていて読みにくいが、forを使うとすっきりと表現できる。
(defn unique-pairs [n] (reduce concat (for [i (range 1 (inc n))] (for [j (range 1 i)] (list i j)))))
これにとどまらず、Clojureのforマクロはかなり便利で、二重ループはもっとすっきり表現できる。
(defn unique-pairs [n] (for [i (range 1 (inc n)) j (range 1 i)] (list i j)))
なんと、これだけで済んでしまった。 Clojure見事なり。
mapと再帰で木構造を扱う
SICP楽しすぎるな。 第２章の途中、mapを使って木構造のデータ処理を紹介していて、えらく感動した。
題材は以下のとおり、木構造の中の全要素に対して任意のfactorを掛ける関数scale-treeを作ること。
(def ttree (list 1 (list 2 (list 3 4) 5) (list 6 7))) (scale-tree ttree 10) ;-> (10 (20 (30 40) 50) (60 70))
再帰を使うのは分かりやすい。
(defn scale-tree [tree factor] (cond (not (coll? tree)) (* tree factor) (empty? tree) nil :else (cons (scale-tree (first tree) factor) (scale-tree (rest tree) factor))))
一回分解して組み立て直しているコストはかかるが、木構造と再帰は実に相性がよい。
処理の流れは以下のとおりで、データの先頭と残り取り出して、ツリー階層を下っている。 （カッコがあるとデータが分かりにくいので、関数呼び出しは簡略的に記す。）
1: scale-tree (1 (2 (3 4) 5) (6 7)), 10
2: cons scale-tree 1, 10
scale-tree ((2 (3 4) 5) (6 7)), 10
3: cons 10
scale-tree ((2 (3 4) 5) (6 7)), 10
4: cons 10
cons scale-tree (2 (3 4) 5)), 10
scale-tree (6 7), 10
5: cons 10
cons cons 2, 10
((3 4) 5), 10
scale-tree (6 7), 10
...
これをmapを使うと以下のように書ける。
(defn scale-tree [tree factor] (map (fn [sub-tree] (if (coll? sub-tree) (scale-tree sub-tree factor) (* sub-tree factor))) tree))
処理の流れは下記のとおり。
1: scale-tree (1 (2 (3 4) 5) (6 7)), 10
2: map処理
fn 1
fn (2 (3 4) 5)
fn (6 7)
3: map処理
10
scale-tree (2 (3 4) 5)
fn (6 7)
4: map処理
10
map処理
fn 2
fn (3 4)
fn 5
fn (6 7)
...
これの何がすごいかって？
実際には木構造を再構築しているのにconsをまったく使用していないところだ。
（表に見えるところでは）
map関数はシーケンス（データ列）をインプットに、各要素に処理を施したあとのシーケンスを返す。 しかし、これが単純なデータ列だけではなく、木構造にも応用できるとは思ってもみなかった。
それも、概念を整理するとシンプルで、シーケンスの構成要素が、たまたま別のシーケンスだった場合は そこを再帰的にたどっていけばよいだけ、だ。
同じデータ構造に対して、別の視点を持つことで、プログラミングの仕方が変わってくる。 SICPを読んでいると、こういうパラダイムの転換が頻繁に出てくるから実に面白い。
recordを使ってデータ構造をつくる
SICPまじ楽しいな。この本は、一読して内容を理解するだけじゃなくて、手を動かしてコードを写経したり練習問題をやると、純粋にプログラミングの楽しさを味わえる。本質的な部分（パラダイム）を濃密に扱っているので、数学と一緒で、手を動かして思考を追う過程に悦びがある。
まだ２章の途中だが、データ構造をLISPの流儀で定義するところが、考え方としてはすごくシンプルでエレガント。 しかし、何度味わっても美味しい。（いや、逆にシンプルゆえに美味しいのかもしれない）
手続き型言語やオブジェクト指向言語みたいにstructやclassを使ってデータ構造そのものを定義するのではなく、関数というインタフェースだけを使って、データの抽象概念を見せる。
さて、練習問題2.2では、線分を作ってその線分の中点を求めるために、点、線分を扱う関数を定義する。 使う側からすると以下のようになる。
(def seg (make-segment (make-point 10 20) (make-point 20 30))) (x (midpoint-segment seg)) ; -> 15 (y (midpoint-segment seg)) ; -> 25
OOPっぽく書けば
seg = Segment.new( Point.new(10,20), Point.new(20, 30)) seg.midpoint-segment.x # -> 15 seg.midpoint-segment.y # -> 25
(x-point (midpoint-segment seg))とseg.midpoint-segment.x-pointは順番が逆になっただけで、記述量に違いはない。
しかし、考え方が真逆なのが、やはり面白い。
関数の定義は、SICP流に従ってClojureで書くと下記のとおりになる。
(defn make-point [x y] (list x y)) (defn x [p] (first p)) (defn y [p] (last p)) (defn make-segment [start end] [start end]) (defn start [s] (first s)) (defn end [s] (last s)) (defn midpoint-segment [s] (let [ss (start s) es (end s)] (make-point (/ (+ (x ss) (x es)) 2) (/ (+ (y ss) (y es)) 2))))
これをClojureのrecordと使うと、ぐっと簡単に書ける。
midpoint-segmentはデストラクテャリングを使って記述を短くしている。
(defrecord Point [x y]) (defrecord Segment [start end]) (defn midpoint-segment [{:keys [start end]}] (->Point (/ (+ (:x start) (:x end)) 2) (/ (+ (:y start) (:y end)) 2)))
recordは内部的にはJavaのclassそのもので、データ構造を定義できて、なおかつClojureで定義したものをJavaの世界からでも参照できる。 まさにJavaとのinteroperabilityのための機能だ。
recordのいいところはmapと同等の機能を持つ点で、要素を取り出すための関数定義x、y、start、endが不要で、
defrecord時の引数に渡す要素名がそのままkeyとして使える。
さらに、生成関数を自前で定義する必要ないという点もある。
(->Segment)と書けばSegment.new()に相当する。(Segment.)と書いても動作する。
このJavaからのいいとこ取り、しかもwell-designedなところが、Clojureのセクシーなところだ。
最初の使用例を書き直すと下記になる。
(def seg (->Segment (->Point 10 20) (->Point 20 30))) (:x (midpoint-segment seg)) ;-> 15 (:y (midpoint-segment seg)) ;-> 25
最後の２行は、スレッディングマクロを使えば、さらにOOPっぽくかける。
(-> seg midpoint-segment :x) ;-> 15 (-> seg midpoint-segment :y) ;-> 25
以上。
SICP第一章読了
SICP第１章を読了した。演習問題もコンプリート！ 言語はSchemeではなくClojureを使ったのでClojureのいい練習にもなった。
振り返ると、プログラミングの教材として、構成が実によく考えられていて感動すら覚える。 一級品の少年漫画やRPGなみのストーリー展開を思わせる（笑）。 序盤の伏線がクライマックスで花開く、みたいな。
しょっぱなの入り口では、平方根を求める関数を、ニュートン法の考え方を使って、 丁寧に要素に分解して関数を階層化してプログラムを作っていく。 関数型プログラミングのまさにお手本を示している。
クライマックスにおいては、まったく同じ問題を、高階関数を使うことでより高いレベルで解いている。 プログラミングの道具としては「関数を引数に渡す」「関数を返り値にする」機能を使うことで、 もののみごとに平方根を求める処理が、汎用的な抽象概念の組み合わせによって表現できることを示す。
平方根をもとめることとは何か？
それは、y = x/yの平均減衰(average damp)を使って不動点(fixed point)を求めるに等しい。
(defn sqrt [x] (fixed-point (average-damp (fn [y] (/ x y))) 1.0))
まさにコードが体を表している。
上記はSchemeではなくClojureで書いたコードだが、 この本がプログラミング言語にLISPを選んだ理由がよくわかる。 問題を解くための手続きを、これ以上直接的かつ簡潔に表現できる言語は他には無いと思う。 余計なものはいっさいない。表現したいことをダイレクトに表現できる。
読んでいると、この本のプログラムで何気なくやっていることが、他の言語だと難しいだろうなと感じることも多々ある。 Schemeは実にシンプルで強力だな！とほれぼれする。
いまのところClojure以外はやる気はしないのだが、Schemeがそれに匹敵するものだとよく分かった。 結局、動作環境（プラットホーム）が一番重要なんだな。ClojureはJVMを選んで大正解だと思う。
しかし、SICPとClojureで十分幸せなプログラミングの時間を過ごせるな。SICPで数学自体の面白さも味わえるし。 まあ、この本はむしろ数学のバックボーンがしっかりしている学生にプログラミングを教えるための教材ではあるが。
Clojureでパスカルの三角形
SICP遅々と読む。練習問題にパスカルの三角形の要素を計算せよ（再帰を使って）、というのがある。 フィボナッチ数列の次くらいに手軽な題材でいろいろ試せて遊べるなと。
Clojureらしい解き方は、やっぱ遅延シーケンスを作るやり方だろうなと。 出力形式は問われていないから、任意の行数までの計算結果を返すとしよう。
=> (take 5 (pascal-triangle)) ([1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1]) => (nth (pascal-triangle) 5) [1 5 10 10 5 1]
コード：
(defn next-row [row] (letfn [(add-1-both-ends [coll] (concat [1] coll [1]))] (->> (partition 2 1 row) (map (fn [[a b]] (+ a b))) add-1-both-ends vec))) (defn pascal-triangle ([] (pascal-triangle [1])) ([col] (lazy-seq (cons col (pascal-triangle (next-row col))))))
next-rowはパスカル三角形の特定の行の数列が与えられたとして、その次の行の数列を返す。
=> (next-row [1 1]) [1 2 1] => (next-row [1 2 1]) [1 3 3 1]
この関数の実装方法としては、以前「プログラミングClojure」で衝撃的だったフィボナッチ数列の解き方に習って、 いったん与えられた数列の形を扱いやすい形に変えている。
[1 3 3 1] → [[1 3] [3 3] [3 1]]
これで再帰を使わなくてもmapを使って要素の計算ができる。 partitionという関数を使えば、上記は簡単に出来る。
=> (partition 2 1 [1 3 3 1]) ((1 3) (3 3) (3 1))
仮にcore関数のpartitionを使わずに、似たことをやるとしたら以下の関数を作れば良い。
(defn my-partition [[a b :as col]] (when (and a b) (cons [a b] (my-partition (rest col)))))
デストラクチャリングを使って要素を取り出して再帰するClojureのエレガントさを味わえるので、これはこれで楽しい。
pascal-triangle関数も、遅延シーケンスを使わずに再帰を使って、しかもStack Overflowを起こさない末尾最適可能なように作るとしたら、下記になるかなと。（中で使っているnext-rowは変わらない）
(defn pascal-triangle ([n] (pascal-triangle n [1] [])) ([n a b] (if (zero? n) b (recur (dec n) (next-row a) (conj b a)))))
遅延シーケンスほど使い回しは効かなくなるが、
=> (pascal-triangle 5) ([1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1])
という感じになる。
この小さい題材の実装でもClojureの以下の機能が便利すぎて、
- シーケンスを扱う高階関数(map, partition)
- 引数個数ごとに関数の処理を分けて定義できる（multi-arity）
- デストラクチャリングによる引数の分解
- スレッディングマクロ(->>)
これらが無い世界で暮らすのが辛い（笑）。
続Clojureのdestructuringメモ
前回「 Clojureのdestructuringメモ - Programmer's Note 」の続き。
マップのdestructuring
文字列をキーに使った場合を試す
(def mab {"a" 1 "b" 2}) (let [{:strs [a b]} mab] (println b "," a)) ; 結果 => 2,1
Goood!!
下記非短縮形もOK。
(def mab {"a" 1 "b" 2}) (let [{x "a" y "b"} mab] (println x y))
シンボルがキーの場合
(def mcd {'c 1 'd 2}) (let [{:syms [c d]} mcd] (println c "," d)) ; 結果 => 1,2
Goooooood!!
下記非短縮形もOK。
(def mcd {'c 1 'd 2}) (let [{x 'c y 'd} mcd] (println y "," x))
さて、マップの入れ子構造も試してみる
(def dat {:name "boo" :body {:weight 60 :height 160 } :money 100}) (let [{{h :height} :body} dat] (println h)) ; 結果 => 160
ベクターとマップの組み合わせ！
マップの中にベクターがある場合。
(def dat {:name "boo" :body [60 160] :money 100}) (let [{[_ height] :body} dat] (println height)) ; 結果 => 160
ベクターの中にマップがある場合。
(def dat ["boo" {:weight 60 :height 160} 100]) (let [[_ {h :weight} _] dat] (println h)) ; 結果 => 60
なんつービューティフルな言語なんだ！
関数に引数をマップで与える場合の省略形
たとえば関数にパラメータでマップを渡したい場合、
(boo "foo" {:weight 50 :height 120})
にするが、これを
(boo "foo" :weight 50 :height 120)
のように書ける！
前者の関数定義は
(defn boo [name opts] (let [{w :weight h :height} opts] (println name ": (" w "," h ")")))
で、後者は
(defn boo [name & opts] (let [{w :weight h :height} opts] (println name ": (" w "," h ")")))
違いは引数の定義に&を使っているだけ！
defnは実はマクロで、& optsと定義したときは、残りの引数をまとめてシーケンスに入れてくれる。
さらにシーケンスはベクターにもマップにも展開できる。
シーケンスという一個上位の抽象概念をかますと、物事をシンプルに扱える。美しい。
destructuringは関数の引数定義[]でも同じように使えるから、後者はこのようにも書ける。
(defn boo [name & {w :weight h :height}] (println name ": (" w "," h ")"))
いやあClojure最高です。
