はじめに

弊社Flatt Securityでは学生の学びを支援したいという想いから今回少額ではありますが高橋さんの留学を支援させていただき、そのご縁で弊社のYONEUCHI, Takashi (@lmt_swallow) | Twitterもスタッフを務めるセキュリティミニキャンプにおける素晴らしい講義の内容をテックブログに書いていただけることになりました。以下本文になります。

@00_ です。今年の夏のUC Berkeleyへの留学費用をFlatt Securityさんに支援して頂いた経緯で、セキュリティミニキャンプの講義内容についてテックブログで書くことになりました。

2019/09/28-2019/09/29 のセキュリティミニキャンプ山梨で「ミニキャン言語を作ってみよう！」の講座を行いました。この講座では、「ミニキャン言語（MC言語）」という独自言語のコンパイラを、自分がコミッタでもあるLLVMというコンパイラ基盤を用いて作りました。本記事では、行った事前学習とその内容について紹介します。

専門講座1つ目の講義はセキュリティ・キャンプ全国大会2016修了生髙橋祐花氏による『ミニキャン言語を作ってみよう！』です。参加者はなんと既に事前課題として LLVM バックエンドの言語を実装しており、本日はその成果を一人一人発表する日となっています。#seccamp pic.twitter.com/lp6PVgwbv7
— セキュリティ・キャンプ (@security_camp) 2019年9月29日

午前中の講義の熱そのままに、お昼ごはんの最中にも自作コンパイラについての発表がなされていました。#seccamp pic.twitter.com/Ci2BWi0Ph7
— セキュリティ・キャンプ (@security_camp) 2019年9月29日

講義『ミニキャン言語を作ってみよう！』の全参加者の発表が終わりました！どの発表もよく自分の実装や今後の課題が丁寧に説明された、とても素敵なものでした。負の即値や浮動小数点数を扱えるようにしたりなど、課題の言語仕様にはない機能を追加する参加者もいました。#seccamp pic.twitter.com/z4arVYkgoK
— セキュリティ・キャンプ (@security_camp) 2019年9月29日

セキュリティ・ミニキャンプ in 山梨 2019 の全プログラムが終了しました。お疲れさまでした！ #seccamp pic.twitter.com/UJCEKecckg
— セキュリティ・キャンプ (@security_camp) 2019年9月29日

概要

本講義では、講義日の三週間前から事前課題の出題を開始し、参加者の皆さんに解いて頂きました。事前課題は完成まであと少しのMC言語コンパイラの実装と誘導を元に、穴埋め形式でインクリメンタルにコンパイラを動かせるようにしました。当日の150分の講義時間中では、参加者の皆さんに事前課題や発展課題で行った内容を発表してもらうという形式にしました。

このような講義形式なのでサポートもしっかりと行う必要がありました。kintoneで参加者と講師が連絡を取れるようになっており、少ない日でも一日20件ほどの質問を受けました。

スケジュール

09/08　第一回事前課題出題
09/13　第二回事前課題出題
09/18　第三回事前課題出題
09/29　講義当日の発表会＠山梨

最終的には、以下のように再帰を含んだミニキャン言語（MC言語）のコードがコンパイルできるようになります

def fib(x)
    if x < 3 then
        1
    else
        fib(x-1) + fib(x-2);

この講義では、事前課題を一つ一つやっていくことで、このようなチューリング完全な言語が実装出来るようになっています。

今回のコンパイラでは、大きく分けてLexer, Parser, Codegenという三つのステップがあります。Lexerは与えられたテキストファイルの文字列をトークンに分割し（例えば、"12+345"という文字列を、12, +, 345のトークンに分割する）、ParserはAST（構文木）を構成し、Codegenでは構成されたASTから再帰的にLLVM IRを生成するという役割があります。

第一回事前課題

事前課題1では、数字と二項演算子のみからなるexpressionをコンパイルし、オブジェクトファイルを得ることが目標です。この課題を終えると、以下のような簡単な構文が正しくコンパイル出来るようになります。

# This is a comment
;;;;;;2
(4*2) - (4+3) * 9 + 2 * 2 - 1; # Able to handle '-' and '*'

第一回事前課題には全部で7のセクションがあり、そのうち実装のセクションは以下のようになっています。

f:id:yamaguchi_1024:20191019153341p:plain — 第一回事前課題実装セクション

詳しくはGitHubのソースコードのコメントに書いてありますが、この回では数字のトークナイザ（与えられた文字列を数字のトークンに分割する）、#で始まる行をコメントとして無視する、(ではじまり)で終わる中身を括弧としてパースする、+,-,*等の二項演算に対する構文木を構成しLLVM IRを生成しました。

ミニキャンプでは様々な参加者がいるため、事前課題全てに以下のような丁寧な誘導を付け、プログラミング初心者でも付いてこれるように工夫をしました。

f:id:yamaguchi_1024:20191019153059p:plain — 事前課題1.3の誘導コメント。この課題では、前述した数字のトークナイザを実装する。

f:id:yamaguchi_1024:20191019153002p:plain — 事前課題1.5の誘導コメント。この課題では`(`ではじまり`)`で終わる中身を括弧としてパースする実装を行う。

第二回事前課題

第二回事前課題では、関数定義と関数呼び出しを実装し、C++のmain関数とMC言語で生成したオブジェクトファイルをリンクし、ELFファイルを作り実行します。この課題を終えると、以下のような簡単な構文が正しくコンパイルできるようになり、さらに実行できるようになります。

def foobar(x y c)
    x + y - c;

def myfunc (x y)
    foobar(x, y, 5);

上記の様な名前の付いた関数を定義出来るようにする為、def, foobar, (x y c), そしてx + y - c;をパースし、codegen出来るようにしました。

f:id:yamaguchi_1024:20191019154349p:plain — 事前課題2.2の例。この課題では、現在見ている識別子が引数(変数)の参照か関数の呼び出しか判別し、引数をパースして新たなASTノードを作る。

また、コンパイルが出来るだけではなく実際のELFファイルから実行できるようにする為に、MC言語のオブジェクトファイルをC++のファイルにリンクすることによって、main関数からMC言語で定義した関数を呼び出せるようにしました。

第三回事前課題

最終回である第三回事前課題ではif, then, elseを用いたコントロールフローを実装し、フィボナッチ数列の計算が再帰的に行えるようにしました。これで、「プログラムを順次実行する」「プログラムが条件分岐する」「プログラムが（再帰により）反復する」というプログラミング言語の基本構造を全て揃えたことになり、チューリング完全な言語が出来ました。

実際の事前課題、細かい実装の話は全て事前課題のGitHubに書いてありますので、興味がある方は見てください。

発展課題

また、誘導付きの事前課題では物足りなかった方向けに誘導なしの発展課題も以下のように準備しました。当初は解かれることをあまり想定していなかったのですが、全ての発展課題を一人以上の参加者が解いてくれました。

fibより複雑な例をMC言語で実装する
>, >=, <=, ==等の比較演算子を実装する
負の数を読み込めるようにする
externを実装し、外部ライブラリの関数を呼び出せるようにする
三項演算子を実装する
for文を実装する
変数を実装する(グローバル変数でも可)
変数のスコープを関数内に制限する
intだけでなく他の型もサポートする(上級)
UEFIアプリからミニキャン言語で作ったバイナリを起動する

10の「UEFIアプリからミニキャン言語で作ったバイナリを起動する」という発展課題はもう一人の講師の内田さんの講義と連携し、内田さんの講義で作ったUEFIアプリからミニキャン言語バイナリを起動できるようにする、という講義横断な面白い課題でした。

発展課題の様子は、発展課題10を解いた方のこちらのツイートや、発展課題5を解いた方のこちらのブログで確認出来ます。

参加者の反応

講義中に取ったアンケートの結果から、概ね満足してもらえたと考えています。参加者が発表するという形式、事前課題については多くの方に非常にポジティブな回答をして頂けました。また、事前課題に書けた時間は数時間から数十時間までばらつきがありましたが、平均的には合計15時間程度の時間を使った人が多かったようです。

自由記述の欄では、多くの参加者の方から「（普段とは違う事が出来て）楽しかった」とコメントを頂けました。他に、発表時間が少し長引いてしまったことについて「時間厳守にしてほしい」というコメントも頂いたので、この点は反省しており次回に活かそうと思います。

以下は参加者の皆さんによる、参加記です。

セキュリティ・ミニキャンプ in 山梨 2019 参加記 - task4233のめも diaryです

講師を引き受けた責任を結構重く感じていた為、きちんと終えることが出来てとても安心しています。私自身も学ぶことが多くとても楽しかった為、このような機会があればまた参加したいなと思いました。