When you think your functional code is stack safe

Recursion is a functional primitive and thus we try to avoid it, because ultimately it is only a nasty imperative loop in disguise. In FP we usually use folds and only resort to recursion if folding is not expressive enough.

In Javascript we additionally need to take care of stack-safety. It is therefore a smart strategy to implement folds with specific trampolines suitable for each type:

// Foldable

const arrFold = f => init => xs => {
  let acc = init;

  for (let i = 0; i < xs.length; i++) // trampoline
    acc = f(acc) (xs[i], i);

  return acc;
};

// identity

const id = x => x;

// function composition

const comp = f => g => x => f(g(x));

const compn = arrFold(comp) (id); // variadic

// MAIN

const inc = x => x + 1;

compn([inc, inc, inc, inc, inc]) (0); // 5

run code

You may think yourself safe with arrFold being implemented as a stack-safe trampoline. However, you are not:

// MAIN

const inc = x => x + 1;

const xs = Array(1e5).fill(inc);

const foo = compn(xs); // still okay

foo(0); // stack overflow

run code

Composing means to combine two functions to a description of a new function, which is only evaluated if the required argument is provided. So iteratively composing builds up a huge description of descriptions waiting to be run.

What can we do about it? We need a way to break the composition apart. We've already used trampolines. It seems to be the proper tool:

// trampoline for deferred function call trees

const postRec = f => (...args) => {
  let step = f(...args);

  while (step.tag !== "Base")
    step = f(...step.args);

  return init => {
    let {f, x} = step.x(init);

    while (step = f(x)) {
      if (step && step.tag === "Call") {
        step = step.f(step.x);

        if (step && step.tag === "Call") {
          ({f, x} = step);
          continue;
        }

        else break;
      }

      else break;
    }

    return step;
  }
};

const Base = x =>
  ({tag: "Base", x});

const Call = f => x =>
  ({tag: "Call", f, x});

const Step = (...args) =>
  ({tag: "Step", args});

// function composition

const comp = f => g => x => f(g(x));

const compn = xs => // variadic
  postRec((i, acc) =>
    i === xs.length
      ? Base(acc)
      : Step(i + 1, Call(comp(acc) (xs[i]))))
        (0, Call(id));

// MAIN

const inc = x => x + 1;

const xs = Array(1e5).fill(inc);

compn(xs) (0); // 100000

run code

postRec isn't a beauty. It reveals all its ugly operational semantics. Javascript was never about beauty but to get things done, I guess.

Anayway, in FP we often have to deal with descriptions of computations that create huge deferred function call trees. Having a specialized trampoline at our disposal allows us to get serious about FP in JS.

If you want to learn more about FP in JS take a look at my course on Github.

Comments

[Functional Javascript]

Interesting analysis Iven.

Is there any reason you wouldn't just do this?...

const pipe = (...fns) => v => fns.reduce((r, fn) => fn(r), v);

const inc = x => x + 1;
const aFns = Array(1e5).fill(inc); //arr of funcs

console.log(pipe(...aFns)(0)); //100000

[Iven Marquardt]

No, you missed the whole point of the post! In order to keep your code pure while working with data bases, local storage, file systems, random numbers, dates etc. you need to defer the impure computations. You do that by merely describing them. This may lead to stack overflows as I demonstrated with the contrived example above.

[Functional Javascript]

You've lost me there.

Could you give me an example of where my code above would throw a RangeError (stack overflow)?

[Iven Marquardt]

No offence, but I can't help ya. I wasn't talkin about your exmaple, because it doesn't make any sense in the context of my post. You built a variadic applicator, which is dual to function composition. You cannot compare function application f => x => f(x) with composition f => g => x => f(g(x)). Both have completely different operational semantics.

[Functional Javascript]

Sounds pretty deep in the academics. ;)

When building applications I test if the behavior is robust and if it's performant and achieves the desired result.

Good luck.