tools.analyzerとtools.emitterを組み合わせてキミだけの最強Clojure処理系を作ろう

(このエントリは、Clojure Advent Calendar 2014 21日目、および Clojure Contrib Library Advent Calendar 2013 24日目の記事です。)

今回はClojureのcontribライブラリであるtools.analyzerとtools.emitterを使ってカスタマイズしたClojure処理系を作ってみます。

tools.analyzer/tools.emitterとは

tools.analyzerとtools.emitterはClojureのセルフホスティングコンパイラ、つまりClojureで書かれたClojureコンパイラを構成するライブラリ群です。以前からCinC(Clojure in Clojure)という名前だけがあったプロジェクトが、ようやく具体的にcontribライブラリという形で開発が進められているという状況です。これらのライブラリは、Clojureのコア開発陣であるCognitectから出資を受けたり、Typed Clojureクラウドファンディングで集めた資金の一部が使われるなど、開発に非常に期待がかけられていて、将来的にClojure標準の次期コンパイラになる実装だと考えられます。

tools.analyzer/tools.emitterの大雑把な構成はこうです。 tools.analyzerとtools.emitterは抽象構文木(AST)を中心にして、ASTを作るまでの構文解析部分をtools.analyzerが、ASTを作った後の(ターゲット言語での)コード生成部分をtools.emitterが担当します。

tools.analyzer/tools.emitterからなるこの枠組みは、実際にはClojureだけでなく、ClojureScriptも対象にしています。ClojureとClojureScriptは言語としても微妙に違いますし、ターゲット言語もかたやJVMバイトコード、かたやJavaScriptと異なっています。
このような状況に対応するために、

  • ASTの拡張可能な標準フォーマットを規定
  • ソース言語の共通部分についてはtools.analyzerが対応
  • ソース言語固有の部分はanalyzerの拡張ポイントで対応
  • ターゲット言語ごとにemitterを実装

という構成になっています。
これをさきほどの図に反映させると、こんな感じになるでしょうか*1

ClojureおよびClojureScriptの解析には、それぞれtools.analyzer.jvmおよびtools.analyzer.js(以下、t.a.jvmおよびt.a.js)という個別のライブラリを使います。Clojureのコード生成にはtools.emitter.jvm(以下t.e.jvm)というライブラリを使うことができます。現時点では、ClojureScript用のJavaScriptコード生成に使えるemitterの実装はありません。

インストール

tools.analyzer/tools.emitterをLeiningenから使うには、以下を依存ライブラリとして追加します。各ライブラリのバージョンは2014/12/20時点の最新版です。

[org.clojure/tools.analyzer "0.6.4"]
[org.clojure/tools.analyzer.jvm "0.6.5"]
[org.clojure/tools.analyzer.js "0.1.0-SNAPSHOT"]
[org.clojure/tools.emitter.jvm "0.1.0-SNAPSHOT"]

これらのライブラリ間には、t.a.jvmおよびt.a.jsがtools.analyzerに依存し、t.e.jvmがtools.analyzerとt.a.jvmに依存する、という依存関係があります。どのライブラリも開発途上でまだまだ不安定で、互換性のないバージョン同士を一緒に使うとうまく動かないこともあります。そのため、各ライブラリのバージョンを個別に指定するのではなく、依存するライブラリのバージョンをLeiningenに解決してもらった方が安全でしょう。

analyzer/emitterの使い方

analyzerとemitterの使い方を見てみましょう。ここではtools.analyzer.jvmとtools.emitter.jvmについて見てみます。

tools.analyzer.jvmの使い方

tools.analyzer.jvmのエントリポイントの1つはanalyze関数です。analyzeは解析するフォーム1つを引数にとり、解析結果を戻り値として返します。

user=> (require '[clojure.tools.analyzer.jvm :as a])
nil
user=> (set! *print-level* 2)   ;; 解析結果は巨大なマップになるので表示を省略
2
user=> (a/analyze '(let [x 42] x))
{:children [:bindings :body], :bindings [#], :op :let, :env {:file "/private/var/folders/zr/_mpf274n7mn0_5fyx84ypb280000gn/T/form-init3642608216430177312.clj", :line 1, :column 13, :context :ctx/expr, :locals #, :ns user}, :o-tag long, :top-level true, :form (let* # x), :tag long, :body {:o-tag long, :tag long, :body? true, :op :do, :env #, :form #, :statements #, :ret #, :children #}, :raw-forms (#)}
user=>

tools.analyzer.jvmには他にも、名前空間全体を一括して解析するanalyze-nsや、解析した後に解析した結果をevalするanalyze+evalなどが用意されています。詳しくはリファレンスを参照して下さい。

tools.emitter.jvmの使い方

tools.emitter.jvmはevalとloadを提供します。どちらもClojure標準にある関数を、tools.analyzer/tools.emitterのツールチェーンによる実装に置き換えたもので、標準のものと同じように使うことができます。

user=> (require '[clojure.tools.emitter.jvm :as e])
nil
user=> (e/eval '(let [x 42] x))
42
user=> (e/load "foobar/core")
nil
user=>

analyzer/emitterの拡張

さきほど述べたとおり、analyzer/emitterの枠組みは拡張することを想定して作られています。ここではオリジナルのanalyzer/emitterの作り方について概要をサラッと説明します。

analyzerを作る

tools.analyzerには、各analyzerが実装するべき拡張ポイントが用意されています。自分でanalyzerを実装する場合には、この拡張ポイントを実装する必要があります。

  • macroexpand-1: マクロ展開処理
  • parse: 特殊形式をパースするマルチメソッド
  • create-var: Varの生成処理
  • var?: オブジェクトがVarかどうかをテストする述語

Varに関する関数が拡張ポイントになっているのは奇妙に感じるかもしれませんが、これはClojureとClojureScriptという異なるプラットフォーム上ではVarの扱いが変わることに起因します。

また、analyzeから生成されたASTに対して実行する処理を「パス」として提供することもできます。「パス」は特殊形式単位よりも広い範囲の構文木を見ながら進める必要がある処理を記述するために用意されています。tools.analyzerは「パス」処理用のスケジューラを持っていて、構文木全体をなめる回数をなるべく少なくするように動作します。

emitterを作る

analyzerと異なり、emitterには決まった拡張ポイントはありません。基本的な構成としては、emitterがanalyzerを呼び出し、得られたASTを基にコード生成処理をする、という感じになります。

「パス」処理はemitterのコード生成に必要な処理を記述するのにも使えます。形式もanalyzerの場合と違いはありません。

「ぼくのかんがえたさいきょうのClojure

以上を踏まえたうえで、tools.analyzer/tools.emitterの枠組みを使って、カスタマイズしたClojure処理系を作ってみましょう。ここではtools.analyzer.jvmおよびtools.emitter.jvmをベースに考えます。

今回作るのは以下のような、インラインアセンブリとしてJVMバイトコードを記述できるようにする特殊形式を追加したClojureです。

(asm <インストラクション1>
     ...
     <インストラクションn>)

コンパイル結果のバイトコードには、asm特殊形式のボディにS式として書かれたJVMバイトコードのインストラクション<インストラクション1>, ..., <インストラクションn>がこの順に出力されます。

実装してみる

asm特殊形式を扱えるようなClojure処理系を作ってみましょう。

省力化のために、今回はtools.analyzer.jvmとtools.emitter.jvmの一部を上書きすることでanalyzer/emitterの実装に代えます。

実装の方針としては、analyzeした結果としてできるASTにasm特殊形式に渡されたインストラクション列を保持し、コード生成時にその保持したインストラクション列をそのままバイトコードに出力するようにします。

tools.emitter.jvmは内部にJVMバイトコード(の一部)をS式で記述できる機能を持っているので、それを流用してインストラクションをS式で書けるようにします。

細かいことをいろいろ省くと、この程度のコードで上記の機能を実現できます。

(ns prime-clojure.core
  (:require [clojure.tools.analyzer.jvm :refer [parse specials]]
            [clojure.tools.emitter.jvm.emit :refer [-emit]]))

(alter-var-root #'specials conj 'asm)

(defmethod parse 'asm [form env]
  {:op :asm
   :env env
   :form form
   :children []
   :insns (vec (for [[op & args] (rest form)]
                 `[~(keyword (name op)) ~@args]))})

(defmethod -emit :asm [{:keys [insns]} frame]
  insns)

実行例は以下のとおりです。

user=> (require 'prime-clojure.core)
nil
user=> (require '[clojure.tools.emitter.jvm :as e])
nil
user=>
(e/eval
  '(asm (push "hoge")
        (push "fuga")
        (invoke-virtual [java.lang.String/concat String] java.lang.String)))
"hogefuga"
user=> 

tools.emitter.jvmが持っているS式バイトコードがカバーするインストラクションの割合が思った以上に低いのでできることはだいぶ制限されていますが、同様の考えにしたがって自前で補完していけばカバー率を上げることができます(今回は時間が足りなかったので割愛)。

まとめ

今回は、tools.analyzer/tools.emitterの紹介と、それらを使ったClojure処理系の自作方法について見てきました。

上でも触れたように、tools.analyzer/tools.emitterはまだまだ開発途上で、tools.emitter.jvmが提供するevalはClojure標準のものより5~8倍遅いようなので、今すぐに現行コンパイラを置き換える存在になれるわけではなさそうです。しかし、Clojureで書かれている分、Javaで書かれた現行コンパイラよりも変更が容易なため、いろいろなコンパイル技術を試すプロトタイピング環境としては今からでも期待できるでしょう。今後の開発が進んでいくのが楽しみです。

明日はnobkzさんの番です。乞うご期待!

*1:ここでは説明のためにtools.emitterという名前をtools.emitter.*の総称として使っていましたが、実際にはtools.emitterというライブラリはありませんので注意して下さい