Co to jest optymalizacja połączeń z ogonami?

Question

Po prostu, co to jest optymalizacja ogona? Mówiąc dokładniej, czy każdy może wyświetlać małe fragmenty kodu, w których można je zastosować, a gdzie nie, z wyjaśnieniem, dlaczego?

Answer 1

Optymalizacja ogona jest tam, gdzie można uniknąć przydzielania nowej ramki stosu dla funkcji, ponieważ funkcja wywołująca po prostu zwróci wartość, którą otrzymuje z wywoływanej funkcji. Najczęstszym zastosowaniem jest rekursja ogona, w której funkcja rekurencyjna napisana w celu skorzystania z optymalizacji wywołania końcowego może wykorzystywać stałą przestrzeń stosu.

Program jest jednym z kilku języków programowania, które gwarantują w specyfikacji, że każda realizacja musi dostarczyć tej optymalizacji (JavaScript będzie również po ES6 zostanie sfinalizowana), więc oto dwa przykłady silni funkcji w schemacie:

(define (fact x) 
    (if (= x 0) 1 
     (* x (fact (- x 1))))) 

(define (fact x) 
    (define (fact-tail x accum) 
    (if (= x 0) accum 
     (fact-tail (- x 1) (* x accum)))) 
    (fact-tail x 1)) 

Pierwsza funkcja nie jest rekurencyjna, ponieważ po wywołaniu rekursywnym funkcja musi śledzić mnożenie, które musi wykonać z wynikiem po powrocie połączenia. Jako takie, stos wygląda następująco:

(fact 3) 
(* 3 (fact 2)) 
(* 3 (* 2 (fact 1))) 
(* 3 (* 2 (* 1 (fact 0)))) 
(* 3 (* 2 (* 1 1))) 
(* 3 (* 2 1)) 
(* 3 2) 
6 

Natomiast ślad stosu za ogon rekurencyjnej silnia wygląda następująco:

(fact 3) 
(fact-tail 3 1) 
(fact-tail 2 3) 
(fact-tail 1 6) 
(fact-tail 0 6) 
6 

Jak widać, tylko musimy śledzić tyle samo danych dla każdego połączenia z faktem, ponieważ zwracamy po prostu wartość, którą otrzymujemy od samego początku. Oznacza to, że nawet gdybym miał zadzwonić (fakt 1000000), potrzebuję tylko tyle samo miejsca co (fakt 3). Nie dzieje się tak w przypadku rekursywnego faktu, który nie powoduje ogonów, a ponieważ takie duże wartości mogą powodować przepełnienie stosu.

Answer 2

Spójrz tutaj:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

Jak zapewne wiecie, rekurencyjne wywołania funkcji może siać spustoszenie na stosie; łatwo jest szybko zabraknąć miejsca na stosie. Optymalizacja wywołania ogona jest metodą, dzięki której można utworzyć algorytm stylu rekursywnego, który wykorzystuje stałą przestrzeń stosu, dlatego nie rośnie i nie rośnie, a występują błędy stosu.

Answer 3

Uwaga: po pierwsze, nie wszystkie języki go obsługują.

TCO stosuje się do specjalnego przypadku rekursji. Istotą tego jest, jeśli ostatnią rzeczą, jaką wykonujesz w funkcji, jest samo wywołanie (np. Wywołuje się z pozycji "ogon"), może to zostać zoptymalizowane przez kompilator, aby działał jak iteracja zamiast standardowej rekursji.

Widzisz, zwykle podczas rekurencji środowisko wykonawcze musi śledzić wszystkie wywołania rekursywne, aby po powrocie mogło zostać wznowione po poprzednim połączeniu i tak dalej. (Spróbuj ręcznie wypisać wynik rekursywnego wywołania, aby uzyskać wizualny obraz tego, jak to działa.) Śledzenie wszystkich połączeń zajmuje miejsce, które staje się znaczące, gdy funkcja sama się nazywa. Ale dzięki TCO może powiedzieć "wróć do początku, tylko tym razem zmień wartości parametrów na te nowe." Może to zrobić, ponieważ nic po wywołaniu rekursywnym nie odnosi się do tych wartości.

Answer 4

TCO (Tail Call Optimization) to proces, w którym inteligentny kompilator może nawiązać połączenie z funkcją i nie zajmować dodatkowego miejsca na stosie.jedynie sytuacja, w której to się dzieje, jeśli ostatnia instrukcja wykonywana w funkcji f jest wywołanie funkcji g (Uwaga: g może być f). Kluczem jest to, że f nie potrzebuje już miejsca na stosie - po prostu wywołuje g, a następnie zwraca to, co zwróciło ponownie g. W tym przypadku można zoptymalizować, że g po prostu działa i zwraca jakąkolwiek wartość, jaką miałaby na rzecz zwaną f.

Ta optymalizacja może spowodować, że wywołania cykliczne przyjmą stałą przestrzeń stosu, zamiast eksplodować.

Przykład: ta funkcja nie jest silnia TCOptimizable:

def fact(n): 
    if n == 0: 
     return 1 
    return n * fact(n-1) 

Funkcja ta ma rzeczy oprócz wywołać inną funkcję w swojej instrukcji return.

To poniżej funkcji jest TCOptimizable:

def fact_h(n, acc): 
    if n == 0: 
     return acc 
    return fact_h(n-1, acc*n) 

def fact(n): 
    return fact_h(n, 1) 

To dlatego, że ostatnią rzeczą zdarzyć się w każdym z tych funkcji jest wywołanie innej funkcji. spacer

Answer 5

Let poprzez prosty przykład: funkcja silnia realizowane w C.

Zaczynamy z oczywistym rekurencyjnej definicji

unsigned fac(unsigned n) 
{ 
    if (n < 2) return 1; 
    return n * fac(n - 1); 
} 

Funkcja kończy się wezwaniem ogona jeżeli ostatnia operacja przed funkcji zwraca to inne wywołanie funkcji. Jeśli to wywołanie wywołuje tę samą funkcję, jest rekursywne.

Nawet fac() wygląda ogon rekurencyjny na pierwszy rzut oka, to nie jest tak, co faktycznie dzieje

unsigned fac(unsigned n) 
{ 
    if (n < 2) return 1; 
    unsigned acc = fac(n - 1); 
    return n * acc; 
} 

czyli ostatnia operacja jest mnożenie, a nie wywołanie funkcji.

Jednakże, jest możliwe, aby przerobić fac() za ogon rekurencyjne przepuszczając skumulowaną wartość w łańcuchu połączeń jako dodatkowy argument i przechodząc tylko wynik końcowy znów jako wartość powrotna:

unsigned fac(unsigned n) 
{ 
    return fac_tailrec(1, n); 
} 

unsigned fac_tailrec(unsigned acc, unsigned n) 
{ 
    if (n < 2) return acc; 
    return fac_tailrec(n * acc, n - 1); 
} 

teraz , dlaczego jest to przydatne? Ponieważ natychmiast powracamy po wywołaniu ogona, możemy odrzucić poprzednią ramkę stosu przed wywołaniem funkcji w pozycji ogonowej lub, w przypadku funkcji rekurencyjnych, ponownie użyć ramki stosu bez zmian.

Optymalizacja ogona wywołanie przetwarza naszą rekurencyjne kodu do

unsigned fac_tailrec(unsigned acc, unsigned n) 
{ 
TOP: 
    if (n < 2) return acc; 
    acc = n * acc; 
    n = n - 1; 
    goto TOP; 
} 

Może być wstawiane do fac() i dotrzeć

unsigned fac(unsigned n) 
{ 
    unsigned acc = 1; 

TOP: 
    if (n < 2) return acc; 
    acc = n * acc; 
    n = n - 1; 
    goto TOP; 
} 

co jest równoważne

unsigned fac(unsigned n) 
{ 
    unsigned acc = 1; 

    for (; n > 1; --n) 
     acc *= n; 

    return acc; 
} 

As jak widzimy, wystarczająco zaawansowany optymalizator może zastąpić rekursję ogonową w z iteracją, która jest o wiele bardziej wydajna, ponieważ unikasz narzutu wywołania funkcji i używasz tylko stałej ilości miejsca na stosie.

Answer 6

1. Należy dopilnować, aby w samej funkcji nie było instrukcji goto .. dbano o to, by wywołanie funkcji było ostatnią rzeczą w funkcji wywołującej.

2. Rekurencje na dużą skalę mogą wykorzystać to do optymalizacji, ale w małej skali, narzut instrukcji powodujący, że funkcja wywołuje wywołanie ogona, zmniejsza rzeczywisty cel.

3. TCO może spowodować zawsze działa funkcję:

   void eternity() 
   { 
       eternity(); 
   } 
   

Answer 7

Prawdopodobnie najlepszy opis wysoki poziom znalazłem dla połączeń ogon, rekurencyjnych wywołań ogona i optymalizacji połączenia ogon jest blogu

"What the heck is: A tail call"

od Dana Sugalskiego. Na ogonie optymalizacji połączeń pisze:

Consider, for a moment, this simple function:

sub foo (int a) { 
    a += 15; 
    return bar(a); 
} 

So, what can you, or rather your language compiler, do? Well, what it can do is turn code of the form return somefunc(); into the low-level sequence pop stack frame; goto somefunc(); . In our example, that means before we call bar , foo cleans itself up and then, rather than calling bar as a subroutine, we do a low-level goto operation to the start of bar . Foo 's already cleaned itself out of the stack, so when bar starts it looks like whoever called foo has really called bar , and when bar returns its value, it returns it directly to whoever called foo , rather than returning it to foo which would then return it to its caller.

I na ogon rekursji:

Tail recursion happens if a function, as its last operation, returns the result of calling itself. Tail recursion is easier to deal with because rather than having to jump to the beginning of some random function somewhere, you just do a goto back to the beginning of yourself, which is a darned simple thing to do.

tak, że w ten sposób:

sub foo (int a, int b) { 
    if (b == 1) { 
    return a; 
    } else { 
    return foo(a*a + a, b - 1); 
    } 

dostaje spokojnie zamienił się:

sub foo (int a, int b) { 
    label: 
    if (b == 1) { 
     return a; 
    } else { 
     a = a*a + a; 
     b = b - 1; 
     goto label; 
    } 

Co Podoba mi się ten opis, to jak udany i jest łatwy do uchwycenia dla tych, którzy pochodzą z imperatywnego języka (C, C++, Java).