Búsqueda de sitios web

javascript - ¿Cómo ejecutar el bucle de eventos al realizar cálculos anidados/recursivos?

Los ejemplos habituales de cómo interrumpir un cálculo y liberar usando setTimeout() parecen depender de tener una pila de llamadas superficial (de 1 nivel). Pero, ¿qué pasa cuando estás realizando un cálculo profundamente anidado o recursivo-mutuo (como una búsqueda en árbol) y tienes mucho contexto en la pila?

Sería ideal que JavaScript tuviera una función que encapsulara la 'continuación actual' (es decir: la pila de llamadas actual), la pusiera en la Cola de Eventos y devuelva/lance/llame de nuevo al bucle de eventos de nivel superior. (para que otros eventos se ejecuten y luego la computación se reanude justo donde se quedó). Estoy buscando una manera fácil de que una función voluntariamente 'ceda' el control, deje que los eventos se pongan al día y luego devuelva el control a donde lo dejamos. Preferiblemente sin reescribir cada función en la cadena de llamadas.

Pero no puedo encontrar nada que haga esto...

  • Como un planificador retirado, estoy esperando algo como call/cc, pero no lo encuentro.
  • setTimeout() devolverá el control [pero solo un nivel hacia arriba], y reanudará algún otro cálculo distinto (pero no la continuación implícita actual, a menos que comprometamos toda la aplicación a CPS...)
  • 'yield' encapsulará la continuación de la función/marco de pila actual, para que pueda reiniciarse, pero yield solo retorna un nivel hacia arriba. (yield es como: return/cc vs call/cc)
  • 'throw' puede lanzar muy arriba en la pila, pero no tiene la capacidad de reiniciar el cálculo desde el punto del throw (que yo sepa; necesito algo como 'throw/cc')

He construido una semi-solución usando 'yield', pero es torpe, requiriendo que cada función en la pila (a) sea declarada como 'function*' y (b) incluya código repetitivo alrededor de cada llamada a la siguiente función [para propagar un yield y reiniciar con next()]

P: ¿Existe una manera de lograr esto en JavaScript sin instrumentar todas las funciones en la cadena de llamadas?

Respuesta #1

Agregaré una solución alternativa que parece que no has considerado: Promises. O más específicamente, el azúcar de sintaxis para manejar promesas: async/await.

Usando un Promise es sencillo implementar tu función allowEventLoop():

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

Ahora, cada vez que necesites suspender la computación actual y ejecutar el bucle de eventos, solo necesitas llamar a:

await allowEventLoop();

Aquí hay un ejemplo de un analizador descendente recursivo simple usando la función anterior (nota: el código está en Js pero debería ser trivial hacerlo en 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;
}

Como puedes ver, muy poco ha cambiado en la lógica de la función recursiva. Se ve casi exactamente igual que la versión síncrona sencilla. La principal diferencia es que tu función ahora devuelve una Promise del resultado.

Al usar async/await básicamente saltas la pila de llamadas. En su lugar, lo que realmente estás haciendo es usar una cadena de llamadas .then(). Así que, en realidad, la pila de llamadas sigue siendo de 1 nivel, pero estás construyendo dinámicamente una cadena complicada de .then(). En la práctica, se siente como la recursión habitual basada en la pila de llamadas.

La cola de funciones a ejecutar es manejada de forma invisible por las Promesas, lo cual es esencialmente un patrón de diseño para manejar código en Estilo de Paso de Continuación (CPS). Esto es similar a cómo la pila de llamadas gestiona la cola de funciones a retornar. Por eso se siente igual.

Respuesta #2

Queremos habilitar el procesamiento de eventos durante llamadas de función recursivas mutuamente prolongadas. (por ejemplo, una búsqueda recursiva en un árbol) Después de cierta profundidad o tiempo, la búsqueda quiere suspender voluntariamente la ejecución para permitir que el Event Loop de nivel superior se ejecute (manejar eventos del mouse/teclado, repintar gráficos, etc.)

Lo ideal sería una función a nivel de sistema runEventLoop() que 'ceda' la computación actual, ponga su propia continuación en la cola de eventos y pase el control al EventLoop del sistema.

Parece que Javascript solo proporciona soluciones parciales para esto:

  • 'setTimeout()' pondrá una función en la cola de eventos [pero no en la continuación actual]
  • 'yield' suspenderá la continuación actual, pero no la pondrá en la cola de eventos. Y 'yield' devuelve un valor al llamador del Generador un nivel arriba en la pila de llamadas. Así que ese llamador ya debe tener la 'continuación' en forma del Generador.

También observamos que, aunque un 'throw' no capturado devolverá el control al nivel superior, no hay manera (TIKO) en JS de recuperar y reiniciar el cálculo 'lanzado'. (desde el nivel superior a través de las llamadas mutuamente recursivas hasta el 'yield' voluntario)

Entonces: para devolver el control desde la cesión voluntaria, a través de las funciones anidadas o recursivas mutuamente, hasta el EventLoop del sistema, hacemos 3 cosas:

  1. Cada función [llamante y llamada] debe ser declarada como function* (para que pueda usar yield)
  2. Cada función [llamante] debe verificar si su descendiente [llamado] se suspendió y, de ser así, ceder su control para propagar el 'yield' hasta el nivel superior:
    let result, genR = calledStarFunction(args);
       while (result = genR.next(), !result.done) yield;
       use (result.value)

Nota: #2 no se puede envolver útilmente en una función... porque esa función estaría sujeta a #1, y el llamador de esa función está sujeto a #2

  1. A nivel superior, use setTimeout(() => genR.next()) para volver al bucle de eventos de JS y luego reiniciar la cadena de funciones suspendidas.

[antes de que #2 fuera obvio, escribí este código TypeScript, ahora 'yieldR' está en línea, como se muestra arriba]

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

Nota: el uso documentado más común de function* es para crear un Iterador, un caso en el que 'yield' proporciona el valor interesante/útil, y 'return' indica cuándo se ha terminado. En este caso de uso eso está invertido: yield da una señal, pero ningún valor interesante, y 'return' proporciona el valor computacional interesante.

Apelación a los Dioses de JS: Proporcione una función: runEventLoop() que coloque de manera transparente la continuación actual (la pila completa) en el bucle de eventos y devuelva el control directamente al nivel superior, de modo que todos los demás llamadores y la pila de llamadas no necesiten ser conscientes de la suspensión/reanudación que se realiza en el nivel inferior.

Nota posterior: parece que hay una disminución significativa en el rendimiento al usar Generadores de esta manera. Después de insertar el código para reducir los Generadores anidados de 4 a 2, el código se ejecutó 10 veces más rápido. Así que tal vez se indique el diseño CPS o de flujo de datos para aplicaciones complejas/sensibles al tiempo. (pero aun así, funcionó durante el desarrollo/depuración para poner en marcha el teclado/gráficos)

Otra nota: Chrome impone un retraso mínimo de 'setTimeout' de 4 ms; así que si calculas durante 1 ms y luego cedes durante 4 ms, eso es lento y puede explicar la nota anterior. Ayuda calcular el delta desde la última cesión hasta Date.now() y ceder solo cuando eso sea mayor que [20 -- 200 ms?] (dependiendo del grado de capacidad de respuesta que necesites).

Artículos relacionados