OCaml でコンパイラに入門するための2冊

この記事は言語実装 Advent Calendar 2018の19日目の記事です。

今年の前半に OCaml でコンパイラに入門したので、その過程をつらつらと書いていきます。

言語選定

コンパイラ（というか言語実装）についてネットなどで調べてみると、関数型言語で実装・解説されていることが多く、特に OCaml や Haskell がよく使われている印象を受けました。

もちろんCやJavaでも言語実装は可能なはずで、なぜ関数型言語の使用が多いのか疑問でしたが、camlspotterさんが書かれた「金融と OCaml」という記事に以下のように書かれており、腑に落ちました。

LexiFi はこの商品記述言語システムを関数型言語 OCaml で実装した。これはまったく自然な選択だった。 http://d.hatena.ne.jp/camlspotter/20131105/1383619506 (そうです。これはこの記事を書くための前座だったのです)でも書いたように、言語を代数的に扱うならばオブジェクト指向言語よりも代数的データ型を持つ関数型言語が適しているし、構成されるプリミティブに第一級関数が使われていたからでもある。

引用中のリンク先の記事も参考になります。

つまり関数型言語だからではなく、代数的データ型を持っている言語の一つとして OCaml/Haskell があり、それが選ばれていたという感じでしょうか。

ということで、まずは OCaml を勉強することにしました。

OCaml の学習

OCaml の学習には「 プログラミング in OCaml」を読みました。 紙版はすでに絶版のようですが、技術評論社で電子書籍が販売されています。

この本は非常にわかりやすく良書だと思います。Amazonでの高評価も頷けます。
静的型付けの関数型言語を勉強するのは初めてでしたが、単なる言語仕様だけではなく型推論の理論的概要なども説明しており、その辺りも理解できてよかったです。(最後のGUIの章は読まなくても良いかも)

なお、現在 OCaml の最新バージョンは 4.0.7 ですが、この本は 3.0.x の頃に書かれており OCaml の最新機能については自分で調べる必要があります。
※ 次の紹介する書籍のサンプルコードはこの本で学べる内容で問題ありません。

拙作ですが学習ログを Qiita に投稿したので参考になれば幸いです。

1. OCaml 入門その1 OCamlの基本と型推論
2. OCaml 入門その2 リスト・ヴァリアント・パターンマッチ
3. OCaml 入門その3 例外・ミュータブル・手続き型の処理
4. OCaml 入門その4 モジュール・ファンクタ
5. OCaml 入門その5 オブジェクト指向機能
6. OCaml 入門その6 ラベル付き引数・オプション引数・多相ヴァリアント

コンパイラの学習

コンパイラの学習には「実践コンパイラ構成法」を読みました。
2017年に出版された本で、サンプルソースが OCaml で書かれています。

この本を最後まで読み勧めていくと、x64環境で実際に動作するバイナリを出力するコンパイラが完成します。
Linux/macOS/Windows(Cygwin)の各プラットフォーム向けのコードも用意されているので学習環境の制限も少なく、現在 OCaml でコンパイラを学ぶにはピッタリの本だと思います。

この本では Simple という名前のコンパイル言語を作成します。
Simple の仕様は以下の通りで非常にミニマムな言語です。

1. 型は文字列と整数のみ
2. 制御構造は if と while のみ
3. レキシカルスコープ

各章の感想

1. はじめに

• とくになし

2. 記述言語

• 書籍中で必要になる OCaml の解説がありますが、この章の解説のみで掲載されているサンプルソースを読み解いていくのは厳しいのではないかという印象です。
• すでに関数型言語に慣れている人にはこの章だけで良いかもしれませんが、初めての人は上述の「プログラミング in OCaml」やその他の書籍で OCaml に慣れておいたほうが良いと思います。
• 「プログラミング in OCaml」を読んだなら飛ばしてよいですが、章の最後にある四則演算を行うインタプリタ実装の解説は読んでおいたほうが良いでしょう。

3. 字句解析

• ここから本格的に言語処理系の学習に入っていきます。
• プログラムソース中の文字列を解析してトークンに分割する方法を学びます。 非決定性オートマトンを決定性オートマトンに変換するアルゴリズムの説明が出てきますが、とても難しく苦戦しました。というか今だにちゃんと理解できていません。
• 字句解析には Lex を使い、正規表現で決定性オートマトンを書くことになるので、最悪飛ばしても良いかもしれません。

4. 構文解析

• 書籍中で一番ボリュームのある章で、いわゆる文法クラスを学びます。
• 例えばANTLRはLL(k)、yaccはLALR(1)など、パーサーの扱える文法クラスの意味も理解できるようになるので、この章は飛ばさずしっかりやることをおすすめします。
• 構文解析の方法を学んでいきますが、字句解析の章のような難しいアルゴリズムなどは出てこないので、根気があれば最後まで理解できると思います。

5. 意味解析

• パーサーで解析した構文から抽象構文木を構築する方法を学びます。
• この章は理論というよりは実装がメインの章なので、慣れた方ならサクッと終わるかもしれません。

6. 実行時環境

• どのようなバイナリがCPUで実行されるのか、実際にプログラムが動作する環境について学びます。
• メモリフレーム(ヒープやスタックと呼ばれているもの)やアセンブリ言語などを題材に低レイヤーの処理について入門していきます。
• ひたすら仕様を学んでいく覚えゲーみたいな章なので、そういうものかと読み進めていけばよいかと思います。 この書籍ではx64-CPUを対象にしており、ネットの記事なども参考にしながら読めば理解も進みます。

7. コード生成

• 前章で学んだ内容をもとに抽象構文木からアセンブリコードを生成する処理を書いていきます。
• この章も実装がメインですが、生成されるアセンブリコードの意味を把握する必要があるため、理解しながら実装を写経するのはそこそこ時間がかかると思います。
• 最後に生成されたアセンブリコードを最適化する手法の一つを学んで終わります。
• この章が終われば実際に動作するバイナリを吐けるコンパイラが完成します。

またまた拙作ですが、以下のサイトに学習ログを書いたので参考になれば幸いです。

• https://scrapbox.io/zenwerk/実践コンパイラ構成法

zenwerk/practical-compiler-construction-book

学んでみて

プログラマの3大作りたいものに「OS・CPU・プログラミング言語」とよく挙げられますが、やはりコンパイラ作りを終えてみると非常に満足感があります。

OCaml という言語自体も学ぶべき点が多くあり、学習する価値は十分にあると思います。
はじめに「言語処理系と代数的データ型の相性がいい」という話をしましたが、実際にOCamlのヴァリアントとパターンマッチの組み合わせは強力で、言語処理系のような仕様がカッチリしたものに対しては非常に便利だと感じました。

「プログラミング in OCaml」読了まで大体1ヶ月、「実践コンパイラ構成法」の読了まで大体3ヶ月くらい、合計4ヶ月くらいかかったでそれなりに時間を使いましたが、これまでブラックボックスだった言語処理系を把握できるようになるので学習する価値はあると思います。

皆さんも OCaml でコンパイラに入門してみてはいかがでしょうか。