![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
for (i = 0x20; i != 0x7f; i++) { putchar(i); } で出力されるものと同一の出力結果を求められるのが、通称charsという コードゴルフです。これはASCIIキャラクタのうち印字可能なものすべての列挙になっています。helloと違うのは、 ただ文字列表示を一回呼べばそれでいいというわけにはいかないことです。明記していませんが、もちろん末尾には改行も 必要です。
[このあたりにコンソールでの実行画面を入れる]
DOSではシグネチャなしで17バイトまで行きました。フェアに比較するなら点数は19バイト相当ということになります。 そしてg01では13バイトになりました。ということは、DOS版の19バイトのうちの31%はムダというわけです。
おっとここで補足が必要かもしれません。helloといいcharsといい、本当にくだらなくて実用的ではないことでゴルフして いるなと思われたかもしれません。いや全くそれはそのとおりです。面目ないです。しかしいきなり実用的な規模でゴルフ しても、私にはどうしたらいいか分からなくなってしまうのです。最初は易しい問題を解き、そして少しずつ難しい 問題に挑戦して、よいOSはどうあるべきか、限界はどこなのかを探っていくのです。
私は先に機械語のコードゴルフについて、他の言語よりも短くできるから機械語がいいと書きましたが、実際charsを 先のルールを守って実装したら、機械語以外のプログラミング言語で13バイト相当にするのは不可能じゃないかと 思います。シグネチャを引いたら11バイトです。11文字以内でcharsが書けるプログラミング言語なんてあるんでしょうか？
この先、話の流れ上g01はもう出てこないのですが、しかしg01はx86用のOSとしてはもっともコードゴルフに有利な OSだろうと思っています。helloやchars以外でも、何を作ってもとても小さくなる傾向があります。かっこいいです（自画自賛）。
今までLinuxのhelloの58バイトの話からの流れで、x86の機械語限定で話を進めてきました。しかしx86以外にもCPUの アーキテクチャはたくさんありますし、x86はコードゴルフに向いた命令体系を持っているのかというと、そんなことは ありません。ここまでの話の通り、私はLinuxの最善が示されてもそこで満足はできず、OSの制約をなくして最善解を 探しました。その結果x86の最善解に到達したものの、やはりそこでは満足できないのです。機械語の命令体系の制約も 自由にして、真の無差別級ではどうなるのかをすごく知りたくなりました。
そのためにはOSだけではなく機械語の命令体系も設計しなければいけません。私は理想の命令体系を設計して 仮想マシンを作って、それで実際にテストしながらAPIも作り究極を探求しました。自分で言っちゃいますが、 これはすごいことです。なぜって、将来たとえメジャーなOSが何に取って代わろうとも、それどころか今後 どんなCPUが主流になるにせよ、私がここで追求した解は（ちゃんと限界に到達していれば）不変の真理として 永遠に正しいわけです。経済動向やくだらないデファクトスタンダードをめぐる争いも、すべて超越したところに 到達するわけです。超かっこいいです。ドキドキがとまりません。役に立たないという唯一にして決定的な欠点だけが 本当に惜しまれます・・・。
私の研究によれば、この究極の条件でのhelloのサイズは、15バイトであると思われます。つまり、x86での研究は すでに限界に達していたように思います。そしてcharsはなんと8バイトなのです。efg01の13バイトでも自分と しては相当によくできていると思っていたのですが、さらに5バイトも縮むとは・・・。というか8バイトってシグネチャを 引いたら6バイトですよ。6バイトでこの処理が記述できるってにわかに信じられますか？コードゴルファーなら どうしても信じられなくて、ルールを破ってズル用のCPU命令かAPIがあるんじゃないかと疑わずにはいられない はずです。・・・詳細は後ほど。
この結果はx86の機械語の命令体系にも無駄が多く残っていたという明白な証明になっています。
helloとかcharsはコンソールアプリで、はっきりいって見栄えがしません。じゃあグラフィカルなアプリではどうでしょうか？ ええ、もちろん小さくなります。ズルはないので不得意分野はありません。
以下のような画像を描画するプログラムは13バイトで書けます。
[ここに画像を入れる]
以下のような画像の場合は71バイトで書けます。これはちょっと判断に困るかもしれません。参考までに書くと、この模様を 既存のCPU+OSで一番小さくかけるのは、NEC PC-9801上のMS-DOSでした。しかしそれでも114バイトを要して いました。71バイトが究極の答えだとしたら、その114バイトのうちの37%は無駄だったというわけです。
[ここに画像を入れる]
[このあたりで今までのサイズ比較表を入れる]
それではcharsの改良過程を比較して、鑑賞する事にしましょう。・・・ここから16進数が出てきますが、個々の数字の意味が よくわからなくてもあまり気にせずに、話の流れを追ってください。16進数は2桁でちょうど1バイトです。
まずMS-DOS用の.COM形式でごく普通にcharsを作ると、以下のような23バイトになります。
B402 // 機能番号=2（一文字表示API） B220 // A=32（文字コード） CD21 // MS-DOSのシステムコール命令（Aの文字が表示される） FEC2 // Aに1を加える 80FA7F // Aと127を比較 75F7 // 等しくなければCD21のところへ戻って繰り返し B20A // A=10（文字コード：改行） CD21 // MS-DOSのシステムコール命令（改行される） B44C // 機能番号=76（プログラムの終了API） B000 // 終了コード=0 CD21 // MS-DOSのシステムコール命令（終了する）
このままでも他のOSと比べれば十分に小さくて無駄が少なくて美しいのですが、より小さくするために、以下のような改変を加えます。
(1) x86の仕様によると、この文脈では FEC2 の代わりに 42 を使うことができる (2) MS-DOSの仕様によると、この文脈では C3 という1バイトの命令だけでプログラムの終了処理をすることができる
その結果は以下のとおりです。これが17バイトで、MS-DOSにおける最小のcharsです。
B402 // 機能番号=2（一文字表示API） B220 // A=32（文字コード） CD21 // MS-DOSのシステムコール命令（Aの文字が表示される） 42 // Aに1を加える 80FA7F // Aと127を比較 75F7 // 等しくなければCD21のところへ戻って繰り返し B20A // A=10（文字コード：改行） CD21 // MS-DOSのシステムコール命令（改行される） C3 // プログラムの終了
うーん、美しい。・・・え、この美しさが分からないですか？これ以上削れないというところが美しいんですよ。 ・・・まあいいです。
次はOSECPU（おせくぷ、OSの名前）の例です。8バイトのcharsへの道です。
最初はやっぱり工夫しないで普通に書いた場合からはじめます。
05E1 // シグネチャ 20C20 // A=32（文字コード） 1 // ラベル1 2B0750FF07 // 機能番号=65287（文字列表示API） 2132B11CF4B11B1 // メモリを1バイト確保する 48D890B130 // Aを確保したメモリへ書き込む 43B019EBFA8411CFE10 // OSECPUのシステムコール命令 CF5B11B1 // メモリを1バイト開放する 9401 // Aに1を加える A10C7F6 // Aと127を比較して等しくなければラベル1へ戻って繰り返し 208a // A=10（文字コード） 2132B11CF4B11B1 // メモリを1バイト確保する 48D890B130 // Aを確保したメモリへ書き込む 43B019EBFA8411CFE10 // OSECPUのシステムコール命令 CF5B11B1 // メモリを1バイト開放する 2B0750FF06 // 機能番号=65286 2B10 // 終了コード=0 43B019EBFA8411CFE10 // OSECPUのシステムコール命令
なんかちょっと見ただけでもすごく長そうです。はい、なんと86バイトにもなります。これはひどいです。 これはもっとも基本的な命令だけを組み合わせて作ったので、どうしても長くなってしまいます。ということで改良です。
(3) 43B019EBFA8411CFE10 は BFA8 という短縮形に置き換える (4) 20C20-1-...-9401-A10C7F6 は 60C20C7F...87 という短縮形に置き換える (5) プログラムの末尾の正常終了処理は全て省略できるので書かないことにする (6) プログラム最後の改行処理も省略できるので書かないことにする
そうするとこうなります。
05E1 // シグネチャ 60C20C7F // A=32～126までの繰り返し範囲開始 2B0750FF07 // 機能番号=65287（文字列表示API） 2132B11CF4B11B1 // メモリを1バイト確保する 48D890B130 // Aを確保したメモリへ書き込む BFA8 // OSECPUのシステムコール命令 CF5B11B1 // メモリを1バイト開放する 87 // 繰返し範囲終了
これで31バイトです。かなり短くなりました。まだ8バイトではありませんが。
ここで説明が必要だと思うので書きます。まず(3)の短縮形はずるいと思われるかもしれません。しかしx86でもCD21と いうのは実は短縮形で、基本的な命令だけで書いたら10バイト（20桁）以上を要する命令です。ですからこれは 「おあいこ」なのです。(4)に相当する短縮形はx86にはありません。私はこれはシステムコール命令以上に頻出な パターンだと思っているのですが、x86の設計者はそうは思わなかったのかもしれません。コードゴルフ的な設計力に 関しては私の勝ちですね。(5)はOSの仕様の勝負で、(2)に相当する仕様です。(6)もOSの仕様です。
さて、このプログラムはまだまだ小さくできます。OSECPUではAPIと頻出する関数呼び出しについて、超短縮形を 用意しています。5で始まる命令群です。これはAPIと関数呼び出しのパターンを分析して、パラメータの渡し方を いくつかのタイプに分類して整理して設計したものです。g01もこれとほぼ同じ仕組みを持っています。 これを使うとcharsは劇的に短くなります。
(7) 2B0750FF07-2132B11CF4B11B1-48D890B130-BFA8-CF5B11B1 は 511B00 という短縮形に置き換える
05E1 // シグネチャ 60C20C7F // A=32～126までの繰り返し範囲開始 514B00 // Aの文字を文字列表示APIを使って表示 87 // 繰返し範囲終了
これで10バイトです。一気に8バイトが見えてきました。さらに以下の省略ルールを使って8バイトにします。
(8) プログラム末尾の87は省略してよい (9) プログラムが00で終わる場合、これも省略してよい
05E1 // シグネチャ 60C20C7F // A=32～126までの繰り返し範囲開始 514B // Aの文字を文字列表示APIを使って表示
ついに8バイトになりました。無駄がなくて美しいです！
(7)の是非はいったん保留にして、(8)と(9)について説明したいと思います。OSECPUでは、プログラムが 中途半端な終わり方をしていると判断すると、つじつまを合わせようとする機能を持っています。(8)や (9)はその機能を利用したものです。この手の機能には一部に強い抵抗があることも分かります。なぜなら、 プログラマのミスによって中途半端になっているかも知れず、それをエラーも警告もなしに勝手に推測して 修復するのはけしからん、バグ発見を困難にする、という主張も可能だからです。
私はこれに対し次のような見解を持っています。まずソースレベルではこのような省略は許していません。 これはまさにその手のミスを防止するためです。しかしそれらのチェックを全てパスした後で、機械語を 出力するときにOSECPUが推定修復可能な省略を適用します。プログラマがこれらに気を使わなくて よくなっているのです。もはやバグ発見を困難にする問題がないので、この機能は純粋に便利で賢い機能に なっています。
以上の説明の流れで感じてもらえたと思いますが、コードゴルフは、短く書ける代替表記を探してそれを適用して いくことがメインです。つまりコードゴルフに強いOSとは、多くのプログラム中に表れる頻出パターンに対して、 短くする方法を十分に用意しておいただけのことだと思っています。OSECPUの場合、頻出パターンを短くするために 基本命令はやや長くなる傾向があります（短い書き方を短縮用にとっておいているため）。これをずるいと思う人も いるかもしれません。それも一つの見解です。しかしこれは非常に効果のある手法ですし、私はよい方法だと 思っています。
そして(7)ですが、これも短縮形なのです。それに尽きます。51が文字列表示API呼び出しの短縮形であることを 表して、その次の4が短縮形のタイプを表して、B0が変数Aを、そして最後の0が文字列の終端を表しているのです。
私のこだわりポイントについて話す前に、まずはコードゴルフに関する状況を紹介したいと思います。 今のところ、私がライバルだと感じている人は世界に一人しかいません。他にも一生懸命にやっている人が いるのかもしれませんが、私はまだ知りません（すみません！）。これを読んで「なーんだ」と思うかも しれません。「じゃあ二人で低レベルな争いをしているんだな」と思うかもしれません。
しかしそれはたぶん大きな間違いです。私たちはたった二人ながらも、十分にレベルの高い競争をしてきたのです。 私たちはどちらもOSの開発経験があり、独自OSをいくつも作ってきました。そんなプログラマはそんなに多くは ありません。ですから腕前はそれなりにあるのです。そしてお互いに何度も追い抜きあっているうちに、ついに 世界広しと言えどもこれを越えるものを作れる者は私たち二人以外にはいないだろう、と思えるところにまで 来てしまったのです。中二病的だと思われるかもしれませんし、まあ実際そうかもしれないですが（笑）、 まあやれるものならやってみてほしいです。
ということで、完全無差別級のコードゴルフは日本が最高レベルです。しかも圧倒的に最高レベルです。 確信しています。これくらいのことを簡単に断言できてしまうくらいに、私たちは研究に研究を重ねてきたのです。 ・・・もし私たちがどうやってやっているのか知らないのに同じところまでできちゃうすごい人がいたら （それはつまり私たちと同格ということですが）、絶対に友達になりたいです。というか私たちのノウハウを 学んでさらに改良してくれる人だって十分にすごいと思うので、やっぱり友達になりたいです。
きっと誰も賛同してくれないのを分かってて言っていますが（笑）、日本人はコードゴルファーをもっと尊敬しても いいのではないかと思います。だって世界一ですよ。まあくだらない趣味だと言われればそれまでですが、でも 世界一ですよ。そう簡単になれるものじゃないんです。日本が世界一になれる分野ってそんなにたくさんあるわけ じゃないです。世界一を大事に思ってほしいです。・・・まあ思ってもらえなくても私はがんばりますけどね。
現在charsに関しては世界記録は私が保持している8バイトです（自称）。しかし、競争相手は11バイトを達成して おります（しかも私より先に）。私は今回chars最小記録を奪還したのです。でもその差はたったの3バイトしか ないのです。油断はできません。
先のcharsの鑑賞のところで、私はたった1バイトを削っただけでもかなりの満足感を得ていたことが感じられると 思います。それはなぜかと言えば、ライバルに勝つためです。私たちの差は本当に小さいのです。ちょっと 油断したら、すぐに追い抜かれてしまうのです。世界一とはそういうものなのです。
自分でも、何もここまでやらなくても・・・と思うことはよくあります。まあ1バイトくらいいいじゃないかとか 思うこともあります。きっと仲良しのライバルだってここまではやらないだろうと思うこともあります。しかし そのたびに思うのです、将来海外の人たちがこの分野に興味を持って、節操なく頑張って世界一を取られたら どうしようと。そしてそのときになって「そのアイデアなら自分も1年以上も前から持っていたんだ、でも やりすぎだと思っていたからやらないんでいたんだ」と言ってみたところで、それは負け犬の遠吠えにしか ならないだろうと。
私は今までずっと競争してきた仲良しのライバルになら負けてもいいんです。彼に負けるのは当然というか、 納得できるのです。しかしそれ以外の人に負けるのは到底容認できません。もし負けないようにするチャンスが 十分にあったのにそれをしなかったせいで負けたのだとしたら、きっと一生後悔します。だから私はやるのです。 たったの1バイトでも取れるものはすべて取るのです。
そもそもコードゴルフの美学は何ですか。そう、無駄がないことです。削れる部分が残っているようでは美しい なんて言えません。削れると分かっていて削らないという選択はあり得ません。美しくなければコードゴルフ している意味がないからです。
余談ですが、日本人はコードゴルフに向いているような気がします。なんかこう、小さい物を緻密に作るのは、 日本人の得意分野のような気がしませんか？ そしてコードゴルフをやると、1バイトの本当の価値が分かるよう になります。
先の例ではどんどん削って短くしていく方向でのコードゴルフをご覧に入れましたが、逆の発想も可能です。 まず、絶対に削れないものは何かを考えるのです。helloの場合ですと、"hello, world!"の文字列を削ることは できません。これを削ってしまうと、結局それはhello専用APIを持っているということになるからです。任意の 文字列表示をコンパクトにできるものこそ究極なのです（まあhelloやworldなどの基本的な英単語に番号を振って OSに対して単語番号で表示できるようにするような方法はありだとは思いますが）。charsの場合ですと、 32と127（20と7F）は削れない情報だと思います。もちろんデータだけではダメです。これらのデータをそのまま 表示するのか、それとも開始値や終了値を表しているのかなど、そういうことを示す制御用の情報も必要でしょう。 こうして必要なものだけを積み上げていって、究極解に到達することも可能だと思います。私はこの方向で 自分のプログラムを解説できるだけの能力がまだないので、この話は今回はここまでです。
これは当たり前の事実ですが、charsを1バイト小さくするためには、OSに機能を追加しなければなりません。 それは当然OSが大きくなってしまうことを意味しますが、その増加量は1バイトではなく、もっとたくさん 増えます。つまりOSの大きさとcharsの大きさの合計を見れば、増加以外の何物でもありません。短縮形の サポートにしても、OS側には短縮形と展開形の両方のデータを内部には持っているので、やはりOSのサイズは 増えてしまいます。そう考えると、そもそもOS改造も許した無差別コードゴルフって一体なんなのかという気が してくるかもしれません。
でもこう考えてみてください。OSの改良によって小さくなるアプリはcharsだけではないのです。他のアプリも 小さくなるのです。もしOSが100バイト増加しても、100個以上のアプリが1バイト小さくなるのなら、トータル では得と言えるではないですか。私たちはまさにそういう観点で考えているのです。実際私はたくさんのアプリ を書いてみて、感じをつかみながらOSを改良してきました。ある機能を導入すると、アプリによって大きく なったり小さくなったりまちまちなことがありました。そんなときは、その機能をOSに入れるかどうかで悩む わけですが、その時の基準は、結局トータルではどうなのかということです。将来このOSのアプリ数が1000とか になったとして、その時にどのくらいの割合のアプリがどのくらいの影響を受けそうなのか。それを勘と経験で 見積もって取捨選択していくのです。
とにかく一番やっちゃいけないのは、charsしか小さくならないような機能を入れてしまうことです。それは hello専用APIと同じことです。だからルール違反なのです。というか私の誇りが許しません。特定のアプリ しか小さくならない機能なんて全く必要ありません。OSがそれ以上に大きくなってしまうかもしれないとか、 そんなのは全部関係なくてそもそもダメなのです。
さてコードゴルフの世界が少しは分かっていただけたでしょうか。面白いとは思ってもらえないのは分かって います。説明も難解だったと思います。ですからそこは共感してもらえなくていいのです。とにかく私が伝えた かったのは、たかがコードゴルフにここまで熱中している人がいるんだということなのです！
| コメント | お名前 | NameLink | |
