[As described below, this is Part B of a 3-part course. Participants should complete Part A first -- Part B "dives right in" and refers often to material from Part A.] This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language “fits together” to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module of Part A. Part B assumes successful completion of Part A. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.
Using Streams
Loading...
From the course by University of Washington
Programming Languages, Part B
372 ratings
From the lesson
Section 5 and Homework 4 (First Module with Racket)
Let's get started programming with Racket and then learning idioms related to delaying evaluation. The welcome message has a few additional comments about picking up a new language and how to approach the homework assignment, so let's get started...
Meet the Instructors
Dan GrossmanProfessor
Computer Science & Engineering
, 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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
