コンパイラ

この記事は英語の原文を日本語に翻訳したものです。原文: https://blog.stenmans.org/theBeamBook/#CH-Compiler

翻訳元: happi/theBeamBook 7998e22e78417dbe20e5136b9aee862a1ecaa404（コミット 7998e22）

本書ではErlangというプログラミング言語そのものは扱わない。しかし、ERTSの目的はErlangコードを実行することにあるため、Erlangコードのコンパイル方法を知っておく必要がある。本章では、人間が読めるBEAMコードを生成するために必要なコンパイラオプションと、生成された.beamファイルにデバッグ情報を追加する方法を扱う。章の最後にはElixirコンパイラについての節もある。

自分の好きな言語をERTS向けにコンパイルしたいと考えている読者のために、本章ではコンパイラ内部の様々な中間形式についての詳細な情報と、自作コンパイラをBEAMコンパイラのバックエンドに接続する方法も扱う。またパース変換についても紹介し、Erlang言語を調整するための使用例を示す。

Erlangのコンパイル

Erlangは、.erlファイルのソースコードモジュールから、バイナリの.beamファイルへとコンパイルされる。

コンパイラはOSのシェルからerlcコマンドで実行できる。

> erlc foo.erl

erlcの一般的な振る舞いを制御するオプションはいくつかあり、たとえば出力先ディレクトリを指定する-o <Directory>はCコンパイラのオプションとおおむね似ている。完全な一覧はhttps://www.erlang.org/doc/apps/erts/erlc_cmd.htmlを参照。より具体的なコンパイラオプションはプラス記号で始まり、+debug_infoのように書く。これらはコンパイラアプリケーションにそのまま渡されるErlangの項であり、{や"のような特殊文字を含む場合はシェル上でクォートが必要になることがある。これらのオプションの完全な一覧はcompileモジュールのドキュメントにある。参照: http://www.erlang.org/doc/man/compile.html。

コンパイラはErlangシェルから呼び出すこともできる。シェルのショートカットコマンドc()を使う方法(コンパイル後にモジュールをロードする)と、compile:file()を呼び出す方法(コンパイルはするがロードはしない)の2通りがある。ファイル名はアトムまたは文字列で指定でき、.erl拡張子を含める必要はない。

1> c(foo).
{ok, foo}

あるいは

1> compile:file(foo).
{ok, foo}

どちらの関数も、第2引数としてオプションのリストを取れる。これらはerlcから+オプションとして渡せるのと同じ項である。

1> c(foo, [nowarn_unused_function, debug_info]).

通常、コンパイラは.erlファイルからErlangソースコードをコンパイルし、生成されたバイナリのbeamコードを.beamファイルに書き出す。 compile:file()にbinaryオプションを渡すことで(c()のショートカットには渡せない)、生成されたバイナリをErlangの項として直接受け取ることもできる。

1> compile:file(foo, [binary]).
{ok, foo, <<70,79,82,...>>}

一部のオプションは、コンパイラにコンパイルの特定の段階で処理を止めさせ、中間表現を出力として生成させる。たとえば、Core Erlangへの変換後にプログラムがどう見えるかを確認するには次のようにする。

1> c(foo, [to_core]).
** Warning: No object file created - nothing loaded **
ok

ここでの警告はc()シェルショートカットからのものである。 .beamオブジェクトファイルが生成されなかったため、ロードすべきモジュールの新しいバージョンが存在しないという意味である。代わりに、テキストファイルfoo.coreが生成されているはずである。

プリプロセッシングの結果を見たい場合は、代わりに'P'オプションを渡す。

1> c(foo, ['P']).
** Warning: No object file created - nothing loaded **
ok

出力ファイルfoo.Pには、すべてのインクルードファイルが読み込まれ、マクロが置換され、-ifdefのような条件コンパイルディレクティブが評価された後のErlangソースコードの姿が示される。

実のところ、binaryオプションには「コンパイラが停止した段階の中間形式を、ファイルに書き出す代わりに項として返す」という意味が上乗せされている。たとえばCore Erlangコードを返してほしい場合は、[to_core, binary]というオプションを渡せばよい。

1> compile:file(foo, [to_core,binary]).
{ok, foo, {c_module, ...}}

この場合に得られるのはテキストの塊ではなく、Erlangの項としての実際の内部表現であることに注意してほしい。ほとんどの内部表現には対応するプリティプリント関数がある。たとえば次のようにする。

1> {ok, foo, Core} = compile:file(foo, [to_core,binary]).
{ok, foo, {c_module, ...}}
2> io:put_chars(core_pp:format(Core)).
module 'foo' [...]
  ...

コンパイルを後の段階、たとえば.coreソースファイルから再開するようコンパイラに指示することもできる。 erlcを使う場合は次のようになる。

> erlc foo.core

erlcのフロントエンドは.erlだけでなく複数の拡張子を認識し、それぞれに対応するバックエンドを適用する。詳細はhttps://www.erlang.org/doc/apps/erts/erlc_cmd.html#supported-compilersを参照。

あるいはErlangから直接実行する場合。

1> c(foo, [from_core]).
{ok, foo}

中間コードをErlangの項として持っている場合は、それをそのままコンパイラに渡し、続きの処理をするよう指示できる。

1> {ok, foo, Core} = compile:file(foo, [to_core,binary]).
{ok, foo, {c_module, ...}}
3> {ok, foo, Bin} = compile:forms(Core, [from_core,binary]).
{ok,foo, <<70,79,82,...>>}

そして最後に、バイナリ形式のBeamモジュールを持っている場合は、それを直接メモリにロードして実行できる。

4> code:load_binary(foo, "nopath", Bin).
{module,foo}
5> foo:f()
hello
6> code:which(foo).
"nopath"

(この場合、バイナリが一度もファイルに保存されていなくても、モジュール名と、コードサーバーがオブジェクトファイルパスとして報告する文字列の両方をローダーに伝える必要がある。)

このようにして、コンパイラの様々な地点にフックを差し込んで出力を調べたり、それを修正して戻したり、対応する.erlファイルを持たないまま自分で生成した低レベルのコードを渡したりすることさえ可能になる。しかも、望まない限りファイルに何かを書き出す必要は一切ない。

コンパイラの概要

コンパイラは複数のパスから構成されている。わかりやすさのため、これを2つの部分に分ける。 Erlangソースコードを受け取ってCore Erlangコードへと変換するフロントエンド(図1)と、Core Erlangレベルから続けてコードを変換・最適化しBEAMバイトコードへ落とし込むバックエンド(図2)である。

コンパイラのパス(フロントエンド)

図1: コンパイラのパス(フロントエンド)。実線は処理の流れを、破線は各パスから得られる中間出力(ファイル形式とErlangの項形式、および有効化するコンパイラオプション)を示す。パース変換はユーザー定義の変換モジュールと双方向にやり取りする。

コンパイラのパス(バックエンド)

図2: コンパイラのパス(バックエンド)。実線は処理の流れを、破線は各パスから得られる中間出力を示す。from_coreやerlc *.core、from_asmやerlc *.Sは、それぞれCoreパスやASMパスへ外部から処理を持ち込めることを示す。

コンパイラのパスの完全かつ最新の一覧を見たい場合は、Erlangシェルでcompile:options()関数を実行すればよい。コンパイラについての決定的な情報源は、もちろんErlang/OTPのソースコードである。 compile.erlを参照。

中間出力の生成

コンパイラが生成するコードを見ることは、仮想マシンがどう動作するかを理解するうえで大いに役立つ。幸い、コンパイラは各パスの後の中間コードと、最終的なbeamコードを見せてくれる。

さっそく身につけた知識を使って、生成されたコードを見てみよう。

 1> compile:options().
 dpp - Generate .pp file
 'P' - Generate .P source listing file

...

 'E' - Generate .E source listing file

...

 'S' - Generate .S file

小さなサンプルプログラムworld.erlで試してみよう。

-module(world).
-export([hello/0]).

-include("world.hrl").

hello() -> ?GREETING.

そしてインクルードファイルworld.hrl。

-define(GREETING, "hello world").

このプログラムを'P'オプション付きでコンパイルし、パース済みファイルを取得すると、ファイルworld.Pが得られる。

2> c(world, ['P']).
** Warning: No object file created - nothing loaded **
ok

生成された.Pファイルには、プリプロセッサ(とパース変換)を適用した後のコードのプリティプリント結果が見える。

-file("world.erl", 1).

-module(world).

-export([hello/0]).

-file("world.hrl", 1).

-file("world.erl", 4).

hello() ->
    "hello world".

すべてのソースコード変換が終わった後のコードがどう見えるかを確認するには、'E'フラグ付きでコードをコンパイルすればよい。

3> c(world, ['E']).
** Warning: No object file created - nothing loaded **
ok

これにより.Eファイルが得られる。この場合、すべてのコンパイラディレクティブが除去され、レコードがあればすべてタプルへと展開され、関数インポートの使用箇所があれば明示的なリモート呼び出しへと展開され、組み込み関数module_info/{1,2}がソースに追加される。

-vsn("\002").

-file("world.erl", 1).

-file("world.hrl", 1).

-file("world.erl", 5).

hello() ->
    "hello world".

module_info() ->
    erlang:get_module_info(world).

module_info(X) ->
    erlang:get_module_info(world, X).

パース変換について見ていく際に、この'P'と'E'のオプションを活用する。パース変換を書くを参照。

他の中間段階に進む前に、最終的に生成されるBEAMコードを、その人間が読める「アセンブラ」形式で見ておこう。コンパイラに'S'オプションを渡すと、コード中の各BEAM命令に対応するErlangの項が入った.Sファイルが得られる。

3> c(world, ['S']).
** Warning: No object file created - nothing loaded **
ok

world.Sファイルは次のような内容になっているはずである。

{module, world}.  %% version = 0

{exports, [{hello,0},{module_info,0},{module_info,1}]}.

{attributes, []}.

{labels, 7}.


{function, hello, 0, 2}.
  {label,1}.
    {line,[{location,"world.erl",6}]}.
    {func_info,{atom,world},{atom,hello},0}.
  {label,2}.
    {move,{literal,"hello world"},{x,0}}.
    return.


{function, module_info, 0, 4}.
  {label,3}.
    {line,[]}.
    {func_info,{atom,world},{atom,module_info},0}.
  {label,4}.
    {move,{atom,world},{x,0}}.
    {line,[]}.
    {call_ext_only,1,{extfunc,erlang,get_module_info,1}}.


{function, module_info, 1, 6}.
  {label,5}.
    {line,[]}.
    {func_info,{atom,world},{atom,module_info},1}.
  {label,6}.
    {move,{x,0},{x,1}}.
    {move,{atom,world},{x,0}}.
    {line,[]}.
    {call_ext_only,2,{extfunc,erlang,get_module_info,2}}.

これはドット(.)区切りのErlangの項が並んだファイルなので、次のようにすればシェルに簡単に読み戻せる。

{ok, BEAM_Code} = file:consult("world.S").

見てのとおり、アセンブラコードはおおむね元のソースコードのレイアウトに従っている。

最初の命令はコードのモジュール名を定義する。コメント中に書かれているバージョン(%% version = 0)はオペコード形式のバージョンである(beam_opcodes:format_number/0が返す値)。

続いてエクスポートの一覧と、コンパイラ属性(この例では無い)が、通常のErlangソースモジュールと同じように並ぶ。

最初の本物のbeam命令は{labels, 7}であり、コード中のラベル数をVMに伝える。これによってVMはコードを1回走査するだけで、すべてのラベル分の領域を確保できる。

その後に各関数の実際のコードが続く。最初の命令が関数名、アリティ、そしてラベル番号としてのエントリポイントを与える。エントリポイントが関数内の最初のラベルではないことに気づくだろう。その前には、関数のメタデータを定義する命令がいくつかある。これらは実行時には実行されない。

'S'オプションはBEAMがどう動作するかを理解するのに大いに役立ち、後の章でもこれを使っていく。自分のコンパイラをCore Erlangを通してBEAMにコンパイルするような言語を開発している場合にも、生成されたコードを見るために欠かせない。

コンパイラのパス

以降の節では、図1と図2に示したコンパイラのパスのほとんどを見ていく。 BEAMをターゲットとする言語設計者にとって、マクロ、パース変換、Core Erlang、BEAMコードという異なるアプローチでそれぞれ何ができるか、そしてそれらが互いにどう依存しているかがわかるという点で、これは興味深い内容のはずである。

Erlangコードをチューニングする際には、いつどんな最適化が適用されるか、また最適化の前後で生成されたコードをどう見ればよいかを知っておくとよい。

コンパイラパス: Erlangプリプロセッサ(epp)

コンパイルはトークン化(あるいはスキャン)とプリプロセッシングから始まる。プリプロセッサeppはファイルを読み込み、トークナイザerl_scanを呼び出して、テキストを文字の並びではなく個別のトークンの並びへと展開し、空白とコメントを捨てる。続いてマクロ定義と条件コンパイルディレクティブを処理し、マクロの使用箇所を置換する。

プリプロセッサはインクルード文を見つけると、指定されたインクルードファイルを読み込んでトークン化し、その結果得られたトークン列をインクルード文の代わりに挿入し、それも同様に処理する。これによってファイル同士が再帰的に互いをインクルードできる。あるファイルから別のファイルへと切り替わる際、プリプロセッサは-fileアノテーションを挿入する。これは前述の例で見た通りで、後続のパスが特定のコードがどこ由来かを知るために使われる。

...
-file("world.hrl", 1).

-file("world.erl", 4).
...

world.hrlのようなインクルードファイルが処理されても、実際のコードは何も挿入されないことがある点に注意してほしい。インクルードファイルにはマクロ定義とプリプロセッサの条件分岐しか含まれていないことが多いからである。残るのは「今ヘッダファイルの1行目にいる」「今は元のソースファイルの4行目に戻った」というアノテーションだけである。

以上のことから、eppは(C/C++のプリプロセッサcppと同じように)トークンレベルで動作するのであって、(たとえばm4のような)純粋な文字列置換処理系ではないことがわかる。 Erlangのマクロを使って独自の構文を勝手に定義することはできない。マクロは周囲の文字とは別のトークンとして展開されるため、マクロと文字を連結して1つのトークンにすることはできない。

-define(plus,+).
t(A,B) -> A?plus+B.

これは次のように展開される。

t(A,B) -> A + + B.

次のようにはならない。

t(A,B) -> A ++ B.

一方で、マクロ展開は実際のパースより前のトークンストリーム上で行われるため、マクロの右辺には有効なErlangの項である必要はなく、最終的に有効な項になるような使い方さえしていればよい。たとえば次のようになる。

-define(p,o, o]).
 t() -> [f,?p.

これは次のトークン列に展開される。

 t ( ) -> [ f , o , o ] .

これに実用的な使い道はほとんどなく、難読化Erlangコードコンテストで優勝することくらいしかない。ここで覚えておくべき要点は、Erlangプリプロセッサを使ってErlangとは異なる構文を持つ言語を定義することは実質的にできないということである。

コンパイラパス: Erlangパーサ

パーサerl_parseは、プリプロセッサから最終的なトークン列を受け取り、Erlangの文法と照合して、プログラムを連続したテキストとしてではなくデータ構造として表現する抽象構文木、すなわちAST(http://www.erlang.org/doc/apps/erts/absform.htmlを参照)を生成する。

コンパイラパス: パース変換

パース変換とはASTに対して動作する関数である。コンパイラは最初のトークン化・プリプロセッシング・パースを終え、それまでにエラーが無かったと仮定すると、パース変換関数が宣言されていればそれを呼び出し、現在のASTを渡して修正後のASTを受け取ることを期待する。

これは、入力が引き続きErlangパーサに受理される必要があるという意味でErlangの構文を根本的に変えることはできないが、コードを好きなように書き換えることで意味論は変更できるということでもある。

パース変換は、それが使われるモジュール内で次のように宣言する。

-compile({parse_transform, my_pt}).

すると、コンパイラは追加のパスとしてmy_pt:parse_transform(Forms, Options)を呼び出そうとする。同じモジュール内で複数のパース変換を使うこともでき、その場合は宣言した順に実行される。

パース変換はMnesia(そのQLC構文のため)、EUnit、Merlなどのライブラリで使われている。パース変換を書くでは、自作のパース変換を実装する完全な例を示す。

コンパイラパス: リンタ

「リンタ」という用語は元々、乾燥機のリントフィルタのようにコンパイラに追加されるツールを指していた。スタイル上の誤りやアンチパターンなど、コンパイラ自身がチェックしない事柄(当時のコンパイラは使えるメモリが非常に少なく、速度を重視していたため)を検査するものだった。しかし、コンピュータが高速化するにつれ、リンタはたまに実行するものではなく常に実行したいパスとしてコンパイラ自身に組み込まれるようになった。

Erlangコンパイラでは、リンタerl_lintが、パースと変換が終わった後にソースコードのチェックの大半を行う段階である。 (これはつまり、パース変換が返せるASTはリンタが受理するものに限られるということである。)

リンタは、未定義の変数や関数といったエラーをチェックするほか、“export_all flag enabled"のような、正しいが疑わしいコードに対する警告も生成する。

コンパイラパス: ASTの保存

モジュールのデバッグを可能にするには、そのモジュールを「デバッグコンパイル」する必要がある。つまり、コンパイラにdebug_infoオプションを渡す。すると抽象構文木は「ASTの保存」パスによって保存され、コンパイルの最後に.beamファイルへ含められる。これはブレークポイントの設定やシングルステップ実行などのためである。このときコードはコンパイルされたコードとしてではなく、インタプリタで実行される。

このコードが保存されるのは最適化が適用される前であることに注意してほしい。したがって、コンパイラの最適化パスにバグがあり、デバッガでインタプリタ実行のコードを動かすと、異なる挙動になってしまう。自分でコンパイラの最適化を実装している場合、これは思わぬ落とし穴になりうる。

コンパイラパス: 展開

展開フェーズでは、レコードのようなソースレベルのErlang構文が、より低レベルのErlang構文へと展開される。これによってコンパイラディレクティブが取り除かれ、レコード構文がタプルへの操作に置き換えられ、関数インポートの使用箇所が明示的なリモート呼び出しへと展開され、組み込み関数module_info/{1,2}がコードに追加される。

コンパイラパス: Core Erlang

Core Erlangは、コンパイラの最適化に適した厳格な関数型言語である。同じ操作を表現する方法の数を減らすことで、コード変換をやりやすくしている。そのための方法の1つが、スコープをより明示的にするlet式とletrec式の導入である。コンパイラはCoreレベルで複数回のパスを行う。

Core ErlangはERTS上で動かしたい言語のターゲットとしてよい候補になりうる。変化がとても少なく、それでいてErlangのあらゆる側面をきれいな形で含んでいるからである。 BEAM命令セットを直接ターゲットにすると、扱うべき詳細がずっと多くなり、しかもその命令セットはERTSのメジャーリリースごとに多少変化する。逆にErlang自体をターゲットにすると、表現できる内容がより制限され、しかもCore Erlangの方がすっきりした言語である分、より多くの詳細を扱わなければならないこともある。

ただし、素のErlangをターゲットにすると、生成したコードがきちんとした挙動をするかどうかをコンパイル時によりよくチェックできるという利点がある。 Core Erlangを直接生成すると、Erlangコンパイラがこれまで遭遇したことのないコーナーケースを見つけてしまうことがあり、正しいコードを生成する責任がより重くのしかかる。

Erlangファイルをcoreにコンパイルするには、to_coreオプションを渡す。これにより、生成されたCore Erlangプログラムが拡張子.coreのファイルに出力される。 .coreファイルからCore Erlangプログラムをコンパイルするには、コンパイラにfrom_coreオプションを渡せばよい。

1> c(world, to_core).
** Warning: No object file created - nothing loaded **
ok
2> c(world, from_core).
{ok,world}

.coreファイルは、人間が読めるcore形式で書かれたテキストファイルである。 coreプログラムをErlangの項として取得したい場合は、コンパイルにbinaryオプションを追加すればよい。

コンパイラパス: Kernel Erlang

Kernel Erlangは、いくつかの違いを除けばCore Erlangをフラットにしたものである。たとえば、それぞれの変数は一意であり、スコープは関数全体になる。パターンマッチングはより原始的な操作へとコンパイルされる。 Kernel表現には明確に定義されたファイル形式が無く、安定しているとは期待しないほうがよい。

コンパイラパス: BEAMアセンブリコード

通常のコンパイルの最終段階は、個々のBEAM命令の並びをErlangの項として表現した、外部向けのBEAMアセンブリコード形式である。デッドコード除去やピープホール最適化といった一部の低レベルな最適化は、このレベルで行われる。

BEAM命令についてはBEAM命令の章と、BEAM命令一覧の付録で詳しく説明する。

コンパイラパス: BEAMバイナリ形式

BEAMアセンブリコードは最終的に、バイナリの転送形式へとパッキングされる。この形式は.beamファイルへの書き出し、ネットワーク越しの送信、あるいはcode:load_binary/3によるメモリへの直接ロードのいずれにも使える。詳細はbeamモジュールの構造を扱う章を参照。

パース変換を書く

Erlang言語を調整する最も簡単な方法はパース変換(parse transform)を通すことである。パース変換には、OTPドキュメントにある次のような注意書きをはじめ、あらゆる種類の警告が付きまとう。

プログラマーはパース変換に手を出さないことを強く勧められており、問題が発生してもサポートは提供されない。

パース変換を使うということは、基本的にコンパイラに追加のパスを書き加えるということであり、注意を怠ると非常に予期しない結果を招きかねない。しかしパース変換を使うには、それを使うモジュール内で使用を宣言する必要があり、その効果はそのモジュールに限定される。したがって、コンパイラの調整としてはこれは比較的安全な部類に入る。

私の見るところ、パース変換の最大の問題は、独自の構文を発明してしまうことであり、それによって他の誰かがあなたのコードを読むのがより難しくなる、という点にある。少なくとも、あなたのパース変換がQLCのように広く普及するまでは。

さて、パース変換を使うべきではないということはもうわかっただろうが、それでも使わなければならない場合のために、実装方法の例を示そう。

たとえば、何らかの理由でErlangコードの中に直接jsonコードを書きたいとしよう。幸運なことに、jsonとErlangのトークンは基本的に同じである。また、Erlangコンパイラはパース変換パスの後に続くリンタパスでほとんどのチェックを行うため、有効なErlangを表現していないASTを許すことができる。

パース変換を書くには、parse_transform/2関数をエクスポートするErlangモジュール(これをpと呼ぶことにする)を書く必要がある。この関数は、コンパイル対象のモジュール(これをmと呼ぶ)がコンパイラオプション{parse_transform, p}を含んでいる場合に、パース変換パスの間にコンパイラから呼び出される。この関数への引数は、モジュールmのASTと、コンパイラ呼び出し時に渡されたコンパイラオプションである。

ファイル内で渡されたコンパイラオプションは一切受け取れないことに注意してほしい。これはコードからパース変換にオプションを渡せないという、ちょっとした不便さである。

コンパイラは、パース変換パスの後に来る展開パスまでコンパイラオプションを展開しない。

抽象構文形式のドキュメントはかなり密度が高く、それを読んで抽象構文形式を把握するのはなかなか難しい。 AST上での本格的な作業には、syntax_tools、特にerl_syntax_libを使うことを勧める。

ここでは、ASTを理解するための単純なパース変換を作っていく。そのため、syntax_toolsではなく、直接ASTを操作し、昔ながらのio:formatを使うアプローチを取る。

まず、コンパイルできるようにしたいものの例json_test.erlを作る。

-module(json_test).
-compile({parse_transform, json_parser}).
-export([test/1]).

test(V) ->
    <<{{
      "name"  : "Jack (\"Bee\") Nimble",
      "format": {
                 "type"      : "rect",
                 "widths"     : [1920,1600],
                 "height"    : (-1080),
                 "interlace" : false,
                 "frame rate": V
                }
      }}>>.

続いて、最小限のパース変換モジュールjson_parser.erlを作る。

-module(json_parser).
-export([parse_transform/2]).

parse_transform(AST, _Options) ->
  io:format("~p~n", [AST]),
  AST.

この恒等パース変換はASTをそのまま返すが、その内容を出力もするので、ASTがどのようなものかを見ることができる。

> c(json_parser).
{ok,json_parser}
2> c(json_test).
[{attribute,1,file,{"./json_test.erl",1}},
 {attribute,1,module,json_test},
 {attribute,3,export,[{test,1}]},
 {function,5,test,1,
  [{clause,5,
    [{var,5,'V'}],
    [],
    [{bin,6,
      [{bin_element,6,
        {tuple,6,
         [{tuple,6,
           [{remote,7,{string,7,"name"},{string,7,"Jack (\"Bee\") Nimble"}},
            {remote,8,
             {string,8,"format"},
             {tuple,8,
              [{remote,9,{string,9,"type"},{string,9,"rect"}},
               {remote,10,
                {string,10,"widths"},
                {cons,10,
                 {integer,10,1920},
                 {cons,10,{integer,10,1600},{nil,10}}}},
               {remote,11,{string,11,"height"},{op,11,'-',{integer,11,1080}}},
               {remote,12,{string,12,"interlace"},{atom,12,false}},
               {remote,13,{string,13,"frame rate"},{var,13,'V'}}]}}]}]},
        default,default}]}]}]},
 {eof,16}]
./json_test.erl:7: illegal expression
./json_test.erl:8: illegal expression
./json_test.erl:5: Warning: variable 'V' is unused
error

json_testのコンパイルは、モジュールが無効なErlang構文を含んでいるため失敗するが、ASTがどのようなものかは見ることができる。あとはASTを走査してjsonコードをErlangコードへ書き換える関数を書けばよい¹。

-module(json_parser).
-export([parse_transform/2]).

parse_transform(AST, _Options) ->
    json(AST, []).

-define(FUNCTION(Clauses), {function, Label, Name, Arity, Clauses}).

%% 関数の中のコードだけに興味がある。
json([?FUNCTION(Clauses) | Elements], Res) ->
    json(Elements, [?FUNCTION(json_clauses(Clauses)) | Res]);
json([Other|Elements], Res) -> json(Elements, [Other | Res]);
json([], Res) -> lists:reverse(Res).

%% 関数本体のコードに注目する。
json_clauses([{clause, CLine, A1, A2, Code} | Clauses]) ->
    [{clause, CLine, A1, A2, json_code(Code)} | json_clauses(Clauses)];
json_clauses([]) -> [].


-define(JSON(Json), {bin, _, [{bin_element
                                         , _
                                         , {tuple, _, [Json]}
                                         , _
                                         , _}]}).

%% 探すパターン: <<"json">> = Json項
json_code([])                     -> [];
json_code([?JSON(Json)|MoreCode]) -> [parse_json(Json) | json_code(MoreCode)];
json_code(Code)                   -> Code.

%% JSONオブジェクト -> [{}] | [{Label, Term}]
parse_json({tuple,Line,[]})            -> {cons, Line, {tuple, Line, []}};
parse_json({tuple,Line,Fields})        -> parse_json_fields(Fields,Line);
%% JSON配列 -> リスト
parse_json({cons, Line, Head, Tail})   -> {cons, Line, parse_json(Head),
                                                       parse_json(Tail)};
parse_json({nil, Line})                -> {nil, Line};
%% JSON文字列 -> <<String>>
parse_json({string, Line, String})     -> str_to_bin(String, Line);
%% JSON整数 -> Integer
parse_json({integer, Line, Integer})   -> {integer, Line, Integer};
%% JSON浮動小数点数 -> Float
parse_json({float, Line, Float})       -> {float, Line, Float};
%% JSON定数 -> true | false | null
parse_json({atom, Line, true})         -> {atom, Line, true};
parse_json({atom, Line, false})        -> {atom, Line, false};
parse_json({atom, Line, null})         -> {atom, Line, null};

%% 変数。ErlangでエンコードされたJsonを含むはず
parse_json({var, Line, Var})         -> {var, Line, Var};
%% JSONの負の整数または浮動小数点数
parse_json({op, Line, '-', {Type, _, N}}) when Type =:= integer
                                             ; Type =:= float ->
                                          {Type, Line, -N}.
%% parse_json(Code)                  -> io:format("Code: ~p~n",[Code]), Code.

-define(FIELD(Label, Code), {remote, L, {string, _, Label}, Code}).

parse_json_fields([], L) -> {nil, L};
%% Label : Json項 --> [{<<Label>>, Term} | Rest]
parse_json_fields([?FIELD(Label, Code) | Rest], _) ->
    cons(tuple(str_to_bin(Label, L), parse_json(Code), L)
         , parse_json_fields(Rest, L)
         , L).


tuple(E1, E2, Line)    -> {tuple, Line, [E1, E2]}.
cons(Head, Tail, Line) -> {cons, Line, Head, Tail}.

str_to_bin(String, Line) ->
    {bin
     , Line
     , [{bin_element
         , Line
         , {string, Line, String}
         , default
         , default
        }
       ]
    }.

そして今度は、エラー無くjson_testをコンパイルできる。

1> c(json_parser).
{ok,json_parser}
2> c(json_test).
{ok,json_test}
3> json_test:test(42).
[{<<"name">>,<<"Jack (\"Bee\") Nimble">>},
{<<"format">>,
  [{<<"type">>,<<"rect">>},
   {<<"widths">>,[1920,1600]},
   {<<"height">>,-1080},
   {<<"interlace">>,false},
   {<<"frame rate">>,42}]}]

parse_transform/2が生成するASTは、複数のパース変換を適用する場合を除き、有効なErlangコードに対応していなければならない(複数適用すること自体は可能である)。コードの妥当性は、後続のコンパイラパスによってチェックされる。

その他のコンパイラツール

コード生成とコード操作を助けるツールがいくつか用意されている。これらのツールはErlangで書かれており、厳密にはランタイムシステムの一部ではないが、BEAM上に別の言語を実装しようとする場合には知っておくととても役立つ。

本節では、最も有用なコードツールのうち3つ、レキサーであるLeex、パーサジェネレータであるYecc、そして抽象構文を操作するための汎用的な関数群であるSyntax Toolsを取り上げる。

Leex

LeexはErlangのレキサージェネレータである。レキサージェネレータは、定義ファイルxrlからDFAの記述を受け取り、そのDFAが記述するトークンにマッチするErlangプログラムを生成する。

トークナイザ向けにDFAの定義を書く方法の詳細は本書の範囲を超える。詳しい説明については、「ドラゴンブック」を勧める。他に良い資料としては、leexにインスピレーションを与えたレキサープログラムであるflexのmanページやinfoエントリ、それにleex自身のドキュメントがある。 infoとflexがインストールされていれば、次のように入力することで完全なマニュアルを読める。

> info flex

オンラインのErlangドキュメントにもleexのマニュアルがある(yecc.htmlを参照)。

レキサージェネレータを使って、JSONトークンを認識するErlangプログラムを作ってみよう。 JSONの定義(http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-404.pdf)を見ると、扱う必要のあるトークンはひと握りしかないことがわかる。

Definitions.

Digit         = [0-9]
Digit1to9     = [1-9]
HexDigit      = [0-9a-f]
UnescapedChar = [^\"\\]
EscapedChar   = (\\\\)|(\\\")|(\\b)|(\\f)|(\\n)|(\\r)|(\\t)|(\\/)
Unicode       = (\\u{HexDigit}{HexDigit}{HexDigit}{HexDigit})
Quote         = [\"]
Delim         = [\[\]:,{}]
Space         = [\n\s\t\r]

Rules.

{Quote}{Quote} : {token, {string, TokenLine, ""}}.
{Quote}({EscapedChar}|({UnescapedChar})|({Unicode}))+{Quote} :
  {token, {string, TokenLine, drop_quotes(TokenChars)}}.

null  : {token, {null,  TokenLine}}.
true  : {token, {true,  TokenLine}}.
false : {token, {false, TokenLine}}.

{Delim} : {token, {list_to_atom(TokenChars), TokenLine}}.

{Space} : skip_token.

-?{Digit1to9}+{Digit}*\.{Digit}+((E|e)(\+|\-)?{Digit}+)? :
  {token, {number, TokenLine, list_to_float(TokenChars)}}.
-?{Digit1to9}+{Digit}* :
  {token, {number, TokenLine, list_to_integer(TokenChars)+0.0}}.

Erlang code.
-export([t/0]).

drop_quotes([$" | QuotedString]) -> literal(lists:droplast(QuotedString)).
literal([$\\,$" | Rest]) ->
  [$"|literal(Rest)];
literal([$\\,$\\ | Rest]) ->
  [$\\|literal(Rest)];
literal([$\\,$/ | Rest]) ->
  [$/|literal(Rest)];
literal([$\\,$b | Rest]) ->
  [$\b|literal(Rest)];
literal([$\\,$f | Rest]) ->
  [$\f|literal(Rest)];
literal([$\\,$n | Rest]) ->
  [$\n|literal(Rest)];
literal([$\\,$r | Rest]) ->
  [$\r|literal(Rest)];
literal([$\\,$t | Rest]) ->
  [$\t|literal(Rest)];
literal([$\\,$u,D0,D1,D2,D3|Rest]) ->
  Char = list_to_integer([D0,D1,D2,D3],16),
  [Char|literal(Rest)];
literal([C|Rest]) ->
  [C|literal(Rest)];
literal([]) ->[].

t() ->
  {ok,
   [{'{',1},
    {string,2,"no"},
    {':',2},
    {number,2,1.0},
    {'}',3}
   ],
   4}.

Leexコンパイラを使うことで、このDFAをErlangコードにコンパイルできる。さらにdfa_graphオプションを渡せば、Graphvizなどで表示できるdotファイルも生成される。

1> leex:file(json_tokens, [dfa_graph]).
{ok, "./json_tokens.erl"}
2>

生成されたDFAグラフ(JSONトークンのDFAグラフ)は、たとえばdottyで表示できる。

> dotty json_tokens.dot

JSONトークン認識のための状態遷移を示すDFA(決定性有限オートマトン)グラフ

図3: JSONトークンのDFAグラフ

サンプルのjsonファイル(test.json)でトークナイザを試してみよう。

{
    "no" : 1,
    "name"  : "Jack \"Bee\" Nimble",
    "escapes" : "\b\n\r\t\f\//\\",
    "format": {
        "type"      : "rect",
        "widths"    : [1920,1600],
        "height"    : -1080,
        "interlace" : false,
        "unicode"   : "/",
        "frame rate": 4.5
    }
}

まずトークナイザをコンパイルし、ファイルを読み込んで文字列に変換する。最後に、leexが生成するstring/1関数を使ってテストファイルをトークン化する。

2> c(json_tokens).
{ok,json_tokens}.
3> f(File), f(L), {ok, File} = file:read_file("test.json"), L = binary_to_list(File), ok.
ok
4> f(Tokens), {ok, Tokens,_} = json_tokens:string(L), hd(Tokens).
{'{',1}
5>

シェル関数f/1は、変数束縛を忘れるようシェルに指示する。これは、レキサーを書きながら書き直すたびに試すといった、複数回変数を束縛するコマンドを試したいときに便利である。シェルコマンドについては後の章で詳しく見ていく。

JSON用のトークナイザが手に入ったので、次はパーサジェネレータYeccを使ってjsonパーサを書いてみよう。

Yecc

YeccはErlang向けのパーサジェネレータである。名前の由来はYacc(Yet Another Compiler Compiler)、C言語向けの代表的なパーサジェネレータである。現代のオープンソース版の相当品はBisonで、Flexと組み合わせて使われることが多い。

JSON用のレキサーが手に入ったので、yeccを使ってパーサを書いてみよう。

Nonterminals value values object array pair pairs.

Terminals number string true false null '[' ']' '{' '}' ',' ':'.

Rootsymbol value.

value -> object  :  '$1'.
value -> array   :  '$1'.
value -> number  :  get_val('$1').
value -> string  :  get_val('$1').
value -> 'true'  :  get_val('$1').
value -> 'null'  :  get_val('$1').
value -> 'false' :  get_val('$1').

object -> '{' '}' : #{}.
object -> '{' pairs '}' : '$2'.

pairs -> pair : '$1'.
pairs -> pair ',' pairs : maps:merge('$1', '$3').

pair -> string ':' value : #{ get_val('$1') => '$3' }.

array -> '[' ']' : {}.
array -> '[' values ']' : list_to_tuple('$2').

values -> value : [ '$1' ].
values -> value ',' values : [ '$1' | '$3' ].



Erlang code.

get_val({_,_,Val}) -> Val;
get_val({Val, _}) -> Val.

続いてyeccを使ってパーサを実装するErlangプログラムを生成し、トークナイザが生成したトークンを引数としてparse/1関数を呼び出す。

5> yecc:file(yecc_json_parser), c(yecc_json_parser).
{ok,yexx_json_parser}
6> f(Json), {ok, Json} = yecc_json_parser:parse(Tokens).
{ok,#{"escapes" => "\b\n\r\t\f////",
      "format" => #{"frame rate" => 4.5,
        "height" => -1080.0,
        "interlace" => false,
        "type" => "rect",
        "unicode" => "/",
        "widths" => {1920.0,1.6e3}},
       "name" => "Jack \"Bee\" Nimble",
       "no" => 1.0}}

LeexとYeccというツールは、独自の言語をまるごとErlang仮想マシン向けにコンパイルしたい場合に便利である。これらをSyntax Tools、とりわけMerlと組み合わせることで、Erlangの抽象構文木を操作し、Erlangコードを生成したり、Erlangコードの振る舞いを変えたりできる。

Syntax ToolsとMerl

Syntax Toolsは、Erlangの抽象構文木(AST)の内部表現を操作するためのライブラリ群である。

syntax toolsアプリケーションには、メタプログラミングユーティリティのMerlも含まれている。 Merlを使えば、構文木をとても簡単に操作でき、Erlangコードでパース変換を書ける。

Syntax Toolsのドキュメントはerlang.orgのサイトにある。 http://erlang.org/doc/apps/syntax_tools/chapter.html

Elixirのコンパイル

BEAM上に自作の言語を実装するもう1つのアプローチは、Elixirのマクロプログラミング機能を使うことである。 ElixirはErlangの抽象構文木を経由してBEAMコードへコンパイルされる。

Elixirのdefmacroを使えば、Elixirの中に直接、独自のドメイン固有言語を定義できる。

この変換はEEP 18(Erlang Enhancement Proposal 18: “JSON bifs”)に沿って行っている。 ↩︎