『低レイヤを知りたい人のためのCコンパイラ作成入門』を使ってやってみた、縛り実況と初見実況

縛り実況、初見実況と呼ばれるタイプのゲーム実況が大好き

hsjoihs氏（以下、hsjoihs）：プレゼンその2をやります。

プレゼンその2、「Rui Ueyama compiler book any% 縛り実況（C-to-ELF category）」というタイトルで発表をしたいと思います。自己紹介はさっきやったので飛ばします。

みなさん、ゲーム実況は好きですか？　私は、ゲーム実況が大好きです。ゲーム実況がきっかけで大学の進路が決まったぐらいには大好きです。

司会者：へぇ。

hsjoihs：その中でも特に好きなのが、縛り実況、初見実況と呼ばれるタイプの実況動画です。

縛り実況とはどういうものか。こういうのは「ニコニコ大百科」を引用するのが一番早いので、ニコニコ大百科を引用しますが、ゲームをプレイする際、本来ゲーム側からは設定されていない制限を自ら課すことによって、より難易度の高いゲームをプレイすること、という解説がされています。

太字になっている部分だけを読むと、クリアするだけなら難易度が低いゲームに対して、自主的な制限をつけることであえて難易度を引き上げ、やりごたえのあるゲームを自ら作り上げる、というのが縛りプレイの主な趣旨である、と記載されています。

初見実況とは何かというと、そのゲームの前提情報なしの状態でプレイするというタイプの実況です。プレイ済みの人もプレイしたことがない人も共に楽しめることもあり、わりと人気が高いです。プレイヤーが求めない限り、基本的にネタバレ禁止というのが当然ながら初見実況の醍醐味となるわけです。

特に私は、「倭寇（わこう）」さんという実況者の、「【実況】初見のゼルダをフランス語でやるとどこまでいけるのか」というシリーズがとても大好きです。

初見のゲームを初見の言語でプレイするという縛りとなっていて、ゲームそのものに対する勘と、英語と類似しているフランス語の綴りをヒントに推理をしていくことで、だんだんとゲームができていくという、おもしろい実況になっています。

『低レイヤを知りたい人のためのCコンパイラ作成入門』で遊ぶことに決定

hsjoihs：ということで、私も縛り実況、初見実況をやってみたいという気持ちになるわけです。「さぁ、どのゲームで遊ぼう？」というのが問題になるわけですが。

よし、これに決めた！　『低レイヤを知りたい人のためのCコンパイラ作成入門』。

ということで、本ゲームの概要について解説していきたいと思います。ステップ1から28と名づけられたパズルが出題されるので、そのパズルを順番に解いていくことによって実績が解除されてクリアとなるというゲームです。

ステップ1でどういうタスクが出されるかというと、42という入力を受け取った時に、こういうアセンブリを出力するような、関数、プログラムを実装するというお題ですね。

この右側のアセンブリは、コンパイル、リンクして実行することによって、終了コードとして42を返すような関数になるのですが、そういう関数の元になるアセンブリファイルを出力するというタスクがお題になっています。

このゲームのおもしろさはどこにあるのか？

hsjoihs：本ゲームのおもしろさですが、最初のほうは丁寧な手ほどきがあって、後半ほどヒントが少ないという、おもしろいゲームによくある性質がこれも満たされていて、本ゲームのおもしろさを引き立てるのに役立っていると思っています。さらに、どんどんと手元のコードがCコンパイラっぽくなっていくというおもしろさがあります。

ステップ28まで突破すると、かなりCっぽいコードがコンパイルできるようになります。これが「any%部門」ですね。その勢いで自発的に進めていくと、自分自身をコンパイルできるようになります。これが「self-host部門」です。さらにがんばると、Cの仕様に完全に準拠した完璧なコンパイラが完成します。これが「100%部門」ですね。「100%部門」の達成者がいるのかどうかは、知りません。

私が今回やるのは、この「any%部門」という枠になります。ということで、次にいきましょう。

このゲームは、比較的大人気だと思ってよくて、かなり多数の走者がいるんですね。「Twitter」で（スライドの）このページのURLを検索すると、どんどんヒットするので、かなりたくさんの走者のいる大人気ゲームであるということがよくわかると思います。かく言う私も、4年半前に「self-host部門」を走りました。

縛り実況というのは、先ほど言ったように、今クリアするだけなら難易度が低いゲームを選ぶのがポイントですが、私はもうすでにこのゲームをクリアしているので、縛り実況をやるのに向いているだろうという気持ちになりました。

さらに、あえて難易度を引き上げて、やりごたえがあるゲームを自ら作り上げる、ここなんですよね、縛り実況のミソって。ここで本当に発想力が問われる。縛り実況のおもしろさは、縛りのおもしろさで決まるし、おもしろい実況者さんは、おもしろい企画をコンスタントに出し続けることができるお方です。

縛り内容3つを発表

hsjoihs：さて、ということで今回の縛り内容を発表していきます。縛り内容は3つ。1、アセンブリではなくて、実行形式はELFを常に出力するというフォーマットで、コンパイラブックを走る。これによって難易度引き上げの効果を出すことができます。

2つ目、ELFや機械語のフォーマットを調べすぎてはいけないという縛りをつけます。これによって、目的を達成できる方法のうち、最も調べごとが少ないルートを選ぶことになるので、謎解き、初見実況の効果が出ておもしろくなります。

最後に、私が奇数番目のステップをやり、tkr（kgtkr氏）という私の友人が偶数番目のステップを実装するという、2人実況という形式にします。これにより互いのコードを読まなきゃいけなくなるので、コードの可読性を担保し、かつ、「なるほど、そう組んできたか」ということを、お互いのコードに感じることができ、そういう楽しみも得ることができます。

ということで、この3つを縛りに加えて走っていこうという、そういうわけでございます。

実際にやってみた結果

hsjoihs：実際にやってみた。ステップ1、縛り実況というのはですね、基本的にパート1が一番おもしろいです。なぜかというと、パート1でその縛りのおもしろさを出せないと、残りのパートを視聴者が見てくれないからです。そのため、必然的に縛り実況はパート1が一番おもしろくなります。

そういった話は置いておいて、今回ELFを吐くという縛りなので、3という入力を与えられて、実行すると終了コードが3になるような実行形式のELF。42が入力されて実行すると終了コードが42になるような、そんなELF。こういうのを出力する関数を実装するのがステップ1のタスクになるわけです。

さて、さぁ、ELFの知識なしでこれを作れというのが、縛りの都合上発生するわけですね。ELFの知識なしでどうやってこんなものを作るのか。みなさんどうやって作ると思いますか？　ちょっと考えてみてください。その間に私はちょっと休憩をします。

ふぅ。

司会者：今のところ、私がTwitterで一番好きなコメントは、tetsu_kobaさんの「異世界から来た方ですね」という感想です。

hsjoihs：いいですね。

さて、ここで長々と時間を取ってもしょうがないので、種明かしにいきたいと思います。私が出した答えはこうです。

最初に、3を終了コードにするアセンブリと、42を終了コードにするアセンブリを書いて、それにnasm -felf64 --reproducibleビルドをつけます。

ビルドの日時とかそういう変な情報が紛れ込まないようにした後に、さらにstripコマンドを通過させることで、ファイル名の情報もそぎ落として、tiny3という実行形式と、tiny42という実行形式を作ります。当然このtiny3、tiny42を走らせると、終了コードがそれぞれ3や42になって終了します。

さて、このtiny42とtiny3のバイナリを比較すると、なんと1byteしか差分がない。この52というのは8進数なので42の意味です。なので、42と3の違いしかない。単一のbyteでしか異なっていないことが検証できました。

さて、ここまで来たらもう勝ちですね。差分が1byteということは、こういうコードを書いてやればいい。大事なところにフォーカスすると、ここです。

tiny_3の中身をループして、tiny_42と中身が一致していたら、その中身を写経する。片方が3で、もう片方が42になっていたら、唯一の差分に目的の数を突っ込んで、残りは写経。はい、これで達成できました。ということで、このステップ1をELFの知識なしで達成できました。

コメント返しのコーナー

hsjoihs：はい、コメント返しのコーナー。「なんでELFにしたんですか？」。ELFは一番ポピュラーで、私のWSL環境で動くし、さらにステップ1で小技を導入することで複雑さがうまく回避できておもしろいからです。

それについて、a.outのサポートが消えたとか、WindowsのCOM（コンポーネントオブジェクトモデル）が今はもう使えないとか、そういう有益な情報をいただけたので、みなさんも走る時にはELFで走ってみるとおもしろいのかもしれません。

「ステップ15：関数の定義に対応する」まではクリア済み

hsjoihs：現状なんですが、「ステップ15：関数の定義に対応する」まではクリアしております。「フィボナッチ数列を再帰で計算しつつ表示」を実装しております。

ただし、符号付き8bitを越えるjmpのオフセットを書く方法をまだ知らないという設定になっているので、「else { return fib(n-1) + fib(n-2); }」と書くと、このreturnの中で最適化をなにもしていないので、nを呼んできて、それをスタックに載せて、1を呼んできてそれをスタックに載せて、スタックの2つからポップして、それの引き算をしてみたいな、かなり冗長なコードになっているせいで、バッファの中身が130になってしまって、ぎりぎり符号付き8bitに入らず、elseの中身にこんなに長い式を書くとpanicしてしまう。

そんなしょぼいコンパイラになってしまっていて、結果として、再帰フィボナッチは汚いコードになっております。

何をやったかというと、まず「return fib(n-1) + fib(n-2);」はelseの外に書くことでjmpを発生させない。あとリンカがないので、出力はこの__builtin_putcharっていうコンパイラマジックで出力を行うという設計にしてあります。

リンカもアセンブラも思った以上に複雑なことをしていた

hsjoihs：「完走していない感想」ですが、やはり元のやつはかなり楽だったんだなと。元のやつはかなり多くをアセンブラとリンカに押しつけることができて楽なんだなと。リンカもアセンブラもさまざまな複雑なことをしているんだなと、もう1人のtkrが述べていますが、私もまったく同じ気持ちです。

実況本体は、（スライドを示して）テキストログがこちらにあります。テキストなので実況というか連載みたいなものですが、まだ連載中なのでよかったら読んでみてください。不定期更新です、すみません。

ご清聴ありがとうございました。

質疑応答

hsjoihs：なにか質問はありますか？

司会者：質問という質問は、出ていないかな。たぶん多くの人が、「この縛りってどういう意味なんだろう？」とたぶんルールを聞いた時は思ったと思うんですけど、置換するところで、あぁ、そういう話ねという、なるほど感がみんなあったようです。ELFを調べずにELFを触るという意味ですね。

hsjoihs：はい、そういうことになっています。

司会者：確かに、any感あるっていう（笑）。みんなRust好きだな（笑）。

hsjoihs：言語は何にします？　ってもう1人の走者に聞いたら、Rustって言われたのでRustになりました。

司会者：あと、2人リレー。「縛りも2人リレーだけでも十分やろ」みたいな（笑）。これを2人でやろうという発想がおもしろいですよね。交互にやるっていう。

hsjoihs：経緯がいろいろとあって、1人でやると学業をおろそかにしてひたすら突き進んでしまうリスクがあったので、1人がやって、はい、もう片方に投げた。はい、もう片方が暇になるまで待つぞみたいにやることで、それを防止できるみたいな、そういう裏の理由もありました。

司会者：確かに。

hsjoihs：そんな感じですね。質問はそんなもんかな。