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
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Memoization

Loading...

Programming Languages, Part B

University of Washington

4.9 (460 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 (460 ratings)

5 stars
431 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

Transcript

, I wanted to show you one more idiom that helps us avoid repeated computations and

how it's useful. Turns out this idiom does not really use thunks, but that's okay

it's still worth knowing and it's called memoization which is not an English word.

But it is a technical word we use for this. And we really do leave the r out and

call it Memoization not memorization and it's been called that for a long time. So

here's the idea, if a function has no side effects and doesn't read anything that can

change. There's no point in computing it twice for the same argument. If you call

it twice with seven you're going to get the same answer. If you call it twice with

the same lists you're going to get the same answer. Doesn't matter how many times

you call it. So what we could do is keep what's called a cache of previous results.

Keep some data structure that remembers. Hey if you call this funciton with seven,

this is what you're going to get back. And this can be a great idea if maintaining

and using the cash is cheaper. Then recomputing the results. And if people

actually do the recomputations. They actualy call the same function with the

same argument again. Otherwise, the cache is a waste of space and a waste of time.

So, this idea is really pretty similiar to promises. That thing we saw with force and

delay, right? That when we do the first force, we'll store the result so any later

force just has the result there. But force of delay was for thunks that don't take

any arguments. Once you take arguments, you can't just have one thing that you've

stored for future reference. You need a table of them, depending on what the

arguments are. So that's where memoization is a little more sophisticated and I'm

going to show you an example where using memoization with a recursive function

actually leads to a program that is exponentially faster. And so it's a common

technique, something you can apply almost mechanically. That could actually lead to

programs that are much more efficient. other times, the y're just a little more

efficient, and it's still considered a convenient thing to do. So I'm going to

show the most of the rest of this with the code. I'm going to use this classic

example from memoizaton, this is what most people use. Here's an implmentation the

fibonacci function. This is a function for mathematics the same way we've been using

factorial, which says that the factorial n is n times factorial of n minus 1. With a

base case of factorial 0 as 1. Fibonacci is a little more sophisticated. It says

fibonacci is one for both 1 and 2. So just read the racket code here. If x is one or

x is 2, it's 1. Otherwise it's the sum of fibonacci of x minus 1. And Fibonacci of x

minus 2. So you see two recursive calls here. And turns out these two recursive

calls cause this to be a very inefficient implementation. This is exactly how it's

defined mathematically. You recall Fibonacci 1 with 30 you get a nice big

number like 830,000. But if you call with 40, this takes about a thousand times

longer to evaluate. And I don't have a thousand times longer to wait so I'm just

going to stop this. And say this is not a good implementation of the fibonacci

function. Okay so, what are we going to do about it? One thing you could do, which

I'm not going to focus on here, is throw away that algorithm, and implement this

other bottom up algorithm, that uses a local helper function that takes an

accumulator and starts at low numbers. And figures out fibonacci up to high numbers

by adding the 2 previous numbers as you go along. You're welcome to look at the code,

it's not that complicated. I just want to admit that this algorithm exists before

moving on and showing you a different way to do this efficiently that show this idea

of memoization. 'Kay, so, we're going to forget about that second version. Just

move on to the third version. I know it looks big and complicated. We're just

going to go through it line by line and see that it's just implementing this idea

of keeping around all the previous results. So, any time we compute Fibonacci

of anything we're going to put that in our table. And because we're going to do that

even when we make recursive calls it's going to in turn Fibonacci into an

effecient. Function. So let's see how that works. So the first

thing that you'll notice is that fibonacci ends up just being this helper function f.

So I'm going to define this function f here and then just return it. And the

reason why I'm doing that, is that I need f to use this memo table, this cash, this

thing that is initially null but is bound to this variable memo. It's essential, I

don't want memo to be at the top level, I don't want to define memo up here, 'cause

this is an implementation detail. I don't want to expose it to the outside world. ,

But I also cannot put it inside this function I'm going to define. 'Cause if

you put it inside, we're going to recreate a new table every time we call this

function. Because we do not execute function bodies until we call them. We

need it outside the table, so that it persists, so it's still around from one

call to the next. And it's initially null. Now, we're going to use mutation to update

it appropriately. Really. Okay, so when we want ca, find fibonacci

of x, so we just call x right here, okay? The first thing we're going to do is see,

is it already in the memo table. So, here, I'm using a little library function,

assoc, that takes in something and a list and tells you if that something is in the

list in the following way. Let me show you how this works. You can look it up on your

own in the manual, if you don't get this quickly. So let me define a little list

here. it has to be a list of pairs. Because pairs could have anything you want

in them, but how about just, three different pairs of integers here. Okay.

So that's a little list, xs just looks like this. What assoc does is it takes a

number like 3. And a list of pairs and it checks the car fields of the pairs for

something equal and with the first time it finds one, it returns that pai r. So a

assoc 3 xs returns 3, 4. Assoc 1 xs returns 1, 2 and if it's not in the list,

like 6 you do see a 6 up here but it only looks at the car fields, it returns false.

Meaning I did not find it in the list. So that's assoc. We're going to use assoc up

here, so I had to tell you how it works. So our memo table, which is initially

null, is going to be a list of pairs, and what it's going to be is argument dot

result. We're going to store in that list pairs of, if fibonacci, fibonacci of arg

is result. Alright? So here's what we do. If we find our answer in the table, so we

gotta pair here, and everything that is not false is true, so this works, and

return the cdr of that pair. We looked up the argument x, we found it, return the

result. So that's how we get our reels. In this else branch, we didn't find it. So

now all we have to do is compute it and then put it in the table so people can

find it in the future. So, how do we compute it? That's what this let variable

does, new-ans. We say, well, if x is 1 or 2, then it's 1. Otherwise it's adding

recursive call of x minus 1 and recursive call of x minus 2. Before we return,

change via set! memo to hold a bigger list. Take the old list memo, cons on to

it the pair of our new argument result pair. So that in the future, if anyone

needs fibonacci of x They'll find it in the table. After we've done that, return

this thing that we computed and that is the fibonacci of the number. So, this all

works and what might surprise you is that it's fast. I can ask fibonacci 3 of 1000

and I get this big number. No time at all. So why is this so much efficient than the

naive recursive version, that couldn't even do 40. I don't even think it could do

35. It looks like if it's not in the table, we're still doing these two

recursive calls, and it would blow up exponentially. But we are doing two

recursive calls, whichever one we do second. Will be very, very fast. See, the

problem with exponential blowup is that we make two recursive calls, and they m ake

two recursive calls, and they make two recursive calls, and it blow ups, blows up

2, 4, 8, 16 and 32. But what happens here is we make two recursive calls. The first

recursive call ends up filling up the table with lots of numbers. The second

recursive call ends up finding what it needs in the table. Especially if the

second one is with x minus 2. The second one is x minus 1. It will still have to do

one more recursive call, but then it will find what it needs in the table. And

that's only at the top level. After that, everything's already in the table. So

recursivly, at every step, instead of making two expensive recursive calls, we

make one recursive call. And then, for the next recursive call, everything is already

in the table. So this isn't just twice as fast, it's twice as fast at every level.

And in fact, it's taking something that would take time proportional to 2 to the

x. And turning it to something that takes time proportional to x. Or if you really

want to be picky, since I have to run down this list doing assoc, maybe x squared.

But x squared for a 1000 is nothing. that's no problem at all. Whereas, 2 to

the x, where x is a 1000, is more than I believe, the number of particles in the

universe. So that's our example. It's just a programming idiom. All we did was really

that something that had nothing with fibonacci itself. We created this table.

We always checked it first. If we found it, we did nothing else. Otherwise, we

compute our answer. And before we return, we add our result to the table for the

future. And that is Memoization.

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