Compiler | Stanford Online を受講した

11月の頭から受講を始めて、5ヶ月弱かけてようやく受講しきりました。

何度か心が折れかけましたがどうにか完遂できました!

lagunita.stanford.edu

f:id:goropikarikun:20200321181551p:plain

この講義は COOL (classroom object oriented language)という、講義のために作られた言語のコンパイラを理論を学びながら作っていくというものです。

リアルの講義スピードだと11週間のコースなのですが、修了するまでに5ヶ月弱も掛かってしまいました。 self paced だったので良かったですが、これが実際の講義だったら落単必死です。

※ 今後は edX で受講できます。 www.edx.org

講義の流れとしては動画を見て理論を学び、学んだことをもとにコンパイラを実装していくといった感じです。 各週の最後のクイズに加えて、約2週間に1度プログラミング課題(lexer, parser, semantic analyzer, code generator)が出ます。

講義の難易度としては、Cコンパイラで有名な Rui Ueyama さんにとってはちょっと簡単過ぎて、G社のエンジニアが弱音を吐くくらいらしいです。(Ueyama-san のは正規の講義で私が受けたのはネットで無料で受講できたものなので難易度が下がっているかも)

ちなみに、私の感想をいうと今まで受けた講義の中で最も難しかったです。最終課題を出すまでに5ヶ月、述べ230時間をこの講義のために費やしました。edX でのコースページを見ると Level: Introductory となっていますが、さすがにそれは過小評価だと思います。最低でも intermediate くらいの難しさはあると思います。

スタンフォードの単位は通わなくてもリモートで取れるよ、テストとかの難易度は同じで|Rui Ueyama|note

教科書はなくとも受講できるという触れ込みでしたが、配布資料とネットの情報だけでは限界を感じて以下の本を購入しました。

flex & bison: Text Processing Tools

flex & bison: Text Processing Tools

  • 作者:Levine, John
  • 発売日: 2009/08/24
  • メディア: ペーパーバック

Lexer, Parser の課題のときに大活躍でした!

Introduction to Compilers and Language Design

Introduction to Compilers and Language Design

  • 作者:Thain, Douglas
  • 発売日: 2019/07/24
  • メディア: ペーパーバック
Introduction to Compilers and Language Design
GitHub - dthain/compilerbook-examples: Example code for compilers textbook.

PDF を著者のページからダウンロードできます。結局ほとんど読まなかったですが、GitHub に上がっている Flex や Bison のサンプルを見て Flex / Bison の使い方の理解が進みました。

タイガーブックでおなじみの本ですね。不定期にやってくる Amazon の謎の値下げがちょうどあり、3700円と格安で買えました。 6章の Activation Record まで読みました。講義では LR Parsing がイマイチ理解できなかったのですがこの本のおかげで理解できました。 難しい本だと聞いていたのですが、少なからず私が読んだ6章までは CS のバッググラウンドがない私でも読みやすかったです。

プログラミング言語StandardML入門

プログラミング言語StandardML入門

  • 作者:淳, 大堀
  • 発売日: 2001/09/30
  • メディア: 単行本

タイガーブックは疑似コードで書かれている部分は良かったのですが、ML で書かれている部分は何をしているのかさっぱり理解できなかったので買いました。 初めて ML 触りましたが面白い言語ですね。パターンマッチが便利だなと思いました。

加えて正規言語、文脈自由文法といった予備知識が足りなかったので Automata Theory の講義の該当箇所も同時に受講しました。

www.edx.org

最後の Code Generation の課題は特に難しくて、要求される機能の実装方針が全く思いつきませんでした。講義を見返してもヒントになりそうなこともなかったので最終的に配布されているコンパイラ(バイナリのみ、ソースコードなし)の吐き出すアセンブリを読んで実装方法を推測するというリバースエンジニアリングっぽいことをしてどうにか課題を終わらせることが出来ました。

アセンブリから実装を推測するなんてよっぽどの変態優秀な人にしか無理な芸当だと思っていましたが、素人にも案外できるものですね。

おわりに

昨年の GoCon で Go コンパイラを作った方の話に触発されて軽い気持ちでコンパイラを作り始めましたが、思いの外時間がかかってしまいました。最初は毎日やっていれば1ヶ月もあれば終わるだろうと高をくくっていたのですが、全然そんなことなかったですね。

Go Conference 2019 Autumn | Goコンパイラをゼロから作ってセルフホスト達成するまで

今まで概念だけ知っていた型推論やクラスの継承などをコンパイラを作ることを通して実践的に理解することができたなと思います。

昨今ではコンパイラを作るのは珍しいことではないのかもしれませんが、自分で実際にコンパイラを作ったことがあるという経験は何事にも変え難いことだなと思います。