On #ruby-lang, we talked about SICP yesterday, and that reminded me I didn’t look into this wonderful book for a long time. I had enough time today to open it…

Quickly skipping over the first two chapters that I remembered fairly well (and that are “easy”), I started reading chapter 3 Modularity, Objects, and State. The section on Streams finally made me switch to my always-open Emacs window and port that beautiful Scheme into even better Ruby. :-)

In short, streams can be explained like this:

From an abstract point of view, a stream is simply a sequence. However, we will find that the straightforward implementation of streams as lists doesn’t fully reveal the power of stream processing. As an alternative, we introduce the technique of delayed evaluation, which enables us to represent very large (even infinite) sequences as streams.

Stream processing lets us model systems that have state without ever using assignment or mutable data.

What a great target for an functional installment in Ruby! Should you not be any familiar with streams, I recommend you to read above chapter now, and come back after. Or just read on, if you want to bite into the code.

To make use of Ruby’s object-orientation, I decided to make each
`string-cons`

instances of class `Stream`

. A Stream contains two
objects, `car`

and `cdr`

, whereas `cdr`

is evaluated lazily. In Ruby, we
do this using a block:

```
class Stream
def initialize(car, &cdr)
@car = car
@cdr = cdr
end
def car; @car; end
def cdr; @cdr.call; end
end
```

Now, we can create a simple cons:

```
cons = Stream.new(1) { 2 }
[cons.car, cons.cdr] # => [1, 2]
```

That way of creating new conses is not very beautiful, but everything we get in Ruby (no macros…).

We will also need a few helper methods:

```
class Stream
def self.interval(low, high)
if low > high
nil
else
new(low) { interval low+1, high }
end
end
def filter(&pred)
if pred.call car
Stream.new(car) { cdr.filter &pred }
else
cdr.filter &pred
end
end
def take(n)
stream = self
results = []
n.times {
results << stream.car
stream = stream.cdr
}
results
end
end
```

`Stream.interval(1, 100)`

will return a new stream that will evaluate
in the numbers of 1 to 100.

`Stream#filter`

returns a new stream that only contains elements that
satisfy a given predicate. Lazily of course.

`Stream#take`

finally will evaluate the string `n`

times and return an
Array of the evaluated values.

Now, let’s do an example from SICP,
*calculate the third prime between 10000 and 1000000*.
If this was evaluated eagerly, you still
wouldn’t see the result. Instead, we simply run:

```
def prime?(n)
2.upto(Math.sqrt(n).round) { |i| return false if n % i == 0 }
true
end
Stream.interval(10000, 1000000).filter { |s| prime? s }.take(3).last
# => 10037
```

The answer comes instantly. Why is this? In the end, the stream
behaves just a loop: We loop over all the integers in the range, and,
basically, *trackback* if the numbers aren’t primes. Now, we do that
only three times, because that often the stream will be evaluated.
Therefore, we only test 37 numbers for being prime, not 999000.

Another nice example are fibonacci numbers, where each element—I
hope you knew that already—is the sum of its successors. But first,
we need to *add* two streams:

```
class Stream
def self.fibonacci
new(0) { new(1) { fibonacci.cdr + fibonacci } }
end
def +(other)
Stream.new(self.car + other.car) { self.cdr + other.cdr }
end
end
```

A quick test, it works:

```
Stream.fibonacci.take(10)
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
```

Now, by the way, we also can calculate the
*golden mean*, which is the can be
approximated as the quotient of two successive fibonacci numbers.

```
n = Stream.fibonacci.take(20).last(2)
n[1] / n[0].to_f # => 1.61803405572755
(Math.sqrt(5.0) + 1) / 2.0 # => 1.61803398874989
```

Unfortunately, lazyness with lambdas is not exactly a wonder of speed in Ruby, therefore Streams are, beyond their very interesting properties, not of much use for the usual Ruby programmer. In purely functional languages (e.g. Haskell), where lazy evaluation is a common thing, they are however a very common way of implementing state without actually changing things.

NP: Jetscreamer—Front Porch