Yコンビネータのお話

JavaScript

過去にもいろいろなブログで何度も取り上げられて話題になりましたが、自分なりの理解で書いてみました。Yコンビネータはシンプルでありながら、不思議で奥が深いので興味をそそる要素があるのでしょう。

JavaScriptも広い意味では関数型言語であり、λ計算とほぼ同等のものが表現できます。λ計算による再帰的関数定義で登場するYコンビネータのJavaScriptでの実装について簡単にメモしておきます。

唐突ですが、JavaScriptで再帰的階乗計算factは以下のように定義されます。

function fact(n) {
  return n == 0 ? 1 : n * fact(n - 1);
}


関数オブジェクトを陽にあらわすと、これは

var fact = function (n) {
  return n === 0 ? 1 : n * fact(n - 1);
};


とほぼ同等です。しかし、関数の中のfactは関数の外の変数factを参照しているため、その変数の値は自由に書き換えることができるため問題です。いま、関数本体でそのような自由変数を使わないで再帰関数を定義できるかどうかを検討してみましょう。つまり、無名関数オブジェクトとして閉じたもので再帰関数オブジェクトが実現できるかどうかです。自由変数を使わないようにすればよいので、fact という変数を関数の引数にして、上のfact関数を返す関数gfactを以下のように定義します。

var gfact = function (fn) {
  return function (n) {
    return n == 0 ? 1 : n * fn(n - 1);
  }
};

このgfactと上のfactを使うと gfact(fact) の 結果は factを計算する関数を返すことがわかります。そして、gfact(fact)(10)は 10の階乗を返します。しかし、ここではまだfactが自由変数として出現していますが、そのfactを使わないで gfactだけでこのようなことが可能かどうかを検討します。いま、仮に、Y(gfact) = factとなるような関数Yが存在すると仮定します。すると、

gfact(fact) = fact
Y(gfact) = fact

から

Y(gfact) = gfact(Y(gfact))

が成立します。つまり、関数Yは

Y(gfact) = gfact(Y(gfact))

という性質を満たしていなければならないことになります。これは、gfactはY(gfact)の不動点であることを意味しています。つまり、

gfact(gfact(gfact(gfact(.......Y(gfact))))) = Y(gfact)

のような式が成り立ちます。こんな関数Yが存在するなんて直感的には信じられませんが、Haskell Curryがそのような関数を最初に発見しています。実は、このような不動点関数は無数にあることがわかっています。そのような関数のうち一番シンプルなものがYコンビネータです。

λ式を使うと、Yコンビネータは

Y = λf.(λx.f (x x))(λx.f (x x))

と定義できます。

このYは任意の関数Fについて

Y F = F (Y F)

が成立しています。λ計算で簡単に証明しておきましょう。

Y F = λf.(λx.f (x x))(λx.f (x x)) F
    = (λx.F (x x))(λx.F (x x))
    = F (λx.F (x x))(λx.F (x x))
    = F λf.(λx.f (x x))(λx.f (x x)) F
    = F (Y F)


上でλ式で定義したYをそのままJavaScriptで書くと以下のようになります。

var Y = function(f) {
  return (function(x){ return f(function(a){ return x(x)(a);});})
         (function(x){ return f(function(a){ return x(x)(a);});});
};

一番外の return は return F(F) という形式です。またFの中にもx(x) という形式が存在しています。つまり、自分自身に自分自身を適用するという形式が入れ子になった一種のフラクタル構造になっています。構文木を図示するとYという形になるからYコンビネータと呼ばれています。Yの中にYが含まれるフラクタル樹形図です。

普通の関数定義を使って分かりやすく書くと、下記のようになりますが、ますますわけが分からなくなります。

function Y(f) {
  function g(x) {
    function h(a) {
      return x(x)(a);
    }
    return f(h);
  }
  return g(g);
}

果たして、実際に動作するか確認してみます。

var x = Y(gfact)(10);

の結果は、確かに 10の階乗になり、

var x = gfact(gfact(gfact(gfact(gfact(Y(gfact))))))(10);

の結果も確かに 10の階乗になりました。

念のためフィボナッチ計算も確認してみましょう。

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

var fib = Y(gfib);
for (var i = 0; i < 15; i++) {
  print("fib(" + i + ")=" + fib(i));
}

結果は以下のようになりました。正しいようです。

fib(0)=0
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(8)=21
fib(9)=34
fib(10)=55
fib(11)=89
fib(12)=144
fib(13)=233
fib(14)=377


ちなみに、一般にYコンビネータは強い意味での型はないので、HaskellやMLでそのまま書くと型推論に失敗します。Haskellでは Yは以下のように記述できます。関数は小文字で始まるのでy、またデータ型を再帰させています。これは y f = f y f と書いたのと意味的に同じです。

newtype T a = Rec { rec :: T a -> a }
y :: (a -> a) -> a
y f = g (Rec g)
  where g x = f (rec x x)

gfact = \f n -> if (n == 0) then 1 else n * f(n - 1)

y gfact 10 で確かに3628800が得られました。


このようにYコンビネータを使うと、無名関数の再帰関数が定義できます。もっともJavaScriptでは自分自身の関数を arguments.callee で参照できるため、このような必要はありません。また、無名関数にその関数内だけで有効な名前を付けることができる(JScriptではこれが異なる動作になる)ので、Yコンビネータが必要になることはまずはありません。しかし、再帰関数の最小不動点意味論において、非常に重要なものです。