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クラスなので,ClojureJava 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のような機能を好きなように作れるはず。このあたりをさらに掘り下げるもっとおもしろいことができそう。

まとめ

ということで,今回は

  • Clojureコードは内部でExprという内部形式に変換される
  • Exprは主に2つメソッド(eval, emit)をもち,(基本的には)evalはインタプリタから,emitはコンパイラから呼ばれる
  • clojure.lang.Compiler/analyzeを呼ぶことでClojureからでもExprオブジェクトへの変換ができる
  • オンザフライのクラス生成にはObjExprが関係している

といったようなことが分かった,というまとめ。