Ho un algoritmo di individuazione del percorso ricorsivo di coda che ho implementato in Javascript e vorrei sapere se alcuni (tutti?) Browser potrebbero ottenere eccezioni di overflow dello stack.I richiami dei motori Javascript sono ottimizzati?
La specifica ECMAScript 4 avrebbe originariamente aggiunto il supporto per il TCO, ma è stata eliminata.
http://lambda-the-ultimate.org/node/3047
Per quanto ne so, le implementazioni non ampiamente disponibili JS attualmente fanno TCO automatico. Questo può essere utile a voi, però:
http://www.paulbarry.com/articles/2009/08/30/tail-call-optimization
In sostanza, utilizzando il modello dell'accumulatore ottenere lo stesso effetto.
O semplicemente usa un trampolino. .. – sclv
Solo una FYI, Rhino ha TCO automatico insieme a Continuazioni in modalità "interpretata" (opt = -1) http://wiki.apache.org/cocoon/RhinoWithContinuations –
(mi dispiace per la traina) ECMAScript 6 ha incluso TCO, definito corretto chiamate a coda nelle specifiche. – frosty
Praticamente tutti i browser che incontrerai si troveranno in "troppa ricorsione". Ecco uno entry in the V8 bug tracker che probabilmente sarà una lettura interessante.
Se è semplice auto-ricorsione, probabilmente vale la pena di usare l'iterazione esplicita piuttosto che sperare nell'eliminazione di coda.
Il bug è stato finalmente accettato. È sotto l'epopea: "Feature Request Harmony". Si spera che ciò significhi che hanno intenzione di aggiungerlo al supporto ES6 nel V8. – Txangel
Puoi votare per il supporto del TCO in Internet Explorer qui: https://wpdev.uservoice.com/forums/257854-internet-explorer-platform/suggestions/6850816-es6-tail-call-optimization –
nessuna gioia per il momento, ma per fortuna le chiamate di coda adeguati sono in programma per Harmony (ECMAScript versione 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls
@MarkWilbur La domanda riguardava specificamente _browsers_, non tutte le implementazioni esistenti di ECMAScript. –
@UselessCode No, questa domanda è di "motori JavaScript" Allora ... non solo browser –
@BT Ci sono infatti molti ambienti JS non-browser, e il titolo fa uso delle più generico "motori JavaScript", ma il corpo del domanda specifica "... vorrebbe sapere se alcuni (tutti?) ** browser ** potrebbero ottenere eccezioni di overflow dello stack." –
ottimizzazione chiamata coda è ora disponibile in LispyScript che compila a JavaScript. Potete leggere di più su di esso here.
E riguardo la ricorsione reciproca? – cat
Attualmente nessuna implementazione JS riconosce la ricorsione della coda. I cambiamenti sono stati fatti in ECMAScript 6, e come altri hanno detto, non v'è un biglietto aperto sul V8
Qui potete vedere generato assemblatore di V8 per una funzione di ricorsione in coda
https://gist.github.com/mcfedr/832e3553964a014621d5
Confronti che, per quanto clang ha compilato la stessa funzione in C
https://gist.github.com/mcfedr/63ad08370d856bad3694
V8 mantiene la chiamata ricorsiva, mentre il compilatore C ha riconosciuto la ricorsione coda e cambiato i nto a loop
"Attualmente nessuna implementazione JS riconosce la ricorsione in coda." non è corretto a partire dal Nodo 6.2.0, ma devi passare un flag –
L'ottimizzazione della coda sarà supportata in modalità rigorosa ECMAScript 6 in futuro. Controllare http://www.2ality.com/2015/06/tail-call-optimization.html per i dettagli.
Controllare http://kangax.github.io/compat-table/es6/ per il supporto motore corrente.
Al momento (2018/05/01) i seguenti motori ottimizzazione supporto chiamata coda:
supporto se "sperimentale Funzioni JavaScript "-flag è attivato:
E 'in realtà un algoritmo ricorsivo, o un algoritmo iterativo implementato con la ricorsione? La mia comprensione è che il TCO può solo aiutare con quest'ultimo. – nmichaels
Voglio solo aggiungere che il TCO non è "solo" un'ottimizzazione. Il supporto dovrebbe essere parte delle specifiche del linguaggio, non del compilatore/interprete poiché il codice scritto contro un interprete/compilatore con TCO probabilmente non funzionerebbe su un interprete/compilatore senza TCO. – Hoffmann
Puoi vedere il supporto attuale e guardarlo evolvere attraverso i motori nella tabella di compatibilità ES6 di Kangax qui: http://kangax.github.io/compat-table/es6/#proper_tail_calls_(tail_call_optimisation) –