Javaプログラマーのための圏論(5.積と余積)
積と余積
$$
$$
古代ギリシャの劇作家エウリピデスは言った。「人はその人が付き合っている人に似ている(類は友を呼ぶ)」我々は関係によって定義されている。そのことがどこよりも明らかなのは圏論である。ある圏からある特別な対象を選択したいなら、他の対象(及びそれ自体)との関係性のパターンを表すだけでよい。このような関係性は射で定義される。
圏論では普遍的構成と呼ばれる共通の構成があり、対象とそれらの関連性により定義される。これを行う一つの方法はあるパターン、即ち対象と射から構成されるある特定の形を選び取り、その圏のすべての発生を探し求める方法である。それが十分に共通なパターンで、その圏が大きいならば、非常にたくさんの適合する候補を得る公算が高い。これらの候補の間である種のランキングを構築し、何が最適なものを考えられるか選びとるのがコツである。
この過程はウェブ検索する方法を連想させる。問い合わせはこのパターンに似ている。かなり一般的な問い合わせは大きな再現率、たくさんの適合する候補を与えるだろう。あるものは関連性があるかもしれないし、別のものは関連性がないかもしれない。関連性のない候補を取り除くため、問い合わせを見直す。それによって精度が増す。最終的に検索エンジンはその候補をランク付けし、うまくいけば、最も関心がある一つの結果がリストの最上位にくるだろう。
始対象
最も単純な形は単一の対象である。ある圏を与えると、明らかに対象が存在するのと同じ数だけこの形のインスタンスが存在する。そこから選びとるには手間がかかる。ある種のランク付けを構築して、このヒエラルキーの最上位である対象を見つけようとする必要がある。我々が自由に使えるのは使えるのは射だけである。射を矢印として考えると、圏のある終端から別の終端への矢印のすべてのネットフローが存在することが可能である。順序圏、例えば半順序圏ではこれは成り立つ。対象a
から対象b
への矢印(射)が存在すれば、a
がb
「より始まりに近い」とすることで対象の優先順位の概念を一般化出来る。すべての自身以外の対象への矢印を持つような対象を始対象と定義する。明らかにこのような対象が存在する保証はない。より大きな問題として、余りにたくさんのこのような対象が存在するかもしれない。適合率はよいが、精度は失われる。その答えは順序圏からヒントを得ることが出来る。即ち、任意の2つの対象の間には高々1つの矢印しかない。別の対象より小さい、または等しいと言う一方向だけが存在する。そこで次のような始対象の定義を導く。
$$
{\bf 始対象}はその圏の中の任意の対象へ向かう1つ、かつ唯一の射を持つ
$$
けれども(もし存在したとしても)始対象の一意性は保証されていない。しかし、一意性については次の最も良いことが保証されている、即ち同型の違いを除いて一意であると言うことである。同型は圏論では非常に重要であり、まもなく少し触れる。さしあたり、同型の違いを除いて一意であることが始対象の定義で対象を特定することが正当化される。
ここで例を挙げる。半順序集合(よくposetと呼ばれる)での始対象は最小の要素である。始対象を持たない半順序集合も存在する。例えば、以下の関係を射とする、全ての整数、正数と負数の集合がある。
集合と関数の圏では、始対象は空集合である。
終対象
単一対象パターンを続けよう。今度は対象のランク付けの方法を変更する。もし対象b
から対象a
への射(向きが逆)が存在すれば、a
がb
「より終わりに近い」ととする。圏の自身以外の対象より終わりに近い対象を探してみる。再び一意性を主張する。
$$
{\bf 終対象}はその圏の中の任意の対象から向かってくる1つ、かつ唯一の射を持つ。
$$
さらに再び、終対象は同型の違いを除いて一意である。これもまもなく触れる。最初に例を見ておこう。半順序集合では、終対象は、もし存在すれば、最大の対象である。集合の圏では、終対象はシングルトンである。既にシングルトンについては触れた。Javaではvoidがそれに対応する。それは唯一つの値を持つ型である。Javaでは暗黙的にである。任意の型から単位型への唯一つの純粋関数を構築出来る。
<A> void unit(A x) { return; }
全ての終対象の条件は満たされている。
この例で一意性は重要である。なぜなら、任意の集合から向かってくる射を持つ他の集合(実際には、空集合を除く全ての集合)が存在する。例えば、任意の型に対して定義されたブール値関数(述語)が存在する。
<A> Boolean yes(A x) { return true; }
しかし、Booleanは終対象ではない。少なくとももう一つの任意の集合から向かってくる射が存在する。
<A> Boolean no(A x) { return false; }
一意性を主張することで終対象の定義を唯一つの型へ絞り込むための正しい精度を得ることができる。
双対性
始対象と終対象を定義の対称性について気付かざるを得ない。二つの違いは射の向きだけである。任意の圏$C$に対してすべての矢印が逆向きにすることだけで反対圏$C^{op}$ を定義することができる。反対圏は同時に合成を再定義する限り、自動的に圏の要求をすべて満たす。もし元の圏で射$f:A \rightarrow B$と$g:B \rightarrow C$を合成して$h=g \circ f$で与えられる$h:A \rightarrow C$があった場合、反対向きの射$f^{op}:B \rightarrow A$と$g^{op}:C \rightarrow B$を合成すると$h^{op}=f^{op} \circ g^{op}$ で与えられる $h^{op}:C \rightarrow A$を得られるだろう。
双対性は圏の非常に重要な性質である。それは圏論を扱う数学者の生産性を二倍にする。すべての構成に対して、反対が存在する。証明された定理に対して、もう一つ無料でついてくる。反対圏での構成は接頭辞「余(co)」を付けることが多い。例えば、積(product)と余積(coproduct)、モナド(monad)と余モナド(comonad)、錘(cone)と余錘(cocone)、極限(limit)と余極限(colimit)などである。余余モナドは存在しない。二回矢印を逆向きにしても元の状態に戻るからである。
したがって、終対象は反対圏の始対象である。
同型
プログラマーは皆等価を定義することが自明ではないことをよく知っている。二つのオブジェクトが等しいとはどういう意味だろうか?メモリ内で同じ場所を占めているなければならないのだろうか(ポインタの等値性)?それともそれらのコンポーネントの値が等しいことで十分なのであろうか?2つの複素数に対して、一方は実部と虚部で表され、他方は動径と偏角として表されている場合に、これらの複素数は等しいのだろうか?数学者が等値性の意味を見つけ出したと思うかもれないが、そうではない。数学者も多様な競合する等価の定義の同じ問題を持っている。命題的等値性(propositional equality)、内包的等値性(intensional equality)、外延的等値性(extensional equality)、及びホモトピー型理論での道(path)としての等値性が存在する。そして、より弱い概念である同型、さらにより弱い概念である同値性も存在する。
直観的には同型な対象は同じように見える、即ち同じ形を持つ。それが意味するのは、一つの対象の各部が別の対象の部分に1対1の写像で対応することである。分かる範囲でその二つの対象はお互いの完全なコピーである。数学的に意味するのは、対象a
から対象b
への写像が存在し、且つ対象b
から対象a
に戻る写像が存在し、これらの写像はお互い逆写像であるということである。圏論では写像を射に置き換える。同型は可逆な射であり、もしくは射のペアで一方が多少の逆射である。
合成と恒等射で逆射を理解する。射$g$が射$f$の逆射であるとは、これらの射の合成が恒等射であることである。二つの射の合成は2方向存在するので、実際には二つの等式が存在する。
$$
f \circ g = id
$$
$$
g \circ f = id
$$
始対象(終対象)は同型の違いを除いて一意であると述べたが、任意の二つの始対象(終対象)は同型と言う意味であった。実際に簡単なので見ていこう。二つの始対象$i_1$と$i_2$があると仮定しよう。$i_1$は始対象なので、$i_1$から$i_2$への一意な射$f$が存在する。同様に、$i_2$は始対象なので、$i_2$から$i_1$への一意な射$g$が存在する。これらの射の合成はどうなるだろうか?
合成$g \circ f$は$i_1$から$i_1$への射でなければならない。しかし、$i_1$は始対象であり、そのため$i_1$から$i_1$への射は唯一つだけ存在する。圏を扱っているので、$i_1$から$i_1$へ恒等射が存在することが分かっており、唯一つであるため、これはその合成と一致する。従って、$g \circ f$は恒等射と等しい。同様に、$i_2$から$i_2$に戻っていく射は唯一つであるため、$f \circ g$も恒等射に等しい。以上によって、$f$と$g$はお互いに逆射であることが証明された。従って、任意の二つの始対象は同型である。
この証明では始対象からそれ自身はの射の一意性を使った。それなしでは「同型の違いを除いて」の部分を証明することはできない。しかし、なぜ$f$と$g$の一意性が必要なのであろうか?始対象は同型の違いを除いて一意であるだけでなく、一意な同型射の違いを除いて一意であるからである。原則としては二つの対象の間に一つ以上の射が存在するが、ここでは当てはまらない。この「一意な同型射の違いを除いて一意であること」はすべての普遍的構成の重要な性質である。
積
次の普遍的構成は積である。二つの集合のデカルト積がペアの集合であることは知られている。しかし、構成する集合の積集合をつながるパターンとは何だろうか?もしそれを見つけ出したとして、他の圏へそれを一般化することはできるのであろうか?
二つの関数、即ち積から各成分への射影が存在することは言える。これらの二つの関数$fst$と$snd$をそれぞれ次のように定義する。
$$
fst:(A, B) \rightarrow A
$$
$$
fst(x, y) = x
$$
$$
snd:(A, B) \rightarrow B
$$
$$
snd(x, y) = y
$$
例えば、Javaで以下のように表すことができる。
class Pair<A,B> { final A first; final B second; Pair(A first, B second) { this.first = first; this.second = second; } } // (A,B)をPair<A,B>と同一視する Function<Pair<A,B>, A> fst = p -> p.first; Function<Pair<A,B>, B> snd = p -> p.second;
このような一見すると非常に限定された知識をもとにして、二つの集合$A$と$B$の積の成分を導くような集合の圏の対象と射のパターンを定義してみよう。このパターンは対象$c$と二つの射$p$及び$q$で構成され、それぞれ次のように対象$C$から$A$と$B$へ移す。
$$
p:C \rightarrow A
$$
$$
q:C \rightarrow B
$$
このパターンを満たす$C$はすべて積の候補と考えることができる。そのようなものが沢山存在するかもしれない。
例えば、構成として、Integer
とBoolean
を取り上げて、これらの積候補をサンプリングしてみよう。
一つ目の候補を挙げる。Integer
である。Integer
をInteger
とBoolean
の積の候補として考えることができるのであろうか?実際にできる。次のような射影が存在する。
Function<Integer,Integer> p = x -> x;
Function<Integer,Boolean> q = x -> true;
かなり洗練さが足りないが、基準は満たしている。
別の候補を挙げる。$(Integer,Integer,Boolean)$ である。三つの要素のタプル、トリプルである。これを正当な候補するような二つの射影は次のようなものである。クラスTriple
を定義する。
class Triple<A,B,C> { final A first; final B second; final C third; Triple(A first, B second, C third){ this.first = first; this.second = second; this.third = third; } } // (Integer,Integer,Boolean)をTriple<Integer,Integer,Boolean>と同一視する Function<Triple<Integer,Integer,Boolean>,Integer> p = x -> x.first; Function<Triple<Integer,Integer,Boolean>,Boolean> q = x -> x.third;
最初の候補は小さ過ぎる。積のInteger
の次元しか網羅できていないためである。次の候補は大き過ぎる。Integer
の次元が不正に重複しているためである。
しかし、普遍的な構成の別の部分である、ランク付けを探究していない。ここでのパターンの二つの例を比較できるようにしたい。一つの候補、対象$C$と二つの射影$p$と$q$を別の候補、対象$C'$ と二つの射影$p'$ と$q'$ を比較したい。$C'$ から$C$への射が存在すれば$C$は$C'$ と比べて「より良い」としたい。しかし、それでは弱すぎる。$C$の射影もまた$C'$ の射影と比べて「より良い」または「より普遍的である」としたい。それが意味することは、射影$p'$ と$q'$ が$ m $を使って、$p$と$q$から再構成できることである。
$$
p' = p \circ m
$$
$$
q' = q \circ m
$$
これらの等式を別の見方をすると、$ m $が$p'$ と$q'$ を分解している。これらの等式を自然数で、合成を乗算と見なすと、$ m $は$p'$ と$q'$ の公約数である。
直観を働かせるため、二つの標準的な射影、$fst$と$snd$を持つペア $(Integer, Boolean)$ が、既に挙げた二つの候補より真に「より良い」ことを示そう。
$(Integer,Boolean)$ をPair<Integer,Boolean>
と見なして、最初の候補に対する写像$ m $は次のようになる。
Function<Integer,Pair<Integer,Boolean>> m = x -> new Pair<>(x, true);
実際、二つの射影$p$と$q$は次のように再構成できる。
Function<Integer,Integer> p = x -> fst.apply(m.apply(x)); Function<Integer,Boolean> q = x -> snd.apply(m.apply(x));
2番目の例に対する$ m $は同様に一意に次のように定められる。
Function<Triple<Integer,Integer,Boolean>,Pair<Integer,Boolean>> m = x -> new Pair<>(x.first,x.third);
$(Integer,Boolean)$ が二つの候補のどちらとも比べてもより良いこと示すことができた。なぜ反対は真ではないことを見ていこう。$p$と$q$から$fst$と$snd$を再構成するような$m'$ を見つけてみよう。
$$
fst = p \circ m'
$$
$$
snd = q \circ m'
$$
最初の例では、$q$は常にtrue
を返し、ペアの二つ目の成分はfalse
を取りうる。$q$から$snd$を再構成することはできない。
2番目の例は異なっている。$p$または$q$を実行した後十分な情報を得られる。しかし、$fst$と$snd$を分解する1つ以上の方法が存在する。$p$と$q$はトリプルの2つ目の成分を無視しているので、そこに値を設定することができない。次のようなものが得られる。
Function<Pair<Integer,Boolean>,Triple<Integer,Integer,Boolean>> m' = x -> new Triple<>(x.first, x.first, x.second);
もしくは
Function<Pair<Integer,Boolean>,Triple<Integer,Integer,Boolean>> m' = x -> new Triple<>(x.first, 42, x.second);
などである。
すべてをまとめると、二つの射影$p$と$q$を持つ任意の型$C$を与えると、$C$からデカルト積 $(A, B)$ への一意で、デカルト積を分解するような$ m $が存在する。事実、それは$p$と$q$を結合してペアを作る。
$$
m:C \rightarrow (A, B)
$$
$$
m(x) = (p(x), q(x))
$$
こうすることでデカルト積 $(A, B)$ はベストマッチする。それはこの普遍的構成が集合の圏において働くことを意味する。それは任意の二つの集合の積を選び取っているのである。
今は集合については忘れ、同じ普遍的構成を使って任意の圏の二つの対象の積を定義しよう。このような積が常に存在するとは限らないが、存在するときは一意な同型の違いを除いてそれは一意である。
二つの対象$A$と$B$の${\bf 積}$は二つの射影を持つ対象$C$であり、二つの射影を持つ任意の他の対象$C^{'}$に対して、それらの射影を分解するような$C^{'}$から$C$への一意な射が存在する。
二つの候補から分解関数$ m $を生み出すような(高次な)関数はしばしば因子化(factorizer)と呼ばれる。ここでは、次のような関数である。
$$
factorizer:(C \rightarrow A) \rightarrow (C \rightarrow B) \rightarrow (C \rightarrow (A, B))
$$
$$
factorizer(p,q)(x) = (p(x), q(x))
$$
余積
圏論の各構成と同様に、積も双対を持ち、これを余積と呼ぶ。積の矢印を逆向きにすると、二つの単射、即ち$a$及び$b$から$c$への射$i$と$j$を持つような対象$c$と言う結果となる。
$$
i:A \rightarrow C
$$
$$
j:B \rightarrow C
$$
ランク付けもまた反転する。対象$C$が単射$i^{'}$ と単射$j^{'}$ を持つ対象$C^{'}$ と比べて「より良い」とは、次のように単射を分解する$C$から$C^{'}$ への射$ m $が存在することである。
$$
i^{'} = m \circ i
$$
$$
j^{'} = m \circ j
$$
「最も良い」このような対象、即ちそこから任意の他のパターンにつながるような一意な射を持つ対象であり、このような対象を余積と呼ぶ。もし余積が存在すれば、一意な同型の違いを除いて一意である。
二つの対象$A$と$B$の${\bf 余積}$は二つの単射を持つ対象$c$であり、二つの単射を持つ任意の他の対象$C^{'}$に対して、それらの単射を分解するような$C$から$C^{'}$への一意な射が存在する。
集合の圏では、余積は二つの集合の直和である。$A$と$B$の直和の要素は$A$の要素、または$B$の要素のいずれかである。二つの集合が重なっているならば、直和は共通部分の二つのコピーを含んでいる。直和の要素は元の集合を特徴付ける識別子でタグ付けされたものとして考えることができる。
Javaには共用体がないので、タグ付けされた共用体で直和を定義することはできないが、次のようにして、直和を定義することができる。
interface Contact { enum tag {isPhone, isEmail}; tag tag(); } class PhoneNum<A> implements Contact { final A phoneNum; PhoneNum(A phoneNum) { this.phoneNum = phoneNum; } @Override public tag tag() { return tag.isPhone; } } class EmailAddr<A> implements Contact { final A emailAddr; EmailAddr(A emailAddr) { this.emailAddr = emailAddr; } @Override public tag tag() { return tag.isEmail; } } Contact helpdesk = new PhoneNum<Integer>(22222222);
ここで、タグは列挙型として定義し、PhoneNum
とEmailAddr
がコンストラクタ(単射)を提供している。
次のようなEither
を導入することでより標準的な実装を定義することができる。
abstract class Either<A,B> { abstract Boolean isLeft(); abstract Boolean isRight(); static class Left<A,B> extends Either<A,B> { final A left; Left(A left) { this.left = left; } @Override Boolean isLeft() { return true; } @Override Boolean isRight() { return false; } } static class Right<A,B> extends Either<A,B> { final B right; Right(B right) { this.right = right; } @Override Boolean isLeft() { return false; } @Override Boolean isRight() { return true; } } }
これは二つの型引数A
とB
による総称型で、Left
が型A
の値を取り、Right
が型B
の値を取る。
積で因子化を定義したのと同様に、余積に対する因子化を定義できる。候補となる型$A$と二つの候補となる単射$i$と$j$を与えられたとき、(Either<A,B>
に対応する)$A \oplus B$に対する因子化は次のような関数で構成される。
$$
factorizer:(A \rightarrow C) \rightarrow (B \rightarrow C) \rightarrow A \oplus B \rightarrow C
$$
$$
factorizer(i,j)(a) = i(a)
$$
$$
factorizer(i,j)(b) = j(b)
$$
非対称
2種類の双対な定義を見てきた。終対象は始対象の定義から矢印の向きを逆にすることで得ることができる。同様に余積は積の定義から得ることができる。しかし集合の圏論では、始対象は終対象と著しく異なっており、余積は積と著しく異なっている。後で触れるように、積は乗算のよに振る舞い、終対象は1の役割を担う。一方で、余積は加算のように振る舞い、始対象は零の役割を担う。特に有限集合に対して、積のサイズは個々の集合のサイズの積になり、余積のサイズは個々の集合のサイズの合計になる。
次に集合の圏は矢印の反転の点で対称でないことを示す。
空集合は任意の集合への一意な射を持つ一方で、空集合に戻ってくる射は持たない。シングルトンは任意の集合から自身への一意な射を持つだけでなく、(空集合を除く)任意の集合への射も持つ。既に見たように、終対象から出ていく射は他の集合の要素を選び取ると言う非常に重要な役割を担っている(空集合は要素を持たない。よって選び取ることもない)。
積に対するシングルトン集合の関係は余積とは別である。かなり劣ったものであるが、シングルトン集合を使って、積のパターンに対する候補を考えてみよう。それは次のような二つの射影$p$と$q$、即ちシングルトンから各成分への関数を持つ。各々それぞれの集合から具体的な要素を選択する。積は普遍的であるので、ここでの候補、シングルトンから積への(一意な)射$ m $もまた存在する。この射は積集合から要素を選択する。即ち、それは具体的なペアを選択する。それはまた次のように二つの射影に分解する。
$$
p = fst \circ m
$$
$$
q = snd \circ m
$$
シングルトンの値()
、即ちシングルトン集合の唯一の要素に作用すると、次のような等式が成り立つ。
p() = fst(m()) q() = snd(m())
m()
は$ m $によって選び取られた積の要素なので、これらの等式によって示されているように、最初の集合から$p$によって選び取られた要素p()
は$ m $によって選び取られたペアの最初の成分と一致する。同様にq()
は2番目の成分に等しい。このことは、積の要素は成分集合からの要素のペアであると言う理解と完全に一致している。
余積ではこのような単純な解釈はない。シングルトン集合から要素を抜き出す試みで、余積に対する候補としてシングルトン集合を試してみることができる。しかし、その場合、シングルトン集合から出ていく二つの射影ではなく、シングルトン集合に向かう二つの単射を使うことになる。それらは始域については何の情報ももたらさない(事実それらは入力引数を無視する)。余積からシングルトンへの一意な射も得られない。集合の圏は始対象から見たのと終対象からみたのと比べるとかなり異なっていることが分かる。
次は集合の固有の性質ではなく、関数の性質、即ち ${\bf Set}$での射としての関数の性質である。一般的に関数は非対称である。では説明しよう。
関数は始域の各要素に対して定義されるはずである(プログラミングでは、そのような関数を全値関数と呼ぶ)。しかし、それは終域全体を網羅しているとは限らない。その極端な場合を見てきた。シングルトン集合からの関数である。それは終域の唯一つの要素だけを選択する関数である(実際には、空集合からの関数は本当に極端である)。始域のサイズが終域のサイズより小さい場合、このような関数を終域の中への始域の埋め込みとして考えることが多い。例えば、シングルトン集合からの関数は終域の唯一つの要素の埋め込みとして考えることができる。そのような関数を埋め込み関数と呼ぶが、数学者は反対側の名前を与えることをより好む。終域を隙間なく占める関数を 全射(surjective) または 上の(onto)と読んでいる。
非対称の他のケースとして、始域の多くの要素を終域の一つの要素へ写す関数がある。それはそれらの始域の要素を潰している。極端なケースは集合全体をシングルトンへ写す関数である。既に見たように多態関数unit
がそれに当たる。潰すことは合成によって混ぜ合わせられることでしかできない。二つの潰すような関数の合成は個々の関数以上にさらに潰していく。数学者は潰さない関数に対して、単射(injective) または 1対1(one-to-one) と呼んでいる。
もちろん埋め込むでも潰すでもない関数も存在する。それらは 全単射(bijection) と呼ばれ、正確に対称である。なぜなら、それらは可逆であるからである。集合の圏では、同型は全単射と同じである。
Javaプログラマーのための圏論(4.クライスリ圏)
クライスリ圏
これまで型と純粋関数を圏としてモデル化する方法を見てきた。圏論で副作用、また非純粋関数をモデル化する方法があることも触れた。次のような例:実行時のログまたはトレースをする関数を見てみよう。javaでは次のようにグローバルに状態を変更して実装するだろう。
String logger; Boolean negate(Boolean b) { logger += "Not so! "; return !b; }
参照透過性(同じ入力に対して同じ作用と同じ出力とを持つこと)が成り立たないので、この関数は純粋関数ではない。
現代では、グローバルな状態を変更するのをできるだけ避けようとする(並列の複雑さのため)。ライブラリではこのようなコードは決して使われない。
幸いにも、このような関数を純粋関数にすることができる。引数と戻り値で明示的にログを通過させればよい。文字列の引数を追加して、更新されたログを含む文字列とペアにして戻せばよい。
class Pair<A, B> { final A first; final B second; Pair(A first, B second) { this.first = first; this.second = second; } } Pair<Boolean, String> negate(Boolean b, String logger){ return new Pair<>(!b, logger + "Not so! "); }
この関数は純粋で、副作用を持たず、同じ引数で呼び出されれば毎回同じペアを返し、必要なら記憶することもできる。けれども、ログは累積していくものであることを考慮すると、ある呼び出しを引き起こすことができるようなすべての可能な履歴を記憶しなければならない。次のようにそれぞれ別々のエントリになる。
negate(true, "It was the best of times. "); negate(true, "It was the worst of times. ");
また、ライブラリでのインターフェースとしても余り良くない。呼び出される関数は戻り値の型のその文字列を無視したいが、引数としての文字列を通過させなければならず、便利ではない。
ログの追加するのをより軽減して同じことをする方法はないか?関心事を分離すること方法はないか?この単純な例では、関数の主な目的はあるブール値を別のブール値に変換することである。ログを残すのは副次的なことである。その関数で特定されるメッセージは決まっているが、ある連続するログの中にそのメッセージを追加する処理と別の関心事である。その関数が文字列を生成したいが、ログを生成することの負担は避けたい。妥協すると以下のようになる。
Pair<Boolean, String> negate(Boolean b) { return new Pair<>(!b, "Not so! "); }
ログは関数の呼び出しの間で集約されるだろうと言う発想である。
もう少し現実的な例を見てみよう。小文字を大文字に変換する関数と文字列を空白の区切り文字で文字列の配列に分割する関数で取り上げる。
String toUpper(String s) { return s.toUpperCase(); } String[] toWords(String s) { return s.split(" "); }
関数toUpperとtoWordsを変更することで、正規な戻り値の最上位にメッセージ文字列を上に載せるようにしたい。これらの関数の戻り値を「装飾する」。次のように総称型でWriterを定義すれば、最初の任意の型Aの値と二つ目の文字列型の値のペアをカプセル化する。
class Writer<A> extends Pair<A, String> { Writer(A v, String s) { super(v, s); } }
これを使って装飾する。
Writer<String> toUpper(String s) { String result = s.toUpperCase(); return new Writer(result, "toUpper "); } Writer<String[]> toWords(String s) { String[] result = s.split(" "); return new Writer(result, "toWords "); }
これらの二つの関数を合成して、別の装飾された関数、を大文字にして単語に分解する、そしてこれらの操作のログを生成する関数にしたい。それは次のようにするかもしれない。
Writer<String[]> process(Stirng s) { var p1 = toUpper(s); var p2 = toWords(p1.first); return new Writer(p2.first, p1.second + p2.second); }
我々が達成したいゴールは次のようなものである。ログの集約は個々の関数の関心事ではない。これらはそれぞれのメッセージを生成し、その後このメッセージはより大きなログに外部で連結される。
このようなスタイルのプログラム全体を想像して欲しい。繰り返しと間違いをおこしやすいコードの悪夢である。しかし我々はプログラマーである。繰り返しのコードを扱う方法を知っている。それを抽象化すればよい。けれども、これはありふれた抽象化ではない。関数の合成を抽象化するのである。合成は圏論の核心である。より多くのコードを書く前に、圏論の視点からその問題を解析してみよう。
Writer圏
追加機能を上に載せるために一連の関数の戻り値を装飾する発想はとても良い結果をうむことがわかる。そのような例をこれから提示していくつもりである。出発点は型と関数の正則圏である。対象としての型の話題を置いておき、装飾された関数で射を再定義する。
例えば、Integer
からBoolean
を得るisEven
と言う関数を装飾してみよう。この関数は装飾された関数で表される射に変化する。重要な点は、この射がInteger
とBoolean
の対象の間での矢印として依然として見なせることである。この装飾された関数が次のようにペアを返すとしてもである。
Pair<Boolean, String> isEven(Integer n){ return new Pair<>(n % 2 == 0, "isEven "); }
圏の法則により、この射はBoolean
の対象から任意の対象を得る別の射と合成出来るはずである。特に、次のような先に述べたnegate
で合成できるはずである。
Pair<Boolean, String> negate(Boolean b){ return new Pair<>(!b, "Not so! "); }
明らかにこれらの射は通常の関数と同じように合成することは出来ない。入力と出力が一致しないからである。これらの合成は次のようなものになるべきである。
Pair<Boolean, String> isOdd(Integer n) { Pair<Boolean, String> p1 = isEven(n); Pair<Boolean, String> p2 = negate(p1.first); return new Pair<>(p2.first, p1.second + p2.second); }
ここで行った圏論で2つの射の合成の手順は次のようなもので構成されている。
1. 最初の射に対応する装飾された関数を実行する。
2. 結果のペアの最初の要素を取り出して、2番目の射に対応する装飾された関数に渡す。
3. 最初の結果の2番目の要素(文字列)と2番目の結果の2番目の要素(文字列)を連結する。
4. 最後の結果の最初の要素と連結した文字列を一緒にして新たなペアを作って戻す。
Javaでこの合成を抽象化したいなら、ここでの圏の3つの対象に対応する3つの型による総称型を使う必要がある。ここで触れた規則に従う合成できる2つの装飾された関数を引数とし、3番目の関数を戻すような関数である。
<A,B,C> Function<A, Writer<C>> compose(Function<A, Writer<B>> m1, Function<B, Writer<C>> m2) { return x -> { var p1 = m1.apply(x); var p2 = m2.apply(p1.first); return new Writer<C>(p2.first, p1.second + p2.second); }; }
ここで以前に触れた例に戻り、toUpperとtoWordsの合成をこの新しいテンプレートを使って実装すると、次のようになる。
Writer<String[]> process(String s) {
return compose<String, String, String[]>>(toUpper, toWords)(s);
}
合成のテンプレートに型を渡すための無駄が多い。一般化されたラムダ関数を使うと総称型の指定を削減できる。
const var compose = (m1, m2) -> { return x -> { var p1 = m1.apply(x); var p2 = m2.apply(p1.first); return new Writer<C>(p2.first, p1.second + p2.second); } }
この新しい定義では、processの実装はもっとシンプルになる。
Writer<String[]> process(String s){
return compose(toUpper, toWords)(s);
}
まだ終わっていない。新たな圏で合成を定義したが、恒等射はどうなる?正規な恒等射は存在しない。型A
から型A
へ戻す射で、次のような装飾された関数である。
Writer<A> identity(A);
合成の観点で単位元のように振る舞わなければならない。先に定義した合成を見ると、恒等射は引数を変更しないでそのまま戻し、ログには空の文字列を与えなければならない。
<A> Writer<A> identity(A x){ return new Writer(x, ""); }
ここで定義した圏が本当に正当な圏であることが納得できるだろう。特に、合成の結合律を満たすことは自明である。各ペアの1番目の要素では正規の関数の合成であり、それは結合律が成り立つ。2番目の要素は連結であり、連結もまた結合律が成り立つ。
文字列に限定せず、任意のモノイドに対して容易にこのような一般化が出来ることに気づいたかもしれない。compose
の中はmappend
、identity
の中はmempty
を使える(+
と""
を置き換える)。文字列のログを残すことに限定する必要もない。良いライブラリであれば、ライブラリの働きをするのに最低限の制約だけ課せばよい。ここでは、ログライブラリの要求はログがモノイドの性質を持つことである。
クライスリ圏
この圏は発明したものではなく、クライスリ圏と呼ばれる例である。クライスリ圏はモナドに基づく圏である。まだモナドについて議論するのに準備が整っていないが、モナドがどのようなものか雰囲気を感じてもらいたかった。限定的な目的に対して、クライスリ圏は対象として、根本的なプログラミング言語の型を持つ。型Aから型Bへの射は型Aから特別な装飾が行われた型Bから派生した型への関数である。クライスリ圏は独自のやり方でこのような射の合成を定義し、またその合成の観点で恒等射を定義した。(後で「装飾」と言う不正確な用語が圏における自己関手に対応することを触れる予定である。)
ここで述べた圏の基本的な内容を説明するのに使った特別なモナドはWriterモナドと呼ばれ、関数の実行のログを残したり、トレースしたりするものとして使われている。純粋な計算の効果を埋め込むためのより一般的なメカニズムもある。集合の圏でプログラミング言語の型と関数をモデル化できるのは既に見てきた。このモデルを少し異なった圏に拡張する。装飾された関数で表される射を持つ圏で、その合成は単にある関数の出力から別の関数の入力へ通過出来るだけではない。合成そのものの自由度を引き上げた。この自由度のおかげで、命令型プログラミング言語で従来副作用を使って実装されていたプログラムに対して単純な表示的意味論を与えることが出来たのである。
Javaプログラマーのための圏論(3.大小様々な圏)
大小様々な圏
対象がない圏
最も自明な圏は一つの対象も持たない圏で、射も持たない圏である。状況によって重要になるかもしれない。例えば全ての圏の圏を考えるとき。空集合に意味がある状況であれば、空な圏も意味があるだろう。
単純グラフ
対象を矢印で結ぶことで圏を作ることが出来る。任意の有効グラフからスタートして、単純に矢印を次々と追加することで圏にすることができる。最初に恒等射を各ノードに追加する。次に、ある矢印の終点と別の矢印の始点が一致するような2つの矢印に対して、合成になるように新しい矢印を追加する。新しい矢印を追加する度に、別の矢印(恒等射を除く)との合成を考えなればならない。通常無限にたくさんの矢印まで続くが、仕方がない。
圏を作るこの過程に別の見方をすると、グラフの各ノードは対象であり、合成可能なグラフの辺のすべての可能なチェーンは射として見ることができる(恒等射は長さが零のチェーンの特殊なケースとみることもできる)。
このような圏は与えられたグラフによって生成された自由圏と呼ばれる。
順序
今度は全く別の例を取り上げよう。対象の関係が射である圏である。その関係は以下である。各対象は自分自身以下である。$a \leqq b$ かつ $b \leqq c$ ならば、 $a \leqq c$ となり、合成が成り立つ。結合律も成り立つ。このような関係を持つ集合を前順序と呼び、前順序は圏である。
$a \leqq b$ かつ $b \leqq a$ ならば、 $a = b$ が成り立つような、より強い関係を与えることもできる。このような関係を持つ集合は半順序と呼ばれる。
任意の対象$a, b$に対して、$a \leqq b$または$b \leqq a$のいずれかが成り立つ条件を仮定すると、全順序を与えることができる。
前順序は圏であり、対象$a$から対象$b$へのへの射を高々一つ持つ。このような圏を「薄い」という。前順序は薄い圏である。
圏$C$の対象$a$から対象$b$への射の集合は射集合(hom-set)と呼ばれ、$C(a,b)$(または、$Hom_C(a,b)$)と記す。前順序の各射集合は空またはシングルトンである。それは射集合$C(a,a)$、即ち$a$から$a$への射の集合は、シングルトンであり、前順序の恒等射のみ含む。前順序は循環を含む場合もあるが、半順序は循環はありえない。
集合としてのモノイド
モノイドは驚くほど単純だが、強力な概念である。基本的な算術の背景にある概念である。加算と乗算はモノイドを形成する。モノイドはプログラミングにおいてユビキタスである。文字列、リスト、畳み込み可能なデータ構造、並列プログラミングでのfuture、関数型リアクティブプログラミングでのeventなどである。
モノイドは二項演算を持つ集合として定義される。この演算は、結合律が成り立ち、単位元と言う特殊な要素を持つ。
例えば、零を持つ自然数は加算の下でモノイドを形成する。結合律は次のような意味になる。
$$
(a+b)+c=a+(b+c)
$$
(数字を加算する際に括弧を外してもよいと言い換えることもできる)
単位元(中立元とも言う)は零である。なぜなら、
$$
0+a=a
$$
かつ
$$
a+0=a
$$
だからである。
2番目の式は加算が交換可能($a+b=b+a$)なため、冗長であるが、交換可能性はモノイドの一部ではない。例えば、文字列の連結は交換可能ではないが、モノイドを形成する。文字列連結に対する単位元は空文字であり、文字列のどちら側から連結しても変わらない。
Java(Java8以降)でモノイドを定義することができる。単位元をmempty
、二項演算をmappend
を持つ。
class Monoid<M> { M mempty; Function<M,Function<M,M>> mappend; Monoid(M mempty, Function<M,Function<M,M>> mappend) { this.mempty = mempty; this.mappend = mappend; } }
2つの引数の関数に対して、Function<M,Function<M,M>>
と言うシグネチャは最初は奇異に見えるかもしれないが、カリー化について触れた後では納得してもらえるだろう。
mempty
とmappend
の実装を与えることでString
についてモノイドを宣言することができる。
var m = new Monoid<String>("", s1 -> s2 -> s1 + s2);
s1 -> s2 -> s1 + s2
の複数の矢印を持つシグネチャは2通りに解釈できる。一つ目は複数の引数を持ち、最も右の値を返す関数、二つ目は最初の引数(最も左の引数)に対して関数を返すような関数の2通りである。後者の解釈は括弧を追加することによって強調することができる。s1 -> (s2 -> s1 + s2))
(矢印は右結合なので、括弧は冗長である。)
(Java7以前の)Javaでモノイドを定義すると次のように定義することもできる。
interface Monoid<M> {
M mempty();
M mappend(M m1, M m2);
}
Monoidのインスタンスは文字列で定義すれば以下のようになる。
class MonoidString implements Monoid<String> { String mempty() { return ""; } String mappend(String s1, String s2) { return s1 + s2; } }
圏としてのモノイド
集合の要素に対するモノイドの定義は圏と似ている。しかし、圏論では、集合やその要素から離れ、その代わり対象と射について議論する。二項演算の適用を集合のものを移動することとして少し視点を変えて考える。
例えば、自然数に5を加算する操作がある。これは0を5に、1を6に、2を7に写す。自然数の集合上に定義された関数である。任意の数mに対してnを加算する関数が存在する。nの加算器である。
加算器の合成はどうなるのか?5を加算する関数と7を加算する関数の合成は12を加算する関数である。よって、加算器の合成は加算のルールと同等である。関数の合成は加算で置き換えることが出来る。
単位元、零の加算器もまた存在する。零を加算しても動かない、だから自然数の集合においてそれは恒等射である。
整数から加算器へ写すことは、mappendをm->(m->m)とみなすことに対応している。mappendは、モノイドの要素をその集合に作用する関数へ写しているとみなせる。
一度自然数の集合から離れて、単一の対象、すなわち、加算器の射の束の塊として考える。モノイドは単一の対象の圏である。モノイドは合成律に従う射の集合を持つ単一の対象の圏とみなすことが出来る。文字列連結は右連結、左連結が選択できる。2つのモデルの合成テーブルはお互い対称の関係にある。"foo"の後に"bar"を連結することと、"foo"の前に"bar"を連結することが対応する。
圏論的モノイド、単一対象の圏は二項演算を持つ唯一の集合として定義できる。一つの対象の圏からある集合を取り出すことができることがわかる。この集合は射、先の例では加算器の集合である。言い換えると、圏$ M $の単一対象$ m $の射集合$M(m,m)$ である。この集合での二項演算を定義することができ、2つの集合要素のモノイド積が要素に対応する射の合成に対応する。$M(m,m)$ の2つの要素$f$と$g$に対して、これらの積は合成$f \circ g$に対応する。合成は必ず存在する。これらの射の始域と終域は同じ対象だからである。また、結合律も成り立つ。恒等射はこの積の単位元である。故に圏論的モノイドから集合的モノイドへ元に戻すことができる。実際、これらは一つであり、同じものである。少しだけ数学の話を掘り下げると、射は集合を形成するとは限らない。圏の世界は集合より広いものを扱う。任意の二つ対象間の射が集合を形成するような圏は局所的に小さい(locally small)と呼ばれる。通常はこのような微妙なものは無視すればよい。
圏論での興味深い現象の多くは射集合の要素が合成律を満たす射であり、且つ集合の点のどちらでもあると言う事実に依っている。ここでは、$ M $の射の合成は$M(m,m)$ のモノイド積に変換される。
Javaプログラマーのための圏論(2.型と関数)
型と関数
型の合成について
圏論の本質は矢印の合成である。必ずしも2つの矢印が合成できるとは限らない。ある矢印の終端の対象が次の矢印の始点の対象と一致していなければならない。プログラミングではある関数の結果が別の関数へ通過させることになる。ある関数によって生成されたデータが次の関数によって正確に解釈されなかれば、プログラムは動かない。二つの端は合成するために適合しなければならない。言語の型システムが堅くなればなるほど、この適合が表現しやすくなるし、機械的に検証もされやすくなる。
型とは何か?
型は最もシンプルな直観的には値の集合である。型BooleanはTRUEとFALSEの2つの要素である。
集合は有限集合も無限集合もありうる。StringはCharacterのリストであるが、無限集合である。IntegerはJavaでは $-2^{31}$から $2^{31}-1$の間なので有限集合である。
型と集合の識別は扱いにくい微妙なところがある。ポリモルフィックな関数は循環定義を必要とする問題があり、すべての集合の集合は存在しないと言う事実がある。重要なことは集合の圏が存在し、それは$Set$と呼ばれる。$Set$では、対象は集合であり、射(矢印)は関数である。
$Set$は特殊な圏で、対象の中をのぞき見たり、実際にそうすることで多くの直感が得られるためである。例えば、空集合は要素を持たない。1つの要素しか持たない集合もある。ある集合から別の集合への関数もある。2つの要素の集合から1つの要素の集合への関数もあるし、1つの要素の集合から2つの要素の集合への関数もある。恒等関数は集合の各要素を自身へ移す。
徐々に全ての情報は忘れて、圏論の記号、対象と矢印で表現していく予定である。
型の例
幾つかの風変わりな型について考えてみよう。空集合に対応する型は何だろうか?Javaのvoidではない。どのような値も継承しないし、その型を引数にして呼び出すことができない型である。引数にして呼び出すためには、その型の値を与える必要があるが、この型は値を持たない。この関数はどのような値を戻すかと言う点でなんの制約もない。この関数はどのような型も戻すことできる(但し、呼び出されることができないので、そのようなことは起きないが)別の言葉で言えば、その関数は戻り値の型においてポリモルフィックな関数と言える。
次にシングルトン集合に対応する型を考えてみよう。この型は唯一つだけ値を持つことが出来る。Javaでは void
である。この型を引数とする関数、戻り値とする関数を考えてみよう。voidを引数とし、それがもし純粋関数であれば、常に同じ値を返すことになる。次のような例になる。
int f44() { return 44; }
この関数は何も取らないのではなく、既に見たように、何も取らない関数は呼びだすことが出来ない。なぜなら、何もないことを表す値が存在しないからである。この関数は何を引数に取るのか?概念的にはダミーの値を取る。それは唯一のインスタンスで、明示しなくてもよい。単位元(unit)の各関数はtarget typeからある一つの要素を取り出すすることと同値である。(ここでは、int 44を取り出している)実際にf44を数字44の別の表現として考えることが出来る。これは関数(矢印)ついて述べることで集合の要素について述べること代わりになることの例である。単位元から任意の型Aへの関数は集合Aの要素と1対1で対応している。
戻り値がvoidである関数はどうだろう?単位元を戻す純粋関数は何もしない。議論の対象から外す。
数学的に、集合Aからシングルトン集合への関数はAの各要素をシングルトン集合の唯一つの要素へ写す。Aに対して唯一つこのような関数が存在する。これは次のような関数である。
void fInt(int x) { return; }
任意の数値を与えると、voidを返す。
任意の型に対して同じ式を実装した関数はパラメータ多相と呼ぶ。具体的な型の代わりに型パラメータを使ってこのような関数を実装することができる。任意の型から単位元への多相な関数をunitと呼ぶことにする。
<T> void unit(T x) { return; }
次に2つの要素を持つ集合である。JavaではBooleanである。Booleanからの純粋関数はそのような集合の2つの値を取り出すが、一方はTrueと対応し、もう一方はFalseと対応する。
Booleanへの関数は述語と呼ばれる。JavaではCharacter.isDigitなどが述語に該当する。
Javaプログラマーのための圏論(1.圏)
圏
圏は対象(object)と対象から対象へ進む矢印(arrow)から構成される。対象は丸印または点で表し、矢印は矢印(有向辺)で表す。圏の本質は合成であり、合成の本質は合成と言える。対象Aから対象Bへの矢印と対象Bから対象Cへの矢印があれば、これらの合成であるAからCへの矢印が存在する。
矢印
関数としての矢印は、射と呼ばれる。型Aを引数とし型Bを戻り値とする関数$f$と型Bを引数とし型Cを戻り値とする関数$g$を合成することで、型Aを引数とし型Cを戻り値とする新たな関数を定義することができる。このような合成を$f \circ g$と記す。
javaで書いてみると、次のようになる。
B f(A a)
C g(B b)
C g_after_f(A a)
{
return g(f(a));
}
Java8以降であれば、次のように書ける。
Function<A,B> f; Function<B,C> g; g.compose(f);
合成
圏では、次の合成に関する2つの重要な性質を満たさなければならない。
1. 合成の結合
$f$,$g$,$h$の3つの射があり、合成できるのであれば、これらを合成する際に括弧は不要である。
$$
h \circ (g \circ f) = (h \circ g) \circ f = h \circ g \circ f
$$
1. 任意の対象Aに対して、合成の単位元である矢印が存在する。この矢印は対象からそれ自身へのループの矢印である。合成の単位元と言うのは、対象Aで始まる矢印、対象Aで終わる矢印と合成すると、それぞれ同じ矢印と一致すると言う意味である。対象Aに対する単位元を$id_A$と表記し、A上の恒等射と呼ぶ。AからBへの矢印$f$に対して、
$$
f \circ id_A = f
$$
かつ
$$
id_A \circ f = f
$$
となる。
恒等射を実装すると、引数をそのまま返す恒等関数となる。どのような型に対しても実装は同じであり、ユニバーサルにポリモルフィクである。Javaでは次のように実装することができる。
<T> T id(T x) { return x; }
Java8以降であれば、Functon、UnaryOperatorにidentity()が定義されているので、
Function<T,T> id = Function.identity(); UnaryOperator<T> id = UnaryOperator.identity();
として表すことできる。 単位元の条件は、Javaで疑似的に表現すると、次のようになる。
Function<A,B> f; Function<A,A> id_A = Function.identity(); Function<B,B> id_B = Function.identity(); f.compose(id_A) == f id_B.compose(f) == f
恒等射idは、数字の0(零)と何もしないことを表すシンボルで、極めて役に立つものである。
プログラミングのエッセンスである合成
関数型プログラミングを行う際には、特異な問題解決のアプローチを行う。自明でない問題を解決する際には、大きな問題を小さい問題に分解する。分解した問題がまだ大きければ、さらに小さい問題に分解する。最終的には小さい問題を解決するプログラムのコードを書くことになる。プログラミングのエッセンスは、こうした分解した断片のコードを合成することによって、大きな問題を解決するのである。分解した断片が元に戻せなければ意味がない。
Javaプログラマーのための圏論(はじめに)
Bartosz Milewskiによって書かれた「Category Theory for Programmers」と言う書籍の内容が以下で公開されている。
https://github.com/hmemcpy/milewski-ctfp-pdf
この書籍では、多くの具体的な説明はHaskellであり、一部C++で説明されている。 今回はこの書籍の内容を基にJavaで説明を試みた。数学の説明や論旨の展開はなるべき原書に沿っており、翻訳に近い形とした。 不十分なところも多々あると認識しているが、まず公開したいと思う。
現在は5章の積と余積までしかないが、今後順次増やしていく予定にしている。
はじめに
数節でこの本で書かれていること、「豊富な余暇」で数学の最も抽象的な一分野を学ばなければならないのかと言う異論が完全に事実無根であることについて説明しよう。
このような楽観論は幾つかの観察に基づいている。最初に、圏論は極めて有用なプログラミングのアイデアの埋蔵物である。Haskellプログラマーは長い間この資源を叩いてきており、そのアイデアはゆっくりと他の言語へ徐々に広がっているが、この過程は非常に遅い。もっとスピードを上げる必要がある。
二つ目に、多くの異なる種類の数学があり、それらは異なる読者にアピールしている。微積分、または代数にアレルギーがあるかもしれないが、それによって圏論が楽しめないと言うことはない。圏論はプログラマーの精神に特に合う数学の種類であるとまで主張する。それは圏論が、特別なものを扱うより寧ろ構造を扱うからである。それが扱うのは、プログラムを合成可能とするような種類の構造である。
合成は圏論の最も根本である。そして、それは圏自身の定義の一部でもある。合成はプログラミングの本質であると強く主張する。偉大なエンジニアはサブルーチンのアイデアを思いつくより前に我々は絶えず、長い間合成をしてきた。少し前に構造的プログラミングの原則がプログラミングに革命を起こした。なぜならそれがコードのブロックを合成可能にしたからである。その後、オブジェクト指向プログラミングが現れた。これは対象を合成することがすべてである。関数型プログラミングは関数と代数データ構造を合成するだけでなく、それは並行処理を合成可能としたが、他のプログラミングで事実上不可能な何かである。
三番目に、秘密兵器、肉切り包丁がある。それを使って、数学を食肉処理して、プログラマーにとってもっと口に合うようにする。専門的な数学者の立場であれば、非常に注意して、すべての仮定は正しく得られるように、すべての発言は正確に制限するように、証明は厳密に構成するようにする必要がある。このようにして、数学の論文や書籍は外部の者にとって極めて読むのが困難にしている。物理学では形式ばらない論法を使って驚くべき進歩を生み出してきた。数学者はディラックのデルタ関数を笑ったが、それは偉大な物理学者P.A.M.ディラックがいくつかの微分方程式を解くために即興で生み出したものである。ディラックの洞察を形式化した分布理論と呼ばれる微積分の完全に新しい分野を発見されると、彼らは笑うのをやめた。
もちろんごまかしの主張を使って明らかに誤ったことを述べるリスクを犯す時には、形式ばらない議論の背後にある厳密な数学的な理論が存在することを確かめるつもりである。ソーンダース・マックレーンの圏論の基礎 の使い古したコピーが寝室用のランプの上に置いてある。
プログラマーのための圏論なので、コンピュータ・コードを使って主要な概念の説明をする。関数型言語がより好まれている命令型言語と比べて数学に近いことに気が付くであろう。それはまたより抽象化する力を提供する。だから、自然な衝動で、圏論の報奨金が得られる前にHaskellを学ぶべきと言いたくなる。しかし、それは圏論が関数型言語の外側では適用できないことを暗示しているのではなく、単純に真実ではない。だから、多くのJavaの例を提供している。確かに醜い構文を乗り越えなければならず、パターンは冗長の背景より際立っていないかもしれないし、より高次な抽象化の代わりにコピー&ペーストを強いられるかもしれないが、Javaプログラマーのすべてである。
経験豊富なプログラマーであれば、圏論や関数的なメソッドについて気に掛けることなくコードを書いてきた。何が変わるかと、尋ねるかもしれない。確かに、新たな関数型の特徴の厳密な傾向が命令型言語に広がっていくことに気付くだけかもしれない。オブジェクト指向プログラミングの要塞、Javaにさえ、ラムダ式が取り入れられた。大きな変化を駆動する強制力の一つがマルチコアの革命である。広く行き渡っているプログラミング・パラダイム、即ちオブジェクト指向プログラミングは並行処理の領域では何ももたらさず、その代わりに危険でバグを生みやすい設計を奨励する。データの隠蔽化、オブジェクト指向の基本的な前提は、共有とミューテーションと組み合わさった時、データレースの処方箋となる。データの持つミューテックスを組み合わせると言うアイデアはデータを保護するには便利であるが、不幸にも、ロックは合成しないし、ロックによる隠蔽はデッドロックを起こしやすくなるし、デバッグもより困難となる。
しかし、たとえ並行処理がなかったとしても、ソフトウェアが益々複雑になっていくことで、命令型パラダイムのスケーラビリティの限界を試されている。短く言えば、副作用は手に負えなくなってきている。確かに、副作用を持つ関数はよく重宝されていて、書きやすい。原則としてそれらの高価は名前とコメントでエンコードすることができる。SetPassword
やWriteFile
と呼ばれる関数は明らかに何らかの状態を変化させるし、副作用を生み出し、それを扱ってきている。副作用のある関数を直ぐに他の副作用のある関数と合成し、次々と合成していくだけで、身の毛もよだつことが始まる。副作用は本質的に悪いのではないが、それらが隠蔽されることで、大規模で管理できないようになることも事実である。副作用はスケールしないし、命令型プログラミングは副作用がすべてである。
ハードウェアの変化とソフトウェアの複雑性の増大により、プログラミングの基礎を再考することに迫られている。ヨーロッパのゴシック教会の建築家のように、材料と構造の限界に対する技術を磨いてきた。フランス、ボーベの終わりのないゴシック教会がある。それは人類の限界への深い闘争の証人である。高さと明るさの以前の記録を乗り越えようとしたが、一連の崩落に苦しめられた。鉄棒と木製素材のような場当たり的な対策で、それを崩壊から防いでいるが、明らかに多くの物が間違った方向に進んでいる。現代的な視点でみると、現在の材料科学、コンピュータ・モデリング、有限要素分析、及び一般的な数学と物理学の助けを借りずに、これほど多くのゴシック構造物が成功裏に完成されてきたことは奇跡である。将来の世代が。複雑なオペレーティングシステム、ウェブサーバ、インターネット・インフラストラクチャを構築することを誇示するようなプログラミング技術を称賛するようになることを期待する。率直に言えば、非常にもろい理論的な基礎に基づてすべてのことを行おうとしている。もし前に進みたいのであれば、それらの基礎を確固としたものにしなければならない。