Pemrograman: Memrogram dengan sesuatu yang lebih sedikit daripada ketiadaan

• Tulisan ini memuat narasi satir tentang seorang kandidat dalam situasi wawancara yang mencoba mengimplementasikan soal FizzBuzz sederhana dengan kombinator fungsi murni berbasis kalkulus lambda
• Tokoh utamanya memulai dengan JavaScript, tetapi perlahan mendefinisikan kombinator S, K, I dan merekonstruksi sendiri struktur dasar bahasa
• Setelah itu, ia merepresentasikan boolean, angka, daftar, dan string hanya dengan kombinator, lalu mengimplementasikan rekursi melalui kombinator Y
• Pada akhirnya FizzBuzz diselesaikan dalam gaya point-free sepenuhnya, tetapi kodenya berkembang hingga ke tingkat yang tak lagi bisa dipahami manusia
• Tulisan ini mengeksplorasi hakikat bahasa pemrograman dan ekstrem abstraksi secara jenaka, sambil menampilkan satire diri budaya developer

---

Awal wawancara: FizzBuzz dan kombinator

• Cerita dibuka dengan pewawancara Dana yang meminta kandidat memecahkan soal FizzBuzz
  • Alih-alih memakai perulangan biasa, kandidat mulai menyelesaikan masalah dengan mendefinisikan kombinator S dan K
  • Dana kebingungan, tetapi kandidat berkata, “sedikit lagi selesai,” lalu terus melanjutkan
• Kandidat kemudian mendefinisikan berbagai kombinator seperti I, B, C, W, T dan memakainya sebagai komponen dasar bahasa baru
  • Tiap kombinator mengimplementasikan konsep inti kalkulus lambda seperti komposisi fungsi, pertukaran argumen, dan penerapan diri
  • Dalam komentar kode muncul nama alias kombinator seperti “Bluebird, Cardinal, Warbler, Thrush”

Definisi boolean dan angka

• Kandidat membangun logika boolean dengan mendefinisikan TRUE, FALSE, NOT hanya lewat kombinator
  • Saat Dana bertanya, “ini kalkulus lambda ya,” kandidat menjawab, “kalkulus lambda terlalu gemuk”
• Lalu ia menyusun sistem bilangan (Church numeral) dengan mendefinisikan ZERO, SUCC, PRED, IS_ZERO dan lainnya
  • SUCC mengimplementasikan suksesor, PRED pendahulu, dan DECREMENT operasi pengurangan yang tidak turun di bawah 0
  • Angka dari ONE sampai TEN didefinisikan secara berurutan

Rekursi dan kombinator Y

• Kandidat mendefinisikan fungsi ADD lalu secara bertahap mengubahnya ke bentuk point-free
  • Ia mendefinisikan ADD_MAKER, lalu membungkusnya dengan kombinator Y agar rekursi menjadi mungkin
  • Dana menunjukkan bahwa rekursi juga bisa dilakukan di JavaScript, tetapi kandidat menjawab, “sebentar lagi ini bukan JavaScript”
• Ketika eager evaluation di JavaScript menyebabkan stack overflow, kandidat menjalankan kode itu di interpreter JS “lazy” bernama Skoobert
  • Hasilnya berhasil menampilkan 3

Aritmetika, daftar, dan string

• Kandidat mengimplementasikan semua operasi aritmetika seperti SUBTRACT, MULTIPLY, MOD, DIVIDE berbasis kombinator
  • Tiap operasi disusun dengan menggabungkan IS_ZERO, PRED, SUCC dan lainnya secara rekursif
• Setelah itu ia membangun struktur daftar dengan mendefinisikan CONS, FIRST, REST, EMPTY
  • Operasi fungsional tingkat tinggi seperti MAP, FOLD, RANGE, CONCAT juga diimplementasikan dalam bentuk kombinator
• Untuk menampilkan daftar sebagai string, ia menulis fungsi renderList dan showLines
  • Dana tampaknya sudah menyerah dan tidak lagi bereaksi

Penyusunan karakter dan string

• Kandidat mendefinisikan kode karakter dari 1 sampai 9, lalu per puluhan, menggunakan kombinator
  • Dari CHAR_A sampai CHAR_Z dan CHAR_0 sampai CHAR_9, semuanya direpresentasikan sebagai kombinasi bilangan
• Melalui fungsi ARRAY, string diubah menjadi daftar, lalu dibentuk FIZZ, BUZZ, dan FIZZBUZZ
  • Fungsi extractString dipakai untuk mengubah daftar itu menjadi string sungguhan
  • Hasil output di konsol adalah "fizzbuzz"

Konversi dari angka ke string

• Didefinisikan NUMBER_TO_DIGIT_LIST untuk mengubah angka menjadi daftar digit, dan NUMBER_TO_STRING untuk mengubahnya menjadi string
  • Dengan DIVIDE, MOD, dan TEN, tiap digit dipisahkan satu per satu
  • Pemetaan ke karakter angka dilakukan melalui daftar DIGITS_NUMERAL
• Melalui proses ini, konversi angka → karakter → string menjadi sepenuhnya mungkin di dalam sistem kombinator itu sendiri

Penyelesaian FizzBuzz

• FIFTEEN dan ONE_HUNDRED didefinisikan, lalu MAP dan RANGE digunakan untuk membuat daftar dari 1 sampai 100
  • Untuk tiap angka, kelipatan 3, 5, dan 15 diperiksa untuk menampilkan "Fizz", "Buzz", "FizzBuzz", atau string angkanya
  • Hasil akhir ditampilkan dengan showLines(extractString)(FIZZBUZZ_RESULT)
• Saat Dana bertanya, “sekarang puas?”, kandidat justru menghapus semua definisi variabel dan menulis ulang kode hanya dengan kombinator murni
  • Hasilnya adalah ekspresi raksasa yang terdiri hanya dari S dan K sepanjang ribuan baris

Penutup dan makna

• Tulisan ini sekaligus mengeksplorasi komponen paling mendasar bahasa pemrograman dan menyindir kecenderungan developer membuat masalah sederhana menjadi terlalu rumit
  • Judul “memrogram dengan sesuatu yang lebih sedikit daripada ketiadaan” melambangkan upaya merekonstruksi dunia dari unit bahasa yang paling minimal
• Karya ini adalah bentuk sastra teknis yang menguraikan pemahaman mendalam tentang functional programming, kalkulus lambda, dan logika kombinator melalui humor dan narasi
  • Pada saat yang sama, tulisan ini secara satir menampilkan “semangat developer yang bahkan mengubah FizzBuzz menjadi eksperimen filosofis”

[GN⁺]

Komentar Hacker News

• Sepertinya banyak orang berpikir, “Ini sebenarnya apa?”, jadi saya coba jelaskan inti dari combinator
  combinator adalah fungsi yang tidak mengubah state global dan tidak menangkap variabel luar. Jika diberi argumen yang sama, hasilnya selalu sama, dan tidak memberi pengaruh apa pun pada bagian lain dari sistem
  Jika fungsi-fungsi murni seperti ini digabungkan, hasilnya juga menjadi combinator lain. Artinya, komposisi fungsi murni tetap merupakan fungsi murni
  Fungsi seperti ini juga bisa dengan mudah ditulis dalam assembly atau C. Misalnya, jika Anda mengimplementasikan S dan K secara langsung di x64, lalu mengompilasi Common Lisp berbasis combinator di atasnya, pada akhirnya Lisp berjalan di atas dua fungsi assembly saja
  Performanya mungkin kurang bagus, tetapi jika Anda membuat beberapa ratus pola yang sering dipakai sebagai inline combinator dan memberi nama pada masing-masing, itu bisa menjadi “mesin” yang cukup praktis
  Struktur seperti ini juga mirip dengan Forth yang takut pada mutation, bytecode VM, atau CPU yang menyebut combinator sebagai “instruksi”
  Pada akhirnya, combinator bisa disebut sebagai ekspresi ilmu komputer terapan yang sebisa mungkin mengabaikan detail implementasi. Karena itu, bisa dibilang ia lebih sederhana daripada lambda calculus
  Jika Anda mengimplementasikan lambda calculus dengan beberapa combinator, lalu menaruh Lisp di atasnya, pekerjaan yang bergantung pada mesin di lapisan paling bawah stack menjadi sangat berkurang

  • Rasanya seperti ada satu fungsi di suatu tempat yang memanggil dirinya sendiri lalu menerima seed round
  • Saya pernah mencoba hal serupa saat masih mahasiswa (bukan Lisp, melainkan bahasa sederhana yang macro expansion-nya menuju lambda calculus), dan fakta bahwa semuanya bisa diimplementasikan hanya dengan S dan K benar-benar mengejutkan. Tapi pada saat yang sama, betapa tidak efisiennya itu juga sama mengejutkannya. Meski begitu, situasinya jauh membaik jika instruction set diperbesar
  • Secara teori semua ini memang mungkin, tetapi dalam praktiknya sebaiknya memilih fondasi komputasi yang lebih praktis daripada graph rewriting. Kecuali Anda memang sedang bereksperimen dengan batas-batas komputabilitas, ini nyaris cuma trik pesta. Selain itu, representasi angka juga jadi masalah. Minimal harus memakai integer komplemen dua dan destructor yang efisien supaya layak dikagumi
  • Saya penasaran apakah Lisp yang diimplementasikan di atas combinator seperti ini benar-benar ada. Kalau ada, sepertinya akan cukup seru untuk di-porting

• let A = (x) => (y) => (z) => x(z)(y((w) => z))
  

  Tinggal menggabungkannya beberapa kali saja

  let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
  let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
  

  “Saya sama sekali tidak pakai lambda calculus. Itu bahasa yang terlalu menggelembung.”
  Tapi sebenarnya combinatory logic lebih menggelembung. Untuk mengekspresikan program yang sama, dibutuhkan lebih banyak bit
  Lambda calculus justru salah satu bahasa paling ringkas
  Bahkan dalam bahasa eager seperti JavaScript, Anda bisa membuatnya menjadi lazy dengan membungkus argumen dalam lambda dummy. Untuk contohnya, lihat interpreter JS BLC ini
  Untuk makalah terkait, lihat PDF ini dan contoh IOCCC ini

  • Hal yang menarik adalah, beberapa interpreter lambda calculus tercepat (misalnya uni.c) pada akhirnya menghitung dengan mengubah lambda expression menjadi combinatory logic. Hanya saja, mereka memakai himpunan dasar yang lebih besar daripada S dan K
  • “bloated language” berarti bahasa dengan banyak fitur yang tidak perlu. Misalnya, C++ bisa lebih pendek daripada C, tetapi tetap merupakan bahasa yang jauh lebih kompleks
  • Melihat blok kode itu membuat suara yang keluar dari mulut saya hampir sama persis dengan daftar argumennya
  • Sepertinya ada kesalahan tanda kurung pada definisi K dan S. Versi yang diperbaiki adalah sebagai berikut

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
    let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
    

    Dan membuat bahasa eager menjadi lazy bisa dilakukan seperti ini

    let A = x => y => z => () => x()(z())(y()(w => z()));
    

  • Muncul pertanyaan, “w itu apa?”

• “Tahu FizzBuzz?”
  “Tentu. Yang versi code golf 10 karakter, versi 12 baris yang bisa dipahami junior, atau versi benar-benar aneh buat pamer pengetahuan nyeleneh?”

  • Setelah melihat ini, saya mencoba mengimplementasikan FizzBuzz tercepat di C64 BASIC. Pagi saya terbuang dengan menyenangkan
    Tautan hasilnya

• Penjelasan combinator logic-nya benar-benar keren. Gaya tulisannya mengingatkan saya pada seri ini

  • Ini lebih terasa seperti pertunjukan demonstratif daripada penjelasan. Meski begitu, tetap cukup mengesankan
  • Memang terasa seperti terinspirasi dari seri itu. Akan lebih bagus kalau nama penulisnya disebutkan
  • Di Inggris akses ke sana diblokir karena Online Safety Act, jadi sayang sekali

• Ini mengingatkan saya pada tulisan lama “FizzBuzz in TensorFlow”
  Tautan

  • Kali ini setidaknya saya masih bisa mengikutinya, jadi itu menyenangkan

• Kerangka wawancara pemrograman seperti ini rasanya agak keliru
  Tujuan wawancara adalah (1) memeriksa pengetahuan pemrograman kandidat, (2) memeriksa kecocokan dengan budaya pemrograman perusahaan
  Misalnya, jika Anda sedang merekrut untuk posisi JavaScript tetapi kandidat sangat tenggelam dalam combinatory logic, kemungkinan besar itu tidak cocok secara budaya. Jadi tidak aneh kalau dia gagal lolos

  • Mungkin ini merujuk ke seri ini. Hanya saja, itu tidak disebutkan secara eksplisit di teks aslinya
  • Kadang komentator HN terasa seperti orang-orang yang lupa cara bersenang-senang
  • Ini memang menekankan keberagaman dalam pemrograman, tetapi itu hanya salah satu bentuk perekrutan untuk keahlian dalam ekosistem tertentu. Sebagian besar adalah pilihan untuk menangani kode legacy atau memanfaatkan ekosistem yang sudah ada
  • Ucapan seperti “kalau IQ rendah ya gagal” memang lucu, tapi pada akhirnya kalau uangnya cukup, gaya OOP/FP/FRP apa pun bisa diikuti
  • Di dunia nyata, wawancara ideal seperti ini hampir tidak ada. Kebanyakan adalah pewawancara frustrasi yang memaksakan pandangan dunianya. Pekerjaan nyata hampir tidak ada hubungannya dengan isi wawancara

• Sudah saatnya mengingat Moses Schönfinkel
  Ia menciptakan combinatory logic pada tahun 1920 saat menjadi murid Hilbert. Setelah kembali ke Rusia, ia menderita penyakit mental dan meninggal miskin di Moskow. Menurut Wikipedia, makalah-makalahnya dibakar tetangga untuk dijadikan bahan pemanas

• Blok kode terakhir cukup besar sampai memunculkan scroll (166KB)
  S dan K adalah fungsi curried yang hanya menerima satu argumen setiap kali
  Untuk detail lebih lanjut, lihat jawaban StackOverflow ini

  • Bagian paling lucu adalah saat syntax highlighting menyerah ketika saya scroll ke bawah

• Saya sangat suka nama-nama burung seperti “Bluebird, cardinal, warbler, thrush”. Rasanya ingin menjadikannya konvensi penamaan baru
  “Barendregt. Church terlalu mainstream.”
  “Sebentar lagi ini bahkan tidak akan jadi JavaScript lagi.”
  Rasanya seperti Douglas Adams yang mengajarkan SICP

  • Nama-nama burung itu berasal dari buku Smullyan, 『To Mock a Mockingbird』. Di sana ada lebih banyak burung lagi

• “Itu… Y combinator?”
  “Betul. Untuk rekursi, itu memang diperlukan.”
  Fakta menarik: fixed-point combinator jumlahnya tak terbatas. Artinya, rekursi bisa diimplementasikan dengan tak terhingga banyak cara bahkan tanpa Y combinator