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!

About these ads