Mengapa fungsi di Ocaml / F # tidak rekursif secara default?

104

Mengapa fungsi di F # dan Ocaml (dan mungkin bahasa lain) tidak secara default rekursif?

Dengan kata lain, mengapa desainer bahasa memutuskan bahwa sebaiknya Anda secara eksplisit membuat Anda mengetik recdalam deklarasi seperti:

let rec foo ... = ...

dan tidak memberikan kemampuan rekursif fungsi secara default? Mengapa perlunya reckonstruksi eksplisit ?

f# recursion ocaml nsantorello
sumber
Lihat juga stackoverflow.com/questions/3739628/…
Brian

Jawaban:

87

Keturunan Prancis dan Inggris dari ML asli membuat pilihan yang berbeda dan pilihan mereka telah diwarisi selama beberapa dekade ke varian modern. Jadi ini hanya warisan, tetapi memengaruhi idiom dalam bahasa-bahasa ini.

Fungsi tidak rekursif secara default dalam keluarga bahasa CAML Prancis (termasuk OCaml). Pilihan ini memudahkan untuk mengganti definisi fungsi (dan variabel) yang digunakan letdalam bahasa tersebut karena Anda dapat merujuk ke definisi sebelumnya di dalam isi definisi baru. F # mewarisi sintaks ini dari OCaml.

Misalnya, menggantikan fungsi psaat menghitung entropi Shannon dari suatu urutan di OCaml:

let shannon fold p =
  let p x = p x *. log(p x) /. log 2.0 in
  let p t x = t +. p x in
  -. fold p 0.0

Perhatikan bagaimana argumen pke fungsi tingkat tinggi shannondigantikan oleh argumen lain pdi baris pertama badan dan kemudian argumen lain di baris badan pkedua.

Sebaliknya, cabang bahasa Inggris SML dari keluarga bahasa ML mengambil pilihan lain dan funfungsi -bound SML bersifat rekursif secara default. Ketika sebagian besar definisi fungsi tidak memerlukan akses ke binding sebelumnya dari nama fungsinya, ini menghasilkan kode yang lebih sederhana. Namun, fungsi superceded dibuat untuk menggunakan nama yang berbeda ( f1, f2dll.) Yang mengotori ruang lingkup dan memungkinkan untuk secara tidak sengaja memanggil "versi" yang salah dari suatu fungsi. Dan sekarang ada perbedaan antara funfungsi yang terikat secara implisit-rekursif dan fungsi yang terikat secara non-rekursif val.

Haskell memungkinkan untuk menyimpulkan dependensi di antara definisi dengan membatasinya menjadi murni. Hal ini membuat sampel mainan terlihat lebih sederhana tetapi harus dibayar mahal di tempat lain.

Perhatikan bahwa jawaban yang diberikan oleh Ganesh dan Eddie adalah pengalih perhatian. Mereka menjelaskan mengapa kelompok fungsi tidak dapat ditempatkan di dalam raksasa let rec ... and ...karena itu mempengaruhi ketika variabel tipe digeneralisasi. Ini tidak ada hubungannya dengan recdefault di SML tetapi tidak di OCaml.

JD
sumber
3
Saya tidak berpikir itu adalah red herring: jika bukan karena pembatasan inferensi, kemungkinan seluruh program atau modul akan secara otomatis diperlakukan sebagai saling rekursif seperti kebanyakan bahasa lain. Itu akan membuat keputusan desain spesifik apakah "rec" harus diperdebatkan atau tidak.
GS - Minta maaf kepada Monica
"... secara otomatis diperlakukan sebagai rekursif timbal balik seperti kebanyakan bahasa lain". BASIC, C, C ++, Clojure, Erlang, F #, Factor, Forth, Fortran, Groovy, OCaml, Pascal, Smalltalk dan Standard ML tidak.
JD
3
C / C ++ hanya memerlukan prototipe untuk definisi maju, yang tidak benar-benar tentang menandai rekursi secara eksplisit. Java, C # dan Perl memang memiliki rekursi implisit. Kita dapat berdebat tanpa akhir tentang arti "paling" dan pentingnya setiap bahasa, jadi mari kita puas dengan "sangat banyak" bahasa lain.
GS - Minta maaf kepada Monica
3
"C / C ++ hanya memerlukan prototipe untuk definisi maju, yang tidak benar-benar tentang menandai rekursi secara eksplisit". Hanya dalam kasus khusus rekursi sendiri. Dalam kasus umum rekursi timbal balik, deklarasi maju adalah wajib di C dan C ++.
JD
2
Sebenarnya, deklarasi maju tidak diperlukan dalam C ++ dalam cakupan kelas, misalnya metode statis boleh memanggil satu sama lain tanpa deklarasi apa pun.
polkovnikov.ph
52

Salah satu alasan penting untuk penggunaan eksplisit recadalah berkaitan dengan inferensi tipe Hindley-Milner, yang mendasari semua bahasa pemrograman fungsional yang diketik secara statis (meskipun diubah dan diperluas dalam berbagai cara).

Jika Anda memiliki definisi let f x = x, Anda mengharapkan definisi tersebut memiliki tipe 'a -> 'adan dapat diterapkan pada 'atipe yang berbeda pada titik yang berbeda. Tetapi sama halnya , jika Anda menulis let g x = (x + 1) + ..., Anda akan berharap xdiperlakukan sebagai intbagian tubuh lainnya g.

Cara inferensi Hindley-Milner menangani perbedaan ini adalah melalui langkah generalisasi eksplisit . Pada titik-titik tertentu saat memproses program Anda, sistem tipe berhenti dan berkata "ok, jenis definisi ini akan digeneralisasi pada titik ini, sehingga ketika seseorang menggunakannya, variabel jenis bebas apa pun dalam tipenya akan baru dibuat , dan karenanya tidak akan mengganggu penggunaan lain dari definisi ini. "

Ternyata tempat yang masuk akal untuk melakukan generalisasi ini adalah setelah memeriksa sekumpulan fungsi yang saling rekursif. Lebih awal, dan Anda akan menggeneralisasi terlalu banyak, yang mengarah ke situasi di mana tipe sebenarnya bisa bertabrakan. Nanti, dan Anda akan menggeneralisasi terlalu sedikit, membuat definisi yang tidak dapat digunakan dengan beberapa jenis contoh.

Jadi, mengingat bahwa pemeriksa tipe perlu mengetahui tentang kumpulan definisi mana yang saling rekursif, apa yang dapat dilakukannya? Salah satu kemungkinannya adalah dengan hanya melakukan analisis ketergantungan pada semua definisi dalam ruang lingkup, dan menyusunnya kembali menjadi kelompok sekecil mungkin. Haskell sebenarnya melakukan ini, tetapi dalam bahasa seperti F # (dan OCaml dan SML) yang memiliki efek samping tak terbatas, ini adalah ide yang buruk karena mungkin menyusun ulang efek samping juga. Jadi sebaliknya ia meminta pengguna untuk secara eksplisit menandai definisi mana yang saling rekursif, dan dengan demikian dengan ekstensi di mana generalisasi harus terjadi.

GS - Minta maaf pada Monica
sumber
3
Err, tidak. Paragraf pertama Anda salah (Anda sedang berbicara tentang penggunaan eksplisit dari "dan" dan bukan "rec") dan, akibatnya, sisanya tidak relevan.
JD
5
Saya tidak pernah senang dengan persyaratan ini. Terima kasih untuk penjelasannya. Alasan lain mengapa Haskell lebih unggul dalam desain.
Bent Rasmussen
9
TIDAK!!!! BAGAIMANA INI DAPAT TERJADI ?! Jawaban ini salah! Silakan baca jawaban Harrop di bawah ini atau lihat The Definition of Standard ML (Milner, Tofte, Harper, MacQueen - 1997) [
p.24
9
Seperti yang saya katakan dalam jawaban saya, jenis masalah inferensi adalah salah satu alasan perlunya rec, bukan satu-satunya alasan. Jawaban Jon juga merupakan jawaban yang sangat valid (selain dari komentar sinis yang biasa tentang Haskell); Saya tidak berpikir keduanya bertentangan.
GS - Minta maaf kepada Monica
16
"Jenis masalah inferensi adalah salah satu alasan perlunya rec". Fakta bahwa OCaml membutuhkan rectetapi SML tidak merupakan contoh tandingan yang jelas. Jika jenis inferensi adalah masalah karena alasan yang Anda gambarkan, OCaml dan SML tidak dapat memilih solusi yang berbeda seperti yang mereka lakukan. Alasannya, tentu saja, yang Anda bicarakan anduntuk membuat Haskell relevan.
JD
10

Ada dua alasan utama mengapa ini adalah ide yang bagus:

Pertama, jika Anda mengaktifkan definisi rekursif maka Anda tidak dapat merujuk ke pengikatan sebelumnya dari nilai dengan nama yang sama. Ini sering kali merupakan idiom yang berguna ketika Anda melakukan sesuatu seperti memperluas modul yang sudah ada.

Kedua, nilai rekursif, dan terutama kumpulan nilai rekursif yang saling menguntungkan, jauh lebih sulit untuk dipikirkan kemudian adalah definisi yang diproses secara berurutan, setiap definisi baru dibangun di atas apa yang telah didefinisikan. Sangat menyenangkan ketika membaca kode seperti itu untuk mendapatkan jaminan bahwa, kecuali untuk definisi yang secara eksplisit ditandai sebagai rekursif, definisi baru hanya dapat merujuk ke definisi sebelumnya.

zrr
sumber
4

Beberapa tebakan:

  • lettidak hanya digunakan untuk mengikat fungsi, tetapi juga nilai reguler lainnya. Sebagian besar bentuk nilai tidak boleh rekursif. Bentuk nilai rekursif tertentu diperbolehkan (misalnya fungsi, ekspresi malas, dll.), Jadi diperlukan sintaks eksplisit untuk menunjukkannya.
  • Mungkin lebih mudah untuk mengoptimalkan fungsi non-rekursif
  • Penutupan yang dibuat saat Anda membuat fungsi rekursif perlu menyertakan entri yang mengarah ke fungsi itu sendiri (sehingga fungsi tersebut dapat memanggil dirinya sendiri secara rekursif), yang membuat penutupan rekursif lebih rumit daripada penutupan non-rekursif. Jadi, mungkin menyenangkan untuk dapat membuat penutupan non-rekursif yang lebih sederhana saat Anda tidak memerlukan rekursi
  • Ini memungkinkan Anda untuk menentukan fungsi dalam istilah fungsi atau nilai yang telah ditentukan sebelumnya dengan nama yang sama; meskipun saya pikir ini adalah praktik yang buruk
  • Keamanan ekstra? Memastikan bahwa Anda melakukan apa yang Anda inginkan. misalnya Jika Anda tidak bermaksud untuk menjadi rekursif tetapi Anda tidak sengaja menggunakan nama di dalam fungsi dengan nama yang sama dengan fungsi itu sendiri, kemungkinan besar akan mengeluh (kecuali nama telah ditentukan sebelumnya)
  • The letmembangun mirip dengan letmembangun di Lisp dan Scheme; yang non-rekursif. Ada letreckonstruksi terpisah dalam Skema untuk rekursif mari
newacct
sumber
"Sebagian besar bentuk nilai tidak diperbolehkan untuk menjadi rekursif. Bentuk nilai rekursif tertentu diperbolehkan (misalnya fungsi, ekspresi malas, dll.), Jadi diperlukan sintaks eksplisit untuk menunjukkan ini". Itu benar untuk F # tapi saya tidak yakin seberapa benar itu untuk OCaml di mana Anda bisa melakukannya let rec xs = 0::ys and ys = 1::xs.
JD
4

Diberikan ini:

let f x = ... and g y = ...;;

Membandingkan:

let f a = f (g a)

Dengan ini:

let rec f a = f (g a)

Mantan mengubah fmenerapkan ditetapkan sebelumnya fdengan hasil dari penerapan guntuk a. The mengubah terakhir floop selamanya menerapkan guntuk a, yang biasanya tidak apa yang Anda inginkan dalam varian ML.

Meskipun demikian, ini adalah gaya desainer bahasa. Lakukan saja.

james woodyatt
sumber
1

Sebagian besar darinya adalah memberikan programmer lebih banyak kendali atas kompleksitas cakupan lokal mereka. Spektrum let, let*dan let recmenawarkan tingkat daya dan biaya yang meningkat. let*dan let recpada dasarnya adalah versi bersarang dari yang sederhana let, jadi menggunakan salah satunya lebih mahal. Grading ini memungkinkan Anda untuk mengatur optimalisasi program Anda karena Anda dapat memilih level mana yang Anda perlukan untuk tugas yang ada. Jika Anda tidak memerlukan rekursi atau kemampuan untuk merujuk ke binding sebelumnya, maka Anda dapat menggunakan metode biarkan sederhana untuk menghemat sedikit performa.

Ini mirip dengan predikat kesetaraan bertingkat dalam Skema. (yaitu eq?, eqv?dan equal?)

Evan Meagher
sumber