# Y Combinatorを直感的に理解。しようと試みる。 _published: 2008/02/02_  [id:yuji1982](http://d.hatena.ne.jp/yuji1982/)さんのエントリ。 - [Y Combinatorが凄すぎる！ - yuji1982の日記](http://d.hatena.ne.jp/yuji1982/20080124/1201177935) なにこれ。Y Combinatorすげぇ！意味わからん。 今朝、妻からメールが来ました。 > 静かに歩く犬は犬じゃない。私の夢に出てきたフレーズ。 意味わからん。でも、それ以上にY Combinator意味わからん。 普通にフィボナッチ数を計算するプログラムは、こうですよね。 ```cs static int fib(int n) { if (n < 2) { return n; } else { return fib(n - 1) + fib(n - 2); } } ``` これを、C#のクエリ式で書くと。 ```cs static int fib(int num) { Func<int, int> f = null; f = n => (n < 2) ? n : f(n - 1) + f(n - 2); return f(num); } ``` `if` は三項演算子に変えておきました。そのほうがカッコイイから。 で、`Func<int, int> f = null;` っていらないよね。って話しです。そこで、id:yuji1982さんのところのメソッドをパクってきました。このメソッドが噂のY Combinatorらしいです。 ```cs static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> F) static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> F) { return t => F(Fix(F))(t); } ``` この魔法のメソッドを使うと、 `fib` メソッドはこう書けます。 ```cs static int fib(int num) static int fib(int num) { return Fix<int>(ff => n => (n < 2) ? n : ff(n - 1) + ff(n - 2))(num); } ``` なにこれ。Y Combinatorすげぇ！意味わからん。 そこで、可哀想な私が、頑張って仕組みを考えてみます。 まずは、ラムダ式だと型が省略されるので、匿名メソッドに書き換えます。それから、変数名をわかりやすく日本語に。.NETは日本語OKなので、下のコードはコンパイル可能です。Tは、intに固定しました。 ```cs static Func<int, int> Fix(Func<Func<int, int>, Func<int, int>> 擬似フィボ使って元のフィボ返す) { // 「擬似フィボ使って元のフィボ返す」から「元のフィボ」を取り出して実行する関数 Func<int, int> 最終フィボ = delegate(int num) { // 「擬似フィボ」と「最終フィボ」は同じ（ただし、階層が違うイメージ） Func<int, int> 擬似フィボ = Fix(擬似フィボ使って元のフィボ返す); // 「元のフィボ」を取り出す Func<int, int> 元のフィボ = 擬似フィボ使って元のフィボ返す(擬似フィボ); // 「元のフィボ」を実行 int 答え = 元のフィボ(num); return 答え; }; return 最終フィボ; } static int fib(int num) { // 「擬似フィボ」を入れたら「元のフィボ」を返す関数 Func<Func<int, int>, Func<int, int>> 擬似フィボ使って元のフィボ返す = delegate(Func<int, int> 擬似フィボ) { Func<int, int> 元のフィボ = n => (n < 2) ? n : 擬似フィボ(n - 1) + 擬似フィボ(n - 2); return 元のフィボ; }; Func<int, int> 最終フィボ = Fix(擬似フィボ使って元のフィボ返す); return 最終フィボ(num); } ``` そして、このコードをグルグル眺めます。グルグル。グルグル。グルグル！そういえば、再帰でした！ 「最終フィボ」と「擬似フィボ」が同一人物だというのがポイントですね。この「最終フィボ＝擬似フィボ」がひとつの「環境」になっています。図を描くと、こんなカンジ。 ![[20080202164458.png]] 「元のフィボ」から「最終フィボ＝擬似フィボ」を呼んでいますが、これは「元フィボ」が所属する「最終フィボ＝擬似フィボ」ではなくて、ひとつ下の階層の「最終フィボ＝擬似フィボ」を呼んでいるイメージです。図を描くと、こんなカンジ。 ![[20080202164550.png]] おお、何となく解ったような。今日はこれくらいにしといてやろう。 それでは、Y Combinatorをググって見ましょう。順番が逆か。 [id:amachang](http://d.hatena.ne.jp/amachang/)のエントリ。 - [Y コンビネータって何？ - IT戦記](http://d.hatena.ne.jp/amachang/20080124/1201199469) ~~さすが。~~それにしても、JavaScriptすげぇ。（追記：id:amachangに対して「さすが」のひと言で済ますのは失礼ですよね。裏でがむしゃらにやってるんだから。） しかし、「式がすべて λ 計算に変換できる」という考え方が具体的にどのように役にたつかが分からない＞＜ コードが破壊的じゃなくなる。ってことでしょうか。状態を持たない。スレッドセーフ。これからはマルチコアの時代。マルチスレッドは当たり前。.NETはスレッド生成するごとに、自動的にCPUに割り当ててくれるから楽チン。サーバーサイドだけでなく、クライアントもマルチコア。ちなみに、Windows Formsのイベントは「シングルスレッド・マルチ・アパートメント・モデル」で、マルチスレッドじゃありません。当たり前か。クライアントからサーバーを呼び出すときに、非同期で呼び出すことが増えるでしょうね。と、マルチスレッドの話しにもって行きましたが、関係あるのかどうかは不明です。たぶん、関係ないです。そんなこと言っている人、誰もいないし。そういえば、SOA（サービス指向アーキテクチャ）は、オブジェクト指向と違って状態（ステート）を持ちません。そうすると、オブジェクト指向言語より関数型言語ってことですか？だからF#とか？ id:amachangのエントリをブクマしてる人は、解ってる人と、まったく解ってない人に二極化してますね。 こういう計算の話だと、dankogai氏も何か言ってるのではないでしょうか。と思ったら、案の定ありました。 - [404 Blog Not Found:TuringとChurchの狭間で](http://blog.livedoor.jp/dankogai/archives/50458503.html) あとで読む。今日はK-1を観ないといけないので。 Schemeで。 - [Y Combinator](http://www.loveruby.net/ja/misc/ycombinator.html) あとで読む。今日はK-1を観ないといけないので。 その他もまとめようと思ったら、d:yuji1982さんのブックマークにまとまってるじゃないですか。 - [はてなブックマーク - yuji1982のブックマーク - Y combinator](http://b.hatena.ne.jp/yuji1982/Y%20combinator/) あと、このエントリがおもしろいかも。理解していませんが。 - [ホワット・ア・ワンダフル・ワールド 2 つの原理と文化](http://alohakun.blog7.fc2.com/blog-entry-894.html) ラムダ計算とかチューリングマシンとか。そういえば書店で「たのしいRuby」のナナメ向かいの書棚にそんな本が並んでました。今までスルーしてきましたが、これはおもしろそう。勉強してみよう。