Y Combinator のお勉強
Y Combinator さんを参考に Y Combinator についてお勉強しました。
中身はほとんどそのままなのですが、唯一違う所といえばコードが Schemeから Smalltalk なところくらい。丸カッコよりも角カッコが好きな人向けです(ぉ
名前で再帰ってグローバル変数みたいでカッコ悪いよねっ！
Smalltalk で階乗を書くとこんな感じになります。
| fact | fact := [:n | (n = 0) ifTrue: [1] ifFalse:[n * (fact value: n -1)]]. (fact value: 5) printNl.
せっかくの ブロッククロージャなのですが、再帰するために「fact」という外部の名前 に依存しちゃってます。無名でいられないし、外の名前に依存してしまうのはブロックの中からみたらまるでグローバルな変数を参照しているプログラムみたいな感じでカッコ悪いです。
そこで、再帰する関数を引数に括り出してしまおう！というのが動機付けです。
グローバル変数イクナイ→引数渡しにリファクタリングです！みたいな。
というわけで、再帰する関数を f という引数で受け取るブロックで一層くるんでしまいました。
| fact | fact := [:f| [:n | (n = 0) ifTrue: [1] ifFalse:[n * (f value: n -1)]]].
こうすれば 最初に fact に引数で fact 自身を与えてあげれば OK なハズ。というわけでやってみます。
((fact value: fact) value: 5) printNl
が、これは動きません。エラーになります...orz
というのも、f に渡ってくるのは確かにfact自身ですが、この改造のせいで既にfactは「再帰させたいブロック」ではなく、「再帰させたいブロックを生成するブロック」になってしまったからです。むー。
手っ取り早く解決するには、fact の中でも f value: f をして階乗処理のブロックを作って、その作ったブロックに対して再帰するようにすればOK。
具体的にはこうなります。
| fact | fact := [:f| [:n | (n = 0) ifTrue: [1] ifFalse:[n * ((f value: f) value: n -1)]]]. ((fact value: fact) value: 5) printNl "=> 120"
というわけで、確かに動く。けれどこれは惜しい。
「再帰ブロックを作る処理」を括り出します
やっぱり作りたかったのは「再帰する自身を生成するブロックを引数で受け取るブロック」じゃなくって「再帰する自身を引数で受け取るブロック」です。、むー、だからこれは残念賞。
ええい、なんたる邪魔者ですか！ f value: f !
なので「再帰するブロック」 fact の方は元のままに、なんとか呼出側で頑張って
どうにかしてみたいなー、と思います。
| fact y | fact := [:f| [:n | (n = 0) ifTrue: [1] ifFalse:[n * (f value: n -1)]]]. y := [:f | [:proc | f value: [:arg | (proc value: proc) value: arg]] value: [:proc | f value: [:arg | (proc value: proc) value: arg]]]. ((y value: fact) value: 5) printNl "=> 120"
fact の中の邪魔者 f value: f の部分をブロッククロージャにしてしまって( [:arg | (proc value: proc) value: arg] の部分ね)、それを fact の引数として fact 自身の代わりに渡してしまえばいい。という発想で。
というわけで、2番目の動かなかったヤツの ブロックと呼び出しコードのつじつまを合わせる Y という ブロックを定義です。
あとはウネウネ頑張ったらこうなった、と言った感じです。初回の一回転を作るために同じコードのコピペして value: する構造になっちゃってますが、結論から言えば、これが Y combinator です。
よかった、できて。
でも本当はコレ Y combinator じゃないんですよ
f value: f の括り出しのとき、わざわざブロッククロージャでくるんで遅延させるようなこの構造は、本当は Z combinator というらしいです。
Y combinator は本当はこの様な感じ。
| fact y | fact := [:f| [:n | (n = 0) ifTrue: [1] ifFalse:[n * (f value: n -1)]]]. y := [:f | [:proc | f value: (proc value: proc)] value: [:proc | f value: (proc value: proc)]]. ((y value: fact) value: 5) printNl "=> センセー、動きません(TT"
おぉ、全然見やすい。けれど Smalltalk は f value: に渡す前に先に proc value: proc を評価しちゃうので、期待通りには動きません。しくしく。(gstだとSEGVで落ちるよ..ママン）
で、Y combinator の何が魅力です？
ちなみにコンビネータっていうのはプログラム意味論の用語。手続き名も含む「変数」がすべて束縛変数である (引数になっている) λ式のこと。そういうλ式はまわりの環境に依らずに同じ動作ができる……つまり完全に自分自身の意味が固定されている。
Y Combinator
へー。最初の動機、関数名を引数に括り出して無名化するのって そういう意味があったんですね。
Y combinator も Z combinator も不動点コンビネータの一種で、「不動点」というのはf(x) = x になるような 値x の事で、高階関数の場合は f(g(f)) = g(f) な 関数g のことだそうな。
・・あんまり意味分かってないで言ってますよ、もちろん。
Y combinator は これがあれば lambda で全部できるよ！・・みたいな凄い話と、メモ化して結果をキャッシュすると計算はやいよ！メモ化どころかログ出しでもなんでも再帰の合間に処理を突っ込めるよ！みたいな凄い話への入り口だから、みんな Y combinator にトキメいてしまうのだと思います。
このように、関数とデータの等価性は、データから関数を作り出すTuringのアプローチからも、関数からデータを作り出すChurchのアプローチからも保証されている。
なぜ関数型言語を注目すべきか、これで感じ取れるだろう。関数型を知っていれば、トンネルをもう片方の側からも掘る事ができるのだ。
404 Blog Not Found:TuringとChurchの狭間で
再帰というのはじつは「関数を入力として受け取りその関数を使う」関数の、特殊な場合という事が解ります。たまたま(?)入力されてきたのが自分自身だった場合が再帰というわけです。
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
おー、かっちょいい！
残念ながらわたしは、あんまり頭がよい方じゃないので、こういうネタも記事を読んだりするだけじゃいまいちピンとこない──「すごーい」とならずに「ふーん、そうなんだ」で終わっちゃいがち。
そんな残念なわたしでも、こうしてコードを組んで動かしながら試してみれば、理解もできるし「凄いねコレ！」と感動もできます。そんなときプログラミングを覚えてよかったな、お得だったな、プログラマで良かったなと、しみじみ実感するのです。
だから絶対小学校で学校でプログラミングを教えて、みんなが理解の為のツールを手にするべきですよねっ！（・・と、持論へ誘導して脱線しつつ終わる）
