http://d.hatena.ne.jp/propella/20070526/p2 の続きです。今日待ってる時暇だったので、純粋関数的に書いたプログラムをどうやったら命令的に変換出来るか、またその逆について考えていました。こういうのは凄い研究が沢山あると思うけど、どうせいきなりそういうの勉強しても絶対分からないので、無駄と思いつつ自分で考えておいた方が良いのです。
ようするに、
plusTwo n = let a = 1 + n b = 1 + a in b
のような(またはポイントフリーに plusTwo = (1+).(1+)) 関数があった時に、
int plusTwo(n) { int a= n; a++ a++ return a; }
に変換できれば良いという事かな？これを機械的に判断する方法がバッチリ分かれば最高なんだけど、まだ考え中で、だけどもしかしてこれって群やモノイドに関係あるのではないかと思った。つまり、a++ を関数的に考えると、 a を一つ増やした数を作って、今までの a を置き換える事になるんだけど、引数と値は同じ型だし、命令的なプログラムは任意のサブルーチンに分ける事が出来るので、結合法則は満たしているし、nop が単位元だと思える。そしてそのプログラムが undo 可能なら群で、不可能ならモノイドだ。
という事は、システムを undo 可能にするなら、全部群で構成すれば良いという事になる。
ここでふと困ったのが表記法。関数を表記するのに Haskell はベストだと思うけど、命令型言語を正確に表記するにはどうすれば良いだろうか。これが無いと命令的に操作する方法を記述できない。やっぱり純粋状態型言語http://d.hatena.ne.jp/propella/20060803/p2 が必要だろう。アセンブラみたいなので良いんだけど。えーと。
あれ？でもポイントフリーに出来るんだったらスタックマシンでそのまま実行出来るから、これはもう、状態型言語なんじゃないか？ヒープ使わないならガベコレも要らなくなる？むむ。これは凄い。美しい。これ究極の答えじゃ？あとでゆっくり考えよう。
