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 loopy
funkcji 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.
loopy
nie przepełnia się, ponieważ się nie nazywa .Odpowiedzi:
Powodem, dla którego Twój mózg buntuje się przeciwko tej funkcji
loopy()
, jest niespójny typ :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:
Początkowo
foo
jest równaloopy(0)
. Co to jestloopy(0)
? Cóż, to mniej niż 10000000, więc rozumiemyfunction(){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 jakloopy(1)
. Ponieważ 1 jest wciąż mniejszy niż 10000000, zwraca tofunction(){return loopy(2)}
, a następnie przypisujemyfoo
.foo
jest nadal funkcją, więc kontynuujemy ... dopóki ostatecznie foo nie będzie równefunction(){return loopy(10000000)}
. Jest to funkcja, więc robimy tofoo = foo()
jeszcze raz, ale tym razem, gdy wywołujemyloopy(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.źródło
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:
Jeśli zadzwonimy
countdown(3)
, przeanalizujmy, jak wyglądałby stos wywołań bez całkowitego kosztu posiadania.W przypadku TCO każde wywołanie rekurencyjne
countdown
jest 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ówn
.Trampolinowanie omija to ograniczenie, umieszczając opakowanie wokół
countdown
funkcji. Następniecountdown
nie wykonuje wywołań rekurencyjnych i zamiast tego natychmiast zwraca funkcję do wywołania. Oto przykładowa implementacja:Aby lepiej zrozumieć, jak to działa, spójrzmy na stos wywołań:
Na każdym kroku
countdownHop
funkcja 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 implementacjatrampoline
pomija 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ń.
źródło
Może łatwiej jest zrozumieć, jeśli trampolina jest implementowana z dedykowanym typem powrotu (zamiast nadużywania funkcji):
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.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ć.Tak, to dokładnie konieczne zło pętli. Można również pisać
trampoline
bez mutacji, ale wymagałoby to ponownej rekurencji: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 -
trampoline
funkcji, którą można następnie zoptymalizować w jednym miejscu, aby użyć pętla.ź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.foo
zawiera, tylko zmienna jest modyfikowana.while
Pętla wymaga stan zmienny jeśli chcesz go rozwiązać, w tym przypadku zmiennejfoo
lubx
.fn
w rekurencyjne wywołanie dotrampoline
- nie jestem pewien, czy to poprawa.