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]