Akumulator dan tail call

Tail call optimization dan pola akumulator untuk rekursi berkebutuhan memori konstan.

Daftar isi

Topik ini menjelaskan tail call dan pola akumulator: mengapa pemanggilan sebagai langkah terakhir tidak menumpuk keadaan di tumpukan, bagaimana akumulator membawa hasil sementara, dan kapan rekursi tubuh justru tetap pilihan alami. Contohnya membandingkan dua versi fungsi penjumlahan yang sama secara berdampingan.

Panggilan terakhir dan tumpukan#

Pemanggilan fungsi biasa menyimpan keadaan pemanggil di tumpukan, karena setelah pemanggilan selesai, pemanggil masih perlu melanjutkan pekerjaan. Pada rekursi tubuh seperti K + total(S), setiap tingkat menunggu penjumlahan, sehingga list dengan sejuta elemen menumpuk sejuta keadaan menunggu. VM mengelola tumpukan proses secara dinamis, tetapi kebutuhan memori yang tumbuh seiring data tetap menjadi beban.

Keadaan berbeda terjadi bila pemanggilan rekursif adalah langkah terakhir fungsi, yang disebut tail call. Tidak ada pekerjaan yang tersisa setelah pemanggilan, sehingga frame pemanggil tidak lagi dibutuhkan dan VM cukup menggantinya dengan frame pemanggilan baru. Prosesnya berulang tanpa pertumbuhan tumpukan, terlepas dari panjang datanya. Kualitas ini bukan optimasi opsional melainkan jaminan spesifikasi bahasa Erlang, sehingga dapat dipakai dengan percaya diri.

Versi dengan akumulator#

Masalahnya, bentuk K + total(S) tidak bisa langsung diubah menjadi tail call karena penjumlahannya harus menunggu hasil ekor. Solusinya adalah memindahkan hasil sementara ke argumen tambahan yang disebut akumulator: hasil sebagian dibawa maju pada setiap pemanggilan, dan saat list habis, akumulator itulah jawabannya. Modul berikut menampung kedua versi:

erlang jumlah2.erl

-module(jumlah2).
-export([total/1, total_tail/1, maks/1]).

total([]) -> 0;
total([K | S]) -> K + total(S).

total_tail(L) -> total_acc(L, 0).

total_acc([], Acc) -> Acc;
total_acc([K | S], Acc) -> total_acc(S, Acc + K).

maks([K | S]) -> maks_acc(S, K).

maks_acc([], M) -> M;
maks_acc([K | S], M) when K > M -> maks_acc(S, K);
maks_acc([_ | S], M) -> maks_acc(S, M).

Fungsi publik total_tail/1 hanya memulai proses dengan akumulator nol, sedangkan helper total_acc/2 mengerjakan semuanya sebagai tail call: setiap langkah menghitung Acc + K lebih dulu, lalu hasilnya dipanggil kembali sebagai argumen. Pemisahan dua fungsi ini adalah pola baku. Pengguna modul tidak perlu tahu keberadaan akumulator. Alur total_acc([2, 5, 1], 0) berjalan sebagai berikut: kepala 2 dipindahkan ke akumulator menjadi total_acc([5, 1], 2), lalu 5 menumpuk menjadi total_acc([1], 7), lalu 1 menjadi total_acc([], 8), dan list kosong mengembalikan akumulator 8. Hasil selalu siap di argumen, bukan menunggu di tumpukan. Eksekusinya:

erlang Membandingkan kedua versi

Erlang/OTP 29 [erts-17.1.1] [source] [64-bit] [smp:2:2] [ds:2:2:10] [async-threads:1] [jit:ns]

Eshell V17.1.1 (press Ctrl+G to abort, type help(). for help)
1> c(jumlah2).
{ok,jumlah2}
2> jumlah2:total([2, 5, 1]).
8
3> jumlah2:total_tail([2, 5, 1]).
8
4> jumlah2:total(lists:seq(1, 100000)).
5000050000
5> jumlah2:total_tail(lists:seq(1, 100000)).
5000050000

Kedua versi menghasilkan nilai yang sama pada data kecil maupun list seratus ribu elemen. Perbedaannya berada di dalam proses: total/1 menumpuk keadaan sebanyak panjang list, sedangkan total_tail/1 bekerja dengan memori konstan sepanjang proses. Untuk list yang panjangnya tidak terbatas, misalnya data yang mengalir terus dari jaringan, perbedaan ini memisahkan program yang bertahan dan program yang kehabisan memori.

Akumulator untuk nilai maksimum#

Pola yang sama melayani bentuk pengolahan lain. Fungsi maks/1 pada modul di atas membawa kandidat maksimum sebagai akumulator: kandidat awal adalah kepala list, lalu setiap langkah membandingkan elemen berikutnya dengan kandidat dan memilih yang lebih besar. Guard pada klausanya memastikan pembaruan kandidat hanya terjadi bila elemen memang lebih besar:

erlang Maksimum dengan akumulator kandidat

1> c(jumlah2).
{ok,jumlah2}
2> jumlah2:maks([3, 9, 2]).
9
3> jumlah2:maks([-1, -7, -3]).
-1

Pemanggilan kedua menunjukkan alasan kandidat awal diambil dari kepala, bukan dari 0: untuk list bilangan negatif, angka 0 sebagai nilai awal pasti menghasilkan jawaban yang salah. Dua klausa helper membentuk keputusan yang saling melengkapi, satu dengan guard untuk pembaruan kandidat dan satu klausa penangkap untuk sisanya, dan seluruh prosesnya tetap tail call.

Kapan rekursi tubuh tetap dipakai#

Akumulator juga punya biayanya: membawa hasil sementara berarti membangun struktur sambil berjalan. Untuk fungsi yang menghasilkan list baru, cara paling alami justru menunda pembangunan hingga kembali dari rekursi, sebagaimana bentuk [K | S] ++ hasil(S). Mengubahnya menjadi tail call menuntut pembangunan terbalik lalu pembalikan di akhir. Topik idiom pengolahan list menuntaskan pola itu. Pedoman praktisnya: perhitungan yang menghasilkan satu nilai, seperti jumlah atau nilai maksimum, cocok dengan akumulator. Pembangunan struktur besar boleh memakai rekursi tubuh selama kedalaman rekursinya sebanding dengan ukuran masukannya.

Terakhir, tumpukan yang dimaksud di sini adalah milik proses Erlang, bukan thread sistem operasi. Setiap proses mengelola tumpukan dan heapnya sendiri, keduanya tumbuh dan menyusut sesuai kebutuhan tanpa konfigurasi, dan pengumpulan sampah dikerjakan per proses sehingga satu proses yang menyapu memori tidak menghentikan yang lain. Dengan pengikatan tunggal dan tail call, kebutuhan memori satu proses dapat dibaca dari bentuk fungsinya, dan inilah salah satu alasan aplikasi Erlang dapat menampung jutaan proses pada satu VM.

Kesalahan umum#

Mengekspos helper berakumulator sebagai API modul. Pemanggil luar tidak boleh diharuskan menghitung nilai awal, sehingga helper dideklarasikan tanpa -export dan fungsi publik bertugas memberi nilai awal yang benar.
Memilih nilai awal akumulator yang bukan unsur identitas. Nilai awal 0 untuk penghitungan, 1 untuk perkalian, dan kandidat kepala list untuk maksimum. Nilai awal yang keliru menghasilkan angka yang tampak benar pada contoh kecil tetapi salah pada data lain.
Menganggap tail call selalu mengubah hasil. Nilai kembalinya identik. Yang berbeda hanya kebutuhan memorinya, sehingga keputusan memakainya didasarkan pada ukuran data yang dikerjakan, bukan pada hasilnya.

Ringkasan#

Tail call adalah pemanggilan fungsi sebagai langkah terakhir, dan VM menggantikan frame pemanggil alih-alih menumpuknya.
Jaminan tail call adalah bagian spesifikasi Erlang, bukan optimasi opsional.
Pola akumulator memindahkan hasil sementara ke argumen tambahan, dengan fungsi publik sebagai pembuka dan helper berakumulator sebagai pelaksana.
Rekursi tubuh tetap sah untuk pembangunan struktur, sedangkan pengolahan menjadi satu nilai lazim memakai akumulator.

Referensi#

Erlang Reference Manual: Functions — Ericsson — Dokumentasi resmi fungsi, termasuk perilaku tail recursion.
Erlang Efficiency Guide: Functions and Fun — Ericsson — Panduan resmi tentang last call optimization dan implikasinya.
Learn You Some Erlang for Great Good! — Fred Hebert — Bab rekursi yang memperkenalkan tail recursive dan pola akumulator.