Functional Programming: Understanding Memoization.
Introduction
According to Wikipedia, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
There is a caveat that shouldn’t be ignored; only pure functions can be memoized.
This is an advanced topic so I have curated a list of pre-requisite concepts (with helpful links) to grasp before jumping in. I really recommend going through (and understanding) these topics if you have no prior knowledge of them before jumping into this article.
For this article, we will use a very interesting mathematical concept, the Fibonacci Sequence.
Simply put, the Fibonacci Sequence is a series of numbers in which any term is the sum of the previous 2 terms.
So if we start from 0 and 1 (people argue that it should start from 1 directly since 1 is the first term in the sequence) the sequence can be fleshed out to read 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ….
The list can continue for as much as we can count, and to prove this, we are going to write a pure function f(n) that takes in n as a parameter and then returns the nth term of the sequence.
A beautiful function right? If you don’t understand this function, kindly pause and go read this article again.
If you’re half as curious as I am (I’d be dead if I was “the cat”), you would try larger numbers like 40, 50 or even higher. I can actually guarantee that after trying 50 (or anything above), you would think twice before running the function again with the same argument 😁🏃🏿♂️🏃🏿♂️🏃🏿♂️. Well, our smart computer has a hard time computing the results as n increases. This is because, as n increases, the function calls become more “expensive”.
This may sound a bit vague but I think a graphical representation will make things clearer. Below is a sketch of how the function executes for n = 5;
As we can see, there is a lot of repetitive computation, f(3) is called twice, f(2) is called three times and so on. And remember for each call, we will still go down the tree to get the final value. Things are already starting to get messy.
Our lovely computer will get away with f(5) of course and maybe f(10). But what if we really need to compute the Fibonacci number for higher values of n?
Memoization
Just like we said earlier, we can use memoization to speed up the computation of functions (the Fibonacci number in this case) by skipping computations we’ve already encountered and instead, read the value directly from the cache. This is possible because our function is a pure function. For the same input, we will always get the same result. This allows us to replace the function call with its resulting value without changing the meaning of the program. And we can confidently do this because we know that our function has no side effects.
Below is a memoized version of our fibonacci function.
Ok. There’s quite a lot going on here but let me explain…
The memoizedFibonacci function returns a brand new, smart fibonacci function. And notice we declare a new variable called fibonacci outside the memoizedFibonacci function. This should not be confused with the function returned from the memoizedFibonacci function. The outer fibonacci function holds a reference to the returned fibonacci function. The inner fibonacci function has closure over the cache variable and therefore can store and retrieve data from the cache. This can be demonstrated in a browser console.
Do not be overwhelmed by the image above. It is a very basic demonstration of the closure concept. From the outerFunction we return an object with two methods: increase and decrease. If we execute the outerFunction and store the result in a variable, we can inspect the resulting object and see the properties of the increase and decrease function. Notice the [[scopes]] property, it also has a property called Closure. The Closure property lists all the variables available (enclosedVariable in this example) to the function from the parent function’s block scope. And we can’t access this variable from outside the outerFunction. But calling increase or decrease will alter this variable because it was enclosed together with the functions when they were returned from outerFunction.
Back to our fibonacci function with superpowers, calling the memoizedFibonacci function will return the fibonacci function enclosed with the cache variable and each execution of the returned function will store its result in the cache.
The execution steps are now thus:
- check for the input, n in the cache. If it exists, return it. Don’t do any other thing, just return the value because we already know what it is. (Just think about the amount of time this will save us).
- If the value is not in the cache, we calculate it and add the result to our cache for easy retrieval the next time.
So for every input encountered down the execution tree, save it in the cache (implemented as a hashmap where the inputs are the key and the results are the values) so that the next time it’s seen, we just return from the hashmap rather than execute the time-consuming part of the function.
Interesting right?
Now you can see why our computer didn’t run out of breath trying to figure out what the 1000th term of the Fibonacci sequence is.
Memoization can be applied to other functions as long as they are pure functions and have no side effects. The next step in this article is to write a memoization function that can be applied to any pure function.
Notice that the first call to memoizedFibonacci took approximately 2 seconds to execute. But the next and other subsequent calls with the same input will execute immediately.
There is one flaw with our memoize function. It only caches the input of the function at the top of the node (40 in this case). Calling memoizedFibonacci(30) will still take some time to execute even though we know we must have encountered it while calculating the 40th Fibonacci number. Here’s why:
Line 6 executes our function and stores the returned value in the cache, although this caches the return value, it does this just for the value we pass, so if we call memoizedFibonacci(40), here’s what our cache will look like:
{ '40': 102334155 }To walk around this, we can memoize the fibonacci function itself and then pass it into the memoize function.
Notice how even though we have way larger values for n in this example (1000 vs 40), we have significantly less compute time.
I know you may be thinking, “this is way too messy for me to even dabble into, Thanks for nothing Chux”. Well, you’re absolutely right. Apart from the fact that I’m a horrible teacher, the implementation is way too verbose and hard to keep up with. But I’ll show you a much neater way to implement this.
Decorators
In its simplest form, a decorator is simply a way of wrapping one piece of code with another — literally “decorating” it. This is a concept you might well have heard of previously as functional composition or higher-order functions.[source]
Decorators are currently a stage 2 proposal in JavaScript and should become a part of the language in a future update.
But since this isn’t strictly a JavaScript article, I’ll show decorators in action using python.
Neat huh?
I love decorators so much as they make our code a lot more readable. Notice we didn’t have to memoize the fibonacci function again as the decorator tells the code each time you encounter the fibonacci function (line 8), memoize it. The same implementation written verbosely will end up looking like our previous implementation in JavaScript. I will leave it up to you to write out the verbose implementation in python and feel free to drop it in the comments section.
And it’s a wrap…
We touched a lot of advanced concepts in this article and if you had a hard time following, I really suggest you take a look at the topics I listed at the beginning of this article. Functional programming can be quite daunting at first approach. And this is simply because of the new terms and concepts you need to wrap your head around. But really, these are really just fancy words. Once you grasp the concepts, you will see how easy it is to mess around with pure functions and solve complex problems (Quickly and Elegantly).
Thanks for reading.
