再帰のところで、もう解ってるfib(x)は最初から計算せずに済ませたい!。違うコードに書き直せば、出来るかも知れないけど、解りやすいコードがめちゃくちゃになるのも困る><そこで不動点です。fibをコードのキモの部分をそのままにして、前回説明した「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を用意してやります。};}これをYに入力すれば、不動点すなわち再帰する関数が得られます。Y(F_for_fib);不動点版fibが出来ました。fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が返ってきます。ここまでではYコンビネータを使うようにしただけでまだ高速化は何もしてません。そこで、Yコンビネータの方に(とりあえず安直な)キャッシュ機構を仕込んでみます。名前をYmemoとしましょう。Ymemo(F_for_fib);「キャッシュ機構利用版」のfibが出来ました。fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が帰ってきます。こいつで時間を計測してみると、fib(30)は0msec、fib(35)でも0msecでした。計測不可能の瞬殺です。fib(30)は少なくとも1000倍以上、fib(35)は少なくとも1万4千倍以上の高速化ができました。結果はちゃんと1346269と14930352が帰ってきてます。大事なのは、Ymemoはfib専用ではないと言う事です。Ymemoは、「キャッシュ機構付き再帰」を作り出す汎用のライブラリとして使えます。様々な「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」に対して、「キャッシュ機構付き再帰」を産み出してくれます。Ymemoのほかの利用例として、「ハノイの塔」*2というパズルを解くプログラムを試してみます。Hanoi(x.x-1,x.c,x.b,x.a))].join("");}hanoi()にパズルの状態Hanoiを入力として渡すと、文字列で解法のステップが返ってきます。Hanoiのプロパティxがパズルの規模を表す値で、a,b,cはパズルで使う3本の棒を表します。この普通のバージョンを実行したところ、x(パズルの規模)が20の時に23秒515msec、22の時には1分33秒781msec掛かりました。さきほどのfibと同様に、hanoiをコードのキモの部分をそのままにして、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を用意します。}}そして、Ymemoに入力して「キャッシュ機構付き再帰」を取得します。Ymemo(F_for_hanoii);このYmemoで作った「キャッシュ機構利用版」hanoiを実行したところ、掛かった時間は、x(パズルの規模)が20の時に578msec、22の時には2秒125msecでした。fibほどじゃないですが、40〜50倍は高速化されています。Yコンビネータへの機能追加をpluggableにYmemoでは「メモ化」を直接Yコンビネータに組み込みました。他の機能も追加する事を考えると、これでは不自由です。ここで色んな機能を追加するための準備として、Yコンビネータと追加機能を分離します。Yコンビネータの方は素のままにしておき、Yコンビネータに渡す「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」の方に仕込みを入れる様にします。{//仕込みgを組み込んだ「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を返す。};}仕込みであるgは、受け取ったfのフリをする関数(fの偽物)を返すようにします。仕込みの例として、先ほどYコンビネータに直接組み込んだメモ化機能を、独立した仕込みとして切り出します。{//メモ化の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。}}これで、素のYコンビネータを機能を仕込んで利用できます。gen_memorizer()));Yコンビネータは素のものです。F_for_fibの代わりに、メモ化の仕込みを入れた「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」をYコンビネータに渡します。fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が返ってきます。gen_memorizer()));です。これもちゃんと動きます。トレース機能の追加では、メモ化の次に、今度はデバッグ的な機能を追加してみます。安直ですが、トレース機能の仕込み生成関数です。{//トレース機能の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。}}再帰の度に引数を表示します。'0'とダイアログボックスが出てきます。こんな感じに動いてるんですね。同じ引数で何度も実行しているようです。さっきのメモ化版ではどう動いていたのでしょうか。複数の機能追加を組み合わせて使うプラグイン化した追加機能は、組み合わせて使えます。gen_memorizer()));fib(5);wrapは、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」に対して、機能を仕込んだ「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を返します。それに対しても同様にwrapで機能を仕込めます。実行結果は以下の通り。'4'ずいぶん減ってますね。組み合わせた機能も、fibだけじゃなくて、ほかの関数にも使えます。さっきのhanoiに使ってみます。「普通の再帰関数」を呼ぶ。「普通の再帰関数」の代わりにfを呼ぶ。};}にしておく事で、再帰に色んな機能をpluggableに追加できるよ、というお話でした。機能を追加しないでそのままYコンビネータに入力してただの再帰にも出来ます。以下、作ってみた追加機能を他にもダラダラ挙げてみます。大きな規模の計算は、ひとつの「プログラム」*3をたくさんのマシンを使って協調させて走らせます。「プログラム」の方ではマシンの間の通信とかどのマシンで動いているとかはあまり意識せずに書きたいものです。PCでも一昔前には、SETI@homeとかUDとか、世界中の参加PCを使って計算をするようなプロジェクトもたくさんありました。そんなわけで、弾さんのllevalサーバを利用させてもらって、再帰の実行をリモートに分散させて実行する自動分散化機能を。{//自動分散実行化の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。}}ブラウザだとクロスドメイン制約のせいでうまくいかないので、Rhinoで動かします。お茶の子さいさいでエレガントに書けると思います*4。こんな感じで実行します。//cond:偶数番目を弾さんサーバで実行。Hanoi(5,'A','B','C'));その6。gen_speculative(vent){//先読み山かけ先行実行の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。}}必要になると思われる再帰を、先取りして実行しておく機能です。wikipedia:投機的実行を見てください。メモ化機能と組み合わせて使います。最近のCPUのようにコアがたくさんあるマシンだと速くなるかも知れません。組み合わせてもいいかも知れません。いうわけで、Haskellやろうぜ!(おまけ)落ち着いてみてみると、再帰というのはじつは「関数を入力として受け取りその関数を使う」関数の、特殊な場合という事が解ります。(?)入力されてきたのが自分自身だった場合が再帰というわけです。実際のところ、Yコンビネータじゃなくて単なる再帰の方が速いので自分はプロダクションコードで実際に使った事はないです。目の前の状況しか考えてないコードよりも、一般的な形に書いておいた方が、ものすごく可能性が広がるという事を実感できれば、お仕事にも意味があるかなぁと思います。関数型言語では、この考え方が徹底していて、ライブラリなんかももの凄い汎用的にできてます。それは単に文化だけでなく、関数型言語のパワーのおかげでもあります。上記の再帰への機能追加関数達ですが、構造が似ていますね。これもちゃんとした関数型言語プログラマなら汎用的な関数を用意してしまうでしょう(自分は全然ちゃんとしてないので気持ち悪さに耐えてしまいました)。関数型言語では、処理(関数)を普通に気軽に後から渡してやれるし、数学の関数の様に縦横無尽に組み合わせやすいので、コードのありがちな構造自体すらライブラリ化できてしまうのです。Haskellではfibを多分ふつうはこんな感じに書きます。Haskellではここで使ってる関数はみんなデフォルトでimportも不要で使えます。fibs).head;}こんな感じです。使ってる関数は、JavaScriptにはないので、それらも翻訳するとだいたいこんな感じです。}}zipWithが構造自体をライブラリ化したものの例と言えると思います。何か同じ計算を沢山のデータに対して行う、というありがちなパターンのプログラムの構造を、関数としてライブラリ化してある訳です。JavaScriptは関数をファーストクラスが扱える(関数を関数のまま引数に渡したり出来る)ので、言語としては上記のように関数型のプログラミングも可能です。いう使われ方を想定してないので、こういうライブラリを探して*5きてさらに実行時環境にも用意してやり、そう言うコーディングするあなたを変態と呼ぶ心無い人に耐えられればOKです。関数をそのように扱えない言語だと、こういうやり方をするために、かえっていろんな無駄な記述が必要になっり、トリッキーなテクニックが必要になってしまいます。あと、JavaScirptの例ではfibsの所が関数じゃなくてただの値なのにfibs自身を参照していてエラーになってしまうと思います。Haskellでは、データ自体でも問題なく自己参照が出来ます。fibsは長さ無限ですが、Haskellは、プログラムの必要になった部分だけを必要になってから評価(実行)するのでノープロブレムです。エントリの冒頭に書いたように、数学(主に基礎論系。)との対応付けもよくなされていて、何気ないライブラリが数学的に証明されているもの凄い汎用性とパワーを持っていたりします。超汎用的なライブラリをちょこちょこと組み合わせるだけで、どんどん高度なプログラムが出来ていきます。モジュールを組み合わせてさらにモジュールを作るようにプログラミングしていけば、プログラムの機能は、コードの規模にたいして、足し算ではなく、掛け算的に広がっていきます。上記のfibもずいぶん短く書けていますが、大きなプログラムになればなるほど差は倍々に広がっていきます。この感覚というか習慣は、関数型言語を使う事で最もよく培われて最もよくパワーを発揮すると思いますが、JavaなりPHPなりでのコーディングにも必ず良い影響をもたらすと思います。目の前の状況しか考えてないコードよりも、一般的な形に書いておいた方が、ものすごく可能性が広がるという事自体は、どの言語でも同じだからです。極北(??)、Haskellの本を紹介しておきます。詳細を見るWebにHaskellの情報は結構ありますが、玄人向けです。Haskell)」というドキュメントがありますが、これは「天才な人にはやさしい」という意味なので気を付けて下さい。ふつうの人には、この本がふつうの意味でやさしいくていい感じです。興味が湧いた人は、まずこの本を読む事をお勧めします。偉そうな事を書きましたが、自分は真性のへなちょこなので、玄人がこのエントリを見たら炊飯ものだと思います*6。それでも、仲間が増えて欲しいという思いであえて恥をさらさせて貰います。追記Haskell版fibの定義で、当初カッコが抜けていたのを修正しました。(2009-04-24)*1:オリジナルは名前空間汚染を回避していますが、ここでは気にしていません。20:42さあ、Yコンビネータ(不動点演算子)を使おう!Tweet広告を非表示にするもっと読むコメントを書く2009-04-17おとうさんにもわかるYコンビネータ!(絵解き解説編)先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。きしださんのエントリのおさらい本題の前に、きしださんのエントリをおさらいしておきます。Yコンビネータはただのオモチャじゃないんだよ関数だけで色んな事が出来る条件分岐をする関数ってのもある。再帰(ループ)を作れる関数もある。←これがYコンビネータ。数値も関数で表現できる。関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう!!って事が書いてありました。普通のプログラミング言語では常識である、if文もfor文やwhile文も、仮引数以外の変数・変数代入も、果ては数値すらすべて使わずに、ただただ関数だけでそれらを「エミュレート」できちゃってます。関数というか、正確にはλという単純な文字列変換ルールだけでできちゃってます。λSUGEEEEEEEEEEEEEEEEEEEEEE!!!!!!!!*2きしださんのエントリの趣旨は、「λSUGEEEEEEEEEEEEEEEEEEEEEE!!!!!!!!」であって、Yコンビネータはその一部な訳ですが、そのお話の一部であるYコンビネータの所を、今回整理してみまず。何かを入れたら、何かが出てくるモノだ中学校で習いましたね。関数に関数を入れたっていいじゃない中学校では、関数に関数を入れるというのはやらなかったかも知れませんが、いいじゃないですか入れたって。関数を入力とする関数のなかに、Yってのがある通称Yと呼ばれるある関数があります。こいつは関数を入力として、関数を出力します*3。Yから出力される関数の性質このYが出力する関数(図では☆=Y(M))は、ある性質を持ちます。自分の元ネタであるYに入力した関数(図ではM)に入れると、また自分と同じ関数(図では☆=M(Y(M))=Y(M))が出てくるのです。Mからの出力である☆とMへの入力である☆とが同じという訳ですから、M(Y(M))=Y(M)と言う訳です。Yから出力される関数の性質ーもういちどMに入れ直してみる最初にMにY(M)を入力したときの出力はM(Y(M))ですね。それをもう一度Mに入れてます。すると出てくるのはM(M(Y(M)))と言う事になりますが、これもやはり同じく☆であり、Yから出てきたときの☆=Y(M)と同じです。M(M(Y(M)))=Y(M)と言う訳です。Yから出力される関数の性質ー何度も何度もMに入れ直してみる何遍やっても変わりませんね。Mにとって、Y(M)という入力は、変わらずにそのまま出てきてしまう特別な入力なのです。この特別な入力を不動点と言うらしいです。それと再帰/ループと何の関係があんの?ですよねー。何回もMを適用(呼び出し)してるあたりがちょっと関係ありそうですけど。きしださんのエントリだと、ここが僕には解りずらかった。計算した結果が出力されます。して2を入力すると10が出力されます。再帰というのは、関数が自分自身を使ってる事です。それをちょっといじった、こんな関数にしてみます。