Photo Credit: Edu Lauton https://unsplash.com/edulauton | Modified by Chinedum Ukejianya

Functional JS: Trampolines & Tails

Functional Programming is the new craze today. Object Oriented Programming is still the most popular form of coding, however, many new JS frameworks and ideas are adopting functional programming philosophies. In this article, I will not be going into exactly what functional programming is, but if what you learn today sounds interesting, I would highly encourage you to do more research on the subject.

Trampolines&Tails

I first heard about trampolines in a functional-javascript exercise from node school. I did not know what the exercise was asking at the time and was not aware that to understand the question I needed to understand tail recursion.

Screenshot of the trampoline exercise

Recursion

Before we dive into tail-recursion, we need to first talk about recursion. If you are a math nerd or took a mathematical proofs class, you might have heard this word before. A recursion function is a function that continuously calls itself with modified inputs until it reaches a base case. The classical recursion function example is the“factorial.”

function factorial (n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial (n — 1);
}

Photo Credit: Penjee https://blog.penjee.com/how-recursion-works-in-7-gifs/

So factorial(4) = 
4 * factorial(3) = 
4 * (3 * factorial(2) ) = 
4 * (3 *(2 *factorial(1)))= 
4 * ( 3 ( 2 * ( 1 ) ) ) = 
24

Recursion can be used to express code in a more readable form, but there are limits to its use. If a function makes too many nested function calls, something called a stack overflow occurs. Every time you call a function, that function call is put into the call stack within allocated memory. This stack has its limits and can only store so many function calls. This is where tail recursion comes into play.

factorial(4) // 24
factorial(50000) //RangeError: Maximum call stack size exceeded

Tail Recursion

Tail recursion is an important feature in functional programming. The subtle difference between regular recursion and tail recursions is rather than using the function as an operand, we pass the changing result into the next recursive step. What this prevents is a stack overflow. A way to implement this would be like the following

function factorial(n) {
  var recur = function (result, n) {
    if (n === 1)
      return result;
  
    return recur(result * n, n — 1);
  }
  return recur(1, n);
}
So factorial(4) = recur(1, 4) = recur(4 * 1, 3) = recur(4 * 3, 3) = recur(12 * 2, 2) = recur(24 * 1, 1) = 24. 

This implementation would be great if not for one thing; this factorial function still causes a stack overflow in javascript. Tail recursion is a feature which needs to be implemented on the language level. In a language that implements tail recursion, the interpreter or compiler sees that the recurring function call is the very last thing in the function to be executed and there is no other operation that needs to be applied to the returned result of the function. The interpreter/compiler then optimizes the recursion by eliminating the past function call from the call stack. But in javascript, tail recursions are not recognized and are still placed into the call stack.

Trampoline

You might be asking yourself, what does this have to do with trampolines. Well, a trampoline is a helper function that helps implement tail recursion in Javascript. If you have read other articles, you might have heard words like thunk and trampolining. Thunk is usually just a function that has not been called yet. You semi see this with features such as currying and binding. In the trampoline function, we will be passing a thunk, a bound function, as an argument and through a while-loop, call their recursive functions until the variable function is not a function anymore.

function trampoline(fn) {
  while (fn && fn instanceof Function) { 
//continue if fn is not undefined/null and if it is still a
//function
    fn = fn();
  }
//we call the function and assign the result of called previous fn
//to new fn
  return fn; 
//when we are done return fn when fn is the result and no longer
//function.
}
function factorial(n) {
  var recur = function(result, n) {
    if (n === 1)
      return result;
    return recur.bind(null, result * n, n — 1);
  }
  return trampoline(recur(1, n));
}

So for computing factorial(4), I will do a little bit more of a walkthrough. In the above example, the thunk is the recur function. When we pass recur(1, n) into the trampoline function, we kind of skip a step. We are actually passing recur.bind(null, 1 * 4, 3) since we are passing the call of recur(1, 4) instead of recur(1, 4) itself. The while loop checks to see if recur is not undefined/null and if it is a function. Side note: Since recur is bounded, recur still remains as an instance of the Function object.

console.log(recur.bind(null, 1 * 4, 3)) // [Function: bound recur]

Since it passes the while loop’s two conditionals, fn is called, then reassigned to its result. Now fn is recur.bind(null, 4 *3, 2). This loop continues until recur.bind(null, 12*2, 1) is called which returns 24. 24 is not undefined/null, so it passes that condition; however, 24 is not a function which stops the loop. The trampoline function returns fn which is 24.

During this process, we never have to stack the function calls. Each function is called and returns a bound function, then is removed from the call stack. We then use the trampoline’s while loop to jump to each recursive step by calling the bound functions. Cool stuff.

This will not be needed in ES6 since tail recursion optimization will be a feature. However, I will note that it has yet to be implemented in any of the major browsers/nodejs.

This is my first technical blog. Any feedback would be greatly appreciated. Thank you for reading. Hope to write many more.