[elixir] マクロを使ってloop/recurを実装してみる
Elixir Advent Calendar 2014 7日目の記事。
前日は@keithseahusさんの 去年のやつをv1.0仕様で書き直します だった。
loop/recurとは何?
最近からelixirを始めた人にはピンとこないかもしれないが、elixir-0.5あたりでサポートされていた、無名関数を使わずにループを行う構文だ。clojureにインスパイアされたと言われていた。
その後、問題があったため、elixir-0.6あたりでdeprecatedとなり、現在は存在しない。
オリジナルのloop/recurの具体的な使いかたは、
loop initial-args do case1 -> do_1 case2 -> do_2 ... casen -> do_n recur next-args end
といったもので、例えば、
loop 10 do 0 -> 1 1 -> 1 x -> recur(x-1) + recur(x-2) end
のように使う*1。caseと非常に似ているが、SpecialFormだったため、loopの変数の数(アリティ)は、任意の個数が可能であった。
ここで、このなくなってしまったloop/recurのサブセットを復活させてみる。マクロで実装する都合上、loopの引数は１つだけ*2。それ以外は忠実に再現してみる事を目標にする。
方針
一般に、マクロを作る場合は、「どのように書きたいか」と、「どのように展開してほしいか」を考える事から始める。例として、フィボナッチ関数の定義をどうやって展開していくかを考える道筋を示しながら、検討していこう。
loop 10 do 0 -> 1 1 -> 1 x -> recur(x-1) + recur(x-2) end
これをどのように展開してほしいか。まずは無名関数とその呼び出しにしてほしいので、こんな感じか。
fn(x) -> case x do 0 -> 1 1 -> 1 x -> recur(x - 1) + recur(x - 2) end end.(10)
しかし、recur/1をどうするか。無名関数を定義した後で、その関数を引数にして呼び出せば、再帰できるので、そのポイントまでを書くと、
f = fn(y, x) -> case x do 0 -> 1 1 -> 1 x -> recur(x - 1) + recur(x - 2) end end f.(f, 10)
となる。これで無名関数の中でy.という名前で自分自身を参照できるようになった。一方、recurは名前付きの関数だが、これを渡された無名関数を使うようにして、ついでに、仮引数をyからrecurにしてみると*3、
recur = fn(recur, x) -> case x do 0 -> 1 1 -> 1 x -> recur.(recur, x - 1) + recur.(recur, x - 2) end end recur.(recur, 10)
できた。さて、これが実行できるかためしてみる。
iex(3)> recur = fn(recur, x) ->
...(3)> case x do
...(3)> 0 -> 1
...(3)> 1 -> 1
...(3)> x -> recur.(recur, x - 1) + recur.(recur, x - 2)
...(3)> end
...(3)> end
#Function<12.90072148/2 in :erl_eval.expr/5>
iex(4)> recur.(recur, 10)
89うまく動いている感じなので、変換の内容をまとめると、
defmacro loop(a, block)は、以下をする:
- blockについては、内部を参照(コードウォーク)してrecur(x) をrecur.(recur, x)に変換する。
- 変換後のブロックmblockと初期値aを使い以下のようにする。
recur = fn(recur, x) -> case(x, mblock) end
recur.(recur, a)
こんな感じ。elixirのASTは、
{ 関数, META, ARGS }
{ 変数, META, CONTEXT }
となっていて、今回はrecurという関数をrecurという変数に変換することになる。また、変数に格納された無名関数を呼び出す関数は:"."で、
{{:".", META, [{変数, META, CONTEXT}]}, META, 引数}
となる。今回の変数は関数の引数なのでCONTEXTはnilとなる。
マクロの実際
変換そのものはコードウォークが必要だが、今回程度の変換は、手で書くことができる。関数fの戻値が{:skip, r}なら、それ以上の解析はせず、rを返し、{:done, ret}なら、retをさらに{op, meta, arg}に分解し、opとargをそれぞれ解析するというのが骨子。
def traverse(a, f) do {ret, r} = f.(a) case ret do :skip -> r :done -> cond do is_tuple(r) -> case r do {op,meta,arg} -> {traverse(op, f), meta, traverse(arg, f)} r -> List.to_tuple(traverse(Tuple.to_list(r), f)) end is_list(r) -> :lists.map(fn(x) -> traverse(x, f) end, r) true -> r end end end
変換は、このtraverse/2を使って
mb = traverse(block, fn(x) -> case x do {:recur, x, args} when is_atom(args) -> {:done, {:mrecur, x, nil}} {:loop, _meta, args} when is_list(args) -> {:skip, x} {:recur, meta, args} when is_list(args) -> {:done, {{:".", meta, [{:recur, meta, nil}]}, meta, [{:recur, meta, nil}|args]} } _ -> {:done, x} end end)
とすっきり記述できる。また、関数呼び出しは、
m = {:fn, [], [{:"->", [], [[{:recur, [], nil}, {:x, [], nil}], {:case, [], [{:x, [], nil}, mb]}]}]}
のように書ける。ここまで準備すると、recurの呼び出し部分の変換は、
quote do recur = unquote(m) recur.(recur, unquote(p)) end
となる。全体をまとめると、
defmodule MyMacro do @doc """ (block, {:mrecur,_, args}, {{:.,0,[{:f, 0, :quoted}]}) """ def traverse(a, f) do {ret, r} = f.(a) case ret do :skip -> r :done -> cond do is_tuple(r) -> case r do {op,line,arg} -> {traverse(op, f), line, traverse(arg, f)} r -> List.to_tuple(traverse(Tuple.to_list(r), f)) end is_list(r) -> Enum.map(r, &(traverse(&1, f))) true -> r end end end defmacro loop(p, block) do mb = traverse(block, fn(x) -> case x do {:recur, x, args} when is_atom(args) -> {:done, {:recur, x, nil}} {:loop, line, args} when is_list(args) -> {:skip, x} {:recur, line, args} when is_list(args) -> {:done, {{:".", line, [{:recur, line, nil}]}, line, [{:recur, line, nil}|args]} } _ -> {:done, x} end end) m = {:fn, [], [{:"->", [], [[{:recur, [], nil}, {:x, [], nil}], {:case, [], [{:x, [], nil}, mb]}]}]} quote do recur = unquote(m) recur.(recur, unquote(p)) end end end
使ってみる
上記のコードをMyMacro.exとでもいうファイルに保存して、importしてiexから使ってみる。
iex(11)> c("MyMacro.ex") [MyMacro] iex(12)> import MyMacro nil iex(13)> loop 10 do ...(13)> 0 -> 1 ...(13)> 1 -> 1 ...(13)> x -> recur(x-1) + recur(x-2) ...(13)> end 89
現在のelixirでも、ちょっとしたループを記述するのにはやっぱり便利である。
アッカーマン関数を定義してみる
アッカーマン関数とは、
def ack(0, n) -> n + 1 (m, 0) -> ack(m - 1, 1) (m, n) -> ack(m - 1, ack(m, n - 1) end
というもので、原始再帰関数*4ではない関数の一つ。
今回のloop/recurでは、これを定義、実行できる。
iex(12)> ack = fn(m, n) -> ...(12)> loop {m, n} do ...(12)> {0, n} -> n + 1 ...(12)> {m, 0} -> recur({m-1, 1}) ...(12)> {m, n} -> recur({m-1, recur({m, n-1})}) ...(12)> end ...(12)> end #Function<12.90072148/2 in :erl_eval.expr/5> iex(13)> ack.(3, 2) 29 iex(14)> ack.(3, 3) 61 iex(15)> ack.(3, 4) 125
このようにちょっとした再帰関数をアドホックに定義することも便利になる。
明日は@keithseahusさんです。
