星にゃーんはセキュリティキャンプ全国大会2019の卒業生です。Cコンパイラを作るもくもく型のゼミに参加して、hoc_nyanというCコンパイラを書きました。
セキュリティキャンプ勢?の中の慣例として、応募課題を晒す流れがあります。僕も公開したかったのですが、どうしても応募課題のテキストファイルが見つからなかったため断念しました。
……時は流れ、2022年。普通にMacのメモ(iCloudに保存されるやつ)にあるのを見つけたので、落ちた2017年、2018年のものも含めて公開します。 2017年は言語自作ゼミ、2018年と2019年はCコンパイラゼミに応募しました。
今も言語作ったりコンパイラ書いたりしてるので、割と初志貫徹してるみたいです。
2017年 言語自作ゼミに応募
応募課題の内容は覚えてませんが、内容からなんとなく察せるかと思います。 当時は大学のB1でした。
1(1) ペイントソフト, GUI付きのオセロ, ポーカーの役判定, 小さなLispインタプリタ, RPN電卓, タイマー, ブロック崩し, 市販のロボットをWiiリモコンで操作できるようにした, ライフゲーム (2) * ペイントソフト(C++, Siv3D) Siv3Dというライブラリを用いて作成した。 * オセロAIとWebサイトの技術を応用したGUI(Common Lisp) ミニマックス法などを用いてオセロのAIを実装。 Electron(Atom)のように、Webサーバーをローカルに立て、ブラウザをGUIとして使用した。 https://github.com/takoeight0821/othello で公開している。 * ポーカー(Common Lisp) 日本でもっともポピュラーな5枚ポーカーの役判定を実装。 Common Lispの学習のために制作した。 * 小さなLispインタプリタ(Common Lisp, Haskell) Common Lispでは、Common Lispのリーダを使いソースファイルを解釈、リストに変換して、構文木インタプリタを実装。 Haskellでは、Parsecを用いてパーサーも書いた。 最適化やコンパイルなどの実装を追加したい。 * RPN電卓(Common Lisp) dc(1)との互換性を実現したい。 bc(1)からのコンパイルも実装したい。 * タイマー(HSP) * ブロック崩し(HSP) * RAPIROをWiiリモコンで操作できるように(C, Python, Arduino) 市販のロボット(Rapiro)にWiiリモコンを接続、操作できるようにした。 高校の部活での個人の活動テーマとしていたが、他のことにリソースを割きすぎて あまり手がまわっていない。 カメラやマイクなどを搭載して、会話ロボットにしてみたい。 * ライフゲーム(Common Lisp) GUIを追加したい。 オセロの実装の前に、CUIによる描画方法を身につけるために作成。 最終的にオセロにはGUIをつけたが、デバッガ用のUIとして役立った。 1(3) http://takoeight0821.hatenablog.jp/ 1(4) Twitter : @takoeight0821 Github, Gist : takoeight0821 Blog : takoeight0821.hatenablog.jp 2(1) Mac OS X上でのCommon Lispの環境構築。 特に、SBCLという処理系に存在する、日本で発売された一部のMacでのみsb-posixというPOSIXをラップした付属ライブラリのユニットテストが正常に動作せず、sb-posixのインストールが失敗するため、ディレクトリ操作などを行う多くのライブラリ、ツールが動作しない問題。 文字コードに由来するバグであり、直っては問題を知らないプログラマにより復活してきた10年来のバグだった。 ユニットテストの一部に仕様上の制限による不具合が存在するという性質上、根本的な解決が難しい。 macOS Sierraからは類似の問題は発生していない 2(2) 当時開発が始まったRoswellという環境構築のためのツールから、パッチを当てることで対応。日本のコミュニティで開発が始まり、広く普及しているため、この対応で問題はほぼ解決したと考えている。 この時、問題の指摘、調査、解決策の提示までを、熟練CLerのアドバイスにより自分が行った。 Common Lispのエコシステム、文字コードの取扱いをめぐる様々な問題について理解が非常に深まった。 2(3) OSSのバグらしき挙動に遭遇した際は、まず、その挙動を再現できる最小の環境の構築方法を特定する必要がある。少しづつ要素を削っていって問題を特定すると良い。 そのOSSの開発メーリングリストやバグリストを検索する。 過去の報告が見つかれば、そのときどうやって解決したのかを辿り、自分もそれを再現する。 問題が解決したら、その解決策を自身のブログなどで公開、共有する。 可能な範囲で、バグ修正のパッチを送ると良い。 3(1) ものづくりコース、言語処理系の作成。 実際の処理系制作の上での、クリティカルなバグを未然に防止するなど言語設計について。 特に、C言語などで問題になることが多い型安全性とメモリ管理に興味がある。 標準ライブラリの品質保証にも興味がある。 昔からプログラミング言語に興味を持っているため。 3(2) 利便性ととっつきやすさと安全性を兼ね備えた独自の言語処理系の実装。 言語処理系の作成だけでなく、実際にある程度大きなプロジェクトに腰をすえて取り組む能力、プログラミング体力とでも呼ぶべきものも身につけたい 選(1) Common Lisp。2年半。 Haskell 3年。しかしここ1年はまともに使って無かったのでリハビリ中。 C 1年。 OCaml 2ヶ月 選(2) Gradual Typingと呼ばれることもある、実行時型検査を行う言語に、型アノテーションを搭載した、部分的なコンパイル時型検査(あるいは実行前型検査) 動的プログラミング言語では、自前で型検査相当の処理を記述しなければならない場合や、 型の記述が良いドキュメントとなる場合が多いので、これは有用な機能だと考えている。 Lispのようなマクロ。 最近はJuliaやRustなどでも採用されているが、Lisp likeなマクロはプログラムの抽象化のための道具として非常に有用だと感じている。 さらに、Rustで行われているように、構文要素の型とでも言うべきものを使えば、 マクロそのものの可読性も上がるため、マクロの静的型付けも興味深い。 簡単な並行化。 アノテーションをつけるだけで関数を並行化できれば、プログラムの処理の効率化が期待できる。 しかし、命令型プログラミングのパラダイムとの相性はあまり良くないと考えている。 宣言型プログラミングと並行化の相性は、Erlangなどをみてもわかるようにとても良い。 最近は、第5世代コンピュータ計画の時代に開発された「並列論理プログラミング」について調べている。 総称関数 なくても困らないが、あると非常に便利。 例えば、Visitorパターンを簡潔に実装できる。 第一級オブジェクトとしてのモジュール。 ML系の言語で有名な、第一級オブジェクトとして扱えるモジュールは非常に便利だと思っている。 例えば、JavaScriptでのオブジェクトはそれにかなり近い。 Rubyでもモジュールは第一級オブジェクトで、ClassはModuleを親クラスに持っている、Mixinなど、面白い機能がある。 選(3) 大学受験が早めに終わったので、空いた時間で「型システム入門」を読んでいた。 半分ほどしか読めていないが、また時間が空けば後半にチャレンジしようと思っている。 4月からは「最新コンパイラ構成技法」を読んでいる。 最近は論理型プログラミングに興味を持っていて、PrologやGHCについて調べている。
2018年 Cコンパイラ自作ゼミに応募
この頃からMalgoを作り始めていたようです。 なぜCコンパイラ自作ゼミを選んだかは忘れましたが、多分インターネットの影響だと思います。 自作言語はなんか出来てきたし自力でいけそうだが、既存のちゃんとした言語の実装はまだ分からない、と感じていた気もします。
[問1] 中学2年からプログラミングを始めました。 最初に触った言語は確かJavaで、MinecraftというゲームのModを作ろうとしたのがきっかけだったはずです。 このあたりの記憶は曖昧ですが、その後HSP、Ruby、Scalaと進み、 いわゆるプログラミング言語オタクになりました。 これまでのプログラミング歴について好きなだけ語るということなので、 今まで使ったことがある中で特に興味深い言語と関連する制作物についていくつか取り上げます。 * Common Lisp Common LispはLisp方言の中でもかなり巨大な言語仕様を持っており、 デバッガや逆アセンブラのインターフェースまで標準で定義されています。 デバッガを駆使したデバッグや、VM命令レベルの最適化など、 興味深いスキルの多くをCommon Lispを通して学びました。 学習リソースが少ないので、実際のアプリケーションのコードを読み込んでCommon Lispに対する理解を深めました。 この経験はCommon Lispのみならず、一般的なコードリーディング力の向上にも役立ちました。 高校3年の文化祭に合わせ、Common Lispでオセロを実装しました。 (https://github.com/takoeight0821/othello) オセロAIの部分は『実用Common Lisp』という本を読みながら実装し、 グラフィカルなUIは、簡易的なWebサーバーを建ててオセロ盤をSVGで描画、 各マスを入力を表すデータの載ったURLのリンクにすることで実現しました。 * Haskell とても高い表現力を持つ型システムを持つプログラミング言語です。 その型システムの最大の特徴は型クラスにあると考えています。 型クラスはアドホック多相(型によって実体が変わる多相性)を実現するための機能です。 型クラスそのものはCoqなどの言語にもあり、Scalaなどもそれに類する機能を持っています。 しかし、型クラス(やそれに類する機能)を言語レベルでここまで活用している言語はHaskellをおいて他にはないでしょう。 最初にHaskellに触れたのは確か中学3年の夏でした。 数年のブランクの後、大学1年の夏からHaskellで自作言語のコンパイラを制作し始めました。 (https://github.com/takoeight0821/malgo) malgoはMLベースの単純な言語で、現在の実装ではLLVM IRを吐きます。 言語機能としては、 * letによるSMLライクな変数、関数宣言 * クロージャ * 無名関数リテラル を持っています。 現在は相互再帰関数と多相型を絶賛開発中です。 * Guarded Horn Clauses 第5世代コンピュータプロジェクトで設計された並列論理プログラミング言語で、 並列実行が基本、軽量プロセスを簡単に扱えるなど、並列プログラミングを強く指向した言語です。 その名の通り、ホーン節にガードを導入した規則の集合としてプログラムを構成します。 特に興味深いのはIO周りです。tail部に単一化されていない変数を持つリストをストリームとして扱うことで、 並列実行の中で自然に逐次IOを記述できるようになっています。 大きなプログラムは書いていませんが、以前ブログ(http://takoeight0821.hatenablog.jp/entry/2017/06/10/151330)でGHCで書いたfizzbuzzを紹介しました。 こうしてみるとstreemにも似ている気がします。 [問2] ほとんどのコンパイラは大きく分けて「字句解析」、「構文解析」、「意味解析」、「最適化」、「コード生成」の5段階でソースコードをアセンブリ言語まで変換した後、アセンブラによってオブジェクトファイルに変換され、ライブラリ等とリンカでリンクされ実行バイナリになります。 具体的な流れや中間生成物はコンパイラごとに異なります。 例えばHaskellコンパイラの一つであるGHCは以下のようなステップを踏みます。 1. 字句解析 2. 大まかな構文解析 3. 名前解決と中置演算子の結合順序の適用 4. 型検査 5. 中間表現Coreへの変換(脱糖衣) 6. Coreレベルの最適化 7. モジュール間のリンク用インターフェースファイルの生成 7. 中間表現STGへの変換 8. 中間表現C--への変換 9. C--レベルの最適化 10. 目的言語の生成(C、ネイティブコード、LLVM) 生成された目的言語に応じてCコンパイラ、アセンブラ、llcなどが実行され、各種ライブラリ等とリンクして実行バイナリが生成されます。 GHCの興味深い点は数多くあります。 Haskellは、結合順序までユーザー定義可能な中置演算子および関数の中置記法に代表されるような多くの複雑な構文規則をもつため、 単一パスで正確にパースし、かつ可読性の高いエラーメッセージを生成することは困難を極めます。 そこでGHCでは、構文解析の段階では緩い規則でASTを生成し、 その後のフェーズで中置演算子の絡む構文木の組み換えなどを行うことでコードの単純化とエラーメッセージの可読性を実現しています。 [問3] 実装に用いる言語によって楽な部分、難しい部分は変わってくると思いますが、どの場合でも最も難しいのは構文解析と意味解析のどちらかだと思います。 Cはほとんどの宣言が型名から始まり、しかもtypedefで型名を新たに宣言することもできるので、 構文解析器の開発中に込み入ったバグを仕込みがちになるのではないかと推測しています。 経験上、手書きで書いた構文解析器のバグは原因の特定が難しい印象があります。 パーサジェネレータを使えば多少改善されるかもしれませんが、 いずれにしても慎重を期す部分だと考えます。 意味解析の実装は、どの程度質の高いものを作るかによって難易度が大きく変わるはずです。 例えば、正しいCプログラムを受理することだけを目標にするなら、 誤ったCプログラムが入力された場合はただexit 1すればいいだけなので、その実装は比較的容易です。 しかし、プログラマに対し適切にエラーメッセージを出力し、意味解析の結果をプログラミングに役立てようとするなら、 単純な型検査はもちろん、エラー箇所に関連するコードを導き出しプログラマにヒントを与える、 バグの原因となりやすいコードに対し警告を出すなど、求められる機能は数多くあります。 これらを実装するのはかなり難易度が高いと考えます。 もちろん、その分重要性の高い部分でもあります。 [問4] ここ1年ほどの間、コンパイラに強い興味を持っています。 一口にコンパイラと言っても、非常に広い分野にまたがっており、関心は尽きません。 このセキュリティ・キャンプが、同じ興味を持つ人たち、あるいは関連する分野に興味を持つ人たちと互いの存在を知る機会となり、 良い刺激を与え合うことができればと思っています。
2019年 Cコンパイラ自作ゼミ
3回目の応募で合格しました。2019年度生の中ではトップタイのスコアだったはずです。 サークルの仲間と喋っているときにノリで最初の実装を書き始めた記憶がありますが、当時は休学していたはずなので真相は定かではありません。
Y-II Cコンパイラ自作ゼミ [問1] これまでのプログラミング歴(C言語に限りません)について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。 昔からプログラミング言語そのものに対する関心が強く、 『計算機プログラムの構造と解釈』を読んでLispの超循環評価器(セルフホストインタプリタ)を書いたりして遊んでいました。 気の向くままにいろいろな言語で遊んでいたので、どのような経緯で今に至ったのか覚えていませんが、一番強いインパクトを与えたのが『Land of Lisp』と『On Lisp』の二冊の本であることは間違いありません。マクロ、ホットリロード、関数プログラミングといったアイディアをプログラミング学習の初期に知ったことが、プログラミング言語にここまでのめり込む一つの要因になったと感じています。 他にもCoq、Erlang、Prolog、Ruby、Go、Scala、etc...と色々手を出していたら、いつのまにか大学でプログラミング言語オタクとして有名になっていました。しかし、大学に入ってから新しく学んだ言語はRustぐらいなので、これらの言語の知識は中学高校の間に見に付けたことになります。 こういう書き方をするのは、僕自身の高校以前の記憶が曖昧ではっきりしていないからです。この課題を書くついでに少しまとめてみました。 ブログ(http://takoeight0821.hatenablog.jp)を見ると2015年の3月に『Land of Lisp』を読んだらしいので、Common Lispに入れ込んでいたのは高校3年生の間のようです。 それまではHaskellをメインにしていた記憶があるので手元の『すごいHaskellたのしく学ぼう』を確認すると、2012年9月10日発行の第4刷でした。ということは中学3年〜高校2年の間のどこかでHaskellを学んだことになります。 Coqは高校2年のときに行った大学のオープンキャンパスで『Software Foundations』の存在を知って学び始めました。 Erlangは『すごいErlangゆかいに学ぼう』を発売してすぐに買って読んで勉強したので2014年。これも高校2年のころになります。 大学に入ってHaskellを再び使い始めたのは、自作言語コンパイラの制作にHaskellを使うことにしたのがきっかけです。コミット履歴をたどると2017年の6月でした。 今まで作ったものの中で一番の大作は、自作言語のコンパイラ(https://github.com/takoeight0821/malgo)です。 Standard ML風のトイ言語で、Haskellで書かれたコンパイラがLLVM IRを吐くようになっています。 例えばこんな感じのソースコードから let extern print_int : Int -> Unit = "print_int" extern newline : Unit -> Unit = "newline" fun fib(n : Int) : Int = if n <= 1 then 1 else fib(n - 1) + fib(n - 2) fun fib_loop(n : Int) : Unit = let val unused:Int = fib(30) in if n <= 0 then print_int(fib(0)); newline() else print_int(fib(n)); newline(); fib_loop(n - 1) end in fib_loop(30) end こんな感じのLLVM IRが吐かれます。 ; ModuleID = 'examples/fib.mlg' declare external ccc i8* @GC_malloc(i64) declare external ccc {} @newline({}, i8*) declare external ccc {} @print_int(i32, i8*) define external ccc {} @"fib_loop.4:(Int -> {})"(i32 %n.5, i8* %captures){ ; <label>:0: %"unused.6:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 30, i8* undef) %"$k.16:Bool" = icmp sle i32 %n.5, 0 %resultptr = alloca {} br i1 %"$k.16:Bool", label %then, label %else then: %"$k.19:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 0, i8* undef) %"$_.18:{}" = call ccc {} @print_int(i32 %"$k.19:Int", i8* undef) %valdec = call ccc {} @newline({} undef, i8* undef) store {} %valdec, {}* %resultptr br label %end else: %"$k.23:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %n.5, i8* undef) %"$_.22:{}" = call ccc {} @print_int(i32 %"$k.23:Int", i8* undef) %"$_.24:{}" = call ccc {} @newline({} undef, i8* undef) %"$k.26:Int" = sub i32 %n.5, 1 %valdec1 = call ccc {} @"fib_loop.4:(Int -> {})"(i32 %"$k.26:Int", i8* undef) store {} %valdec1, {}* %resultptr br label %end end: %valdec2 = load {}, {}* %resultptr ret {} %valdec2 } define external ccc i32 @"fib.2:(Int -> Int)"(i32 %n.3, i8* %captures){ ; <label>:0: %"$k.7:Bool" = icmp sle i32 %n.3, 1 %resultptr = alloca i32 br i1 %"$k.7:Bool", label %then, label %else then: store i32 1, i32* %resultptr br label %end else: %"$k.10:Int" = sub i32 %n.3, 1 %"$k.9:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.10:Int", i8* undef) %"$k.13:Int" = sub i32 %n.3, 2 %"$k.12:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.13:Int", i8* undef) %valdec = add i32 %"$k.9:Int", %"$k.12:Int" store i32 %valdec, i32* %resultptr br label %end end: %valdec1 = load i32, i32* %resultptr ret i32 %valdec1 } define external ccc i32 @main(){ %main = call ccc {} @"fib_loop.4:(Int -> {})"(i32 30, i8* undef) ret i32 0 } 整数、真偽値、文字、文字列、配列、タプル、クロージャが扱え、C言語やアセンブラのコードと素直にリンクできる仕様になっています。 ライフゲームのサンプルが https://github.com/takoeight0821/malgo/blob/master/examples/life.mlg です。 malgoコンパイラのパスは 1. パースする 2. 名前解決 3. 型検査 4. K正規化 5. クロージャ変換 6. LLVM IRの生成 の6段階で、中間表現は 1. パーサが生成するAST 2. 名前解決後のAST(識別子に連番が付加) 3. 型検査後のAST(識別子に型情報が付加) 4. K正規化後の中間表現(すべての式が変数に束縛されている) 5. クロージャ変換後の中間表現(自由変数の捕縛が明記され、すべての関数定義がフラットになっている) の5つです。 初めてにしてはなかなかのできだと思っていますが、いくつか改良点が分かっています。例えば、型検査以降の中間表現がすべて型付の表現であるため、K正規化とクロージャ変換のアルゴリズムが複雑になっています。設計当初はLLVM IRが型付の表現なので最後まで型情報を持っていないといけないと思い込んでいましたが、よくよく考えるとLLVM IRでの型はうまくやればLLVM IR生成時に自明に判明するので、型検査が通ったあとは変数と型の対応表(型環境)だけ持っておけば、中間表現自体に型情報を付与する必要はありません。 設計の見直しと言語機能の拡張を目標に、 https://github.com/takoeight0821/griff を作っています。 この言語と処理系の設計はOCamlとHaskell(GHC)を参考にしています。 また、すでにある程度動くCもどきのコンパイラを作っています(https://github.com/takoeight0821/hoc_nyan)。 これを書いている時点では、変数、if文、ブロック文、return文、四則演算、等値比較、大小比較を実装済みです。 [問2] コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。 まず、Cのコンパイラの大まかな実行過程について説明します。 最初に、ソースコードを字句解析によりトークン列に変換します。 次に、トークン列に対してプリプロセッサを実行します。#includeや#defineなどのマクロはここで展開されます。 プリプロセッサを実行したトークン列を構文解析によりASTに変換します。手元の『低レベルプログラミング』によれば、初期のCはASTを介さずにアセンブリ言語に変換できたらしい(今もそう?)ですが、実際には最適化やコンパイラのメンテナンス性などの理由からASTを経由するコンパイラがほとんどです。 ASTに対して意味解析を行い、必要に応じてコンパイルエラーを投げます。型検査や変数宣言の有無、いくつかの構文上の間違いなどはこのタイミングでチェックします。Cは弱い型付けの言語であり、コード生成時に意味解析を同時に行うことも比較的容易なはずですが、これもコンパイラのメンテナンス性やコンパイルエラーの質の向上などの理由から独立したパスとして実行されることがほとんどです。 多くのコンパイラは、意味解析の後や途中でASTを中間表現と呼ばれる別のデータ構造に変換します。中間表現は、ソースコードと目的コードの抽象度のギャップを埋めるために導入されます。例えば、計算の途中結果を逐一変数に代入する形式に変換して、入れ子になった式をフラットにする変換などがよく行われます。 また、多くのコンパイラは中間表現に対して最適化を行います。1 + 2のような定数式をその計算結果に置き換えたり、不要な変数代入を削除したり、実行されないコードを除去したり、現代のコンパイラは多くの最適化を施すことで生成コードの実行速度を大幅に改善しています。 最後に目的コード、多くの場合はアセンブリ言語を出力します。アセンブリ言語のコードはアセンブラによりオブジェクトファイルに変換され、リンカによって他のオブジェクトファイルと結合されて、実行バイナリが生成されます。 他のほとんどのプログラミング言語も大筋は同じですが、言語ごとに特有の処理が必要になることがあります。 モジュールやパッケージなど、ユーザーが名前空間を定義できる言語では、識別子の実体を求める処理(名前解決)が必要です。ASTに対するマクロを持つ言語は、構文解析の後にASTに対してマクロ展開を実行します。型の表現力が高い言語だと、型検査時にSMTソルバを呼び出すものまであります。 [問3] C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか?考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。 最も難しいのはパーサ、特に型の構文解析だと思います。Cはソースコードと機械語の対応が素直な言語です。そのため、Cコンパイラは他の言語のコンパイラに比べて実装が容易であると思っています。 しかし、Cの型の構文は明らかに複雑です。例えば、`int **hoge[5];`のように、宣言される変数名とその型が入り混じることがあります。この問題は`int **hoge[5], foo;`のような宣言をパースするときに牙を向きそうな匂いがします。構文通りに実装すれば問題ないといえばそれまでですが、型の表現力に対して構文が極端に複雑なので、慎重にテストしないといけないポイントだと思います。 一番の問題はもしかすると実装に用いる言語かもしれません。CでCのコンパイラを書くとすると、ASTの扱いがめんどくさそうです。Cはいい意味でも悪い意味でも自由な言語なので、つまらないミスがあとあとになって深刻なバグとして発覚するみたいなことがあり、なにかと大変そうです。 [問4] 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。 GitHub : https://github.com/takoeight0821 Twitter : https://twitter.com/takoeight0821 はてなブログ : http://takoeight0821.hatenablog.jp