Ketika tidak ada TCO, kapan harus khawatir meniup tumpukan?

Setiap kali ada diskusi tentang bahasa pemrograman baru yang menargetkan JVM, pasti ada orang mengatakan hal-hal seperti:

"JVM tidak mendukung optimisasi panggilan balik, jadi saya memprediksi banyak tumpukan yang meledak"

Ada ribuan variasi pada tema itu.

Sekarang saya tahu bahwa beberapa bahasa, seperti Clojure misalnya, memiliki konstruksi berulang khusus yang dapat Anda gunakan.

Yang tidak saya mengerti adalah: seberapa serius kurangnya optimasi tail-call? Kapan saya harus khawatir?

Sumber utama kebingungan saya mungkin berasal dari fakta bahwa Jawa adalah salah satu bahasa paling sukses yang pernah ada dan beberapa bahasa JVM tampaknya berjalan cukup baik. Bagaimana mungkin jika kekurangan TCO benar-benar dari setiap kekhawatiran?

Pertimbangkan ini, katakanlah kita menyingkirkan semua loop di Jawa (penulis kompiler sedang mogok atau sesuatu). Sekarang kita ingin menulis faktorial, jadi kita mungkin benar seperti ini

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

Sekarang kami merasa cukup pintar, kami telah berhasil menulis faktorial kami bahkan tanpa loop! Tetapi ketika kami menguji, kami melihat bahwa dengan angka yang cukup masuk akal, kami mendapatkan kesalahan stackoverflow karena tidak ada TCO.

Di Java asli ini bukan masalah. Jika kita pernah memiliki algoritma rekursif ekor, kita dapat mengubahnya menjadi satu lingkaran dan baik-baik saja. Namun, bagaimana dengan bahasa tanpa loop? Maka Anda disemprot saja. Itu sebabnya clojure memiliki inirecur bentuk , tanpa itu, itu bahkan tidak turing lengkap (Tidak ada cara untuk melakukan loop tak terbatas).

Kelas bahasa fungsional yang menargetkan JVM, Frege, Kawa (Skema), Clojure selalu berusaha untuk menangani kurangnya panggilan ekor, karena dalam bahasa ini, TC adalah cara idiomatis untuk melakukan loop! Jika diterjemahkan ke Skema, faktorial di atas akan menjadi faktorial yang baik. Akan sangat merepotkan jika mengulang 5000 kali membuat program Anda macet. Ini dapat diselesaikan, dengan recurbentuk khusus, anotasi yang mengisyaratkan mengoptimalkan panggilan sendiri, trampolining, apa pun. Tetapi mereka semua memaksa baik kinerja hit atau pekerjaan yang tidak perlu pada programmer.

Sekarang Java juga tidak bebas, karena masih ada lagi untuk TCO kemudian hanya rekursi, bagaimana dengan fungsi rekursif yang saling menguntungkan? Mereka tidak dapat langsung diterjemahkan ke loop, tetapi masih tidak dioptimalkan oleh JVM. Ini membuatnya sangat tidak menyenangkan untuk mencoba menulis algoritma menggunakan rekursi timbal balik menggunakan Java karena jika Anda ingin kinerja / kisaran yang layak Anda harus melakukan sihir gelap untuk membuatnya cocok dengan loop.

Jadi, secara ringkas, ini bukan masalah besar untuk banyak kasus. Sebagian besar panggilan buntut hanya melanjutkan satu kedalaman stackframe, dengan hal-hal seperti

return foo(bar, baz); // foo is just a simple method

atau rekursi. Namun, untuk kelas TC yang tidak cocok dengan ini, setiap bahasa JVM merasakan sakit.

Namun, ada alasan yang layak mengapa kami belum memiliki TCO. JVM memberi kita tumpukan jejak. Dengan TCO kita secara sistematis menghilangkan stackframe yang kita tahu "dikutuk", tetapi JVM mungkin sebenarnya menginginkan ini nanti untuk sebuah stacktrace! Katakanlah kita menerapkan FSM seperti ini, di mana setiap negara bagian memanggil yang berikutnya. Kami akan menghapus semua catatan status sebelumnya sehingga traceback akan menunjukkan kepada kami status apa, tetapi tidak apa pun tentang bagaimana kami sampai di sana.

Selain itu, dan lebih penting lagi, banyak verifikasi bytecode berbasis stack, menghilangkan hal yang memungkinkan kita memverifikasi bytecode bukanlah prospek yang menyenangkan. Antara ini dan fakta bahwa Java memiliki loop, TCO terlihat seperti sedikit lebih banyak masalah daripada nilainya bagi para insinyur JVM.

Optimalisasi panggilan ekor terutama penting karena rekursi ekor. Namun, ada argumen mengapa itu sebenarnya baik bahwa JVM tidak mengoptimalkan panggilan ekor: Karena TCO menggunakan kembali bagian dari tumpukan, jejak tumpukan dari pengecualian tidak akan lengkap, sehingga membuat proses debug sedikit lebih sulit.

Ada beberapa cara untuk mengatasi keterbatasan JVM:

1. Rekursi ekor sederhana dapat dioptimalkan ke loop oleh kompiler.
2. Jika program dalam gaya kelanjutan-lewat, maka sepele untuk menggunakan "trampolining". Di sini, suatu fungsi tidak mengembalikan hasil akhir, tetapi suatu kelanjutan yang kemudian dieksekusi di luar. Teknik ini memungkinkan penulis kompiler untuk memodelkan aliran kontrol kompleks yang sewenang-wenang.

Ini mungkin membutuhkan contoh yang lebih besar. Pertimbangkan bahasa dengan penutupan (mis. JavaScript atau yang serupa). Kita dapat menulis sebagai faktorial

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Sekarang kita dapat mengembalikannya sebagai balasan:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

Ini sekarang bekerja di ruang stack konstan, yang agak konyol karena itu ekor-rekursif pula. Namun, teknik ini mampu meratakan semua panggilan ekor ke ruang stack konstan. Dan jika program ini dalam CPS, maka ini berarti bahwa callstack secara keseluruhan konstan (dalam CPS, setiap panggilan adalah panggilan ekor).

Kerugian utama dari teknik ini adalah bahwa itu jauh lebih sulit untuk di-debug, sedikit lebih sulit untuk diimplementasikan, dan kurang berkinerja - lihat semua penutupan dan tipuan yang saya gunakan.

Untuk alasan ini, akan jauh lebih baik jika VM menerapkan op-language panggilan ekor seperti Java yang memiliki alasan yang baik untuk tidak mendukung panggilan ekor tidak harus menggunakannya.

Sebagian besar panggilan dalam suatu program adalah panggilan ekor. Setiap subrutin memiliki panggilan terakhir, sehingga setiap subrutin memiliki setidaknya satu panggilan ekor. Buntut panggilan memiliki karakteristik kinerja GOTOtetapi keamanan panggilan subrutin.

Memiliki Panggilan Ekor yang Benar memungkinkan Anda menulis program yang tidak dapat Anda tulis. Ambil, misalnya, mesin negara. Mesin negara dapat sangat langsung dilaksanakan dengan meminta setiap negara bagian menjadi subrutin dan setiap transisi negara bagian menjadi panggilan subrutin. Dalam hal ini, Anda beralih dari satu negara ke negara lain, dengan melakukan panggilan demi panggilan, dan Anda sebenarnya tidak pernah kembali! Tanpa Panggilan Ekor yang Benar, Anda akan segera meniup tumpukan.

Tanpa PTC, Anda harus menggunakan GOTOatau Trampolin atau pengecualian sebagai aliran kontrol atau sesuatu seperti itu. Ini jauh lebih jelek, dan bukan representasi langsung 1: 1 dari mesin negara.

(Perhatikan bagaimana saya secara cerdik menghindari penggunaan contoh "loop" yang membosankan. Ini adalah contoh di mana PTC berguna bahkan dalam bahasa dengan loop.)

Saya sengaja menggunakan istilah "Panggilan Ekor yang Benar" di sini alih-alih TCO. TCO adalah pengoptimalan kompiler. PTC adalah fitur bahasa yang mengharuskan setiap kompiler untuk melakukan TCO.

"JVM tidak mendukung optimisasi panggilan balik, jadi saya memprediksi banyak tumpukan yang meledak"

Siapa pun yang mengatakan ini (1) tidak memahami pengoptimalan panggilan-ekor, atau (2) tidak memahami JVM, atau (3) keduanya.

Saya akan mulai dengan definisi panggilan ekor dari Wikipedia (jika Anda tidak menyukai Wikipedia, berikut ini alternatifnya ):

Dalam ilmu komputer, panggilan ekor adalah panggilan subrutin yang terjadi di dalam prosedur lain sebagai tindakan terakhirnya; itu dapat menghasilkan nilai kembali yang kemudian segera dikembalikan oleh prosedur panggilan

Dalam kode di bawah ini, panggilan untuk bar()adalah panggilan ekor dari foo():

private void foo() {
    // do something
    bar()
}

Optimasi panggilan ekor terjadi ketika implementasi bahasa, melihat panggilan ekor, tidak menggunakan doa metode normal (yang menciptakan bingkai tumpukan), tetapi malah membuat cabang. Ini adalah pengoptimalan karena bingkai tumpukan memerlukan memori, dan ini membutuhkan siklus CPU untuk mendorong informasi (seperti alamat pengirim) ke bingkai, dan karena pasangan panggilan / kembali diasumsikan membutuhkan lebih banyak siklus CPU daripada lompatan tanpa syarat.

TCO sering diterapkan pada rekursi, tetapi itu bukan satu-satunya penggunaannya. Juga tidak berlaku untuk semua rekursi. Kode rekursif sederhana untuk menghitung faktorial, misalnya, tidak dapat dioptimalkan ekor-panggilan, karena hal terakhir yang terjadi dalam fungsi adalah operasi multiplikasi.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

Untuk menerapkan optimasi panggilan ekor, Anda memerlukan dua hal:

• Platform yang mendukung percabangan selain panggilan subtroutine.
• Penganalisa statis yang dapat menentukan apakah optimasi panggilan ekor dimungkinkan.

Itu dia. Seperti yang telah saya catat di tempat lain, JVM (seperti arsitektur Turing-complete lainnya) memiliki goto. Itu kebetulan memiliki kebersamaan tanpa syarat , tetapi fungsi dapat dengan mudah diimplementasikan menggunakan cabang bersyarat.

Bagian analisis statis adalah yang rumit. Dalam satu fungsi, tidak ada masalah. Misalnya, inilah fungsi Scala rekursif ekor untuk menjumlahkan nilai dalam List:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

Fungsi ini berubah menjadi bytecode berikut:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Perhatikan goto 0di bagian akhir. Sebagai perbandingan, fungsi Java yang setara (yang harus menggunakan a Iteratoruntuk meniru perilaku memecah daftar Scala menjadi kepala dan ekor) berubah menjadi bytecode berikut. Perhatikan bahwa dua operasi terakhir sekarang merupakan invoke , diikuti oleh pengembalian eksplisit dari nilai yang dihasilkan oleh doa rekursif.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

Optimasi panggilan ekor dari fungsi tunggal sepele: compiler dapat melihat bahwa tidak ada kode yang menggunakan hasil dari panggilan, sehingga dapat menggantikan Invoke dengan goto.

Di mana hidup menjadi sulit adalah jika Anda memiliki banyak metode. Instruksi percabangan JVM, tidak seperti pada prosesor tujuan umum seperti 80x86, terbatas pada metode tunggal. Ini masih relatif mudah jika Anda memiliki metode pribadi: kompiler bebas untuk mengikutsertakan metode-metode yang sesuai, sehingga dapat mengoptimalkan panggilan ekor (jika Anda bertanya-tanya bagaimana ini bisa bekerja, pertimbangkan metode umum yang menggunakanswitch untuk mengontrol perilaku). Anda bahkan dapat memperluas teknik ini ke beberapa metode publik di kelas yang sama: kompiler inline badan metode, menyediakan metode jembatan publik, dan panggilan internal berubah menjadi lompatan.

Tapi, model ini rusak ketika Anda mempertimbangkan metode publik di kelas yang berbeda, terutama mengingat antarmuka dan classloader. Kompilator level sumber tidak memiliki cukup pengetahuan untuk mengimplementasikan optimisasi panggilan balik. Namun, tidak seperti implementasi "bare-metal", * JVM (memang memiliki informasi untuk melakukan ini, dalam bentuk kompiler Hotspot (setidaknya, kompiler ex-Sun tidak). Saya tidak tahu apakah itu benar-benar melakukan optimisasi panggilan ekor, dan curiga tidak, tetapi itu bisa .

Yang membawa saya ke bagian kedua dari pertanyaan Anda, yang saya akan ulangi sebagai "haruskah kita peduli?"

Jelas, jika bahasa Anda menggunakan rekursi sebagai satu-satunya primitif untuk iterasi, Anda peduli. Tetapi, bahasa yang membutuhkan fitur ini dapat mengimplementasikannya; satu-satunya masalah adalah apakah kompiler untuk bahasa tersebut dapat menghasilkan kelas yang dapat memanggil dan dipanggil oleh kelas Java sewenang-wenang.

Di luar kasus itu, saya akan mengundang downvotes dengan mengatakan bahwa itu tidak relevan. Sebagian besar kode rekursif yang pernah saya lihat (dan saya telah bekerja dengan banyak proyek grafik) tidak dapat dioptimalkan . Seperti faktorial sederhana, ia menggunakan rekursi untuk membangun keadaan, dan operasi ekor adalah kombinasi.

Untuk kode yang tail-call dioptimalkan, seringkali mudah untuk menerjemahkan kode itu ke dalam bentuk yang dapat diubah. Sebagai contoh, sum()fungsi yang saya tunjukkan sebelumnya dapat digeneralisasi sebagai foldLeft(). Jika Anda melihat sumbernya , Anda akan melihat bahwa itu sebenarnya diimplementasikan sebagai operasi berulang. Jörg W Mittag memiliki contoh mesin negara diimplementasikan melalui panggilan fungsi; ada banyak implementasi mesin negara yang efisien (dan dapat dipelihara) yang tidak bergantung pada pemanggilan fungsi yang diterjemahkan ke dalam lompatan.

Saya akan selesai dengan sesuatu yang sangat berbeda. Jika Anda Google jalan dari catatan kaki di SICP, Anda mungkin berakhir di sini . Saya pribadi menemukan bahwa tempat yang jauh lebih menarik daripada mengganti kompiler saya JSRdengan JUMP.