如何使延迟的嵌套函数调用结构堆栈安全？

Question

堆栈安全递归有时会产生延迟的嵌套函数调用树，一旦对其进行评估，可能会耗尽堆栈：

const compn = fs => // non-recursive to keep it simple
  fs.reduce((f, g) => comp(f) (g), x => x);

const compn_ = fs => x => // non-recursive to keep it simple
  fs.reduce((x, f) => f(x), x);

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

const inc = x => x + 1;

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

try {compn(fs) (0)}
catch (e) {
  console.log(e.message);
}

console.log(compn_(fs) (0));

我们可以避免完全建立这样的结构（compn_），但我想知道是否有较少有限的方法来处理它们：

const rec = f => (...args) => {
  let step = f(...args);
  const stack = [];

  while (step.tag !== Base) {
    stack.push(step.f);
    step = f(...step.step.args);
  }

  return x => {
    for (let i = stack.length - 1; i >= 0; i--) {
      x = stack[i] (x);

      if (x && x.tag === Base) {
        x = x.x;
        break;
      }
    }

    return x;
  }
};

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

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

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

const id = x => x;

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

const inc = x => x + 1;

const fold = f => acc => xs =>
  rec(i =>
    i === xs.length
      ? Base(acc)
      : Call(f(xs[i]) (id), Step(i + 1))) (0);
//                     ^^ works but is nonsensical

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

console.log(
  fold(f => g => comp(f) (g))
    (id)
      (fs)
        (0)); // 100000

这是可行的，但将id应用于每个递归步骤首先会破坏使用comp的目的。是否可以使用Java中的此类延迟树结构来工作，还是必须退回到线性，类似堆栈的结构？

Answer 1

使comp(inc) (comp(inc) (comp(inc) (..)))堆栈安全的一种方法是通过重新定义延续来进一步推迟执行：