帰ってから、実際に動かしたコードは下の方に掲載しました。
なぜこんなことをしたのか
手元にノートしかない状態に長時間置かれたためです。結構、オススメかもしれません。なぜ Y Combinator なのか
他に適当なネタが思いつきませんでした。すぐ書けるようなものだと、暇つぶしになりませんし・・・。Y Combinator については、以下の記事を見たときの衝撃からか、何かと気になる存在です。
The Little Schemer, 4th Edition 含め、何度も書いているので、どういうものか理解できている（つもり）です。
いつも Web 上の解説を読んだり、The Little Schemer, 4th Edition のやり方を真似てやっていました。
しかし、どれもしっくりこないので、自力で、自分の頭で考えてやってみました。
やってみてどうだったか
紙でいけます。さすが黒板言語。意外と楽しめます。紙面でやるネタが他にも欲しくなりました。括弧の対応がすごく難しいですね。しばらくすると慣れてきます。
lambda は ^ （カレット）で書きました。lambda は紙に書くには長すぎました。
結果
階乗から Y Combinator を取り出せ（導き出せ）ました。目的は、「再帰」の部分と「階乗」の部分を分離すること、と考えて良いのかもしれません。
分離した「再帰」に「階乗」の部分を引数で渡せるようにする、とも言えると思います。
もしくは、「再帰」を一般化するとか「抽象化する」でも良いのかもしれません。
本当の目的はよくわかりません。たぶんλ計算の本を読むと分かるのだと思います。
これができたからといって、特にお得なことはありません。知りません。ですが、頭の体操としては非常におもしろいです。私は好きです。
コード
ではまず、普通の階乗を定義します。
意外とここが一番難しいかもしれません。階乗の定義から手続き名を取り去ります。つまり define を使わないわけですが、名前が無いと再帰できませんよね。
名前を付けるには引数にしてしまえば良い、ということです。ある意味ここが分かれば、もうできたも同然です。ここが頭の中で動かなければ、これ以降が厳しいかもしれません。自分を呼び出す自分に自分を渡す、みたいな。
次に、(f f) の部分を f と書けるようにしたいと思います。ここでは、引数を一つ取る無名関数で包んでしまえば良いです。すると、それを丸ごと外から渡すことができるようになります。(f f) → (lambda (x)((f f) x)) 。
2 で包んだ (lambda (x)((f f) x)) を外から渡せるようにしたいと思います。(lambda (f)(lambda (n) ... の関数をさらに 無名関数で包んで、その中で引数に (lambda (x)((f f) x)) を渡してあげれば良いですね。f のままでも良いのですが、紛らわしいので f を g にしました。これで内側の f には (lambda (x)((g g) x)) が入るようになります。
そうすると、内側の (lambda (f) ... がそのまま「階乗」の部分です。これを分離するのが目的ですから、一番外側で外部から引数として受け取るようにしてあげれば良いです。良い名前が思い浮かばなかったので、concrete の c にしました。できあがり。
単一引数しか受け取れないのもアレなので、可変長引数に対応してみようとしました。たぶん、できたのではないかと思います。apply してあげれば良いです。テストでアキュムレータを第二引数に取る階乗を渡してみましたが、動いているようですね。
これで「再帰」と「階乗」が分離できました。この「再帰」の部分が Y Combinator ということで良いと思います。
あとは、名前を付けるなりして動かしてみます。
The Little Schemer, 4th Edition の9章に出てきますね。The Seasoned Schemer の16章には Y! と Y-bang というのが出てきます。
追記
追記するほどのことでもありませんが・・・。Y Combinator で検索すると Paul Graham が関わっているベンチャーキャピタルが先に出てきますよね。
あと、MITの盾は Y Combinator ですね。 YF = F(YF) 。
0 件のコメント:
コメントを投稿