我们可以实现尾递归模 cons 等吗？通过蹦床？

Question

你可以把trampolines看作是程序中具体化的编译器优化。那么是什么阻止我们以完全相同的方式采用更通用的优化技术。

这是尾递归模缺点的草图：

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]

这种优化取决于表达式的结合性属性。乘法也是结合的，因此存在尾递归模乘法。但是，我必须作弊才能在 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

如您所见，我不能使用常规 mul，这不是特别令人满意。这与 Javascript beeing a strict language 有关吗？有没有更好的方法在 JS 中实现尾递归模乘而不引入笨拙的二元运算符？

Answer 1

不要使用 loop/recur（我认为这是一种丑陋且不必要的 hack），而是考虑使用折叠：

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]

几乎每个递归函数都可以使用折叠定义（a.k.a。结构递归，a.k.a。归纳）。例如，甚至 Ackermann function 也可以使用折叠来定义：

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)");

以上代码片段在我的笔记本电脑上计算答案大约需要 18 秒。

现在，您可能会问为什么我使用迭代而不是自然递归来实现 recNat：

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

我使用迭代的原因与您使用迭代实现 loop 的原因相同。蹦床。通过为您要折叠的每种数据类型实现不同的蹦床，您可以编写功能代码而不必担心堆栈溢出。

底线：使用折叠而不是显式递归。他们比你想象的要强大得多。

我们可以实现尾递归模 cons 等吗？通过蹦床？

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

javascript

recursion

functional-programming

compiler-optimization

tail-recursion