如何在严格评估的语言中实施守护递归？ [英] How to implement guarded recursion in strictly evaluated languages?

问题描述

我在Javascript中实现了一个Scott编码的 List 类型，以及一个模仿<$ c>的重载的 append 函数
$ b

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。

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

为了更好理解，这里是完整的实现/例子：
$ b

// type constructorconst Type = name => {const Type = tag => Dcons => {const t = new Tcons（）; Object.defineProperty（t，`run $ {name}`，{value：Dcons}）; t [TAG] =标签;返回t; }; const Tcons = Function（`return function $ {name}（）{}`）（）; Tcons.prototype [Symbol.toStringTag] = name; const TAG = Symbol（TAG）; const List = Type（List）; // data constructorsconst Cons = x => tx => List（Cons）（cases => cases.Cons（x）（tx））; const Nil = List（Nil）（cases => cases.Nil）; //重载二进制functionsconst overload2 = ，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&&（x中的VALUE））x = x（y）; else if（typeof y ===function&&（y中的VALUE））y = y（x）; const r = pairs.get（dispatch（x，y））;如果（r === undefined）抛出新的TypeError（...）; else if（typeof r ===function）return r（x）（y）;否则返回r; }}}; const dispatcher =（... args）=> args.map（arg => {const tag = Object.prototype.toString.call（arg）; return tag.slice（tag.lastIndexOf（）+ 1，-1）;}）。join（/ ）; // Semigrouptypeclassconst {appendAdd，appendLookup，append} = overload2（append，dispatcher）; //列出SemigroupappendAdd的实例（List / List，tx => ty => tx.runList （{Nil：ty，Cons：x => tx_ => Cons（x）（append（tx_）（ty））}））; // foldconst foldr = f => acc => {const aux = tx => tx.runList（{Nil：acc，Cons：x => tx_ => f（x）（aux（tx_））}）return aux;}; // dataconst tx = Cons（1）（Cons（2） （Nil））; const ty = Cons（3）（Cons（4）（Nil））; const tz = append（tx）（ty）; // runco​​nsole.log（foldr（x => acc =>` $ {x} $ {acc}`）（0）（tz）//12340）;

解决方案

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

1. 尾递归模块缺点 - TRMC（和其他操作的模数）仅指严格评估的上下文，而守护递归指的是延迟评估的一个


2. TRMC是一种昂贵的编译器技术，它可能（在用户空间中）实现它并不合适。
   
3. TRMC要求操作是关联的（至少形成一个半群），以便圆括号可以重新排列

这个Q& A也很有帮助：一个尾巴ursion版本列表追加功能
。

I implemented a Scott encoded List type in Javascript along with an overloaded append function that mimics the Semigroup typeclass.

append works just fine but for large lists it will blow the stack. Here is the decisive part of my implementation:

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

Usually I use a trampoline to avoid a growing stack, but this presupposes tail recursion and thus won't work in this case.

Since this implementation is based on Haskell's, I guess lazy evaluation and guarded recursion/tail recursion modulo cons make the difference:

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

Provided I understand it correctly, due to lazy evaluation (almost) nothing happens in Haskell when I append a list to another, until I actually do something with this new list. In the example below I fold it.

What I don't understand is how guarded recursion can keep the recursion from growing the call stack and whether this behavior can be implemented explicitly in a strictly evaluated language like Javascript.

Hopefully this question isn't too broad.

For a better understanding, here is the full implementation/example:

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

解决方案

This isn't a real answer but conclusions I drew after further study:

1. Tail Recursion modulo Cons - TRMC (and "modulo" for other operations) refers only to a strictly evaluated context, whereas guarded recursion refers to a lazy evaluated one
2. TRMC is an expensive compiler technique and it (probably) doesn't make sense to implement it in userland
3. TRMC requires the operation to be associative (form at least a Semigroup), so that the parentheses can be rearranged

This Q&A is also helpful: a tail-recursion version list appending function .

这篇关于如何在严格评估的语言中实施守护递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！