## SICP Goodness - Stream (I)

Just a little bit of lambda calculus

Do you think Computer Science

equalsbuilding websites and mobile apps?Are you feeling that you are doing

repetitiveandnot so intelligentwork?Are you feeling a bit

sickaboutreading manualsandcopy-pastingcode and keeppoking arounduntil it worksall day long?Do you want to understand the

soulofComputer Science?If yes,

read SICP!!!

Finally, we arrived at one the epic topics in the SICP book, stream.

A brilliant high level explanation about stream, quoted from the book:

We’ve gained a good understanding of assignment as a tool in modeling, as well as an appreciation of the complex problems that assignment raises. It is time to ask whether we could have gone about things in a different way, so as to avoid some of these problems. In this section, we explore an alternative approach to modeling state, based on data structures called streams. As we shall see, streams can mitigate some of the complexity of modeling state.

Let’s step back and review where this complexity comes from. In an attempt to model real-world phenomena, we made some apparently reasonable decisions: We modeled real-world objects with local state by computational objects with local variables. We identified time variation in the real world with time variation in the computer. We implemented the time variation of the states of the model objects in the computer with assignments to the local variables of the model objects.

Is there another approach? Can we avoid identifying time in the computer with time in the modeled world? Must we make the model change with time in order to model phenomena in a changing world? Think about the issue in terms of mathematical functions. We can describe the time-varying behavior of a quantity x as a function of time x(t). If we concentrate on x instant by instant, we think of it as a changing quantity. Yet if we concentrate on the entire time history of values, we do not emphasize change—the function itself does not change.

If time is measured in discrete steps, then we can model a time function as a (possibly infinite) sequence. In this section, we will see how to model change in terms of sequences that represent the time histories of the systems being modeled. To accomplish this, we introduce new data structures called streams. From an abstract point of view, a stream is simply a sequence. However, we will find that the straightforward implementation of streams as lists (as in 2.2.1) 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. This has important implications, both theoretical and practical, because we can build models that avoid the drawbacks inherent in introducing assignment. On the other hand, the stream framework raises difficulties of its own, and the question of which modeling technique leads to more modular and more easily maintained systems remains open.

Let’s dive right in on how to implement stream. (The code for this is surprisingly less than what you might think)

I will take the bottom up approach again, since the book is kind of top down. So we start with the `memo-proc`

procedure.

```
(define (memo-proc proc)
(let ((already-run? false)
(result false))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result)
result))))
```

This is not hard to understand if you understand the environment model.

Basically `memo-proc`

takes in a procedure `proc`

, and returns a new procedure `ret-proc`

. When the `ret-proc`

gets executed for the first time, it runs the original `proc`

and return its result, and it **remembers** the result. The next time `ret-proc`

gets executed, it will return the remembered result directly without executing the original `proc`

again.

Next, let’s look at `delay`

.

```
(define-syntax delay
(syntax-rules ()
((delay exp)
(memo-proc (lambda () exp)))))
```

First thing first, `delay`

is not a procedure. It is kind of a special syntax.

The above code can be translated to the following: if you write `(delay exp)`

in code, before anything starts, it will be automatically replaced by `(memo-proc (lambda () exp))`

. Well, you may ask why can’t `delay`

be a procedure like this:

```
(define (delay exp)
(memo-proc (lambda () exp)))
```

What is the difference here. Good question! The difference being that **when exp gets evaluated**.

Let’s take a look at a simple example:

```
(delay (+ 1 1))
```

If `delay`

is a procedure, `(+ 1 1)`

will first be evaluated to 2 and then passed into the procedure. Well this is against what the name `delay`

means, cause nothing gets delayed.

On the other hand, if `delay`

is a special syntax, `(+ 1 1)`

will not be evaluated first. The evaluation is actually delayed, hence the name `delay`

.

Goes together with `delay`

is `force`

.

```
(define (force delayed-object)
(delayed-object))
```

This is simple, as we see `delay`

returns a procedure. To force a delayed object is just to call it.

Now we have enough to define the constructor of stream.

```
(define-syntax cons-stream
(syntax-rules ()
((cons-stream a b)
(cons a (delay b)))))
```

To create a stream, it is almost the same as cons up a list. The difference is that instead of just `(cons a b)`

, we make a delayed object out of `b`

and cons `a`

with the delayed `b`

. Since we do not want `b`

to be evaluated here, we have to make `cons-stream`

also a special syntax.

The only things left is the car and cdr of stream:

```
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
```

Let’s see some usages of streams in next episode. Stay tuned!

Twitter

Google+

Facebook

Reddit

LinkedIn

StumbleUpon

Email