読者です 読者をやめる 読者になる 読者になる

Clojureコンパイラの型推論器をとりだしてみる

clojure.orgには,Clojureについて次のような説明がある。

Clojure provides easy access to the Java frameworks, with optional type hints and type inference, to ensure that calls to Java can avoid reflection.

http://clojure.org/

この型推論(type inference)は,Clojureの説明でたまに名前だけは出てくるものの,その実態についての説明にはほとんどお目にかかったことがない。そこで今回は,Clojureの型推論の機能をClojureから触れるようにして遊んでみよう。

Clojureになぜ型推論が必要か

まずはじめに注意しておかないといけないのは,Clojureの型推論はMLやHaskellなどの静的型付言語がもつそれとは目的が異なるということだ。Clojureの型推論は型安全性のためには役立たない。型が推論できたからといって型の誤りによるエラーが実行時に起こらないという保証にはならないし,型が推論できないからといって必ずしも誤りがあるというわけでもない。

じゃあClojureの型推論が何のためにあるかというと,上の引用にもあるとおり「Javaにアクセスする際のリフレクションを極力避けるため」だ。

Clojureは実行時に型をチェックする言語なので,プログラムの断片を見ただけでは変数がどんな型の値に束縛されるか分からないことがある。

(defn upper-case [x]
  (.toUpperCase x))

たとえば,上のコードではxがどんな型をもつのかは実際にこの関数が呼び出されるまで分からない。そのため,ここで呼ばれているtoUpperCaseというメソッドもどのクラスに属するものなのかすら分からない。それにも関わらずこのコードがエラーも生じずに実行できるのは,xの実行時の型情報からJVMのリフレクションを使って適切なメソッドを選び出して呼び出しているためだ。メソッド呼び出しだけでなく,ClojureからJavaのフィールドにアクセスする場合にも同様の仕組みが内部では動いている。

しかし,リフレクションを介したメソッド呼び出しやフィールドへのアクセスは,リフレクションを介さないものと比較するとかなり効率が悪い(実行時間にして1〜2桁くらい遅い)。そこでClojureでは,「型ヒント」を入れることによって,リフレクションを発生させないようにすることができる。

(defn upper-case' [x]
  (.toUpperCase ^String x))  ; xがStringであることを型ヒントで指定
;; リフレクションが発生するバージョン
user=> (dotimes [_ 5] (time (dotimes [_ 100000] (upper-case "hoge"))))
"Elapsed time: 1188.655 msecs"
"Elapsed time: 1246.814 msecs"
"Elapsed time: 1165.256 msecs"
"Elapsed time: 1346.774 msecs"
"Elapsed time: 1296.931 msecs"
nil
;; 型ヒントによってリフレクションを抑制したバージョン
user=> (dotimes [_ 5] (time (dotimes [_ 100000] (upper-case' "hoge"))))
"Elapsed time: 39.685 msecs"
"Elapsed time: 35.238 msecs"
"Elapsed time: 36.961 msecs"
"Elapsed time: 44.772 msecs"
"Elapsed time: 76.312 msecs"
nil
user=> 


これでリフレクションの問題は解決できる。ただし,型ヒントだけでは不十分だ。より複雑なプログラムを書く場合,メソッドの呼び出しやフィールドへのアクセスのたびに型ヒントを書くのは面倒になる。

;; メソッド呼び出しのたびに型ヒントをつけるのは辛い…
(defn f [^String x]
  (-> x
      ^String (.toUpperCase)
      ^String (.substring 1 4)
      ^String (.startsWith "HOGE"))
;; できればこんな感じにすっきり書きたい
(defn f [^String x]
  (-> x
      (.toUpperCase)
      (.substring 1 4)
      (.startsWith "HOGE")))

必要最低限だけ型ヒントをつければ,あとは静的に分かる情報からうまく型を導き出してくれるような仕組みがほしい。それがClojureの型推論だ。

型推論と内部表現

前置きが長くなった。ここからが型推論についての具体的な内容になる。
Clojureの型推論は,以前にこのブロクでも説明したClojureコンパイラが使う内部表現Exprによって処理される。

Exprは以下のように定義されている。

interface Expr{
        Object eval() throws Exception;
        void emit(C context, ObjExpr objx, GeneratorAdapter gen);
        boolean hasJavaClass() throws Exception;
        Class getJavaClass() throws Exception;
}

このうちの hasJavaClass() および getJavaClass() が型推論に関連するメソッドだ。Clojureの型推論は,冒頭で触れたとおり,式によっては型が推論できず失敗することがある。hasJavaClass()は,その式から型が推論できる場合にtrueを返し,そうでなければfalseを返す。getJavaClass()は実際に推論された型を返す。getJavaClass()は,hasJavaClass()がtrueを返す場合以外に呼び出すとエラーになる可能性がある。

型推論ツール

Clojureの型推論の仕組みが分かれば,それを利用するツールを作るのは難しくない。

(ns type-infer)

(defmacro $ [c]
  (symbol (str 'clojure.lang.Compiler$ c)))

(defn call-private [class method obj]
  (let [args (into-array Class nil)
        m (.getDeclaredMethod class (str method) args)]
    (when-not (.isAccessible m)
      (.setAccessible m true))
    (.invoke m obj clojure.lang.RT/EMPTY_ARRAY)))

(defn extract [x]
  (let [i? instance?]
    (if (i? ($ InvokeExpr) x)
      (let [fexpr (.-fexpr x)]
        (if (and (i? ($ FnExpr) fexpr)
                 (empty? (.-args x)))
          (.-body (first (.-methods fexpr)))
          x))
      x)))

(defn infer-fn [x]
  (let [expr (extract (Compiler/analyze clojure.lang.Compiler$C/EVAL x))]
    (if (boolean (call-private ($ Expr) 'hasJavaClass expr))
      {:class (call-private ($ Expr) 'getJavaClass expr)})))

(defmacro infer [x]
  (infer-fn x))

ここでは使い方について特に説明しないが,以降の例で使い方と結果の見かたは分かるはずだ。

Clojureの型推論の実態

このツールを使って,実際にClojureの型推論がどうなっているのか調べてみよう。

リテラル

まず基本的なところで,いろんなデータ型のリテラルを試してみる。

user=> (infer 1)
{:class long}
user=> (infer 42)
{:class long}
user=> (infer 3.14)
{:class double}
user=> (infer 1N)
{:class clojure.lang.BigInt}
user=> (infer 1M)
{:class java.math.BigDecimal}
user=> user=> (infer \a)
{:class java.lang.Character}
user=> (infer "hoge")
{:class java.lang.String}
user=> (infer 'sym)
{:class clojure.lang.Symbol}
user=> (infer :keyword)
{:class clojure.lang.Keyword}
user=> (infer #'cons)
{:class clojure.lang.Var}
user=> (infer java.lang.StringBuilder)
{:class java.lang.Class}
user=> (infer nil)
{:class nil}
user=>

うまく推論されていることが分かる。

コレクションリテラル

コレクションの型が推論される。コレクションの要素の型は分からない。

user=> (infer [1 2 3])
{:class clojure.lang.PersistentVector}
user=> (infer '(1 2 3))
{:class clojure.lang.PersistentList}
user=> (infer {:a 0, :b 1})
{:class clojure.lang.PersistentHashMap}
user=> (infer #{1 2 3})
{:class clojure.lang.PersistentHashSet}
user=>
トップレベルに定義された変数の参照

トップレベルに定義された変数の参照は,変数定義に型ヒントがつけられている場合にはその型が推論され,そうでない場合には推論に失敗する。

user=> (def ^String x "hoge")
#'user/x
user=> (infer x)
{:class java.lang.String}
user=> (def y "fuga")
#'user/y
user=> (infer y)
nil
user=> 
関数適用

関数適用は,適用される関数がトップレベルに定義されていて,かつ,関数の定義に型ヒントがつけられている場合にはその型が推論され,そうでない場合には推論に失敗する。

user=> (defn f ^String [x] (str x))
#'user/f
user=> (infer (f 1))
{:class java.lang.String}
user=> (defn g [x] (str x))
#'user/g
user=> (infer (g 1))
nil
user=>
if

第2引数と第3引数の式の型が推論でき,かつ,推論された型が等しい場合には,その型がif式の型として推論される。そうでない場合には推論に失敗する。

user=> (infer (if true 0 1))
{:class long}
user=> (infer (if true 0 'a))
nil
user=> 
let

letの本体における最後の式の型が推論できる場合には,その型がlet式の型として推論される。そうでない場合には推論に失敗する。letで束縛される変数の参照は,変数の束縛に型ヒントがつけられている場合にはその型が推論される。型ヒントがつけれておらず,初期化の式から型が推論できる場合にはその型が推論される。loopも同様の規則に基づく。

user=> (infer (let [^String x nil] x))
{:class java.lang.String}
user=> (infer (let [x 0] x))
{:class long}
user=> 
fn

Clojureの関数型を表す抽象クラスAFunctionが推論される。

user=> (infer (fn [x] (* x x)))
{:class clojure.lang.AFunction}
user=>
Java interop

Javaのクラスのコンストラクタ呼び出しは,そのクラスが推論される。メソッド呼び出しはメソッドの戻り値が推論される。フィールドの参照はフィールドの型が推論される。

user=> (infer (StringBuilder.))
{:class java.lang.StringBuilder}
user=> (infer (Integer/valueOf "hoge"))
{:class java.lang.Integer}
user=> (infer System/out)
{:class java.io.PrintStream}
user=> 


以上のことをふまえると,これくらいの複雑さの式なら型を推論してくれることが分かる。

user=> (infer
  #_=>   (loop [x 10, a 0, b 1]
  #_=>     (if (zero? x)
  #_=>       a
  #_=>       (recur (dec x) b (+ a b)))))
{:class long}
user=>

まとめ

というわけで,今回はClojureの型推論について以下の内容を説明した。

  • Clojureでは,リフレクションを抑える目的でつけられる型ヒントを必要最小限にするために型推論の仕組みをもつ
  • Clojureの型推論は,ExprのhasJavaClass()/getJavaClass()によって実現される
  • hasJavaClass()/getJavaClass()を利用することで,ClojureからClojureの型推論に触わることができる
  • 自作の型推論ツールを使って,Clojureの各式からどんな型が推論されるか確認できる