Berpikir dalam Bahasa Array

• Pemrograman K berfokus pada memindahkan kode yang dieksperimenkan di REPL ke skrip, sambil terus menyusutkan pola imperatif besar menjadi pola array deklaratif yang lebih kecil
• Skrip ngn/k dijalankan baris demi baris seperti input REPL, dan data serta fungsi yang disimpan dapat dimuat ke REPL dengan \l file.k
• Jika perkalian matriks dengan tiga loop ala Wikipedia dipindahkan apa adanya, akan muncul banyak variabel global, loop bersarang, dan mutasi, sehingga bertentangan dengan keunggulan K
• Proses perbaikannya melewati fold +/, each ', eachright /:, eachleft \:, penghapusan transpose, dan transformasi tacit, lalu dipadatkan dari matmul: {x{+/x*y}\:y} menjadi matmul: (+/*)\:
• Contoh perkalian matriks menunjukkan bahwa kemahiran K terletak pada pengulangan proses pemadatan kode untuk mengubah prosedur kompleks menjadi ekspresi array yang lebih mudah dibaca

---

Alur pengembangan K yang berpusat pada REPL

• Seluruh kode sumber dapat dilihat di matmul.k di GitHub
• Pemrograman K sebagian besar dilakukan di REPL, sehingga cocok untuk bereksperimen dan menyempurnakan kode dengan cepat di atas kode sebelumnya
• Kombinasi ngn/k dan rlfe mendukung riwayat dengan tombol panah atas/bawah, cukup untuk mengembangkan program K yang lebih besar
• Alurnya wajar: fungsi terlebih dahulu diuji di REPL, lalu dipindahkan ke kode sebenarnya
• Prettyprinting di ngn/k selalu mengembalikan data K yang valid, sehingga beberapa nilai dapat dihitung lebih dulu untuk mempercepat program

Model eksekusi skrip K

• Skrip K dijalankan seolah-olah diketikkan ke REPL
  • Setiap baris dijalankan secara berurutan
  • Jika sebuah baris tidak diakhiri dengan titik koma, nilai kembaliannya akan dicetak
• Skrip memperbolehkan definisi multibaris untuk meningkatkan keterbacaan
• Untuk memakai data dan fungsi yang tersimpan dari REPL, jalankan \l file.k
  • File dijalankan
  • Data dalam file dimuat
  • Jika file yang sama dimuat beberapa kali, data sebelumnya akan ditimpa
• Perintah lain dapat dilihat di bantuan REPL yang diakses dengan \

Cara mengurangi pola dalam bahasa array

• K dan pemrograman array adalah proses untuk terus menyederhanakan pola
• Bahkan pola yang besar dan sulit dikelola biasanya memiliki setidaknya satu cara untuk diperkecil menjadi bentuk yang lebih kecil, deklaratif, dan mudah dibaca
• Pembahasan terkait dapat dilihat lebih rinci di Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17
• Titik awal yang umum adalah situasi ketika ingin menerjemahkan algoritme terkenal dari GeeksforGeeks atau Wikipedia ke K
• Contohnya menggunakan perkalian matriks

Ketika perkalian matriks imperatif dipindahkan apa adanya

• Matrix multiplication algorithm dari Wikipedia mengisi matriks C dengan tiga loop i, j, k dan akumulasi sum
• Jika diterjemahkan langsung ke K, banyak nilai global seperti A, B, n, m, p, C, i, j, k, sum akan dialokasikan
• Kode ini memakai K seperti bahasa imperatif, sehingga kurang selaras dengan desain K
• Masalahnya dapat dipersempit menjadi tiga hal
  • Banyak alokasi global
  • Beberapa tingkat loop bersarang masih tersisa
  • Mutasi sering terjadi

Melipat dan mengurangi mulai dari loop terdalam

• Loop terdalam menginisialisasi sum ke 0, lalu memutar k untuk mengakumulasi A[i;k]*B[k;j]
• Perbaikan pertama adalah memakai fold / untuk mengubah penjumlahan menjadi +/
  • Global sum hilang
  • Bentuknya dirapikan menjadi C[i;j]::+/...
• Berikutnya, dengan memanfaatkan bahwa each ' mengembalikan array, nilai kembalian dari loop bersarang dapat langsung digunakan tanpa mengubah C
• Setelah tahap ini, hanya tersisa tiga loop tanpa mutasi, dan variabel intinya adalah i, j, k

Proses menghilangkan k, j, i

• Peran tiga variabel tersebut adalah sebagai berikut
  • i mengindeks setiap baris A
  • j mengindeks setiap kolom B
  • k mengindeks setiap kolom A dan setiap baris B
• k membuat setiap baris A dan setiap kolom B dipasangkan untuk dikalikan, sehingga indeks perantara dapat dihilangkan dan dicocokkan langsung
  • Pada tahap ini, satu loop dan m tidak lagi diperlukan
• Untuk menghapus j, perlu mengambil setiap kolom B dan memasangkannya dengan A[i]
  • Transpose B lalu pasangkan setiap elemen dengan eachright /:
• i juga dapat dihilangkan dengan cara yang sama
  • Gunakan eachleft \: untuk memasangkan setiap baris A dengan setiap kolom B
• Setelah proses ini, bentuknya menjadi berikut tanpa global

matmul: {x{+/x*y}/:\:+y}

Menghapus transpose dan bentuk tacit akhir

• Transpose + mahal biayanya, sehingga dapat dihapus
• Cara sebelumnya adalah cara naif yang mengalikan setiap baris x dengan setiap kolom y
• Sebagai gantinya, jika setiap baris B disesuaikan dengan keseluruhan A, pekerjaan yang sama dapat dilakukan secara implisit

matmul: {x{+/x*y}\:y}

• Fungsi ini dapat diubah menjadi bentuk tacit dengan menerapkan aturan dari Chapter 3
• Hasil akhirnya adalah sebagai berikut

matmul: (+/*)\:

Intuisi bahasa array yang dibangun lewat latihan

• matmul: (+/*)\: dirapikan menjadi fungsi perkalian matriks yang khas K
• Proses pemadatan mungkin awalnya terlihat memiliki banyak tahap
• Semakin banyak berlatih K, pemadatan kode akan berubah menjadi pekerjaan yang lebih mudah dan intuitif
• Perkalian matriks adalah prosedur sederhana yang cocok dengan dukungan array di K
• Bab berikutnya akan membahas algoritme yang kurang cocok dengan K dan cara menanganinya

[GN⁺]

Komentar Hacker News

• Bagi saya, hal yang paling meyakinkan dalam menunjukkan potensi bahasa array adalah video Aaron Hsu yang menjelaskan bagaimana ia mengembangkan kompiler APL paralel Co-dfns: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
  Dengan nama arcfide di HN, ia juga beberapa kali menulis tentang kepadatan makna, dan menjelaskan bahwa kode APL dirancang agar cara kerja, konteks sekitar, dan dependensi bisa dilihat hampir tanpa perlu banyak berpindah dalam satu layar: https://news.ycombinator.com/item?id=13571159
  Perspektifnya adalah bahwa jika nama algoritme bisa dibuat sesingkat panjang uraian algoritme itu sendiri, maka kode akan dibaca per idiom seperti membaca frasa bahasa Inggris, dan mungkin akan lebih cepat mengubah langsung semua titik penggunaan yang terlihat di layar daripada membuat abstraksi yang dapat digunakan ulang

  • Saya juga penasaran apakah LLM dengan jendela konteks yang terbatas mungkin akan menangani APL lebih baik daripada bahasa lain
  • Menurut saya, kalau perlu menulis penjelasan sepanjang itu, berarti kodenya memang jelek dilihat. Kalau simbol-simbolnya dipilih agar saat berdempetan terlihat tidak terlalu buruk, mungkin tidak perlu menghabiskan 18 jam untuk meyakinkan orang bahwa bahasanya sebenarnya tidak buruk

• Kalau belum terlalu memahami pemrograman array, saya merekomendasikan The Array Cast sebagai materi pengantar: https://www.arraycast.com/episodes/
  Alamat RSS-nya adalah https://www.arraycast.com/episodes?format=rss

  • Saya mendengarkan sekitar 5 episode awal The Array Cast demi mencoba diyakinkan, tetapi pada akhirnya tetap tidak terpengaruh. Para pembawa acara mengatakan bahwa notasi singkat dan simbol non-ASCII dalam bahasa array akan terasa baik-baik saja setelah terbiasa, dan layak diterima karena kelebihannya, tetapi sebagian besar kelebihan itu sudah merupakan hal yang akrab dari fungsi tingkat tinggi di bahasa arus utama modern
    map/filter/reduce sudah ada hampir di mana-mana, dan rasanya mereka mengabaikan fakta bahwa semua itu bisa dipakai tanpa harus mempelajari sistem notasi baru yang mirip logogram
  • Dari sini saya jadi mengenal BQN, tetapi saya masih belum tahu apakah akan memakainya di lingkungan produksi nyata. Saya memang menyukainya, tetapi selain R, NumPy, dan Julia, kebanyakan bahasa array terasa asing, dan kalau terlalu dalam masuk ke APL, J, atau BQN, rasanya saya justru akan menjauhkan diri dari orang-orang yang nanti bisa dimintai bantuan

• Saya langsung jatuh hati setelah mengenal APL/APL2 pada terminal kertas di tahun 70-an yang benar-benar memakai overstriking, tetapi kemudian setelah mengenal pemrograman fungsional lewat ML dan Haskell, saya sadar bahwa hal yang paling saya sukai dari APL sebenarnya bukan array, melainkan kemampuan komposisi fungsi
  Haskell sepenuhnya murni dan memiliki tipe yang diterapkan secara menyeluruh, jadi dalam hal ini jauh lebih baik, lebih menyenangkan, dan lebih kuat daripada APL. Saya sudah membuat banyak proyek kecil hingga menengah, juga membuat prototipe yang menunjukkan bahwa parser untuk LLVM Flang bisa diimplementasikan dengan parser combinator, dan setiap tahun saya juga menyelesaikan Advent of Code hanya dengan total beberapa ratus baris. Kalau Anda menyukai APL, Haskell juga layak dicoba
  Sekarang aspek APL sebagai “notasi sebagai alat berpikir” terasa seperti ungkapan yang membenarkan keringkasan berlebihan. Ini bagus untuk menunjukkan kekuatan komposisi, tetapi juga bisa merusak kejelasan

  • Saya merasa terus mengulang hal yang sama setiap kali topik ini muncul, tetapi setelah cukup mahir memakai point-free Haskell, saya hampir tidak pernah lagi menyentuh J dan K. Jika functor juga ikut dipakai, hasilnya bahkan lebih kuat daripada train of verbs, dan <=< memang sudah ada, lalu jika memakai padanan untuk fmap, semuanya benar-benar berjalan sangat baik
    |||, +++, &&&, *** juga bagus, dan kita bahkan bisa membuat operator UTF-8 sendiri agar lebih singkat dan lebih indah. Hanya saja, sayang sekali kode Haskell serius yang dipakai di pekerjaan nyata atau dipublikasikan jarang ramah terhadap ruang layar vertikal dengan gaya seperti ini
  • Akan menyenangkan jika bisa melihat tautan ke source code Advent of Code

• Ingin tahu bagaimana bahasa array umumnya menangani masalah seperti “mencari semua bilangan lebih kecil dari N yang memenuhi predikat P”. Misalnya mencari bilangan prima di bawah 1000 atau tripel Pythagoras dengan z lebih kecil dari 1.000.000
  Dalam bahasa imperatif, kita akan memeriksa predikat di dalam loop, dan dalam bahasa fungsional kita akan memakai rekursi atau map/filter pada lazy list, tetapi di bahasa array saya memahaminya biasanya dengan membuat array 1..N, menerapkan predikat untuk membuat array mask, lalu menyaring array asli dengan mask tersebut
  Jika N sebesar 1 miliar dan predikatnya hampir selalu salah, membuat 1..N dan mask berarti dua array sementara raksasa, yang tampak sangat boros dari sisi memori dan sumber daya. Saya penasaran apakah bahasa array memang terus membuat array sementara seperti ini hingga melambat, atau implementasinya mengoptimalkan dengan cara seperti lazy evaluation

  • Benar, itu memang memboroskan banyak memori. Namun memori itu murah, dan jika perlu perhitungannya bisa dibagi per blok. Dalam praktiknya jarang benar-benar kehabisan memori, tetapi blocking berguna untuk tetap berada di tingkat cache yang lebih rendah
    Sebaliknya, bahasa skalar pada dasarnya memproses satu nilai pada satu waktu, sehingga membuang paralelisme potensial yang dimanfaatkan bahasa array melalui algoritme SIMD. Ini juga tidak terlihat sebagai masalah besar hanya karena kita sudah terbiasa dengan keadaan sekarang, dan solusinya juga blocking
    Apakah bahasa array benar-benar lebih baik tergantung pada masalahnya. Dalam sebagian besar penggunaan praktis, performa sama sekali tidak penting, dan reputasi k tampaknya juga lebih karena kdb cepat sebagai basis data daripada karena implementasi k sendiri merupakan bahasa yang cepat. Meski begitu, hanya dengan berfokus pada algoritme array yang elegan alih-alih optimisasi detail per mesin, kita bisa mendapatkan kecepatan yang mengejutkan: https://mlochbaum.github.io/BQN/implementation/versusc.html
  • Ada beberapa jalan memutar. Lazy evaluation adalah salah satunya, dan Kap menggunakannya: https://aplwiki.com/wiki/KAP
    Cara lain yang jelas adalah melakukan loop fusion pada seluruh badan sehingga array sementara tidak muncul. Pilihan yang lebih sederhana adalah membagi array input/output menjadi chunk berukuran puluhan KB untuk membatasi penggunaan memori sementara yang tidak perlu; setahu saya belum ada bahasa array yang melakukan ini secara otomatis, dan saya ingin mencobanya di CBQN suatu saat nanti. Pengguna juga bisa melakukannya secara manual, dan untuk memaksimalkan performa memang sering perlu begitu
  • Intuisinya sebagian besar benar, tetapi dalam praktiknya ini masalah yang jarang. Keluarga k, misalnya ngn/k, memiliki struktur lazy yang memperlakukan iota seperti !10000000 sebagai rentang sederhana, bukan benar-benar membuat array berisi sepuluh juta integer dari 0 sampai 10.000.000
    Tentu saja, tergantung operator apa yang dipakai, pada akhirnya array seperti itu bisa saja tetap terbentuk. Ada juga optimisasi seperti mengubah pola +|x, yaitu membalik x lalu mengambil elemen pertama, menjadi sekadar mengambil elemen terakhir
  • Anda tampaknya menganggap pembuatan array itu terjadi secara harfiah. Tidak ada alasan bahasa array secara internal tidak bisa memproses per chunk. Bahkan jika Anda meminta array integer berisi 10 miliar elemen, belum tentu ia akan membuatnya secara naif apa adanya
  • Banyak bahasa array memang benar-benar memiliki masalah ini. Lebih tepatnya, masalahnya adalah pendekatan yang sederhana dan intuitif cenderung menghitung jauh lebih banyak daripada yang diperlukan
    Tentu saja Anda bisa menulisnya dengan cara berbeda untuk menghindarinya, tetapi solusi seperti itu bisa menjadi lebih panjang dan kurang indah. Dialek APL yang sedang saya kerjakan, Kap, menunda perhitungan sampai hasilnya benar-benar dibutuhkan, sehingga dalam banyak kasus Anda bisa menulis kode secara intuitif tanpa menghitung hasil yang nantinya dibuang

• Hal-hal terbesar yang saya sadari saat memakai bahasa array, khususnya k, adalah sebagai berikut. Verb adalah algoritme, sedangkan dalam bahasa imperatif dan berorientasi objek kita sering harus mengimplementasikan sendiri algoritme umum seperti find, sort, dan group
  Rangkaian verb atau adverb adalah bentuk komposisi paling langsung yang pernah saya pakai, dan komposisinya mudah serta alami. Program jadi tampak sebagai komposisi algoritme, bukan kumpulan kalimat dan ekspresi
  Jika konsep domain dan kodomain diperlakukan konsisten pada array, map, dan fungsi, pilihan desain menjadi lebih sederhana, dan evaluasi dari kanan ke kiri membuat mata tidak perlu meloncat ke sana-sini saat membaca kode
  Alih-alih membawa data ke kode, pendekatan mengirim kode ke data menjadi mungkin dan lebih disukai. Sebagian besar proyek k besar, di luar komentar, muat dalam MTU jaringan, yaitu 1540 byte. Bonus lain dari k adalah view dapat langsung mengimplementasikan relasi fungsional, dan hot code loading melalui interpreter memungkinkan aplikasi yang berjalan “selamanya”

• Kesan pribadi saya yang terbatas dan bias setelah mengerjakan soal bahasa K untuk persiapan wawancara kerja adalah bahwa bahasanya memang sengaja dibuat sulit dipahami. Ini bahasa yang bagus untuk teka-teki dan solusi yang cerdik
  Tetapi menurut saya yang benar-benar mengajarkan bahasa array dan cara berpikir dengan array adalah pengalaman menangani array NumPy di Python

  • Penasaran, wawancara di mana?

• Dari pengalaman memakai J sekitar 50 jam, saya merasa paradigma ini sejujurnya terlalu berat ke satu sisi
  Saya tidak yakin memikirkan semua masalah sebagai susunan array itu membantu sebagai alat berpikir. Jika kita bebas membuat struktur data yang benar-benar menangkap masalah dengan baik, bagian algoritmenya bisa jauh lebih sederhana
  Menurut saya Anda harus lebih pintar untuk memakai APL/J/K. Dalam bahasa yang lebih fleksibel, pendekatan yang langsung sering kali tidak mungkin dilakukan di sini, sehingga masalahnya harus ditransformasikan, dan proses itu bisa menuntut jauh lebih banyak pemikiran

• Contoh ini berbasis K, tetapi ada bahasa array lain yaitu J: http://jsoftware.com
  Di J, Anda bisa menulis dot =: +/ . *, P =: 2 3 4, Q =: 1 0 2, lalu P dot Q untuk mengembalikan hasil kali dalam P dan Q, yaitu 10

  • Bahasa array yang asli adalah APL, dan hasil kali dalam bisa ditulis sebagai dot←+.×. Namun jika notasi yang dieja lengkap sudah hampir sependek nama yang layak, rasanya tidak perlu memberi nama, dan Anda bahkan mungkin harus menambahkan spasi di sekitar nama itu
  • Saya masih belum benar-benar melihat apa keunggulan ini dibanding Haskell. Anda bisa menulis dot = (sum.) . zipWith (*), p = [2, 3, 4], q = [1, 0, 2], lalu p `dot` q
    Bagi saya, satu-satunya perbedaan yang terlihat adalah sum dan zipWith memakai nama, dan lifting atau transformasi struktur tidak terjadi secara “ajaib”
  • Di KlongPy, hasil kali dalam ditulis dot::{+/x*y}. Bentuknya P::[2 3 4], Q::[1 0 2], dan dot(P;Q)

• Melihat contohnya, saya tidak paham apa maknanya. Apakah performanya memang lebih baik dalam hal apa pun?
  Sintaks perkalian matriks memang lebih singkat, tetapi itu tampaknya karena bahasa K menuntut banyak konteks bawaan tentang cara kerjanya untuk tetap diingat di kepala

  • Fakta bahwa itu lebih ringkas sendiri sudah bernilai. Terutama jika dipikirkan bahwa matematika adalah proses memadatkan semakin banyak konsep ke dalam definisi tingkat yang lebih tinggi. Ketika konsep tingkat lebih tinggi menjadi elemen primitif, kita bisa berpikir lebih cepat dan membangun objek yang lebih kompleks
  • Performanya memang bisa lebih baik. Komputer sangat cepat dalam menelusuri array, terutama jika bisa memanfaatkan SIMD, tetapi itu bukan segalanya
    Layak mencoba bahasa array dan memainkannya sampai paradigmanya terasa masuk akal. Sering kali kode imperatif lebih baik diekspresikan dengan gaya array, dan fungsi yang panjang serta remeh bisa sangat disederhanakan hanya dengan operasi array atau dengan memadukannya dengan gaya lain
  • Verbositas juga punya biaya, dan jika Anda percaya bahwa hak untuk menjadi bertele-tele hanya dimiliki fungsi yang benar-benar kompleks, maknanya jadi mudah terlihat
    Di Haskell, jika membandingkan (+) <$> Just 1 <*> Just 2 dengan do x <- Just 1; y <- Just 2; Just (x + y), pada tingkat kompleksitas seperti ini saya akan selalu memilih yang pertama. Yang kedua memakan lebih banyak ruang sehingga terasa seolah ada sesuatu yang lebih rumit sedang terjadi
    Untuk pekerjaan yang lebih rumit, daripada memakai bentuk kedua saya ingin memecahnya menjadi fungsi-fungsi kecil agar variasi pertama tetap masuk akal. Ini adalah kompromi yang mengubah “sebagian pemula bisa membacanya dengan cepat” menjadi “siapa pun di atas tingkat pemula bisa membacanya”
    Jika yang dioptimalkan adalah “sebagian pemula bisa membacanya”, menurut saya penurunan hasil tambahannya sangat besar; karena itu saya lebih memilih menargetkan agar “siapa pun di atas tingkat pemula”, atau dalam beberapa kasus “siapa pun di atas tingkat menengah”, bisa membacanya

• Dalam bahasa apa pun selalu ada banyak alasan untuk memakainya, dan banyak juga alasan untuk tidak memakainya. Tetapi inti persoalannya bukanlah notasi yang pendek, kejelasan yang relatif, atau kemampuan untuk dikompilasi menjadi kode yang cepat, melainkan apakah programmer yang datang belakangan bisa memodifikasi dan memelihara kode itu untuk penggunaan nyata
  Terlalu sering programmer ingin memamerkan kemampuan leet mereka tanpa memikirkan orang malang yang nanti harus mengambil alih kode itu. Secara realistis, banyak kode leet pada akhirnya harus dibuang atau ditulis ulang sepenuhnya demi mendapatkan sesuatu yang bisa didukung dalam jangka panjang
  Saya butuh waktu lama untuk memahami ini, dan setelah itu saya berusaha menulis kode yang bersih, sederhana, dan mudah dipahami agar bisa dipelihara orang lain. Terlalu sering kode yang tadinya untuk dibuang malah mengeras menjadi infrastruktur dasar organisasi, lalu berubah menjadi sesuatu yang tak bisa dipahami oleh generasi berikutnya