Apakah Haskell memiliki pengoptimalan rekursif-ekor?

Saya menemukan perintah "waktu" di unix hari ini dan berpikir saya akan menggunakannya untuk memeriksa perbedaan runtime antara fungsi rekursif ekor dan rekursif normal di Haskell.

Saya menulis fungsi berikut:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

Ini valid mengingat bahwa mereka hanya untuk digunakan dengan proyek ini, jadi saya tidak repot-repot memeriksa angka nol atau negatif.

Namun, setelah menulis metode utama untuk masing-masing, mengompilasinya, dan menjalankannya dengan perintah "waktu", keduanya memiliki runtime yang serupa dengan fungsi rekursif normal yang tidak menggunakan rekursif ekor. Ini bertentangan dengan apa yang saya dengar terkait dengan pengoptimalan rekursif-ekor di cadel. Apa alasannya ini?

Haskell menggunakan evaluasi malas untuk mengimplementasikan rekursi, jadi memperlakukan apa pun sebagai janji untuk memberikan nilai saat diperlukan (ini disebut thunk). Thunk dikurangi hanya sebanyak yang diperlukan untuk melanjutkan, tidak lebih. Ini mirip dengan cara Anda menyederhanakan ekspresi secara matematis, jadi akan sangat membantu jika Anda menganggapnya seperti itu. Fakta bahwa urutan evaluasi tidak ditentukan oleh kode Anda memungkinkan compiler untuk melakukan banyak pengoptimalan yang lebih cerdik daripada hanya eliminasi tail-call yang biasa Anda lakukan. Kompilasi dengan -O2jika Anda ingin pengoptimalan!

Mari kita lihat bagaimana kami mengevaluasi facSlow 5sebagai studi kasus:

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

Jadi seperti yang Anda khawatirkan, kami memiliki penumpukan angka sebelum penghitungan apa pun terjadi, tetapi tidak seperti Anda khawatir, tidak ada tumpukan facSlowpanggilan fungsi yang menunggu untuk dihentikan - setiap pengurangan diterapkan dan menghilang, meninggalkan bingkai tumpukan di dalamnya. bangun (itu karena (*)ketat dan memicu evaluasi argumen keduanya).

Fungsi rekursif Haskell tidak dievaluasi dengan cara yang sangat rekursif! Satu-satunya tumpukan panggilan yang berkeliaran adalah perkalian itu sendiri. Jika (*)dipandang sebagai konstruktor data yang ketat, ini adalah apa yang dikenal sebagai dijaga rekursi (meskipun biasanya disebut sebagai tersebut dengan non konstruktor Data -strict, di mana apa yang tersisa di belakangnya adalah konstruktor Data - ketika dipaksa oleh akses lebih lanjut).

Sekarang mari kita lihat rekursif-ekor fac 5:

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

Jadi Anda dapat melihat bagaimana rekursi ekor itu sendiri tidak menghemat waktu atau ruang Anda. Tidak hanya membutuhkan lebih banyak langkah secara keseluruhan facSlow 5, itu juga membangun thunk bersarang (ditampilkan di sini sebagai {...}) - membutuhkan ruang ekstra untuk itu - yang menjelaskan komputasi masa depan, perkalian bertingkat yang akan dilakukan.

Dunk ini kemudian terurai dengan melintasi itu ke bawah, menciptakan perhitungan pada stack. Ada juga bahaya di sini karena tumpukan melimpah dengan komputasi yang sangat lama, untuk kedua versi.

Jika kita ingin mengoptimalkan ini secara manual, yang perlu kita lakukan adalah membuatnya ketat. Anda bisa menggunakan operator aplikasi yang ketat $!untuk mendefinisikan

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y) 

Ini memaksa facS'untuk menjadi tegas dalam argumen keduanya. (Ini sudah ketat dalam argumen pertamanya karena itu harus dievaluasi untuk memutuskan definisi mana yang facS'akan diterapkan.)

Terkadang ketegasan dapat sangat membantu, terkadang itu adalah kesalahan besar karena kemalasan lebih efisien. Ini ide yang bagus:

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

Menurut saya, apa yang ingin Anda capai.

Ringkasan

• Jika Anda ingin mengoptimalkan kode Anda, langkah pertama adalah mengompilasi -O2
• Rekursi ekor hanya baik jika tidak ada tumpukan, dan menambahkan ketegasan biasanya membantu mencegahnya, jika dan jika perlu. Ini terjadi saat Anda membangun hasil yang dibutuhkan di lain waktu sekaligus.
• Kadang-kadang rekursi ekor adalah rencana yang buruk dan rekursi yang dijaga lebih cocok, yaitu ketika hasil yang Anda buat akan dibutuhkan sedikit demi sedikit, dalam porsi. Lihat pertanyaan ini tentang foldrdan foldlmisalnya, dan uji mereka satu sama lain.

Coba dua ini:

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1adalah rekursif ekor, sedangkan foldr1melakukan rekursi yang dilindungi sehingga item pertama segera ditampilkan untuk diproses / diakses lebih lanjut. _{(Yang pertama "mengurung" ke kiri sekaligus, (...((s+s)+s)+...)+smemaksa daftar masukan sepenuhnya ke ujungnya dan membuat perhitungan besar di masa depan jauh lebih cepat daripada yang dibutuhkan hasil lengkapnya; yang kedua tanda kurung ke kanan secara bertahap s+(s+(...+(s+s)...)), memakan masukan daftar sedikit demi sedikit, sehingga semuanya dapat beroperasi dalam ruang konstan, dengan pengoptimalan).}

Anda mungkin perlu menyesuaikan jumlah nol tergantung pada perangkat keras apa yang Anda gunakan.

Perlu disebutkan bahwa facfungsi tersebut bukan kandidat yang baik untuk rekursi yang dijaga. Rekursi ekor adalah cara untuk pergi ke sini. Karena kemalasan, Anda tidak mendapatkan efek TCO dalam fac'fungsi Anda karena argumen akumulator terus membangun hambatan besar, yang bila dievaluasi akan membutuhkan tumpukan besar. Untuk mencegah hal ini dan mendapatkan efek TCO yang diinginkan, Anda perlu membuat argumen akumulator ini ketat.

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

Jika Anda mengkompilasi menggunakan -O2(atau hanya -O) GHC mungkin akan melakukan ini sendiri dalam fase analisis keketatan .

Anda harus membaca artikel wiki tentang rekursi ekor di Haskell . Khususnya, karena evaluasi ekspresi, jenis rekursi yang Anda inginkan adalah rekursi yang dilindungi . Jika Anda mengetahui detail tentang apa yang terjadi di balik terpal (dalam mesin abstrak untuk Haskell), Anda mendapatkan hal yang sama seperti rekursi ekor dalam bahasa yang ketat. Bersamaan dengan ini, Anda memiliki sintaks yang seragam untuk fungsi malas (rekursi ekor akan mengikat Anda ke evaluasi yang ketat, sedangkan rekursi yang dilindungi bekerja lebih alami).

(Dan dalam mempelajari Haskell, halaman wiki lainnya juga luar biasa!)

Jika saya mengingatnya dengan benar, GHC secara otomatis mengoptimalkan fungsi rekursif biasa menjadi fungsi rekursif ekor yang dioptimalkan.