进行嵌套/递归计算时如何运行事件循环？

Question

如何使用settimeout（）打破计算和发布的通常示例似乎依赖于具有浅（1深）调用堆栈的示例。 但是，当您进行深度嵌套或相互恢复的计算（例如树木搜索）时，堆栈中有很多上下文呢？

如果JavaScript具有将“当前延续”封装（即：当前的呼叫堆栈），将其放在事件队列中，然后 return/throw/call返回到顶级事件的函数，那将是理想的选择。循环。 （因此其他事件将运行，然后计算将在其停止的位置重新启动）。我正在寻找一种简单的方法来自愿'屈服'控制，让事件赶上，然后返回控制，然后返回到我们关闭的位置。最好不要重写呼叫链中的每个功能。

但是我找不到任何可以做到这一点的东西...

• 作为退休的计划，我期望呼叫/CC之类的东西，但找不到。
• settimeout（）将返回控制[但只有1个级别]，然后重新启动一些其他计算（而不是隐式电流 - 登机仪，除非我们将整个应用程序提交给CPS ...）
• “收益率”将限制当前功能/堆栈框架的延续，因此可以重新启动， 但是收益率只能返回一个水平。 （收益率类似：返回/CC vs呼叫/CC）
• “投掷”可以将堆栈扔掉，但没有设施可以重新启动 从投掷点开始的计算（我知道；需要诸如'throw/cc'之类的东西），

我使用“屈服”构建了一个半解决方案，但它是klutzy，需要堆栈上的每个功能）被声明为“函数*”，并且（b）在每个调用周围都包含样板代码，以下到下一个功能[以传播收益率并重新启动下一个（）]

q：有没有办法在JavaScript中实现此目标而无需仪器呼叫链上的功能？

Answer 1

我将添加您似乎没有考虑过的替代解决方案：Promise s。或更具体地说，要处理承诺的语法糖：async/等待。

实现您的allowEventloop（）函数很

function allowEventLoop () {
    return new Promise((ok,fail) => setTimeout(ok,0));
}

使用Promise ，

await allowEventLoop();

容易使用上述函数的简单递归下降解析器的示例（注意：js中的代码，但在ts中执行此操作应该很微不足道）：

async function drawTree(node, indent) {
    if (!indent) indent = 0;

    let tree = `${'\t'.repeat(indent)}${node.name}\n`;

    await allowEventLoop();

    if (node.children) {
        for (let child of node.children) {
            tree += await drawTree(child, indent+1);
        }
    }

    return tree;
}

如您所见，在递归函数的逻辑中，几乎没有更改。它看起来几乎与普通同步版本完全相同。主要区别是您的功能现在返回结果的Promise。

使用async/等待时，您基本上会跳过呼叫堆栈。相反，您真正在做的是使用的链。然后使用（）调用。因此，实际上，呼叫堆栈仍然是1级深的，但是您正在动态构建复杂的。然后（）（）链条。在实践中，感觉就像是通常的基于呼叫堆栈的递归。

要执行的功能的队列被承诺无形地处理 - 这实际上是处理持续通信风格（CPS）代码的设计模式。这类似于调用堆栈如何管理函数返回的队列。这就是为什么感觉一样的原因。

Answer 2

我们希望在长期运行，相互递归的功能调用中启用事件处理。
（例如，递归树搜索）
一定深度或时间后，搜索希望自愿暂停执行
为了允许最高级别事件循环运行（处理鼠标/关键事件，重新绘制图形等），

理想将是runeventloop（）的系统级函数
哪个“产生”当前计算，将其自身延续在事件队列中，
并将控制权控制到系统eventloop。

JavaScript似乎仅为此提供部分解决方案：

• “ Settimeout（）”将在事件队列（但不是当前的延续）
• “收益率”中放置一个功能，而不会将当前延续暂停，但不要将其放在事件队列中。
  并且“收益率”将一个值返回到发电机的呼叫者一个级别上的一个级别。
  因此，呼叫者必须以发电机的形式具有“延续”。

我们还注意到，尽管未被发现的“投掷”会返回到顶级的控制权，但
JS中没有办法（tiko）恢复＆amp;重新启动“投掷”计算。
（从最高级别到相互追回的呼叫到自愿的“产量”）

So：从自愿产量中返回控制，
通过嵌套或相互重新恢复的函数，
一直到系统eventloop，我们执行3件事：

1. 每个功能[呼叫者＆amp;必须将]声明为函数*（以便可以产生）
2. 每个功能[呼叫者]必须测试其[调用]后代是否被暂停，
   如果是这样，则屈服将“产量”传播到最高级别：

    let result, genR = calledStarFunction(args);
       while (result = genR.next(), !result.done) yield;
       use (result.value)

注意：＃2不能用用途包装在功能中...因为该功能将受到＃1的约束，并且 受＃2的约束

3. 的呼叫者函数在顶级处 ，使用settimeout（（）=＆gt; genr.next（））返回JS Eventloop
   然后重新启动悬浮函数的链。

[在＃2显而易见之前，我编写了这个打字稿代码，如上所示，现在“ fardry”被列为

    /** <yield: void, return: TReturn, yield-in: unknown> */
    export type YieldR<TReturn> = Generator<void, TReturn, unknown>
    /**
     * Top-level function to give control to JS Event Loop, and then restart the stack of suspended functions.
     * 'genR' will restart the first/outermost suspended block, which will have code like *yieldR()
     * that loops to retry/restart the next/inner suspended function.
     * @param genR 
     * @param done 
     */
    export function allowEventLoop<T>(genR: YieldR<T>, done?: (result: T) => void): void  {
      let result = genR.next()
      if (result.done) done && done(result.value)
      else setTimeout(() => allowEventLoop(genR, done))
    }
    /** 
     * Return next result from genR. 
     * If genR returns an actual value, return that value
     * If genR yields<void> then propagate a 'yield' to each yieldR up to allowEventLoop(); 
     * 
     * This shows the canonical form of the code.
     * It's not useful to actually *call* this code since it also returns a Generator,
     * and the calling code must then write a while loop to handle the yield-vs-return!
     */
    export function* yieldR<T extends object> (genR: YieldR<T>, log?:string) {
      let result: IteratorResult<void, T>
      while (result = genR.next(), !result.done) yield
      return result.value
    }

'
“收益率”提供了有趣/有用的值，并且完成后“返回”信号。
在这个被反转的用例中：产量发出信号，但没有有趣的值，
“返回”提供有趣的计算值。

吸引JS神：
提供一个函数：runeventloop（）
透明地将当前延续（完整堆栈）放在事件循环中
并将控制直接返回到顶级。
因此，所有其他来电者和呼叫堆栈
不需要意识到较低级别的暂停/简历。

值得注意的：看来使用这样的发电机有重大的性能。将代码插入以将嵌套发生器从4减少到2后，代码速度更快地运行10倍。因此，也许可以针对复杂/时间敏感的应用程序指示CPS或数据流设计。 （但是，它在开发/调试期间起作用以使KBD/图形进行运行）

另一个注意事项： Chrome施加了最小的“ Settimeout”延迟4ms；因此，如果您计算为1ms，然后以4ms的速度屈服，则可以解释上面的注释。它有助于计算三角洲的最后一个产量到date.now（），并且仅在大于[20-200 ms？]的情况下（取决于您需要的响应程度）。

Answer 3

要重新替代替代方法（数据流/函数 - 标题），请考虑以下方式：
为了保持呼叫堆栈的简短，请将应用程序划分为任务（无递归返回的函数）。
如果您要进行递归调用，则使用：calllater（（）=＆gt; recursivetask（arg1，arg2，...）））
并简单地返回。
call-later将闭合[数据和延续]放在queue上，顶级可以依次对其进行处理。

因此，对于树搜索，在第n层，您会招募任务以在n+1层处处理节点，并加上一个任务来收集和组合结果，然后返回。最终的任务应返回最终结果。该“最终”任务可能包括：if（queue.length＆gt; 0）calllater（finalTask​​），因此它将自己放在队列的末端，直到计算出所有其他子任务，并且已经停止将任务添加到队列中。 [或者，也许您使用一些承诺，并使用finalTask​​ promise.all（...）]

下面的代码还包括循环中的计时器，以便运行许多任务，直到超过阈值（以及返回JavaScript事件循环）

type FUNC<T> = ()=>T
const callQueue: Array<FUNC<any>> = []
function callLater(fun: FUNC<any>) {
  callQueue.push(fun)
}
function topLevel<T>(start: FUNC<T>, done?: (value: T) => void, threshold = 30, ms0 = Date.now()) {
  var dms: number
  while ((dms = Date.now() - ms0) < threshold) {
    let value = start()    // which may invoke callLater() to enqueue more tasks
    if (callQueue.length == 0) return done && done(value)
  }
  setTimeout(() => topLevel(callQueue.shift(), done, threshold))
}