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 ⟹ AST¹
AST を "Lowering": AST ⟹ Lowered form (IR)²
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. の段階のプログラム(AST¹と呼ぶ，(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 というパッケージを紹介しようと思います :)

"Abstract Syntax Tree" (抽象構文木) の略．素の Julia プログラムを扱いやすい Tree-like なデータ構造に変換したもの． ↩
"Lowering" とは, 型推論などの解析がしやすいように, AST をさらに変換し, SSA形式("Static Single Assignment form")と呼ばれる IR ("Intermediate Representation", 中間表現)に変形することを指します．詳しくは次の記事で説明します． ↩

Julia のメタプログラミング 1 -- Parse time hack

Julia のメタプログラミング 1 -- Parse time hack

メタプログラミングとは

Julia の実行プロセスとメタプログラミング

Parse time hack example: @generator マクロ

More hacks !: MacroTools.jl

続く

Parse time hack example: `@generator` マクロ

More hacks !: `MacroTools.jl`