2009年04月17日

PythonによるYコンビネータの仕組みの(多分)わかりやすい説明

 lambdaを使っててどうも気になるのが、ループ(再帰)するために一時的に関数に名前をつけなければならないところだ。
 一時的なローカル変数が簡単に設定できる言語ならともかく、Pythonではそれも結構面倒だ。
 ところが、つらつらとネットを探していくと、妙なモノを発見。
 『Yコンビネータ(Y combinator)』とか『不動点コンビネータ (fixed point combinator)』あるいは『不動点演算子』とか呼ばれるモノで、コレを使うと、どうやら関数に名前を付けなくとも再帰できるという代物らしい。
 喜びいさんで見てみたが……書けはしたものの、理解するのに苦労した。
 今回はその解説を、私のようにλ表記になじみの無い人でもわかるように、基本的に一般の関数式とPython式で書いてみることにした。
 さらに、同じ式を2回書いて、次にドコにドコを適用させるかを色分けし、その結果も色分けして書いてみた。

Yコンビネータというのは、簡単に言えば
	Y(f) = f(Y(f))
となる関数である。
 fには、再帰する関数の定義を書いておく。
 ただしその名前は、外側にもう一重、余分にlambdaを咬ませて、引数として与えておく。
 例えば、簡単な再帰の例に一番よく使われる階乗計算は、通常、以下のように定義できる。
	fuct = lambda n: n if n < 2 else fuct(n - 1) * n
 ちなみに最初は面倒なので、末尾再帰とかにしていない。
 ここで、fuctという名前が使われているので、コレをlambdaにくるんでなくしてしまう。
	lambda f: lambda n: n if n < 2 else f(n - 1) * n
 このままでは再帰は不可能だ。
 仮に、
	F = lambda f: lambda n: n if n < 2 else f(n - 1) * n
	N = lambda n: n if n < 2 else f(n - 1) * n
とすると、Fに引数としてNを与えてやらなければならない ⇒ F(N)
 しかし、そのNの中で、fが呼び出されているのだが、Nからは自らがどのような名前で呼ばれているのか、当然判らない。
 よって、Nの中のfは、何を指しているのかわからない、ということになる。
 勿論、Nの中でfではなくNとすれば話は解決するが、元に戻るだけだ(fuctがNになっただけ。
 ここでYコンビネータの登場である。
 YコンビネータYにFを適用すると、以下のようになる。
	Y(F) = F(Y(F))
 つまり、Fの入れ子構造になり、Fの引数としてFが渡されていることになるので、F自身を参照することが出来る。
 ここで、λ式によるYコンビネータの式を書いてみる。
	Y=λf.(λx.f(xx))(λx.f(xx))
 λ式をPythonの式に翻訳するのは、大体こんな感じ(Mはxに関する式。
	λ式             λx.M
	Python          lambda x: M
 ただし、fxはf(x)を意味するので注意(Pythonでは括弧が必要。

 ちなみに、Yコンビネータが本当にそうなるか、を一行ずつ見ていこう。
	Y = λf.(λx.f(xx))(λx.f(xx))
で、
   Y(F) = (λf.(λx.f(xx))(λx.f(xx)))(F)
        = (λf.(λx.f(xx))(λx.f(xx)))(F)
        = (λx.F(xx))(λx.F(xx))
        = (λx.F(xx))(λx.F(xx))	……(1)
        = (λx.F(xx))(λx.F(xx))	……λx.F(xx) → x
        = F((λx.F(xx))(λx.F(xx)))
        = F((λx.F(xx))(λx.F(xx)))
        = F(Y(F))			……(1)より
 これを踏まえて、Yコンビネータの式を素直にPython式にすると、以下のようになる。
	Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))
 ただしコレを実行すると、スタックオーバーフローになる。
>>> Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))
>>> F = lambda f: lambda n: n if n < 2 else f(n - 1) * n
>>> Y(F)(5)
  File "<stdin>", line 1, in <lambda>
(...)
  File "<stdin>", line 1, in <lambda>
RuntimeError: maximum recursion depth exceeded
>>>
 簡単に言えば、最後の引数を適用する前に、関数部分の全ての構造を展開しようとして失敗している、ということだ。
 Yコンビネータ自体は再帰構造となっている。
 どこかで式が完成して止まらなければ、いつまでも動き続ける。
 よって、どこかで連鎖を止めて、最後の引数を取るように細工しなければならない。
 PythonによるYコンビネータの完全な定義は以下の通り。
Y = lambda f: (
    lambda x: lambda m: f(x(x))(m)
  )(
    lambda x: lambda m: f(x(x))(m)
  )
 これを関数Fに適用して、実際に数値を与えてみると、確実に計算しているのが確認できる。
>>> F = lambda f: lambda n: n if n < 2 else f(n - 1) * n
>>> Y = lambda f: (lambda x: lambda m: f(x(x))(m))(lambda x: lambda m: f(x(x))(m))
>>> Y(F)(5)
120
>>> Y(F)(10)
3628800
>>>
 関数FにYを適用させ、引数としてNを与えた時の内部は以下の通り。
Y(F)(N)=(lambda f:(lambda x:lambda m:f(x(x))(m))(lambda x:lambda m:f(x(x))(m)))(F)(N)
       =((lambda x:lambda m:F(x(x))(m))(lambda x:lambda m:F(x(x))(m)))(N)
       =((lambda x:lambda m:F(x(x))(m))(lambda x:lambda m:F(x(x))(m)))(N)	……(1)
※lambda x:lambda m:F(x(x))(m) → x
       =((lambda x:lambda m:F(x(x))(m))(lambda x:lambda m:F(x(x))(m)))(N)
       =(lambda m:F((lambda x:lambda m:F(x(x))(m))(lambda x:lambda m:F(x(x))(m)))(m))(N)
N → m
       =(lambda m:F((lambda x:lambda m:F(x(x))(m))(lambda x:lambda m:F(x(x))(m)))(m))(N)
       =F((lambda x:lambda m:F(x(x))(m))(lambda x:lambda m:F(x(x))(m)))(N)
       =F((lambda x:lambda m:F(x(x))(m))(lambda x:lambda m:F(x(x))(m)))(N)
       =F(Y(F))(N)	……(1)より
 うまくF(Y(F))(N)の形に展開できているのがわかる。
 さて、Fを実際に適用して、うまくいくか確かめてみよう。
 ここで、話を簡単にするために、U = Y(F)としておく。
F = lambda f: lambda n: n if n < 2 else f(n - 1) * n
F(U)(N)=(lambda f:lambda n: n if n<2 else f(n-1) * n)(U)(N)
       =(lambda n: n if n<2 else U(n-1) * n)(N)
       =(lambda n: n if n<2 else U(n-1) * n)(N)
       =N if N<2 else U(N-1) * N
 しっかりと再帰と同じパターンになっていることがわかるだろう。
 同じものをdefを使って、重複部分を短くしようとすると、以下のようになる。
	def Y2(f):
	  y = lambda: lambda x: lambda m: f(x(x))(m)
	  return y()(y())
 もし、これを以下のように定義すると、エラーとなる。
	def Yx(f):
	  y = lambda x: lambda m: f(g(g))(m)
	  return y(y)
 理由は、戻り値のところでyを確定しようとしてしまうためである。
 それを防ぐため、λ式でくくって遅延評価を行う必要が出てくる。
 さて、def版も、実際動かして確認してみよう。
>>> def Y2(f):
...   y = lambda: lambda x: lambda m: f(x(x))(m)
...   return y()(y())
...
>>> Y2(F)(5)
120
>>> Y2(F)(10)
3628800
>>>
 Yコンビネータはlambda式で書けるので、要するに再帰を行うのに一切名前を使わずに書くことが出来る、ということだ。
 ただし、実際書いてみればわかるが、必要以上にウザい。
 中に書く関数に名前を付けたのは説明のためであって、こちらはlambdaで書くのが普通だろうが、再利用可能なYコンビネータまでlambdaで書く必要は無いだろう。
 ……とか思っていたら、実際書いたのがあった。
 まぁ、参考までに階乗のlambda版を書いてみよう。
(lambda f:
  (lambda x:
    lambda m: f(x(x))(m)
  )(lambda x:
    lambda m: f(x(x))(m)
  )
)(
  lambda f:
    lambda n: n if n < 2 else f(n - 1) * n
)(5)

 私は完璧なワンライナではないので、コレが良いのか悪いのかの判断は、読んだ方にお任せしよう。

 さて、思いつく限りの手段を使って判りやすく書いてみたつもりだが、いかがだっただろうか。
 色分け……面倒だったなぁ……(できれば、二度とやりたくない…)

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/kikwai/51587001