clojurescriptのinitial commitのrecurの実装を理解する
初めはinitial commitをすべて解説しようと思ったが記事としてまとまりのあるものにできなさそうなのでrecurを理解することに絞って解説してみることにする。
動機
clojurescriptの実装を理解したいが、実際のコード が縦に長いため(無駄に詳細に引きずられてしまい)目的意識なしでは読むのが結構辛そうだった。初期のコミットから追っていったほうが時間がかかるとはいえ理解できるのではないかと思ったため。 準備
git checkout 515900f9762102987bda7d53b919dafc0b6c0580 などする。
概観
clojureの式をどのような順番でjsに変換していっているかを概観する。以下の式に注目する。
code: clojure
`(emit (analyze {:ns (symbol "test.ns") :context :expr :locals {}} '~form)))
analyze -> emit という順番で処理が進んでいっていることがわかる。analyzeはclojureの式+env(envの構造については後で触れる)をとり、中間データ(今後ASTと書く。ASTと言いつつ、束縛の情報や、emitが知りたい情報がいろいろ含まれている)を吐く。ASTからjsのコードに変換するのが emit. analyzeもemitも(だいたい)マルチメソッドになっていて、analyzeはformのfirstでディスパッチし、emitは:opでディスパッチするようになっている。ある式がどのようにコンパイルされるのかを理解するためには、analyzeの出力を眺める -> analyzeの実装を見る -> emitの出力をみる -> emitの実装をみる、という順番でやっていくのが良さそう.
ASTのデータ構造
試しに analyze にいろいろな入力を食わせてみて、どのような情報がASTに含まれているか観察することにする。全部は解説しないので自分で対応を眺めてみてほしい。
code:clojure
`(analyze {:ns (symbol "test.ns") :context :expr :locals {}} '~form))
(ana nil)
=> {:op :constant, :env {:locals {}, :ns test.ns, :context :expr}, :form nil}
(ana 42)
=> {:op :constant, :env {:locals {}, :ns test.ns, :context :expr}, :form 42}
(ana "foo")
=> {:op :constant, :env {:locals {}, :ns test.ns, :context :expr}, :form "foo"}
;; 便宜のため anaを少し変更
`(clojure.pprint/pprint (analyze {:ns 'test.ns :context :expr :locals {(symbol "ethel") {:name (symbol "ethel_123") :init nil}}} '~form)))
(ana fred)
=>
{:env
{:locals {ethel {:init nil, :name ethel_123}},
:ns test.ns,
:context :expr},
:form fred,
:op :var,
:info {:name test.ns.fred}} ;; :envの:nsがtest.nsなので、test.ns.fredになる
(ana ethel)
=>
{:env
{:locals {ethel {:init nil, :name ethel_123}},
:ns test.ns,
:context :expr},
:form ethel,
:op :var,
:info {:init nil, :name ethel_123}} ;; 束縛が :localsにあるのでそれを利用
(ana (if true 1 2))
=>
{:env
{:locals {ethel {:init nil, :name ethel_123}},
:ns test.ns,
:context :expr},
:op :if,
:form (if true 1 2),
:test
{:op :constant,
:env ...,
:form true},
:then
{:op :constant,
:env ...,
:form 1},
:else
{:op :constant,
:env ...,
:form 2},
:children ...}
:childrenは リストで表現されている式の、部分式のanalyzeの結果を順番に並べただけのもので、見づらいので省略した。このコミットの時点では利用されていないので気にする必要はない。:op に応じて emitがdispatchされる。
envの構造
:envの:locals は シンボルがキーでと {:init hoge :name fuga}がバリューのマップ。:initは初期値で:nameは出力されるJSプログラムに現れる変数名。
:contextは :expr :statement :returnがある。JSには文の概念があるので、clojureの式をコンパイルする際にはその情報が必要。
code: javascript
function () {
var x = 12; // ここの12の部分には、文ではなく式を置く必要がある。12のコンパイルには:context :exprを伝えてやる必要がある。
console.log(x); // :context :statement (文で、関数の最後の文でないもの)
return x; // :context :returnに対応
}
emit-wrapの定義と上の説明が対応していることがわかるだろう。
code: clojure
(when (= :return (:context env#)) (print "return "))
~@body
(when-not (= :expr (:context env#)) (print ";\n"))))
:nsは現在のネームスペースを示している。 x -> test.ns.xのようにvarをプロパティ参照の形にするのにつかわれる。
*recur-frame*
recur関連のanalyzeに利用されるダイナミック変数。
code: clojure
(def ^:dynamic *recur-frame* nil)
(defmacro disallowing-recur body
`(binding *recur-frame* nil ~@body)) ;; recurできない部分のコンパイルにはdisallowing-recurマクロで囲んで、recurが使えないという情報を伝える。 *recur-frame*はハッシュマップ。どのキーにどのようなデータが使われるかを見る。
:names (fn* [x y z] ...) の ...をコンパイルするときの :namesは [x y z], (loop [x y] ...) の ... をコンパイルするときは [x y]にセットされる。recurに正しい数の引数が渡されているかチェックしたり、反復のたびに更新される変数の x = ...というJSの更新の式を生成するのに使う。
:flag atomで、recurを analyzeするときに (reset! (:flag *recur-frame*))される。 補助的なデータ構造で、これ自体は (fn* [x] ...) の ...の部分にrecurが現れるかどうかを fn*のanalyzeに教えてくれる。この情報があると、ちょっと効率の良いコードが吐けて嬉しい(後で見る)
*recur-frame*が nilの状態で recurが analyzeの対象になるとエラーになるようになっている。
準備が整ったので、fn* + recur、loop + recurのコンパイル過程を理解していく。それぞれについて、analyzeの出力を眺める -> analyzeの実装を見る -> emitの出力をみる -> emitの実装をみる、という順番でやっていく。
fn* + recur
analyzeの出力を眺める
code: clojure
(ana (fn* x (if (= x 0) 1 (recur 0)))) =>
{:ret ;; :retに(if (= x 0) 1 (recur 0))の部分のanalyze結果が入っている
{:env {:ns test.ns, :context :return, :locals {x {:name x}}},
:op :if,
:form (if (= x 0) 1 (recur 0)),
:test ...,
:then ...,
:else
{:env {:ns test.ns, :context :return, :locals {x {:name x}}},
:op :recur,
:exprs
[{:op :constant,
:env {:ns test.ns, :context :expr, :locals {x {:name x}}},
:form 0}]},
:children ...},
:children ...,
:recurs true, // この情報は fn*のコンパイルでのみ使われて、少しだけ効率の良いコードを吐くことができる.
:name nil,
:params (x),
:op :fn,
:env {:ns test.ns, :context :statement},
:meths ((x (if (= x 0) 1 (recur 0)))), :statements nil}
fn*と recurの analyzeをみる
code: clojure
;; 長いので注目している部分以外は消してある
(defmethod parse 'fn*
[op env & args name]
(let [name ...
meth ...
params ... ;; (fn* x y ...)なら x body ... ;; (fn* x (println x) (+ x 1))なら ((println x) (+ x 1)) locals (reduce (fn m name (assoc m name {:name name})) (:locals env) params) ;; params: x y, locals: {} -> {x {:name x}, y {:name y}} recur-frame {:names (vec params) :flag (atom nil)}
;; (fn* x ...) の場合 {:names x :flag (atom nil)}になる (analyze-block (assoc env :context :return :locals locals) body))]
...
(merge {:env env :op :fn :name name :meths meths :params params :recurs @(:flag recur-frame)} block)))
;; :recursがどのようなときにtrueになるかを考えると、atomになっているrecur-frameの:flagがreset! trueされたとき。それは、analyze-blockの呼び出し内部でrecurが見つかった時だけ。
(defmethod parse 'recur
[op env & exprs _]
(assert *recur-frame* "Can't recur here")
;; recurの引数チェック. (fn* x y (recur 1 2 3))みたいなのを防ぐ。 (assert (= (count exprs) (count (:names *recur-frame*))) "recur argument count mismatch")
(reset! (:flag *recur-frame*) true) ;; dynamic varを通じてrecurを発見したことを教える
(assoc {:env env :op :recur}
:frame *recur-frame*
:exprs (disallowing-recur (vec (map #(analyze (assoc env :context :expr) %) exprs)))))) emitを見てみる。
code: clojure
(fn* x (if (= x 0) 1 (recur 0))) =>
(function (x){
while(true){
if(cljs.lang.truth(cljs.lang.fnOf(test.ns.=)(x,0)))
return 1;
else
{
var G__8972 = 0;
x = G__8972;
continue;
}
break;
}
})
JSのwhileにへんかんされていることがわかる。(fn* [x] x)など `recurを使わないものと比較してみる。
code: clojure
(emit (ana (fn* x x x x))) =>
(function (x){
x;
x;
return x;
})
whileがなくなっている。これは先ほど見た :recursを利用している。emitの対応する部分を見る。
code: clojure
(defmethod emit :fn
;;fn statements get erased, serve no purpose and can pollute scope if named
(when-not (= :statement (:context env))
(emit-wrap env
(print (str "(function " name "(" (apply str (interpose "," params)) "){\n"))
(when recurs (print "while(true){\n")) ;; :recursを利用
(emit-block :return statements ret)
(when recurs (print "break;\n}\n")) ;; recursを利用
(print "})"))))
(defn emit-block
(if statements
(let [body (str "\t" (apply str (interpose "\t" (map emits statements)))
"\t" (emits ret))]
(print body))
(emit ret)))
(defmethod emit :recur
(let [temps (vec (take (count exprs) (repeatedly gensym)))
names (:names frame)]
(print "{\n")
(print (str "var " (temps i) " = " (emits (exprs i)) ";\n"))) ;; (recur a b c) として、式a,b,cの評価結果を入れるための一時変数を作る。
(print (str (names i) " = " (temps i) ";\n")))
;; ここらへんは、 (print (str (names i)) " = " (emits (exprs i)) ";\n"))としてもよさそうだが... だめなケースがあるかはわからなかった
(print "continue;\n")
(print "}\n")))
loop + recur
一気に見る。
code: clojure
(recur 1))) ;; かんたんのため無限ループするコード
=>
{:env {:ns test.ns, :context :statement},
:op :let,
:loop true,
:bindings
[{:name x__8975,
:init
{:op :constant, :env {:ns test.ns, :context :expr}, :form 1}}],
:statements nil,
:ret
{:env
{:ns test.ns,
:context :statement,
:locals
{x
{:name x__8975,
:init
{:op :constant, :env {:ns test.ns, :context :expr}, :form 1}}}},
:op :recur,
:exprs
[{:op :constant,
:env
{:ns test.ns,
:context :expr,
:locals
{x
{:name x__8975,
:init
{:op :constant, :env {:ns test.ns, :context :expr}, :form 1}}}},
:form 1}]},
:form (loop x 1 (recur 1)), :children ...}
(defmethod parse 'loop
(analyze-let encl-env form true))
;; loopの処理はanalyze-letが担っている
(defn analyze-let
[encl-env bindings & exprs :as form is-loop]
(assert (and (vector? bindings) (even? (count bindings))) "bindings must be vector of even number of elements")
(let [context (:context encl-env)
bes env ... ;; x 1 の1の部分をanalyzeし、:locals {x {:name x_123, :init {:op :constant, :env {:ns test.ns, :context :expr}, :form 1}}} 新しいローカル束縛環境をenvとする recur-frame (when is-loop {:names (vec (map :name bes)) :flag (atom nil)})
(analyze-block (assoc env :context (if (= :expr context) :return context)) exprs))]
{:env encl-env :op :let :loop is-loop ;; loopのときは、内部でrecurが使われるかにかかわらず:loop trueならループを生成する. emitを参照。
:bindings bes :statements statements :ret ret :form form :children (into children (map :init bes))})) ;; emitをみる
=>
(function (){
var x__8978 = 0;
while(true){
{
var G__8979 = 1;
x__8978 = G__8979;
continue;
}
break;
}
})()
;; emitのコード
(defmethod emit :let
(let [context (:context env)
(str "var " name " = " (emits init) ";\n"))
bindings)]
(when (= :expr context) (print "(function ()"))
(print (str "{\n" (apply str bs) "\n")) ;; var x__8978 = 0;の部分。
(when loop (print "while(true){\n"))
(emit-block (if (= :expr context) :return context) statements ret)
(when loop (print "break;\n}\n"))
(print "}")
(when (= :expr context) (print ")()"))))
感想
clojureとJSだと式志向かそうでないかの違いがあるので、:contextをコンパイル時に引きまわす必要があるということだろう。
dynamic varで呼び出された関数から呼び出し元に情報を伝えたいパターンがきれいに書けるのはかなり嬉しそう.
cljs.org なるファイルに設計方針などが書いてあって興味深いので覗いてみると楽しいかもしれない コードの解説は余計なコードは省略するとわかりやすくなるのかなと思った