Yコンビネータ

Y Combinator といえば Paul Graham ですが、それはおいといて。

「関数 f を取って、f の不動点を返す」コンビネータです。

Y f = f (Y f) と大変シンプルな仕様なのに、
eager な評価戦略の下だとその中身は↓こんな実装になる

  ; Y combinator in Scheme
  (lambda (f)
    ((lambda (proc)
       (f (lambda (arg) ((proc proc) arg))))
     (lambda (proc)
       (f (lambda (arg) ((proc proc) arg))))))

上の式だけ見ても頭の中でパースするのすら難しいけれど、
こちらを見ると、どうやってこれが出てくるかがわかる。
fの不動点は(λx.f(xx))(λx.f(xx))と書きたいところだが、
xをfの中で評価するために η-expansion *1を使ってfreezingしてるわけか。
手動で遅延評価っぽいことを書く必要があるのね。

これがあると
　再帰関数 g(x) = e　 (e の中で g を使用)
を (Y λgλx. e) と書ける。

*1:関数 f にλ抽象を一枚被せて (λx.f x) にする。η-reduction の逆