Y combinator dan optimisasi panggilan ekor

Definisi kombinator Y dalam F # adalah

let rec y f x = f (y f) x

f berharap sebagai argumen pertama beberapa kelanjutan untuk subproblem rekursif. Menggunakan yf sebagai kelanjutan, kita melihat bahwa f akan diterapkan pada panggilan yang berurutan yang dapat kita kembangkan

let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...

Masalahnya adalah, apriori, skema ini menghalangi penggunaan optimasi panggilan ekor: memang, mungkin ada beberapa operasi yang tertunda di f, dalam hal ini kita tidak bisa hanya memutasi frame stack lokal yang terkait dengan f.

Jadi:

• di satu sisi, menggunakan kombinator Y membutuhkan kelanjutan yang berbeda secara eksplisit dari fungsi itu sendiri.
• pada saat yang lain untuk menerapkan TCO, kami ingin tidak ada operasi yang tertunda di f dan hanya memanggil f itu sendiri.

Apakah Anda tahu cara apa pun yang bisa dilakukan keduanya? Seperti Y dengan trik akumulator, atau Y dengan trik CPS? Atau argumen yang membuktikan bahwa tidak mungkin dilakukan?

Apakah Anda tahu cara apa pun yang bisa dilakukan keduanya?

Tidak, dan dengan alasan yang bagus, IMHO.

Y-combinator adalah konstruksi teoretis dan hanya diperlukan untuk membuat kalkulus lambda turing lengkap (ingat, tidak ada loop dalam kalkulus lambda, juga tidak lambda memiliki nama yang bisa kita gunakan untuk rekursi).

Dengan demikian, kombinator Y benar-benar menarik.

Tapi : Tidak ada yang benar-benar menggunakan Y-combinator untuk rekursi aktual! (Kecuali mungkin untuk bersenang-senang, untuk menunjukkan bahwa itu benar-benar berhasil.)

Optimasi tail-call, OTOH, adalah, seperti namanya, sebuah optimasi. Ia tidak menambahkan apa pun pada ekspresi bahasa, hanya karena pertimbangan praktis seperti ruang stack dan kinerja kode rekursif yang kami pedulikan.

Jadi pertanyaan Anda seperti: Apakah ada dukungan perangkat keras untuk pengurangan beta? (Pengurangan beta adalah bagaimana ekspresi lambda dikurangi, Anda tahu.) Tapi tidak ada bahasa fungsional (sejauh yang saya ketahui) mengkompilasi kode sumbernya ke representasi ekspresi lambda yang akan dikurangi beta saat runtime.

Saya tidak sepenuhnya yakin tentang jawaban ini, tetapi itu adalah yang terbaik yang bisa saya dapatkan.

Combinator y pada dasarnya malas, dalam bahasa yang ketat kemalasan harus ditambahkan secara manual melalui lambda tambahan.

let rec y f x = f (y f) x

Definisi Anda sepertinya membutuhkan kemalasan untuk mengakhiri, atau (y f)argumen tidak akan pernah selesai mengevaluasi dan harus mengevaluasi apakah menggunakannya atau tidak f. TOC dalam konteks lazy lebih rumit, dan lebih jauh lagi hasil (y f)komposisi fungsi berulang tanpa aplikasi denganx . Saya tidak yakin ini perlu mengambil O (n) memori di mana n adalah kedalaman rekursi, tapi saya ragu Anda bisa mencapai jenis TOC yang sama seperti mungkin dengan sesuatu seperti (beralih ke Haskell karena saya tidak benar-benar tahu F #)

length acc []    = acc
length acc (a:b) = length (acc+1) b 

Jika Anda belum menyadarinya, perbedaan antara foldldan foldl'di Haskell dapat memberi petunjuk pada situasi ini. foldlditulis seperti yang akan dilakukan dalam bahasa yang bersemangat. Tetapi alih-alih menjadi TOC, ini sebenarnya lebih buruk daripada foldrkarena akulator menyimpan potensi besar yang tidak dapat dievaluasi sebagian. (Ini terkait dengan mengapa foldl dan foldl 'tidak bekerja pada daftar yang tak terbatas.) Jadi dalam versi yang lebih baru dari Haskell, foldl'ditambahkan yang memaksa evaluasi akumulator setiap kali fungsi berulang untuk memastikan tidak ada pukulan besar yang dibuat. Saya yakin http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 dapat menjelaskan ini lebih baik daripada saya.