2005/12/09

日替わりハピー

* Tさんと久しぶりにタマリンドにいって、タイカレーを食べたら、予想外にうまかった。昔みたいにご飯がぺちゃぺちゃじゃなかったのが、とくに。
* "Little Schemer" の Chapter 9 が飲み込めた。

で、"Little Schemer" の Chapter 9 は Y-combinator の話題なんだけど、「おまえら名前を付けずに再帰できるか?」という問いからスタートする説明はとても面白かった。で、Web をあちこち見てたら、Y-combinator について「名前を使わずに関数を再帰するための仕組み」だとして説明しているページがあった。そう言っちゃうのは、微妙に誤解だろ……(この本の影響じゃないと信じたい。)

僕自身の古い記憶と(いちおう数学基礎論が専門だった)、いまあちこち調べた部分をまとめると、Church って人が1階の記号論理体系におけるアルゴリズムの決定性を検証するのにλ算法ってのを発明して、それは基本的に変数の名前を置換したり関数を適用するだけで任意のアルゴリズムを定義するような仕組みなんだけど、そこで再帰的なアルゴリズムを定義するための道具として Y-combinator などの「適用しても関数を変化させない」ような関数を作ったって話(勘違いしていたら教えてください)。どうでもいいけど、そんな Y-combinator が話題として盛り上がっちゃうのは、それが Paul Graham の会社の名前であることと関係ないわけがない。

で、僕自身は、それが現実的にどんなアプリケーションで何の役にたつのかは知らない。動くコードとして見たのも、はずかしながら "Little Schemer" が初めて(基礎論の凡人はコンピュータなんて使わないんです!)。それでさらに調べてたら、Y-combinator は memoization に役立つみたいな話を発見。

Y overriding self-application :
http://okmij.org/ftp/Computation/overriding-selfapplication.html

memoization かあ。年内には SICP の Chapter 3 に入りたいなあ。

No comments :