No orz No Life

shinhさんのコメント。このサイトに反応があるのは初めてかもしれないので動揺しています(アクセス解析していないので、他にあったらごめんなさい)。読んでくれてありがとうございます。

前々回のエントリでfact/1やsum/3を作ったとき、引数を1つ多くした(Accumlator)下請け関数を作ったのはご指摘の通り末尾再帰の最適化をするためです。が、本当にかかってるのかしら？というか、いちいちそんなことをしなくても実はうまいこといってたりしないのかしら？という疑問が出てきたので、手元の環境で実験してみました。

最適化が発生していることをどうやって確かめればいいのかと考えてみたのですが、例外吐いてスタックトレースを見るのが手っとり早いかなと思いました。末尾再帰が最適化でジャンプに置き換わっていれば、スタックトレースには再帰呼び出しの痕跡が見えないはずです。

call(F) ->
    try 
	erlang:apply(?MODULE, F, [5]) %% F(5)を呼出す
    catch 
	Class:Reason ->    
	    io:format("~p:~p ~p~n", [Class, Reason, erlang:get_stacktrace()])
    end.

こんな感じで例外をキャッチするようにして、一番深いところで

show_backtrace() ->	    
    1 = 0. %% badmatch

みたいなのを呼ぶようにすればスタックトレースを見ることができるかなと思い、早速試してみたのですが、あまり芳しい結果にはなりませんでした。

fact_tail(N) ->
    fact_tail(N, 1).
fact_tail(N, Result) when N =:= 0 orelse N =:= 1 ->
    show_backtrace(),
    Result;
fact_tail(N, Result) when N > 0 ->
    fact_tail(N - 1, Result * N).
fact_notail(N) when N =:= 0 orelse N =:= 1 ->
    show_backtrace(),
    1;
fact_notail(N) when N > 0 ->
    N * fact_notail(N - 1).

末尾再帰版とそうでない版を準備して...

2> tailrecursion:call(fact_tail).
error:{badmatch,0} [{tailrecursion,show_backtrace,0},
                    {tailrecursion,fact_tail,2},
                    {tailrecursion,call,1},
                    {erl_eval,do_apply,5},
                    {shell,exprs,6},
                    {shell,eval_exprs,6},
                    {shell,eval_loop,3}]
ok
3> tailrecursion:call(fact_notail).
error:{badmatch,0} [{tailrecursion,show_backtrace,0},
                    {tailrecursion,fact_notail,1},
                    {tailrecursion,fact_notail,1},
                    {tailrecursion,call,1},
                    {erl_eval,do_apply,5},
                    {shell,exprs,6},
                    {shell,eval_exprs,6},
                    {shell,eval_loop,3}]
ok

スタックトレースは、{Module, Function, Arity(またはArg)}のリストが帰ってくるんですが、非末尾再帰版見ても2つしか積まれていないように見えます。いろんな関数作って試してみたのですが、どうも同一のM:F/Aは集約されてしまっているように見えます...

ドキュメントをいろいろ調べたり試したりしたところ、erlang:process_display(pid(), backtrace) というのを使うとわりとよい結果になることが分かりました。

show_backtrace/0 を下記のように置き換えて...

show_backtrace() ->	    
    io:format("~p~n", [erlang:process_display(self(), backtrace)]).

呼出してみたところ下記のような結果になりました。

8> tailrecursion:call(fact_tail).
Program counter: 0x01201380 (shell:eval_loop/3 + 44)
CP: 0x00000000 (invalid)

0x00e114d4 Return addr 0x015c2edc (tailrecursion:fact_tail/2 + 52)

0x00e114d8 Return addr 0x015c2db4 (tailrecursion:call/1 + 60)
y(0)     120

0x00e114e0 Return addr 0x01222b60 (erl_eval:do_apply/5 + 1268)
y(0)     []
y(1)     Catch 0x015c2dc4 (tailrecursion:call/1 + 76)

(中略)

0x00e11540 Return addr 0x00a51b64 (<terminate process normally>)
y(0)     8204
y(1)     <0.25.0>
true
120
9> tailrecursion:call(fact_notail).
Program counter: 0x01201380 (shell:eval_loop/3 + 44)
CP: 0x00000000 (invalid)

0x00e08874 Return addr 0x015c2f70 (tailrecursion:fact_notail/1 + 44)

0x00e08878 Return addr 0x015c2fc0 (tailrecursion:fact_notail/1 + 124)

0x00e0887c Return addr 0x015c2fc0 (tailrecursion:fact_notail/1 + 124)
y(0)     2

0x00e08884 Return addr 0x015c2fc0 (tailrecursion:fact_notail/1 + 124)
y(0)     3

0x00e0888c Return addr 0x015c2fc0 (tailrecursion:fact_notail/1 + 124)
y(0)     4

0x00e08894 Return addr 0x015c2db4 (tailrecursion:call/1 + 60)
y(0)     5

0x00e0889c Return addr 0x01222b60 (erl_eval:do_apply/5 + 1268)
y(0)     []
y(1)     Catch 0x015c2dc4 (tailrecursion:call/1 + 76)

(中略)

0x00e088fc Return addr 0x00a51b64 (<terminate process normally>)
y(0)     8204
y(1)     <0.25.0>
true
120

確かにfact_notailの方は呼出された回数分スタックに積まれているようです。

いろいろ試してみたところ、再帰でなくても末尾呼出しであればジャンプに置き換わっているようで、例えば以下のようなコードでahya/0を呼出すと、スタックトレースにはahya6しか出てこない状態です。

ahya() ->
    ahya1().
ahya1() ->
    ahya2().
ahya2() ->
    ahya3().    
ahya3() ->
    ahya4().
ahya4() ->
    ahya5().
ahya5() ->    
    ahya6().
ahya6() ->
    show_backtrace(),
    0.

そんなもんなのかなあと思って「プログラミングErlang」を読みなおしてみたら、 p364(第1版)に「Erlangでは末尾呼び出し最適化を行っている」と明記されていました。その後も、檜山さんの日記で、末尾呼出しのもっと興味深い例を見つけることができました。