Yコンビネータメモ

Y コンビネータって何？ - IT戦記

↑僕も理解したくなったけど、理解には時間がかかった。
いや、理解しきれてないけど。
とりあえず自分が理解できたと思えたことを
忘れないようにするためにメモを残しておく。
（って思って書き始めたけど、Wikipediaのλ計算の解説がよさげ）

1. Yコンビネータってそもそも何？

λ計算で再帰を表現するために導入する関数
λ計算だと関数定義内で自分自身をシンプルには表現できないから。

2. Yコンビネータはどんな働きをする？

言葉だと簡潔に書けないので具体例で。

// YがYコンビネータとすると、
var fib = Y(function(F){return(
  //                 ↑このFが↓のfunction自身を表す
  // ↓ここに書いたfunctionが作りたい再帰処理関数の内部動作になる（ここではフィボナッチ数を返す関数）
  //   内部動作を記述するときに自分自身は↑の引数のFを使えばOK
  function(n){
    return (n <= 2) ? 1:(F(n-2)+F(n-1));
  }
)});
fib(4); // 3

// Yコンビネータ
function Y(f) {
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })
}

3. Yコンビネータはどうしてそう動いてくれるのか

Y コンビネータって何？ - IT戦記

↑ここで提示されたYコンビネータの中間形態を見てみる
（何で最終形じゃなくて中間形態かというと、中間形態のほうが読みやすいから）
（最終形にするには式の入れ替えをしていけばいいから、思考上は同じ意義があると思ってそうした）

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

↑の関数がYコンビネータ（と同じ動作をするλ式じゃない表現）。

fは上で示した2の例でいうと

function(F){return(
  function(n){
    return (n <= 2) ? 1:(F(n-2)+F(n-1));
  }
)}

この部分で、Yコンビネータの引数になる関数。

問題はg。

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

これが理解できれば、Yコンビネータの動作原理も理解できそう。
fは関数を引数にとったら、とりあえず再帰処理したい関数を返してくれる。たとえ引数にとる関数がわけのわからないものだとしても、だ。
だからここはとりあえずg自体がどんな処理をするのかは忘れて考えてみることにして、最初のフィボナッチ数関数を例に挙げて実際の動作手順を追ってみる。

たとえばg(3)を実行させると、
f(g)(3)を返す。
f(g)は、gがなんだろうと以下の関数を返してくれる

function(n){
  return  (n <= 2) ? 1:(g(n-2)+g(n-1))
};

ということはつまりf(g)(3)は

(function(n){
  return  (n <= 2) ? 1:(g(n-2)+g(n-1))
})(3)

だ。
実行すると
g(3-2)+g(3-1) => g(1)+g(2)
になる。
元にもどって、gは何だったかというと

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

だから、

g(1)+g(2)

は

(function(n){
  return  (n <= 2) ? 1:(g(n-2)+g(n-1))
})(1)
+
(function(2){
  return  (n <= 2) ? 1:(g(n-2)+g(n-1))
})(1)

実行すると
1+1 => 2
なるほどねー

function g(m){
  f(g)(m)
}

ってところで？？？ってなっちゃうけど、
要はこれで再帰を実現してるんだな。
ってそりゃそうか、gの定義でgを使ってるんだから、それすなわち再帰だわなぁ。

ってことはやっぱりYコンビネータは中間表現で納得してちゃダメなのかな。
λ式におとす練習をしておこう（ほとんどid:amachangのをなぞってるだけだけど。。。）
関数の引数以外に名前がない形になることを目標にしていけばよいってことかな。

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

↓ 定義の仕方を変える

function(f){
  var g = function(m){
   return f(g)(m);
  };
  return g(m);
}

↓ gを無名関数にして、それを返す関数g2を定義して、それを実行するように

function(f){
  var g2 = function(){
   return function(m){
     return f(g2())(m);
   };
  };
  return g2();
}

↓ 中で呼び出しているg2は引数で渡すことにする。それにともなって名前をg3に変更

function(f){
  var g3 = function(g3){
   return function(m){
     return f(g3(g3))(m); // →g3は呼び出すとき引数にg3が必要になるから
                          //   g3() じゃなくて g3(g3)
   };
  };
  return g3(g3);
}

↓g3を無名関数にして、g3(g3)のところも置き換え

function(f){
  return (function(g3){
   return function(m){
     return f(g3(g3))(m);
   };
  })(function(g3){
   return function(m){
     return f(g3(g3))(m);
   };
  });
}

↓g3の名前をgにする

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

引数をmにしてるのはλ式チックに引数はひとつにするため。
再帰呼び出し定義用につかうならargumentsを渡すようにしてもいいかも
カリー化ができるなら引数を書かずにすむんだけども。
# あ、javascriptより他の関数型言語（もしくはλ式）のほうがキレイにかけるってことか。
# javascriptで考えると引数が余計で混乱しやすいかも？

function(f){
  return (function(g){
    return function(){
      return f(g(g)).apply(null, arguments);
   };
  })(function(g){
   return function(){
     return f(g(g)).apply(null, arguments);
   };
  });
}

Yコンビネータがどうして動くのかはわかったけど

自分で何もないところからYコンビネータ相当のものをつくってみろ、と言われても厳しいだろうなぁ。
でもλ式を考えるようなことをしてる人ならヒョイっと出せるのかもしれないと思ったり。

ところで

Firefoxで、ページ内のJavaScriptでフィボナッチ数関数を再帰で定義して実行すると、引数が10を越えたあたりぐらいからスタックがえらいことになってスクリプト停止しない？ダイアログが出てきてしまいます。
↓こんな感じで途中の計算結果を覚えておくようにすると、スタックがえらいことにならずにすんでfib(100)とかでもさくさく結果をだしてくれるようになりました（Firebugで試したらfib(1000)でtoo much recursionって出ました）。
あ、1000回recursionしたらメッセージ出す仕様ってことだったりして。

var memo = {}; // 結果記憶用
var fib = Y(function(F){return(
  function(n){
    if(n in memo)return memo[n]; // 記憶してたらそれを使う
    return  memo[n] = (n <= 2) ? 1:(F(n-2)+F(n-1));
  }
)});

fib(100);

// Yコンビネータ
function Y(f){
  return (function(g){
    return function(){
      return f(g(g)).apply(null, arguments);
   };
  })(function(g){
   return function(){
     return f(g(g)).apply(null, arguments);
   };
  });
}