Frontend Scrapbook

Notes that make a difference

Tail call optimization ( TCO ) & Trampoline

By admin

on Sat Jun 13 2020

function sumRecursive(sum,num, …nums) {
if(nums.length == 0) return sum+num;
return sum + sumRecursive(num, …nums);
}

TCO allows recursive functions to re-use the stack frame instead of creating new frames on every call.

New stack frames are created as we have more work to do ( adding to sum variable after sunRecursive return on every call )

The idea is to avoid adding to return value of call to sumRecursive once returns at make it the ‘last’ operation within the function. Instead of ‘add’ on return, value is passed to the function.

Idea is to write code in ‘Proper Tail Calls’ – PTC form spec – so that code can run in fixed memory. TCO are ways to implement this spec.

It requires the code to be written in strict-mode. As of now, only safari has implemented support for PTC.

“use strict”;

function foo(x) {
if(x < 10) return x; return bar(x) // requires to return value and at the end; }

It is allowed to use ternary operation instead of simple call to bar.

“use strict”
function sumRecursive(...nums) {
  return recur(...nums);
  function recur(sum, num, ...nums){
    sum += num;
    if(nums.length == 0) return sum;
    return recur(sum, ...nums);
  }
}

recur function is created every time we call sumRecursive. We can avoid this using IIFE.

We could even refactor above to a point-free form

“use strict”
function sumRecursive(sum, num, ...nums){
 sum += num;
 if(nums.length == 0) return sum;
 return sumRecursive(sum, ...nums);
}

sumRecursive(1,3,3,4) // 11

Trampolines is another way to get around call-stack limitation. Here idea is to return a function every-time and defer call

//simple trampoline function
function trampoline(fn) {
  return function(...args){
      let result = fn(...args);
      while(typeof result === 'function') {
          result = result();
      }
      return result;
  }
}

var sumTrampolined = trampoline(function f(sum, num, ...nums) {
  sum += num;
  if(nums.length === 0) return sum;
  return function(){ // continuation function which return sum
    return f(sum, ...nums);
  }
});

sumTrampolined(2,4); // 6