L'utilizzo di un sacco di ricorsione in coda in Erlang lo rallenta?

Question

Ultimamente ho letto di Erlang e di come la ricorsione della coda sia così pesantemente utilizzata, a causa della difficoltà di utilizzare loop iterativi.

Questo elevato uso della ricorsione non lo rallenta, con tutte le chiamate di funzione e l'effetto che hanno sullo stack? O la ricorsione della coda nega la maggior parte di questo?

Answer 1

La ricorsione a coda iterativa viene generalmente implementata utilizzando Tail calls. Questa è fondamentalmente una trasformazione di una chiamata ricorsiva in un ciclo semplice.

C# esempio:

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); 
}; 

a

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); 
}; 

o meglio:

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

---

C non # reale ricorsione tail, questo è perché il valore restituito viene modificato la maggior parte dei compilatori non si romperà di questo wn in un ciclo:

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

a

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

Il punto è che Erlang ottimizza chiamate di coda (non solo ricorsione). Ottimizzare le chiamate tail è abbastanza semplice: se il valore di ritorno è calcolato da una chiamata a un'altra funzione, allora questa altra funzione non è solo messa sullo stack di chiamata della funzione in cima alla funzione di chiamata, ma invece il frame dello stack della funzione corrente è sostituito con una delle funzioni chiamate. Ciò significa che le chiamate tail non aumentano le dimensioni dello stack.

Quindi, no, l'uso della ricorsione della coda non rallenta l'Erlang, né rappresenta un rischio di overflow dello stack.

Con l'ottimizzazione della chiamata di coda in posizione, non è possibile utilizzare solo la ricorsione della coda, ma anche la ricorsione della coda reciproca di diverse funzioni (una coda chiama b, che coda chiama c, che coda chiama un ...) . Questo a volte può essere un buon modello di calcolo.

Answer 3

Non dovrebbe influire sulle prestazioni nella maggior parte dei casi. Quello che stai cercando non sono solo le chiamate di coda, ma l'ottimizzazione di chiamata di coda (o eliminazione chiamata di coda). Ottimizzazione chiamata coda è una tecnica di compilazione o runtime che capta quando una chiamata a una funzione è l'equivalente di "popping the stack" per tornare alla funzione corretta invece di tornare indietro. Generalmente l'ottimizzazione della chiamata di coda può essere eseguita solo quando la chiamata ricorsiva è l'ultima operazione nella funzione, quindi è necessario fare attenzione.

Answer 4

Un'ottimizzazione simile che separa le chiamate di funzione del testo del programma dalle chiamate della funzione di implementazione è "inlining". Nelle chiamate in lingue moderne/minuziose le chiamate hanno una scarsa relazione con le chiamate di funzione a livello macchina.

Answer 5

C'è un problema relativo alla ricorsione in coda ma non è correlato alle prestazioni: l'ottimizzazione della ricorsione in coda di Erlang comporta anche l'eliminazione della traccia dello stack per il debug.

Per esempio vedere il punto 9.13 del 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. 

Questo può essere un po 'di dolore quando si colpisce un incidente (ma lo fa un pò andare con il territorio di programmazione funzionale ...)