Apakah bahasa fungsional lebih baik saat rekursi?

41

TL; DR: Apakah bahasa fungsional menangani rekursi lebih baik daripada yang non-fungsional?

Saat ini saya sedang membaca Kode Selesai 2. Pada titik tertentu dalam buku ini, penulis memperingatkan kita tentang rekursi. Dia mengatakan itu harus dihindari bila memungkinkan dan bahwa fungsi menggunakan rekursi umumnya kurang efektif daripada solusi menggunakan loop. Sebagai contoh, penulis menulis fungsi Java menggunakan rekursi untuk menghitung faktorial dari angka seperti itu (mungkin tidak persis sama karena saya tidak memiliki buku dengan saya saat ini):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

Ini disajikan sebagai solusi buruk. Namun, dalam bahasa fungsional, menggunakan rekursi sering kali merupakan cara yang disukai untuk melakukan sesuatu. Misalnya, inilah fungsi faktorial di Haskell menggunakan rekursi:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

Dan diterima secara luas sebagai solusi yang baik. Seperti yang telah saya lihat, Haskell sangat sering menggunakan rekursi, dan saya tidak melihat di mana pun hal itu disukai.

Jadi pertanyaan saya pada dasarnya adalah:

  • Apakah bahasa fungsional menangani rekursi lebih baik daripada yang non-fungsional?

EDIT: Saya sadar bahwa contoh yang saya gunakan bukan yang terbaik untuk menggambarkan pertanyaan saya. Saya hanya ingin menunjukkan bahwa Haskell (dan bahasa fungsional pada umumnya) menggunakan rekursi lebih sering daripada bahasa non-fungsional.

marco-fiset
sumber
10
Contoh kasus: banyak bahasa fungsional menggunakan optimasi panggilan ekor, sementara sangat sedikit bahasa prosedural yang melakukannya. Ini berarti rekursi panggilan jauh lebih murah dalam bahasa-bahasa fungsional tersebut.
Joachim Sauer
7
Sebenarnya, definisi Haskell yang Anda berikan sangat buruk. factorial n = product [1..n]lebih ringkas, lebih efisien, dan tidak meluap tumpukan untuk besar n(dan jika Anda membutuhkan memoisasi, opsi yang sama sekali berbeda diperlukan). productdidefinisikan dalam hal beberapa fold, yang adalah didefinisikan secara rekursif, tetapi dengan sangat hati-hati. Rekursi adalah solusi yang dapat diterima sebagian besar waktu, tetapi masih mudah untuk melakukannya dengan salah / suboptimal.
1
@ JoachimSauer - Dengan sedikit hiasan, komentar Anda akan membuat jawaban yang berharga.
Mark Booth
Suntingan Anda menunjukkan bahwa Anda tidak mengetahui maksud saya. Definisi yang Anda berikan adalah contoh sempurna rekursi yang buruk bahkan dalam bahasa fungsional . Alternatif saya juga rekursif (meskipun itu dalam fungsi perpustakaan) dan sangat efisien, hanya bagaimana itu berulang membuat perbedaan. Haskell juga merupakan kasus aneh di mana kemalasan melanggar aturan yang biasa (contohnya: fungsi dapat meluap tumpukan sambil menjadi ekor rekursif, dan sangat efisien tanpa menjadi ekor rekursif).
@delnan: Terima kasih atas klarifikasi! Saya akan mengedit suntingan saya;)
marco-fiset

Jawaban:

36

Ya, mereka melakukannya, tetapi bukan hanya karena mereka dapat , tetapi karena mereka harus melakukannya .

Konsep kunci di sini adalah kemurnian : fungsi murni adalah fungsi tanpa efek samping dan tanpa kondisi. Bahasa pemrograman fungsional umumnya mencakup kemurnian karena berbagai alasan, seperti alasan tentang kode dan menghindari ketergantungan yang tidak jelas. Beberapa bahasa, terutama Haskell, bahkan hanya mengizinkan kode murni; efek samping apa pun yang mungkin dimiliki program (seperti menjalankan I / O) dipindahkan ke runtime yang tidak murni, menjaga bahasa itu sendiri tetap murni.

Tidak memiliki efek samping berarti Anda tidak dapat memiliki penghitung lingkaran (karena penghitung lingkaran akan membentuk keadaan yang bisa berubah, dan memodifikasi keadaan tersebut akan menjadi efek samping), sehingga yang paling berulang yang bisa didapat bahasa fungsional murni adalah dengan mengulangi daftar ( operasi ini biasanya disebut foreachatau map). Rekursi, bagaimanapun, adalah kecocokan alami dengan pemrograman fungsional murni - tidak diperlukan kondisi rekursi, kecuali untuk argumen fungsi (hanya baca) dan nilai pengembalian (hanya-tulis).

Namun, tidak memiliki efek samping juga berarti rekursi dapat diimplementasikan lebih efisien, dan kompiler dapat mengoptimalkannya secara lebih agresif. Saya belum mempelajari kompiler semacam itu secara mendalam, tetapi sejauh yang saya tahu, kebanyakan kompiler bahasa pemrograman fungsional melakukan optimasi panggilan ekor, dan beberapa bahkan dapat mengkompilasi beberapa jenis konstruksi rekursif ke dalam loop di belakang layar.

tammmer
sumber
2
Sebagai catatan, eliminasi panggilan ekor tidak bergantung pada kemurnian.
scarfridge
2
@scarfridge: Tentu saja tidak. Namun, ketika kemurnian diberikan, jauh lebih mudah bagi kompiler untuk menyusun ulang kode Anda untuk memungkinkan panggilan ekor.
Pelaku
GCC melakukan pekerjaan TCO yang jauh lebih baik daripada GHC, karena Anda tidak dapat melakukan TCO di seluruh penciptaan thunk.
dan_waterworth
18

Anda membandingkan rekursi vs iterasi. Tanpa eliminasi tail-call , iterasi memang lebih efisien karena tidak ada panggilan fungsi tambahan. Juga, iterasi dapat berlangsung selamanya, sedangkan dimungkinkan untuk kehabisan ruang stack dari terlalu banyak panggilan fungsi.

Namun, iterasi membutuhkan perubahan penghitung. Itu berarti harus ada variabel yang bisa berubah , yang dilarang dalam pengaturan fungsional murni. Jadi bahasa fungsional dirancang khusus untuk beroperasi tanpa perlu iterasi, oleh karena itu fungsi yang disederhanakan memanggil.

Tapi tidak ada yang membahas mengapa sampel kode Anda begitu ramping. Contoh Anda menunjukkan properti yang berbeda, yaitu pencocokan pola . Itu sebabnya sampel Haskell tidak memiliki persyaratan eksplisit. Dengan kata lain, bukan rekursi efisien yang membuat kode Anda kecil; itu adalah pencocokan pola.

chrisaycock
sumber
Saya sudah tahu apa itu pencocokan pola dan saya pikir ini adalah fitur luar biasa di Haskell yang saya lewatkan dalam bahasa yang saya gunakan!
marco-fiset
@marcof Maksud saya adalah bahwa semua pembicaraan tentang rekursi vs iterasi tidak membahas keaslian sampel kode Anda. Ini benar-benar tentang pencocokan pola vs persyaratan. Mungkin saya seharusnya menempatkan itu di bagian atas jawaban saya.
chrisaycock
Ya, saya juga mengerti itu: P
marco-fiset
@ chrisaycock: Apakah mungkin untuk melihat iterasi sebagai rekursi ekor di mana semua variabel yang digunakan dalam loop body adalah argumen dan mengembalikan nilai panggilan rekursif?
Giorgio
@Iorgio: Ya, buat fungsi Anda mengambil dan mengembalikan tupel dengan jenis yang sama.
Ericson2314
5

Secara teknis tidak, tetapi praktis ya.

Rekursi jauh lebih umum ketika Anda mengambil pendekatan fungsional untuk masalah tersebut. Karena itu, bahasa yang dirancang untuk menggunakan pendekatan fungsional sering menyertakan fitur yang membuat rekursi lebih mudah / lebih baik / kurang bermasalah. Dari atas kepala saya, ada tiga yang umum:

  1. Optimasi Panggilan Ekor. Seperti yang ditunjukkan oleh poster lain, bahasa fungsional sering membutuhkan TCO.

  2. Evaluasi Malas. Haskell (dan beberapa bahasa lainnya) dievaluasi dengan malas. Ini menunda 'pekerjaan' sebenarnya dari suatu metode sampai diperlukan. Ini cenderung mengarah pada struktur data yang lebih rekursif dan dengan perluasan, metode rekursif untuk bekerja pada mereka.

  3. Kekekalan. Mayoritas hal yang Anda gunakan dalam bahasa pemrograman fungsional tidak dapat diubah. Ini membuat rekursi lebih mudah karena Anda tidak perlu khawatir dengan keadaan objek dari waktu ke waktu. Misalnya, Anda tidak dapat mengubah nilai dari bawah Anda. Juga, banyak bahasa dirancang untuk mendeteksi fungsi murni . Karena fungsi murni tidak memiliki efek samping, kompiler memiliki lebih banyak kebebasan tentang urutan fungsi yang dijalankan dan optimisasi lainnya.

Tidak satu pun dari hal-hal ini yang benar-benar spesifik untuk bahasa fungsional dibandingkan yang lain, jadi mereka tidak hanya lebih baik karena mereka fungsional. Tetapi karena mereka fungsional, keputusan desain yang dibuat cenderung ke fitur-fitur ini karena mereka lebih berguna (dan kelemahannya kurang bermasalah) ketika pemrograman secara fungsional.

Telastyn
sumber
1
Re: 1. Pengembalian awal tidak ada hubungannya dengan panggilan ekor. Anda dapat kembali lebih awal dengan panggilan ekor, dan memiliki pengembalian "terlambat" juga menampilkan panggilan ekor, dan Anda dapat memiliki satu ekspresi sederhana dengan panggilan rekursif yang tidak dalam posisi ekor (lih. Definisi faktorial OP).
@delnan: Terima kasih; ini masih awal dan sudah cukup lama sejak saya mempelajari hal itu.
Telastyn
1

Haskell dan bahasa fungsional lainnya umumnya menggunakan evaluasi malas. Fitur ini memungkinkan Anda menulis fungsi rekursif tanpa akhir.

Jika Anda menulis fungsi rekursif tanpa mendefinisikan kasus dasar di mana rekursi berakhir, Anda berakhir dengan memiliki panggilan tak terbatas ke fungsi tersebut dan stackoverflow.

Haskell juga mendukung optimisasi panggilan fungsi rekursif. Di Jawa, setiap panggilan fungsi akan menumpuk dan menyebabkan overhead.

Jadi ya, bahasa fungsional menangani rekursi lebih baik daripada yang lain.

Mert Akcakaya
sumber
5
Haskell adalah salah satu dari sedikit bahasa non-ketat - seluruh keluarga ML (selain dari beberapa spin-off penelitian yang menambah kemalasan), semua Lisps populer, Erlang, dll semuanya ketat. Juga, paragraf kedua tampaknya tidak aktif - seperti yang Anda nyatakan dengan benar dalam paragraf pertama, kemalasan memang memungkinkan rekursi tak terbatas (pendahuluan Haskell memiliki contoh yang sangat berguna forever a = a >> forever a).
@deinan: Sejauh yang saya tahu SML / NJ juga menawarkan evaluasi malas tetapi merupakan tambahan untuk SML. Saya juga ingin menyebutkan dua dari beberapa bahasa fungsional yang malas: Miranda dan Clean.
Giorgio
1

Satu-satunya alasan teknis yang saya ketahui adalah bahwa beberapa bahasa fungsional (dan beberapa bahasa imperatif jika saya ingat) memiliki apa yang disebut optimasi panggilan ekor yang memungkinkan metode rekursif untuk tidak menambah ukuran tumpukan dengan setiap panggilan rekursif (mis. Panggilan rekursif lebih atau kurang menggantikan panggilan saat ini di stack).

Perhatikan, bahwa pengoptimalan ini tidak berfungsi pada panggilan rekursif apa pun , hanya metode rekursif panggilan ekor (mis. Metode yang tidak mempertahankan status pada saat panggilan rekursif)

Steven Evers
sumber
1
(1) Optimalisasi seperti itu hanya berlaku dalam kasus yang sangat spesifik - contoh OP bukan mereka, dan banyak fungsi langsung lainnya memerlukan perhatian ekstra untuk menjadi rekursif ekor. (2) Optimal panggilan ekor nyata tidak hanya mengoptimalkan fungsi rekursif, itu menghilangkan ruang overhead dari panggilan apa pun yang segera diikuti oleh pengembalian.
@delnan: (1) Ya, sangat benar. Dalam 'draf orisinal' saya atas jawaban ini, saya telah menyebutkan bahwa :( (2) Ya, tetapi dalam konteks pertanyaan, saya pikir itu tidak ada artinya lagi.
Steven Evers
Ya, (2) hanyalah tambahan yang berguna (meskipun sangat diperlukan untuk gaya kelanjutan-lewat), jawaban yang tidak perlu disebutkan adalah.
1

Anda akan ingin melihat Pengumpulan Sampah Cepat, Tapi Tumpukan Lebih Cepat , makalah tentang menggunakan apa yang akan dipikirkan oleh programmer C sebagai "tumpukan" untuk frame tumpukan di kompilasi C. Saya percaya penulis mengutak-atik Gcc untuk melakukan itu . Itu bukan jawaban yang pasti, tetapi itu mungkin membantu Anda memahami beberapa masalah dengan rekursi.

The Alef bahasa pemrograman , yang digunakan untuk datang bersama dengan Plan 9 dari Bell Labs, memiliki "menjadi" Pernyataan (Lihat bagian 6.6.4 dari referensi ini ). Ini semacam optimisasi rekursi ekor-panggilan eksplisit. "Tapi itu menggunakan tumpukan panggilan!" Argumen menentang rekursi berpotensi dapat dihilangkan.

Bruce Ediger
sumber
0

TL; DR: Ya, mereka melakukan
Rekursi adalah alat utama dalam pemrograman fungsional dan karena itu banyak pekerjaan telah dilakukan untuk mengoptimalkan panggilan-panggilan ini. Sebagai contoh, R5RS mensyaratkan (dalam spek!) Bahwa semua implementasi menangani panggilan rekursi ekor yang tidak terikat tanpa programmer khawatir tentang stack overflow. Sebagai perbandingan, secara default kompiler C tidak akan melakukan optimasi tail-call yang jelas (coba kebalikan rekursif dari daftar tertaut) dan setelah beberapa panggilan, program akan berakhir (kompiler akan mengoptimalkan, meskipun, jika Anda menggunakan - O2).

Tentu saja, dalam program yang ditulis dengan mengerikan, seperti fibcontoh terkenal yang eksponensial, kompiler memiliki sedikit atau tidak ada pilihan untuk melakukan 'sihirnya'. Jadi perhatian harus diambil untuk tidak menghalangi upaya kompiler dalam optimasi.

EDIT: Dengan contoh fib, maksud saya yang berikut:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)
K.Steff
sumber
0

Bahasa fungsional lebih baik pada dua jenis rekursi yang sangat spesifik: rekursi ekor dan rekursi tak terbatas. Mereka sama buruknya dengan bahasa lain pada jenis rekursi lainnya, seperti factorialcontoh Anda .

Itu tidak berarti tidak ada algoritma yang bekerja dengan baik dengan rekursi reguler di kedua paradigma. Misalnya, apa pun yang memerlukan struktur data seperti tumpukan, seperti pencarian pohon kedalaman-pertama, paling sederhana untuk diterapkan dengan rekursi.

Rekursi muncul lebih sering dengan pemrograman fungsional, tetapi juga terlalu sering digunakan, terutama oleh pemula atau dalam tutorial untuk pemula, mungkin karena kebanyakan pemula untuk pemrograman fungsional telah menggunakan rekursi sebelumnya dalam pemrograman imperatif. Ada konstruksi pemrograman fungsional lainnya, seperti pemahaman daftar, fungsi tingkat tinggi, dan operasi lain pada koleksi, yang biasanya jauh lebih cocok secara konseptual, untuk gaya, untuk keringkasan, untuk efisiensi, dan untuk kemampuan untuk mengoptimalkan.

Misalnya, saran delnan tentang factorial n = product [1..n]tidak hanya lebih ringkas dan lebih mudah dibaca, tetapi juga sangat paralel. Sama untuk menggunakan foldatau reducejika bahasa Anda tidak memiliki productbawaan. Rekursi adalah solusi terakhir untuk masalah ini. Alasan utama Anda melihatnya dipecahkan secara berulang dalam tutorial adalah sebagai titik awal sebelum mendapatkan solusi yang lebih baik, bukan sebagai contoh praktik terbaik.

Karl Bielefeldt
sumber