Placeholder Image

字幕列表 影片播放

  • PROFESSOR: Well, last time Gerry really let the cat out

  • 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.

  • The programs don't chop things up in the right way.

  • Going back to this fundamental principle of computer science

  • that in order to control something, you need the name

  • of it, we don't really have control over thinking about

  • things this way because we don't have our hands in them

  • explicitly.

  • We don't have a good language for talking about them.

  • Well, let's invent an appropriate language in which

  • we can build these pieces.

  • The key to the language is these guys, is what is these

  • things I called signals?