Explore "Full-Stack" in depth!

情報系の専門学校で、今は機械学習に的を絞って学習中。プログラミングを趣味でやりつつ、IT系のあらゆる知識と技術を身に付けるべく奮闘中。

Seccamp2019でCコンパイラ実装に取り組みました

概要

セキュリティ・キャンプ全国大会2019に参加しました!
集中開発コースの中にある 「Y-Ⅱ Cコンパイラを自作してみよう!」のテーマに応募し、
普段独学では絶対に出来ない事を多く経験し、
尊敬する講師の方々からたくさんの事を教えて頂きました。

セキュリティ・キャンプ(以下seccamp)とは?と思った方は
こちらのページを参考にしてください!

この記事では、

  • 応募課題はどんな内容のものだったか
    • 提出したものをそのまま載せます
  • 集中開発コースはどのようなものだったか?
    • 特に Yトラックについて詳しく
  • 成果物の進捗、所感
  • 総評

という流れでお話できればと思います。

来年以降seccampに参加しようとしている方の参考になれば幸いです。

注意:応募課題についてですが、
応募時点での状況、応募時点での知識を元にした内容が書かれています。
コンパイラの知識として間違っているものもあり、
また現在はラボユースとして活動していない等、
いくつか現時点とは異なる部分もあります。ご了承ください。

応募課題について

seccampでは参加したいコースを選んだ後、
各コースが用意する設問に解答した上で応募する必要があります。

私達Yトラックの課題はこちらに記載されており、
4/15~5/27の間に問題に答えて提出する、という流れでした。

問題はトラック・コースによって様々なのですが私が個人的に抱いた感想は、
「うわぁ、どのコースもその分野をどれだけ好きか問うているなあ」というものでした。

例えばCコンパイラゼミでは、

  • プログラミングそのものに対する熱意
    • コンパイラ実装には 実装に大きな時間と労力を要する
  • コンパイラの役割・用いられている技術に対する知識
  • 実際にCコンパイラを書いたことがあるか、又はCコンパイラ実装に具体的なイメージが湧いているか

等、
まさにコンパイラについての思い・情熱を答える問題が用意されていました。

ここではその応募課題(4問のうち3問)を記載したいと思います。
参考になるかどうかはわかりませんが、
どちらかというと 後々自分自身で見返したいという気持ちがありますね…

今見返してみるととても恥ずかしいですね。
コンパイラについての勉強は
応募課題を描き始めた4月にし始めたこともあり、
少ない知識からとにかくたくさん書いた記憶があります。
ということはコンパイラの勉強を始めて4ヶ月ぐらいが経過したということになりますね。
なにか成長できたのだろうか…

以下に各問の回答を示しますが、 応募時の内容を一切改変せず記載しています。
冒頭に述べたように 現在とは状況が異なり、間違っている知識が含まれている可能性がある点をご了承ください。

問1

問2

問3


集中開発コースについて

後述しますが私は選択コースに参加したわけではないので、
選択コースの魅力・内容を十分に理解していません。
よってあくまでも集中開発コースについての内容のみ取り上げることにします。

自分のやりたいもの、受けたい講義を幅広い種類から選択し、
それらを受講することで知識を深める 選択コースとは異なり、
集中開発コースはまさに 一本勝負 といえるコースです。

いくつかのテーマがありますが、
Yトラックでは

の2つが存在し、
(事前学習+)3日間OS/コンパイラを書き続けるという夢のような時間を過ごす事ができます。

やりたい事が一つに定まっている且つ、
とにかく"実装したい"という熱意がある人には、集中開発コースはおすすめです。

各ゼミによって差異はあると思いますが、
Cコンパイラゼミでは 受講生が自主的にゴリゴリ進めていきつつ、
講師の方が適宜助けてくれる、というスタンスでした。
これは事前学習の時期でも当日でも変わりません。

受講生全員がCコンパイラを書いている ので、
受講生同士で 「この実装どうやりました?」みたいな会話もあって凄い充実していました。

私は普段学校やサークルで勉強しているときも、
周りにコンパイラ・言語処理系の勉強をしているひとがいないので、
こんな環境憧れだなあと思っていましたね。


成果物とその進捗について

今回seccampで私が実装したコンパイラは以下のリポジトリに置いてあります。
何故アーカイブしたのかについてですが単純で、

  • seccamp2019の取り組みでやったものとして保持したかった
    • 後々見返して駄目だったところ等見返したい
  • 確実にもう一度作り直すが、そのときには 新しくリポジトリを作りたい

という理由です。

github.com

事前学習期間と当日に分けてそれぞれ追っていきます。

事前学習期間

Cコンパイラにあてた時間というのはかなり長くて、
応募した段階で取り組み始めていました。

しかし "インクリメンタルな開発"から離れた方法で実装していた為に、
何度もつまづき、かなり歯痒い思いをしていました。

具体的には、

  • まずC言語の仕様を読んで完全準拠したLexerを作ろうとする
    • 全部の予約語に対応して、小数も整数もやって、みたいな
    • 結果的に コード生成まで結びつかないコードが何百行もある みたいな状態になっていた
  • 次に 構文解析を延々書きまくる みたいなことをしていた
    • それらも全てコード生成出来ない、みたいな
  • 実際にコード生成出来ていたのは加減算だけだった

みたいな感じです。
これは コードの全体感が全く把握できないし、
モチベーションも上がりません。
また コード生成まで結びつかないコードが大量にある為に、
テストも非常にしづらい みたいな状況になっていました。

そこで講師のRuiさんから もう一度作り直したほうが良いという旨のアドバイスを頂きました。
結果、セキュキャン当日まで開発していたコンパイラを作り始めたのは 7/8 ということになります。

twitter.com

これは7/15日の状態です。
このときは RuiさんのCコンパイラブックを参照しながら 実装していました。

twitter.com

その翌日ですね。
引数ありの関数呼び出しができるようになったみたいなやつです。

このときになって
やっぱりインクリメンタルな開発って大事だなあと痛感しました。
ここまで実装したコードが全てコード生成に結びついており、
全てのコードを 何のために書いたのか説明できる 状態だったからです。

twitter.com

7/23、ポインタが実装出来た部分かな?

twitter.com

ポインタ演算ができる様になっていますね。
実はこれが 事前学習期間の最後の進捗 となってしまいます。

このあと配列の実装に着手するんですが、
これがわからなすぎて 悠久の時を過ごしました

このときは あぁ、当日も三日間配列の実装に手こずったまま終わるんだろうなあとか思っていました。

当日

1日目、この日はコースごとの活動は行わず、
全体で講義を受けたりする時間が大半を占めていました。

日中の活動が終了し、
自室に戻って私がしたことは 正規表現エンジンの実装 でした。
配列実装がトラウマになっていて逃げていたのかもしれません。

twitter.com

一応コンパイラには関係あるんですよね。
タイガーブック では字句解析器を実装する方法として正規表現が取り上げられており、
今まで手書きしかやったこと無いなあと思って取り組んでいました。

2日目、いよいよコースでの活動が始まりました。

肝心の配列実装はというと、講師の方々にアドバイスして頂いたおかげで案外パクっと出来てしまいました。

twitter.com

事前学習期間延々悩んでいた事が数時間で実装できて、
とてもスッキリした気分でした。

twitter.com

次に実装したのは グローバル変数 ですね。

あとは char型と、'A'みたいなリテラルの実装をやりました。

私は #100DaysOf精進#100dPeach等、
毎日の進捗をツイートしているのですが、
キャンプ中も変わらず実施していました。

twitter.com

三日目です。変わらずコンパイラを書きまくります。

twitter.com

文字列リテラルが実装できた瞬間です。
これはかなり感動したなあ。

twitter.com

構造体実装の瞬間。
うおお、プログラミング言語になってきている! という実感がありましたね。
ハリボテ実装感は否めないのですが。

Tweetはしていないのですが、

int x = 30; のような初期化式みたいなのも簡易的にやりましたし、

0b10010 , 0777 , 0xff みたいな2進8進16進リテラルの実装もやっていました。

3日目の終わりのほう、
あ、これセルフホストは出来ないかもなみたいな諦めが生じ、

だったら他にできる事をやろうと思い、
float型の実装に着手しました。

twitter.com

4日目の様子です。

C言語

int main(){
    int x = 30.0; //小数リテラルが整数に型変換される
    float y = 30; //整数リテラルが小数に型変換される
    int z = x + y; //加算時にxがfloatに型変換された後、計算結果のfloatをintに型変換して代入される
}

みたいな特徴があるのですが、
これの実装をやってみたくなりました(何故)

gcc -S -O0 -masm=intel -fno-asynchronous-unwind-tables の吐くアセンブリを見ると、

   .file    "c.c"
    .intel_syntax noprefix
    .text
    .section .rodata
.LC1:
    .string  "%d\n"
    .text
    .globl   main
    .type    main, @function
main:
    push  rbp
    mov   rbp, rsp
    sub   rsp, 16
    mov   DWORD PTR -12[rbp], 30 ;30.0が変換された状態でストア
    movss xmm0, DWORD PTR .LC0[rip]
    movss DWORD PTR -8[rbp], xmm0 ;30を変換しストア
    cvtsi2ss  xmm0, DWORD PTR -12[rbp] ; int xを変換しつつxmmレジスタにロード
    addss xmm0, DWORD PTR -8[rbp] ; float同士の加算
    cvttss2si eax, xmm0 ;整数型に変換し
    mov   DWORD PTR -4[rbp], eax ; 格納
    mov   eax, DWORD PTR -4[rbp]
    mov   esi, eax
    lea   rdi, .LC1[rip]
    mov   eax, 0
    call  printf@PLT
    mov   eax, 0
    leave
    ret
    .size    main, .-main
    .section .rodata
    .align 4
.LC0:
    .long    1106247680
    .ident   "GCC: (Ubuntu 8.3.0-6ubuntu1) 8.3.0"
    .section .note.GNU-stack,"",@progbits

みたいな感じになっています。
私は意味解析時に型を変換するところまでは出来たんですが、
cvttss2si 命令等を使ってアセンブリで変換する、みたいな事ができなかったですね。
これはCコンパイラを再実装したときの課題にしたいなあと思っています。


総評

ここまでプログラミングに本気になった3日間はなかったし、
コンパイラ実装について多くの事を学べるとてもいい経験が出来ました。

同じことに熱意を持っている人と知り合う事ができたし、
考え方が大きく変わったという意味でも凄いイベントに参加できたなあ、と思っています。

twitter.com

twitter.com