「switch文を使いたくないばかりに」のその後

以前「code avant-garde - ものすごいハイウエスト日記」というものを書いたのですが、そのあといろいろ考えてみると結局じぶんがやろうとしてたことってラムダ計算なんだな、ということに気づきました。

ものすごく乱暴ないいかたをしてしまうとラムダ計算とは「すべてを1つの引数の関数で表現してしまう」というハードコアなものです。これをプログラムってステージで話をすると「変数の扱いも関数で表現」「条件分岐も関数で表現」「ループも関数で表現」「数値なんかも関数で表現」「もつのろんオブジェクトという概念も関数で表現」etc... とありとあらゆるものを関数で表現するということになります。半世紀以上前に生まれたlispは生まれたそのときからこの性質を持ち、closとかmacroというものに生かしてきたわけで、じぶんの性質を利用して言語仕様そのものをアップデートさせてきたわけです。そりゃLOL本で「lispは世界で最も過激な言語」とかいっちゃいますよね。

というわけで「関数ですべてを表現」ということは「クロージャでもすべてを表現できるのでは」と思っていたところ、とてもすばらしい記事を発見しましたよ。

2009-04-09

Groovyのクロージャを使ってラムダ計算の説明をされていて、すごく分かりやすいです。この記事を読ませていただき「あ、おれってこれやりたかったんじゃないのかな」と思ったわけですね。

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コンビネータ)が使われることもありますよってことです。

やっとgroovyの話です

ただこれまで書いたことがGroovyで有効に使えるかといったら、それはNOだと思います。よく考えてみるとクロージャをネストさせればそのぶんの無名クロージャオブジェクトが生成されるコストがかかるはずなので、純粋関数型な言語でなければYコンビネータやらZコンビネータをGroovyクロージャでやるのはあんまりメリットが感じられないからです。

Groovyらしくクロージャをつかって、キャッシュ機能をもりこんでおなじものをやるならこんなかんじになるのではと思います。

def cached_fib = {
  def cache = new HashMap()
  return {n->
    if(n==0 || n==1){
      return 1
    }else{
      if(cache[(n-1).toString()]==null){
        cache[(n-1).toString()] = call(n-1)
      }
      if(cache[(n-2).toString()]==null){
        cache[(n-2).toString()] = call(n-2)
      }
      return cache[(n-1).toString()]+cache[(n-2).toString()]
    }
  }
}()

def s3 = System.currentTimeMillis()
println "ans: "+cached_fib(40)
println "キャッシュつき再帰クロージャ: ${((System.currentTimeMillis()-s3)/1000)} sec"

実行してみると…

ans: 165580141
キャッシュつき再帰クロージャ: 0.003 sec

もう笑うしかないですね。

で結局なにがいいたいのか

自分自身に対して客観的アドヴァイス+反省。

「並列処理するまえに実際のコードをリファクタりましょう」ってこと。
並列でスレッドを動かしても、ひとつの計算に時間がかかってしまっては何の意味もありません。

それと「関数指向」について耳にする機会が多い昨今ですが「関数思考」でいきましょうってこと。
「関数指向」がすべてを解決してくれるものではなく、「関数思考」で考えたことをその環境に落しこみましょうってこと。
↑でやったfib(40)の結果がすべてを語ってる。Groovyらしいクロージャの使いかたが一番高速だったことが何よりの証拠。

ということを踏まえたうえで、gparsをいじりたいと思います。