如何在严格评估的语言中实现保护递归？

Question

我在Javascript中实现了一个Scott编码的List类型以及一个模拟append类型类的重载Semigroup函数。

append工作得很好但是对于大型列表它会炸掉堆栈。这是我实施的决定性部分：

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));

通常我使用蹦床来避免不断增长的堆栈，但这预示着尾递归，因此在这种情况下不起作用。

由于这个实现是基于Haskell的，我想懒惰的评估和保护的递归/尾递归模数缺点有所不同：

(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

如果我理解正确的话，由于懒惰的评估（差不多），当我向另一个人添加一个列表时，Haskell中没有任何事情发生，直到我真正对这个新列表做了一些事情。在下面的例子中，我折叠它。

我不明白的是，保护递归如何保持递归不会增加调用堆栈以及是否可以在严格评估的语言（如Javascript）中显式实现此行为。

希望这个问题不是太宽泛。

为了更好地理解，这里是完整的实现/示例：

// type constructor

const Type = name => {
  const Type = tag => Dcons => {
    const t = new Tcons();

    Object.defineProperty(
      t,
      `run${name}`,
      {value: Dcons});

    t[TAG] = tag;
    return t;
  };

  const Tcons =
    Function(`return function ${name}() {}`) ();

  Tcons.prototype[Symbol.toStringTag] = name;
  return Type;
};


const TAG = Symbol("TAG");
const List = Type("List");


// data constructors

const Cons = x => tx => List("Cons") (cases => cases.Cons(x) (tx));
const Nil = List("Nil") (cases => cases.Nil);


// overload binary functions

const overload2 = (name, dispatch) => {
  const pairs = new Map();

  return {
    [`${name}Add`]: (k, v) => pairs.set(k, v),

    [`${name}Lookup`]: k => pairs.get(k),

    [name]: x => y => {
      if (typeof x === "function" && (VALUE in x))
        x = x(y);

      else if (typeof y === "function" && (VALUE in y))
        y = y(x);

      const r = pairs.get(dispatch(x, y));

      if (r === undefined)
        throw new TypeError("...");

      else if (typeof r === "function")
        return r(x) (y);

      else return r;
    }
  }
};


const dispatcher = (...args) => args.map(arg => {
  const tag = Object.prototype.toString.call(arg);
  return tag.slice(tag.lastIndexOf(" ") + 1, -1);
}).join("/");


// Semigroup "typeclass"

const {appendAdd, appendLookup, append} =
  overload2("append", dispatcher);


// List instance for Semigroup

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));


// fold

const foldr = f => acc => {
  const aux = tx =>
    tx.runList({
      Nil: acc,
      Cons: x => tx_ => f(x) (aux(tx_))})

  return aux;
};


// data

const tx = Cons(1) (Cons(2) (Nil));
const ty = Cons(3) (Cons(4) (Nil));
const tz = append(tx) (ty);


// run

console.log(
  foldr(x => acc => `${x}${acc}`) (0) (tz) // "12340"
);

Answer 1

这不是一个真正的答案，而是我在进一步研究后得出的结论：

1. Tail Recursion modulo Cons - TRMC（和其他操作的“modulo”）仅指严格评估的上下文，而保护递归指的是懒惰的评估上下文
2. TRMC是一种昂贵的编译器技术，它（可能）在userland中实现它是没有意义的
3. TRMC要求操作是关联的（至少形成一个半群），以便可以重新排列括号

这个问答也很有帮助：a tail-recursion version list appending function 。