ぱたへね!

はてなダイアリーはrustの色分けができないのでこっちに来た

Writing Compilers and Interpreters まとめ

Writing Compilers and Interpreters A Software Engineering Approach 3rd Editionを5月から読んでました。なかなか面白い本なので紹介します。コンパイラの勉強というとどうしてもパーサーで挫折してしまいがちです。この本は、まずはフロントエンドと、中間処理(intermidiate)、バックエンドまでを簡単に作って、そこから少しずつ進めていきます。前半はどうしてもパーサーよりですが、パーサーという章があるわけではないのでそこで詰まることなく、面白いところまで手を動かしながら読めました。

どんな本

難しい理論は置いておいて、PascalコンパイラインタープリターをJavaで実装していく本です。本の内容は、タイトルの通りコンパイラを書くことに重点が置いてあります。実装上のテクニックは詳しく書いてありますが、背景のアルゴリズム説明や、別の実装方法の検討などは最後の方で少し出てくるレベルです。

目次はこうなっています。Kindleで読んだのでボリューム不明でしたが、紙の本だと800ページ越えですね。半分くらいはJavaのソースなので、見た目よりはボリューム少ないと思います。理解を確認するための演習問題は特にないですが、Pascalソースコードがあるので、それがちゃんと動くかどうかで理解度を確認できます。

Chapter 1 Introduction 1
Chapter 2 Framework I: Compiler and Interpreter 11
Chapter 3 Scanning 55
Chapter 4 The Symbol Table 97
Chapter 5 Parsing Expressions and Assignment Statements121
Chapter 6 Interpreting Expressions and Assignment Statements167
Chapter 7 Parsing Control Statements 189
Chapter 8 Interpreting Control Statements 233
Chapter 9 Parsing Declarations 249
Chapter 10 Type Checking 331
Chapter 11 Parsing Programs, Procedures, and Functions 371
Chapter 12 Interpreting Pascal Programs 431
Chapter 13 An Interactive Source-Level Debugger 501
Chapter 14 Framework II: An Integrated DevelopmentEnvironment (IDE) 543
Chapter 15 Jasmin Assembly Language and Code Generation forthe Java Virtual Machine 577
Chapter 16 Compiling Programs, Assignment Statements, andExpressions 625
Chapter 17 Compiling Procedure and Function Calls and StringOperations 661
Chapter 18 Compiling Control Statements, Arrays, and Records719
Chapter 19 Additional Topics 791

ぱっと見て面白そうなのが、13章、14章のデバッガやIDEの作成ですね。インタープリターで動かしながら、最後はJavaアセンブラを出力できるところまでやります。

12章までは手を動かしながら、あーだこーだやってました。いまいち仕組みが分かってない中、おかしいポイントを見つけて修正はできていたので、それなりには理解している気がします。

13章以降は、デバッガについては過去仕事で作ったことがあるし、構文ツリーができてしまえばSICP読んでいるからまあ読まなくても大丈夫かなと判断しました。

読んでいて面白かった所

コンパイラの構成

筆者がBeautiful Codeの執筆もしている事もあり、インターフェイスと実装をちゃんと分けたりソースコードはわかりやすく、教科書としても重点的に説明してありました。フロントエンドやバックエンドの単位でファクトリーパターンを使うのは理にかなっていて、すごく勉強になりました。コンパイラのバージョンアップで文法が変わったとき、オプションで昔の文法でコンパイルするとき等、この仕組みがあれば便利です。

コンパイラ全体を通して、オブザーバーパターンが使われています。例えば、変数が宣言される度にメッセージが飛び、簡単にログを取ることができます。インタープリタ実装時にも、変数の代入(更新)の度にメッセージを送ることでデバッグ可能な環境を作っています。パーサーのデバッグ時には、エラーメッセージを受信するところにブレークポイントを張っておけば、エラー発生時にスタックトレースを見て、どういう経路でエラーになったかが一発で特定でき、非常に開発効率が良かったです。

構文ツリーを構成するにあたって面倒なところは、どんどん辞書に入れて行ってデータ構造が難解になるのを防いでました。例えば、for文に相当するnodeは、インデックスの初期値(最小値)、終了の値(最大値)、それらの型、ステップなどを、全部辞書に入れて行くことで、ソースコードがすっきりしていました。構文ツリーをXMLでダンプするところも結構ページを割いて解説してあり、始めてコンパイラを作る人にはうれしい情報が満載でした。

Class名は非常にわかりやすい反面、関数名は微妙な物があり、悩ましい感じはします。標準関数arctan,cos,exp,ln,sin,sqrtを処理する関数名がexecuteArctanCosExpLnSinSqrtだったり。これは浮動小数点数を引数に、浮動小数点数を返す関数の処理ルーチンです。同じくabsとsqrを処理する関数はexecuteAbsSqrで、これは引数の型によって整数か浮動小数点数を返す関数です。もうちょっと良い名前はなかったのかと・・・。

型システム

コンパイラインタープリタの型システムの事を正直舐めてました。

修飾のバリエーション、ユーザー型、コンテナ、スコープ、再帰的な定義、オブジェクト指向だとこれに継承が入ってきます。型をパースして、その情報を管理するだけでも相当めんどくさい。手を動かしてみて始めて分かりました。TAPL読まねば。

コンパイラインタープリタ

二つとも適当に作れそうな気がしていたが、同じソースをコンパイラインタープリタで全く同じ動きを保証するのがかなり大変と言うことが分かりました。特にコンパイラが最適化で計算順序を入れ替えたりしたとき、全く同じ結果を保証するのはそれはそれで別の技術ですね。

Pythonコンパイラを作る事

今回JavaのソースをPythonに移植しながら動かしました。良く分かってないコードを動かすときに、型をちゃんと宣言できないと何をやっているかさっぱり分からなくなりました。全然違うclassの列挙体(enum)を比較しても、しれっとFalseを返すところとかは泣きそうでした。比べても意味のないものを比較しているので、せめて実行時にワーニング出して欲しい。途中からPEP484 type hintを使ってアノテーションをつけていくと大分ましになりました。コンパイラ作るときは、F#みたいにコンパイル時にちゃんと型のチェックをしてくれる言語の方が良いですね。出遅れたけどRustは触ってみたいです。

あとディレクトリをまたぐ(一度上って別のディレクトリへ降りる)Classのimport方法が未だによくわからないです。ソースの一番上でなくて、classの中でimportすると若干規制が緩くなることが分かったがそこまでです。実際のコードでも、フロントエンド、中間処理、バックエンドが綺麗に分かれていることは難しく、すごくごちゃごちゃした参照関係になります。間に中間処理が入るので、フロントエンドとバックエンドなら独立しているかというとそうでもなく、バックエンド側でエラーが出たときに元のソースコードの情報(行数とか)と得ようとすると、フロントエンド側のclassにアクセスできる方が手っ取り早かったりします。実際に書いてみて気がついた事で、標準入力から読み込んだ文字列の処理は、ソースコードリテラルと同じ処理をする事があり、インタープリタ側でスキャナーとかトーカナイザーの機能を使うケースがあります。何も考えずトーカナイザーだからフロントエンド側にソースを配置しちゃうと、全体としてぐちゃぐちゃしてきました。これも辛かったです。

おすすめの人

コンパイラの説明は最小限なので、最初の一冊にはお勧めしないです。
コンパイラの勉強が電卓で終わってしまう人、パーサーの章で飽きちゃう人にお勧めです。僕自身はすごく楽しめたので、実際に手を動かしながら理解していく勉強方法が好きな人は是非買ってみてください。