Wednesday, 11 March 2009

高階関数、高階論理

関数を取り扱う関数が高階関数。論理式そもののを取り扱う論理が高階論理。なんか、すごいことが出来そうだよね。

でも、集合の集合で矛盾が出てカントールがいじめられたし。λ計算は、高階関数を取り扱えるんですが、否定を入れると矛盾してしまいます。

一方で、一階だろうが高階だろうが、プログラムや論理式は有限な記号で記述されます。なので、有限な記号上の「あるルールに従ったゲーム」にすぎません。このゲームで出来ることは、実は限られている。その限界が不完全性定理であり、それを計算機に焼なおしたのがTuring Machineというわけ。

そのゲームに入れる階層が階数だったり型だったりするわけ。と言うわけなので、プログラミングに関する限り、一階と高階では出来ることは変わらないというのが僕の理解です。

関数を評価する時には、その関数が依存している変数の値が必要。
 f(x) = x + a
で、a の値がいくつかってのは重要だよね。aとその値の組は環境とか呼ばれます。

環境と関数を組にして扱うと便利。それは closure と呼ばれます。適切な日本語訳は知りません。

closure とオブジェクト指向のオブジェクトとは同じものです。実際、closure を使ってオブジェクトを実装することが可能。

機械語による実装を考えると、環境を入れるヒープ領域と関数の組でしかありません。メモリ管理がめんどうなだけ。

今の高階関数を扱える言語は、closureを取り扱える言語という意味だと思う。

もう一つ別な高階関数があって、字面を直接取り扱うマクロがそれ。普通はコンパイル時にしか展開されないわけですが、これが、わからない。LISPのマクロは超すごい。だけど、マクロ展開した結果を表示するツールを持ってないとどうしようもありません。

C++のテンプレートは、はっきり、マクロ。しかも機能的にかなり強力。さらに、展開結果を見ることは出来ません。誰か助けてください。

Java のGenericは、単なるSyntax Sugarですが、やはり、マクロの一種です。機能的に制限されているのが救いです。また、discompiler を使うと、展開結果を見ることが出来ます。Java compilerはGenericの情報を持っているので、裏で、こそこそチェックが走ります。便利と見るか、怪しいと見るかは、自分次第だな。

Post a Comment