Subtitles section Play video Print subtitles 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.