Julia のメタプログラミング 1 -- Parse time hack
この記事は CAMPHOR- Advent Calendar 2019 20日目の記事です。
Julia は,"Walks like Python. Runs like C." ("Python のように簡単に書けて,C のように早く実行される") という文言で言い表されるように,プログラマの生産性とプログラムの効率性の両立を最大の特徴とする言語です.
一方で,その型システムやメタプログラミングに代表されるような,言語としての表現力の高さも大きな魅力です.
今回は,2つの記事にまたがって Julia が Lisp から受け継いだ強力なメタプログラミングの機能を紹介したいと思います.
この記事では,メタプログラミングの概説と,Julia の parse time を hack する方法を説明します.
初めて技術記事を投稿するので,指摘点などあればぜひ教えていただけると嬉しいです! :)
メタプログラミングとは
メタプログラミングを簡単に言うと,「プログラム自身を操作するプログラミング」ということになると思います.
ここで重要なのは,プログラムが,プログラマが操作することができるデータ構造である,ということです. それによりプログラムをただのテキストデータとして操作(例えば文字列置換)するよりも遥かに複雑なことができるようになります.
...
といってもよく意味が分からないかもしれないので,まず例を見てみましょう:
julia> function foo(itr)
@show s = zero(eltype(itr))
for i in itr
s += i
end
return s
end;
julia> foo(1:10)
s = zero(eltype(itr)) = 0 # `@show` の出力
55 # `foo` の返り値
この関数内で @show
が「プログラムを操作するプログラム」に相当します. ここで注意してほしいのは,@show
の部分の出力が [プログラム] = [実際の値]
となっていることです.
関数を使う場合,関数は [プログラム]
(ここでは s = zero(eltype(itr))
という代入式) 自体を扱えないので,同様の出力を得るためには,プログラマが自ら println("s = zero(eltype(itr))", " = ", s = zero(eltype(itr)))
という面倒なコードを書かなければなりません.
一方で,マクロ( Julia では @show
のような @
がついているやつ) は [プログラム]
を受け取り,直接操作することが可能です. この場合だと @show
マクロは [プログラム]
を受け取り,それを println([プログラム], " = ",[実際の値])
というプログラムに書き換えることにより,上のようなちょっとリッチな print debug を可能にしています.
Julia の実行プロセスとメタプログラミング
メタプログラミングの本質は,プログラムの実行プロセスを理解すると,より分かりやすくなると思います.
Julia プログラムは大まかに分けて次のようなプロセスを経て実行されます:
- プログラムをパース: Julia program ⟹ AST1
- AST を "Lowering": AST ⟹ Lowered form (IR)2
- IR に対して型推論: Lowered form (IR) ⟹ Typed lowered form (IR)
- 型推論から得られた情報に基づいて LLVM instructions を生成: Typed lowered form (IR) ⟹ LLVM instructions
- LLVM が native code を生成: LLVM instructions ⟹ native code
- コンピュータが native code を実行
通常「プログラミング」は step 1. でパースされるプログラムを書くことを指しますが, 「メタプログラミング」は これらの実行プロセス中のプログラムの状態を書き換えること として考えることができるかもしれません.
上で紹介した,@show
のようなマクロは,step 1. の段階のプログラム(AST1と呼ぶ,(AST は "Abstraction Syntax Tree" の略)) を操作し,新しい AST を返すような, パースされた状態のプログラムに対して行うメタプログラミングです. なので,実際には上記のプロセスにおいては,次の step 1.5. が存在します.
1.5. step 1. の AST に含まれるマクロを展開: AST ⟹ AST
(1.5. のプロセス ("マクロ展開 (Macro expansion)" と呼びます)を経た後は,マクロを含まないプログラムと同様に型推論され,コード生成にかけられます.)
Julia においては,step 1.5. のマクロ展開を経たコードがどのようになっているか簡単に確認できます. @show
マクロがどのように展開されているかがわかると思います:
julia> @macroexpand function foo(itr)
@show s = zero(eltype(itr))
for i in itr
s += i
end
return s
end
:(function foo(itr)
#= none:2 =#
begin
Base.println("s = zero(eltype(itr)) = ", Base.repr(begin
#= show.jl:613 =#
var"#2692#value" = (s = zero(eltype(itr)))
end))
var"#2692#value"
end
#= none:3 =#
for i = itr
#= none:4 =#
s += i
end
#= none:6 =#
return s
end)
Parse time hack example: @generator
マクロ
上の方で「プログラムが,プログラマが操作することができるデータ構造である」といった意味は,この AST がある種のデータ構造を持っていて,Julia プログラマはマクロを通じて,この AST を自在に扱うことができるということです.
(AST をメタプログラミングの文脈でデータとして扱う場合は, "AST" ではなく,"Expression" と呼ぶことが多いので, 以降はそのように呼称します.)
Expression が具体的にどのようなデータ構造であるかは,Julia manual の metaprogramming chapter あるいは,developer document のsurface syntax AST chapter を参照するとよいですが,一番良いのはやはり実際に手で触ってみることだと思います.
ここでは例として,for
block から generator を作る @generator
マクロを作ってみましょう. (コードはここにもあげています)
イメージ: for loop を comprehension に変換して,generator にする
julia> g = @generator for i = 1:3
if isodd(i)
2i
else
i
end
end;
julia> collect(g)
3-element Array{Int64,1}:
2
2
6
Julia の expression は :(...)
quoting あるいは quote ... end
block から簡単に作成することができます. まず for
block がどのような expression なのか調べてみます.
# 代入 expression の AST
julia> ex = :(a = 10);
julia> typeof(ex) # Expr 型のデータ
Expr
julia> fieldnames(Expr)
(:head,:args)
julia> ex.head
:(=)
julia> ex.args # Symbol や Int などの「リテラル」も expression を構成する
2-element Array{Any,1}:
:a
10
# for block の AST
julia> ex = :(
for i = 1:3
if isodd(i)
2i
else
i
end
end
);
julia> ex.head
:for
# iteration の spec と iteration の body. NOTE: #= ... =# は行番号
julia> ex.args
2-element Array{Any,1}:
:(i = 1:10)
quote
#= none:3 =#
if isodd(i)
#= none:5 =#
2i
else
#= none:9 =#
i
end
end
julia> typeof.(ex.args)
2-element Array{DataType,1}:
Expr
Expr
Expression が木のようなデータ構造であり,head
field がそれがどのような AST であるかを表しているのがわかると思います.
Julia の for block iteration の specification には for i = itr
,for i in itr
,for i ∈ itr
の3つの方法がありますが,AST 上では全て for i = itr
の形に normalize されているようです.
julia> :(for i in 1:10; end)
:(for i = 1:10
#= none:1 =#
end)
julia> :(for i ∈ 1:10; end)
:(for i = 1:10
#= none:1 =#
end)
ここまでくればあとは簡単です. macro
キーワードを使って,expression を受け取って,expression を返すマクロを定義します.
ある expression に,変数に入っている他の expression を代入するときは,文字列への interpolation と同じように,$
で "expression interpolation" をします.
julia> macro generator(forblk)
@assert forblk.head === :for "for block expression should be given"
itrspec, body = forblk.args
@assert itrspec.head === :(=) "invalid for loop specification"
v, itr = itrspec.args
# `esc` が必要な理由は manual 参照: https://docs.julialang.org/en/v1/manual/metaprogramming/index.html#Hygiene-1
# 簡単に言うと,`body` や `v`,`itr` に含まれる変数名を,この macro の名前空間で評価しない
return :((
$(esc(body))
for $(esc(v)) in $(esc(itr))
))
end;
julia> @macroexpand @generator for i in 1:100
if isodd(i)
2i
else
i
end
end
:((begin
#= none:3 =#
if isodd(i)
#= none:5 =#
2i
else
#= none:9 =#
i
end
end for i = 1:100))
julia> g = @generator for i in 1:3
if isodd(i)
2i
else
i
end
end
Base.Generator{UnitRange{Int64},var"#13#14"}(var"#13#14"(),1:100)
julia> collect(g)
3-element Array{Int64,1}:
2
2
6
More hacks !: MacroTools.jl
マクロを書くとき,上のように一々 expression が具体的にどうなっているかを確認するのは面倒です.
そこで expression に対して pattern match を行ったり,expression walk (走査) を簡単に行える MacroTools.jl という素晴らしいパッケージがあるので,試してみましょう.
@capture
マクロは,expression に対して pattern match を行うことができます
julia> using Pkg; Pkg.install("MacroTools")
julia> using MacroTools
julia> ex = :(for i in 1:10; i; end);
julia> @capture(ex, for v_ = itr_; body_ end) # match したら true を返す
true
julia> v # match した expression
:i
julia> itr # match した expression
:(1:10)
julia> @capture(:(a = 10), for v_ = itr_; body_ end) # match しなければ false を返す
false
@capture
マクロを使うと,@generator
マクロをこのように書き換えることができます :)
julia> macro generator(forblk)
@assert @capture(forblk, for v_ = itr_; body_ end) "for block expression should be given"
return :((
$(esc(body))
for $(esc(v)) in $(esc(itr))
))
end;
prewalk
や postwalk
関数を用いて,expression を 2分木のように走査することもできます:
julia> macro plus2minus(ex)
ex = postwalk(ex) do x
x === :+ ? :- : x # expression 内の全ての `+` を `-` に置き換え
end
return esc(ex)
end;
julia> a = 100;
julia> @plus2minus for i = 1:(200 + 100) # @plus2minus マクロによって `200 - 100` と置き換えられる
global a = a + 1 # @plus2minus マクロによって `global a = a - 1` と書き換えられる
end
julia> a # wao !
0
最後に,@capture
と postwalk
を組み合わせて @generator
がネストした for
ループを扱えるようにしてみましょう:
julia> macro generator(ex)
return postwalk(ex) do x
@capture(x, for v_ in itr_ body_ end) || return x
return :(($(body) for $(v) in $(itr)))
end |> esc
end;
julia> g = @generator for i = 1:3
for j in i:3
j
end
end;
julia> collect.(g)
3-element Array{Array{Int64,1},1}:
[1, 2, 3]
[2, 3]
[3]
Julia の expression をいじるときにとても便利なパッケージなのでぜひ試してみてください.
続く
実は,上で紹介した形のメタプログラミングは,Julia で可能な2種類のメタプログラミングの一方に過ぎません.
もう1つのメタプログラミングは,"Staged programming" と呼ばれる,実行プロセス 2. の段階のコンパイル前のプログラムを書き換えるプログラミングです.
次の記事ではその概説と,簡単な応用例として,TypeCommentator.jl というパッケージを紹介しようと思います :)