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

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的目的。有没有办法在Javascript中使用这种延迟的树结构，或者我们必须退回到线性的、类似堆栈的结构？

Answer 1

使comp(inc) (comp(inc) (comp(inc) (..)))堆栈安全的一种方法是通过实例化continuation来进一步推迟执行：

​

const Cont = k => ({tag: "Cont", k});

const compk = f => g => x =>
  Cont(k => k(f(g(x))));

const compn = fs =>
  fs.reduce((f, g) => compk(f) (g), x => x);

const id = x => x;

const inc = x => x + 1;

const postRec = cont => {
  do {
    cont = cont.k(id);
  } while (cont && cont.tag === "Cont")

  return cont;
};

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

const main = compn(fs) (0);

console.log(
  postRec(main));

​

现在，结构的每个嵌套级别的处理被推迟，并在跳床内执行。我称之为postRec，因为它是在原始递归算法完成其工作之后运行的。不过，我不知道这种方法是否普遍足够有用。