Apakah ada tail call (TCO) mesin JavaScript yang dioptimalkan?

91

Saya memiliki algoritma pathfinding rekursif ekor yang telah saya terapkan dalam JavaScript dan ingin tahu apakah ada (semua?) Browser yang mungkin mendapatkan pengecualian stack overflow.

javascript functional-programming tail-recursion clofresh
sumber
2
Apakah itu sebenarnya algoritma rekursif, atau algoritma berulang yang diimplementasikan dengan rekursi? Pemahaman saya adalah bahwa TCO hanya dapat membantu dengan yang terakhir.
nmichaels
1
Saya hanya ingin menambahkan bahwa TCO bukanlah onlyoptimasi. Mendukungnya harus menjadi bagian dari spesifikasi bahasa, bukan compiler / interpreter karena kode yang ditulis terhadap satu interpreter / compiler dengan TCO mungkin tidak akan berfungsi pada interpreter / compiler tanpa TCO.
Hoffmann
1
Anda dapat melihat dukungan saat ini dan melihatnya berkembang di seluruh mesin dalam tabel kompatibilitas ES6 Kangax di sini: kangax.github.io/compat-table/es6/…
Roy Tinker

Jawaban:

47

Spesifikasi ECMAScript 4 awalnya akan menambahkan dukungan untuk TCO, tetapi dibatalkan:

Tidak ada lagi tail call di JavaScript?

Sejauh yang saya tahu, tidak ada implementasi JavaScript yang tersedia secara luas saat ini yang melakukan TCO otomatis. Ini mungkin berguna bagi Anda, meskipun:

Optimasi Tail Call

Pada dasarnya, menggunakan pola akumulator menghasilkan efek yang sama.

Tim Sylvester
sumber
1
Sekadar info, Rhino memiliki TCO otomatis bersama dengan Kelanjutan dalam mode "ditafsirkan" (opt = -1) wiki.apache.org/cocoon/RhinoWithContinuations
Mark Porter
5
(maaf karena trolling) ECMAScript 6 telah menyertakan TCO, disebut Panggilan Tail yang Benar dalam spesifikasi.
sangat dingin
@sclv: Apa referensi trampolinnya?
bukzor
39
Pola akumulator tidak mencapai efek yang sama seperti TCO. Ini hanya mengubah algoritma rekursif menjadi bentuk rekursif-ekor. Ini adalah prasyarat agar TCO menjadi mungkin, tetapi ini bukan penggantinya. Anda masih akan gagal dalam bahasa yang tidak mengoptimalkan tail-call.
Marcelo Cantos
"Tidak ada implementasi JS yang tersedia secara luas saat ini yang melakukan TCO otomatis" ini salah pada Node 6.2.0, jika Anda meneruskan flag yang benar
Janus Troelsen
26

Tidak ada kegembiraan untuk saat ini, tapi untungnya panggilan ekor yang tepat dijadwalkan untuk Harmony (ECMAScript versi 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls

Tuan Pembicara
sumber
1
@MarkWilbur Pertanyaannya khusus tentang browser , tidak semua implementasi ECMAScript yang ada.
Kode Tidak Berguna
1
@UselessCode Tidak, pertanyaan ini tentang "mesin Javascript" jadi ... bukan hanya browser
BT
1
@BT Memang ada banyak lingkungan JS non-browser, dan judulnya memang menggunakan "mesin Javascript" yang lebih umum, tetapi isi pertanyaan menentukan "... ingin tahu apakah ada (semua?) Browser yang mungkin mendapatkan tumpukan pengecualian melimpah. "
Kode Tidak Berguna
Saya harus melawan "tapi judulnya mengatakan ...". Saya pikir karena dia menyebutkan keduanya, pertanyaannya adalah tentang keduanya. Tetapi Anda benar jika Anda mengatakan itu tidak membuat jawaban menjadi usang.
BT
4
@MarkWilbur Sejauh yang saya tahu, node menggunakan versi v8 yang sama dengan chrome - yang saat ini tidak mendukung do TCO, saya memiliki inti dengan JS, dan assembler yang dioptimalkan yang diproduksi V8 saat ini - gist.github.com/mcfedr / 832e3553964a014621d5
mcfedr
12

Hampir semua browser yang Anda temui akan muntah "terlalu banyak rekursi". Berikut adalah entri di pelacak bug V8 yang mungkin akan menjadi bacaan yang menarik.

Jika rekursi mandiri sederhana, mungkin upaya untuk menggunakan iterasi eksplisit lebih baik daripada berharap untuk eliminasi tail-call.

Hank Gay
sumber
Bug tersebut akhirnya diterima. Di bawah epik: "Permintaan Fitur Harmoni". Mudah-mudahan itu berarti mereka berencana untuk menambahkannya ke dukungan ES6 di V8.
Txangel
Anda dapat memilih dukungan TCO di Internet Explorer di sini: wpdev.uservoice.com/forums/257854-internet-explorer-platform/…
Roy Tinker
12

Pengoptimalan tail call akan didukung dalam mode ketat ECMAScript 6 di masa mendatang. Lihat http://www.2ality.com/2015/06/tail-call-optimization.html untuk detailnya.

Periksa http://kangax.github.io/compat-table/es6/ untuk dukungan mesin saat ini.

Saat ini (18-07-2019) mesin berikut mendukung optimalisasi panggilan ekor:

  • Safari> = 10
  • iOS> = 10
  • Kinoma XS6
  • Duktape 2.3.0

mendukung jika "fitur JavaScript eksperimental" -bendera diaktifkan:

  • Node 6.5
  • Chrome 54 / Opera 41 Versi terbaru dari tabel compat tidak mencantumkannya lagi
Simon Zyx
sumber
3

Pengoptimalan panggilan ekor sekarang tersedia di LispyScript yang dikompilasi ke JavaScript. Anda dapat membaca lebih lanjut di sini .

Santosh
sumber
Bagaimana dengan rekursi bersama?
kucing
2

Saat ini tidak ada implementasi JavaScript yang mengenali rekursi ekor. Perubahan sedang dilakukan di ECMAScript 6 , dan seperti yang dikatakan orang lain, ada tiket terbuka di V8 .

Di sini Anda dapat melihat assembler yang dihasilkan V8 untuk fungsi rekursi ekor:

Contoh bagaimana V8 mengkompilasi rekursi

Bandingkan itu dengan bagaimana Clang telah menyusun fungsi yang sama di C

Contoh rekursi ekor compiler C.

V8 mempertahankan panggilan rekursif, sedangkan kompiler C telah mengenali rekursi ekor dan mengubahnya menjadi loop.

mcfedr.dll
sumber
"Saat ini tidak ada implementasi JS yang mengenali rekursi ekor." itu salah pada Node 6.2.0, tetapi Anda harus memberikan sebuah bendera
Janus Troelsen