javascript - Hvordan kjøre hendelsesløkke når man gjør nestede/rekursive beregninger?

De vanlige eksemplene på hvordan man kan bryte en beregning og frigjøre ved bruk av setTimeout() ser ut til å være avhengig av å ha en grunn (1-dyp) kallstabel. Men hva med når du utfører en dypt nestet eller gjensidig rekursiv beregning (som et tresøk) og du har mye kontekst i stabelen?

Det ville vært ideelt om JavaScript hadde en funksjon som kunne kapsle inn den 'nåværende kontinum' (det vil si: den nåværende kall-stakken), legge den på hendelseskøen og returnere/kaste/tilbakekalle til top-nivå hendelsessløyfe. (slik at andre hendelser kunne kjøre, og deretter ville beregningen bli startet på nytt akkurat der den sluttet). Jeg leter etter en enkel måte for en funksjon å frivillig 'overgi' kontroll, la hendelser ta igjen, og deretter returnere kontrollen til der vi slapp. Helst uten å måtte omskrive hver funksjon i kallkjeden.

Men jeg kan ikke finne noe som gjør dette...

  • Som en pensjonert schemer, forventer jeg noe som call/cc, men finner det ikke.
  • setTimeout() vil returnere kontroll [men bare 1 nivå opp], og starte noen andre beregninger (men ikke den implisitte nåværende-kontinuasjonen, med mindre vi forplikter hele applikasjonen til CPS...)
  • 'yield' vil pakke inn fortsettelsen av den nåværende funksjonen/stakk-rammen, slik at den kan startes på nytt, men yield returnerer bare ett nivå opp. (yield er som: return/cc vs call/cc)
  • 'throw' kan kaste langt opp i stakken, men har ingen mulighet til å gjenoppta beregningen fra punktet der throw skjedde (så vidt jeg vet; trenger noe som 'throw/cc')

Jeg har bygget en semi-løsning ved å bruke 'yield', men den er klossete, og krever at hver funksjon i stakken (a) deklareres som 'function*' og (b) inkluderer standardkode rundt hvert kall ned til neste funksjon [for å propagere en yield og starte på nytt med next()]

Spørsmål: Finnes det en måte å oppnå dette på i JavaScript uten å instrumentere alle funksjonene i kallkjeden?

Svar #1

Jeg vil legge til en alternativ løsning som du ser ut til å ikke ha vurdert: Promises. Eller mer spesifikt syntakssukkeret for håndtering av promises: async/await.

Ved å bruke en Promise er det enkelt å implementere din allowEventLoop()-funksjon:

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

Nå, hver gang du trenger å sette den nåværende beregningen på pause og kjøre hendelsesløkken, trenger du bare å kalle:

await allowEventLoop();

Her er et eksempel på en enkel rekursiv nedstigningsparser som bruker funksjonen ovenfor (merk: kode i Js, men det bør være trivielt å gjøre dette i 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;
}

Som du kan se, er det veldig lite som er endret i logikken til den rekursive funksjonen. Den ser nesten helt lik ut som den vanlige synkrone versjonen. Hovedforskjellen er at funksjonen nå returnerer et Promise av resultatet.

Når du bruker async/await hopper du egentlig over kallestakken. Det du egentlig gjør er å bruke en kjede av .then()-kall. Så i realiteten er kallestakken fortsatt 1-nivå dyp, men du konstruerer dynamisk en komplisert .then()-kjede. I praksis føles det som vanlig rekursjon basert på kallestakken.

Køen av funksjoner som skal utføres håndteres usynlig av Promises - som i hovedsak er et designmønster for håndtering av Continuation-Passing-Style (CPS) kode. Dette ligner på hvordan kallstakken håndterer køen av funksjoner som skal returnere. Dette er grunnen til at det føles likt.

Svar #2

Vi ønsker å muliggjøre hendelsesbehandling under langvarige, gjensidig rekursive funksjonskall. (for eksempel en rekursiv tre-søk) Etter en viss dybde eller tid ønsker søket å frivillig suspendere utførelsen for å la toppnivå Event Loop kjøre (håndtere muse-/tastaturhendelser, tegne grafikk på nytt, osv)

Det ideelle ville være en systemnivåfunksjon runEventLoop() som 'gir fra seg' den nåværende beregningen, legger sin egen fortsettelse i hendelseskøen, og overfører kontrollen til systemets EventLoop.

Det ser ut til at Javascript bare gir delvise løsninger for dette:

  • 'setTimeout()' vil legge en funksjon på hendelseskøen [men ikke på den nåværende fortsettelsen]
  • 'yield' vil suspendere den nåværende continuasjonen, men ikke sette den i hendelseskøen. Og 'yield' returnerer en verdi til Generatorens oppringer ett nivå opp i kallestakken. Så den oppringeren må allerede ha 'continuation' i form av Generatoren.

Vi bemerker også at selv om en ufanget 'throw' vil returnere kontroll til toppnivå, finnes det ingen måte (TIKO) i JS for å gjenopprette og starte på nytt den 'kastede' beregningen. (fra toppnivå gjennom de gjensidig rekursive kallene til den frivillige 'yield')

Så: for å returnere kontroll fra den frivillige overgivelsen, opp gjennom de nestede eller gjensidig rekursive funksjonene, hele veien til systemets EventLoop, gjør vi 3 ting:

  1. Hver funksjon [kaller og kalt] må deklareres som function* (slik at den kan yield)
  2. Hver funksjon [caller] må teste om dens [called] etterkommer ble suspendert, og i så fall gi fra seg kontroll for å spre 'yield' til toppnivå:
    let result, genR = calledStarFunction(args);
       while (result = genR.next(), !result.done) yield;
       use (result.value)

Merk: #2 kan ikke nyttig innkapsles i en funksjon... fordi den funksjonen ville være underlagt #1, og den som kaller den funksjonen er underlagt #2

  1. På toppnivå, bruk setTimeout(() => genR.next()) for å returnere til JS EventLoop og deretter starte kjeden av suspenderte funksjoner på nytt.

[før #2 var åpenbart, skrev jeg denne typescript-koden, nå er 'yieldR' inline, som vist ovenfor]

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

Merk: mest dokumentert bruk av function* er for å lage en Iterator, et tilfelle der 'yield' gir den interessante/nyttige verdien, og 'return' signaliserer når det er ferdig. I dette brukstilfellet er det omvendt: yield gir et signal, men ingen interessant verdi, og 'return' gir den interessante beregningsverdien.

Appell til JS-gudene: Gi en funksjon: runEventLoop() som transparent legger den nåværende fortsettelsen (hele stakken) på eventløkken og returnerer kontroll direkte til toppnivå, slik at alle de andre kallene og kallstakken ikke trenger å være klar over suspenderingen/ gjenopptagelsen som gjøres på lavere nivå.

Etter merknad: det ser ut til å være et betydelig ytelsestap ved å bruke Generatorer på denne måten. Etter å ha inline-et koden for å redusere nestede Generatorer fra 4 til 2, kjørte koden 10 ganger raskere. Så kanskje CPS- eller dataflytdesign kan være aktuelt for komplekse/tidskritiske apper. (men fortsatt, det fungerte under utvikling/debugging for å få tastatur/grafikk til å fungere)

En annen merknad: Chrome pålegger en minimumsforsinkelse på 4 ms for 'setTimeout'; så hvis du beregner i 1 ms og deretter gir kontrollen i 4 ms, er det tregt og kan forklare merknaden ovenfor. Det hjelper å beregne deltaen fra siste pause til Date.now() og gi kontrollen bare når dette er større enn [20 -- 200 ms?] (avhengig av hvor rask respons du trenger).

Relaterte artikler