無名関数での再帰処理

elixir

elixirでの無名関数はfnスペシャルフォームで定義できるが、無名関数のため、自分自身を呼び出すような処理は記述できない。
たとえば、フィボナッチ数を求める関数は、

fn (0) -> 0
    (1) -> 1
    (n) -> self(n-1) + self(n - 2)

のように書くことは出来ない。
Lispでは、そういうときのためにlabelsというスペシャルフォームがあり、

(setf x (labels ((self (n)
                (cond
                  ((eq n 0) 0)
                  ((eq n 1) 1)
                  (t (+ (self (- n 1)) (self (- n 2)))))))
                ))
(funcall x 10)
55

と書ける。elixirでも同じように書きたいが、selfはpidを返す関数なのでmeという疑似変数を導入して

 > a = fn (0) -> 0
             (1) -> 1
             (n) -> me(n-1) + me(n-2) 
          end
>a.(10)
>  55

こんなふうに書けたら便利な気がする。

無名関数から自分自身を呼び出す

とりあえず、無名関数を変数に保存しておいて使ってみると、

    a = fn(0) -> 0
              (1) -> 1
              (n) -> a.(n-1) + a.(n-2) end

ではfnの評価時にaが定義されていないので駄目。なので、仮引数としてaを
渡してやれば良い。

   b = fn(a) ->
             fn(0) -> 0
                (1) -> 1
                (n) -> a.(n-1) + a.(n-2) end end

これを評価すると、無名関数を返す無名関数関数が出来上がる。
b.(b)を評価すると、

> c = b.(b)
#Function<6.80484245 in :erl_eval.expr/5>
> c.(3)
** (ArithmeticError) bad argument in arithmetic expression
    :erlang.+(#Function<6.80484245 in :erl_eval.expr/5>, #Function<6.80484245 in :erl_eval.expr/5>)

おお、エラーだ。よく見ると、上のfnではaはbつまり、関数を引数にとることになっているが、上記コードではn-1つまり2を渡している。実際、b.(b)がcつまり、求める無名関数の筈なので、fn中のaをa.(a)に書き換えてみる。

   b = fn(a) ->
             fn(0) -> 0
                (1) -> 1
                (n) -> a.(a).(n-1) + a.(a).(n-2) end end

これを同様にして評価していくと、

> c = b.(b)
#Function<6.80484245 in :erl_eval.expr/5>
> c.(3)
2

うまくいった。つまり、アウトラインはこんな感じ。

  defmacro afn(function) do
     cfunc = translate(:me, function) ## function中のmeをme.(me).に変更
     quote do
        me = fn(me) -> unquote(function) end
        me.(me)
     end
  end

afnというマクロ名はOn Lispのalambdaからとった。

マクロとしてまとめる

translate/2はelixirのASTをトラバースしながらパターンを置き換えることになる。
ASTは以下のリテラルから成り立つ。

  def ast_traverse(a, _f) when is_atom(a) or is_number(a) or is_binary(a) do
    a
  end
  def ast_traverse({a, b}, _f) do
    {a, b}
  end
  def ast_traverse(a, _f) when is_list(a) do
    a
  end

次に、関数呼び出しを含むスペシャルフォームは以下の種類がある。

      {a, b, c} when :"->" == a and is_list(c) -> 節
      {a, b, c} when is_atom(a) and is_list(c) ->  関数実行
      {a, b, c} when is_tuple(a) and size(a) == 3 and is_list(c) -> 関数戻り値を関数として実行
      {a, b, c} when is_atom(a) and is_atom(c) -> 変数

それぞれに対応してパターンを記述すると、

  def ast_traverse({a, b, c}, f) do
    {a, b, c} = f.({a, b, c})
    case {a, b, c} do
      {a, b, c} when :"->" == a and is_list(c) ->
        {a, b, Enum.map(c, fn(x) ->
                               {args, meta, node} = x
                               {Enum.map(args, &(ast_traverse(&1, f))),
                                       meta, ast_traverse(node, f)}
                           end)}
      {a, b, c} when is_atom(a) and is_list(c) ->
        {ast_traverse(a, f), b, Enum.map(c, &(ast_traverse(&1, f)))}
      {a, b, c} when is_tuple(a) and size(a) == 3 and is_list(c) ->
        {ast_traverse(a, f), b, Enum.map(c, &(ast_traverse(&1, f)))}
      {a, b, c} when is_atom(a) and is_atom(c) ->
        {ast_traverse(a, f), b, c}
    end
  end

これを使ってtranslate/3は以下のように書ける。

  def translate(tree, a, module // nil) do
    ast_traverse(tree, fn({^a, b, c}) when is_list(c) ->
                           {{:., b, [{{:., b, [{a, b, module}]},
                                        b,
                                        [{a, b, module}]}]},
                              b, c}
                         (x) -> x
                       end)
  end

これでlispのlabelsもどきを実施するdo_label/2とafn/1をやっと定義できるようになった。

  def do_label({n, line, module} = nvar, clouse) do
    {n, line, module} = nvar
    c = translate(clouse, n, module)
    c2 = {:fn, line, [{:"->", line, [{[nvar], line, c}]}]}
    r = quote  do
      me = unquote(c2)
      me.(me)
    end
    r
  end
  defmacro afn(clouse) do
    r = do_label({:me, [], nil}, clouse)
    r
  end

これをモジュールMMとかに入れておいて、コンパイルして使ってみる。

iex(106)> c("mm.ex")
[MMM, MM]
iex(107)> require MM;
iex(108)> r = MM.afn(fn (0) -> 0
...(108)>           (1) -> 1
...(108)>           (n) -> me(n-1) + me(n-2) end)
#Function<6.80484245 in :erl_eval.expr/5>
iex(109)> r.(10)
55
iex(110)>

無名関数の内部でmeという関数名で自分自身を参照できるようになった。