Czy użycie wielu rekursji ogona w Erlangu spowalnia działanie?

Question

Ostatnio czytałem o Erlang i jak rekursja ogona jest tak intensywnie wykorzystywana, ze względu na trudność w używaniu pętli iteracyjnych.

Czy to wysokie użycie rekursji nie spowalnia, co z wszystkimi wywołanymi funkcjami i efektem, jaki mają na stosie? A może rekursja ogonowa neguje większość tego?

Answer 1

Iteracyjna rekurencja ogona jest ogólnie realizowana za pomocą Tail calls. Jest to w zasadzie transformacja wywołania rekursywnego do prostej pętli.

C# przykład:

uint FactorialAccum(uint n, uint accum) { 
    if(n < 2) return accum; 
    return FactorialAccum(n - 1, n * accum); 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

do

uint FactorialAccum(uint n, uint accum) { 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

lub jeszcze lepiej:

uint Factorial(uint n) { 
    uint accum = 1; 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 

---

C nie # rzeczywistym ogon rekursji tym, że wartość powrotna jest modyfikowany większość kompilatorów nie złamie tego WN pętlę:

int Power(int number, uint power) { 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    return number * Power(number, --power); 
} 

do

int Power(int number, uint power) { 
    int result = number; 
start: 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    result *= number; 
    power--; 
goto start; 
} 

Answer 2

Chodzi o to, że Erlang optymalizuje połączenia ogona (nie tylko rekurencji). Optymalizacja wywołań ogonowych jest dość prosta: jeśli wartość zwracana jest obliczana przez wywołanie innej funkcji, to ta druga funkcja nie jest po prostu umieszczana na stosie wywołania funkcji na funkcji wywołującej, ale zamiast tego ramka stosu bieżącej funkcji jest zastąpiony przez jedną z funkcji wywoływanych. Oznacza to, że wywołania ogona nie są dodawane do rozmiaru stosu.

Tak, nie, używanie rekursji ogonowej nie zwalnia Erlanga w dół, ani nie stanowi ryzyka przepełnienia stosu.

Z optymalizacją wywołania ogona można korzystać nie tylko z prostej rekursji ogonowej, ale również z wzajemnej rekurencji ogona z kilku funkcji (ogon-wywołania b, którego ogon wywołuje c, który ogon wywołuje ...) . Czasami może to być dobry model obliczeń.

Answer 3

Nie powinno to w większości przypadków wpływać na wydajność. To, czego szukasz, to nie tylko połączenia typu "ogon", ale "optymalizacja połączenia" (lub eliminacja połączenia końcowego). Optymalizacja wywołania ogona to technika kompilatora lub środowiska wykonawczego, która wylicza, kiedy wywołanie funkcji jest równoważne "wyskakiwaniu stosu", aby powrócić do właściwej funkcji, a nie tylko wrócić. Zasadniczo optymalizacja wywołań końcowych może być wykonana tylko wtedy, gdy wywołanie rekurencyjne jest ostatnią operacją w funkcji, więc musisz być ostrożny.

Answer 4

Podobna optymalizacja, która oddziela wywołania funkcji tekstowych programu od wywołań funkcji implementacji, to "inlining". W nowoczesnych/przemyślanych językach wywołania funkcji mają niewielki związek z wywołaniami funkcji na poziomie maszyny.

Answer 5

Istnieje problem związany z rekurencją ogona, ale nie jest on związany z wydajnością - optymalizacja rekursji ogona Erlanga obejmuje również eliminację śledzenia stosu do debugowania.

Na przykład patrz punkt 9.13 Erlang FAQ:

Why doesn't the stack backtrace show the right functions for this code: 

     -module(erl). 
     -export([a/0]). 

     a() -> b(). 
     b() -> c(). 
     c() -> 3 = 4.   %% will cause badmatch 

The stack backtrace only shows function c(), rather than a(), b() and c(). 
This is because of last-call-optimisation; the compiler knows it does not need 
to generate a stack frame for a() or b() because the last thing it did was 
call another function, hence the stack frame does not appear in the stack 
backtrace. 

To może być trochę bólu po trafieniu awarii (ale to jest trochę przejść z obszaru programowania funkcjonalnego ...)