of the bag.

He introduced the idea of assignment.

Assignment and state.

And as we started to see, the implications of introducing

assignment and state into the language are absolutely

frightening.

First of all, the substitution model of

evaluation breaks down.

And we have to use this much more complicated environment

model and this very mechanistic thing with

diagrams, even to say what statements in the programming

language mean.

And that's not a mere technical point.

See, it's not that we had this particular substitution model

and, well, it doesn't quite work, so we have to do

something else.

It's that nothing like the substitution model can work.

Because suddenly, a variable is not just something that

stands for a value.

A variable now has to somehow specify a place

that holds a value.

And the value that's in that place can change.

Or for instance, an expression like f of x might have a side

effect in it.

So if we say f of x and it has some value, and then later we

say f of x again, we might get a different value

depending on the order.

So suddenly, we have to think not only about values but

about time.

And then things like pairs are no longer just their CARs and

their CDRs.

A pair now is not quite its CAR and its CDR. It's rather

its identity.

So a pair has identity.

It's an object.

And two pairs that have the same CAR and CDR might be the

same or different, because suddenly we have to worry

about sharing.

So all of these things enter as soon as we introduce

assignment.

See, this is a really far cry from where we started with

substitution.

It's a technically harder way of looking at things because

we have to think more mechanistically about our

programming language.

We can't just think about it as mathematics.

It's philosophically harder, because suddenly there are all

these funny issues about what does it mean that something

changes or that two things are the same.

And also, it's programming harder, because as Gerry

showed last time, there are all these bugs having to do

with bad sequencing and aliasing that just don't exist

in a language where we don't worry about objects.

Well, how'd we get into this mess?

Remember what we did, the reason we got into this is

because we were looking to build modular systems. We

wanted to build systems that fall apart into chunks that

seem natural.

So for instance, we want to take a random number generator

and package up the state of that random number generator

inside of it so that we can separate the idea of picking

random numbers from the general Monte Carlo strategy

of estimating something and separate that from the

particular way that you work with random numbers in that

formula developed by Cesaro for pi.

And similarly, when we go off and construct some models of

things, if we go off and model a system that we see in the

real world, we'd like our program to break into natural

pieces, pieces that mirror the parts of the system that we

see in the real world.

So for example, if we look at a digital circuit, we say,

gee, there's a circuit and it has a piece and

it has another piece.

And these different pieces sort of have identity.

They have state.

And the state sits on these wires.

And we think of this piece as an object that's different

from that as an object.

And when we watch the system change, we think about a

signal coming in here and changing a state that might be

here and going here and interacting with a state that

might be stored there, and so on and so on.

So what we'd like is we'd like to build in the computer

systems that fall into pieces that mirror our view of

reality, of the way that the actual systems we're modeling

seem to fall into pieces.

Well, maybe the reason that building systems like this

seems to introduce such technical complications has

nothing to do with computers.

See, maybe the real reason that we pay such a price to

write programs that mirror our view of reality is that we

have the wrong view of reality.

See, maybe time is just an illusion, and

nothing ever changes.

See, for example, if I take this chalk, and we say, gee,

this is an object and it has a state.

At each moment it has a position and a velocity.

And if we do something, that state can change.

But if you studied any relativity, for instance, you

know that you don't think of the path of that chalk as

something that goes on instant by instant.

It's more insightful to think of that whole chalk's

existence as a path in space-time.

that's all splayed out.

There aren't individual positions and velocities.

There's just its unchanging existence in space-time.

Similarly, if we look at this electrical system, if we

imagine this electrical system is implementing some sort of

signal processing system, the signal processing engineer who

put that thing together doesn't think of it as, well,

at each instance there's a voltage coming in.

And that translates into something.

And that affects the state over here, which changes the

state over here.

Nobody putting together a signal processing system

thinks about it like that.

Instead, you say there's this signal that's

splayed out over time.

And if this is acting as a filter, this whole thing

transforms this whole thing for some sort of other output.

You don't think of it as what's happening instant by

instant as the state of these things.

And somehow you think of this box as a whole thing, not as

little pieces sending messages of state to each other at

particular instants.

Well, today we're going to look at another way to

decompose systems that's more like the signal processing

engineer's view of the world than it is like thinking about

objects that communicate sending messages.

That's called stream processing.

And we're going to start by showing how we can make our

programs more uniform and see a lot more commonality if we

throw out of these programs what you might say is an

inordinate concern with worrying about time.

Let me start by comparing two procedures.

The first one does this.

We imagine that there's a tree.

Say there's a tree of integers.

It's a binary tree.

So it looks like this.

And there's integers in each of the nodes.

And what we would like to compute is for each odd number

sitting here, we'd like to find the square and then sum

up all those squares.

Well, that should be a familiar kind of thing.

There's a recursive strategy for doing it.

We look at each leaf, and either it's going to

contribute the square of the number if it's odd

or 0 if it's even.

And then recursively, we can say at each tree, the sum of

all of them is the sum coming from the right branch and the

left branch, and recursively down through the nodes.

And that's a familiar way of thinking about programming.

Let's actually look at that on the slide.

We say to sum the odd squares in a tree, well, there's a

test. Either it's a leaf node, and we're going to check to

see if it's an integer, and then either it's odd, in which

we take the square, or else it's 0.

And then the sum of the whole thing is the sum coming from

the left branch and the right branch.

OK, well, let me contrast that with a second problem.

Suppose I give you an integer n, and then some function to

compute of the first of each integer in 1 through n.

And then I want to collect together in a list all those

function values that satisfy some property.

That's a general kind of thing.

Let's say to be specific, let's imagine that for each

integer, k, we're going to compute

the k Fibonacci number.

And then we'll see which of those are odd and assemble

those into a list.

So here's a procedure that does that.

Find the odd Fibonacci numbers among the first n.

And here is a standard loop the way we've been writing it.

This is a recursion.

It's a loop on k, and says if k is bigger than n, it's the

empty list. Otherwise we compute the k-th Fibonacci

number, call that f.

If it's odd, we CONS it on to the list starting

with the next one.

And otherwise, we just take the next one.

And this is the standard way we've been

writing iterative loops.

And we start off calling that loop with 1.

OK, so there are two procedures.

Those procedures look very different.

They have very different structures.

Yet from a certain point of view, those procedures are

really doing very much the same thing.

So if I was talking like a signal processing engineer,

what I might say is that the first procedure enumerates the

leaves of a tree.

And then we can think of a signal coming out of that,

which is all the leaves.

We'll filter them to see which ones are odd, put them through

some kind of filter.

We'll then put them through a kind of transducer.

And for each one of those things, we'll take the square.

And then we'll accumulate all of those.

We'll accumulate them by sticking them together with

addition starting from 0.

That's the first program.

The second program, I can describe in a very, very

similar way.

I'll say, we'll enumerate the numbers on this interval, for

the interval 1 through n.

We'll, for each one, compute the Fibonacci number, put them

through a transducer.

We'll then take the result of that, and we'll

filter it for oddness.

And then we'll take those and put them into an accumulator.

This time we'll build up a list, so we'll accumulate with

CONS starting from the empty list.

So this way of looking at the program makes the two seem

very, very similar.

The problem is that that commonality is completely

obscured when we look at the procedures we wrote.

Let's go back and look at some odd squares again, and say

things like, where's the enumerator?

Where's the enumerator in this program?

Well, it's not in one place.

It's a little bit in this leaf-node test,

which is going to stop.

It's a little bit in the recursive structure of the

thing itself.

Where's the accumulator?

The accumulator isn't in one place either.

It's partly in this 0 and partly in this plus.

It's not there as a thing that we can look at.

Similarly, if we look at odd Fibs, that's also, in some

sense, an enumerator and an accumulator, but

it looks very different.

Because partly, the enumerator is here in this greater than

sign in the test. And partly it's in this whole recursive

structure in the loop, and the way that we call it.

And then similarly, that's also mixed up in there with

the accumulator, which is partly over there and partly

over there.

So these very, very natural pieces, these very natural

boxes here don't appear in our programs. Because they're kind

of mixed up.