こんにちは。15のphi16とかいいます。はじめてrogyブログをかかさせていただきます。
これはrogy Advent Calendar 2015の12日目の記事です。11日目は@cyan_rej55さんでした。
テーマは†万物の創造†ということですが、宗教色は多分ないのです。たぶん。

はじめに

私は一応rogyのほうでゲーム制作とかしてます。謎のゲームつくったのでそろそろ公開したいです。
さて、私はゲーム作るのが好きなのですが、プログラミングにおける「関数型言語」というものも好きです。
そこで(元祖)手続き型にはあんまりない、関数型言語でよく用いられる概念について、文字通り1から解説・創造していきます。
長々とした読み物になってしまいましたが、読んで面白さとかを感じた方がいたら関数型言語をやるなり手続き型にそれらをつっこむなりしたらいいなと思っています。
対象はプログラマっぽくて数学好きっぽい人です。

1

何よりも最初に必要なのは1です。ですがこの1はいわゆる自然数ではありません。言うなれば「自明」と呼ぶようなものです。
そこにただ存在しているということ、はなかなか認識されているものではありません。具体的には : 
  • int main(){}
という関数をC/C++で書くことがあるかと思われますが、これは0引数の関数ではなく、「1を受け取る」関数とみなすことができるのです。1引数ではなく、1です。
実際これはHaskellではユニット型『()』と呼ばれます。これが全てのベースになります。
ちなみに1って呼ぶのは後述の直積の単位元だから(とか)です。

直積 A × B

集合の方でも出てくる直積という概念ですが、これは2つの物があったときにその両方を保持する物が存在することを表します。
つまり、いわゆるPair,Tuple(,Struct)です。戻り値のためにわざわざ構造体を作らなくて良いなど便利なのです。
個人的に必要だとおもうのはPairを生で生成可能なこと、つまりJavaのようにわざわざ自分でnewとかを書かなくていいことかなと思っています。仕方ないですけど。
C++のstd::tieみたいになるのも残念ですし、直積はもっと言語側でサポートしほしいなとか思います。

直和 A + B

この直和ですが、全くと言っていいほど認知されていません。
何かというと、直積の反対で、2つのうち片方のみを保持していることを表す型です。Eitherとかいいます。
Eitherの制限としての「Maybe, Optional, Nullable」の方は最近ようやく流行ってきてる気がします。
これらは「あるかないか」ですが、Eitherは「AかBか」を表現します。一般的ですね。
例えば「本来なら」直和として表現すべきなのに大抵そうなっていないものがあります : Boolです。
Boolは、まさしく1と1の直和として表現できます(つまり1+1=2です。)。これで値が-1なんかになることはなくなるわけです。
Eitherそのものは例えばエラー処理に使うことができます。正常な値を「右」で返して発生したエラーを「左」で保持、みたいなことをしたり。
うまくやれば例外処理機構そのものを「創り上げる」ことができます : C++のExpectとかまさにそんな感じで使われますね(未来的に)。Expectについてはこれが詳しいです。
ちなみに演算子の優先順位として A × B + C = (A × B) + C として解釈してください。

冪 B → A

型に対して冪(二項演算)を定義するというのも変かもですが、集合においてA^BがBからAへの写像の集合であったように、型の冪とは関数のことです。
集合の冪集合といえば2^Aですが、これはAから2 = Boolへの写像、つまりAの指示関数と同じものですね。
指示関数に具体的な値を渡すことでBoolが得られます。即ちBとB → AがあるときAを得ることができます。これが関数適用です。
といってもまぁ細かいことは気にせず関数 B → A を使っていこうかと思います。私は最近冪と関数の対応に感動しました。
関数は様々な解釈を生みます : 「導出」「抽出」「変換」「埋め込み」「割り当て」「計算」などでしょうか。この多様性が便利な所以でもあるのかもしれません。
実際これだけでも殆どを構築できます。直積直和どちらも関数のみで作ることもできますし。だいたい。
ですが更に世界を広げる為にもうちょっと基本概念を創ります。
あと優先順位としては A + B → C → D = (A + B) → (C → D) となります。最弱で右結合。

多相 F A

ちょっと話は変わりますが「一定の構造」を「任意の型」に適用したいニーズはかなりあります : template,Genericsなど。
これは「型をとって型を返すモノ」Fとして考えることができます。Fは型じゃないです。
これによって関数型ではよく出てくるリストを作ることができます。要素の型をAとしたリストLは
  • L A = 1 + A × L A
として表せます。直和の左は「空」、右は「要素とリスト」なので、「要素がない、または要素があってその後続も存在する」ものがリストと考えられるわけです。この構造はAの中身には依存していません。
例えば、リストという構造には一般的に「長さ」が定義され、これは要素の型に不変です。
つまりlength : L A → Intです。
多相型にしないとlengthを全ての型Aについて作ることになるわけです。これを防ぐためにC言語では暗黙の型キャストがあったのかなぁ、と思わなくもないですがダメです。
ちなみに今までの例もみんな多相型です。例えば直積は左・右の型に依存せず定まるので。

型クラス

先ほどの例では「任意の型」の適用でしたが、実際は「乗算のできる型」に対して適用したい、みたいなことがあると思います。
これを実現するのが型クラスで、C++ではconcept(無い)、Javaでいうinterfaceみたいなものです。ゆるいことを言えばオーバーロードっぽい感じです。
例えば「A × A → A」ができる型を「乗算のできる型」みたいに扱います。すると「全ての乗算可能型」について同名で掛け算を適用できるわけです。
Haskellでは「数値」「除算」「実数」「比較」「順序」「最大最小」「自然数対応」「表示」「読み込み」「畳み込み」などたくさんの型クラスがあり、演算を一般化しています。
例えば比較に関しては compare : A × A → 3 が必要とされており(ここで3はLessとEqualとGreaterの直和になる)、これを満たす型は x < y や x >= y などの比較演算ができるようになります。

具体的な構成

これで†万物の創造†への準備は整いました。実際に例を書いていきます。
細かく解説しようと思ったんですけど長くなりすぎるので列挙していくのです。

1. よくあるもの

  • Bool = 1 + 1 ―― 二値論理
  • Nat = 1 + Nat ―― 自然数 (ペアノの公理)
  • List A = 1 + A × List A ―― Consリスト
  • Stream A = A × Stream A ―― 無限リスト
  • Tree A = A + Tree A × Tree A ―― 葉に値を持つ二分木

2. 計算 Arrow

通常の計算A → Bの「→」を一般化すると(二項演算としてみると)、P A Bです。ここで計算Pに求める制限は、
  • P A A (何もしないでそのまま出力する計算)
  • P A B × P B C → P A C (順序結合可能)
  • (A → B) → P A B (通常の計算を一般化する)
  • P A B → P (A × C) (B × C) (一部だけを計算させる)
というもので、これを満たすとArrowという型クラスになります。
  • P A B = A → B ―― 通常の計算(関数)
  • P A B = Stream A → Stream B ―― ストリーム処理
  • P A B = A × S → B × S ―― Sを状態としてもつ計算
  • P A B = A → B + E ―― 例外処理
  • P A B = A → B × P A B ―― オートマトン

3. 結果 Monad

これは完全に私の個人的思想なのですが、Arrowが入力についても考えるのに対しMonadというのは結果のみを保持するようなもの、と思っています。まぁ順序実行でいいんですけど。
そうすると入力がなくなって、値Aを表現するM Aとして表わせ、必要な法則(型クラス)は単純になって、
  • A → M A (ただの値を計算結果にする)
  • M A × (A → M B) → M B (前回の計算結果と、その値を使った計算をつなげる)
です。Arrowの特殊版なので実際にP A B = A → M Bと対応がとれます(KleisliArrow)。
  • M A = A ―― ただの値
  • M A = 1 + A ―― 失敗
  • M A = S → A × S ―― 状態
  • M A = List A ―― 非決定性計算
  • M A = (A → R) → R ―― CallBack, 継続

4. 環境 Comonad

あんまり理解していないので細かいことは言えませんが、Monadの「逆」としてP A B = W A → Bを考えます。
そうすると法則が逆転して、
  • W A → A (環境から抽出)
  • W A × (W A → B) → W B (環境を移し替える)
これだと結果を返すのではなく環境を受け取ることになるわけです。
  • W A = List A × Int ―― 現在地、近傍
  • W A = Tree A ―― 部分木畳み込み
  • W A = (S → A) × S ―― 環境更新

5. アクセス Lens

いわゆるオブジェクト指向でのGetter/Setterは、A → B(抽出), A → (B → A) (書き込んだ結果を返す)と書くことができます。
これを直積で合成するとA → B × (B → A)となり、軽量Lensと呼ばれます。これもこれでおもしろい。
そして、これをいじると(B → F B) → A → F Aが出てきます(ここでFはFunctorという型クラスに含まれる型)。 出てくるらしいです。
このときGetterとSetterはそれぞれ
  • (A → R) → B → R ―― Aでの読み出しをBでの読み出しに変換
  • (A → A) → B → B ―― Aの変換をBに書き込み
と考えることができ、それぞれが
  • Getter A = Const R A ―― 常にR。
  • Setter A = Identity A ―― 常にA。
というFunctorに対応します。もっとやっちゃうと
  • (A → F A') → B → F B' ―― Lens
となります。これは本当に様々な「アクセス」を一般化することができます。
  • F A = A ―― Setter
  • F A = R ―― Getter
  • Contravariant F, Applicative F ―― Fold, 畳み込み
  • Applicative F ―― Traversal, 走査
  • Functor F ―― Lens
さらに「→」を一般化してP A (F A') → P B (F B')とすると
  • Choice P, Applicative F ―― Prism, 部分的全単射
  • Profunctor P, Functor F ―― Iso, 同型
  • Forall P, Forall F ―― Equality, 等価
とまでなります。一般化された方は一般化する前のものとして使えます。つまり「同型」があるとそこから「Getter」「Setter」ができます。
説明的にはとりあえず様々な「アクセス」を一般化することができた、と考えればいいかなぐらいです。
これを使うと複素数で点P中心にθ回転する関数は subtracting P . _phase +~ θ　で終わりです。すごい。
ちなみにsubtractingはIso、_phaseはLensです。
正直Lensを一番紹介したかった。 

6. 世界 IO

せっかく万物の話をしているので世界をつくりたいとおもいます。
Haskellで用いられている「世界」は単純に、RealWorldという型を状態として持つMonadとして扱われます。これがIOモナドです。
IO A = RealWorld → RealWorld × A ―― 世界。実際には細かい違いがある。
このRealWorldはまさに世界そのもので、これを使うことで任意の操作(システムコールとか)ができる、という「仮想的な対象」です。
Monad内部の値を取り出すにはMonad以外の何らかの方法が必要、という制約によってRealWorldの整合性が保たれるのです。たぶん。
というわけで、「世界」とはMonadにより閉じ込められた状態、ということになります。
ちなみになんと「世界を過去に書き換える」みたいなことができるみたいです。過去の書き換えに永遠に時間がかかるみたいですけどね :(
 

終わりに

解説ほとんど無い上に省略・適当な部分が多く申し訳ないです。間違えてる部分などあれば教えて下さい。
とりあえずは「1」から「世界」まで、いろいろなものが型で表せることがちょっとでもわかっていただければとおもいます。
C言語とかではハード的制限が強かった上に型は殆ど自明ですが、言語にきちんとした型をいれることでいろんなものができるようになるのです。
もっと関数と型を大事にしてあげてください、よろしくおねがいします。
あともっと面白い話を見たければ型理論とか圏論とかみるといいんだとおもいます。はい。
実際の実用っぽいです。おもしろい。 : dynamorphism
タグ ：
#phi16
#プログラミング言語