MATLAB esegue l'ottimizzazione delle chiamate tail?

Question

Recentemente ho imparato Haskell e sto cercando di portare lo stile puramente funzionale sul mio altro codice quando possibile. Un aspetto importante di questo è il trattamento di tutte le variabili come immutabili, cioè le costanti. Per fare ciò, molti calcoli che dovrebbero essere implementati usando loop in uno stile imperativo devono essere eseguiti utilizzando la ricorsione, che di solito comporta una penalità di memoria dovuta all'assegnazione di un nuovo stack frame per ogni chiamata di funzione. Nel caso speciale di una chiamata di coda (in cui il valore di ritorno di una funzione chiamata viene immediatamente restituito al chiamante del chiamato), tuttavia, questa penalità può essere bypassata da un processo chiamato ottimizzazione di chiamata di coda (in un metodo, questo può essere fatto da essenzialmente sostituendo una chiamata con una jmp dopo aver impostato correttamente lo stack). MATLAB esegue il TCO di default, o c'è un modo per dirlo a?

Answer 1

Se io definisco una semplice coda ricorsiva funzione:

function tailtest(n) 
    if n==0; feature memstats; return; end 
    tailtest(n-1); 
end 

e chiamare in modo che esso sarà ricorsivamente abbastanza profondamente:

set(0,'RecursionLimit',10000); 
tailtest(1000); 

allora non sembra come se stack frame sono mangiando molta memoria Tuttavia, se lo faccio ricorsione molto più profondo:

set(0,'RecursionLimit',10000); 
tailtest(5000); 

poi (sulla mia macchina, oggi) MATLAB si blocca semplicemente: il processo muore senza tanti complimenti.

Non penso che questo sia coerente con MATLAB facendo qualsiasi TCO; il caso in cui una funzione si autodefinisce, solo in un punto, senza variabili locali diverse da un singolo argomento, è semplicemente la cosa più semplice che chiunque possa sperare.

Quindi: No, sembra che MATLAB non esegua affatto il TCO, almeno per impostazione predefinita. Non ho (finora) cercato opzioni che potrebbero renderlo possibile. Sarei sorpreso se ce ne fossero.

Nei casi in cui non facciamo esplodere lo stack, quanto costa la ricorsione? Vedi il mio commento alla risposta di Bill Cheatham: sembra che l'overhead temporale sia non banale ma non folle.

... Tranne che Bill Cheatham ha cancellato la sua risposta dopo aver lasciato quel commento. OK. Così, ho preso una semplice implementazione iterativa della funzione di Fibonacci e una semplice ricorsiva di coda, facendo essenzialmente lo stesso calcolo in entrambi e cronometrandoli entrambi su fib(60). L'implementazione ricorsiva ha impiegato circa 2,5 volte di più rispetto a quella iterativa. Ovviamente l'overhead relativo sarà più piccolo per le funzioni che fanno più lavoro di una addizione e una sottrazione per iterazione.

(sono d'accordo anche con il sentimento di delnan:. Codice altamente ricorsiva del genere che si sente naturale in Haskell è tipicamente probabile che sia unidiomatic in MATLAB)