Io で Y コンビネータ

それで、遊びたかったのは何かというと、このタイトルのものです。epcg さんの clouds の最近のエントリー「Yオペレータとメモ化」で Y オペレータがうまく動作しない…というような記述があったので、ちょっと気になってチャレンジしてみました。


デフォルトでは「'」を getSlot として使えないので(「'」は epcg さんの独自拡張)、ここでは getSlot を使っています。

Y := block(f, h := block(g, f(block(x, g(getSlot("g")) performOn(x)))); h(getSlot("h")))


以前のバージョンではブロックは変数に代入しないと評価できず、on を使ってこねくりまわさなければならなかったかと記憶しています。performOn が追加されて便利になったのですね。performOn は Smalltalk の #valueWithArguments:、Ruby の call に相当します。


たしかにこの定義でよいはずなのですが、このままだと、

Y(block(fact, block(x, if(x < 2, 1, x * fact(x - 1))))) performOn(10)

でエラーになります。


ためしに引数を減らして 2 を試すと、これなら大丈夫なようです。

Y(block(fact, block(x, if(x < 2, 1, x * fact(x - 1))))) performOn(2)
==> 2


改めてエラーを見ると「Nil does not respond to 'performOn'」なので、Y の定義中に使っている performOn のレシーバが怪しいですね。そこで、performOn の前に、ifNil(blcok(1)) を挿入してエラーが起きないようにし、さらに writeln(getSlot("g")); を適当な場所に挿入してみます。

Y := block(f, 
           h := block(g, 
                      f(block(x, 
                              writeln(getSlot("g"))
                              g(getSlot("g")) ifNil(block(1)) performOn(x))))
           h(getSlot("h")))

これで再び引数を 3 以上にして実行すると(もちろん引数が大きくなると答は正しく出ませんが)正常に終了し、問題が、getSlot("g") にあることが分かります。

Y(block(fact, block(x, if(x < 2, 1, x * fact(x - 1))))) performOn(3)
Nil
Nil
==> 6

そこで、こんな式を試してみました。

block(x, block(getSlot("x"))) performOn(3) performOn
==> Nil

どうやら入れ子になった block 内での省略時レシーバは self とは別のもののようです。そこでレシーバを明示的にしてやると、

block(x, block(self getSlot("x"))) performOn(3) performOn
==> 3

と、うまくゆきました。この方針で Y コンビネータも正常に動作するはずです。

Y := block(f,
           h := block(g, f(block(x, g(self getSlot("g")) performOn(x))))
           h(getSlot("h")))
Y(block(fact, block(x, if(x < 2, 1, x * fact(x - 1))))) performOn(10)
==> 3628800

めでたし、めでたし。