2007/09/26

マシン語ブーム便乗

ついかっとなってやった。マシン語ならなんでもよかった。今は反省している。

どう書く?.org ソートするコードの生成

当然のことながら、プログラムというのは、マシン語を出力して初めて「生成できる」と言うのです。

(追記) このお題についてはもうひとつネタを思いついていたのだが アセンブラと戯れていたら時間がなくなってしまった。 アイディアをここに記しておくので興味のある人はチャレンジしてみては。 基本的なアイディアは、コード生成をlazyにやるということ (お題を満たすかどうかは微妙だが)

• gensortは入力数Nを受け取ると、ソートプログラム sorter0 を生成する。
• sorter0 は最初の入力を受け取ると、「残りのN-1個の入力を受け取り、 それをソートしてN個の値を出力するプログラムsorter1」 を生成してただちに実行する。
• sorter1も実は同様に、入力を一個受け取ると「残りのN-2個の入力を受け取り、 それをソートしてN個の値を出力するプログラムsorter2」を生成して ただちに実行する。
• 以下、入力が全て消費されるまで再帰。

プログラムをカリー化してる、と考えられなくもない。Partial Evaluationの 限定的な応用とも言えるかな?

各ステージのプログラムは次のステージの生成規則を持っていればいいはずだし、 既に受け取った入力によって大幅に枝刈りが出来るから、 元のお題のようにn!で大きくなるってことは無いと思うけど、 どんな姿になるのかは興味がある。 あと、「「「プログラムを生成するプログラム」を生成するプログラム」…」 というふうに入れ子になってゆくとS式が圧倒的に有利になるんじゃないかと 思うんだが、実はそうでもないかもしれない。

Tags: Programming, Assembly