Jadi, Anda Ingin Memahami Monads?

Penjelasan intuitif tentang konsep pemrograman fungsional yang tidak perlu membingungkan

Saya baru saja membaca sebuah artikel di mana seseorang yang malang berusaha keras untuk menjelaskan kepada pembaca apa itu monad dan gagal total karena dia sendiri tidak benar-benar memahaminya. Karena sebagian besar keinginan untuk membantunya, saya pikir mungkin masuk akal untuk menulis artikel yang memungkinkan orang memahami intuisi di balik monad terlebih dahulu tanpa membahas sintaksis bahasa fungsional yang gila.

Apakah saya berhasil melakukan ini atau tidak, Anda yang menilai, tetapi mari kita langsung saja.

Saya pertama kali menemukan monad ketika diperkenalkan oleh Eugenio Moggi sebagai cara untuk menyusun semantik bahasa pemrograman. Formulasinya elegan dan jelas memberikan bentuk matematis yang bagus untuk kelas konstruksi bahasa pemrograman yang sangat besar yang, hingga saat itu, hanya ditangani secara terpisah.

Apa yang Moggi bawakan dalam makalah itu (jika Anda bisa memahami matematikanya) adalah pemahaman yang mendalam tentang komputasi yang hanya muncul sekali dalam satu generasi. Ya, ini adalah makalah yang sangat intuitif yang memetakan intuisi ilmu komputer ke dasar matematika yang kuat. Saya akan meninggalkan sebagian besar matematika dari eksposisi di sini, tapi saya berharap untuk memberikan intuisi.

Mari kita mulai dengan ekspresi yang sangat sederhana: getc(). Pemrogram C mungkin mengenali ini mirip dengan fungsi yang Anda panggil untuk mendapatkan satu karakter dari sebuah file. Alih-alih file di sini, anggaplah file tersebut mendapatkan satu karakter dari keyboard. Ini adalah fungsi sederhana yang menghasilkan satu karakter. Anda dapat menggunakan fungsi ini di mana pun ekspresi karakter dapat digunakan (yaitu, secara nominal bertipe char). Jadi, misalnya, jika kita ingin memeriksa apakah pengguna menekan tombol q, kita dapat melakukan (getc() == ‘q’).

Namun secara komputasi, getc() sama sekali bukan char sederhana. Ini melibatkan serangkaian interaksi kompleks dengan lingkungan di luar program, termasuk sistem operasi, perangkat keras, dan pengguna. Saat kita memikirkan program, kearifan tradisional (yang diwarisi dari kalkulus λ) adalah hanya memikirkan nilai. Ini bagus jika Anda berurusan dengan entitas yang seluruhnya ada di dalam program. Namun getc() di sini memaksa kita untuk menghadapi kenyataan bahwa ada dunia lain di luar program yang juga harus kita hadapi. Hal ini disertai dengan fakta bahwa operasi I/O bisa gagal, atau operasi tersebut tidak selalu menghasilkan nilai yang sama, dan fakta bahwa pengguna mungkin tidak pernah menekan tombol sama sekali.

Di sinilah bagian pertama dari kejeniusan Moggi muncul. Dia memiliki intuisi bahwa suatu nilai secara kualitatif berbeda dari perhitungan yang menghasilkan nilai tersebut. Dengan kata lain, getc()adalah perhitunganyang menghasilkanchar dantidak boleh digabungkandengan char.

Jadi, daripada memberikan getc() tipe char, mari kita berikan tipe T[char], yang merupakan kependekan dari komputasi (atau proses) yang menghasilkan char. Pada awalnya, ini tampak seperti sebuah langkah mundur. Sekarang kita tidak bisa menggunakan getc()di semua tempat yang bisa kita gunakan untuk char, jadi (getc() == ‘q’) tidak lagi benar karena tipe di kedua sisi == berbeda. Apa yang harus kita lakukan sekarang?

Izinkan saya memperkenalkan Anda pada sepasang kata baru: injeksi dan proyeksi. Saat kita mengambil nilai bertipe char dan menyematkannya ke dalam tipe lain, seperti T[char], ini dikenal sebagai injeksi. Kebalikan dari injeksi dikenal sebagai proyeksi. Di sinilah kami mengekstrak nilai yang dimasukkan dari penyematan. Dengan kata lain, kami memproyeksikan char dari T[char]. Secara umum, injeksi dan proyeksi selalu dirancang untuk menjadi kebalikan satu sama lain: Keduanya menyusun fungsi identitas.

Jadi, apakah operator proyeksi sekarang mengizinkan kita mengeluarkan char dari T[char]? Seperti apa proyeksi ini? Untuk proses komputasi seperti getc(), kita “memproyeksikan” dari T[char] dengan menunggu panggilan I/O berakhir, menyajikan nilai, dan kemudian bekerja dengan nilai, menggunakannya seperti kita menggunakan nilai lain. char dan nilai lain apa pun yang diturunkan darinya. Namun, begitu kita keluar dari lahan komputasi dan lahan nilai, kita kini telah sepenuhnya mengabaikan fakta bahwa ada keseluruhan komputasi yang menghasilkan nilai dan mengembalikan kita ke tempat kita memulai (yaitu, tidak mampu mempertahankan nilai). dunia luar yang getc() menyeret kita ke dalamnya. )

Di sinilah bagian ke-2 dari kejeniusan Moggi dimulai. Dia mengusulkan operator proyeksi yang agak terbatas yang dia sebut let yang dengannya kita dapat menulis ulang tes sederhana kita di atas seperti ini (ini bukan bentuk akhir, tapi ini tempat yang baik untuk memulai) :

let c = getc() in (c == ‘q’)

Biarkan saya menguraikannya sedikit. Di sini, c bertipe char — bukan T[char].Tugas let ini adalah memproyeksikan char keluar dari T[char], mengikatnya ke nama c, dan mengizinkannya digunakan sebagai char di badan (ekspresi setelah in). Dalam hal ini, proyeksi berarti menunggu getc() mengembalikan karakter.

Jika let melakukan operasi proyeksi standar, ekspresi ini akan menghasilkan boolean di akhir. Namun, keseluruhan ekspresi ini masih memiliki operasi I/O (yaitu komputasi) yang terlibat dalam menghasilkan boolean ini. Artinya ekspresi ini tidak benar-benar mewakili boolean namun merupakan perhitungan yang menghasilkan boolean. Jadi hal yang benar untuk dilakukan adalah memberikan seluruh ekspresi let ini tipe T[boolean], yang berarti isi let harus mengembalikan tipe T[boolean].

Dalam formulasi Moggi, tipe ini wajib untuk semua ekspresi letyang diproyeksikan dan diterapkan oleh pemeriksa tipe. Untuk memastikan kami dapat memenuhi persyaratan ini, kami memperkenalkan operator, η, yang tujuan utamanya adalah memasukkan nilai bertipe τ ke Τ[τ]. Ini memaksa kita untuk mengingat bahwa nilai ini dihasilkan dari perhitungan. Jadi kita tulis ulang let di atas seperti ini:

let c = getc() in η(c == ‘q’)

Sekarang, jenis ekspresi ini adalah T[boolean]. Secara umum, ini berarti fakta bahwa suatu nilai dihasilkan dari suatu komputasi tidak pernah dilupakan. Jika kita harus menggunakan nilai yang dihasilkan oleh let ini di tempat lain, kita harus ingat bahwa itu adalah T[boolean]. Untuk mengekstrak boolean ini, kita memerlukan let lain, dan yang tubuhnya adalah T[something] dan seterusnya. Jika Anda sudah memahami paragraf ini dan ingin memamerkannya kepada teman-teman Anda, lemparkan kata-kata “hukum asosiatif monads”.

Dengan mengambil kesimpulan logis ini, program apa pun yang menggunakan komputasi pada akhirnya selalu menghasilkan jawaban bertipe T[x]dan bukan nilai bertipe x. Rahasia kecil kotor monads adalah ada satu proyeksi akhir yang perlu kita lakukan untuk mengekstrak x dari T[x]. Dalam praktiknya, setiap T selalu disertai dengan operasi proyeksi seperti itu, namun harus digunakan hanya di area yang teridentifikasi dengan sangat jelas di mana kita tidak lagi berupaya mempertahankan properti komputasi T[].

Tipe T[], bersama dengan η yang menyertainya, dan let adalah monad (terkadang juga diberi nama menarik “Kleisli triple”). Nama sebenarnya berasal dari struktur teori kategori yang memformalkan ide ini dalam lebih banyak matematika daripada yang perlu diketahui kebanyakan orang. Itu dia. Meskipun T[] merupakan singkatan dari komputasi yang melibatkan I/O dalam kasus kita, T[] dapat digunakan untuk berbagai jenis komputasi berbeda yang akan kita lihat di bawah.

Hanya itu yang ada pada monad. Tujuan dari formulasi ini adalah untuk dengan jelas mempartisi dunia komputasi yang berperilaku buruk ke dalam pengikatan (bagian dari let sebelum in yang mengikat nama ke nilai yang diproyeksikan dari komputasi) dari let dan dunia fungsional yang berperilaku baik di tubuh let. Dunia di dalam pengikatan penuh dengan ketidakpastian yang terkait dengan pengikatan, namun dunia di dalam tubuh bersih namun tetap mempertahankan fakta bahwa nilai-nilai tersebut berasal dari perhitungan.

Jadi meskipun saya memiliki “efek” (yang merupakan nama yang kami berikan untuk perhitungan ini) dalam program saya, saya dapat memikirkan sebagian besar program tanpa terlalu memikirkan efeknya karena efek tersebut sekarang dikemas dengan baik di T[]. Aturan let jangan sampai saya lupa saat saya menangani suatu komputasi dan saat saya menangani nilai yang dihasilkan oleh komputasi tersebut.

Kisaran komputasi yang dapat diperlakukan seperti ini sangatlah besar. I/O adalah salah satu contoh di atas. Jenis perhitungan lain yang sering digunakan adalah “Ketidakpastian” dalam arti bahwa suatu nilai mungkin ada atau tidak ada. Misalnya, Anda mungkin mencari kunci di tabel hash yang mungkin ditemukan atau tidak. Jenis komputasi ini dikemas ke dalam monad Option. Cara untuk memikirkan hal ini adalah jika let menemukan ketidakberadaan saat mengekstraksi nilai dari perhitungan (yaitu tabel hash tidak memiliki kunci yang kita cari), keseluruhan let akan menjadi tidak ada. Jika tidak, jika nilainya ada, isi let akan memiliki nilai juga. Di Option, injeksi nilai (η) dilakukan menggunakan Some di Scala atau Just di Haskell. Primitif lainnya (seperti get dari tabel hash, yang dalam hal ini dianalogikan dengan getc) secara otomatis menghasilkan nilai dalam Option.

Jenis komputasi lain yang umum digunakan adalah “Asynchronous.” Dalam hal ini, komputasi terjadi secara asinkron — mungkin di sistem lain (seperti database) — dan komputasi ini akan menghasilkan nilai yang diinginkan. Jenis komputasi ini biasanya dikemas sebagai monad Future. Future mewakili perhitungan yang akan menghasilkan nilai yang pada akhirnya akan kita dapatkan. Pengikatan di let menunggu komputasi menghasilkan nilai ini dan hanya mengevaluasi isi saat nilainya siap. Selain itu, let secara keseluruhan sekarang mewakili perhitungan yang, pada titik tertentu, akan menghasilkan nilai dalam isi let. Sesuai dengan gagasan kami tentang cara kerja let, ekspresi let itu sendiri adalah Future.

Ini adalah cara yang sangat bersih untuk menyusun program yang menyertakan efek. Moggi menggunakannya untuk mendefinisikan semantik efek seperti keadaan yang bisa berubah, kelanjutan, dll., tapi Phil Wadler-lah yang "memperluas" penggunaannya ke pemrograman fungsional. Bersama Simon Peyton Jones dan lainnya, dia memimpin penggabungan mereka ke Haskell. Selanjutnya, mereka telah dimasukkan ke dalam banyak bahasa pemrograman lain, termasuk Scala dan Swift.

T[] spesifik yang kita pilih untuk penghitungan sering kali memiliki operasinya sendiri, sehingga Anda dapat memengaruhi/mengamati penghitungan sebenarnya itu sendiri. Misalnya, Anda dapat menempatkan batas waktu pada Future tanpa harus mengubah bagian program yang hanya berhubungan dengan nilai Future. Atau, berikan opsi pemulihan pada penghitungan (karena Anda tahu ini adalah penghitungan!).

Jadi, ini dia. Monad memiliki konsep yang sangat sederhana. Lalu, mengapa ada kekacauan dan drama di sekitar mereka? Izinkan saya untuk sekarang memetakan (tidak ada permainan kata-kata) ide-ide yang sangat sederhana ini ke dalam beberapa konstruksi konkret dalam bahasa nyata, dan Anda akan melihat mengapa hal itu menjadi kacau.

Konstruksi Moggi yang sangat elegan let … in … dirumuskan ulang dalam Scala (dan Swift) sebagai nama sayangnya for … yield … dan bahkan lebih sayangnya lagi bernama do … return … di Haskell (mereka juga sedikit berbeda dalam semantik). Perhatikan bahwa kedua bahasa memilih untuk menamai operasi mengikat sebagai operasi imperatif, yang merupakan keputusan desain yang menurut saya sangat disesalkan. Siapa pun yang membaca sebuah program dengan kata-kata tersebut di dalamnya akan langsung merasa bingung karena alih-alih membawanya ke tempat yang “mengikat”, program tersebut malah membawanya ke tempat yang “berulang”, atau yang lebih membingungkan lagi, secara imperatif “kembali” dari suatu tempat.

Tentu saja ada sejarah bertahun-tahun di balik mengapa hal ini terjadi, tetapi ada baiknya jika kita melihat lebih dalam.

Dalam “makalah” berikutnya, Wadler memperhatikan dan memanfaatkan fakta bahwa daftar dan monad memiliki sifat aljabar yang serupa, dan kesamaan tersebut dapat dimanfaatkan dengan memperluas beberapa fungsi daftar ke semua monad secara umum. Jadi, misalnya, kita memiliki fungsi daftar map yang mengambil fungsi bertipe (a ->b)dan memetakannya ke List[a] untuk menghasilkan List[b]. Wadler mengamati bahwa kesamaan ini dapat dieksploitasi untuk monad kecuali bahwa alih-alih List[a]dan List[b], Anda memiliki tipe T[a] dan T[b]. Jadi, untuk tipe monad apa pun T, kita dapat mendefinisikan:

map (f: (a->b), m:T[a]) : T[b] = let v = m in η(f v)

Begitu Anda mengambil langkah itu, banyak hal lain yang menyusul. Anda mendapatkan monster seperti flatMap yang bermakna dalam konteks daftar tetapi notasi monad sama sekali tidak berarti. Bagi mereka yang belum tahu apa itu flatMap, ketika kita memetakan suatu fungsi pada sebuah daftar dan hasilnya adalah sebuah daftar, flatMap akan menambahkan semua sub-daftar itu bersama-sama untuk menghasilkan sebuah daftar datar.

Saya tahu apa itu Future dan saya tahu apa itu flatMapitu. Tapi flatMapping dan Future? Hah? Apa sebenarnyaarti itu? Sayangnya, dalam beberapa bahasa (seperti Scala dan Swift), sebenarnya tidak memiliki arti. Ini adalah nama untuk sesuatu yang sebenarnya merupakan bagian dari definisi aslimonads. Ini adalah operator bind, yang mana let dipecah menjadi: let v = Exp_0 dalam Exp_1 diterjemahkan menjadi bind(Exp_0, λv. Exp_1). Ini dilambangkan dengan ‘*’ dalam matematika dan Haskell menyebutnya >>=.

Namun, menyebutnya flatMap adalah tindakan yang salah. Faktanya, salah satu artikel Swift yang saya baca lebih jauh mengatakan bahwa jika Anda dapat mendefinisikan flatMap untuk struktur data, itu adalah monad. Aku bahkan tidak tahu harus berkata apa mengenai hal itu. Ini adalah betapa buruknya kita telah mengacaukan pikiran banyak orang.

Demikian pula, for (yaitu perulangan) pada daftar yang merupakan pemahaman wajar dalam dunia daftar (yang pada akhirnya didasarkan pada pemahaman Himpunan yang umum dalam teori Himpunan) menjadi perulangan yang sama sekali tidak berarti pada monad (misalnya, izinkan saya mengulang Anda dan Option.Hah?).

Yang juga membuat frustasi adalah, tidak semua fungsi daftar mencakup monad. Misalnya, saya bisa melihat seperti apa head dari Future itu. Tapi apa sih tail dari Future itu? Perhitungan yang tersisa setelah perhitungan selesai atau mungkin perhitungan yang sedangsehingga saya dapat menjalankannya kembali? Ya ya ya. Saya tahu bahwa semua aljabar sangat mirip dan dapat dikerjakan secara matematis, namun program dimaksudkan untuk membaca, dan intensionalitasnya penting. Dunia mana pun yang flatMap sama dengan bindadalah dunia yang sangat salah.

Mengapa tidak menggunakan penjilidan let yang simpel dan elegan saja?Apakah sesulit itu? Generasi baru telah berjuang (dan mungkin masih berjuang) dengan pemisahan sederhana antara perhitungan dan nilai karena alat yang dirancang secara berlebihan. Ya, let memang memiliki arti lain di sebagian besar bahasa lain, tetapi masalah tersebut sangat mudah diperbaiki dengan sintaks minor seperti mlet, let[T] (misalnya let[Option] c = … in …), atau sesuatu yang sama bermaknanya. Atau dengan risiko kerumitan yang sedikit lebih besar, tetap gunakan operator bind yang melakukan hal yang sama tanpa sintaksis.

Jadi jika Anda baru mengenal monad dalam bahasa apa pun yang Anda gunakan, temukan padanan dari T[]yang Anda minati, identifikasi komputasi yang diwakilinya dan padanan dari let … in …, dan itulah semua yang Anda perlukan. Segala sesuatu yang lain adalah kebisingan.