Clojure 内部で使われる中間形式 Expr について分かったこと
最近,暇を見つけてClojureのコンパイラを読んでいる。まだよく分かっていない部分もたくさんあるけれど,今まで読んできた中で分かったこと,特にClojureの内部で使われている "Expr" という中間形式についてまとめておく。
Expr って何?
Clojureの内部では,以下のような処理が行われている。
Exprは,次のように定義されるインタフェースで,抽象構文木の各ノードを表す。
interface Expr{ Object eval() throws Exception; void emit(C context, ObjExpr objx, GeneratorAdapter gen); boolean hasJavaClass() throws Exception; Class getJavaClass() throws Exception; }
重要なのが eval と emit という2つのメソッド。大まかにいえば,REPL(インタプリタ)から呼ばれるのがevalで,コンパイラから呼ばれるのがemitだ。
Clojureの構文それぞれについてExprの実装クラスが用意されていて,全部でだいたい50個くらいある。
$ sed -n -e '/class [a-zA-Z]*Expr/p' Compiler.java public static abstract class UntypedExpr implements Expr{ static class DefExpr implements Expr{ public static class AssignExpr implements Expr{ public static class VarExpr implements Expr, AssignableExpr{ public static class TheVarExpr implements Expr{ public static class KeywordExpr extends LiteralExpr{ public static class ImportExpr implements Expr{ public static abstract class LiteralExpr implements Expr{ static public abstract class HostExpr implements Expr, MaybePrimitiveExpr{ static abstract class FieldExpr extends HostExpr{ static class InstanceFieldExpr extends FieldExpr implements AssignableExpr{ static class StaticFieldExpr extends FieldExpr implements AssignableExpr{ static abstract class MethodExpr extends HostExpr{ static class InstanceMethodExpr extends MethodExpr{ static class StaticMethodExpr extends MethodExpr{ static class UnresolvedVarExpr implements Expr{ static class NumberExpr extends LiteralExpr implements MaybePrimitiveExpr{ static class ConstantExpr extends LiteralExpr{ static class NilExpr extends LiteralExpr{ static class BooleanExpr extends LiteralExpr{ : : (以下略)
Expr を解析するツール
ClojureプログラムからExprへのパースは,clojure.lang.Compilerクラスのanalyzeメソッドを呼び出すことで実行される。Compilerクラスといえども一介のJavaクラスなので,ClojureのJava interopの機能を利用してClojureから呼び出すことができる。そこで,analyzeによるパースを適当にClojureのオブジェクトに変換してくれるツールを作った。ソースコードはanalyze.clj。
簡単な実行例はこんな感じ。
Clojure 1.2.0 user=> (use 'analyze) nil user=> (analyze 0) {:$ ConstantExpr, :v 0} user=> (analyze ''(0 1)) {:$ ConstantExpr, :v (0 1)} user=> (analyze [0 1]) {:$ VectorExpr, :args [{:$ ConstantExpr, :v 0} {:$ ConstantExpr, :v 1}]} user=> (analyze "hoge") {:$ StringExpr, :str "hoge"} user=> (analyze 'cons) {:$ VarExpr, :var #'clojure.core/cons} user=> (analyze '(+ 0 1)) {:$ StaticMethodExpr, :c clojure.lang.Numbers, :method-name "add", :args [{:$ ConstantExpr, :v 0} {:$ ConstantExpr, :v 1}]} user=> (pprint (analyze '(fn [] 0))) {:$ MetaExpr, :meta {:$ MapExpr, :keyvals [{:$ KeywordExpr, :k :line} {:$ ConstantExpr, :v 9}]}, :expr {:$ FnExpr, :methods [{:$ FnMethod, :req-parms [], :rest-parms nil, :body {:$ BodyExpr, :exprs [{:$ ConstantExpr, :v 0}]}}]}} nil user=>
analyzeの内部では,clojure.lang.Compilerクラスのanalyzeメソッドを呼び出し,結果として返ってきたExprオブジェクトを適当にClojureのMapに変換している。analyzeを2引数で呼び出すと,第1引数で解析するコンテキストを指定することができる。コンテキストには,EVAL, EXPRESSION, RETURN, STATEMENT の4つがある。コンテキストの違いについてはいまいちよく分かっていないけど,EVALがREPLから入力されたトップレベルのフォーム,EXPRESSIONが通常の式,RETURNが末尾位置,STATEMENTが値を捨てていいコンテキストを表しているらしい,という理解。
指定するコンテキストが異なると解析できない構文もある。このあたりも謎。
user=> (pprint (analyze EVAL '(let [x 0] x))) {:$ InvokeExpr, :fexpr {:$ FnExpr, :methods [{:$ FnMethod, :req-parms [], :rest-parms nil, :body {:$ BodyExpr, :exprs [{:$ LetExpr, :binding-inits [{:$ BindingInit, :binding {:$ LocalBinding, :sym x, :init {:$ ConstantExpr, :v 0}}}], :body {:$ BodyExpr, :exprs [{:$ LocalBindingExpr, :b {:$ LocalBinding, :sym x, :init {:$ ConstantExpr, :v 0}}}]}}]}}], :compiled-class user$fn__1056}, :args []} nil user=> (pprint (analyze EXPRESSION '(let [x 0] x))) java.lang.NullPointerException (NO_SOURCE_FILE:81) user=> (pprint (analyze RETURN '(let [x 0] x))) java.lang.NullPointerException (NO_SOURCE_FILE:82) user=> (pprint (analyze STATEMENT '(let [x 0] x))) java.lang.NullPointerException (NO_SOURCE_FILE:83) user=>
インタプリタとコンパイラをつなぐ ObjExpr
さっき「evalはインタプリタから呼ばれ,emitはコンパイラから呼ばれる」とざっくり説明したが,この2つは完全に分業しているわけじゃない。というのも,Clojureの関数はJavaのオブジェクトとして実現されていて,そのためにClojureのインタプリタでは,オンザフライでクラスを生成する必要があるためだ。他に,reify や deftype の実現にも動的なクラス生成が使われている。
こういった動的なクラス生成を担っているのがObjExprで,compileメソッドを呼ぶことでバイトコードを生成できる。このcompileメソッドは,fnやreify, deftypeをanalyzeするときに呼ばれる。なので,たとえば先程のanalyze関数で解析すると,その時点ですでにクラスが生成されている。
user=> (-> (analyze '(fn [] (println "Hello, World"))) :expr :compiled-class) user$fn__1183 user=> (clojure.lang.Reflector/invokeConstructor *1 (object-array 0)) #<user$fn__1183 user$fn__1183@477b1683> user=> (*1) Hello, World nil user=>
ObjExprのサブクラスを作って,適当なメソッド(emitMethodsあたり)をオーバーライドすれば,reifyやdeftypeのような機能を好きなように作れるはず。このあたりをさらに掘り下げるもっとおもしろいことができそう。