-module(generators). -author([{name,"Fred T-H"},{email, "mononcqc@gmail.com"}]). -description("An example of generators implemented in erlang, allowing to generate the equivalent of lists with constant memory."). -vsn(0.0). -export([t_fib/1, y_fib/1, sum/1, fold/3, test/2, batch_test/3]). % macros to make the creation of generators a tad more user-friendly. -define(yield(X), receive {Pid, next} -> Pid ! {self(), X} end). -define(last_yield(X), receive {Pid, next} -> Pid ! {self(), X, done} end). %-compile(export_all). %% Tail-recursive fibonacci function. t_fib(1) -> [1]; t_fib(2) -> [1,1]; t_fib(L) -> t_fib(3,L,[1,1]). t_fib(L,L,[N1,N2|_]=F) -> lists:reverse([N1+N2|F]); t_fib(C, L, [N1,N2|_]=F) -> t_fib(C+1,L,[N1+N2|F]). %% Generator-like tail-recursive fibonacci function. y_fib(L) -> y_fib(1,L,1,0). y_fib(L,L,N1,N2) -> ?last_yield(N1+N2); y_fib(C, L, N1,N2) -> N = N1+N2, ?yield(N), y_fib(C+1,L,N2,N). %% what the lists:sum version for generators could look like sum({M,Gen,Args}) -> Pid = spawn(M, Gen, Args), sum(Pid,0). sum(Pid,S) -> Pid ! {self(), next}, receive {Pid, N} -> sum(Pid, S+N); {Pid, N, done} -> S+N end. %% ... and lists:foldl/3 (no foldr possible with generators). fold(F, Acc,{M,Gen,Args}) when is_function(F,2) -> Pid = spawn(M,Gen,Args), fold(F, Acc, Pid); fold(F, Acc, Pid) -> Pid ! {self(), next}, receive {Pid, N} -> fold(F, F(N,Acc), Pid); {Pid, N, done} -> F(N,Acc) end. %% Comparing execution times of lists vs generators test(fold,N) -> erlang:statistics(wall_clock), F = fun(X, Acc) -> if X rem 2 == 0 -> Acc+1; true -> Acc end end, ?MODULE:fold(F, 0, {?MODULE, y_fib, [N]}), io:format("generator ok~n"), {_, T1} = erlang:statistics(wall_clock), lists:foldl(F, 0, t_fib(N)), io:format("list ok~n"), {_, T2} = erlang:statistics(wall_clock), if T1>0 -> {T1,T2, T2/T1}; T2 == T1, T1 == 0 -> {T1,T2,1}; true -> {T1,T2, '?'} end; test(sum, N) -> erlang:statistics(wall_clock), ?MODULE:sum({?MODULE, y_fib, [N]}), io:format("generator ok~n"), {_, T1} = erlang:statistics(wall_clock), lists:sum(t_fib(N)), io:format("list ok~n"), {_, T2} = erlang:statistics(wall_clock), if T1>0 -> {T1,T2, T2/T1}; T2 == T1, T1 == 0 -> {T1,T2,1}; true -> {T1,T2, '?'} end. %% Testing lists vs generators many times. batch_test(Type, N, Lim) -> batch_test(Type, N, 0, Lim, 0). batch_test(_Type,_N,Lim,Lim,Acc) -> Acc/Lim; batch_test(Type,N,Ct,Lim,Acc) -> {_,_,X} = test(Type,N), batch_test(Type,N,Ct+1,Lim,Acc+X).