Y combinator real life application: recursive memoization in javascript

Aug 10, 2016 • Yehonathan Sharvit

When we presented the Y combinator, we said that it was very aesthetic but not so practical.

Today, we are going to show a real life application of the Y combinator: the memoization of a recursive function.

The problem

Did you ever try to memoize a recursive function?

At first glance, it seems easy, using standard memoization technique e.g the memoize function from github Javascript Toolbet:

xxxxxxxxxx

JST.memoize

[Function anonymous]

Now, let’s create a memoized version of factorial, including a counter of the number of function calls to factorial:

xxxxxxxxxx

factorial = n => {

  window.function_calls++;

  return (n === 0) ? 1: n * factorial(n - 1)

}

​

factorial_memo = JST.memoize(factorial);

factorial_memo(5)

xxxxxxxxxx

120

And indeed subsequent calls to factorial-memo are cached:

xxxxxxxxxx

factorial_memo = JST.memoize(factorial);

window.function_calls = 0

factorial_memo(6)

factorial_memo(6)

​

window.function_calls

xxxxxxxxxx

7

The function has been called only 7 times.

By the way, all the code snippets of this page are live and interactive powered by the klipse plugin:

1. Live: The code is executed in your browser
2. Interactive: You can modify the code and it is evaluated as you type

But what happens to subsequent calls with smaller numbers? We’d like them to be cached also. But they are not.

Here is the proof:

xxxxxxxxxx

factorial_memo = JST.memoize(factorial);

window.function_calls = 0

factorial_memo(6)

factorial_memo(5)

window.function_calls

xxxxxxxxxx

13

The reason is that the code of factorial_memo uses factorial and not factorial_memo.

In javascript, we could modify the code of factorial so that it calls factorial_memo, but it is very very ugly: the code of the recursive function has to be aware of its memoizer!!!

xxxxxxxxxx

factorial_ugly = n => {

  window.function_calls++;

  return (n === 0) ? 1 : n * factorial_memo_ugly(n - 1)

}

factorial_memo_ugly = JST.memoize(factorial_ugly);

window.function_calls = 0

factorial_memo_ugly(6)

factorial_memo_ugly(5)

window.function_calls

xxxxxxxxxx

7

With the Y combinator we can solve this issue with elegance.

The Y combinator for recursive memoization

As we explained here, the Y combinator allows us to generate recursive functions without using any names.

As envisioned by Bruce McAdam in his paper Y in Practical Programs and exposed here by Viksit Gaur, we are going to tweak the code of the Y combinator, so that it receives a wrapper function and apply it before executing the original function. Something like this:

xxxxxxxxxx

Ywrap = (wrapper_func, f) => (x => x(x))(x => f(wrapper_func(y => x(x)(y))))

xxxxxxxxxx

[Function Ywrap]

And here is the code for a memo wrapper generator:

xxxxxxxxxx

memo_wrapper_generator = () => {

  const memo = {};

  return f => n => {

    if (memo.hasOwnProperty(n)) {

      return memo[n];

    }

    const result = f(n);

    memo[n] = result;

    return result;

  };

}

null

xxxxxxxxxx

null

It is almost the same code as JST.memoize we presented in the beginning of this article.

And now, we are going to build a Y combinator for memoization:

xxxxxxxxxx

Ymemo = f => Ywrap(memo_wrapper_generator(), f)

xxxxxxxxxx

[Function Ymemo]

And here is how we get a memoized recursive factorial function:

xxxxxxxxxx

factorial_gen = f => {

  window.function_calls++; 

  return (n => ((n === 0) ? 1 : n * f(n - 1)))

};

factorial_memo = Ymemo(factorial_gen)

xxxxxxxxxx

[Function anonymous]

And here is the proof that it is memoized properly:

xxxxxxxxxx

window.function_calls = 0

factorial_memo = Ymemo(factorial_gen)

factorial_memo(6)

factorial_memo(5)

window.function_calls

xxxxxxxxxx

7

Isn’t it elegant?

Fibonacci without exponential complexity

The worst effective implementation (exponential complexity) of the Fibonacci function is the recursive one:

xxxxxxxxxx

fib = n =>

(n < 2) ? 1 : fib(n - 1) + fib(n - 2)

xxxxxxxxxx

[Function fib]

There are a couple of effective implementations for the Fibonacci sequence without using recursion.

Using our Ymemo combinator, one can write an effective recursive implementation if the Fibonnaci sequence:

xxxxxxxxxx

fib_gen = f => n =>

(n < 2) ? 1 : f(n - 1) + f(n - 2)

​

fib_memo = Ymemo(fib_gen)

xxxxxxxxxx

[Function anonymous]

Let’s compare the performances of the naive recursive version and the memoized recursive:

First, let’s load a timing function named JST.time code from github Javascript Toolbet: it works like console.time but with two differences:

1. It returns the elapsed time instead of printing it
2. The elapsed time resolution is fraction of milliseconds

xxxxxxxxxx

JST.time

xxxxxxxxxx

[Function anonymous]

And now, let’s compare:

(We have to redefine fib_memo, in order to reset the cache each time we re-run the code snippet.)

xxxxxxxxxx

var n = 35;

fib_memo = Ymemo(fib_gen);

​

[

  JST.time(() => fib(n)),

  JST.time(() => fib_memo(n))

]

xxxxxxxxxx

Array [

  "169.445000 msec",

  "0.190000 msec",

]

On my computer, the memoized one is around 300 times faster!

Please share your thoughts about this really exciting topic…

to stay up-to-date with the coolest interactive articles around the world.

Discover more cool interactive articles about javascript, clojure[script], python, ruby, scheme, c++ and even brainfuck!

Give Klipse a Github star to express how much you appreciate Code Interactivity.

Feel free to email me [email protected] for getting practical tips and tricks in writing your first interactive blog post.