みなさんこんにちは。(はじめまして|お久しぶりです)。艮鮟鱇です。6月に入り少しずつ暑くなって参りましたが皆様御機嫌如何でしょうか。私は花粉症です。
さてこの度 セキュリティ・キャンプ全国大会2018 というものに出来心で応募したところ、なんと通ってしまいました。びっくらぽんです。このイベントは一度選考を通ってしまえば参加できる（二次面接などはない）ので、 8月の半ばぐらいに開催地である東京に行って、私の場合はC言語コンパイラを作成することになります。今からわくわくどきどき楽しみです。セキュリティ・キャンプの詳細を知りたい方は公式サイトをどうぞ。
さて、セキュリティ・キャンプに通った人はその応募内容を晒すと、ナウなヤングでバッチグーになれるそうです。ぜひ私もナウなヤングでバッチグーになりたいので以下に貼り付けようと思います。
問題
私は集中開発コースシステムプログラミングトラックの「C コンパイラを自作してみよう！」というゼミに応募しました。このゼミの問題は以下のようなものでした。
[問1] これまでのプログラミング歴（C言語に限りません）について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。
[問2] コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。
[問3] C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか？考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。
[問4]. 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。
鮟鱇の回答
順に掲載します。
[問1] これまでのプログラミング歴（C言語に限りません）について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。
※ この問の一番下に、これまでに作成したプログラムの一覧の抜粋を書きました。
小学生のころにコンピュータ将棋がきっかけでプログラミングを始め、現在まで続けてきました。はじめはコンピュータ将棋のれさぴょんなどが実装されているC++に興味を持ったのですが、当時の自分には難しく、Windowsの簡単なバッチファイルを書くなど以外では、プログラミングそのものをすることはあまりありませんでした。その代わり、近くの図書館にあった『コンピュータ将棋のアルゴリズム』（池 泰弘、I・O BOOKS、2005）や、『30日でできる! OS自作入門』（川合 秀実、毎日コミュニケーションズ、2006）などを読みながら、コンピュータの動き方や内部的な構造、MinMax法・リングバッファといったアルゴリズム・データ構造を眺めていました。いま思えば、このときの経験が、自分が情報系の道に進みたいと思った大きなきっかけとなったと思っています。
中学生になって情報同好会に入り、本格的にプログラミングを始めました。C言語からはじめ、C++・Perlなどを書いていました。特にC++（というよりむしろBetter Cでしたが）とDXライブラリを使ってゲームなどを作成し、文化祭などで展示していました。そのうちDXライブラリでは、Windowsのコンポーネントを利用したツール類が作りにくいことを知り、『猫でもわかるWindowsプログラミング 第3版』（粂井 康孝、ソフトバンククリエイティブ、2008年）やインターネットの情報などを頼りに、 Win32APIを使ってソフトウェアを作成していました。
また中学三年のころから「さくらのVPS」を借り、簡単なCGI掲示板を書いて運用していました。同じサーバーでMinecraftのためのマルチサーバーなども立ち上げていましたが、これを起動・終了するためのシェルスクリプトを書いているうちにシェルスクリプトで全てを行うことに限界を感じ、 PerlやRubyで書き直したりしていました。
高校生になってからは、C++やRubyを使って簡単なツールなどを作るようになりました。高校1年のときには、クイズ研究会に頼まれて、後輩と共に得点表示ソフトウェアを作りました。高校2年のときには、文化祭でインターネットラジオを放送することになり、複数本のマイクの音声を内部でミックスし、仮想オーディオラインに流すようなソフトウェアを書きました。
また、WordPressを使用して、複数人で更新するブログの管理をやっていました。ここで使用したWordPressテンプレートがSimplicity2ですが、デフォルトのコードではどの著者が投稿したのかひと目では分からず困ったため、PHPを書き換えて表示するようにしました。
大学に入ってからは忙しくなったこともあり、大きなプログラムを書くことはあまりなくなりました。情報技術の基礎を教える授業で登場したモデルコンピュータ（アセンブリと機械語が対応していることを示すためのモデル化されたコンピュータ）の仕様から、簡単なアセンブラやエミュレータを作りました。 Ruby on Railsを使って過去問管理Webアプリケーションを作成しました。友達に誘われて競技プログラミングを始めました。現在はAtCoderで水色です。 Mastodonのセットアップの際に実行されるスクリプトにバグがあったのでPull Requestを送り、マージされました。
直近ではMaLというチュートリアルを参考にしながらLISPインタプリタを作成しました。またC++17のconstexprを使用して、ニューラルネットの学習をコンパイル時に行うプログラムを作成中です。 C++でTwitterクライアントを作成中ですが、TwitterのUserstream廃止を受けて、現在計画が宙ぶらりんになっています。 Python3と機械学習用ライブラリであるChainerを使って、ニューラルネットに関する論文の実装などを行っています。
【これまでに作成したソフトウェアの一覧の抜粋】
おおよそ時系列です。
ブロック崩し
自分で作った最初のまともなソフトウェアです。C++とDXライブラリで実装しました。下の方でユーザーが操作するバーが動き、上にあるブロックに動く玉をぶつけてこわします。文化祭で展示しました。
お絵かきソフト
ドラッグすると線が引かれます。初めはDXライブラリを使って実装しましたが、太い線が書けず、Win32APIのペンを使用して実装し直しました。
ComingBossSoon
予め指定したキーを押すと、現在開いているウィンドウを全て隠してくれるソフトウェアです。 C++とWin32APIのライブラリであるWin32++を使用して実装しました。内部的には、Win32APIのEnumWindows()とShowWindow()を使用していました。
Chess
『コンピュータ将棋のアルゴリズム』を参考にしながらチェスAIをC++で作成しました。単純なαβ法に定跡データを載せただけのものでしたが、自分より強くなってしまい、AIが負けた時のデバッグに困りました。
Ash
クイズの大会中に参加者の点数を表示するためのソフトウェアです。学校のクイズ研究部と協力して作成しました。「クイズの大会」と一口に言ってもその種類は様々で、表示すべき内容と入力仕様（つまりMVCのViewとController）が多様でした。そこで、Viewに関しては後輩がHSPを使用して作成し、私がC++で書くModel部分とはWM_COPYDATAを使用して通信を行いました。また、Luaを組み込んだ上でこれを使用してControllerを書くことで、Model側のコンパイルをせずに変更が可能なようにしました。
ソースはこちらです。
cables
インターネットラジオを文化祭で放送するに当たって作成したソフトウェアです。WindowsとLinux両対応です。 PCに接続された複数のマイクから入力を取り込み、それをミックスしてスピーカーに出力します。ここで「マイク」と「スピーカー」は、WindowsやLinuxからそう認識されるものであれば何でも良いので、音楽再生用ソフトウェアから出力される音楽を仮想オーディオラインを通じてcablesに取り込んでミックスし、ラジオのBGMとするなどの使い方をしました。また、実際の運用時にはマイクが接続されるPCとインターネットに配信するPCを別にしました。そのため、この2台のPCをLANケーブルでつなぎ、両方でcablesを起動した後、cables内部でソケット通信を行うことで音声をやりとりしました。
入力・出力は仮想化されていて、実際にそれが何をしているかを気にせずに扱うことが出来るようにしました。音声を入出力する単一のデバイスをUnitという単位で構成し、これらをSocketと呼ばれる機構でつなぎ合わせることで、全体のシステムが構築されるようにしました。Unitにはマイクから直接音声を取得するものだけではなく、リバーブフィルタなども含まれました。
全体として、音声を受け取るとスレッドが走り、予め指定したユニットを経由して、スピーカーやソケット通信路へと流すようになっていました。
ソースはこちらです。
Repka
大学過去問管理Webアプリケーションです。Ruby on Railsを使用して作成しました。（主に法的な）諸般の事情から運用はしていません。過去問の情報（教員・科目名・年度・ファイルへのリンクなど）を登録すると、それらの情報に対して部分一致検索をできるようになっています。 RoRの習作として作成しました。
ソースはこちらです。
鼻くんパズル
友人が作った「鼻くん」というキャラクターを使った8パズルです。C++とSFMLを使って作りました。動いているイメージがこちらにあります。
ソースはこちらです。
パチンコ
Windows XPに付属していたピンボールのようなゲームです。C++とSFMLを使って作りました。 SFMLを使用する部分は上の「鼻くんパズル」と実装が共通しています。
SVGを読み込ませると、それがそのままマップになります。汎用的な当たり判定の仕組みを作成するのに苦労した覚えがあります。 hanakunブランチにすると上の「鼻くん」がボールとして飛びます。動作イメージはこちらです。
ソースはこちらです。
MastodonへのPull Request
Mastodonサーバーを立てる際に実行されるrakeファイルにバグが有ったので、これを直すPRを送ったところ、マージされました。 1つめ 2つめ
MaL
MaLというチュートリアルに従って LISPインタプリタを作成しました。Step Aを除いて全てのテストを通しました。
ソースはこちらです。
constexpr-nn
C++17のconstexprを使用して、コンパイル時にニューラルネットの学習を行うプログラムです。現在作業中です。 C++14においてconstexprが大幅に制限緩和されたため、実行時向けに書くコードとほとんど同じように、コンパイル時に動くコードを書くことが出来ます。
ソースはこちらです。
Yellow
バイナリ一つで動くTwitterクライアントを目指してC++で書き始めましたが、TwitterがUserstreamの8月廃止を決めたため、モチベーションが下がっています。Twitterとの通信にlibcurlを使用しています。
ソースはこちらです。
Chainerを用いたニューラルネット論文の実装
Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes という論文で登場する「訓練サンプルに対しては良い性能を示すが、テストサンプルに対しては悪い性能を示すニューラルネット」を作成するためのシステムの実装を、Python3と機械学習用ライブラリのChainerを用いて行っています。基本的な実装は終了しましたが、適切なハイパーパラメータが見つからず、調整中です。
ソースはこちらです。
[問2] コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。
C言語コンパイラについて説明します。まずソースコードを読み込んで、正規表現などを用いてトークンごとに切り分けます。正規表現は決定性有限オートマトンに変換できるため、これにマッチするかどうかで文字列の切り分けを行うことが出来ます。言語処理系のトークン切り分けのためのC言語コードを生成するソフトウェアとしてLex及びその強化版であるFlexなどがあります。
次に、それらのトークンの列を抽象構文木（AST）と呼ばれる木構造に変換します。これによって、トークンの羅列だったソースコードを、コンパイラが理解できるような形にします。例えば、「a = 1 + 2 * 3;」というプログラムは
=
/ \
a +
/ \
1 *
/ \
2 3以上のような木に変換されます。このような変換は、文脈自由文法によって記述された規則をもとに構文解析器を作成することで行います。構文解析器は、その仕組みによってLL法・LALR法・LR法などに別れます。C言語にはLALR法の構文解析器を使用することが出来ます。言語処理系の構文解析器のC言語コードを生成するソフトウェアとしてYacc及びその強化版であるBisonなどがあります。
次に意味解析を行います。ここでは、C言語の言語仕様と照らし合わせて不正なプログラムが書かれていないかを検査すると同時に、プログラム内で使用されている識別子に関する情報を得ます。例えば int i; という文があるときには、ここでint型の変数iが宣言されることを記録すると同時に、同一スコープ内で同名の変数が宣言されていないかなどを確認し、不正な場合にはエラーを出力します。
続いて最適化を行います。例えば即値で書かれているような計算は、あらかじめコンパイラが計算した値を代わりに使用することで、最終的なバイナリの実行速度を上げることができます。また、必要のない計算を行っている部分を削除することで、バイナリのサイズを小さくすることが出来ます。
最後にコード生成を行います。上で作成した構文木や識別子の情報などを参照し、それらに対応するアセンブリ（LLVMを利用するならば中間コード）を出力します。
出力されたアセンブリはアセンブラによって機械語へと翻訳されオブジェクトファイルとなります。その後、複数の（少なくとも1つ以上の）オブジェクトファイルがリンカによってリンクされて実行バイナリとなります。
参考：『実践コンパイラ構成法』（滝本宗宏、コロナ社、2017）
[問3] C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか？考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。
この問への答えは、どの程度の技術水準を持った人がプログラムを書くかや、Lex・Yaccなどのツールを使用するかによってかなり異なると思います。
仮にYaccを使用せずにC言語コンパイラを書くとすると、一番困難かつ煩雑なのは構文解析器を作成する部分だと思います。再帰下降型構文解析を行うことが出来るLL法は比較的実装が簡単ですが、これではC言語の構文解析は不可能なため、LR法やLALR法を用いる必要があります。私はこれらの構文解析器の実装をしたことがないので正確なところはよく分かりませんが、今回この文章を書くために『実践コンパイラ構成法』などを調べた際に、理論的に難解であるという印象を受けました。実装に落とし込むのは、より難しいだろうと思います。逆に、Yaccを使用するならば、構文解析器の作成はある程度簡単になるだろうと思います。C言語の言語仕様は、 Yaccと同じような記法で書かれているためです（C99言語仕様のAnnex A）。これを利用してYaccコードを書くことができれば、極めて容易に構文解析器を実装することが出来ると思います。
その他に困難な点として、言語仕様を理解するという点が挙げられると思います。例えばsizeof演算子の詳細な挙動や暗黙の型変換の規則など、コンパイラを作る際には把握しなければならないであろう事柄でも、 C言語のコードを書くだけなら、「なんとなく」の理解で済んでしまいます。私は、C言語の表層的な理解はしているつもりですが、言語仕様を1から読んだことはありません。 C言語コンパイラを作成する際にはこれを理解する必要があります。
そのうえで、いま作ろうとしているコンパイラの実装デザインを考える必要があります。拙速に実装を初めてしまうと、途中で大幅にコードを改変する必要が出てくることがあります。アドホックなやり方でこれを乗り切ると、最終的に誰も読めないようなソースコードが生まれてしまう可能性があります。これはバグの温床になりえるため、避けなければなりません。ただ、未来のコードを予測して現在のコードを書くことはそれほど容易ではありません。逆に想定しなくても良いコードを想定してしまったために、コードが煩雑になってしまうこともあります。例えばC++などで不用意に共通部分を継承関係でまとめてしまうと、あるクラスの特異な挙動を実装しにくくなり、結果としてdynamic_castを多用するようなコードを書いてしまうことがあります。このような状況を回避するためには、既存のC言語コンパイラの実装を参照する必要があると思いますが、他人が書いたコードを読むのは一般的に大変な作業になりがちです。
また、個人的に困難なポイントとしてコード生成があります。コンパイラは最終的にアセンブリを出力するため、コンパイラを書くためにはアセンブリを理解しておく必要があります。私はアセンブリを書いたことがほとんど無く、この点に関して1から勉強する必要があると思っています。アセンブリはハードウェアに近い部分であることから、これまで自分がやってきたプログラミングの規則とは異なる部分も多くあると予想されます。これを習得するのは簡単ではないだろうと思います。
[問4]. 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。
Twitterです。 GitHubです。 AtCoderです。ブログです。ブログ「カオスの坩堝」は複数人で更新しています。私は「艮 鮟鱇」名義です。私が管理・運営しています。
Linuxに関する通り一遍の知識はあるつもりです。知人向けにLinux 講習会を開催した経験があります。上に書いたブログに、この講習会の議事録があります。
プログラミングを始めた中学1年の頃からコンパイラに興味がありました。当時は何も分かりませんでしたが、そのうちASTや正規表現などを知り、一度挑戦してみようと思っている間に年月が過ぎ去っていました。これではダメだと思い、MaLを見ながらLISPインタプリタを作成しました。おかげで簡単なインタプリタの構造は理解できましたが、実用的なコンパイラに関する興味は一層高まりました。同時期にTuring Complete FMを知って聴取し、自分と同世代のハッカーがたくさん居るということを知りました。何か自分もやってみたいとちょうど思っているときに今回のセキュリティキャンプを見つけ、ぜひやりたいと思って応募しました。よろしくお願いします。
終わりに
今読み直すとかなりひどい文章だと思います。特に問2・問3をもう少し書くべきだったかもしれません。来年度以降応募される方は、あまり参考にしないことをおすすめしておきます。代わりに、といっては変ですが、この記事を編集している間に続々と公開されていた、他の参加者の応募用紙をおすすめしておきます。インターネット上で公開されている応募用紙はここにまとめられています。ぜひ参考になさってみてはいかがでしょうか。
