如何在进行 nested/recursive 计算时运行事件循环？

Question

如何使用 setTimeout() 中断计算和释放的常见示例似乎依赖于浅（1 深）调用堆栈。但是，当您进行深度嵌套或相互递归计算（如树搜索）并且堆栈中有大量上下文时怎么办？

如果JavaScript有一个函数可以封装'current continuation'（即：当前调用堆栈），将其放入事件队列和，那将是理想的return/throw/call回到顶层事件循环。（所以其他事件会运行，然后计算会在它停止的地方重新开始）。我正在寻找一种简单的方法来让函数自愿 'yield' 控制，让事件赶上，然后 return 控制到我们离开的地方。最好不要重写调用链中的每个函数。

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

作为一名退休的阴谋家，我期待 call/cc，但没有找到。
setTimeout() 将 return 控制 [但仅向上 1 级]，并重新启动一些 other 计算（但不是隐式电流延续，除非我们将整个申请提交给 CPS...)
'yield'会框住当前function/stack-frame的延续，所以可以重新开始，但只产生 returns 一级。（产量就像：return/cc vs call/cc）
'throw' 可以向上抛出堆栈，但无法重新启动从投掷点开始的计算（据我所知；需要类似 'throw/cc'）

我已经使用 'yield' 构建了一个半解决方案，但它很笨拙，要求堆栈上的每个函数 (a) 声明为 'function*' 并且 (b) 包含样板代码围绕每次调用下一个函数[传播收益并使用 next() 重新启动]

问：有没有一种方法可以在 JavaScript 中实现这一点，而无需检测调用链上的所有函数？

Answer 1

我们希望在 long-running 期间启用事件处理，相互递归函数调用。（例如，递归树搜索）一定深度或时间后，搜索想主动暂停执行允许顶级事件循环运行（处理 mouse/key 事件、重绘图形等）

理想的是 system-level 函数到运行EventLoop() 'yield' 当前计算，将其自己的延续放在事件队列中，并将控制权交给系统 EventLoop。

Javascript似乎只提供了部分解决方案：

'setTimeout()' 会将函数放入事件队列[但不是当前延续]
'yield' 会暂停当前的继续，但不会将其放入事件队列。并且 'yield' return 是生成器调用者在调用堆栈上一级的值。因此，调用者必须已经具有生成器形式的 'continuation'。

我们还注意到，虽然未捕获的 'throw' 会 return 控制 top-level， JS 中无法 (TIKO) 恢复并重新启动 'thrown' 计算。（从顶层通过 mutually-recursive 调用到自愿 'yield'）

所以：要return控制自发的yield，通过嵌套或 mutually-recursive 函数，一直到系统 EventLoop，我们做了 3 件事：

每个函数 [caller & called] 必须声明为函数*（这样它就可以产生）
每个函数 [caller] 必须测试它的 [called] 后代是否挂起，如果是这样，让自己传播 'yield' 到顶层：

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

注意：#2 不能有用地包装在函数中...因为该函数将受制于#1，而 的调用者 函数受制于#2

在top-level处，使用setTimeout(() => genR.next())return到JS EventLoop 然后重新启动挂起的函数链。

[之前 #2 很明显，我写了这个 typescript 代码，现在 'yieldR' 是内联的，如上图]

    /** <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
    }

注意： 大多数记录在案的函数用法* 是创建迭代器，这种情况下 'yield' 提供 interesting/useful 值，并在完成时发出 'return' 信号。在这个倒置的 use-case 中： yield 给出了一个信号，但没有有趣的值， 'return' 提供有趣的计算值。

呼吁JS大神： 提供一个函数：运行EventLoop() t运行sparently 将当前的延续（完整堆栈）放在事件循环中 returns 直接控制 top-level。所以所有其他调用者和调用堆栈不需要知道在较低级别完成的 suspend/resume。

注后： 看起来像这样使用生成器会显着降低性能。内联代码以将嵌套生成器从 4 个减少到 2 个之后，代码运行速度提高了 10 倍。因此，可能会为 complex/time-sensitive 个应用指示 CPS 或 data-flow 设计。（但它仍然在 dev/debug 期间发挥作用，使 kbd/graphics 继续进行）

另一个注意事项： Chrome 强加最小 'setTimeout' 4 毫秒的延迟；因此，如果您计算 1 毫秒，然后计算 4 毫秒，这很慢并且可以解释上面的注释。它有助于计算从最后一次产量到 Date.now() 的增量，并且仅当它大于 [20 -- 200 毫秒？] 时才产量（取决于您需要的响应程度）。

Answer 2

要具体化替代 (data-flow/function-queue) 方法，请考虑：为了保持 call-stack 简短，将应用程序划分为任务（return 没有递归的函数）。如果您要进行递归调用，则改为使用：callLater(()=>recursiveTask(arg1, arg2, ...)) 并且只是 return。 callLater 将闭包 [data and continuation] 放在 queue 上，top-level 可以依次处理它。

因此对于树搜索，在第 N 层，您将任务排入队列以处理第 N+1 层的节点，再加上一个收集和组合结果的任务，然后 return。最后排队的任务应该 return 最终结果。该 'final' 任务可能会包含如下内容： if (queue.length > 0) callLater(finalTask) 因此它将自己置于队列的末尾，直到计算完所有其他子任务并停止向队列中添加任务。 [或者您可能使用一些 Promise 并使用 Promise.all(...)]

触发 finalTask

下面的代码还在循环中包含一个计时器，以便运行一些任务直到超过阈值（以及 return 到 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))
}

Answer 3

我将添加一个您似乎没有考虑过的替代解决方案：Promises。或者更具体地说，用于处理承诺的语法糖：async/await.

使用 Promise 很容易实现 allowEventLoop() 功能：

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

现在，每当您需要暂停当前计算和运行事件循环时，您只需调用：

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;
}

如您所见，递归函数的逻辑几乎没有变化。它看起来与普通的同步版本几乎完全一样。主要区别在于您的函数现在 return 是结果的 Promise。

当使用 async/await 时，您基本上跳过了调用堆栈。相反，您真正在做的是使用一系列 .then() 调用。所以实际上调用堆栈仍然是 1 级深，但你正在动态构建一个复杂的 .then() 链。在实践中，感觉就像通常的基于调用堆栈的递归。

要执行的函数队列由 Promises 无形地处理 - 这本质上是一种处理 Continuation-Passing-Style (CPS) 代码的设计模式。这类似于调用堆栈管理 return 函数队列的方式。这就是为什么感觉一样。

如何在进行 nested/recursive 计算时运行事件循环？

How to run event loop when doing nested/recursive computations?

javascript

yield

generator

typescript

如何在进行 nested/recursive 计算时 运行 事件循环？

How to run event loop when doing nested/recursive computations?

javascript

yield

generator

typescript

如何在进行 nested/recursive 计算时运行事件循环？