Mengapa Java tidak memiliki optimasi untuk rekursi ekor sama sekali?

92

Dari apa yang saya baca: Alasannya adalah karena tidak mudah untuk menentukan metode mana yang akan benar-benar disebut karena kita memiliki warisan.

Namun, mengapa Java setidaknya tidak memiliki optimisasi rekursi ekor untuk metode statis dan menerapkan cara yang tepat untuk memanggil metode statis dengan kompiler?

Mengapa Java tidak memiliki dukungan sama sekali untuk rekursi ekor?

Saya tidak yakin apakah ada kesulitan di sini sama sekali.

Mengenai duplikat yang disarankan , seperti yang dijelaskan oleh Jörg W Mittag 1 :

  • Pertanyaan lain bertanya tentang TCO, yang ini tentang TRE. TRE jauh lebih sederhana daripada TCO.
  • Selain itu, pertanyaan lain bertanya tentang batasan apa yang dikenakan JVM pada implementasi bahasa yang ingin dikompilasi ke JVM, pertanyaan ini menanyakan tentang Java, yang merupakan satu bahasa yang tidak dibatasi oleh JVM, karena spesifikasi JVM dapat diubah oleh orang yang sama yang mendesain Java.
  • Dan terakhir, bahkan tidak ada batasan dalam JVM tentang TRE, karena JVM memang memiliki intra-metode GOTO, yang merupakan semua yang diperlukan untuk TRE

1 Pemformatan ditambahkan untuk memanggil poin yang dibuat.

java compiler recursion InformedA
sumber
26
Mengutip Eric Lippert : "Fitur tidak murah; mereka sangat mahal dan mereka tidak boleh hanya membenarkan biaya mereka sendiri, mereka harus membenarkan biaya peluang karena tidak melakukan seratus fitur lain yang bisa kita lakukan dengan anggaran itu." Java dirancang sebagian untuk menarik pengembang C / C ++ dan optimisasi rekursi ekor tidak dijamin dalam bahasa tersebut.
Doval
5
Koreksi saya jika saya salah, tetapi apakah Eric Lippert adalah perancang untuk C # yang memiliki optimasi rekursi ekor?
Diinformasikan pada
1
Dia ada di tim kompiler C #, ya.
Doval
10
Dari apa yang saya mengerti, JIT mungkin melakukannya , jika kondisi tertentu terpenuhi , mungkin. Jadi dalam praktiknya Anda tidak bisa mengandalkannya. Tetapi apakah C # memiliki atau tidak memilikinya tidak penting bagi poin Eric.
Doval
4
@InstructedA Jika Anda menggali sedikit lebih dalam, Anda dapat melihat bahwa itu tidak pernah dilakukan di kompiler JIT 32-bit. JIT 64-bit lebih baru dan lebih cerdas dalam banyak hal. Kompiler eksperimental yang bahkan lebih baru (baik untuk 32 dan 64-bit) lebih cerdas lagi, dan akan mendukung optimisasi rekursi ekor di IL yang tidak secara eksplisit memintanya. Ada hal lain yang perlu Anda pertimbangkan - kompiler JIT tidak punya banyak waktu. Mereka sangat dioptimalkan untuk kecepatan - aplikasi yang mungkin membutuhkan waktu berjam-jam untuk dikompilasi dalam C ++ masih harus beralih dari IL ke asli dalam beberapa ratus ms, paling banyak (setidaknya sebagian).
Luaan

Jawaban:

132

Seperti yang dijelaskan oleh Brian Goetz (Arsitek Bahasa Jawa di Oracle) dalam video ini :

di kelas jdk [...] ada sejumlah metode sensitif keamanan yang mengandalkan penghitungan frame tumpukan antara kode pustaka jdk dan kode panggilan untuk mengetahui siapa yang memanggil mereka.

Apa pun yang mengubah jumlah bingkai pada tumpukan akan merusak ini dan akan menyebabkan kesalahan. Dia mengakui ini adalah alasan yang bodoh, dan sejak itu para pengembang JDK telah mengganti mekanisme ini.

Lebih lanjut ia menyebutkan bahwa itu bukan prioritas, tetapi rekursi ekor itu

pada akhirnya akan selesai.

NB Ini berlaku untuk HotSpot dan OpenJDK, VM lain mungkin berbeda.

govan
sumber
7
Saya kagum ada jawaban yang agak kering dan kering seperti ini! Tetapi sepertinya jawabannya - itu mungkin sekarang, untuk alasan teknis yang sudah ketinggalan zaman belum dilakukan, dan sekarang kita tunggu seseorang memutuskan apakah itu cukup penting untuk diterapkan.
BrianH
1
Mengapa tidak menerapkan solusi? Seperti label-goto di bawah selimut yang hanya melompat ke bagian atas pemanggilan metode dengan nilai baru untuk argumen? Ini akan menjadi optimasi waktu kompilasi dan tidak perlu menggeser frame tumpukan atau menyebabkan pelanggaran keamanan.
James Watkins
2
Akan jauh lebih baik bagi kami jika Anda atau orang lain di sini dapat menggali lebih dalam dan memberikan secara khusus apa "metode sensitif keamanan" itu. Terima kasih!
InformedA
3
@InstructedA - lihat securingjava.com/chapter-three/chapter-three-6.html yang berisi penjelasan rinci tentang bagaimana sistem Manajer Keamanan Java bekerja sekitar rilis Java 2.
Jules
3
Satu solusi adalah dengan menggunakan bahasa JVM lain. Scala, misalnya, melakukan ini di kompiler, bukan saat runtime.
James Moore
24

Java tidak memiliki optimasi panggilan ekor untuk alasan yang sama sebagian besar bahasa imperatif tidak memilikinya. Loop imperatif adalah gaya bahasa yang disukai, dan programmer dapat mengganti rekursi ekor dengan loop imperatif. Kompleksitas tidak sepadan untuk fitur yang penggunaannya tidak disarankan karena masalah gaya.

Hal ini di mana pemrogram ingin kadang-kadang menulis dalam gaya FP dalam bahasa yang tidak penting hanya menjadi populer dalam 10 tahun terakhir, setelah komputer mulai melakukan penskalaan dalam core bukan GHz. Bahkan sekarang, itu tidak sepopuler itu. Jika saya menyarankan mengganti loop imperatif dengan rekursi ekor di tempat kerja, setengah dari peninjau kode akan tertawa dan setengah lainnya akan memberikan tampilan bingung. Bahkan dalam pemrograman fungsional, Anda biasanya menghindari rekursi ekor kecuali konstruksi lain seperti fungsi tingkat tinggi tidak pas bersih.

Karl Bielefeldt
sumber
36
Jawaban ini sepertinya tidak benar. Hanya karena rekursi ekor tidak sepenuhnya dibutuhkan bukan berarti itu tidak akan berguna. Solusi rekursif seringkali lebih mudah dipahami daripada iterasi, tetapi kurangnya panggilan ekor berarti algoritme rekursif menjadi tidak benar untuk ukuran masalah besar yang akan menghancurkan tumpukan. Ini tentang kebenaran, bukan kinerja (kecepatan perdagangan untuk kesederhanaan sering sepadan). Sebagai jawaban yang benar mencatat, kurangnya panggilan ekor adalah karena model keamanan aneh mengandalkan jejak tumpukan, bukan kefanatikan imperatif.
amon
4
@amon James Gosling pernah berkata bahwa dia tidak akan menambahkan fitur ke Java kecuali beberapa orang memintanya , dan baru kemudian dia akan mempertimbangkannya . Jadi saya tidak akan terkejut jika bagian dari jawabannya benar - benar adalah "Anda selalu bisa menggunakan forloop" (dan juga untuk fungsi kelas vs objek). Saya tidak akan menyebutnya "imperatif fanatik" tetapi saya tidak berpikir itu akan menjadi permintaan yang sangat tinggi pada tahun 1995 ketika perhatian utama mungkin kecepatan Jawa, dan kurangnya obat generik.
Doval
7
@amon, model keamanan menganggap saya sebagai alasan yang sah untuk tidak menambahkan TCO ke bahasa yang sudah ada, tetapi alasan yang buruk untuk tidak mendesainnya ke dalam bahasa di tempat pertama. Anda tidak membuang fitur yang terlihat oleh programmer untuk memasukkan fitur minor di belakang layar. "Mengapa Java 8 tidak memiliki TCO" adalah pertanyaan yang sangat berbeda dari "Mengapa Java 1.0 tidak memiliki TCO?" Saya menjawab yang terakhir.
Karl Bielefeldt
3
@rwong, Anda dapat mengubah setiap fungsi rekursif untuk satu berulang. (Jika saya boleh, saya telah menulis contoh di sini )
alain
3
@ ZanLynx itu tergantung pada jenis masalah. Misalnya Pola pengunjung dapat mengambil manfaat dari TCO (tergantung pada spesifikasi struktur dan pengunjung) sementara tidak ada hubungannya dengan FP. Pergi melalui mesin negara serupa meskipun transformasi menggunakan trampolin tampaknya sedikit lebih alami (tergantung pada masalah). Juga sementara Anda dapat, secara teknis, menerapkan pohon menggunakan loop saya percaya konsensus adalah bahwa rekursi jauh lebih alami (serupa untuk DFS meskipun dalam hal ini Anda dapat menghindari rekursi karena batas stack bahkan dengan TCO).
Maciej Piechotka
5

Java tidak memiliki optimasi panggilan tinggi karena JVM tidak memiliki bytecode untuk panggilan ekor (ke beberapa pointer fungsi yang tidak diketahui secara statis , misalnya metode dalam beberapa vtable).

Sepertinya karena alasan sosial (dan mungkin teknis), menambahkan operasi bytecode baru di JVM (yang akan membuatnya tidak kompatibel dengan versi sebelumnya dari JVM) sangat sulit bagi pemilik spesifikasi JVM.

Alasan teknis untuk tidak menambahkan bytecode baru dalam spesifikasi JVM termasuk fakta bahwa implementasi JVM kehidupan nyata adalah perangkat lunak yang sangat rumit (misalnya karena banyak optimasi JIT yang dilakukannya).

Tail Tail ke beberapa fungsi yang tidak diketahui membutuhkan penggantian frame stack saat ini dengan yang baru, dan operasi itu harusnya ada di JVM (ini bukan hanya masalah mengubah kompiler pembuat bytecode).

Basile Starynkevitch
sumber
17
Pertanyaannya bukan tentang panggilan ekor, ini tentang rekursi ekor. Dan pertanyaannya bukan tentang bahasa bytecode JVM, ini tentang bahasa pemrograman Java, yang merupakan bahasa yang sama sekali berbeda. Scala mengkompilasi bytecode JVM (antara lain) dan memiliki eliminasi ekor-rekursi. Implementasi skema pada JVM memiliki panggilan ekor yang tepat. Java 7 (JVM Spec, 3rd Ed.) Menambahkan bytecode baru. IBM J9 JVM melakukan TCO bahkan tanpa perlu bytecode khusus.
Jörg W Mittag
1
@ JörgWMittag: Itu benar, tetapi kemudian, saya ingin tahu apakah benar benar bahwa bahasa pemrograman Java tidak memiliki panggilan ekor yang tepat. Mungkin lebih akurat untuk menyatakan bahwa bahasa pemrograman Java tidak harus memiliki panggilan ekor yang tepat, karena tidak ada dalam spesifikasi yang mengamanatkannya. (Yaitu: Saya tidak yakin bahwa apa pun dalam spesifikasi itu sebenarnya melarang implementasi dari menghilangkan panggilan ekor. Ini tidak disebutkan.)
ruakh
4

Kecuali jika suatu bahasa memiliki sintaks khusus untuk membuat panggilan ekor (rekursif atau sebaliknya) dan kompiler akan mengomel ketika panggilan ekor diminta tetapi tidak dapat dihasilkan, optimasi "opsional" panggilan ekor atau pengulangan ekor akan menghasilkan situasi di mana sebuah karya kode mungkin memerlukan kurang dari 100 byte tumpukan pada satu mesin, tetapi lebih dari 100.000.000 byte tumpukan pada yang lain. Perbedaan seperti itu harus dianggap kualitatif daripada sekadar kuantitatif.

Diharapkan mesin mungkin memiliki ukuran tumpukan yang berbeda, dan dengan demikian selalu memungkinkan kode untuk bekerja pada satu mesin tetapi meniup tumpukan pada yang lain. Namun, secara umum, kode yang akan bekerja pada satu mesin bahkan ketika stack secara artifisial cenderung akan bekerja pada semua mesin dengan ukuran stack "normal". Namun, jika metode yang berulang 1.000.000 dalam adalah tail-call dioptimalkan pada satu mesin tetapi tidak pada yang lain, eksekusi pada mesin sebelumnya kemungkinan akan bekerja bahkan jika tumpukannya sangat kecil, dan gagal pada yang terakhir meskipun tumpukannya sangat besar. .

supercat
sumber
2

Saya pikir rekursi panggilan ekor tidak digunakan di Jawa terutama karena hal itu akan mengubah jejak stack dan karenanya membuat debugging program menjadi lebih sulit. Saya pikir salah satu tujuan utama Java adalah untuk memungkinkan programmer untuk dengan mudah men-debug kode mereka, dan stack tracing sangat penting untuk melakukan itu terutama di lingkungan pemrograman yang sangat berorientasi objek. Karena iterasi dapat digunakan sebagai gantinya, panitia bahasa pasti mengira itu tidak layak menambahkan rekursi ekor.

annoying_squid
sumber