How do you implement lazy evaluation?

Lazy evaluation is easily implemented in any language that can create first-class computations. That means functions or objects. In this episode, I explain how to implement a Delay, which is a reusable lazy component that is common in functional programming languages.

Transcript

Eric Normand: How do you implement lazy evaluation, even if your language doesn't support it out of the box? By the end of this episode, you'll be able to implement lazy evaluation in your favorite language.

My name is Eric Normand and I help people thrive with functional programming.

Lazy evaluation is important because it's great for separating two concerns. One concern is how you generate a value, so the code for generating the value. The other concern is how much of that value do you need? Are you even going to need it at all?

You have one part of your code say, "Here is how you generate the value," and another part of your code that decides, given that value, how much of it to actually use or whether to use it at all.

Let's go over this recipe for how you would build this thing. What we're going to be building, in spoken code, is called a delay. A delay is an object that represents one lazily evaluated value. It represents the value but it hasn't been calculated yet, or maybe it has. It doesn't matter.

From the outside, there's just one interface method on that object and it will give you the value. It's an object. Whatever you use in your language to build a little object. I'm going to assume something that has a constructor. The constructor is going to take a calculation and that calculation is what generates the value.

Let's give a really dumb example. If I need to calculate the value five plus four but I don't want to do it right now, I want to delay it, I would pass the calculation five plus four to the constructor. How do you make a calculation? How do you pass it? That depends on your language.

In something like JavaScript, I would wrap that up in a function. I'd make a function that just returns five plus four. The function has zero arguments. What functional programmers call that, a function of zero arguments — it's really not a function at all — it's always going to return the same value. It's practical because it's something that hasn't run yet but you could run it.

This is called a thunk. A function of zero arguments. If it's a pure function, it's always going to return the same thing because there's no arguments. It's called a thunk. I think it's supposed to be the incorrect past tense of to think, "I thunk about it." Anyway, it's a thunk. The only thing you can do with it is call it and it'll calculate the answer.

When I call this thunk, it'll return nine to me. Until I call it, it hasn't done that addition yet. That's the constructor for the delay object. It takes a thunk. If you're in Java and you don't have...maybe Java 8 does have first class functions now. I don't want to argue about that.

In other languages it's going to be an object with a single method called invoke or run, something like that. It's not going to take any arguments. It's just going to finally run the thing. That would be your thunk.

Now this object, besides the constructor, it has one method. Doesn't matter what you call it, it could be called get or get value.

This is what the method does. It's going to first check whether you have already calculated the value. If you have then it's going to return that value. It has to have saved it somewhere, like some field in the object. If it has not already calculated the value, it's going to run the thunk. It's going to call, invoke or whatever method it is or if it's a function it's going to call it.

It's going to take the return value from that function. It's going to save it and then it's going to return the value.

The first time you run this method, it will have to call the thunk. The second time though, it will already be saved so you won't need to call it again. What we've done with this...that's it, that's done. What we've done is we've made a reusable and generic object that can work for any calculation you might want to delay.

This is a standard functional programming tool, a little reusable thing. It takes a calculation and it delays it. It's just one thing. It only works on functions of zero arguments. Because it does not remember. It's not a memoized but it's like memoized but only for functions of zero arguments.

Memoize is another thing we can talk about in a future episode. I just wrote that down, so we'll get to that.

We've made this reusable thing. It's called the delay. It takes a thunk which is a function of zero arguments and part of the constructor. It remembers whether it has called that function before. If it has, it returns the saved value. If it hasn't, it calls it and saves the value and then returns it.

It's reusable, you can use this a lot of places. You might be saving values already, in some other method or some function has a little thing that remembers whether it's been called or not. This is a reusable thing. Now you have a thing that is totally reusable.

Do yourselves a favor. I always like to give a takeaway that you can go home and try. Implement this. This shouldn't be more than 10 lines of code. Probably less if you've got succinct language. I'd love to get your code. If you want to show it to me, I'd love to see what you've come up with to implement this thing.

One of the cool things about functional programming that I really like is that it has...People have thought about these little reusable components. These primitives that give you a lot of power. This is a higher order primitive. It takes a function and transforms it into something else. I really appreciate these because, first of all, they're not hard to understand.

I feel like I can understand them and I can collect them as part of a repertoire of things that I've learned. I can see how they are implemented into a few lines of code and say, "Ah, I get it. This really makes sense."

I learn it in a functional language and I go to another language. Let's say I have to do some work in Java and I can just write it. Even though I don't have it, it'd be really nice to already have it. I can just write it and it's not a big deal.

That's what I really like, that this knowledge is transferable. It's really convenient to have a functional language built around these things but I can bring it to any language I want.

One thing I'm thinking of now that I should have mentioned. I said that the constructor takes the thunk and that the thunk should be a pure function. It doesn't need to be a pure function. It does need to be something runnable so it can be an action or a calculation.

As an example, I could have a thing that lazily accesses the database. It has a delay for every page of values I get from the database. I could make my interface for the database just return these lazy things and say, "Here's all the pages. You want page one? You call this delay. You want page two? You call this delay. You want page three? You call this delay."

It can say, "I'm done. I've told you how to...I've given you everything I've got." The code that calls that interface has all these delays. It can decide, "I only need two pages. I don't need all 700 pages from the database so I'm just going to call these two." Isn't that nice? That's the separation of concern I'm talking about.

It can say, "I just need these two pages. Yeah, I have these. Thank you but I don't need to get all that data from the database." I'm saving some bandwidth going back and forth from the database. The connection can be freed faster, what have you.

If you didn't have the laziness, you would have to have some logic of you would ask for the first page, then you'd ask for the second page, then you'd stop. It's so much nicer to be able to have the thing just say, "Here is everything I know. Here's all the pages."

Like I said before, pop in the stack. I'd love to see your codes. Send me a gist. That would be pretty cool to see the code you've written in your language. I'll put it together. I'll collate them all into a single gist and link to it from the page.

Speaking of which, if you want to see all of the past episodes you can go to lispcast.com/podcast. There I've got video version, audio version and transcript, that's text version. That's video, audio and text of all of the old episodes and all future episodes. I will have the future episodes, I wonder how you conjugate that.

You can also find links for subscribing, for my email, and my social media if you want to get in touch with me.

Thank you very much. My name is Eric Normand and I will see you in the next episode. Wait, is that true? No, you'll see me but I won't see you so what do I say? See me in the next episode? Anyway, I hope you listen to the next episode. How about that? There we go. Bye.