Mengapa kita menggunakan struktur data persisten dalam pemrograman fungsional?

Pemrograman fungsional menggunakan struktur data yang persisten dan objek yang tidak dapat diubah. Pertanyaan saya adalah mengapa sangat penting untuk memiliki struktur data di sini? Saya ingin memahami pada level rendah apa yang akan terjadi jika struktur data tidak persisten? Apakah program akan crash lebih sering?

Saat Anda bekerja dengan objek data yang tidak dapat diubah, fungsi memiliki properti yang setiap kali Anda menyebutnya dengan input yang sama, mereka menghasilkan output yang sama. Ini membuatnya lebih mudah untuk membuat konsep perhitungan dan membuatnya benar. Itu juga membuat mereka lebih mudah untuk diuji.

Itu baru permulaan. Karena matematika telah lama bekerja dengan fungsi, ada banyak teknik penalaran yang bisa kita pinjam dari matematika, dan menggunakannya untuk penalaran yang ketat tentang program. Keuntungan paling penting dari sudut pandang saya adalah bahwa sistem tipe untuk program fungsional dikembangkan dengan baik. Jadi, jika Anda membuat kesalahan di suatu tempat, kemungkinannya sangat tinggi bahwa itu akan muncul sebagai jenis ketidakcocokan. Jadi, program fungsional yang diketik cenderung jauh lebih dapat diandalkan daripada program imperatif.

Sebaliknya, ketika Anda bekerja dengan objek data yang dapat berubah, Anda pertama-tama memiliki beban kognitif untuk mengingat dan mengelola berbagai status yang dilalui objek selama perhitungan. Anda harus berhati-hati untuk melakukan hal-hal dalam urutan yang benar, memastikan bahwa semua properti yang Anda butuhkan untuk langkah tertentu puas pada saat itu. Mudah membuat kesalahan, dan sistem tipenya tidak cukup kuat untuk menangkap kesalahan itu.

Matematika tidak pernah bekerja dengan objek data yang bisa berubah. Jadi, tidak ada teknik penalaran yang bisa kita pinjam darinya. Ada banyak teknik kami sendiri yang dikembangkan dalam Ilmu Komputer, terutama Floyd-Hoare Logic . Namun, ini lebih sulit untuk dikuasai daripada teknik matematika standar, sebagian besar siswa tidak bisa mengatasinya, sehingga jarang diajarkan.

Untuk tinjauan singkat tentang bagaimana perbedaan kedua paradigma, Anda dapat berkonsultasi dengan beberapa handout pertama dari catatan kuliah saya tentang Prinsip-Prinsip Bahasa Pemrograman .

Lebih mudah bekerja dengan benar dengan struktur data yang persisten daripada bekerja dengan struktur data yang bisa berubah. Menurut saya, inilah keuntungan utama.

Tentu saja, secara teoritis, apa pun yang kita lakukan dengan struktur data yang persisten dapat juga kita lakukan dengan struktur data yang bisa berubah, dan sebaliknya. Dalam banyak kasus, struktur data yang persisten menimbulkan biaya tambahan, biasanya karena sebagian dari mereka harus disalin. Pertimbangan ini akan membuat struktur data yang persisten jauh kurang menarik 30 tahun yang lalu ketika superkomputer memiliki lebih sedikit memori dibandingkan ponsel Anda. Tetapi saat ini hambatan utama dalam produksi perangkat lunak tampaknya adalah waktu pengembangan dan biaya pemeliharaan. Dengan demikian kami bersedia mengorbankan beberapa efisiensi dalam pelaksanaan untuk efisiensi dalam pembangunan.

Mengapa lebih mudah menggunakan struktur data yang persisten? Karena manusia benar-benar buruk dalam melacak aliasing dan jenis interaksi tak terduga lainnya di antara berbagai bagian program. Mereka secara otomatis berpikir bahwa karena dua hal dipanggil xdan y, maka tidak ada dalam commmon. Lagi pula, perlu upaya untuk mengetahui bahwa "bintang pagi" dan "bintang malam" benar-benar sama. Demikian pula, sangat mudah untuk melupakan bahwa struktur data dapat berubah karena utas lain bekerja dengannya, atau karena kami menyebut metode yang terjadi untuk mengubah struktur data, dll. Banyak dari kekhawatiran ini tidak hadir ketika kami bekerja dengan struktur data persisten.

Struktur data yang persisten juga memiliki keunggulan teknis lainnya. Biasanya lebih mudah untuk mengoptimalkannya. Sebagai contoh, Anda selalu bebas untuk menyalin struktur data yang persisten ke beberapa node lain di cloud Anda jika Anda mau, tidak perlu khawatir sinkronisasi.

Menambah jawaban orang lain, dan memperkuat pendekatan matematika, pemrograman fungsional juga memiliki sinergi yang bagus dengan Aljabar Relasional, dan Koneksi Galois.

Ini sangat berguna di bidang Metode Formal.
Contohnya:

• Bukti formal dalam verifikasi program disederhanakan dengan Extended Static Checking;
• Sejumlah properti dari Relational Algebra berguna dalam penyelesaian SAT, dengan alat-alat seperti Alloy;
• Galois Connections memungkinkan pendekatan perhitungan terhadap spesifikasi perangkat lunak, seperti yang terlihat di blog ini , dengan referensi pada makalah , oleh Shin-Cheng Mu dan José Nuno Oliveira.
• Koneksi Galois (dan Pemrograman Fungsional) dapat digunakan dalam Desain dengan mode Kontrak, karena mereka adalah konsep yang lebih umum daripada Hoare Logic.

Contoh

$\{p\} P \{q\}$$[P] \cdot \phi_p \subseteq \phi_q \cdot [P]$

• $[P]$$P$
• $\phi_p$$\phi_q)$$p$$q$

Pendekatan ini juga memungkinkan perhitungan pra-kondisi dan kondisi pasca-terkuat terlemah , yang berguna dalam sejumlah situasi.

Saya ingin memahami pada level rendah apa yang akan terjadi jika struktur data tidak persisten?

Mari kita lihat generator nomor pseudorandom dengan ruang keadaan besar (seperti " Mersenne twister " dengan status 2450 byte) sebagai struktur data. Kami tidak benar-benar ingin menggunakan angka acak lebih dari sekali, jadi sepertinya ada sedikit alasan untuk menerapkan ini sebagai struktur data persisten yang tidak dapat diubah. Sekarang mari kita bertanya pada diri sendiri apa yang mungkin salah dalam kode berikut:

mt_gen = CreateMersenneTwisterPRNGen(seed)
integral = MonteCarloIntegral_Bulk(mt_gen) + MonteCarloIntegral_Boundary(mt_gen)

Sebagian besar bahasa pemrograman tidak menentukan urutan MonteCarloIntegral_Bulkdan MonteCarloIntegral_Boundaryakan dievaluasi. Jika keduanya mengambil referensi ke mt_gen yang bisa berubah sebagai argumen, hasil perhitungan ini bisa bergantung pada platform. Lebih buruk lagi, mungkin ada platform di mana hasilnya tidak dapat direproduksi sama sekali di antara berbagai proses.

Seseorang dapat mendesain struktur data yang dapat diubah yang efisien untuk mt_gen sedemikian rupa sehingga setiap interleaving dari eksekusi MonteCarloIntegral_Bulkdan MonteCarloIntegral_Boundaryakan memberikan hasil yang "benar", tetapi interleaving yang berbeda pada umumnya akan mengarah pada hasil "benar" yang berbeda. Non-reproduktifitas ini membuat fungsi yang sesuai "tidak murni", dan juga menyebabkan beberapa masalah lainnya.

Non-reproduktifitas dapat dihindari dengan menegakkan urutan eksekusi berurutan tetap. Tetapi dalam hal ini kode dapat diatur sedemikian rupa sehingga hanya satu referensi ke mt_gen tersedia pada waktu tertentu. Dalam bahasa pemrograman fungsional yang diketik, tipe keunikan dapat digunakan untuk menegakkan batasan ini, sehingga memungkinkan pembaruan yang dapat diubah juga dalam konteks bahasa pemrograman fungsional murni. Semua ini mungkin terdengar bagus dan keren, tetapi setidaknya dalam teori simulasi Monte Carlo secara paralel memalukan, dan "solusi" kami baru saja menghancurkan properti ini. Ini bukan hanya masalah teoretis, tetapi masalah praktis yang sangat nyata. Namun, kita harus memodifikasi (fungsi yang ditawarkan oleh) generator nomor pseudorandom kita dan urutan nomor acak yang dihasilkannya, dan tidak ada bahasa pemrograman yang dapat melakukan ini secara otomatis untuk kita. (Tentu saja kita dapat menggunakan pustaka nomor acak pseudorandom berbeda yang sudah menawarkan fungsionalitas yang diperlukan.)

Pada tingkat rendah, struktur data yang dapat berubah dengan mudah menyebabkan tidak dapat direproduksi (dan karenanya tidak murni), jika urutan eksekusi tidak berurutan dan diperbaiki. Strategi imperatif khas untuk menangani masalah ini adalah memiliki fase berurutan dengan urutan eksekusi tetap, di mana struktur data yang bisa berubah berubah, dan fase paralel dengan urutan eksekusi sewenang-wenang, di mana semua struktur data yang dapat dibagikan bersama tetap konstan.

Andrej Bauer mengangkat masalah aliasing untuk struktur data yang bisa berubah. Yang cukup menarik, bahasa imperatif yang berbeda seperti Fortran dan C memiliki asumsi yang berbeda tentang aliasing argumen fungsi yang dibolehkan, dan sebagian besar programmer cukup tidak menyadari bahwa bahasa mereka memiliki model aliasing sama sekali.

Semantik ketidakmampuan dan nilai mungkin sedikit berlebihan. Yang lebih penting adalah bahwa sistem tipe dan kerangka kerja logis (seperti model mesin abstrak, model aliasing, model konkurensi, atau model manajemen memori) bahasa pemrograman Anda menawarkan dukungan yang cukup untuk bekerja "secara aman" dengan data "efisien" struktur. Pengenalan "pindahkan semantik" ke C ++ 11 mungkin terlihat seperti langkah mundur besar dalam hal kemurnian dan "keamanan" dari sudut pandang teoretis, tetapi dalam praktiknya kebalikannya. Sistem tipe dan kerangka logis bahasa telah diperluas untuk menghilangkan bagian besar dari bahaya yang terkait dengan semantik baru. (Dan bahkan jika tepi kasar tetap ada, ini tidak berarti bahwa ini tidak dapat diperbaiki dengan "lebih baik"

Uday Reddy mengangkat masalah bahwa matematika tidak pernah bekerja dengan objek data yang dapat berubah, dan bahwa sistem tipe untuk program fungsional dikembangkan dengan baik untuk objek data yang tidak dapat diubah. Ini mengingatkan saya pada penjelasan Jean-Yves Girard bahwa matematika tidak digunakan untuk bekerja dengan benda-benda yang berubah, ketika dia mencoba untuk memotivasi logika linier.

Orang mungkin bertanya bagaimana memperluas sistem tipe dan kerangka kerja logis dari bahasa pemrograman fungsional untuk memungkinkan bekerja "dengan aman" dengan struktur data non-persisten yang "bisa diubah" yang bisa berubah. Satu masalah di sini mungkin logika klasik dan aljabar boolean mungkin bukan kerangka kerja logis terbaik untuk bekerja dengan struktur data yang bisa berubah. Mungkin logika linier dan monoid komutatif mungkin lebih cocok untuk tugas itu? Mungkin saya harus membaca apa yang dikatakan Philip Wadler tentang logika linier sebagai sistem tipe untuk bahasa pemrograman fungsional? Tetapi bahkan jika logika linier seharusnya tidak dapat menyelesaikan masalah ini, ini tidak berarti bahwa sistem tipe dan kerangka kerja logis dari bahasa pemrograman fungsional tidak dapat diperluas untuk memungkinkan "aman" dan "efisien"