さあ、Yコンビネータ(不動点演算子)を使おう！

前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。


Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。


じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？


というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。


今回、プログラムの例をJavaScriptで書きます。Yコンビネータ(不動点演算子)は、amachang先生の定義を拝借します*1。

function Y(f) {
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })
}

その1。無駄な再帰を省略して爆速化

まず、Yコンビネータや不動点の考え方の応用は、「メモ化(memoization)」という汎用関数です。


きしださんも例に用いていた、フィボナッチ数という数を計算する関数を考えます。


まず、Yコンビネータとか関係なく、普通に再帰するバージョンです。

function fib(x) {
  if (x < 2) {
    return 1;
  } else {
    return fib(x-1) + fib(x-2);
  }
}

fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が返ってきます。これでちゃんと計算できるし、なにより、フィボナッチ数の定義通りのコードでとても解りやすいです。が、実はものすごい無駄があります。

    return fib(x-1) + fib(x-2);

ここです。たとえば、xが5のときは、fib(4)とfib(3)の両方を計算します。その前者fib(4)の計算では、同様にfib(3)とfib(2)の両方を計算します。fib(3)は、fib(5)の計算でもfib(4)の計算でも、どちらでも計算されます。答えは同じなのに２回計算されます。無駄です。同じ感じに、fib(2)は３回、fib(1)は５回計算されます。超無駄です。xが大きくなるにつれて、この無駄は凄い事になります。


自分のポンコツマシンとOpera9.64でfib(30)を実行してみたところ、結果は1346269で、1秒188msec掛かりました。fib(35)だと結果は14930352で、なんと14秒547も掛かりました。


遅い。なんとかしたい。再帰のところで、もう解ってるfib(x)は最初から計算せずに済ませたい！。ぜんぜん違うコードに書き直せば、出来るかも知れないけど、解りやすいコードがめちゃくちゃになるのも困る＞＜


そこで不動点です。


まず、fibをコードのキモの部分をそのままにして、前回説明した「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を用意してやります。前回で書いた\small Fに当たるものです。

function F_for_fib(f) {
  return function (x) {
    if (x < 2) {
      return 1;
    } else {
      return f(x-1) + f(x-2);
    }
  };
}

これをYに入力すれば、不動点すなわち再帰する関数が得られます。

fib = 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としましょう。

function Ymemo(f) {
  var memo = {};//キャッシュ
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return (function(n){
        if (memo[""+n] == undefined) {//キャッシュにないときだけ、
          memo[""+n] = f(g(g))(n);//まじめに計算してキャッシュに入れる
        }
        return memo[""+n];//結果をキャッシュから返す
      })(m);
    };
  })
}

fib = 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というパズルを解くプログラムを試してみます。

function Hanoi(x,a,b,c) {//パズルの状態を表すオブジェクト
  this.x = x;
  this.a = a;
  this.b = b;
  this.c = c;
}
Hanoi.prototype.toString = function() {//パズルの状態を表すオブジェクトのメソッド(オブジェクトを文字列化)
  return ["{",this.x,":",this.a,":",this.b,":",this.c,"}"].join('');
}

function hanoi(x) {//パズルの解法を文字列で返す関数
  if (x.x==0) {
    return "\n";
  }
  return [hanoi_(new Hanoi(x.x-1,x.a,x.c,x.b)),
          x.x, ":", x.a, x.b, "\n",
          hanoi_(new Hanoi(x.x-1,x.c,x.b,x.a))].join("");
}

hanoi()にパズルの状態Hanoiを入力として渡すと、文字列で解法のステップが返ってきます。Hanoiのプロパティxがパズルの規模を表す値で、a,b,cはパズルで使う３本の棒を表します。


この普通のバージョンを実行したところ、x(パズルの規模)が20の時に23秒515msec、22の時には1分33秒781msec掛かりました。


さきほどのfibと同様に、hanoiをコードのキモの部分をそのままにして、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を用意します。

function F_for_hanoi(f) {
  return function (x) {
    if (x.x==0) {
      return "\n";
    }
    return [f(new Hanoi(x.x-1, x.a, x.c, x.b)),
            x.x, ":", x.a, x.b, "\n",
            f(new Hanoi(x.x-1, x.c, x.b, x.a))].join("");
  }
}

そして、Ymemoに入力して「キャッシュ機構付き再帰」を取得します。

var hanoi = Ymemo(F_for_hanoii);

このYmemoで作った「キャッシュ機構利用版」hanoiを実行したところ、掛かった時間は、x(パズルの規模)が20の時に578msec、22の時には2秒125msecでした。fibほどじゃないですが、40〜50倍は高速化されています。


その2。Yコンビネータへの機能追加をpluggableに


Ymemoでは「メモ化」を直接Yコンビネータに組み込みました。しかし、他の機能も追加する事を考えると、これでは不自由です。ここで色んな機能を追加するための準備として、Yコンビネータと追加機能を分離します。Yコンビネータの方は素のままにしておき、Yコンビネータに渡す「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」の方に仕込みを入れる様にします。

function wrap(F,g) {//仕込みgを組み込んだ「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を返す。
  return function (f){
    return F(g(f));
  };
}

仕込みであるgは、受け取ったfのフリをする関数(fの偽物)を返すようにします。


では仕込みの例として、先ほどYコンビネータに直接組み込んだメモ化機能を、独立した仕込みとして切り出します。

function gen_memorizer() {//メモ化の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  var memo = {};
  return function (f) {
    return function(n){
      if (memo[""+n] == undefined) {
        memo[""+n] = f(n);
      }
      return memo[""+n];
    };
  }
}

これで、素のYコンビネータを機能を仕込んで利用できます。

fib = Y(wrap(F_for_fib, 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が返ってきます。


ハノイの塔の方は、

hanoi = Y(wrap(F_for_hanoi, gen_memorizer()));

です。これもちゃんと動きます。


その3。ホントに動いてる？どう動いてる？ トレース機能の追加

では、メモ化の次に、今度はデバッグ的な機能を追加してみます。


またも安直ですが、トレース機能の仕込み生成関数です。

function gen_tracer() {//トレース機能の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  return function (f) {
    return function(n){
      alert("called with argument: '"+n+"'");
      return f(n);
    };
  }
}

再帰の度に引数を表示します。（ここでは、alertを使って引数を表示しますが、デバッグと言う事でconfirmやpromptを使えば、実行中に変数の値などをユーザが変えてしまうような機能も作れますね）

fib = Y(wrap(F_for_fib, gen_tracer()));
fib(5);

とやると、
called with argument: '5'
called with argument: '4'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '4'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '2'
called with argument: '1'
called with argument: '0'
とダイアログボックスが出てきます。こんな感じに動いてるんですね。


やはり、同じ引数で何度も実行しているようです。では、さっきのメモ化版ではどう動いていたのでしょうか。

その4。複数の機能追加を組み合わせて使う


プラグイン化した追加機能は、組み合わせて使えます。

fib = Y(wrap(wrap(F_for_fib, gen_tracer()), gen_memorizer()));
fib(5);

wrapは、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」に対して、機能を仕込んだ「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を返します。なので、それに対しても同様にwrapで機能を仕込めます。実行結果は以下の通り。

called with argument: '5'
called with argument: '4'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '2'
called with argument: '3'
called with argument: '4'
ずいぶん減ってますね。


もちろん組み合わせた機能も、fibだけじゃなくて、ほかの関数にも使えます。さっきのhanoiに使ってみます。

hanoi = Y(wrap(wrap(F_for_hanoi, gen_tracer()), gen_memorizer()));
hanoi(new Hanoi(5,'A','B','C'));

called with argument: '{4:A:C:B}'
called with argument: '{3:A:B:C}'
called with argument: '{2:A:C:B}'
called with argument: '{1:A:B:C}'
called with argument: '{0:A:C:B}'
called with argument: '{0:C:B:A}'
called with argument: '{1:B:C:A}'
called with argument: '{0:B:A:C}'
called with argument: '{0:A:C:B}'
called with argument: '{2:C:B:A}'
called with argument: '{1:C:A:B}'
called with argument: '{0:C:B:A}'
called with argument: '{0:B:A:C}'
called with argument: '{1:A:B:C}'
called with argument: '{3:B:C:A}'
called with argument: '{2:B:A:C}'
called with argument: '{1:B:C:A}'
called with argument: '{1:C:A:B}'
called with argument: '{2:A:C:B}'
called with argument: '{4:C:B:A}'
called with argument: '{3:C:A:B}'
called with argument: '{2:C:B:A}'
called with argument: '{2:B:A:C}'
called with argument: '{3:A:B:C}'

こんな感じにいくらでも作れる、組み合わせれる、しかも汎用

function 普通の再帰関数(x) {
  中身。「普通の再帰関数」を呼ぶ。
}

を、Yコンビネータに食わせる形の

function 関数を入力として受け取りその関数を使う新しい関数を作って出力する関数(f) {
  return function (x) {
    中身。「普通の再帰関数」の代わりにfを呼ぶ。
  };
}

にしておく事で、再帰に色んな機能をpluggableに追加できるよ、というお話でした。もちろん、機能を追加しないでそのままYコンビネータに入力してただの再帰にも出来ます。いろいろ遊んでみましょう。



以下、作ってみた追加機能を他にもダラダラ挙げてみます。

その5。一部の再帰を勝手にリモートマシンで実行する自動分散実行化機能

天気予報とか大きな規模の計算は、ひとつの「プログラム」*3をたくさんのマシンを使って協調させて走らせます。「プログラム」の方ではマシンの間の通信とかどのマシンで動いているとかはあまり意識せずに書きたいものです。


PCでも一昔前には、SETI@homeとかUDとか、世界中の参加PCを使って計算をするようなプロジェクトもたくさんありました。そんなわけで、弾さんのllevalサーバを利用させてもらって、再帰の実行をリモートに分散させて実行する自動分散化機能を。

function distribute(env, ftext, cond, argstr2exp, retstr2val) {//自動分散実行化の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  var make_uri =  function(n) {
    var envtext = "";
    for (i in env) {
      envtext += env[i] + ";\n";
    }
    n = argstr2exp(n);
    return "http://api.dan.co.jp/lleval.cgi?c=callback&s="
           + encodeURIComponent(envtext+'print(('+ftext+')('+n+'));')
           + "&l=js";
  }
  var read_as_text = function(is) {
    var result = '';
    var reader = new java.io.BufferedReader
               (new java.io.InputStreamReader(is));
    var line = reader.readLine()
    while(line != null){
        result += line;
        line = reader.readLine();
    }
    reader.close();
    return result;
  }
  var f_at_lleval = function(n) {
    var callback = function(a) {
      if (a.status != 0) {
        throw 'Error in lleval: ' + a.status + ' : ' + a.stdout +' : ' + a.stderr;
      }
      return a.stdout;
    }
    var conn = new java.net.URL(make_uri(n)).openConnection();
    conn.connect();
    if (conn.getResponseCode() != 200) {
      throw 'Error! : ' + getResponseCode();
    }
    var resultout = eval(read_as_text(conn.getInputStream()));
    return retstr2val(resultout)
  }
  return function (f) {//これが「受け取ったfのフリをする関数(fの偽物)」
    return function(n){
      if (cond(n)) {
        return f_at_lleval(n);
      } else {
        return f(n);
      }
    };
  }
}


ブラウザだとクロスドメイン制約のせいでうまくいかないので、Rhinoで動かします。ブラウザで動かないのは残念ですが、Rhinoでなくても、また中身的にはJavaScriptでなくても通信が出来る普通の言語環境なら問題ないですしErlangとかならお茶の子さいさいでエレガントに書けると思います*4。



こんな感じで実行します。

hanoi = Y(wrap(F_for_hanoi, 
          distribute(
            [Y, F_for_hanoi, Hanoi, 'Hanoi.prototype.toString='+Hanoi.prototype.toString],//env:実行環境情報(リモートに送る)
            'Y(F_for_hanoi)',//ftext:リモートで実行する関数
            function(n){return n.x%2==0;}, //cond:偶数番目を弾さんサーバで実行。奇数はローカル実行
            function(n){return 'new Hanoi('+n.x+',"'+n.a+'","'+n.b+'","'+n.c+'")';},//argstr2exp:リモートに渡す引数値を送信できる形式に変換
            function(n){return n;}//retstr2val:リモートからの返却結果を値に変換(hanoiだと変換不要なので意味はない)
         )));
hanoi(new Hanoi(5,'A','B','C'));

その6。先読み山かけ先行実行(speculative evaluation:投機的実行) 機能

function gen_speculative(vent){//先読み山かけ先行実行の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  return function (f) {
    var make_f_caller = function(n) {
      return function() {
        f(n);
      }
    }
    var executor = java.util.concurrent
      .Executors.newCachedThreadPool();//spawnは激遅だった
    return function(n) {
      var forecasts = vent(n);
      for (var i in forecasts) {
        executor.execute(make_f_caller(forecasts[i]));
      }
      return f(n);
    };
  }
}

必要になると思われる再帰を、先取りして実行しておく機能です。wikipedia:投機的実行を見てください。メモ化機能と組み合わせて使います。最近のCPUのようにコアがたくさんあるマシンだと速くなるかも知れません。または、自動分散実行化機能と組み合わせてもいいかも知れません。


というわけで、Haskellやろうぜ！(おまけ)


落ち着いてみてみると、再帰というのはじつは「関数を入力として受け取りその関数を使う」関数の、特殊な場合という事が解ります。たまたま(?)入力されてきたのが自分自身だった場合が再帰というわけです。実際のところ、Yコンビネータじゃなくて単なる再帰の方が速いので自分はプロダクションコードで実際に使った事はないです。でも、目の前の状況しか考えてないコードよりも、一般的な形に書いておいた方が、ものすごく可能性が広がるという事を実感できれば、お仕事にも意味があるかなぁと思います。


関数型言語では、この考え方が徹底していて、ライブラリなんかももの凄い汎用的にできてます。それは単に文化だけでなく、関数型言語のパワーのおかげでもあります。


例えば、上記の再帰への機能追加関数達ですが、構造が似ていますね。これもちゃんとした関数型言語プログラマなら汎用的な関数を用意してしまうでしょう(自分は全然ちゃんとしてないので気持ち悪さに耐えてしまいました)。関数型言語では、処理(関数)を普通に気軽に後から渡してやれるし、数学の関数の様に縦横無尽に組み合わせやすいので、コードのありがちな構造自体すらライブラリ化できてしまうのです。


例えば、Haskellではfibを多分ふつうはこんな感じに書きます。Haskellではここで使ってる関数はみんなデフォルトでimportも不要で使えます。

fibs = 0:1:(zipWith (+) fibs (tail fibs))
fib = (fibs !!)

イメージを伝えるために上記をJavaScriptに翻訳すると、

var fibs = cons(0, cons(1, zipWith(plus, fibs, fibs.tail)))
var fib = function(n){return at(n, fibs).head;}

こんな感じです。使ってる関数は、JavaScriptにはないので、それらも翻訳するとだいたいこんな感じです。

function cons(h,t) {
  return {head:h, tail:t};
}
function plus(a,b) {
  return a + b;
}
function zipWith(op, xs, ys) {
  if (xs.tail && ys.tail) {
    return cons(op(xs.head, ys.head), zipWith(op, xs.tail, ys.tail));
  } else {
    return cons(op(xs.head, ys.head), undefined);
  }
}
function at(n, xs) {
  if (n==0) {
    return xs.head;
  } else {
    return at(n-1, xs.tail);
  }
}

zipWithが構造自体をライブラリ化したものの例と言えると思います。何か同じ計算を沢山のデータに対して行う、というありがちなパターンのプログラムの構造を、関数としてライブラリ化してある訳です。JavaScriptは関数をファーストクラスが扱える(関数を関数のまま引数に渡したり出来る)ので、言語としては上記のように関数型のプログラミングも可能です。ただ、こういう使われ方を想定してないので、こういうライブラリを探して*5きてさらに実行時環境にも用意してやり、そう言うコーディングするあなたを変態と呼ぶ心無い人に耐えられればＯＫです。しかし、関数をそのように扱えない言語だと、こういうやり方をするために、かえっていろんな無駄な記述が必要になっり、トリッキーなテクニックが必要になってしまいます。


あと、JavaScirptの例ではfibsの所が関数じゃなくてただの値なのにfibs自身を参照していてエラーになってしまうと思います。Haskellでは、データ自体でも問題なく自己参照が出来ます。さらに、fibsは長さ無限ですが、Haskellは、プログラムの必要になった部分だけを必要になってから評価(実行)するのでノープロブレムです。


さらに、エントリの冒頭に書いたように、数学(主に基礎論系。)との対応付けもよくなされていて、何気ないライブラリが数学的に証明されているもの凄い汎用性とパワーを持っていたりします。超汎用的なライブラリをちょこちょこと組み合わせるだけで、どんどん高度なプログラムが出来ていきます。モジュールを組み合わせてさらにモジュールを作るようにプログラミングしていけば、プログラムの機能は、コードの規模にたいして、足し算ではなく、掛け算的に広がっていきます。上記のfibもずいぶん短く書けていますが、大きなプログラムになればなるほど差は倍々に広がっていきます。


この感覚というか習慣は、関数型言語を使う事で最もよく培われて最もよくパワーを発揮すると思いますが、JavaなりPHPなりでのコーディングにも必ず良い影響をもたらすと思います。目の前の状況しか考えてないコードよりも、一般的な形に書いておいた方が、ものすごく可能性が広がるという事自体は、どの言語でも同じだからです。そんなわけで、実用系関数型言語の極北(??)、Haskellの本を紹介しておきます。


ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門
ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門
posted with amazlet at 09.04.17
青木 峰郎
ソフトバンククリエイティブ
売り上げランキング: 68076
Amazon.co.jp で詳細を見る


WebにHaskellの情報は結構ありますが、玄人向けです。「やさしいHaskell入門(A Gentle Introduction to Haskell)」というドキュメントがありますが、これは「天才な人にはやさしい」という意味なので気を付けて下さい。ふつうの人には、この本がふつうの意味でやさしいくていい感じです。興味が湧いた人は、まずこの本を読む事をお勧めします。


偉そうな事を書きましたが、自分は真性のへなちょこなので、玄人がこのエントリを見たら炊飯ものだと思います*6。それでも、仲間が増えて欲しいという思いであえて恥をさらさせて貰います。

追記

Haskell版fibの定義で、当初カッコが抜けていたのを修正しました。(2009-04-24)

*1:オリジナルは名前空間汚染を回避していますが、ここでは気にしていません。あしからず。あと、本当はZコンビネータと言うのでしょうが、不動点演算子なら別によいのです

*2:ご存じでない方はググってください、すみません

*3:一本のソースという意味ではなくて、ひとつの目的のひとつのまとまりという意味で

*4:自分は使った事無いですが…

*5:または自分で書いて

*6:間違いにはツッコミを頂けたら幸いです