Mengapa JVM masih belum mendukung pengoptimalan tail-call?

95

Dua tahun setelah do -the-jvm-prevent-tail-call-optimizations , tampaknya ada implementasi prototipe dan MLVM telah mendaftarkan fitur tersebut sebagai "proto 80%" untuk beberapa waktu sekarang.

Apakah tidak ada minat aktif dari pihak Sun / Oracle dalam mendukung panggilan ekor atau hanya panggilan ekor yang "[...] ditakdirkan untuk menempati posisi kedua pada setiap daftar prioritas fitur [...]" seperti yang disebutkan di JVM Language Summit ?

Saya akan sangat tertarik jika seseorang telah menguji membangun MLVM dan dapat berbagi beberapa kesan tentang seberapa baik kerjanya (jika ada).

Pembaruan: Perhatikan bahwa beberapa VM seperti Avian mendukung panggilan ekor yang tepat tanpa masalah apa pun.

java language-agnostic optimization jvm tail-call-optimization soc
sumber
14
Dengan eksodus orang Sun yang dilaporkan dari Oracle, saya tidak akan berharap bahwa salah satu proyek saat ini berlanjut kecuali secara eksplisit dikatakan demikian dari Oracle :(
Thorbjørn Ravn Andersen
16
Perhatikan bahwa jawaban yang Anda terima sepenuhnya salah. Tidak ada konflik mendasar antara pengoptimalan panggilan ekor dan OOP dan, tentu saja, beberapa bahasa seperti OCaml dan F # memiliki OOP dan TCO.
JD
2
Nah, menyebut bahasa OCaml dan F # OOP adalah lelucon yang buruk di tempat pertama. Tapi ya, OOP dan TCO tidak memiliki banyak kesamaan, kecuali fakta bahwa runtime harus memeriksa bahwa metode yang dioptimalkan tidak diganti / disubclass di tempat lain.
soc
5
+1 Berasal dari latar belakang C, saya selalu berasumsi bahwa TCO diberikan dalam JVM modern mana pun. Tidak pernah terpikir oleh saya untuk benar-benar memeriksanya dan ketika saya melakukannya hasilnya mengejutkan ...
thkala
2
@soc: "kecuali fakta bahwa runtime harus memeriksa bahwa metode yang dioptimalkan tidak diganti / disubkelas di tempat lain". "Fakta" Anda benar-benar tidak masuk akal.
JD

Jawaban:

32

Mendiagnosis Kode Java: Meningkatkan Kinerja Kode Java Anda ( alt ) menjelaskan mengapa JVM tidak mendukung optimasi tail-call.

Tetapi meskipun telah diketahui dengan baik bagaimana secara otomatis mengubah fungsi tail-recursive menjadi loop sederhana, spesifikasi Java tidak mengharuskan transformasi ini dibuat. Agaknya, salah satu alasan mengapa ini bukan persyaratan adalah, secara umum, transformasi tidak dapat dilakukan secara statis dalam bahasa berorientasi objek. Sebaliknya, transformasi dari fungsi tail-recursive ke simple loop harus dilakukan secara dinamis oleh compiler JIT.

Ini kemudian memberikan contoh kode Java yang tidak akan berubah.

Jadi, seperti contoh pada Listing 3, kita tidak bisa mengharapkan compiler statis untuk melakukan transformasi tail recursion pada kode Java sambil mempertahankan semantik bahasa. Sebaliknya, kita harus mengandalkan kompilasi dinamis oleh JIT. Bergantung pada JVM, JIT mungkin melakukan ini atau tidak.

Kemudian ini memberikan tes yang dapat Anda gunakan untuk mengetahui apakah JIT Anda melakukan ini.

Secara alami, karena ini adalah kertas IBM, ini termasuk steker:

Saya menjalankan program ini dengan beberapa Java SDK, dan hasilnya mengejutkan. Berjalan di Sun's Hotspot JVM untuk versi 1.3 mengungkapkan bahwa Hotspot tidak melakukan transformasi. Pada pengaturan default, ruang tumpukan habis dalam waktu kurang dari satu detik di komputer saya. Di sisi lain, JVM IBM untuk versi 1.3 berputar tanpa masalah, menunjukkan bahwa itu memang mengubah kode dengan cara ini.

emory
sumber
62
FWIW, panggilan ekor bukan hanya tentang fungsi rekursif diri seperti yang dia maksudkan. Panggilan ekor adalah panggilan fungsi apa pun yang muncul di posisi ekor. Mereka tidak harus menjadi panggilan ke diri sendiri dan mereka tidak harus menjadi panggilan ke lokasi yang dikenal secara statis (misalnya, panggilan metode virtual). Masalah yang dia jelaskan adalah bukan masalah jika optimasi panggilan ekor dilakukan dengan benar dalam kasus umum dan, akibatnya, contohnya bekerja dengan sempurna dalam bahasa berorientasi objek yang mendukung panggilan ekor (misalnya OCaml dan F #).
JD
3
"harus dilakukan secara dinamis oleh kompilator JIT" yang berarti itu harus dilakukan oleh JVM itu sendiri, bukan oleh kompilator Java. Tapi OP menanyakan tentang JVM.
Raedwald
11
"secara umum, transformasi tidak dapat dilakukan secara statis dalam bahasa berorientasi objek." Ini adalah kutipan tentu saja, tetapi setiap kali saya melihat alasan seperti itu, saya ingin bertanya tentang angka - karena saya tidak akan terkejut jika dalam praktiknya di sebagian besar kasus, angka itu dapat ditetapkan pada waktu kompilasi.
greenoldman
5
Tautan ke artikel yang dikutip sekarang rusak, meskipun Google menyimpannya dalam cache. Lebih penting lagi, alasan penulis salah. Contoh yang diberikan dapat dioptimalkan tail-call, menggunakan statis dan bukan hanya kompilasi dinamis, jika hanya kompilator memasukkan tanda instanceofcentang untuk melihat apakah thisitu sebuah Exampleobjek (bukan subkelas Example).
Alex D
4
cukup tautkan ke webarchive web.archive.org/web/20120506085636/http://www.ibm.com/…
Suvitruf - Andrei Apanasik
30

Salah satu alasan yang pernah saya lihat di masa lalu untuk tidak mengimplementasikan TCO (dan dianggap sulit) di Java adalah bahwa model izin di JVM peka terhadap tumpukan dan dengan demikian panggilan ekor harus menangani aspek keamanan.

Saya yakin ini terbukti bukan halangan oleh Clements dan Felleisen [1] [2] dan saya cukup yakin patch MLVM yang disebutkan dalam pertanyaan tersebut juga menangani masalah tersebut.

Saya menyadari ini tidak menjawab pertanyaan Anda; hanya menambahkan informasi menarik.

  1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
  2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf
Alex Miller
sumber
1
+1. Dengarkan pertanyaan / tanggapan di akhir presentasi Brian Goetz youtube.com/watch?v=2y5Pv4yN0b0&t=3739
mcoolive
15

Mungkin Anda sudah mengetahui hal ini, tetapi fiturnya tidak sesederhana kedengarannya karena bahasa Java sebenarnya memperlihatkan pelacakan tumpukan kepada pemrogram.

Pertimbangkan program berikut:

public class Test {

    public static String f() {
        String s = Math.random() > .5 ? f() : g();
        return s;
    }

    public static String g() {
        if (Math.random() > .9) {
            StackTraceElement[] ste = new Throwable().getStackTrace();
            return ste[ste.length / 2].getMethodName();
        }
        return f();
    }

    public static void main(String[] args) {
        System.out.println(f());
    }
}

Meskipun ini memiliki "panggilan mundur", ini mungkin tidak dioptimalkan. (Jika yang dioptimalkan, masih membutuhkan pembukuan dari seluruh panggilan-tumpukan sejak semantik program bergantung pada itu.)

Pada dasarnya, ini berarti sulit untuk mendukung ini sambil tetap kompatibel ke belakang.

aioobe
sumber
17
Menemukan kesalahan dalam pikiran Anda: "memerlukan pembukuan dari seluruh tumpukan panggilan karena semantik program bergantung padanya". :-) Ini seperti "Pengecualian yang dirahasiakan". Program yang mengandalkan hal-hal seperti itu pasti akan rusak. Menurut pendapat saya, perilaku program benar-benar benar: Membuang tumpukan frame adalah inti dari panggilan ekor.
soc
4
@Marco, tetapi hampir semua metode dapat memunculkan pengecualian, yang darinya seluruh tumpukan panggilan pasti akan tersedia, bukan? Selain itu, Anda tidak dapat memutuskan sebelumnya metode mana yang secara tidak langsung akan memanggil gdalam kasus ini ... pikirkan tentang polimorfisme dan refleksi misalnya.
aioobe
2
Ini adalah efek samping yang disebabkan oleh penambahan ARM di Java 7. Ini adalah contoh bahwa Anda tidak dapat mengandalkan hal-hal yang Anda tunjukkan di atas.
soc
6
"fakta bahwa bahasa mengekspos tumpukan panggilan membuat sulit untuk menerapkan ini": apakah bahasa mengharuskan pelacakan tumpukan yang dikembalikan getStackTrace()dari metode x()yang ditampilkan kode sumbernya dipanggil dari metode y()juga menunjukkan dari mana x()dipanggil y()? Karena jika ada kebebasan maka tidak ada masalah yang nyata.
Raedwald
8
Ini hanyalah masalah kata-kata spesifikasi dari satu metode, dari "memberikan Anda semua tumpukan frame" sampai "memberikan Anda semua stackframe aktif, meninggalkan yang usang oleh panggilan ekor". Lebih jauh lagi, seseorang dapat menjadikannya sebagai saklar baris perintah atau properti sistem apakah panggilan-ekor dihormati.
Ingo
12

Java adalah bahasa yang paling tidak berfungsi yang dapat Anda bayangkan (yah, oke, mungkin tidak !) Tetapi ini akan menjadi keuntungan besar untuk bahasa JVM, seperti Scala .

Pengamatan saya adalah bahwa menjadikan JVM sebagai platform untuk bahasa lain sepertinya tidak pernah berada di urutan teratas daftar prioritas untuk Sun dan saya kira, sekarang untuk Oracle.

oxbow_lakes
sumber
16
@ Thorbjørn - Saya menulis sebuah program untuk memprediksi apakah program tertentu akan berhenti dalam waktu yang terbatas. Aku butuh waktu lama !
oxbow_lakes
3
DASAR-DASAR pertama yang saya gunakan tidak memiliki fungsi, melainkan GOSUB dan RETURN. Menurut saya, LOLCODE juga tidak berfungsi dengan baik (dan Anda dapat menerimanya dalam dua pengertian).
David Thornley
1
@ David, fungsional! = Memiliki fungsi.
Thorbjørn Ravn Andersen
2
@ Thorbjørn Ravn Andersen: Tidak, tapi itu semacam prasyarat, bukan?
David Thornley
3
"menjadikan JVM sebagai platform untuk bahasa lain sepertinya tidak pernah menjadi yang teratas dalam daftar prioritas untuk Sun". Mereka berusaha lebih keras untuk menjadikan JVM sebagai platform untuk bahasa dinamis daripada yang mereka lakukan untuk bahasa fungsional.
JD