Y combinator cont'd cont'd

先日のY combinatorの記事が間違っているわけではないがせっかく型付けが弱いんだから再帰なしで書いたらいいじゃないとの指摘を受けて、土日からうーんと悩んでいた。理論的な根拠付けとしては再帰を使わないでラムダ式で定義したYこんびねーた

Y = λf.(λx.f (x x)) (λx.f (x x))

をErlang風に書けばよいのだけども、最初はこのラムダ式の意味が理解できなかった。Wikipediaのところを参考にしながら、うーんとかいってたわけです。石垣の人にもちょいちょい教えてもらいながら。というかこのページすごく参考になりました。もう石垣島にケツ向けて寝れません。
でまあそれでも動かず、無限ループになるYコンビネータ

Y = fun(F)-> (fun(X)->F(X(X))end)(fun(X)->F(X(X))end) end.

書いたりして無限ループしてCtrl-Cとか押したりしてたわけです。うーんうーん。そしたら id:camlspotter さんに助言をいただきながら今日やっとピコーンと来たわけです。やってくる宿敵月曜日と闘いながらというか月曜日の朝そろそろ家を出ないといかん時間になってピコーンと来たわけです。

Y = fun(F)-> fun(N)-> 
  ((fun(X)->F( fun(M)->X(X) end ) end)(fun(X)->F(fun(M)-> X(X) end) end))(N)
  end end.

ええ見事に動きました。でも、形がちょっと違うし美しくない。私は気に入らなかったので、今日の仕事が手に付かなかった。というわけで、帰ってからちょっとやってみたら

Y = fun(F)->fun(N)->
   ((fun(X)->fun(M)->(F(X(X)))(M)end end)(fun(X)->fun(M)->(F(X(X)))(M)end end))(N)
   end end.

そしたら動いた。いちおうシンメトリック（でも、最終型じゃない）。いちおうErlangも関数がFirst class objectみたいなんだけど、関数適用が左結合じゃないからいちいちカリー化しなきゃいけなくてめんどうくさい。こういうときOCamlがいいなぁとか思う。Haskellシラネ。C++ templateもまあ強い型付けといえばそうなんだけど黒魔術に近いと思うので、素直にOCamlとかHaskellがいいんだろなぁ。OCamlに軽量プロセスとOTPがあればなぁ。オブジェクトがimmutableにならないから、むつかしいんだろなぁ。ちなみにOCamlは片付けが強いせいで、Y combinatorの型を定義したりしないといけない。

type 'a recc = In of ('a recc -> 'a)
let out (In x) = x in
let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a));;

ともあれ、いろいろ教えてくれた石垣の人と岡村蓮化郎のお父上*1には感謝感謝です。
で、深夜に、下に評価順を書き下してじーっと見てみたら、まだゴルフできそうなわけですよ。やってみるとこれでも問題なく動く：

Y=fun(F)->(fun(X)->fun(M)->(F(X(X)))(M)end end)(fun(X)->fun(M)->(F(X(X)))(M)end end) end.

というか、これが一番短くて一番美しい。シンメトリーがどうとかじゃなくてこれが最初のラムダ式の定義そのまま（Erlangなので明示的にカリー化せんといかんですとか）。いつもそうなのですが、岡村さんはいただいたコメントは馬に念仏状態なわけで、そのときは全く理解できない。ポカーンとして反応できないのです。しばらく経って振り返って運が良ければ意味がわかる手合いが多いのです。私も一般教養を身につけて馬状態から脱却せんといかんですばい。

かいせつ　　ー追記しましたが、fun(N)->(...)(N) endは単に ... と書いても動きます。というか不要。自戒のため残置ですよ。

Y = fun(F)->fun(N)->
   ((fun(X)->fun(M)->(F(X(X)))(M)end end)(fun(X)->fun(M)->(F(X(X)))(M)end end))(N)
   end end,
Fa = fun(Fact)->fun(1)->1; (N)->N*Fact(N-1) end end.

こいつが評価される順

(Y(Fa))(10) --->
-> (fun(N)-> ((fun(X)->fun(M)->(Fa(X(X)))(M)end end)(fun(X)->fun(M)->(Fa(X(X)))(M) end))(N)) <-- 10
-> ((fun(X)->fun(M)->(Fa(X(X)))(M) end end)(fun(X)->fun(M)->(Fa(X(X)))(M) end end))(10)
-> (fun(M)->(Fa(fun(X)-> ... end)( fun(X)-> ... end)))(M)end)(10)
-> (Fa((fun(X)-> ... end)(fun(X)-> ... end)))(10)
-> (Fa(fun(M)->(Fa((fun(X)->...end)(fun(X)->...end)))(M)end))(10)
-> 10 * (fun(M)->(Fa((fun(X)-> ... end)(fun(X)-> ... end))(M)end)(9) %三行上と同じ式
-> 10 * (Fa((fun(X)-> ... end)(fun(X)-> ... end)))(9)
-> 10 * (Fa(fun(M)->(Fa((fun(X)->...end)(fun(X)->...end)))(M)end))(9)
-> 10 * 9 * (fun(M)->(Fa((fun(X)->...end)(fun(X)->...end)))(M)end)(9-1)
-> 10 * 9 * (fun(M)->(Fa((fun(X)-> ... end)(fun(X)-> ... end))(M)end)(8) %四行上と同じ式
-> ...
-> 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * (fun(M)->(Fa((fun(X)-> ... end)(fun(X)-> ... end))(M)end)(1)
-> 10*...*2 * (Fa((fun(X)->...end)(fun(X)->...end)))(1)
-> 10*...*2 * (Fa(fun(M)->(Fa((fun(X)->...end)(fun(X)->...end)))(M)end))(1)
-> 10*...*2 * 1

って、あれ。何か違う←書き直した。多分これで合ってるけど、もうfunとかendとかタイプするのがしばらくイヤになってしまったという

苦労した形跡

*1:おめでとうございます。