Yコンビネータによる無名再帰をRubyで理解する

アンダースタンディングコンピュテーション180ページでは、Yコンビネータ（Zコンビネータ）によって無名再帰を実装している。

が、詳しい説明が省かれているので、Wikipediaの不動点コンビネータの例をRubyで書いて理解してみる。

まず普通に再帰を使って、階乗を実装する。

Fac = -> x {
  if x.zero?
    1
  else
    x * Fac[x-1]
  end
}

このコードは次のように書き直しても同じである。

Fac = -> x { U[Fac, x] }

U = -> (f, x) {
  if x.zero?
    1
  else
    x * f[x-1]
  end
}

さらにUをカリー化して、次のようにしても同じ。

Fac = -> x { V[Fac][x] }

V = -> f {
  -> x {
    if x.zero?
      1
    else
      x * f[x-1]
    end
  }
}

ここで Fac に注目すると、引数を省けば、次のような構造になっている。

Fac = V[Fac]

実際には引数の評価を遅延しないと動作しないが、これはVに対する不動点の定義そのものである。

よって不動点コンビネータでVの不動点を求めれば、それがFacと同じものになる。

f2 = Z[V]

まとめて書けば次の通り。

Fac = Z[-> f {
  -> x {
    if x.zero?
      1
    else
      x * f[x-1]
    end
  }
}]

tkykmw code