Lazy Evaluation in Javascript

TD;DR, Lazy Evaluation in Javascript object properties can be easily performed with Object.defineProperty().

Some time ago i was searching for a way to reach some kind of lazy evaluation in node.js.

I was building an object that must have an attribute containing an instance of its same kind (recursively). This could be achieved through a function instead of an attribute, but this was a very specific scenario.

So what i really needed was way to run this instantiation only when the object property was called, and not during the object construction.

Even tough i found some Javascript articles about call-by-name or call-by-need strategies on stackoverflow, nothing was working for what i was trying to do.

Most articles, code and libraries i came across was achieving lazy evaluation through a Proxy. But this kind of object is not available in older versions of node.js, which was my case.

In brief, Lazy Evaluation, also known as call-by-need, is defined as:

Call by need is a memoized version of call by name.

But what is a call by name? And what about memoized?

Call by Name & Call by Value

First, lets examine these two functions:

// Evaluates with call-by-name strategy
1 function callByName (a, b) {
2  if (a === 1) {
3    return 10
4  }
5  return a + b
6 }
// Evaluates with call-by-value strategy
1 function callByValue (a, b) {
2  if (a === 1) {
3    return 10
4  }
5  return a + b
6 }

Keep in mind that this is not Javascript. The first function evals through call-by-name, and the second one through call-by-value.

To understand the difference between both types of evaluation strategies, we can look line by line of some pseudocode of how the execution might be executed.

1 > callByName (1, 2 + 3)
2 > a === 1
3 > return 10
1 > callByValue(1, 2 + 3)
1 > callByValue(1, 5)
2 > a === 1
3 > return 10

You might seem familiar with the second one. This is because Javascript only passes arguments as values (or by reference if it is an object).

In a call-by-value function (or Eager Evaluation) the numbers 2 and 3 are first summed up and then they are passed as function argument with the value 5.

On the other hand, in the call-by-name function (or Lazy Evaluation) showed in the example, the second parameter b is not even evaluated since the function returns 10 before b is used by the function.

Memoization

In short, memoization is an optimization technique to store pre-computed results (cache), to avoid recomputation for the same inputs.

In a more formal way, this means that if an idempotent function

f(x) = g(x) + 1

will always output some value y when it receives an input v, then f(v) = y.

So if g(v) is very expensive in terms of time or machine resources, we can store the result y in a cache to be returned when v is the input, such that we don’t have to recompute g(v) again.

cache = {}
cache[v] = y

The Infinite Recursion Problem

Now we will go through some very straightforward code of a recursive object which does lazy evaluation to avoid infinite recursion.

We will analyse an infinite data structure called Stream, very common on Functional Programming languages.

What would happen if we try to run this code?

var stream = new Stream(10);
> RangeError: Maximum call stack size exceeded

As expected, it would fail with a RangeError.

The problem is in the line of code below, where we are doing an Eager loading of the next attribute.

this.next = new Stream(value + 1);

Let’s change the Stream to be Lazy instead.

Note that i also added a takeUntil method to the Stream. Lets move on and try to run this code.

var stream = new Stream(10);
console.log(stream.takeUntil(20))
> [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Now, not only we can build the Stream, but it is also possible to run infinite algorithms like takeUntil with this implementation.

You may be thinking: Why we didn’t use memoization here?

Well, we could, but this optimization is no worthy since we are doing just a basic math operation of summing two operands. This is not expensive computationally like it would be, for example, to calculate if value is a prime number.

References:

• http://stackoverflow.com/questions/6605640/javascript-by-reference-vs-by-value#6605700
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/defineProperty
• https://en.wikipedia.org/wiki/Evaluation_strategy
• https://en.wikipedia.org/wiki/Memoization

Hacker Noon is how hackers start their afternoons. We’re a part of the @AMIfamily. We are now accepting submissions and happy to discuss advertising &sponsorship opportunities.

To learn more, read our about page, like/message us on Facebook, or simply, tweet/DM @HackerNoon.

If you enjoyed this story, we recommend reading our latest tech stories and trending tech stories. Until next time, don’t take the realities of the world for granted!