orap_memo0000 :: OSASK計画

orapに関するメモ-0000

• (by K^[1], 2009.02.05)

(0)

• 元ネタはGUIGUI01​/memo29^[2]。orapは Optimizer with RAndom Programing かなにかの略のつもり。おらぷ？自分で言うのもなんだけど実にシケた名前だ。
• なんかいろいろ書いているうちに実は結構簡単に作れるかもしれない気がしてきた（それほど本格的でなければ）。もちろん最長でも10バイト程度のプログラムしか見つけられないだろうけど。
• で、そのアイデアを書いていくには.g01ネタの延長で書くのは無理があると思って、一応独立。まあやや乱発気味のOSASKサブプロジェクトの一つだと思ってください。もちろんこれは時間のかからない一時的な脱線ネタで、現在の本流は当然.g01の整備です。

(1)

• やる前から非実用的だということは分かっているんだけど、それゆえに最初にこのプロジェクトの当面の目標を明らかにしておきたい。それはあまり気合を入れないで「orapもどき」というか「えせorapみたいなもの」を作り、「ああやっぱりこんなに遅いのね、あはは」ということを確認することだ。それでまあ作っているうちに高速化のアイデアが浮かぶかもしれないし、オープンソースにしておけば誰かが改造してネタとして遊んでくれるかもしれない。それでひょっとしてもしかして100バイトくらいまでなら実用になるかもしれない（ないない・・・苦笑）。まあとりあえず適当に作ってみてもいいんじゃない？、もしも結構簡単そうなら。という程度のもの。

(2)

• いきなり任意の全てのプログラムを生成させるというのは荷が重いので、当面は何も入力しないで、指定したバイト列を出力する最小のプログラムを探す、という一点にしぼることにする。これはたとえばcharsやhelloが最小かどうかを確認する行為とも言えるだろう。
• ・・・しかしこれで終わるのは応用が利かなくて面白くない。だからASCII列に限定せず、さらに画面にも出力せず、単に指定されたメモリに指定されたバイト列を生成させるだけのプログラムを探させることにする。これだと何が面白いかというと、これは実は究極の自己解凍型ファイル圧縮になりうるということだ。・・・ほーら、どう？なんか急に興味が沸いてこないですか？・・・入力と出力の関係をチェックするのは想像するだけでも大変そうだけど、無入力に対して一方的に出力させてその結果をチェックするだけなら検索速度も（相対的に）速そうじゃないか。
• しかもいろんなファイルを圧縮させてそのorapの結果を見れば、今まで誰も思いつかなかったような圧縮テクニックを見出せるかもしれない！・・・が、まあそんなまともなサイズのデータを圧縮させようものなら、すぐに終了まで1兆年とかになりそうだけど（苦笑）。

(3)

• orapの基本構成はこんな感じだ。
  • テスト用プログラム生成部は、総当たり的に次に試行するプログラムを生成。結局は整数を数えていく感じかな。
  • そしてそれがx86インタプリタ部で実行される。そして無効命令を検出したり、変なところをアクセスしようとしたり、もしくはあらかじめ設定していたステップ数になっても帰ってこないようなら、それはボツと見なす。また実行に寄与した部分をマークしておき、そこが変化しなければ何度試行したって同じ結果にしかならないので、インタプリタ実行する前にスキップするように工夫する。
  • また無事に帰ってきても、出力結果が期待通りでなければ当然ボツ。
  • 以上の全てをくぐり抜けて合格したら見つかったことになるので終了。
• で最初の頃はx86インタプリタ部を適当に作る、つまり最初は全ての命令セットをサポートしない。あらかじめ解（の一つ）を想定し、その解のために必要な命令しかサポートしないで、残りは全部無効命令扱いでいいと思う。だから簡単。

(4)

• 僕が作るとしたらやっぱり春か夏かそれくらいだけど、もちろん他の人が適当に作ってみてもいいので、待ちきれない人は暇つぶしにどうぞ。
• とりあえず最適化アルゴリズムとしては、究極かつ、あきれるほど馬鹿らしくて、そういう意味で画期的なはず！（笑）。

(5)

• 補足：
  • インタプリタ部が「実行に寄与した部分をマーク」するとしたが、実は寄与したバイトのうち一番最後のアドレスだけ分かればいい気がする。
  • それでプログラム生成部は、GUIGUI01​/memo29^[2]ではリトルエンディアンで話をしたけどそれはやめてビッグエンディアン的に総当りすることにすれば、スキップも効率よくできそうに思う。最初は1バイトで総当たり、次は2バイトで総当たり、次は3バイトで総当たり・・・みたいな感じかな。

こめんと欄

• 最悪でもベンチマークくらいの使い道はあったりして？（笑）。 -- K^[1] 2009-02-05 (木) 17:39:14