Keterbatasan apa yang diberlakukan JVM pada optimasi panggilan ekor

Clojure tidak melakukan optimasi panggilan ekor sendiri: ketika Anda memiliki fungsi rekursif ekor dan Anda ingin mengoptimalkannya, Anda harus menggunakan formulir khusus recur. Demikian pula, jika Anda memiliki dua fungsi yang saling rekursif, Anda dapat mengoptimalkannya hanya dengan menggunakan trampoline.

Scala compiler dapat melakukan TCO untuk fungsi rekursif, tetapi tidak untuk dua fungsi rekursif yang saling menguntungkan.

Setiap kali saya membaca tentang keterbatasan ini, mereka selalu dianggap berasal dari batasan intrinsik dengan model JVM. Saya tidak tahu banyak tentang kompiler, tapi ini sedikit membingungkan saya. Biarkan saya ambil contohnya Programming Scala. Di sini fungsinya

def approximate(guess: Double): Double =
  if (isGoodEnough(guess)) guess
  else approximate(improve(guess))

diterjemahkan ke dalam

0: aload_0
1: astore_3
2: aload_0
3: dload_1
4: invokevirtual #24; //Method isGoodEnough:(D)Z
7: ifeq
10: dload_1
11: dreturn
12: aload_0
13: dload_1
14: invokevirtual #27; //Method improve:(D)D
17: dstore_1
18: goto 2

Jadi, pada level bytecode, kita hanya perlu goto. Dalam hal ini, sebenarnya, kerja keras dilakukan oleh kompiler.

Fasilitas apa dari mesin virtual yang mendasarinya yang memungkinkan kompiler menangani TCO dengan lebih mudah?

Sebagai catatan, saya tidak berharap mesin yang sebenarnya jauh lebih pintar daripada JVM. Namun, banyak bahasa yang mengkompilasi ke kode asli, seperti Haskell, tampaknya tidak memiliki masalah dengan mengoptimalkan panggilan ekor (well, Haskell kadang-kadang bisa karena kemalasan, tapi itu masalah lain).

Sekarang, saya tidak tahu banyak tentang Clojure dan sedikit tentang Scala, tetapi saya akan mencobanya.

Pertama, kita perlu membedakan antara ekor-CALL dan ekor-RECURSION. Rekursi ekor memang agak mudah untuk diubah menjadi satu lingkaran. Dengan panggilan ekor, jauh lebih sulit untuk mustahil dalam kasus umum. Anda perlu tahu apa yang dipanggil, tetapi dengan polimorfisme dan / atau fungsi kelas satu, Anda jarang tahu itu, sehingga kompiler tidak dapat mengetahui cara mengganti panggilan. Hanya pada saat runtime Anda tahu kode target dan dapat melompat ke sana tanpa mengalokasikan bingkai tumpukan lain. Sebagai contoh, fragmen berikut memiliki panggilan ekor dan tidak memerlukan ruang stack ketika dioptimalkan dengan benar (termasuk TCO), namun tidak dapat dihilangkan ketika mengkompilasi untuk JVM:

function forward(obj: Callable<int, int>, arg: int) =
    let arg1 <- arg + 1 in obj.call(arg1)

Meskipun ini sedikit tidak efisien di sini, ada gaya pemrograman keseluruhan (seperti Continuation Passing Style atau CPS) yang memiliki banyak panggilan ekor dan jarang pernah kembali. Melakukan itu tanpa TCO penuh berarti Anda hanya dapat menjalankan sedikit kode sebelum kehabisan ruang stack.

Fasilitas apa dari mesin virtual yang mendasarinya yang memungkinkan kompiler menangani TCO dengan lebih mudah?

Instruksi panggilan ekor, seperti di Lua 5.1 VM. Contoh Anda tidak menjadi jauh lebih sederhana. Milik saya menjadi seperti ini:

push arg
push 1
add
load obj
tailcall Callable.call
// implicit return; stack frame was recycled

Sebagai seorang sidenote, saya tidak berharap mesin yang sebenarnya jauh lebih pintar daripada JVM.

Anda benar, mereka tidak. Bahkan, mereka kurang pintar dan bahkan tidak tahu (banyak) tentang hal-hal seperti stack frames. Itulah mengapa seseorang dapat menarik trik seperti menggunakan kembali ruang stack dan melompat ke kode tanpa mendorong alamat pengirim.

Clojure dapat melakukan optimasi otomatis rekursi ekor menjadi loop: tentu saja dimungkinkan untuk melakukan ini pada JVM saat Scala membuktikan.

Sebenarnya itu adalah keputusan desain untuk tidak melakukan ini - Anda harus secara eksplisit menggunakan recurformulir khusus jika Anda menginginkan fitur ini. Lihat utas surat Re: Mengapa tidak ada optimasi panggilan ekor di grup google Clojure.

Pada JVM saat ini, satu-satunya hal yang tidak mungkin dilakukan adalah optimasi panggilan ekor antara fungsi yang berbeda (saling rekursi). Ini tidak terlalu rumit untuk diimplementasikan (bahasa lain seperti Skema telah memiliki fitur ini dari awal) tetapi akan membutuhkan perubahan pada spesifikasi JVM. Misalnya, Anda harus mengubah aturan tentang mempertahankan tumpukan panggilan fungsi yang lengkap.

Iterasi JVM di masa mendatang kemungkinan akan mendapatkan kemampuan ini, meskipun mungkin sebagai opsi agar perilaku yang kompatibel dengan mundur untuk kode lama tetap dipertahankan. Katakanlah, Fitur Pratinjau di Geeknizer mencantumkan ini untuk Java 9:

Menambahkan panggilan ekor dan kelanjutan ...

^{Tentu saja, roadmap masa depan selalu berubah.}

Ternyata, itu bukan masalah besar. Dalam lebih dari 2 tahun coding Clojure, saya tidak pernah mengalami situasi di mana kurangnya TCO adalah sebuah masalah. Alasan utama untuk ini adalah:

• Anda sudah bisa mendapatkan rekursi ekor cepat untuk 99% kasus umum dengan recuratau loop. Kasus rekursi timbal balik cukup langka dalam kode normal
• Bahkan ketika Anda membutuhkan rekursi timbal balik, seringkali kedalaman rekursi cukup dangkal sehingga Anda bisa melakukannya di atas tumpukan tanpa TCO. TCO hanyalah sebuah "optimasi" ....
• Dalam kasus yang sangat jarang terjadi di mana Anda membutuhkan beberapa bentuk rekursi timbal-balik yang tidak mengonsumsi, ada banyak alternatif lain yang dapat mencapai tujuan yang sama: urutan malas, trampolin dll.

Sebagai seorang sidenote, saya tidak berharap mesin yang sebenarnya jauh lebih pintar daripada JVM.

Ini bukan tentang menjadi lebih pintar, tetapi tentang menjadi berbeda. Sampai saat ini, JVM dirancang dan dioptimalkan secara eksklusif untuk satu bahasa (Java, tentu saja), yang memiliki memori yang sangat ketat dan model panggilan.

Tidak hanya tidak ada gotoatau pointer, bahkan tidak ada cara untuk memanggil fungsi 'telanjang' (yang bukan metode yang didefinisikan dalam kelas).

Secara konseptual, ketika menargetkan JVM, penulis kompiler harus bertanya "bagaimana saya bisa mengekspresikan konsep ini dalam istilah Java?". Dan jelas, tidak ada cara untuk mengekspresikan TCO di Jawa.

Perhatikan bahwa ini tidak dilihat sebagai kegagalan JVM, karena mereka tidak diperlukan untuk Java. Segera setelah Java membutuhkan beberapa fitur seperti ini, ia ditambahkan ke JVM.

Baru-baru ini pihak berwenang Jawa mulai menganggap serius JVM sebagai platform untuk bahasa non-Jawa, sehingga sudah mendapatkan beberapa dukungan untuk fitur yang tidak memiliki Java yang setara. Yang paling dikenal adalah pengetikan dinamis, yang sudah ada di JVM tetapi tidak di Java.

Jadi, pada level bytecode, kita hanya perlu kebagian. Dalam hal ini, sebenarnya, kerja keras dilakukan oleh kompiler.

Pernahkah Anda memperhatikan bahwa alamat metode dimulai dengan 0? Bahwa semua metode set dimulai dengan 0? JVM tidak memungkinkan seseorang untuk melompat keluar dari suatu metode.

Saya tidak tahu apa yang akan terjadi dengan cabang dengan offset di luar metode dimuat oleh java - mungkin itu akan ditangkap oleh bytecode verifier, mungkin itu akan menghasilkan pengecualian, dan mungkin itu benar-benar akan melompat keluar dari metode.

Masalahnya, tentu saja, adalah bahwa Anda tidak dapat benar-benar menjamin di mana metode lain dari kelas yang sama akan menjadi, apalagi metode kelas lain. Saya ragu JVM membuat jaminan tentang di mana ia akan memuat metode, meskipun saya akan senang bisa diperbaiki.