Island Life

< 暗算 | 悪女とツンデレ >

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

Past comment(s)

nobsun (2007/09/27 00:55:26):

quine のバリエーションになりそうな予感

nobsun :

gensort n は不要で、いきなり sorter0 から始められそう。

shiro (2007/09/27 02:00:23):

いや、総データ数は必要じゃないすかね。 終了を知る必要があるので。 総データ数を最初に与えるのではなく、特定の入力があったら終了ってことに すればnは不要になるけど。そっちの方が綺麗かな?

nobsun (2007/09/27 05:24:29):

sorterN への入力はだんだん短くなるんだから、 その入力がなくなった時点で打ち切ればいいだけじゃないの?

nobsun (2007/09/27 08:44:34):

Haskell版を投稿しちゃった。