This blog has moved here and this post can be found at http://blog.khigia.net/wp-import/erlang/2006/11/25/baby-steps-in-the-erlang-world.html
My projects are all suspended … I have been busy playing with stream examples of chapter 3 of SICP :).
I wrote in Erlang a simple implementation of stream as cons-list. It is not meant to be efficient but easy to understand (and debug):
- a stream is here a tuple {stream, Head, DelayedTail}, where DelayedTail is a 0-arity’s function which return the next stream element tuple;
- a macro implements the delay function used to construct a stream tail:
-define(DELAY(Any), fun() -> Any end).
Note: the head is not delayed, and if we need a delayed head this probably means that we need a lazy-evaluation model, to which I’ll come later. Using abstract functions, head/1 to access current value and tail/1 to force evaluation of next stream state, will enables to hook a memoization process if needed.
Anyway, the stream concatenation and the delay’s macro are enough to build all stream manipulations. Here are some examples:
% map: application of a procedure to all elements of a stream map(Proc, Stream={stream, undefined, undefined}) -> % empty stream: do nothing Stream; map(Proc, Stream) -> % apply Proc to current, and delay apply to all tail elements {stream, Proc(head(Stream)), ?DELAY(map(Proc, tail(Stream)))} % filter elements of stream with respect to some predicate filter(Pred, Stream={stream, undefined, undefined}) -> % empty stream: do nothing Stream; filter(Pred, Stream={stream, _Head, _Tail}) -> Current = head(Stream), case Pred(Current) of true -> {stream, Current, ?DELAY(filter(Pred, tail(Stream)))}; _False -> filter(Pred, tail(Stream)) end. % generalized map: apply proc to multiple streams (traverse streams "in parallel") gmap(Proc, Streams=[First={stream, undefined,undefined}|_Others]) -> % assume all stream have the same length % found one stream empty: end of process First; gmap(Proc, Streams=[First|_Others]) -> % create a list of heads Heads = lists:map(fun(S) -> stream:head(S) end, Streams), % create a generator of the list of tails FTails = fun() -> lists:map(fun(S) -> stream:tail(S) end, Streams) end, % result is the application to heads and delayed mapping to tails {stream, Proc(Heads), ?DELAY(gmap(Proc, FTails()))}.
And now, we have enough to use the streams:
% explicit definition of infinite sequence of integers explicit_integers_from(N) -> {stream, N, ?DELAY(explicit_integers_from(N+1))}. % add values of 2 streams add(S1, S2) -> gmap(fun([X,Y]) -> X + Y end, [S1, S2]). % infinite sequence of Fibonacci numbers fibs() -> {stream, 0, ?DELAY({stream, 1, ?DELAY(add(fibs(), tail(fibs())))}) }.
A bit more usefull: 2 infinite sequences of prime numbers. First one uses the sieve of Eratosthene; second one uses basic definition of prime: number not divisible by any previous primes.
% Sieve of Eratosthene: sieve(Stream) -> Current = head(Stream), {stream, Current, ?DELAY(sieve(filter( fun(N) -> N rem Current /= 0 end, tail(Stream) )))}. sieve_primes() -> sieve(explicit_integers_from(2)). % prime numbers using the factors decomposition property primes() -> {stream, 2, ?DELAY(filter(fun is_prime/1, explicit_integers_from(3)))}. is_prime(N) -> iter_is_prime(N, primes()). iter_is_prime(N, Primes) -> FirstPrime = head(Primes), if FirstPrime * FirstPrime > N -> true; N rem FirstPrime == 0 -> false; true -> iter_is_prime(N, tail(Primes)) end.
And of course there are lot of stream examples in SICP chapter, like the impressive Euler transformation to accelerate convergence of sequence.
In this thread http://erlang.mirror.su.se/ml-archive/erlang-questions/200010/msg00165.html you can find a real stream implementation by Richard Carlsson, as well as interesting discussions about stream and lazy evaluation. Also check this other thread http://www.erlang.org/ml-archive/erlang-questions/200602/msg00003.html if you’re interested by memoization in Erlang. I may test it later to learn the magic of Erlang parse_transform ;), but I think an easy possible way to implement memoization for my stream is to model a stream as a tuple of 4 elements, adding a dictionary of memoized values as last element (my current implementation uses the process dictionary to store memoized values).
Actually I’m not sure if this post is too short to be a tutorial or too long to be a interesting post! Anyway, it exists now 😉 … mostly because a friend gave me motivation to do so, thanks!