, In this segment and the next, we're going to talk about streams which are a different programming idiom that also needs some notion of delaying evaluation and the implementation will use thunks. In order to accomplish that. So, a stream is a word that we use in computer science to mean an infinite sequence of values. All right, something that can go on for as long as you need. It behaves like somethings infinitely big. Now, one thing about infinite sized things, you can't actually make them. Right? We need something that's going to represent something that could go on forever. And the key idea we're going to use is to use a thunk to delay the evaluation of most of the sequence and only generate some prefix of the sequence That some other computation needs. We're not going to need any new language constructs. This is just a program idiom using thunks and things like that. But it's a powerful concept for dividing labor up in a way that works in a lot of different software systems. So, the idea is that. The, the program, part of the program producting the stream, creating the stream, knows how to create any number of values you need. But does not know how many you need. Whereas the stream consumer can ask for these values as it goes along, without knowing anything about the process that is generating So it turns out this comes up a lot in software systems. It's okay if you're not familiar with any of these examples, but I thought I would mention them for those of you who are. one way is if you're implementing code that need to respond to a whole bunch of user events, mouse clicks, keyboard presses, things like that, we saw earlier in the course we could do that will call backs. But another way to do it is to think of that as some stream of events. We'll as for each one as we need it, and then we'll compute some result with that thing so far. And someone else will generate those events as they occur. Have you ever programmed with pipes in the UNIX shell system? It turns out that the second c ommand, pulls data from the first command as it needs it so it views the first command as a stream. And the first command's output is generating that stream. There's also a nice connection with electrical engineering and circuits, that if you think of a timed circuit with feedback. You can think of the different output values it's sending on it's output wires as forming an infinitely long sequence. And then the, the circuits reading those values Can read the ones that they're interested in. Anyway, just optional things just showing this is kind of, of a universal concept even if you find it a bit abstract. You'll also see some simpler and more fun examples on the homeowrk assignment associated with this material. Okay, so we want to represent a stream. In some way that we don't actually generate an infinitely long list or something like that. So here's how we will do it. We're going to represent a stream as a thunk. So a stream will just be a thunk, but not just any kind of thunk, a thunk that, when you call it gives back a pair, where the car is the next thing in the sequence. The first thing in the sequence. And the CDR, is a stream for values 2 through infinity. So it is a stream that, if you use it, you get the next value. So in this segment, I'm just going to show you how to use this thing Then in the next segment, we'll see how to define our own. Using them usually helps explain what they are and get a little better sense before we try to create them. So I've already loaded the file where I've created the streams I will show you in the next segment. And one of the streams is the infinite sequence of powers-of-two. Two. So you know, the first thing this thing returns - I, I forget if it starts at 1 or 2. And the 4, and then 8, and then 16, and then 32, on forever. Because we don't know how many powers of 2 we need. But when I said powers-of-two, as you saw here, all I got back was a procedure. Because our streams are thunks. That when you call them return a pair. So, how do you call a thunk? You put it in parentheses, powers-of-two. And look at that. I got back a pair, who's first component is 2, so I did set it up to start at 2, and a second component is another procedure. Turns out that's a thunk. So, if I wanted the first thing in the sequence, I could just say car. Of calling that. And if I wanted the second sequence. Let's think about this. Need to call the cutter to get another stream, a stream is a thunk so I need to call it. And then I need the car of that. And that gets me four. What if I wanted the next element of the sequence? Well this thing is four, the cdr is another stream, a stream is a thunk so you call it. That gives back a pair and I made the car. of that. And that would give me 8. Now of course we wouldn't keep programming like this to get 16 or 32. The idea is we would have some sort of recursive function that is passing this next stream onto say some recursive call. And then we. Apply that string, to get a pair, and we take car to get the next thing. And so if you wanted to say add up the first 100 powers of 2, you would just have some little recursive function, that would be using this string as you go along. So what I thought I would do instead of showing you that is show you something even more general. Let's define a recursive function that I'll call number until. That's going to take in a stream. And the function which I'll call tester, alright, and the idea of what this is going to do is it's going to count how many stream elements you need to process before tester returns true for the first time. So if it doesn't ever returns true, we're going to an infinite loop. But otherwise, we'll stop as soon as we get our first true and we'll return the count of how many we've got. So I'm going to do this with a little tail recursive helper function. So I have a little letrec here. So I'm going to take in my current stream, the stream that has all the elements I haven't processed so, So far, my accumulator which is my answer so far, I'm goi ng to have to put some stuff in here. and then I'm just going to call F the stream I started with, and 1, that's my initial accumulator. So now the idea is all the body of F has to do, where I've left this dot, dot, dot. is see well, what does tester have to say on the first element of the stream. If that's true, return answer. Ohterwise, call f again with one more and with the tail, if you will of the stream. The rest of the values. So here's how I'm going to do this. Let's first of all call that stream. We know a stream is a thunk. All right? I'll get rid of these so you can see it. So I know a stream is a thunk. So if I call it, I should get back this pair. Right, of the first element, and then the stream that is the rest of the elements. 'Kay. Now that I have that pair, let's call tester on the car. If I get back true, I'm done. Return ans. All right? Otherwise, call f. On the cdr of the pair, that's my new stream, right? Don't call it yet, right? We don't want a pair, right? This would be a pair. But f expects the stream and then f itself calls that thunk to get back the pair. So just with the cdr and then one more for the accumulator. That's my call to f. That finishes my if, my let, my definition of the lambda for f, and this letrec that I then to use to start by calling f with the stream that was passed a number, until. End 1. So, and then I need to end my define, my letrec, and my define, and now I've just defined a function, that's all I did. Okay. So now if I call number-until with the stream powers of 2. Alright? And how about a little function that takes in a number and says, does that number equal 16? I go back to 4. It took me four times through the stream until I got something that equaled 16. Let's have a little more fun. How about I keep going until I get a number that is bigger than This number. Ok? The great thing about powers of two is they grow really fast, so that took 339 tries. If I had come up with a number ten times bigger it'll take 343 tries, and ten times better than that it'll probably take 346 tries. because powers-of-two multiply really fast. Let me point out that when you program your streams, you tend to make lots of mistakes with parenthesis. Think very carefully about, do I want to pass in a stream or a pair that I get back when I call the thunk? If I get this wrong and I put parenthesis here And are passing to number until a pair. And therefore right here you can just see at the top of the screen. That's going to be pair when you try to treat a pair as a function, you get a big nasty error function. It says, procedure obligation expected procedure given the pair two and some string. So you have to think very carefully about the difference between a thunk and a pair. And if you do that, you can do some beautiful programming by using streams with beautiful recursive functions to get interesting results.
