I'd certainly love having this functionality in Reia<br><br><div class="gmail_quote">2009/3/19 Frederic T-H <span dir="ltr"><<a href="mailto:mononcqc@gmail.com">mononcqc@gmail.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
First time posting here, I've been reading this mailing lists for a few months now, programming Erlang for a few months too.<br>
<br>
Python and its most functionnal parts is what eventually brought me to Erlang. One feature that I loved in Python and instantly noticed was not available in Erlang was generators. Generators are basically normal functions, except they return an iterator, letting you fetch each result one by one, effectively letting you work with constant memory. An example of the way Python does it:<br>
<br>
def gen(n):<br>
i = 0<br>
while i<n:<br>
yield i<br>
i+=1<br>
return<br>
<br>
x = gen(2)<br>
x.next() # returns 0<br>
x.next() # returns 1<br>
x.next() # throws an exception<br>
<br>
In python, using yield creates a 'next' method, which is automatically called by most functions that can iterate over text, lists, tuples, dictionaries, etc.<br>
<br>
The idea is to not load all the results from a function at once and pass it around, but to send each part individually.<br>
<br>
As an example, say I have a result set consisting of 1000x5kb tuples (whatever they contain) which I want to map a function over. The way Erlang works, you'd need to have a list that is 5000kb in size in memory and manipulate it every single time the mapped function iterates over it.<br>
<br>
The end goal is to attempt to bypass having to evaluate the whole result set at once (heavy) and instead get each element individually (lighter). This is especially good for smaller systems like phones, web tablets (Nokia) or really anything with limited amounts of RAM.<br>
<br>
While possible to implement in Erlang, generators are quite problematic because every list BIF at the moment only operates on complete lists. This means adding generators in Erlang would require one to do something like duplicate the lists module.<br>
<br>
This may not be the first time this whole idea is discussed, but fast googling didn't reveal much so I've let myself write a small naive and simple prototype of what the implementation could be.<br>
<br>
The idea is quite simple: Have a recursive function as a different spawned process waiting to receive {Pid, next} before returning data. I've attached the file demonstrating the implementation, but in case I got it wrong, I also copy/pasted it there: <a href="http://pastebin.com/f31ae9731" target="_blank">http://pastebin.com/f31ae9731</a><br>
<br>
What the implementation does:<br>
<br>
- define tail-recursive fibonacci functions, a normal one and a<br>
generator version<br>
- define mockups for the sum and fold (foldl) functions from the<br>
list module adapted to generators<br>
- short unscientific tests to compare performances.<br>
<br>
What it doesn't do:<br>
<br>
- consider any kind of safety in case there is an error in a generator<br>
- contain anything past what you'd do for a proof of concept.<br>
<br>
<br>
The way it works, a normal tail-recursive way to get all the fibonacci numbers until the nth one could be done the following way:<br>
<br>
t_fib(1) -> [1];<br>
t_fib(2) -> [1,1];<br>
t_fib(L) -> t_fib(3,L,[1,1]).<br>
<br>
t_fib(L,L,[N1,N2|_]=F) -><br>
lists:reverse([N1+N2|F]);<br>
t_fib(C, L, [N1,N2|_]=F) -><br>
t_fib(C+1,L,[N1+N2|F]).<br>
<br>
That's not the prettiest function in the world, but it still does the job. Here's how it would be as a generator (with the macros I have defined in the file):<br>
<br>
y_fib(L) -><br>
y_fib(1, L, 1, 0).<br>
y_fib(L, L, N1 ,N2) -><br>
?last_yield(N1+N2);<br>
y_fib(C, L, N1, N2) -><br>
N = N1+N2,<br>
?yield(N),<br>
y_fib(C+1, L, N2, N).<br>
<br>
The code overhead one gets writing it that way is minimal and denies the need to use a list as an accumulator.<br>
<br>
The generator sum function is written the following way:<br>
<br>
sum({M,Gen,Args}) -><br>
Pid = spawn(M, Gen, Args),<br>
sum(Pid,0).<br>
sum(Pid,S) -><br>
Pid ! {self(), next},<br>
receive<br>
{Pid, N} -> sum(Pid, S+N);<br>
{Pid, N, done} -> S+N<br>
end.<br>
<br>
Called with the custom sum function in the generators module (This could be made better, I agree):<br>
<br>
> generators:sum({generators,y_fib,[100]}). 927372692193078999175<br>
<br>
Now for performance, I've tested it with Erlang R13A. My computer:<br>
AMD phenom 9950 quad-core 2.6ghz processor, 4gb RAM, Windows 7 Beta build 7000 (32 bits).<br>
batch_test/3 will compare both versions with a sequence/list of Fibonacci numbers of length 10000 and 50000, 20 times each, and round the results showing how much faster the generator is (1.0 is equal).<br>
<br>
26> generators:batch_test(sum, 10000, 20).<br>
0.9438942747654998<br>
27> generators:batch_test(sum, 50000, 20).<br>
2.406425935803285<br>
28> generators:batch_test(fold, 10000, 20).<br>
0.6706634763086374<br>
29> generators:batch_test(fold, 50000, 20).<br>
1.3918125332818239<br>
<br>
This seems to show that using a generator scales much better, while becoming faster as the list grows and becomes expansive to generate and carry around.<br>
<br>
The real advantage, though, is the fact that using a function that won't accumulate lots of data (sum, folds, foreach, all, any, nth, etc.) will be done with constant memory. This is especially good for small systems or scaling as a whole.<br>
<br>
The testing I've done is minimal, and while I don't expect the Erlang community to jump on the idea and adopt it, I'm one of these people who'd like to eventually use this in production code. What kind of stuff would you see missing, or likely to cause trouble in the current implementation?<br>
What ways would I have to test this giving better results?<br>
<br>
Any other comments, tips? Thanks in advance! (Have a nice day also.)<br>
<br>-module(generators).<br>
-author([{name,"Fred T-H"},{email, "<a href="mailto:mononcqc@gmail.com">mononcqc@gmail.com</a>"}]).<br>
-description("An example of generators implemented in erlang,<br>
allowing to generate the equivalent of lists with constant memory.").<br>
-vsn(0.0).<br>
-export([t_fib/1, y_fib/1, sum/1, fold/3, test/2, batch_test/3]).<br>
<br>
% macros to make the creation of generators a tad more user-friendly.<br>
-define(yield(X), receive {Pid, next} -> Pid ! {self(), X} end).<br>
-define(last_yield(X), receive {Pid, next} -> Pid ! {self(), X, done} end).<br>
%-compile(export_all).<br>
<br>
%% Tail-recursive fibonacci function.<br>
t_fib(1) -> [1];<br>
t_fib(2) -> [1,1];<br>
t_fib(L) -> t_fib(3,L,[1,1]).<br>
<br>
t_fib(L,L,[N1,N2|_]=F) -><br>
lists:reverse([N1+N2|F]);<br>
t_fib(C, L, [N1,N2|_]=F) -><br>
t_fib(C+1,L,[N1+N2|F]).<br>
<br>
%% Generator-like tail-recursive fibonacci function.<br>
y_fib(L) -><br>
y_fib(1,L,1,0).<br>
<br>
y_fib(L,L,N1,N2) -><br>
?last_yield(N1+N2);<br>
y_fib(C, L, N1,N2) -><br>
N = N1+N2,<br>
?yield(N),<br>
y_fib(C+1,L,N2,N).<br>
<br>
%% what the lists:sum version for generators could look like<br>
sum({M,Gen,Args}) -><br>
Pid = spawn(M, Gen, Args),<br>
sum(Pid,0).<br>
sum(Pid,S) -><br>
Pid ! {self(), next},<br>
receive<br>
{Pid, N} -> sum(Pid, S+N);<br>
{Pid, N, done} -> S+N<br>
end.<br>
<br>
%% ... and lists:foldl/3 (no foldr possible with generators).<br>
fold(F, Acc,{M,Gen,Args}) when is_function(F,2) -><br>
Pid = spawn(M,Gen,Args),<br>
fold(F, Acc, Pid);<br>
fold(F, Acc, Pid) -><br>
Pid ! {self(), next},<br>
receive<br>
{Pid, N} -> fold(F, F(N,Acc), Pid);<br>
{Pid, N, done} -> F(N,Acc)<br>
end.<br>
<br>
%% Comparing execution times of lists vs generators<br>
test(fold,N) -><br>
erlang:statistics(wall_clock),<br>
F = fun(X, Acc) -><br>
if X rem 2 == 0 -> Acc+1;<br>
true -> Acc<br>
end<br>
end,<br>
?MODULE:fold(F, 0, {?MODULE, y_fib, [N]}),<br>
io:format("generator ok~n"),<br>
{_, T1} = erlang:statistics(wall_clock),<br>
lists:foldl(F, 0, t_fib(N)),<br>
io:format("list ok~n"),<br>
{_, T2} = erlang:statistics(wall_clock),<br>
if T1>0 -> {T1,T2, T2/T1};<br>
T2 == T1, T1 == 0 -> {T1,T2,1};<br>
true -> {T1,T2, '?'}<br>
end;<br>
test(sum, N) -><br>
erlang:statistics(wall_clock),<br>
?MODULE:sum({?MODULE, y_fib, [N]}),<br>
io:format("generator ok~n"),<br>
{_, T1} = erlang:statistics(wall_clock),<br>
lists:sum(t_fib(N)),<br>
io:format("list ok~n"),<br>
{_, T2} = erlang:statistics(wall_clock),<br>
if T1>0 -> {T1,T2, T2/T1};<br>
T2 == T1, T1 == 0 -> {T1,T2,1};<br>
true -> {T1,T2, '?'}<br>
end.<br>
<br>
%% Testing lists vs generators many times.<br>
batch_test(Type, N, Lim) -><br>
batch_test(Type, N, 0, Lim, 0).<br>
batch_test(_Type,_N,Lim,Lim,Acc) -><br>
Acc/Lim;<br>
batch_test(Type,N,Ct,Lim,Acc) -><br>
{_,_,X} = test(Type,N),<br>
batch_test(Type,N,Ct+1,Lim,Acc+X).<br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br></blockquote></div><br><br clear="all"><br>-- <br>Tony Arcieri<br><a href="http://medioh.com">medioh.com</a><br>