hiromi-mi です。セキュリティキャンプの応募用紙のうち、個人情報を削除したものを置いておきます。来年以降応募される方のうちどなたかにでも、反面教師となれれば幸いかなと思います。

当時のものをあえて残してあります。間違いなど多くあるかと思います。

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

(省略) Excel + Visual Basic for Applications でクイズアプリを書いたり、中学校の同級生や後輩に Vim を教えた記憶があります。 また、円周率を計算させるために、逆正接関数を用いたものや、Gauss-Legendre のアルゴリズムを用いたものを MPFR などのライブラリを用いて作成し、それらの計算速度を比べたり、他の言語でも自作して C言語の早さに驚いた記憶があります。

ここから、今まで作ってきたものでインターネット上に公開されてあるものを述べます。

vim-TermSingleton

Vim 8.1 にて :terminal というターミナルエミュレータ機能が実装されたことに対応し、Vim のターミナルエミュレータ機能の中でVim を開くことが可能になりましたが、Vim が多重に起動していると、レジスタなどが共有されないなど不便がありますなので、複数の Vim が開くとき Vim の clientserver 機能を用外側のVim で開くようにしました。

(省略)

ljmp

Build Your Own Text Editor - Jeremy Ruten をもとに実装したテキストエディタです。 この文章中で取り上げられている、基本的なモードレステキスト編集や、検索機能、構文強調機能に加え、日本語への対応や、コピーペースト機構、あるいは簡易なテキスト補完機能を実装しました。もともと 「1バイトが一文字」の考えなチュートリアルを自分の考えて多バイト対応させるのに苦労したおぼえがあります。

hanando-fukui

3月ごろから 実装していた C コンパイラです。万が一参加できることになれば、これを改造することになると考えています。

そのほか、(省略)

最後に、挫折したものは多すぎて書ききれませんが、例えば 正規表現エンジンの Oblaka (正規表現エンジンでは、正規表現をコンパイルして、JIT上で文字列を処理させることが多いですが、コンパイル部分がうまく動作しなかった) などがあります。

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

C言語での過程について説明します。

まずコンパイラはソースコードを読み込みます。ソースコードから入力された文字列を、Token の列に分割します。そこで、ただの連続した文字列を、要素別に分割します。 たとえば「345」といった数値であれば、int型の 345 という内容に置き換えたり、"文字列" を char型のポインタを用い持つようにします。 改行や空白など、C言語においてさしたる意味を持たないものは、ここで排除してしまうこともありますが、後述するプリプロセスでは改行が区切りとして意味がある場合があり、hanando-fukui の現時点での実装では TK_NEWLINE, TK_SPACE として残してあります。

そののち、プリプロセスを行います。#define A B などとA の内容をB に置き換えたり、#include で他のファイルを取り込む (その際Tokenize とプリプロセスは再帰的に行なわれる) ことです。 なお、C言語においては、おおむね ; を区切りとしていますが、プリプロセスでは (; に影響されないようにするためでしょうか) ( \ 記号を除き) 改行をプリプロセスの区切りとしてあります。なので、hanando-fukui では、TK_NEWLINE, TK_SPACE をこの段階まで残し、プリプロセスの #include 文などの終わりを判断するのに使っています。 あるいは、この後で改行をもって判断する必要はなく、この段階で TK_NEWLINE, TK_SPACE を削除しています。

次に、構文解析を行います。演算子や数値、変数などをノードに持つような木構造として今迄のデータを持つようにします。hanando-fukui では、再帰下降構文解析を行なっています。まず、Node という構造体で再帰的に木構造を表現します。木構造を生成するのには、文法規則の優先順位に従って作った再帰関数を用います。これにより、加法より乗法が優先されるといった演算規則が、再帰関数を呼ぶ際に、node_add() を呼ぶか node_mul() を呼ぶかの違いとして表現できます。

その後に analyzing process を行います。そこで、構文解析時に検出できないエラーを検知したりします。 例えばに、C言語の仕様上では、構文解析しただけでは検知しにくいエラーがあります。 ポインタとポインタの加算はエラーですが、構文解析時に (少なくとも hanando-fukui では) 左辺と右辺の型情報を持っていないため、チェックすることが難しいです。 なお、現状の hanando-fukui では、analyzing process とコード生成時がごちゃまぜになっています。

そして、必要に多じ 最適化プロセスを行います。 たとえば i = (1 << 2); などといった定数同士の演算を先に実行しておき、i = 4; とします。 また、高度な例として、for 文のインライン展開があります。

for (int i=1;i<=10;i++) { <stmt>; }

を、<stmt> の10回の繰りかえしとして実装するものです。これにより、条件分岐処理を省くこバイナリサイズが肥大化するものの <stmt> の実行が速くなることが期待できます。 (hanando-fukui で実装してみようかとも思いましたが、 ad-hoc な形での実装以外思い浮かびません…) なお、今迄のanalyzing process までは、生成したいバイナリのアーキテクチャに関わらず普遍的に作れるものでしたが、ここからは、生成したいバイナリのCPU がどのような命令を持っているか、それぞれの命令にはどのような (時間、メモリなど) 制約があるかに依存します。

最後、具体的にアセンブリコード (あるいはバイナリ) を出力します。 hanando-fukui ではアセンブリコードを上から順番に出力するようになっているため、グローバル変数などを事前に .comm 疑似命令などを使い生成し、そのあと順番にアセンブリコードを出力します。当然これは出力する対象のアーキテクチャごとに異なります。 もちろんアーキテクチャごとに命令は異なりますし、風変わりなところでいえば、構造体のメモリ配置があります。

struct Foo {
int a;
char b;
char c;
int* d;
};

という配列を考えます。メモリ上で最も場所を使わない配置を考えると、

  • a: (アドレス) 0,1,2,3

  • b: 4

  • c: 5

  • d: 6,7, …, 13

となりますが、実際は、v := その変数の型のバイト数 として、アドレスはv で割り切れないといけません。また、これを満たすようにして、なるべく詰められてなければなりません。 なので、

  • a: (アドレス) 0,1,2,3

  • b: 4

  • c: 5 (char は1バイトなので)

  • d: 8,9, …, 15 ( int* は8バイトなので)

となります。hanando-fukui ではこれを最初誤解しており、gcc でコンパイルされた構造体を扱う関数を hanando-fukui でコンパイルされたものから呼び出すと動作しない、といったバグになっていました。 話をもとにもどします。この段階ではABI も重要です。 例えば関数を呼び出す際、(可変長引数など例外がありますが) rdi, rax,…のレジスタに順番に引数の内容を格納し、戻り値はrbp レジスタにしまうようになっています。これはおおむねアプリケーションを実行するもの、具体的にはおおむねOS が定めています。これに従ってコンパイラはアセンブリコードを出力します。 以上は、C標準ライブラリだけを使った関数であっても、Windows 環境と Linux 環境においてアセンブリコードが (表記の方法以外でも) 異なることの理由でもあります。

以上が基本的な経過ですが、gcc などのコンパイラにおいては、具体的に出力する前に中間言語を出力し、それに対する最適化プロセスを行ない、最後にアセンブリコードを出力することもあります。

ここから、アセンブラが、具体的な命令に翻訳します。 これはアーキテクチャごとに大幅に状況が異なります。

最後にリンカを用い、実際に実行できるプログラムを生成させまkす。 これは、ほとんどのプログラムは何かしらの外部ライブラリに依存しており、それを動的あるいは静的に繋げて関数を実行時に呼び出せるようにする必要があるからです。 リンカでは、まずアセンブラで出力したELF ファイルを読み込みます。また、(ほとんどの場合) /usr/lib/libc.so などのstandard library も読み込みます。 その中に含まれるシンボルテーブルを解析して、先のファイルで再配置が必要な箇所 (PLT32 など ELF のシンボルテーブル中に記されている) を見つけます。その後、standard library のどのファイルのどのシンボルが該当するものかを見つけて、静的リンクならファイルをELFヘッダなどを分けて結合します。一方動的リンクなら別途ELF ローダーに動的リンクである旨の指示をELF ヘッダにつけて、最後にバイナリを出力します。

ちなみに https://github.com/hiromi-mi/portlinker というリンカの書きかけで、時間不足で途中で放置になっているものがあります。 もしhanando-fukui の完全な自己完結を目指すとならば、これを復旧させることになるかなと考えています。

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

セルフホストにたどりつく前の考えと、たどりついた後では変化したので、その両方について記します。

開発前 (3月時点)

構文解析の部分が難しく感じました。

ここでいう「難しさ」は、理論を読んでも、実際にソースコードでどのようになるのかイメージできずにいました。 例えば、トークンを生成したものを LR(1) 文法で読み取る、とだけ書かれてあっても、 どのようにデータ構造を持てばいいのか、再帰的に解けばいいのかfor なのか、理解に困難を覚えていました。 これはこのゼミの教科書にある説明のおかげで何となく理解できたように思えます。これは具体的にソースコードが書かれていたからだと思います。逆にいえば、理屈をきちんとソースコードに打ち込む能力の不足を感じさせられます。

セルフホスト達成後 (5月時点) に感じていること

バグを生み出さないようにする、あるいはバグの原因をつかんで解決することが難しく感じています。 例えば、(極論ですが) 構文解析などの理屈を理解するのには、(競技プログラミングや数学など) 他の能力が高かったり、分かりやすい前例があればある程度乗り越えられるとも感じました。

それとは異なり、バグを見つけて取ることには、長い経験が必要で、かつ手元ではあまりうまく文章の形で残せない経験のようなものが必要ではと感じます。

hanando-fukui で生み出したバグを取り上げ、以上の考えに至った経緯を説明します。 セルフホスト間近の状況です。(clang でコンパイルした第一世代の hanando がある状況で、それでコンパイルし生成された第二世代のコンパイラがうまく動作しない状況でした。そのなかで沢山のバグを取ることになりましたが、第二世代コンパイラが「動作しない」ということしか分からず、どこがおかしくなっているのか探索するのに苦労しました。 関数ごとに呼び出して動作がおかしいであろう関数で、セグメンテーション違反になるところをgdb で見つけて、その部分を逆アセンブルしました。そして、コンパイラが出力したアセンブリに対応するC言語ソースコードを見つけ、その部分がなぜそうなっているのかprintf などを入れて調べる… これを繰りかえして疲れを抱きました。 例えば、continue; 文 をコンパイラ内でよく使っていますが、それが異なる場所に飛んでいることに気付き、その原因は break; 文は continue; 文とは違い、switch 文中でも使えることを失念して、continue; 文もswitch で分割するようにした影響でした。 また、charとint 型との比較において、なにも考えず32-bit の領域で比較するようにした結果、char 型の中に未定領域が発生することに気づかなかったこともありました。いつか一致するはずの *p++ == '\0' でエラーとなり、そして無限ループで終了しなくなりました。 などなど、途方にくれることもありました。

バグを見つけてなくしていく上で、以下のような対処が有意義だと感じました。バグを生まないようなプログラミング (思考) をセキュリティキャンプなどで少しでも身につけられたらよいと思います。

バージョン管理の意味

以前から Git、MercurialやPijul などでソースコードをバージョン管理下におくようにしていましたが、その有用性をあらためて感じました。 ソースコードを動く単位でコミットするなどして、「万一うまくいかない場合は戻す」ことができます。そして、git bisect を使うことで、どのコミットが原因なのかを特定することもできます。更に、コミットメッセージを書けば、どの機能をいつ実装したのか、なぜバグを生んだのかを書き残すこともできます。

テストコードを書く

テストコードを書くことで、ちょっとした変更がもたらす影響をすぐ把握できるようになりました。 予想外の場所に影響することが高い確率で把握できます。 ただ、複数の処理を単一のテストコードで書くことをあまりしなかったために発生したバグもあり、今後結合テストのように結合して処理させることもしたいと感じます。

問題のある部分を適切に切り出す

(これを事前に行なったのがテストコードを書くことかもしれません) 具体的には、hanando-fukui の samples/ フォルダの下にあるファイルですが、セルフホスト直前になって、どこの挙動がおかしいか調べるために、hanando-fukui 本体のソースコードからバグが発生してそうな箇所を抜き出してテストしました。このおかげで、本体の膨大な (1万行程度です) アセンブリコードにかわり、100行程度のアセンブリコードを相手に絞り込むことができるようになりました。

バグの記録を残す

バグを見つけて解決した際、なぜ解決できたのか、なぜ生んだのか (考慮漏れなのか、そもそも実装していない機能に依存していたのか、仕様の勘違いなのか) をコミットログなしは手元で意識することで、典型的なバグのパターンを少しなりとも見つけられるようになりました。

例えば、最初型の概念をまともに持たず、全部 unsigned 64-bit 扱いしていたため、途中からコード生成部分や、新しい演算子を実装する際に、出力するのがこの型で正しいかどうか、気をようになるなどがありました。

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

今後やりたいことの案と、それに対してどんな技術的取り組みをすることになりそうかを書きしるします。

0. レジスタマシンへの移行

スタックマシンでは、余計な pop や push 命令が多数発生し、それを最適化するのも手間がかかりそうです。なので、レジスタマシンに移行したい気持ちです。

どのように実装すればよいのか分かっていないのが演算処理です。スタックマシンでは + を 左辺と右辺を計算したものを pop して加えて push する、というふうに実装できましたが、レジスタマシンでは加えた結果をどのように持つかが問題になります。 gcc のソースコードをコンパイルしてみると、rax, rdi などに順番に演算結果を入れているように見えますが、例えば 1 + (2 + (3 + (4 + (5 + ....) )))))) と続いたときに、(最適化しない前提で) レジスタが全て埋まってしまうのではないか、さてどうしよう、ということで止まっています。

1. デバッガの支援

セルフホストが近くなると、前述の通り苦労しながら沢山のバグをとることになりました。その時はprintf を使い(第二世代コンパイラの) 変数の値を眺めるようにしていましたが、何度もデバッガがほしいと思わされました。 そこで、デバッガの出力を支援するデータを与えて、今後の開発を楽にできるかと思います。

まずやりたいと思っているのが、行番号機構の実装、つまりCソースコードベースでのステップ実行と、変数の値の表示です。 そのためには、デバッガに CFI (Call Frame Information) などを与える必要があります。以下分かっていることを列挙すると:

  • 関数を .cfi_startproc と .cfi_endproc で囲みます。

  • push や pop があったときには、.cfi_def_cfa_offset として Call Frameのレジスタが移動したことを表します。

  • それぞれのレジスタの位置を、.cfi_offset [レジスタ名] [オフセット] として、記録しておきます。

  • アセンブリ中に現在のC言語中での行番号を打ち込むには、 .loc 疑似命令を使います。

ただ、clang やgcc でコンパイルしてみると、ソースコード本体を出力したあとに、.Ldebug_info として、変数名と対応する長い情報が付いていますが、まだこれが何なのかを把握できずにいます。

この項の参考文献

  1. Info Page of GNU as

  2. デバッグ情報を探る 〜.cfi_xx命令の動作〜

2. C言語標準への準拠 / double などの浮動小数点型の実装

特に初期の実装について、C言語の標準から乖離している箇所が多くあります。 例えば、C言語の仕様では、宣言と文や式が明確に分割されていますが、手元では明確には分離されておらず、その場しのぎになっています。例えば、goto 文などがgoto 式で扱われるようになっています。きれいにしようとしすぎて以前失敗した Oblaka などの例を思いだし、「セルフコンパイルするまではリファクタリングは避けよう」と考えて、ここまであえて放置していました。

現状 double 型を実装するためには、 mov 命令を、movzl などと型に応じて書き換える必要がありますが、現状コード生成プロセスにおいては、ほとんど mov を出力するだけのソースコードになっており、そこを処理する必要があります。

3. 警告の充実

C言語の仕様をうまく実装できてからになりますが、analyzing process をうまく使うことで、コンパイルする際に、未初期化の変数を検出するなどできるのではないかと考えました。 例えば変数を持つNode型に is_used is_initialized などの真偽値を導入し、構文解析の途中で、変数が使用されたり、代入されればtrue にする。analyzing process でその変数を読む際に、もしそこが false であれば警告を出せると思います。 また、単純なものに限りますがfor 文が無限ループになってしまう例を警告できるとも考えています。

for (int i=10;i>=1;i++ ) {
// i++ から i-- にするのを忘れている
 // for 文の中に break や return がない
}

もちろん汎用なコンパイラではあまりこのような局所的な例に手間をかける意味はないと思いますが、セキュリティキャンプで作れるものとしたら、個性として持っておいて損はないと思います。

4. C++/Objective-C (Subset) Compiler を目指す

これはひとりでは到底出来る規模ではなさそうで、もしやるとしても複数人で分担することになりそうです。もちろんC++ という複雑な言語を丸ごと実装するのは困難であり、適度に省略することになりますが…

まずやるとすれば、クラス機構の実装でしょうか。これは構造体を拡張すれば可能だと考えています。 ただ、山場となるのは仮想関数の実装だと考えています。普通の構造体と異なり、関数ポインタのテーブル vtable のアドレスを持たし、そのアドレスを間接的に参照し呼び出すことが必要です。

参考文献: C++で学ぶ！メモリレイアウトとvtableのすゝめ　〜動的ポリモフィズムを実現する仕組み〜

さらにそこから実装していき、テンプレート機構まで向かいたい気持ちがありますが、どのように実装すればよいのか見当もついていません。

また、これについては目標設定も悩んでいます。STL を使えるようになるには、テンプレートまでなど相当量を実装する必要があり、おそらく無理だろうと考えています。しかし、標準ライブラリをC言語のライブラリで代用すると、「C++ だ」と見せられるような素材に欠けるように思います。

そこで、別案として Objective-C のコンパイラを目指す手も考えています。

Objective-C はC言語を主軸にSmalltalk 由来のオブジェクト指向を加えたもので、NEXTSTEP をはじめとして、今でこそSwift が普及したものの、macOS や iOS 上での開発でよく採用されています。また、今でも GNUStep に依存すれば Linux 環境などでも動作します。 呼び出すメソッドを動的に変更できたり (-performSelector: など) 、カプセル化を無視してみたり、(カテゴリを使って) 既存のクラスに要素を追加できるなど異なる性質を持つおもしろい言語です。C++ と比べ言語仕様が小さく、クラス機構を実装してGNUstep にリンクして動かせたりしないかな、などと思っています。

(この両方を実装し、オブジェクト指向の実装上での違いについて振りかえる文章を書けるとおもしろいのでは、とも思います。ただそれだけの規模について考える時間はないと思います。)

5. 最適化

勿論最適化もおもしろいのではないかと考えます。レジスタマシン実装後、計算できるところは先に計算するなどできればと思います。また、C言語の簡易なインタプリタを内部に組込むことで、C++ 言語における constexpr 定数式 のようなものを再現して、コンパイル時に計算を終わられられればよいのかも、と思います。

以上、あるいは他に他のアーキテクチャへの移植や、OSなし環境への対応などがやっていけたらなと思います。

OSS活動について

(後略)