Tail call pada F# 10

Dukungan tail call di dalam computation expression yang dibawa F# 10.

Daftar isi

Topik ini membahas dukungan tail call pada computation expression yang dibawa F# 10. Pembahasan dimulai dari pengertian tail call dan alasan pentingnya bagi rekursi dalam loop fungsional, dilanjutkan dengan member yang dilaporkan dokumentasi F# 10 sebagai jalur opt-in bagi builder, dan ditutup dengan demonstrasi rekursi melalui workflow khusus pada masukan 300.000 iterasi yang benar-benar dijalankan. Klaim fitur dirujuk dari dokumentasi rilis, sedangkan seluruh keluaran yang ditampilkan berasal dari eksekusi pada F# 10.

Tail call dan rekursi dalam#

Tail call adalah pemanggilan fungsi yang menjadi operasi terakhir sebelum fungsi pemanggilnya mengembalikan hasil. Apabila panggilan terakhir itu tidak menyisakan pekerjaan, compiler dapat menggunakan ulang frame stack milik pemanggil untuk fungsi yang dipanggil, sehingga kedalaman stack tidak bertambah. Rekursi yang menempatkan panggilan ke dirinya pada posisi terakhir disebut rekursi ekor, dan pola ini memungkinkan perulangan ditulis sebagai rekursi tanpa batas kedalaman yang praktis.

Tanpa sifat itu, setiap tingkat rekursi menyimpan satu frame baru pada stack, dan stack berukuran terbatas, sehingga rekursi yang dalam mengalami stack overflow. Loop fungsional pada F# mengandalkan pola ini secara langsung, karena perulangan imperatif digantikan oleh fungsi let rec dengan parameter akumulator. Fungsi berikut menghitung jumlah dari 1 sampai n, dan jumlahnya dapat diperiksa dengan rumus $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ .

fsharp Contoh: rekursi ekor biasa dengan akumulator

// panggilan jalan adalah operasi terakhir, sehingga cocok untuk tail call
let rec jumlahHingga (akumulator: int64) (n: int64) (batas: int64) : int64 =
    if n > batas then akumulator
    else jumlahHingga (akumulator + n) (n + 1L) batas

printfn "%d" (jumlahHingga 0L 1L 300000L)

text Keluaran

45000150000

Bentuknya lurus karena panggilan jumlahHingga berada pada baris terakhir cabang else. Parameter akumulator membuat posisi itu bersih, karena hasil sementara tidak ditahan oleh operasi penjumlahan yang menunggu sisa rekursi. Pola yang sama berpindah ke dalam workflow tanpa perubahan bentuk, cukup dengan menulis langkah rekursifnya sebagai return!. Permasalahan baru muncul ketika langkah perulangan itu dibungkus computation expression, karena return! diterjemahkan menjadi pemanggilan member, bukan panggilan fungsi biasa, sehingga posisi ekornya tidak lagi otomatis dijamin.

Member ekor pada dokumentasi F# 10#

Dokumentasi F# 10 melaporkan dukungan tail call pada computation expression. Builder dapat mengikutinya dengan menambahkan member khusus, yaitu ReturnFromFinal untuk return! pada posisi ekor dan YieldFromFinal untuk yield! pada posisi ekor. Compiler mengenali return!, yield!, dan do! yang berada pada posisi terakhir sebelum workflow selesai, lalu mengarahkan panggilannya ke member tersebut. Apabila member itu tidak ada, panggilan kembali ke jalur biasa, yaitu ReturnFrom, YieldFrom, atau Bind, dan dokumentasi menyatakan semantik builder tanpa member baru tetap tidak berubah. Untuk do! yang menjadi pernyataan terakhir, dokumentasi mencatat urutan preferensi ReturnFromFinal, kemudian YieldFromFinal, sebelum kembali ke jalur Bind.

Rute ini dapat diamati langsung dengan builder yang mencetak member mana yang terpanggil. Berkas berikut menyandingkan return! pada posisi ekor dengan return! di dalam try-finally, yang bukan posisi ekor karena kompensasi finally masih harus dijalankan setelahnya.

fsharp rute-member-ekor.fsx

// Builder yang melacak member mana yang dipanggil untuk return!
type UlangBuilder() =
    member _.Bind(x: 'a, langkah: 'a -> 'b) : 'b = langkah x
    member _.Return(x: 'a) : 'a = x
    member _.ReturnFrom(x: 'a) : 'a =
        printfn "  ReturnFrom dipanggil"
        x
    member _.ReturnFromFinal(x: 'a) : 'a =
        printfn "  ReturnFromFinal dipanggil"
        x
    member _.TryFinally(badan: 'a, kompensasi: unit -> unit) : 'a =
        try
            badan
        finally
            kompensasi ()
    member _.Delay(f: unit -> 'a) : 'a = f ()
    member _.Run(x: 'a) : 'a = x

let ulang = UlangBuilder()

// return! pada posisi ekor: langkah terakhir sebelum workflow selesai
let posisiEkor () =
    ulang {
        let! a = 5
        return! a * 2
    }

printfn "== return! pada posisi ekor =="
printfn "hasil %d" (posisiEkor ())

// return! di dalam try-finally: kompensasi masih harus dijalankan
let posisiNonEkor () =
    ulang {
        try
            return! 40
        finally
            printfn "  finally dijalankan"
    }

printfn "== return! di dalam try-finally =="
printfn "hasil %d" (posisiNonEkor ())

text Keluaran

== return! pada posisi ekor ==
  ReturnFromFinal dipanggil
hasil 10
== return! di dalam try-finally ==
  ReturnFrom dipanggil
  finally dijalankan
hasil 40

Keluaran menegaskan dua rute yang berbeda pada builder yang sama. return! yang menjadi langkah terakhir workflow diarahkan ke ReturnFromFinal, sedangkan return! yang dibungkus try-finally diarahkan ke ReturnFrom karena kompensasi finally menuntut kembali ke frame yang menyelimutinya. Kedua fungsi tetap menghasilkan nilai yang benar, yaitu 10 dan 40, sehingga perbedaan rute hanya menyangkut jalur eksekusi dan bukan hasil akhirnya.

Rekursi dalam lewat workflow#

Demonstrasi terakhir menghitung jumlah 1 sampai 300.000 dengan rekursi yang setiap langkahnya melewati workflow. Fungsi jalan bersifat let rec dan memanggil dirinya melalui return!, dengan akumulator yang menampung jumlah sementara. Bila setiap iterasi menambah frame stack, kedalaman 300.000 tingkat jauh melampaui kapasitas stack bawaan, sehingga selesainya perhitungan ini sekaligus menunjukkan bahwa panggilan ekornya tidak menumbuhkan stack.

fsharp jumlah-akumulator.fsx

// Rekursi ekor di dalam computation expression dengan ReturnFromFinal
type UlangBuilder() =
    member _.Bind(x: int64, langkah: int64 -> int64) : int64 = langkah x
    member _.Return(x: int64) : int64 = x
    member _.ReturnFrom(x: int64) : int64 = x
    member _.ReturnFromFinal(x: int64) : int64 = x

let ulang = UlangBuilder()

// jumlah 1..batas dihitung dengan rekursi ekor lewat workflow
let jumlahHingga (batas: int64) : int64 =
    let rec jalan (akumulator: int64) (n: int64) =
        ulang {
            if n > batas then
                return akumulator
            else
                let! lanjut = akumulator + n
                return! jalan lanjut (n + 1L)
        }
    jalan 0L 1L

printfn "%d" (jumlahHingga 300000L)

text Keluaran

45000150000

Hasilnya dapat diperiksa dengan rumus pada bagian pertama, yaitu $\frac{300000 \times 300001}{2} = 45000150000$ , sehingga keluarannya sekaligus membuktikan seluruh 300.000 iterasi benar-benar dijalankan. Tipe akumulatornya sengaja int64 karena jumlah tersebut melampaui jangkauan int 32-bit. Ukuran masukannya dipilih jauh di atas kedalaman yang sanggup ditampung stack biasa, tetapi tetap kecil agar eksekusinya berhenti cepat, dan skripnya tuntas dalam waktu kurang dari dua detik. Struktur workflow-nya mengikuti pola standar loop fungsional, yaitu cabang kondisi yang mengembalikan akumulator pada kasus dasar dan return! yang memanggil langkah berikutnya pada kasus rekursif, sehingga pola perulangan yang sudah dikenal tetap terbaca di dalam workflow.

Pola ini berlaku pada builder apa pun yang menyediakan ReturnFromFinal, termasuk LoggingBuilder yang dibangun pada topik workflow khusus. Batasannya ada pada konstruksi yang menyelimuti panggilan ekor, misalnya try-finally pada contoh rute di atas, karena konstruksi itu memaksa compiler memilih jalur biasa demi menjalankan kompensasinya.

Ringkasan#

Tail call adalah panggilan yang menjadi operasi terakhir sebelum kembali, sehingga frame stack pemanggilnya dapat digunakan ulang dan rekursi tidak menumbuhkan stack.
Dokumentasi F# 10 melaporkan dukungan tail call pada computation expression melalui member opsional ReturnFromFinal dan YieldFromFinal untuk return! dan yield! pada posisi ekor.
Eksekusi nyata menunjukkan return! pada posisi ekor diarahkan ke ReturnFromFinal, sedangkan return! di dalam try-finally diarahkan ke ReturnFrom.
Rekursi 300.000 iterasi melalui workflow dengan ReturnFromFinal berselesai dengan hasil yang cocok dengan rumus jumlah deretnya.

Referensi#

What’s new in F# 10 — Microsoft Learn — pengumuman resmi dukungan tail call pada computation expression beserta member ReturnFromFinal dan YieldFromFinal.
Computation expressions — Microsoft Learn — kontras member builder yang menjadi jalur fallback rute ekor.
Panduan F# — Microsoft Learn — halaman induk dokumentasi resmi F# di .NET.