read-ctfp
この記事は「プログラマーのための圏論」の読書メモです。
序文
合成は圏論の最も根本であり、圏そのものの定義の一部だ。そして私は、合成こそプログラミングの本質であると強く主張したい。我々は、偉大なエンジニアがサブルーチンのアイデアを思いつく遥か前から、ずっとものを合成してきた。かつて構造化プログラミングはプログラミングに革命をもたらした。コードのブロックを合成可能にしたからだ。続いてオブジェクト指向プログラミングが登場した。これはオブジェクトを合成することこそすべてだ。関数プログラミングは、関数や代数的データ構造を合成するだけでなく、並行性をも合成可能にする。これは他のプログラミングパラダイムでは事実上不可能だ。
なのであれば関数型プログラミングを贔屓して述べるのではなくて、さまざまなプログラミングパラダイムを圏論を通して議論できて見通しよくスッキリと理解できる嬉しい。オブジェクトを合成するとはどういうことだろう。
大きな変化を引き起こしている力のひとつがマルチコア革命だ。広く普及しているプログラミングパラダイムであるオブジェクト指向プログラミングは、並行・並列処理の領域では何のメリットもなく、その代わりに危険でバグを生じやすい設計を奨励している。オブジェクト指向の基本的前提であるデータ隠蔽は、データの共有や改変と組み合わされると、データ競合のレシピになる。ミューテックス3 とそれが保護するデータを組み合わせるというアイデアは素晴らしい。しかし、残念ながらロックは合成できないし、ロックを隠すことでデッドロックが発生しやすくなり、デバッグが難しくなる。
何のメリットもないことはないと思うし、ロックが合成できないとはどういうことなのかよくわからない。どういう性質をロックは持てない、ということなのだろう。
1 圏: 合成の本質
1.2 合成の性質
恒等射は対象ごとに一意だろうか。多分一意なのだろう。圏とその対象を任意に取って、その恒等射二つを i, j とする。そうすると以下のようにそれらは等しいことがわかる。なので一意。
i = i . j (jはidentityなので)
= j (iはidentityなの)
二つの異なるidentityが存在することはありえない。
1.3 合成はプログラミングの本質
オブジェクト指向プログラミングでは、表面はオブジェクトのクラス宣言、あるいはその抽象インターフェイスだ。関数プログラミングでは、それは関数の宣言だ10。（ここでは少し単純化しているが、要点はこれだ。）
プログラミング言語処理系の立場からしたらそれしか観測できないかもしれないが、プログラマはもっとリッチなクラスや関数の契約を表面とするのではないだろうか。
オブジェクト指向プログラミングでは、理想化されたオブジェクトを見られるのは抽象インターフェイス（純粋な表面なので体積なし）を通してだけで、メソッドが射の役割を果たす。他のオブジェクトと合成する方法を理解するためにオブジェクトの実装を掘り下げなければならなくなった瞬間、このプログラミングパラダイムの利点は失われてしまう。
射の役割とは何だろう。ふわふわしている。圏論との関連がわからない。圏論の議論をしているのに関数とか集合の性質の話をしだしたら情報隠蔽に失敗している、みたいな話ならわかる。
1.4 課題
1. 恒等関数を、好きな言語で（それがたまたまHaskellなら2番目に好きな言語で）できるだけうまく実装せよ。
func id[T any](x T) T {
return x
}
2. 合成関数を好きな言語で実装せよ。このメソッドは2つの関数を引数として受け取り、その合成である関数を返す。
func compose[A, B, C any](f func(B) C, g func(A) B) func(A) C {
return func(x A) C {
return f(g(x))
}
}
3. 合成関数が恒等関数と整合しているかテストするプログラムを作成せよ。
関数の等しさの比較を定めたくなるけど、良い案が浮かばない。全ての入力に対して同じ結果を返す関数が同じである、と思う？名前が異なるけど全く同じ実装を持つ関数は同じと見做すということになる。また、中で異なる文字列をprintする関数も同じ見做すことになる。そういう同値関係で割って得られる関数の同値類たちの間での等しさならなんとかなるかもしれない。
関数に限らずGoの値の等しさは全てのオブジェクトに対して定義されているわけではなくて、comparable インターフェースを満たす必要がある。そういう型を入力と出力の型として持つ場合には以下のようなテストをかける。
// いろんなAの値を出力する
func generateAs() []A {}
func generateA2B() []func(A) B {}
for f in generateA2B() {
for a in generateAs() {
b1 := f(a)
b2 := compose(id, f)(a)
b3 := compose(f, id)(a)
assertSame(b1, b2)
assertSame(b1, b3)
}
}
}
4. ワールドワイドウェブは、何らかの意味で圏だろうか？ リンクは射だろうか？
Webページ全体を対象として、そのページからリロードかリンククリックを任意回行って到達する操作を射だと思うと圏なのではないだろうか。全てのページについて、リロードしたらそのページに到達できるはず（ページは削除されないと仮定する）。合成可能性は定義の仕方がずるいので大丈夫。一回だけだとだめ。
合成可能性によって、射というのは序盤の対象に権威を与えるようなものになっている。繋がりの富が集まりやすい傾向にある。
5. Facebookは人を対象とし友達関係を射とする圏だろうか？
友達関係というのはフォローしている状態のことだろうか。そうであれば違う。僕が友達をフォローしていて、その友達がその推しのアイドルをフォローしていたとしても僕はそのアイドルをフォローするとは限らない。
そうではなくて、友達関係というのは友達の友達は友達、という理屈のもとでフォロファーを友達と思って生成される関係ならばどうだろう。これでも違う可能性がある。僕が誰にもフォローされていない場合、僕に対する恒等射が存在しないので。自分以外の全ての人をフォローする人がいて、そして僕が（誰でもいいけど）その人をフォローすれば友達関係を射として圏である、と思えそうだ。この場合、自分以外の全ての人をフォローする人はみんなの友達だし、その人をフォローする僕もみんなが友達である。
6. 有向グラフが圏になるのはどのような場合だろうか？
ノードを対象、エッジを射と思うのが自然だろうか。どんな合成を考えるべきだろう。a->b->cというような風のエッジがあったら、a->cを導き出すようなエッジ二つをとる関数が自然かな。
以下の二つの性質を満たすものは圏だと思えるだろう。
- 全てのノードに自己ループが存在する
- エッジの合成で得られる射もそのグラフのエッジである
グラフを多重グラフと思うとどうなるだろう。恒等射が定まるために自己ループは一つだけであって欲しい。
こうじゃない合成も考えられそうだ。
2 型と関数
2.2
Haskellでは、稀な場合を除いて、型注釈は純粋にオプションだ。プログラマーはどのみち型注釈を使う傾向がある。なぜなら、コードの意味について多くを伝えられ、コンパイルエラーを理解しやすくできるからだ。Haskellでは、型を設計することからプロジェクトを始めるのが一般的な慣習だ。後々、型注釈は実装を駆動し、コンパイラーによって強制されるコメントになる。
どんなソフトウェアであれ、データモデリングは中心に据えて設計することが多いのではないだろうか。Haskellではそれを型として表現することに腐心するイメージがある。
データモデルの授受の期待（つまり契約）を表現して検査するために型システムは便利だと思う。
2.5, 2.6
楽しい議論にならなさそうなのでこれ以上言及しません。
2.7
- サボります
- いかない。まともな乱数ジェネレータは呼び出しごとに返す値が異なるが、これは同じ結果を返すので
- いく。シード値を与えるような乱数ジェネレータはシード値に対して同じ乱数列を生成するようになっていて、指定された仕様は常にその乱数列の第一要素を返す。なのでメモ化してもしなくて返す値は同じである。つまりうまくいく
- 1と3は文句なしだろう。4は繰り返の呼び出しをプロセスごとに分けたらうまくいきそう。2は標準入力の値に依存する。それを入力と思うのは解釈を歪めすぎだろう。なのでうまく行かない
- Boolの値はTrue, False, ボトムの三つだった。なので27種類ある、というのは本当だろうか。ボトムをボトムであると認識することはできないかと思うので、ボトムを受け取ってボトム以外を返す関数は定数関数である必要がある。ボトムを受け取って、ボトムを返す関数はまあなんでもokか。
以下の三つのパターンに分けたとき、最後の二つのパターンは定数関数である、ということ。
map f (True, False, bottom) = (_, _, bottom)
map g (True, False, bottom) = (_, _. True)
map h (True, False, bottom) = (_, _. False)
g = \_. True
h = \_. False
fのタイプは二つの穴をBool型の三つの値から適当に取って埋められる組み合わせ全部がありうる。なので 3*3 = 9種類ある。なので合計11個の Bool->Bool の関数が存在する。