Call-by-need

Program Haskell tidak menghitung ekspresinya segera setelah ekspresi itu ditulis. Bahasa ini menunda pekerjaan hingga hasilnya benar-benar diminta, dan model yang mengatur penundaan tersebut dinamakan call-by-need. Topik ini membahas mekanisme model itu, yaitu thunk sebagai wadah perhitungan tertunda, sharing yang mencegah perhitungan diulang, semantik non-strict, serta batas evaluasi yang disebut weak head normal form. Setelah membacanya, urutan perhitungan pada program sederhana dapat diprediksi dengan tepat.

Definisi yang ditunda menjadi thunk#

Ekspresi yang belum dihitung pada Haskell disimpan dalam bentuk thunk, yaitu wadah yang mencatat ekspresi beserta lingkungan variabelnya untuk dihitung kemudian. Proses penghitungan thunk disebut memaksa (forcing) thunk, yaitu menghitung ekspresinya hingga hasilnya siap digunakan. Argumen fungsi dan definisi lokal keduanya ditunda dengan cara ini, sehingga tidak ada perhitungan yang berlangsung sebelum hasilnya diminta.

Program berikut memperlihatkan kapan perhitungan itu terjadi. Fungsi trace dari Debug.Trace mencetak pesan tepat ketika ekspresinya dipaksa, sehingga pesan tersebut berfungsi sebagai penanda waktu evaluasi.

import Debug.Trace (trace)
import System.IO (BufferMode (..), hSetBuffering, stdout)

-- trace mencetak pesan tepat ketika ekspresinya dipaksa
kuadrat :: Int -> Int
kuadrat n = trace ("menghitung kuadrat " ++ show n) (n * n)

main :: IO ()
main = do
  hSetBuffering stdout LineBuffering
  let x = kuadrat 5
  putStrLn "definisi x sudah dibuat"
  print x
  print x

definisi x sudah dibuat
menghitung kuadrat 5
25
25

Urutan keluaran tersebut memuat tiga fakta. Baris definisi x sudah dibuat tercetak lebih dahulu, artinya let x = kuadrat 5 tidak menghitung apa pun dan hanya menyiapkan thunk. Pesan menghitung kuadrat 5 muncul persis ketika print x pertama meminta hasilnya. Baris 25 kedua tercetak tanpa pesan apa pun karena thunk yang sama sudah pernah dihitung, sehingga print x kedua langsung membaca nilai yang tersimpan.

Sharing#

Nilai yang dihasilkan sebuah thunk digunakan bersama (sharing), artinya satu definisi yang digunakan di banyak tempat dihitung paling banyak satu kali. Ketentuan ini berlaku pada let-binding, yaitu definisi lokal yang diperkenalkan dengan let. Dua penggunaan nama yang sama menunjuk thunk yang sama, sedangkan ekspresi yang sama yang ditulis dua kali menghasilkan dua thunk yang berbeda.

Program berikut membandingkan kedua bentuk itu. Definisi a menuliskan berat 5 dua kali, sedangkan definisi b menampung berat 5 dalam satu let lalu menggunakan x dua kali.

import Debug.Trace (trace)
import System.IO (BufferMode (..), hSetBuffering, stdout)

-- berat mencetak pesan tepat ketika ekspresinya dipaksa
berat :: Int -> Int
berat n = trace ("menghitung " ++ show n) (n * n)

main :: IO ()
main = do
  hSetBuffering stdout LineBuffering
  let a = berat 5 + berat 5
  let b = let x = berat 5 in x + x
  print a
  print b

menghitung 5
menghitung 5
50
menghitung 5
50

Kedua variabel menghasilkan nilai yang sama, tetapi jumlah perhitungannya berbeda. Pemaksaan a mencetak pesan menghitung 5 dua kali karena ekspresi itu ditulis dua kali. Pemaksaan b hanya mencetak satu pesan karena x menunjuk satu thunk yang hasilnya digunakan oleh kedua penjumlahan.

Diagram berikut merangkum siklus satu thunk yang digunakan dua kali.

Semantik non-strict#

Haskell adalah bahasa non-strict, artinya fungsi boleh menghasilkan nilai tanpa menghitung argumennya lebih dahulu. Laporan resmi Haskell menyatakan sifat ini secara eksplisit, sedangkan thunk adalah cara implementasinya, yaitu setiap argumen dikirim sebagai thunk dan dihitung hanya apabila isi fungsi benar-benar memintanya. Model call-by-need merupakan evaluasi non-strict yang disertai sharing thunk, sedangkan bahasa strict menghitung seluruh argumen sebelum isi fungsi dijalankan.

Program berikut menggunakan undefined, yaitu nilai yang pemaksaannya selalu memunculkan error. Operator &&, operator ||, dan fungsi const menghasilkan jawaban pasti tanpa menyentuh nilai itu.

-- Argumen yang tidak dibutuhkan tidak pernah dihitung
main :: IO ()
main = do
  print (False && undefined)
  print (True || undefined)
  print (const 1 undefined)

False
True
1

Pola False && sesuatu pasti bernilai False, sehingga operator tersebut tidak meminta operan kanannya dan thunk undefined tidak pernah dipaksa. Pola yang sama berlaku untuk True || sesuatu dan untuk const 1 sesuatu yang mengabaikan argumen keduanya. Apabila bahasanya strict, ketiga baris tersebut langsung memunculkan error karena setiap argumen dihitung sebelum fungsi dipanggil.

Weak head normal form#

Memaksa sebuah nilai tidak berarti menghitung seluruh isinya. Evaluasi berhenti pada weak head normal form (WHNF), yaitu bentuk di mana konstruktor terluar sudah diketahui, sedangkan komponen di dalamnya boleh masih berupa thunk. Bentuk penuh yang semua komponennya telah dihitung disebut normal form, dan keduanya dibedakan karena banyak operasi cukup dengan bentuk yang pertama.

Program berikut menggunakan seq, yaitu fungsi yang memaksa argumen pertamanya sampai WHNF sebelum mengembalikan argumen keduanya.

import Debug.Trace (trace)
import System.IO (BufferMode (..), hSetBuffering, stdout)

-- kuadrat mencetak pesan tepat ketika ekspresinya dipaksa
kuadrat :: Int -> Int
kuadrat n = trace ("menghitung " ++ show n) (n * n)

main :: IO ()
main = do
  hSetBuffering stdout LineBuffering
  let pasangan = (kuadrat 2, kuadrat 3)
  pasangan `seq` putStrLn "seq: hanya sampai konstruktor terluar"
  print (fst pasangan)

seq: hanya sampai konstruktor terluar
menghitung 2
4

Pemanggilan seq pada pasangan hanya memaksa sampai konstruktor tuple, sehingga pesan dari kuadrat tidak muncul pada saat itu. Baris print (fst pasangan) kemudian meminta komponen pertama, dan hanya pesan menghitung 2 yang tercetak, sedangkan kuadrat 3 tetap tertunda dalam thunk. Komponen tuple dievaluasi secara terpisah, sehingga pemaksaan yang berhenti di batas terluar tidak menyentuh komponennya sama sekali.

Kesalahan umum#

Kesalahan yang lazim terjadi adalah menganggap setiap konsumen list memaksa isi elemennya. Fungsi length hanya menghitung jumlah sel list dan tidak membaca isinya, sehingga elemen yang berisi error tetap lolos dari perhitungan. Perintah berikut menghitung panjang list yang dua elemennya berupa undefined, dan hasilnya tetap tercetak karena tidak ada satu pun elemen yang dipaksa.

# panjang list dihitung tanpa memaksa isi elemennya
ghc -e 'length [undefined, undefined]'

2

Perbaikannya bergantung pada tujuan. Apabila isi elemen memang perlu diperiksa, gunakan fungsi yang benar-benar membaca elemen seperti sum, atau paksa elemennya secara eksplisit sebelum panjangnya dihitung. Kesalahan kedua adalah menulis fungsi validasi yang tidak menyentuh datanya, misalnya fungsi yang mengembalikan True tanpa membaca argumennya. Semantik non-strict membuat fungsi semacam itu tetap lolos pemeriksaan tipe dan mengembalikan True untuk data apa pun, termasuk data yang rusak, sehingga validasi yang benar harus benar-benar memaksa nilai yang diujinya.

Ringkasan#

• Haskell menunda evaluasi, artinya definisi yang hasilnya belum diminta disimpan sebagai thunk dan dihitung hanya ketika hasilnya dipaksa.
• Satu let-binding dihitung paling banyak satu kali karena sharing, sedangkan ekspresi yang sama yang ditulis dua kali dihitung dua kali.
• Semantik non-strict membuat fungsi dapat menghasilkan nilai tanpa menghitung argumennya, sebagaimana False && undefined yang bernilai False.
• Evaluasi berhenti pada weak head normal form, yaitu konstruktor terluarnya, sehingga seq tidak memaksa komponen di dalamnya.

Referensi#

• Haskell 2010 Language Report, Bab 3 — haskell.org — Pernyataan resmi bahwa Haskell adalah bahasa non-strict beserta semantik dasarnya.
• Debug.Trace — Hackage — Semantik trace, yaitu mencetak pesan ke stderr tepat ketika ekspresinya dipaksa.
• Lazy evaluation — Haskell Wiki — Penjelasan mekanisme call-by-need dan peran sharing di dalamnya.