YコンビネータとZコンビネータという魔法

↑で「ループも関数で表現」とか書いたのですが、これをやるにはYコンビネータとそれを拡張させたZコンビネータというものが必要になってきます。詳しい話はものの本とかもっと詳しいサイトがあると思うのでそちらを参照していただくとして、ものすごく乱暴にいってしまうととりあえずは「終了条件を仕込ませた関数を返す関数を引数にとってループをつくる関数」といってもいいかもしれません。このYコンビネータとZコンビネータのGroovyクロージャでの表現を拝借させていただきます。

Yコンビネータ

def Y = {f->{x-> f(x(x))}({x->f(x(x))})}

Zコンビネータ

def Z = {f-> 
  {x-> 
    {m-> f(x(x))(m)}
  }({x-> {m-> f(x(x))(m)}})
}

このZコンビネータをつかって先日のフィボナッチ数を求めるメソッドをつかって実行するとこんなかんじになります。

//Zコンビネータ
def Z = {f-> 
  {x-> 
    {m-> f(x(x))(m)}
  }({x-> {m-> f(x(x))(m)}})
}

//クロージャを返すクロージャ。fは自分だよ
def ret_fib = {f->
  return {n-> (n==0)? 1 : (n==1)? 1 : f(n-1)+f(n-2)}
}

println Z(ret_fib)(10)

なんでこんなことしてるんだろうって思いますよね、じぶんでもそう思います。
しかし実は「ループを制御構文として用意されたものを使わずに、関数(クロージャ)で表現することによって制御構文でのループという機能をユーザレベルで拡張できる」という利点があるわけです。

Zコンビネータにこちらの記事を参考にキャッシュ機能をつけてみます。

//キャッシュ機能つきZコンビネータ
def mem = new HashMap()
def memZ = {f->
  {x-> 
    {m-> f(x(x))(m)}
  }({x-> 
      {m->
        {n->
          if(mem[n.toString()]==null){
            mem[n.toString()] = f(x(x))(n)
          }
          mem[n.toString()]
        }(m)
      }
  })
}

println memZ(ret_fib)(10)

するとどうなるか。先日gparsでつかったfib(40)のベンチをとってみます。

def s1 = System.currentTimeMillis()
println "ans: "+Z(ret_fib)(40)
println "ふつうにZコンビネータで計算: ${((System.currentTimeMillis()-s1)/1000)} sec"

def s2 = System.currentTimeMillis()
println "ans: "+memZ(ret_fib)(40)
println "キャッシュつきZコンビネータで計算: ${((System.currentTimeMillis()-s2)/1000)} sec"

結果は…

ans: 165580141
ふつうにZコンビネータで計算: 61.535 sec
ans: 165580141
キャッシュつきZコンビネータで計算: 0.014 sec

すげーw 考えてみれば当然ちゃ当然で再帰で呼ぶのをキャッシュしてそのぶんの計算回数が減るからこうなるのは当然ですよね。一般的に関数指向の言語ではこのような仕掛けをするのにあたってYコンビネータ(Zコンビネータ)が使われることもありますよってことです。