引っ越しました。

思うところがあり はてなダイヤリーに移行しました。

このblogを追いかけている方がどのくらいいらっしゃるのか分かりませんが、ご迷惑をおかけいたします。

地震

妻、妻の実家、犬たち、私も無事です。社員もいろいろ連絡とりあっています。
今日は会社から帰れそうにないですが。

Erlangとgenerator

前回の続きです。ErlangでPythonのgeneratorみたいなのが使えるとどうなんだろうと思い実験してみました。といっても、ジェネレータの本来の動きを模倣するのは大変そうなので、プロセスを分けてメッセージのやりとりをしているだけです。

-module(generator).
-export([yield/2, next/1, send/2, create/3, create/1]).
-export([all/1, foreach/2]).
-export([xrange/3, xrange/4]).

wait(Pid) ->			    
    receive
	{Pid, next} ->
	    none;
	{Pid, send, Args} ->
	    Args
%% 	Any ->
%% 	    io:format("yield: unexpected message: ~p~n", [Any]),
%% 	    none
    end.
    
yield(Pid, Value) ->
    Pid ! {self(), yield, Value},
    wait(Pid).

next(Iterator) ->
    Iterator ! {self(), next},
    next_loop(Iterator).
next_loop(Iterator) ->
    receive
	{Iterator, yield, Value} ->
	    Value;
	{'DOWN', _Ref, process, Iterator, _Reason} ->
	    eoi
%% 	Any ->
%% 	    io:format("next: unexpected message: ~p~n", [Any]),
%% 	    next_loop(Iterator)
    end.

send(Iterator, Args) ->
    Iterator ! {self(), send, Args},
    next_loop(Iterator).

all(Iterator) ->
    all(Iterator, []).
all(Iterator, Result) ->
    case next(Iterator) of 
	eoi ->
	    lists:reverse(Result);
	Other ->
	    all(Iterator, [Other | Result])
    end.

foreach(Fun, Iterator) ->    
    case next(Iterator) of
	eoi ->
	    ok;
	Other ->
	    Fun(Other),
	    foreach(Fun, Iterator)
    end.

create(M,F,A) ->
    Self = self(),
    Pid = spawn(fun() -> wait(Self), apply(M, F, [Self] ++ A) end),
    erlang:monitor(process, Pid),
    Pid.

create(Fun) ->  
    Self = self(),
    Pid = spawn(fun() -> wait(Self), Fun(Self) end),
    erlang:monitor(process, Pid),
    Pid.


xrange(Pid, From, To) ->
    xrange(Pid, From, To, 1).
xrange(Pid, From, To, Step) when From + Step > To ->
    yield(Pid, From),
    yield(Pid, eoi);
xrange(Pid, From, To, Step) when From =< To ->
    yield(Pid, From),
    xrange(Pid, From + Step, To, Step).

早速試してみましょう...

-module(generator_test).
-compile(export_all).

gen6(Caller) ->
    case generator:yield(Caller, "hoge") of
	none ->
	    generator:yield(Caller, "fuga");
	Any ->
	    generator:yield(Caller, Any ++ "fuga")
    end.

g6() ->
    Pid = generator:create(?MODULE, gen6, []),
    io:format("~p~n", [generator:next(Pid)]),
    io:format("~p~n", [generator:send(Pid, "piyo")]).

(例題は Python のジェネレータ (1) - 動作を試す から拝借しました。)

22> generator_test:g6().
"hoge"
"piyofuga"
ok

無事に動いているようです。同様に、お気楽 Python プログラミング入門 第 4 回 正規表現とジェネレータからも例題を拝借して...

gen_perm(Caller, Nums) ->
    gen_perm(Caller, Nums, 0).
gen_perm(Caller, Nums, N) ->    
    case length(Nums) of
	N ->
	    generator:yield(Caller, []);
	_Otherwise ->
	    Pid = generator:create(?MODULE, gen_perm, [Nums, N+1]),
	    generator:foreach(fun(X) ->
			    lists:foreach(fun(Y) -> 
						  case lists:member(Y, X) of
						      true ->
							  ok;
						      false ->
							  generator:yield(Caller, X ++ [Y])
						  end end, Nums)
						  end, Pid)
    end.

perm() ->
    Pid = generator:create(?MODULE, gen_perm, [[1,2,3]]),
    generator:all(Pid).

見た目はかなり奇妙ですが、元のコードをなるべく忠実に再現したつもりです...。早速動かしてみましょう。

23> generator_test:perm().
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

ふむふむ。期待通りですね。なお、このコードではジェネレータの内部でジェネレータを生成しているので、冒頭のコードでコメントアウト(余計なメッセージを破棄)している部分を生かしてしまうとうまく動きません。当たり前のことなんですが気付くのに若干時間がかかってしまいました。

もっとも順列を得るのであればList comprehensionの方が数倍楽ですね...

24> [[X,Y,Z] || X <- [1,2,3], Y <- [1,2,3], Z <- [1,2,3], X =/= Y, Y =/= Z, X =/= Z].
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

それはともかく、肝心のgenerator:createがいまひとついけてないです。いちいちM/F/Aを指定しなきゃいけなかったり、暗黙のうちにPidを第一引数として付加していたり、fun() でも動くけどだいたい再帰前提で書かなきゃいけないので、Y-combinatorみたいなのを使わないといけないし...

なんとなく、Erlangのプロセスの柔軟さを制限しているだけのような気もしてきました。もうちょっとうまく使う手だてが思いつけばいいのですが...

Erlangとxrange

fizzbuzz作るときはまず1～100までのリストを作るのがLisp流なんだ、と言われると(誰に言われたわけでもないですが、そういう記述を本で読んだ記憶が若干)、なんだかとても抵抗を覚えます。1～100までのリストを確保するための領域と問題解決の間に何の関係があるんでしょう、などとひねくれたことを考えてしまうからです。そこまでひねくれなくても、1～10000だったらどうなる、100億だったら？と、いろいろ考えてしまいます(すぐに「億」と言いだすところは小学生並)。先日も、lists:seqを使うのに抵抗があるなあと書いていますね。

Pythonにはxrangeというものがあって、それを使うと実際にリストを生成することなく数列を作りだすことができます。こちらを見ると、どうもPython3ではxrangeはrangeと統合されたようですが。

"erlang xrange" で検索してみたところ、MLのスレッドを発見しました。このスレッドで紹介されているstreams.erlがなかなか面白かったです。

サンプルにあるように、

> streams:first(10, streams:primes())

などとすると、素数の最初の10コを得ることができます。同じように、integers_starting_from/1 というやつは、引数で指定した整数から1ずつ加算した整数を無限に返す関数となっています。順を追って見てみましょう。

13> streams:integers_starting_from(2).
[2|#Fun<streams.2.60508764>]

最初の要素と、その次を返す関数のリストになっています。

14> F = streams:integers_starting_from(2).
[2|#Fun<streams.2.60508764>]
15> streams:head(F).
2
16> streams:tail(F).
[3|#Fun<streams.2.60508764>]

headすると先頭の要素を返し、tailすると「次の要素、次の次の要素を得る関数」を得ることができるので、これを繰り返し適用してゆくと、対象の関数は無限再帰のように書いておいて、呼出し側は必要な分だけ取得できるという寸法です。必要な分だけ取得するために、firstといった関数も用意されています。

17> streams:head(streams:tail(F)).
3
18> streams:head(streams:tail(streams:tail(F))).
4
19> streams:first(10, F).
[2,3,4,5,6,7,8,9,10,11]

無限再帰ぽく書くために、cons_streamというマクロを作ってそれを呼ぶようにしているようです。

さて、streams.erlにはmapやfilterも定義されていますので、実現方法を応用することでfor i in xrange(1,10):... くらいのことはできそうです。

foreach(_F, []) ->
    ok;
foreach(F, S) ->
    F(head(S)),
    foreach(F,tail(S)).
xrange(From, To, Step) when From + Step > To ->
    ?cons_stream(From, []);
xrange(From, To, Step) when From =< To ->
    ?cons_stream(From, xrange(From+Step, To, Step)).
xrange(From, To) ->
    xrange(From, To, 1).

なんてのを用意して...

17> streams:foreach(fun(X) -> io:format("~p * 2 = ~p~n", [X, X*2]) end, streams:xrange(1,20,3)).
1 * 2 = 2
4 * 2 = 8
7 * 2 = 14
10 * 2 = 20
13 * 2 = 26
16 * 2 = 32
19 * 2 = 38
ok

ふむふむ。ちゃんと動いているようです(Stepをマイナスにできない等いけてないところがありますが)。lists:seq/3と比べて著しく効率がよいとも思えないのですが、なかなか面白いです。

なお、やっぱりリストを得たいとなったら、もともと入っているstreams:all/1を使うことができます。

18> streams:all(streams:xrange(1,20,3)).
[1,4,7,10,13,16,19]

Erlangと末尾再帰

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では末尾呼び出し最適化を行っている」と明記されていました。その後も、檜山さんの日記で、末尾呼出しのもっと興味深い例を見つけることができました。