鮟鱇みなさんこんにちは。(はじめまして|お久しぶりです)。6月に入り少しずつ暑くなって参りましたが皆様御機嫌如何でしょうか。いうものに出来心で応募したところ、なんと通ってしまいました。8月の半ばぐらいに開催地である東京に行って、私の場合はC言語コンパイラを作成することになります。今からわくわくどきどき楽しみです。セキュリティ・キャンプの詳細を知りたい方は公式サイトをどうぞ。セキュリティ・キャンプに通った人はその応募内容を晒すと、ナウなヤングでバッチグーになれるそうです。私もナウなヤングでバッチグーになりたいので以下に貼り付けようと思います。コンパイラを自作してみよう!」というゼミに応募しました。このゼミの問題は以下のようなものでした。これまでのプログラミング歴(C言語に限りません)について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか?考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。これまでのプログラミング歴(C言語に限りません)について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。この問の一番下に、これまでに作成したプログラムの一覧の抜粋を書きました。小学生のころにコンピュータ将棋がきっかけでプログラミングを始め、現在まで続けてきました。はじめはコンピュータ将棋のれさぴょんなどが実装されているC++に興味を持ったのですが、当時の自分には難しく、Windowsの簡単なバッチファイルを書くなど以外では、プログラミングそのものをすることはあまりありませんでした。秀実、毎日コミュニケーションズ、2006)などを読みながら、コンピュータの動き方や内部的な構造、MinMax法・リングバッファといったアルゴリズム・データ構造を眺めていました。いま思えば、このときの経験が、自分が情報系の道に進みたいと思った大きなきっかけとなったと思っています。中学生になって情報同好会に入り、本格的にプログラミングを始めました。C言語からはじめ、C++・Perlなどを書いていました。Cでしたが)とDXライブラリを使ってゲームなどを作成し、文化祭などで展示していました。Win32APIを使ってソフトウェアを作成していました。中学三年のころから「さくらのVPS」を借り、簡単なCGI掲示板を書いて運用していました。PerlやRubyで書き直したりしていました。高校生になってからは、C++やRubyを使って簡単なツールなどを作るようになりました。高校1年のときには、クイズ研究会に頼まれて、後輩と共に得点表示ソフトウェアを作りました。高校2年のときには、文化祭でインターネットラジオを放送することになり、複数本のマイクの音声を内部でミックスし、仮想オーディオラインに流すようなソフトウェアを書きました。WordPressを使用して、複数人で更新するブログの管理をやっていました。ここで使用したWordPressテンプレートがSimplicity2ですが、デフォルトのコードではどの著者が投稿したのかひと目では分からず困ったため、PHPを書き換えて表示するようにしました。大学に入ってからは忙しくなったこともあり、大きなプログラムを書くことはあまりなくなりました。情報技術の基礎を教える授業で登場したモデルコンピュータ(アセンブリと機械語が対応していることを示すためのモデル化されたコンピュータ)の仕様から、簡単なアセンブラやエミュレータを作りました。Railsを使って過去問管理Webアプリケーションを作成しました。友達に誘われて競技プログラミングを始めました。現在はAtCoderで水色です。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アプリケーションです。Railsを使用して作成しました。(主に法的な)諸般の事情から運用はしていません。ファイルへのリンクなど)を登録すると、それらの情報に対して部分一致検索をできるようになっています。RoRの習作として作成しました。鼻くんパズル友人が作った「鼻くん」というキャラクターを使った8パズルです。C++とSFMLを使って作りました。動いているイメージがこちらにあります。XPに付属していたピンボールのようなゲームです。C++とSFMLを使って作りました。SFMLを使用する部分は上の「鼻くんパズル」と実装が共通しています。SVGを読み込ませると、それがそのままマップになります。汎用的な当たり判定の仕組みを作成するのに苦労した覚えがあります。hanakunブランチにすると上の「鼻くん」がボールとして飛びます。動作イメージはこちらです。RequestMastodonサーバーを立てる際に実行されるrakeファイルにバグが有ったので、これを直すPRを送ったところ、マージされました。LISPインタプリタを作成しました。Aを除いて全てのテストを通しました。constexpr-nnC++17のconstexprを使用して、コンパイル時にニューラルネットの学習を行うプログラムです。C++14においてconstexprが大幅に制限緩和されたため、実行時向けに書くコードとほとんど同じように、コンパイル時に動くコードを書くことが出来ます。Yellowバイナリ一つで動くTwitterクライアントを目指してC++で書き始めましたが、TwitterがUserstreamの8月廃止を決めたため、モチベーションが下がっています。Twitterとの通信にlibcurlを使用しています。いう論文で登場する「訓練サンプルに対しては良い性能を示すが、テストサンプルに対しては悪い性能を示すニューラルネット」を作成するためのシステムの実装を、Python3と機械学習用ライブラリのChainerを用いて行っています。基本的な実装は終了しましたが、適切なハイパーパラメータが見つからず、調整中です。コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。C言語コンパイラについて説明します。ソースコードを読み込んで、正規表現などを用いてトークンごとに切り分けます。正規表現は決定性有限オートマトンに変換できるため、これにマッチするかどうかで文字列の切り分けを行うことが出来ます。言語処理系のトークン切り分けのためのC言語コードを生成するソフトウェアとしてLex及びその強化版であるFlexなどがあります。次に、それらのトークンの列を抽象構文木(AST)と呼ばれる木構造に変換します。これによって、トークンの羅列だったソースコードを、コンパイラが理解できるような形にします。3以上のような木に変換されます。このような変換は、文脈自由文法によって記述された規則をもとに構文解析器を作成することで行います。構文解析器は、その仕組みによってLL法・LALR法・LR法などに別れます。C言語にはLALR法の構文解析器を使用することが出来ます。言語処理系の構文解析器のC言語コードを生成するソフトウェアとしてYacc及びその強化版であるBisonなどがあります。次に意味解析を行います。ここでは、C言語の言語仕様と照らし合わせて不正なプログラムが書かれていないかを検査すると同時に、プログラム内で使用されている識別子に関する情報を得ます。いう文があるときには、ここでint型の変数iが宣言されることを記録すると同時に、同一スコープ内で同名の変数が宣言されていないかなどを確認し、不正な場合にはエラーを出力します。続いて最適化を行います。値で書かれているような計算は、あらかじめコンパイラが計算した値を代わりに使用することで、最終的なバイナリの実行速度を上げることができます。必要のない計算を行っている部分を削除することで、バイナリのサイズを小さくすることが出来ます。最後にコード生成を行います。上で作成した構文木や識別子の情報などを参照し、それらに対応するアセンブリ(LLVMを利用するならば中間コード)を出力します。出力されたアセンブリはアセンブラによって機械語へと翻訳されオブジェクトファイルとなります。その後、複数の(少なくとも1つ以上の)オブジェクトファイルがリンカによってリンクされて実行バイナリとなります。C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか?考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。この問への答えは、どの程度の技術水準を持った人がプログラムを書くかや、Lex・Yaccなどのツールを使用するかによってかなり異なると思います。行うことが出来るLL法は比較的実装が簡単ですが、これではC言語の構文解析は不可能なため、LR法やLALR法を用いる必要があります。私はこれらの構文解析器の実装をしたことがないので正確なところはよく分かりませんが、今回この文章を書くために『実践コンパイラ構成法』などを調べた際に、理論的に難解であるという印象を受けました。実装に落とし込むのは、より難しいだろうと思います。逆に、Yaccを使用するならば、構文解析器の作成はある程度簡単になるだろうと思います。これを利用してYaccコードを書くことができれば、極めて容易に構文解析器を実装することが出来ると思います。その他に困難な点として、言語仕様を理解するという点が挙げられると思います。C言語のコードを書くだけなら、「なんとなく」の理解で済んでしまいます。私は、C言語の表層的な理解はしているつもりですが、言語仕様を1から読んだことはありません。C言語コンパイラを作成する際にはこれを理解する必要があります。そのうえで、いま作ろうとしているコンパイラの実装デザインを考える必要があります。拙速に実装を初めてしまうと、途中で大幅にコードを改変する必要が出てくることがあります。アドホックなやり方でこれを乗り切ると、最終的に誰も読めないようなソースコードが生まれてしまう可能性があります。これはバグの温床になりえるため、避けなければなりません。未来のコードを予測して現在のコードを書くことはそれほど容易ではありません。逆に想定しなくても良いコードを想定してしまったために、コードが煩雑になってしまうこともあります。C++などで不用意に共通部分を継承関係でまとめてしまうと、あるクラスの特異な挙動を実装しにくくなり、結果としてdynamic_castを多用するようなコードを書いてしまうことがあります。このような状況を回避するためには、既存のC言語コンパイラの実装を参照する必要があると思いますが、他人が書いたコードを読むのは一般的に大変な作業になりがちです。個人的に困難なポイントとしてコード生成があります。コンパイラは最終的にアセンブリを出力するため、コンパイラを書くためにはアセンブリを理解しておく必要があります。私はアセンブリを書いたことがほとんど無く、この点に関して1から勉強する必要があると思っています。アセンブリはハードウェアに近い部分であることから、これまで自分がやってきたプログラミングの規則とは異なる部分も多くあると予想されます。これを習得するのは簡単ではないだろうと思います。何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。