正木です。
何やら面白そうな話なので良く分からないながら興味深く読ませていただき
ました。
不動点定理の適用の所で少し引っかかる所があります。

|[ruby-list:35060] Re: Y Combinator
|From: sinara / blade.nagaokaut.ac.jp

|そして、これを Proc に当てはめます。ここからはかなりいい加減な話で
|す。今、不動点定理で、F = V = Proc と思います。そして、a の定義を
|
|  a(x, y) = x[y]
|
|とおくと、これは定理の条件を満たします。なぜなら、任意の
|
|  h: Proc -> Proc
|
|に対して f0 = h とおけば a(f0, f) = f0[f] = h[f] だからです。

ここの所で Proc の要素は同時に
Proc**Proc={ f | f: Proc -> Proc }
の要素になっていて、その逆も成り立つことを仮定しているように読めます:
Proc**Proc = Proc
これは Proc が2個以上の要素を持つ限り有り得ないことですが、
この辺の事情はどうなっていますか?

lambda 式では、無名関数の再帰定義がそんなに大変だとは知りませんでした。
しかし良く考えると、それができることの方が不思議なことかもしれません。

ちなみに Ruby では、次のようにすれば 関数定義の中で self がその関数自身を
指すようにすることができます。

class Function
  def initialize(hash={},*parameter)
    @hash=hash
    @para=parameter
    @lambda=eval "lambda{"+yield+"}"
  end
  def [](x)
    @hash[x] || @hash[x]=@lambda.call(x,*@para)
  end
end

Function.new({0=>1}){"|n| n*self[n-1] "}[5] #=> 120
Function.new({0=>0,1=>1}){"|n| self[n-2]+self[n-1] "}[10] #=> 55

上の Function を試しに C で書いてみた時に self がどうしても main 
にしかならず、その Function を指すようにできなかったのであきらめた
ことがあります。