電柱日報

日々の由無し事

Compiler internals(拙訳)

※:この記事は,Crystal Advent Calendar 2018 の22日目です。

Crystalの公式GitHubリポジトリには, Compiler internals というCrystalコンパイラの挙動について解説されたWikiページが公開されています。元の記事が書かれたのは4年ほど前になるため,現状の実装からずれてしまっている部分も多くありますが,crystal コマンドの動きを理解する第一歩としては非常に役に立つ情報だと思いましたので,個人的な理解をベースにざっくりと日本語化してみました。

日本語としての推敲もあまりできておらず不自然な表現もありますが,少しでもお役に立てば幸いです。

なお,これを書いてる人間は翻訳の専門家ではないため,不正確なニュアンスが含まれている可能性があります。おおよその雰囲気がつかめたら,是非原文を当たるようにしてください。

また,もし興味を持っていただけたようであれば,次は現行コンパイラのソースを追いかけてみてはいかがでしょうか。


Compiler internals / コンパイラの内側

ここでは、どのようにコンパイラが動作するかを紹介します。必要に応じて関連コードへのリンクを貼るつもりですが、使用するのは このバージョン です。これは比較的最近(訳注:執筆時点(2014年12月)で)のものなので、もしコードが変更されてしまっても基本的なアルゴリズムに大きな影響はないはずです。

The main file / メインファイル

Crystalコンパイラコンパイルする際のメインファイルは src/compiler/crystal.cr です。このファイルは,Crystalに関連する全てのソースコードを require してから,Crystal::Command.run を実行しています。Command モジュールはコンパイラCUI機能を提供しており,Compiler を生成して,その設定を行い,1つ以上のソースファイルを コンパイル します。

では,Compiler クラスが何をするのかを見ていきましょう。

The Compiler class / Compiler クラス

Comliler クラスの主なパブリックメソッドは compile です。

まず最初に,Program オブジェクトがインスタンス化されます。Program は全てを収容するトップレベルのコンテナで,その内部にクラスやモジュールを定義可能なトップレベルモジュールのように働きます。Rubyputs self を実行した際の main と似たようなものですが,Ruby とは異なり,トップレベルにメソッドを追加すると,そのメソッドはこの Program 型に定義されることになります。Ruby のように Object 型にプライベートメソッドとして定義されるわけではありません。

Program のソースコードを見てもらうとわかるように,ここでは ObjectNilString といった,全てのプログラムで一般的に使用されるいくつかの基本的な型が定義されています。

また,Program はそのコンパイルに関連するデータ,例えば使用される全ての シンボル(シンボルはソースコード内で動的には生成できません)や,CRYSTAL_PATHRubyにおける $LOAD_PATH に似ていますが,変更できません) のようないくつかの設定など,のコンテナでもあります。

Compiler#compile の話に戻りましょう。Program が生成されて設定が完了すると,ソースコード構文解析(parse)ここでも) されます。構文解析によって,それぞれのファイルが AST へ変換されると,それらは 正規化 されます。正規化の処理には,AST ノードを別の形へ変形させるようなものも含まれます。こうした変換処理の一番重要なものは,require を,実際に読み込むファイルの内容に応じた AST ノードへ変換する,という処理です。その他では,例えば unless を,分岐が逆転した if に変換するなどといった処理もあります。

この段階が終了すると,require で取り込んだ内容(特別な "prelude" ファイルは,自動的に取り込まれます)を含んだプログラム全体に相当する AST ノードを手にすることになります。ほとんどの場合,このノードは単一の Expressions ノードで,Expressions とは「2つ以上の AST ノードを含んでいる」という状態を表すノードです。

次のステップは最も重要な 型推論 です。

Type inference / 型推論

この段階の名称は語弊があるかもしれません。ソースコード内では infer_type と呼んでいますが,そこではさらに多くのことが起きています。このような実装には,デメリットもメリットもあります。まずデメリットは,多くの処理が混在することでソースコードを追いかけて理解するのが困難になることです。一方のメリットは,プログラム全体を1度だけ走査すれば良いので,コンパイルが高速になることです。コンパイラを使用する開発者の方が,コンパイラ自身を開発する開発者よりも数が多く,またコンパイル時間は我々にとっても非常に重要であるため,この場合はメリットがデメリットを上回ると我々は信じています。

では,Program#infer_type(node) が何をしているのか見てみましょう。

最初に行われる,もっとも重要な処理は,AST ノードを走査するための TypeVisitor を生成することです。ここでは Visitor パターン を利用しています。この Visitor パターンは,AST ノードを処理するもっとも有用な手法の1つとして,多くのコンパイラで広く利用されています。Crystalの多重ディスパッチ機能は Visitor パターンを使用して非常に簡単に実装できたので,手動でダブルディスパッチ 処理をせずに済んでいます。

TypeVisitor は以下のような多くの仕事を受け持っています。

  • 型やメソッドを宣言する
  • 型情報を伝搬するために AST ノード同士を紐付ける
  • 変数の型とその流れを解析する

Type and methods declaration / 型とメソッドの宣言

ユーザが以下のようなコードを書いたとしましょう。

class Foo
  class Bar
    def baz
        1
    end
  end
end

この場合,Foo クラスを新たに宣言し(すでにあるなら開き直し),その中に Bar クラスを宣言して(すでにあるなら開き直して),その中に buz メソッドを宣言(すでにあるなら再定義)する必要があります。

そのために,TypeVisitor型のスタック を持っています。初期状態のこのスタックは @mod のみが要素として保持されています。

注: コード全体を通じて,mod という単語は,グローバルにアクセス可能なモジュール(module)である Program のことをさします。別の場面では program という単語が使用されることもあります。mod は以前から使われているもので,program に置き換えることもできるのですが,mod はとても短くて便利でもあります。

型のスタックの話に戻りましょう。このスタックは初期状態では Program のみが登録されています。このことは,何らかの型が定義された場合に,それらの型が Program 内に定義されることを意味しています。あるクラスの内部処理中は,その型がスタックに プッシュ され,この状態で追加される新しい型はその型の内部に定義されます。クラス内の処理が終われば,型のスタックからポップされます。この辺りの動きは visit(node : ClassDef) で確認できます。このメソッドにはそれ以外にも,各種バリデーション(例えば,親クラスに齟齬がないか,クラスをモジュールとして開き直していないか,名前空間は存在するかか,等々)や,ジェネリック型の処理,フック(inherited)の実行など,多くのコードが存在しています。

同様の処理は,ModuleEnumLibAliasIncludeExtendDefMacro といった各種定義に対しても行われています。

AST nodes binding / AST ノードの紐付け

このセクションの内容を正確に理解するためには,このブログ記事もう1つ別の記事 を読んでおくよう 強く 推奨します。

簡潔にいうと,型推論アルゴリズムは,AST ノード同士の紐付けによって実現されています。ノード A と B とを紐づけた場合,A の型は B の型になり,もし B の型が変化すれば,同じように A の型も変化します。ここで,A がさらに別のノード C と紐づけられた場合,A の型は B の型と C の型のユニオン型になります。

全ての ASTNode は,自身と1つ以上のノードとを紐づける bind_to メソッドを持っています。ノード A にノード B を紐づけた場合,B は A の dependencies に追加され,同時に B は A を observers に追加します。その結果として,A の dependencies は [B] となり,B の observers は [A] となります。

あるノードが別のノードに紐付けられると,そのノードの型はdependensies の型をマージ(marge) して再計算されます。型のマージがどのように行われるかは付録で説明します(訳注:現時点で付録は公開されていません)。新しい型が追加されると,AST ノードはそのことを 伝搬する(propagate) ために,自身の observersupdate メソッドを実行します。update メソッドでも,大なり小なり同様の処理が行われます(もしその情報を受け取っていなければ,dependencies に基づいた新しい型 を再計算するなど)。そのノードは dirty としてマークされ,全ての observers がの update が終了すると,続いてそれらの propagate が実行されます。こうすることで,情報の伝搬処理を小さくし,余計な伝搬を防止しています。

注:上記のコードは semantic/ast.cr ファイル内に記述されています。syntax/ast.cr というファイルもありますが,こちらには AST ノードとそのプロパティが定義されています。semantic ディレクトリ内のファイルには,意味解析の段階で何を行うかが収められており,AST ノードの定義を開き直して多くの機能を追加しています。このことによって,AST ノードの実装を機能によってグルーピングされた複数のファイルファイルに分割することができ,単一の ast.cr ファイルに全ての機能が混在して巨大化するような事態を防いでいます。

では,bind_to はどこで使われるのでしょうか? 以下のようなコードを想定してみましょう。

a = 1

これは代入(Assign)ノードで,やがて TypeVisitor がそのノードを 訪問(visit) することになります。すると,代入対象(式の左辺)が変数(Var)なので,このメソッド が実行されます。まず先に,代入される値が走査されます。このケースでは,値は数値リテラル(NumberLiteral)でした。数値リテラルから型を割り当てるのは簡単で,それが Int32 リテラルであれば,その型は Int32 型 になります。この型はよく知られたもので,Program 上にすでに定義されており,mod 変数を通じてアクセス可能です。これは,ノードとの紐付けが行われない数少ない例のうちの1つです。この他,NilBoolChar といったプリミティブな型も同様の動きになります。

type_assign)メソッドの話に戻りましょう。そこでは,代入対象が実施に値と紐付けられている様子が確認できます(他にも色々と確認できますが)。同時に,ノードもまた値に紐付けられて います。これは,代入(Assign)というノード(式)自体の型もまた,代入される値の型になるためです。

つづく……