Dlaczego działają trampoliny?

Robiłem funkcjonalny JavaScript. Myślałem, że zaimplementowano optymalizację ogona , ale jak się okazuje, myliłem się. Dlatego musiałem nauczyć się trampoliny . Po krótkiej lekturze tutaj i gdzie indziej udało mi się opanować podstawy i zbudować moją pierwszą trampolinę:

/*not the fanciest, it's just meant to
reenforce that I know what I'm doing.*/

function loopy(x){
    if (x<10000000){ 
        return function(){
            return loopy(x+1)
        }
    }else{
        return x;
    }
};

function trampoline(foo){
    while(foo && typeof foo === 'function'){
        foo = foo();
    }
    return foo;
/*I've seen trampolines without this,
mine wouldn't return anything unless
I had it though. Just goes to show I
only half know what I'm doing.*/
};

alert(trampoline(loopy(0)));

Moim największym problemem jest to, że nie wiem, dlaczego to działa. Mam pomysł ponownego uruchomienia funkcji w pętli while zamiast użycia pętli rekurencyjnej. Tyle że technicznie moja podstawowa funkcja ma już pętlę rekurencyjną. Nie uruchamiam loopyfunkcji podstawowej , ale uruchamiam wewnątrz niej funkcję. Co powstrzymuje foo = foo()Cię przed przepełnieniem stosu? I czy nie jest to foo = foo()technicznie mutujące, czy coś mi brakuje? Być może jest to po prostu zło konieczne. Albo brakuje mi jakiejś składni.

Czy jest jakiś sposób, aby to zrozumieć? A może to tylko jakiś hack, który w jakiś sposób działa? Udało mi się przejść przez wszystko inne, ale to mnie zdenerwowało.

Powodem, dla którego Twój mózg buntuje się przeciwko tej funkcji loopy(), jest niespójny typ :

function loopy(x){
    if (x<10000000){ 
        return function(){ // On this line it returns a function...
            // (This is not part of loopy(), this is the function we are returning.)
            return loopy(x+1)
        }
    }else{
        return x; // ...but on this line it returns an integer!
    }
};

Dość wiele języków nawet nie pozwala ci robić takich rzeczy, a przynajmniej wymaga dużo więcej pisania, aby wyjaśnić, jak to ma jakikolwiek sens. Ponieważ tak naprawdę nie jest. Funkcje i liczby całkowite to zupełnie różne rodzaje obiektów.

Przejdźmy więc przez pętlę while, ostrożnie:

while(foo && typeof foo === 'function'){
    foo = foo();
}

Początkowo foojest równa loopy(0). Co to jest loopy(0)? Cóż, to mniej niż 10000000, więc rozumiemy function(){return loopy(1)}. To jest prawdziwa wartość i jest to funkcja, więc pętla działa dalej.

Teraz dochodzimy do foo = foo(). foo()jest taki sam jak loopy(1). Ponieważ 1 jest wciąż mniejszy niż 10000000, zwraca to function(){return loopy(2)}, a następnie przypisujemy foo.

foojest nadal funkcją, więc kontynuujemy ... dopóki ostatecznie foo nie będzie równe function(){return loopy(10000000)}. Jest to funkcja, więc robimy to foo = foo()jeszcze raz, ale tym razem, gdy wywołujemy loopy(10000000), x jest nie mniejsze niż 10000000, więc po prostu odzyskujemy x. Ponieważ 10000000 również nie jest funkcją, to również kończy pętlę while.

Kevin zwięźle wskazuje, jak działa ten konkretny fragment kodu (wraz z tym, dlaczego jest dość niezrozumiały), ale chciałem dodać trochę informacji o tym, jak ogólnie trampoliny działają.

Bez optymalizacji wywołania ogona (TCO) każde wywołanie funkcji dodaje ramkę stosu do bieżącego stosu wykonania. Załóżmy, że mamy funkcję do wydrukowania odliczania liczb:

function countdown(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    countdown(n - 1);
  }
}

Jeśli zadzwonimy countdown(3), przeanalizujmy, jak wyglądałby stos wywołań bez całkowitego kosztu posiadania.

> countdown(3);
// stack: countdown(3)
Launch in 3
// stack: countdown(3), countdown(2)
Launch in 2
// stack: countdown(3), countdown(2), countdown(1)
Launch in 1
// stack: countdown(3), countdown(2), countdown(1), countdown(0)
Blastoff!
// returns, stack: countdown(3), countdown(2), countdown(1)
// returns, stack: countdown(3), countdown(2)
// returns, stack: countdown(3)
// returns, stack is empty

W przypadku TCO każde wywołanie rekurencyjne countdownjest w pozycji ogonowej (nie pozostaje nic innego, jak zwrócić wynik wywołania), więc ramka stosu nie jest przydzielana. Bez całkowitego kosztu posiadania stos wysadza się nawet w przypadku bardzo dużych rozmiarów n.

Trampolinowanie omija to ograniczenie, umieszczając opakowanie wokół countdownfunkcji. Następnie countdownnie wykonuje wywołań rekurencyjnych i zamiast tego natychmiast zwraca funkcję do wywołania. Oto przykładowa implementacja:

function trampoline(firstHop) {
  nextHop = firstHop();
  while (nextHop) {
    nextHop = nextHop()
  }
}

function countdown(n) {
  trampoline(() => countdownHop(n));
}

function countdownHop(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    return () => countdownHop(n-1);
  }
}

Aby lepiej zrozumieć, jak to działa, spójrzmy na stos wywołań:

> countdown(3);
// stack: countdown(3)
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(3)
Launch in 3
// return next hop from countdownHop(3)
// stack: countdown(3), trampoline
// trampoline sees hop returned another hop function, calls it
// stack: countdown(3), trampoline, countdownHop(2)
Launch in 2
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(1)
Launch in 1
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(0)
Blastoff!
// stack: countdown(3), trampoline
// stack: countdown(3)
// stack is empty

Na każdym kroku countdownHopfunkcja porzuca bezpośrednią kontrolę, co dzieje się obok, zamiast wracać funkcję zadzwonić, który opisuje, co to lubią się wydarzy. Funkcja trampoliny bierze to i wywołuje, a następnie wywołuje dowolną funkcję, która powraca, i tak dalej, aż nie będzie „następnego kroku”. Nazywa się to trampolinowaniem, ponieważ przepływ sterowania „odbija się” między każdym wywołaniem rekurencyjnym a implementacją trampoliny, zamiast funkcji bezpośrednio powtarzającej się. Porzucając kontrolę nad tym, kto wykonuje wywołanie rekurencyjne, funkcja trampoliny może zapewnić, że stos nie będzie zbyt duży. Uwaga dodatkowa: ta implementacja trampolinepomija zwracanie wartości dla uproszczenia.

Trudno jest ustalić, czy to dobry pomysł. Wydajność może ucierpieć z powodu każdego kroku przydzielającego nowe zamknięcie. Sprytne optymalizacje mogą sprawić, że będzie to wykonalne, ale nigdy nie wiadomo. Trampolinowanie jest szczególnie przydatne do omijania twardych limitów rekurencji, na przykład gdy implementacja języka ustawia maksymalny rozmiar stosu wywołań.

Może łatwiej jest zrozumieć, jeśli trampolina jest implementowana z dedykowanym typem powrotu (zamiast nadużywania funkcji):

class Result {}
// poor man's case classes
class Recurse extends Result {
    constructor(a) { this.arg = a; }
}
class Return extends Result {
    constructor(v) { this.value = v; }
}

function loopy(x) {
    if (x<10000000)
        return new Recurse(x+1);
    else
        return new Return(x);
}

function trampoline(fn, x) {
    while (true) {
        const res = fn(x);
        if (res instanceof Recurse)
            x = res.arg;
        else if (res instanceof Return)
            return res.value;
    }
}

alert(trampoline(loopy, 0));

Porównaj to z wersją trampoline, w której przypadek rekurencji występuje, gdy funkcja zwraca inną funkcję, a przypadek podstawowy, gdy zwraca coś innego.

Co powstrzymuje foo = foo()Cię przed przepełnieniem stosu?

Nie nazywa się już sobą. Zamiast tego zwraca wynik (w mojej implementacji, dosłownie a Result), który informuje, czy kontynuować rekurencję, czy też się wyrwać.

I czy nie jest to foo = foo()technicznie mutujące, czy coś mi brakuje? Być może jest to po prostu zło konieczne.

Tak, to dokładnie konieczne zło pętli. Można również pisać trampolinebez mutacji, ale wymagałoby to ponownej rekurencji:

function trampoline(fn, x) {
    const res = fn(x);
    if (res instanceof Recurse)
        return trampoline(fn, res.arg);
    else if (res instanceof Return)
        return res.value;
}

Mimo to pokazuje ideę tego, co funkcja trampoliny robi jeszcze lepiej.

Celem trampolingu jest wyodrębnienie wywołania rekurencyjnego z funkcji ogona od funkcji, która chce użyć rekurencji do wartości zwracanej, i wykonanie rzeczywistej rekurencji tylko w jednym miejscu - trampolinefunkcji, którą można następnie zoptymalizować w jednym miejscu, aby użyć pętla.