セキュリティ・キャンプ全国大会2018に応募して選考に通った話

はじめに

　はてなブログ初投稿です．年齢的に最後のチャンスということで，ダメ元でセキュリティ・キャンプ全国大会2018 「Cコンパイラを自作してみよう！」ゼミへ応募したところ，選考に通りました．応募に至った詳細な経緯は「問4」に記述しておりますので，このゼミへの応募に至った経緯を知りたい方はそちらをご覧ください．どうやら応募課題をはてなブログで晒すという風潮があるようですので，私もその流れに便乗したいと思います．

 　選考は減点方式ではなく，加点方式で行うとのことでしたので，「この情報を記述するべきかどうかを判断するのは私ではない」と自分に言い聞かせながら文章を書いていたので，読み手にとっては非常に読み辛い文章となってしまったと思います．せめて各設問の中で見出しを作るとかして，構造化して書けば良かったかもしれない...

　私よりも文量が多く素晴らしい解答をされている方もいらっしゃいますし，問2以降は私の理解を書いていて，嘘を書いてある可能性もありますので，是非参考程度に...

[問1]. これまでのプログラミング歴（C言語に限りません）について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。

　私がC言語でHelloWorldのプログラムを書いたのは2012年の高校1年のときであり，現在まで常にプログラミングに関わってきたためプログラミング歴は約6年と少しになる．この問では，私のプログラミング歴について時系列に沿って答えていきたいと思う．
　私が高校1年次にC言語に触れるきっかけとなったのは，情報処理部という部活に所属したことである．この部活は主に競技プログラミングに関する大会への参加およびその対策を活動としており，最初にC言語を学んだのは競技プログラミングの問題を解くという目標のためであった．約3ヶ月ほどでC言語の構文や，StackやQueueのような基本的なデータ構造の実装を学び，C言語を使ってシーザー暗号の実装やあみだくじをシミュレートするような，単に実装力のみが求められる問題を50問程解いていた．その後STLを利用するためC++を学び，競技プログラミングはC++で参加するようになり，また競技プログラミングで頻出の深さ優先探索や幅優先探索，ダイクストラ法のようなアルゴリズムを学び，そのようなアルゴリズムの知識が問われるような問題も解くようになっていった．高校時代には300問以上の問題を解き，いくつかの予選を勝ち上がりオンサイトのコンテストに出場することができた．現在に至るまでの競技プログラミングに関する代表的な実績を以下に示す．

• Super Computing Contest 2013本選出場
• Super Computing Contest 2014 本選出場
• 日本情報オリンピック2013-2014 予選 Aランク 本選出場
• CODE FESTIVAL 2015 決勝出場 200名中137位
• ACM-ICPC 国内インターネット予選 2016 全384チーム中17位
• ACM-ICPC アジア地区つくば大会 2016 全45チーム中27位
• DDCC2017本戦出場 200名中152位

競技プログラミングの上位勢と肩を並べる程の実力はないが，100名から200名規模の本戦参加者が居るオンサイトコンテストに出場できる程度の実力である．現在は積極的にコンテストに参加するということをしていないため，問題を解く機会も少ないが，長いこと競技プログラミングをやってきたおかげで簡単なプログラムの実装であれば，周りよりも早く実装できることが多いと感じている．
　高校時代の部活での活動は競技プログラミングが主であったが，毎日のように競技プログラミングに触れていることに対し少々飽きを感じ，当時話題となっていた技術や言語を試すということを並列して行うようになっていった．当時はUnityやJavaScript,Node.jsが話題となっていたため，これらのフレームワーク・言語に触れ，Unityによってオブジェクト指向プログラミングおよびゲーム開発を学び，JavaScript,Node.jsを通じてWebプログラミングやサーバサイドプログラミングを学んだ．これらの技術を利用したアプリケーションを作成し，文化祭ではそれらのアプリケーションの公開をした．高校2年次ではUnityで作成したブロック崩しアプリケーションを作成し，高校3年次ではTwitterを模倣したSNSを作成した．これらのアプリケーションのリポジトリへのリンクを以下に示す．

• https://github.com/sanopy/breakout2013
• https://github.com/sanopy/hamakotter-2014

　大学入学後は講義やグループワーク課題としてプログラミングに関わることが多くなった．1年次では，「プログラミング入門」という講義でJavaを通じてプログラミングを学び，この講義の後半では「ぷよぷよ」というゲームを模倣したゲームの雛形となるプログラムが与えられ，各チームで自由に拡張し，発表せよという課題が与えられた．このとき，私はぷよぷよAIの実装を担当した．AIとは言っても単純に次に来るブロックの情報と，現在の盤面の情報を用いて深さ優先探索を行い，最も連鎖が狙える場所へ落としていくというものであったが，AIという言葉と実際に8〜12連鎖が発生するデモによって発表を盛り上がらせることに成功したことは今でも記憶に新しい．
　大学2年次（後書き:嘘です．大学3年次でした．）には，手続き型言語やオブジェクト指向言語以外の言語に触れることが目的の「記号処理」という講義があった．この講義ではLispとPrologに触れ，入門程度ではあるが関数型言語や論理型言語についての理解を得ることができた．これらの言語を用いて大きなアプリケーションを実装することはなかったが，リストの長さを求めたり，リストを反転させる関数や述語を実装する演習問題を通じてこれらの言語の理解を深めることができた．
　大学3年次には実験科目が始まり，実験科目は「OSより上のレイヤについての実験」，「コンパイラを実装する実験」，「CPU作成を含むハードウェア実験」の3つが必修となっていた．OSより上のレイヤについての実験では，「特定のキーワードを含むレコードの抽出プログラムを実装し，MySQLとの処理速度を比較および高速化を頑張る」といったお題や「脆弱性のあるプログラムに対してバッファオーバランによって任意コード実行が可能なエクスプロイトを作成する」といったお題などがあった．その中のひとつとして「Flickr APIを利用して何か面白いアプリケーションを作成せよ」というお題があり，グループ内の3人でモザイクアートを生成するアプリケーションの作成を行った．これは生成されるモザイクアートがユーザが投稿した画像に近くなるように，Flickrに存在する画像をかき集めて生成するというアプリケーションである．ここで私はアプリケーションのフロントエンド部分（画像の受け取り，APIの呼び出し，モザイクアート生成のアニメーションなど）を担当し，他の2人はAPIの実装や通信部分（ここでは通信にWebSocketを利用した）に関する実装を行った．このときのソースコードとモザイクアートの生成例をいくつか示したもののリンクを以下に記す．

• https://github.com/mjtakenon/exp1part3group1
• https://gist.github.com/sanopy/ff3766bbd5d69debd35b20b91fc12e27

　コンパイラを作成する実験では，CPUを作成するハードウェア実験で実際に作成するSEP (Shizuoka Educational Processor) というアーキテクチャ向けのコード生成を行うコンパイラを作成した．コンパイラへの入力となるプログラミング言語はLL(1)を満たすC言語風の構文規則をもつ言語であり，コンパイラはJavaによって実装された．このコンパイラでは，四則演算，アドレス値，変数宣言・参照・代入，if文，while文，局所変数，引数なし関数，引数付き関数の実装を行った．コンパイラの雛形となるプログラムは与えられたものであるが，DFAを設計し字句解析モジュールを作成すること，LL(1)を満たすBNFから構文解析を行うモジュールを実装すること，変数名と型などの情報をハッシュテーブルに登録し入力文の意味解析を行うモジュールを作成すること，意味解析の結果からSEP向けのコード生成を行うモジュールを実装することなどを経験した．このとき作成したコンパイラのソースコードへのリンクを以下に示す．
（後書き:応募課題にはソースコードのリンクを示しておりましたが，将来同じ実験を履修する後輩がコピペすることを防ぐため，ここではリンクを隠させていただきます．）
　講義以外では，サークルの先輩が立ち上げたスタートアップ企業が将来リリースするアプリケーションの開発を行っている．将来リリースされるアプリケーションであるため，サービス内容については詳しく語ることができないが，教育用のシステム開発を行っており，CodeigniterというPHPフレームワークを用いて中規模のWebアプリケーション開発を行っている．（後書き:応募用紙ではもう少し具体的に書いていました．）
　以上が私のプログラミング歴についてである．

[問2]. コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。

　コンパイラは一般に「字句解析」「構文解析」「意味解析」「コード最適化」「コード生成」の5つの仕事がある．これらの仕事について順に説明しながら，ソースコードから実行バイナリを生成する過程について記す．
　字句解析とは入力された文字列を字句という意味を持つ最小単位に区切ることである．例えば 'int a, b, c = 0;' という入力に対して字句解析を行うと，'int', 'a', ',', 'b', 'c', '=', '0', ';'といったように区切られる．構文解析（後書き:字句解析）は，字句として受理される文字列のDFAを設計し，それを実装することによって可能となる．
　構文解析とは字句を繋ぎ合わせることに構成される文をプログラミング言語の文法に則って解釈をすることである．例えば 'int a = 0;' という文があれば，「aという変数の宣言と同時に0で初期化する」文であると解釈され，'x = p + q;' という文があれば，「xという変数への代入文であり，p+qの演算結果を代入する」文であると解釈される．このとき，'x, p, q'といった変数が既に宣言されているか，代入や演算の型チェックといったような構文規則の範疇を超えるルールの解釈は，構文解析の仕事に含まれない．BNFなどで定義された構文規則に文を当てはめる際の手法として，LL法とLR法という2つの手法が代表的である．
　LL法は下向き構文解析法の一種で，開始記号から始めて解析木を左下から作っていく．非終端記号の場合，ルールの左辺とマッチしたら右辺の記号で木を下にのばし，終端記号の場合，入力文字列とマッチングを行う．このとき，非終端記号が複数のルールとマッチすると，バックトラックなどにより全てのパターンを探索する必要が発生してしまう．また非終端記号から生成されるルールの最も左側に自分自身の非終端記号が含まれている場合，解析木を左下から生成しようとすると，無限ループに陥ってしまう．これらの問題を解消したものがLL法であり，構文規則を書き換えることで非終端記号にマッチするルールの非決定性及び左再帰性を取り除くことで問題を解消する．LL法は一般にLL(k)と表記されることが多く，これはk個の字句を先読みして，非終端記号にマッチするルールが決定的に求められることを意味する．ゆえにLL法では，構文規則に強い制約がかかるが，実装が比較的容易という長所をもつ．
　LR法は上向き構文解析法の一種で，入力文字列を読み進めながら，自分がどのルールのどこまでを読んだことになりうるのかを全て並列的に考えていく．そのために，まず文法に対応する解析表を作成する．解析表は現在読み進めた状態と入力文字から次の遷移を定義する．表に重複が存在する場合，LR文法を満たしていないこととなるが，多くのプログラミング言語はLR(1)で表される．入力文字列を解析表に従って読み進めることで，文の解析を行い，表に存在しない状態へと遷移した場合文法エラーとなる．
　意味解析は，どのような意味を持つ文であるかを解析するフェーズである．例えば 'x = a + b;' という文があったとき，C言語であれば加算を意味することは構文解析の段階で分かるが，aとbという変数の型が整数型であるのか実数型であるのか，それに伴って整数演算の加算が発生するのか，実数演算の加算が発生するのかを解析する．またこのような文の場合，x,a,bという変数が有効な変数であるかを調べる必要がある．これらの変数が宣言済みであるかどうかはもちろん，aとbは'+'という演算が可能であるのか，演算可能である場合どのような演算となるのか（C++のような演算子オーバーロードがある言語では加算とは限らず，コード生成に関連して整数演算か実数演算かを区別する必要もある），xには代入可能であるのか（定数として宣言されていないか，代入先としてxは適切な型であるか）などを調べる必要があり，これらは全て意味解析の仕事となる．
　コード生成は，実行対象の機械で実行可能な機械語を出力することである．簡単な例では，意味解析によって代入文であると解析された場合には，多くの機械ではmov命令に置き換えが可能であるため，高級言語で記述された代入文に対応する機械語命令を出力する．ここで出力される機械語命令が，実行バイナリとなるが，コード生成によって出力される命令がアセンブリ言語である場合は，更にアセンブラを介して実行バイナリを生成することとなる．
　コード最適化とはコード生成で生成されるコードの冗長性などを排除し，最適なコード生成が行われるようにすることである．コード最適化には多くの最適化手法があるが，代表的なものとして定数の事前計算やレジスタ使用の最適化がある．定数の事前計算とは，定数が計算式によって定義されている場合，素直に計算式を代入するコードを生成するコードを生成するのではなく，コンパイラによって計算可能な部分を計算した上でコード生成を行うことで，計算にかかるコストおよびコードを削減する．レジスタ使用の最適化とは，計算の途中結果などを毎回メモリ領域に退避・復旧することで演算を行うようなコードを，途中結果をなるべくレジスタに退避することで，途中結果の読み出しが高速になり，より高速な計算が可能となる．
　コード生成およびコード最適化に関連して，LLVMという技術がある．これは仮想機械向けの中間コードを入力として受け取り，LLVMの中で最適化を行い，最終的に対象となる機械向けの実行バイナリを出力する．この技術を利用する場合，コンパイラは仮想機械向けの中間コードを生成すればよいこととなり，実行対象となる機械が複数ある場合，各アーキテクチャ向けのコード生成について検討したり，最適化について検討をする手間を省くことが可能となる．

[問3]. C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか？考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。

　私が最も難しいポイントだと感じるところは意味解析およびコード生成である．これらの実装のためには，言語仕様に対する深い理解が必要である．基本的に意味解析・コード生成を実装するのは，言語仕様と機械語の命令セットに基づいて実装するだけであるため，難しさがないように感じる．しかしながら例えば「配列型として宣言された変数に対して四則演算は許されるか」，「ポインタ型として宣言された変数に対して四則演算のうち許されない演算は存在するか」，「負数に対するmod演算はどのように行われるべきか」，「ポインタ型と実数型の演算は可能であるか」など，曖昧な挙動は考え出したらキリがない．このような微妙な挙動について，言語仕様としてどのように定義されているのか調べることも骨の折れる作業なように感じるが，ここでどのように定義されているのか見つけることができればその通り実装すればよいだけであるので，それ以降の難しさはないだろう．ここで言語仕様を見つけることができなかった場合には，自分自信でどのような挙動を取ることが，どのように文の意味を解釈することが最も妥当であるかを検討する必要があり，そのようなところに難しさがあると感じている．
　しかしプロダクトとしてリリースするようなコンパイラを書く場合には，コード生成にはまた違った意味での難しさがあると感じている．例えば当初「配列宣言された要素の中身は全て0で初期化する」コード生成を行うコンパイラを作成したとする．その後，方針変換をして「配列宣言された要素の中身の初期化は行わない」コード生成を行うコンパイラへとアップデートしたとする．このとき，当初の「配列宣言された要素の中身は全て0で初期化する」という挙動に依存したプログラムを書いているユーザが居た場合には，そのようなユーザは影響を受け，言語の元々の仕様が「配列宣言された要素の中身の初期値は保証されない」ものであったとしても，ユーザによっては挙動を元に戻すように主張をするだろう．このように，最適化などの理由から破壊的変更を迫られたとき，どこまでの互換性を残し，どこからの変更を実行するのかという決定を下す必要があるというところに難しさがあるように感じる．

[問4]. 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。

　このゼミに応募したきっかけはいくつかある．セキュリティ・キャンプには魅力的な講義がいくつもあり，当初はどのゼミへ応募するか迷ったが，いくつかの動機が重なりこのゼミへの応募に至った．
　ひとつはTuring Complete FMを聴きシステムプログラミングに興味を持たことである．問1の解答から分かるように，私はシステムプログラミングに関する経験は浅く，せいぜい大学の実験の中でコンパイラを実装した程度である．Turing Complete FMを聴くようになってから，自分自身のシステムプログラミングに関する経験の浅さを感じており，低いレイヤについての理解を深めコンピュータに関する幅広い知識を身に着けたいという想いがあった．そこで，この機会にシステムプログラミングを学ぼうと思ったことが動機のひとつである．
　その他に単純にコンパイラを作りたいという思いもある．実験の中でコンパイラを実装したとは言ったものの前述した通り，このコンパイラはLL(1)を満たすC言語風の構文規則をもつ言語をSEP (Shizuoka Educational Processor) 向けのコード生成をするものであり，更に実装言語もJavaであったため，セルフホストできる喜びや，自作コンパイラによって生成されたコードを手元で実行できるという喜びを感じることができなかった．理論を学ぶことはできたと感じているが，世の中で使われているコンパイラの技術を学ぶことやコンパイラ作りの楽しさを100%実感することができなかったと感じているため，このゼミを通してそれらを学び，実感したいと考えている．
　それに加えて，コンパイラという題材を通じて大規模なアプリケーションの開発のノウハウを吸収したいと考えている．自分が過去に作ってきたアプリケーションはソースコード長が高々合計で3,000行程度のものであると思う．しかしながら保守性や拡張性はイマイチで，今から機能追加しようとしてもどこに手を加えるべきか瞬時に判別ができなかったり，機能追加できたとしても後から読み返したときに何のコードであったのか分かりにくいような設計となってしまうことがほとんどであった．そこで大規模アプリケーション開発におけるノウハウを実際の開発を通じて吸収していきたいと常日頃から感じており，そんなときに「Cコンパイラを自作してみようゼミ」の存在を知った．上述のようにセルフホストのようなコンパイラ作りの楽しさを実感したいというのも，動機のひとつであるが，大規模なアプリケーションの開発のノウハウを吸収したいということも動機のひとつとなっている．

さいごに

　このような稚拙な文章に目を通してくださった講師を含む皆さんに感謝致します．

　今まではIT関係で吸収したことは全くアウトプットしてこなかったけれど，これを機にアウトプットしていきたいなぁ．