Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees and Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Defining Streams

Loading...

Programming Languages, Part B

University of Washington

4.9 (437 ratings) | 12K Students Enrolled

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

Skills You'll Learn

Racket (Programming Language), Programming Language Concepts, Type System, Functional Programming

Reviews

4.9 (437 ratings)

5 stars
408 ratings
4 stars
27 ratings
3 stars
2 ratings

KR

Mar 23, 2018

I'm a pretty experienced C/C++ programmer and this course has been a brilliant introduction into functional programming and the underlying philosophies underpinning programming languages in general.

JM

May 09, 2018

DO THIS COURSE. It brings together everything in part A. In particular, the final shorter week on the differences between Statically and dynamically typed languages is mind-bending and brilliant.

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

Introduction to Racket8:23

Racket Definitions, Functions, Conditionals10:14

Racket Lists9:07

Syntax and Parentheses8:36

Parentheses Matter! (Debugging Practice)10:50

Dynamic Typing9:36

Local Bindings13:11

Toplevel Bindings4:54

Mutation with set!8:28

The Truth About Cons7:46

mcons For Mutable Pairs7:38

Delayed Evaluation and Thunks10:12

Avoiding Unnecessary Computations6:48

Delay and Force9:18

Using Streams10:10

Defining Streams10:49

Memoization10:17

Macros: The Key Points8:52

Optional: Tokenization, Parenthesization, and Scope7:30

Optional: Racket Macros With define-syntax9:25

Optional: Variables, Macros, and Hygiene10:52

Optional: More Macro Examples9:12

Taught By

Dan Grossman
Professor

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

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates