Dlaczego działają trampoliny?

104

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.

Ucenna
źródło
5
Tak, ale to wciąż rekurencja. loopynie przepełnia się, ponieważ się nie nazywa .
tkausl,
4
„Myślałem, że TCO zostało wdrożone, ale jak się okazuje, myliłem się”. W większości scenariuszy był przynajmniej w wersji V8. Możesz go użyć na przykład w dowolnej najnowszej wersji Node, mówiąc Node, aby włączył ją w wersji V8: stackoverflow.com/a/30369729/157247 Chrome miał (za flagą „eksperymentalną”) od Chrome 51.
TJ Crowder
125
Energia kinetyczna od użytkownika jest przekształcana w sprężystą energię potencjalną w miarę opadania trampoliny, a następnie z powrotem w energię kinetyczną podczas odbijania.
immibis
66
@immibis, W imieniu wszystkich, którzy przybyli tutaj, nie sprawdzając, która strona Stack Exchange to była, dziękuję.
user1717828,
4
@jpaugh miałeś na myśli „hopping”? ;-)
Hulk

Odpowiedzi:

89

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
źródło
1
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
yannis,
To naprawdę tylko rodzaj sumy. Czasami znany jako wariant. Języki dynamiczne obsługują je dość łatwo, ponieważ każda wartość jest oznaczona, podczas gdy więcej języków o typie statycznym będzie wymagało określenia funkcji zwracającej wariant. Trampoliny są łatwo dostępne na przykład w C ++ lub Haskell.
GManNickG,
2
@GManNickG: Tak, miałem na myśli to „dużo więcej pisania”. W C musiałbyś zadeklarować związek, zadeklarować strukturę, która oznacza związek, spakować i rozpakować strukturę na obu końcach, spakować i rozpakować związek na obu końcach i (prawdopodobnie) dowiedzieć się, kto jest właścicielem pamięci, w której mieszka struktura . C ++ jest prawdopodobnie mniejszym kodem niż ten, ale nie jest koncepcyjnie mniej skomplikowany niż C i wciąż jest bardziej gadatliwy niż JavaScript OP.
Kevin,
Jasne, nie kwestionuję tego, po prostu uważam, że nacisk, jaki kładziesz na bycie dziwnym lub bez sensu, jest trochę silny. :)
GManNickG
173

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ń.

Jacek
źródło
18

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.

Bergi
źródło
foo = foo()jest mutacją w sensie modyfikowania stanu lokalnego, ale ogólnie uważam, że to ponowne przypisanie, ponieważ tak naprawdę nie modyfikujesz podstawowego obiektu funkcji, zastępujesz go funkcją (lub wartością), którą zwraca.
JAB
@JAB Tak, nie miałem na myśli sugerowania mutacji wartości, która foozawiera, tylko zmienna jest modyfikowana. whilePętla wymaga stan zmienny jeśli chcesz go rozwiązać, w tym przypadku zmiennej foolub x.
Bergi,
W odpowiedzi na pytanie Stack Overflow dotyczące optymalizacji wezwania ogona, trampolin itp. Zrobiłem coś takiego w przeszłości
Joshua Taylor,
2
Twoja wersja bez mutacji przekształciła rekurencyjne wywołanie fnw rekurencyjne wywołanie do trampoline- nie jestem pewien, czy to poprawa.
Michael Anderson
1
@MichaelAnderson Ma to jedynie na celu wykazanie abstrakcji. Oczywiście rekurencyjna trampolina nie jest przydatna.
Bergi,