javascriptrecursionfunctional-programmingcompiler-optimizationtailrecursion-modulo-cons

Can we implement tail recursion modulo cons et al. through trampolines?

You can regard trampolines as compiler optimizations reified in the program. So what is stopping us from adapting more general optimization techniques in exactly the same manner.

Here is a sketch of tail recursion modulo cons:

const loop = f => {
  let step = f();

 while (step && step[step.length - 1] && step[step.length - 1].type === recur) {
    let step_ = step.pop();
    step.push(...f(...step_.args));
  }

  return step;
};

const recur = (...args) =>
  ({type: recur, args});

const push = (xs, x) => (xs.push(x), xs);

const map = f => xs =>
  loop((i = 0) =>
    i === xs.length
      ? []
      : push([f(xs[i])], recur(i + 1)));

const xs = 
  map(x => x * 2) (Array(1e6).fill(0).map((x, i) => i))
  .slice(0,5);

console.log(xs); // [0, 2, 4, 6, 8]

This kind of optimization depends on the associativity property of an expression. Multiplication is associative too and hence there is tail recursion modulo multiplication. However, I have to cheat to implement it in Javascript:

const loop = f => {
  let step = f();
  const acc = [];

  while (step && step[1] && step[1].type === recur) {
    acc.push(step[0]);
    step = f(...step[1].args);
  }

  return acc.reduce((acc, f) => f(acc), step);
};

const recur = (...args) =>
  ({type: recur, args});

const mul = x => step => [y => x * y, step];

const pow = (x_, n_) =>
  loop((x = x_, n = n_) =>
    n === 0 ? 1
    : n === 1 ? x
    : mul(x) (recur(x, n - 1)));
    
console.log(
  pow(2, 1e6)); // Infinity, no stack overflow

As you can see I cannot use a regular mul, which isn't particular satisfying. Is this connected with Javascript beeing a strict language? Is there a better way to achieve tail recursion modulo multiplication in JS without having to introduce awkward binary operators?

Solution

  • Instead of using loop/recur (which I consider an ugly and unnecessary hack), consider using folds:

    const recNat = (zero, succ) => n => {
    let result = zero;

    while (n > 0) {
        result = succ(result);
        n = n - 1;
    }

    return result;
};

const mul = x => y => x * y;

const pow = x => recNat(1, mul(x));

console.log([0,1,2,3,4,5,6,1e6].map(pow(2))); // [1,2,4,8,16,32,64,Infinity]

    Almost every recursive function can be defined using folds (a.k.a. structural recursion, a.k.a. induction). For example, even the Ackermann function can be defined using folds:

    const recNat = (zero, succ) => n => {
    let result = zero;

    while (n > 0) {
        result = succ(result);
        n = n - 1;
    }

    return result;
};

const add = x => y => x + y;

const ack = recNat(add(1),
    ackPredM => recNat(ackPredM(1),
        ackMPredN => ackPredM(ackMPredN)));

console.time("ack(4)(1)");
console.log(ack(4)(1)); // 65533
console.timeEnd("ack(4)(1)");

    The above code snippet takes about 18 seconds to compute the answer on my laptop.

    Now, you might ask why I implemented recNat using iteration instead of natural recursion:

    const recNat = (zero, succ) => function recNatZS(n) {
    return n <= 0 ? zero : succ(recNatZS(n - 1));
};

    I used iteration for the same reason you used iteration to implement loop. Trampolining. By implementing a different trampoline for every data type you're going to fold, you can write functional code without having to worry about stack overflows.

    Bottom line: Use folds instead of explicit recursion. They are a lot more powerful than you think.