Apakah JVM mencegah pengoptimalan panggilan ekor?

99

Saya melihat kutipan ini pada pertanyaan: Apa bahasa fungsional yang baik untuk membangun layanan web?

Scala khususnya tidak mendukung eliminasi panggilan ekor kecuali dalam fungsi rekursif sendiri, yang membatasi jenis komposisi yang dapat Anda lakukan (ini adalah batasan mendasar dari JVM).

Apakah ini benar? Jika ya, ada apa dengan JVM yang menciptakan batasan mendasar ini?

java jvm scala tail-recursion Jason Dagit
sumber

Jawaban:

74

Posting ini: Rekursi atau Iterasi? mungkin membantu.

Singkatnya, pengoptimalan tail call sulit dilakukan di JVM karena model keamanan dan kebutuhan untuk selalu memiliki pelacakan tumpukan yang tersedia. Persyaratan ini secara teori dapat didukung, tetapi mungkin akan memerlukan bytecode baru (lihat proposal informal John Rose ).

Ada juga diskusi lebih lanjut di bug Sun # 4726340 , di mana evaluasi (dari 2002) berakhir:

Saya yakin ini bisa dilakukan, tetapi ini bukan tugas kecil.

Saat ini, ada beberapa pekerjaan yang sedang dikerjakan dalam proyek Mesin Da Vinci . Status subproyek panggilan ekor terdaftar sebagai "proto 80%"; kecil kemungkinannya untuk membuatnya menjadi Java 7, tetapi menurut saya ini memiliki peluang yang sangat bagus di Java 8.

Michael Myers
sumber
Saya tidak begitu mengikuti penjelasannya. Saya pikir optimasi tail-call diimplementasikan oleh compiler. Dengan asumsi Anda memiliki fungsi yang dapat dioptimalkan oleh tail-call oleh compiler, Anda juga dapat memiliki fungsi non-rekursif setara yang mengimplementasikan fungsi yang sama menggunakan loop, benar? Jika demikian, tidak bisakah ini dilakukan oleh kompilator. Saya tidak bisa mengikuti ketergantungan pada JVM. Bagaimana ini dibandingkan dengan kompilator Skema yang menghasilkan kode i386 asli?
Gautham Ganapathy
4
@Gautham: Pernyataan saya tentang debugging mengacu pada penggunaan trampolin sebagai solusi atas kurangnya eliminasi panggilan ekor pada JVM. Penghapusan panggilan ekor dapat dan telah diterapkan pada JVM (Arnold Schaighofer melakukannya di OpenJDK, dan juga LLVM) sehingga tidak ada pertanyaan apakah hal itu dapat dilakukan atau tidak. CLR Microsoft, tentu saja, telah mendukung penghapusan panggilan ekor selama 10 tahun dan rilis F # telah menunjukkan bahwa ini adalah pengubah permainan. Saya rasa jawabannya adalah JVM sudah lama mandek.
JD
3
Ini adalah kesalahpahaman yang umum dan alasan yang sering diulang, tetapi tidak benar. Sudah terbukti selama beberapa tahun bahwa keamanan dengan pemeriksaan tumpukan (dan penyediaan jejak tumpukan yang berguna) tidak bertentangan dengan panggilan ekor yang tepat. Misalnya lihat makalah ini dari tahun 2004. citeseerx.ist.psu.edu/viewdoc/… Downvoting, karena jawabannya salah.
Justin Sheehy
5
@JustinSheehy: Apa yang salah? Pertanyaannya adalah, "Apakah JVM mencegah pengoptimalan panggilan ekor?" Dan jawabannya adalah, "Tidak, tapi sulit."
Michael Myers
5
tahukah anda jika di java8 ini sudah termasuk?
nachokk
27

Batasan mendasar adalah bahwa JVM tidak menyediakan panggilan ekor dalam kode byte-nya dan, akibatnya, tidak ada cara langsung untuk bahasa yang dibangun di atas JVM untuk menyediakan panggilan ekor itu sendiri. Ada beberapa solusi yang dapat mencapai efek serupa (misalnya trampolin) tetapi mereka harus membayar mahal untuk kinerja yang buruk dan mengaburkan kode perantara yang dihasilkan yang membuat debugger tidak berguna.

Jadi JVM tidak dapat mendukung bahasa pemrograman fungsional berkualitas produksi apa pun sampai Sun mengimplementasikan tail call di JVM itu sendiri. Mereka telah membahasnya selama bertahun-tahun tetapi saya ragu mereka akan pernah menerapkan panggilan ekor: ini akan sangat sulit karena mereka telah mengoptimalkan VM mereka sebelum waktunya sebelum menerapkan fungsionalitas dasar seperti itu, dan upaya Sun sangat difokuskan pada bahasa dinamis daripada bahasa fungsional.

Oleh karena itu, terdapat argumen yang sangat kuat bahwa Scala bukanlah bahasa pemrograman yang berfungsi nyata: bahasa-bahasa ini telah menganggap panggilan ekor sebagai fitur penting sejak Skema pertama kali diperkenalkan lebih dari 30 tahun yang lalu.

JD
sumber
5
Hence there is a very strong argument that Scala is not a real functional programming language - Argumennya sebenarnya cukup lemah. Tentu tail calls [as] an essential feature, dan bagus jika perangkat keras yang mendasarinya (atau mesin virtal) mendukungnya secara langsung. Tapi itu detail implementasi.
Ingo
8
@Ingo: Hanya jika Anda tidak menganggap stack overflows di program Anda pada waktu proses yang dilihat oleh pengguna sebagai masalah yang signifikan. Menurut pelacak bugnya, bahkan kompiler Scala sendiri telah diganggu oleh stack overflow. Jadi, bahkan pengembang Scala paling berpengalaman pun masih melakukan kesalahan ...
JD
7
Tidak apa-apa menjadi pendukung, katakanlah F #. Tetapi saya telah mencatat Anda untuk waktu yang lama (bahkan bertahun-tahun sebelumnya di usenet) karena bermusuhan dengan segala sesuatu yang bukan F #, namun elaborasi Anda menunjukkan bahwa Anda tidak tahu apa yang Anda bicarakan. Seperti di sini: argumen Anda tampaknya bahwa bahasa di mana saya dapat menulis program yang dibatalkan dengan stack overflow bukanlah bahasa yang berfungsi? Namun, tidak bisakah argumen yang sama dibuat untuk bahasa di mana saya dapat memicu luapan tumpukan? Karenanya, F # suci itu sendiri tidak akan dihitung sebagai fungsional.
Ingo
7
@Ingo: Beberapa idiom dalam pemrograman fungsional, seperti rekursi timbal balik dan gaya penerusan penerusan, dapat memerlukan eliminasi panggilan ekor agar berfungsi. Tanpanya, program Anda akan melimpah. Jika sebuah bahasa tidak dapat menjalankan kode fungsional idiomatik dengan andal, apakah itu berfungsi? Jawabannya adalah panggilan penilaian, seperti yang Anda katakan, tetapi dalam praktiknya merupakan perbedaan penting. Martin Trojer baru saja menerbitkan entri blog yang menarik tentang ini: martinsprogrammingblog.blogspot.com/2011/11/…
JD
2
tetap saja, hanya karena JVM (sayangnya, tidak ada pertanyaan) tidak dapat melakukan panggilan ekor, ini tidak berarti penghapusan panggilan ekor tidak mungkin dilakukan. Ini seolah-olah dinyatakan bahwa penghitungan floating point hanya dapat dilakukan pada komputer dengan FPU.
Ingo
22

Scala 2.7.x mendukung pengoptimalan panggilan ekor untuk rekursi mandiri (fungsi memanggil dirinya sendiri) dari metode akhir dan fungsi lokal.

Scala 2.8 mungkin hadir dengan dukungan perpustakaan untuk trampolin juga, yang merupakan teknik untuk mengoptimalkan fungsi yang saling rekursif.

Banyak informasi tentang keadaan rekursi Scala dapat ditemukan di blog Rich Dougherty .

Daniel C. Sobral
sumber
Bisakah Anda memperbarui pertanyaan tentang status skala saat ini?
om-nom-nom
@ om-nom-nom AFAIK, tidak ada yang berubah, baik di sisi Scala, maupun di sisi JVM.
Daniel C. Sobral
0

Semua sumber menunjukkan bahwa JVM tidak dapat dioptimalkan dalam kasus rekursi ekor, tetapi setelah membaca penyetelan kinerja Java (2003, O'reilly) saya menemukan penulis yang mengklaim bahwa ia dapat mencapai kinerja rekursi yang lebih besar dengan menerapkan rekursi ekor.

Anda dapat menemukan klaimnya di halaman 212 (cari 'rekursi ekor', itu harus menjadi hasil kedua). Apa yang memberi?

fthinker
sumber
IBM telah mendukung beberapa bentuk TCO dalam implementasi JVM mereka (sebagai pengoptimalan, jadi tidak ada jaminan). Mungkin penulis Java Performance tuning mengira fitur ini pada akhirnya akan diterapkan oleh semua JVM. ibm.com/developerworks/java/library/j-diag8.html
llemieng