[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.
Defining Streams
Loading...
From the course by University of Washington
Programming Languages, Part B
345 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
[MUSIC]
So now that we know how to use streams,
I want to show you how you can define your own.
Which is usually what you need to do first before you can use them, but
I put it off in order to present things in the other order.
Remember that what we are a calling a stream is a thunk that when you
call it returns a pair of the first element of the stream, and
then a stream for the rest of the other elements.
The infinitely many that follow.
So now what we want to do is make our own.
I admit this is a little mind-bending but it just uses things we already know.
So just understand where we're using recursion, where we're using funking and
it's all just going to work out surprisingly easily.
It's one of those things where the code is so
short you think it's simpler than it actually is.
And that will be fine, okay?
So let's just do this.
And for the first stream I want to generate,
let's do the simplest thing in the world.
It's a stream that no matter how many times you call it,
it just returns one forever.
It's the infinite sequence of ones.
So I'll just define a variable to hold my stream and I'll call it ones.
So every stream is a thunk, so this is what my thunk is going to be.
So when I call this thunk, I need to return a pair.
Do that with cons.
The first thing should be one, and
now what I need here is a stream that returns all ones.
So what you could think is that, well, that needs to be a thunk, right?
And that's going to have to return a pair.
And then that's going to need another thunk.
And that's going to have to return a pair and
we're going to be here literally forever if you try to define your stream that way.
But we can do something better.
Right here, where I was, I need to put right here
something that is a thunk that when called returns
a pair of 1 and then a thunk with more ones.
And I actually have just the thing I need.
All right, so this looks like I'm defining ones in terms of ones, and I am.
Every recursive function is on some level defined in terms of itself.
This make perfect sense.
Ones will be bound to a thunk that when you call it
returns a pair of one and then the procedure itself.
It's just recursion, just in a different way than you've seen it before.
This really does produce the stream, but let me show you if I
call ones and take the car of that.
Excuse me here, car of that.
I will get a 1 and if I take the cdr of it and call that to get a pair back and
take the car of that, I get another 1 and so on forever, okay?
So that's ones.
Now let's do a more interesting one, slightly more interesting,
we're building up of course.
1, 2, 3, 4, 5.
Something that is the stream of the natural numbers.
The positive integers, okay?
I'm going to define a function f that's going to take one argument.
We'll return the stream that starts at x, all right?
So it'll do x, x + 1, x + 2 forever.
So what I do for that one is I just need to return, let's see a pair.
Well, the way I'm going to do it,
is I'm going to say if you give me x, I'll give you back a pair of x.
So I'm not returning a stream here, I'm returning the pair.
But then the thing in the cdr will
be the infinite sequence that starts at x = 1, and goes on forever.
And again, we see recursion.
That if you call f with a number x, you get back a pair of x.
And a thunk, that when you call it, will give back a pair of x + 1 and
a thunk that when you call it and so on.
And now all I need for nats is a lambda, a thunk,
that when you call it, because every steam is a thunk.
So the stream of natural numbers is just a thunk that then just calls f with 1, okay?
So this works fine.
The way I would prefer to do it.
Let me just make a copy real fast.
Is since f is really a helper function, I'd rather I define it as such.
Cons x (lambda
thunk (f + x 1).
And then lambda f 1.
And that's just slightly better style.
So that's all fine.
We could test that one out as well.
How about the one I showed you in the previous segment, powers of 2.
That goes 2 4 8 16 and so on.
We saw it grew very fast.
It turns out it's a whole lot like nats.
It's so much like nat that I'm going to copy and
paste it and say powers of two, all right?
And all I need to do is instead of adding one,
I need to multiply by two.
And we'll get it over there.
There we go, all right.
And of course, I should've spelled lambda correctly.
And of course, the code posted with the segment will be absolutely correct,
in case I'm making any typos here.
And now I have my stream powers of two.
And of course, and you just saw that sort of copy and paste,
I really shouldn't do that sort of thing.
Instead I should have helper functions, right?
So maybe a helper function could be called stream-maker, and
it could take in a function for combining things.
And the argument that is the previous one, and I'm going to leave this to you if
you're curious to look up in the code that I'll post with this lecture.
How to define this, it's really just subtracting over the fact that I have
a plus one here and a times two there.
And then I define a version of nats where I just call
stream-maker with the addition function in one.
And a version of powers-of-two where I call stream-maker with multiply and 2.
But instead of showing the details of that,
I'd rather emphasize the basic idea of what these streams are doing.
That in every case, right, every stream is a thunk,
that when you call it returns a pair, all right?
And the way it knows the hard part of that pair, is the cdr, the next thunk, right?
And the body of that thunk ends up being something that uses recursion.
So in nats, the body of that thunk, which we don't call right away,
just calls f again with x + 1.
In the ones case, we just got to use the function itself.
It would look more like the other ones if
we said lambda no arguments call ones.
And that's totally correct, it's just unnecessary function wrapping.
What's the point of having a thunk that when you call it calls ones with no
arguments?
Ones is just as good.
So the other thing I want to emphasize for you, because it is mind-bending and
difficult to define your own streams, is some mistakes you might make.
So let's do that in terms of ones.
So here's a couple things that if you understand why these don't work, you may
be in a better position to understand why the version above does work.
So here's one that's just really-bad.
It just returns cons of 1, and ones-really-bad, okay?
So first of all, it's not returning a thunk at all, it's returning a pair.
And to evaluate a pair, we need to look up ones-really-bad but
we're not even done defining it.
This doesn't work in a language like Racket because it's an eager language.
When you go to evaluate this binding for ones-really-bad,
we need to evaluate this pair.
And to evaluate this pair,
we need to look up this variable then we're not done defining it.
That really is circular.
Something like this does work in Haskell, if you've seen it,
exactly because the semantics of function call for cons is different in Haskell.
It definitely does not work in a language like Racket or ML or Java or
any of the other languages with eager semantics for function calls.
So that one definitely doesn't work.
This one might frustrate you a little bit more if you do something like this.
So, I return a thunk.
That's great, all right?
And now I think, well, I need to cons one onto something,
and now what I want to do is call this thunk, ones-bad.
So I can do that.
Because now my recursion is inside this function.
So it is a recursive function call.
But what this does, it does not put a thunk in the cdr.
It puts the results of calling that thunk, and
in its cdr will be the result of calling that thunk.
And in its cdr will be the result of calling that thunk.
And this is an infinite loop.
This is something that if you evaluate ones-bad, so
if I click run here, oop, can't define things multiple times in a module.
So let's delete all this down here, and then come back up here and try it again.
Everything worked fine.
Ones-bad is a thunk, right?
It's a procedure but as soon as I call it,
it's going to generate a list that's infinitely long.
And that's not what streams are.
I'm going to have to click Stop up here.
Streams are not things that are infinitely long.
They are things that, when you keep applying the thunks and
the cdr, you can keep getting additional values.
That's why the version above is correct and
the version bad just creates an infinite loop.
So, that's defining streams.
On your homework, you'll get to define a stream.
You'll also define a function that takes a stream and returns a new stream.
That's something I didn't show you.
It'll be a challenge for you, even though you need to do it.
To just take the steps we've seen, get the idea of right where you have a thunk,
where you need to call a thunk.
And then you can program it with streams.
You'll be able to test them out by using streams and you've learned a powerful and
subtle programming idiom.
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.
