Pemrograman Fungsional: ide yang tepat tentang konkurensi dan negara?

Para pendukung FP telah mengklaim bahwa konkurensi itu mudah karena paradigma mereka menghindari keadaan yang bisa berubah. Saya tidak mengerti.

Bayangkan kita sedang membuat penjelajahan bawah tanah multi-pemain (seperti roguelike) menggunakan FP di mana kami menekankan fungsi murni dan struktur data yang tidak dapat diubah. Kami menghasilkan ruang bawah tanah yang terdiri dari kamar, koridor, pahlawan, monster, dan jarahan. Dunia kita secara efektif merupakan objek grafik struktur dan hubungan mereka. Ketika hal-hal berubah, representasi dunia kita diubah untuk mencerminkan perubahan-perubahan itu. Pahlawan kita membunuh seekor tikus, mengambil kata pendek, dll.

Bagi saya dunia (realitas saat ini) membawa gagasan tentang negara ini dan saya kehilangan bagaimana FP mengatasi hal ini. Saat pahlawan kita mengambil tindakan, fungsi mengubah keadaan dunia. Tampaknya setiap keputusan (AI atau manusia) perlu didasarkan pada keadaan dunia seperti saat ini. Di mana kita akan mengizinkan konkurensi? Kita tidak dapat memiliki beberapa proses secara bersamaan mengubah keadaan dunia agar jangan satu proses mendasarkan hasilnya pada beberapa negara kedaluwarsa. Rasanya bagi saya bahwa semua kontrol harus terjadi dalam satu loop kontrol sehingga kami selalu memproses keadaan saat ini yang diwakili oleh grafik objek kami saat ini di dunia.

Jelas ada situasi yang sangat cocok untuk konkurensi (yaitu ketika memproses tugas-tugas yang terisolasi yang menyatakan independen satu sama lain).

Saya gagal melihat bagaimana konkurensi berguna dalam contoh saya dan mungkin itulah masalahnya. Saya mungkin salah mengartikan klaim itu.

Bisakah seseorang lebih baik mewakili klaim ini?

Saya akan mencoba mengisyaratkan jawabannya. Ini bukan jawaban, hanya ilustrasi pengantar. @Jk jawaban menunjuk ke hal yang nyata, ritsleting.

Bayangkan Anda memiliki struktur pohon yang tidak berubah. Anda ingin mengubah satu simpul dengan memasukkan anak. Hasilnya, Anda mendapatkan pohon yang benar-benar baru.

Tetapi sebagian besar pohon baru persis sama dengan pohon tua. Implementasi yang cerdas akan menggunakan kembali sebagian besar fragmen pohon, mengarahkan pointer di sekitar node yang diubah:

Buku Okasaki penuh dengan contoh-contoh seperti ini.

Jadi saya kira Anda dapat secara wajar mengubah bagian kecil dari dunia permainan Anda setiap gerakan (mengambil koin), dan hanya benar-benar mengubah bagian kecil dari struktur data dunia Anda (sel tempat koin itu diambil). Bagian-bagian yang hanya dimiliki oleh negara bagian di masa lalu akan dikumpulkan dalam waktu singkat.

Ini mungkin perlu beberapa pertimbangan dalam merancang struktur dunia game data dengan cara yang tepat. Sayangnya, saya bukan ahli dalam hal ini. Pasti itu harus sesuatu yang lain daripada matriks NxM yang akan digunakan sebagai struktur data yang bisa berubah. Mungkin itu harus terdiri dari potongan-potongan kecil (koridor? Sel individu?) Yang menunjuk satu sama lain, seperti simpul pohon.

Jawaban 9000 adalah setengah dari jawaban, struktur data persisten memungkinkan Anda untuk menggunakan kembali bagian yang tidak berubah.

Anda mungkin sudah berpikir "hei, bagaimana jika saya ingin mengubah akar pohon?" seperti contoh yang diberikan bahwa sekarang berarti mengubah semua node. Di sinilah resleting datang untuk menyelamatkan. Mereka memungkinkan elemen pada fokus diubah di O (1), dan fokus dapat dipindahkan di mana saja dalam struktur.

Poin lain dengan ritsleting adalah bahwa ada Zipper untuk hampir semua jenis data yang Anda inginkan

Program gaya fungsional menciptakan banyak peluang seperti itu untuk menggunakan konkurensi. Setiap kali Anda mengubah atau memfilter atau mengagregasi koleksi, dan semuanya murni atau tidak berubah, ada peluang bagi operasi untuk dipercepat oleh konkurensi.

Sebagai contoh, misalkan Anda melakukan keputusan AI secara independen satu sama lain dan tanpa urutan tertentu. Mereka tidak bergiliran, mereka semua membuat keputusan secara bersamaan dan kemudian dunia maju. Kode mungkin terlihat seperti ini:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

Anda memiliki fungsi untuk menghitung apa yang akan dilakukan monster dengan memberikan negara dunia, dan menerapkannya ke setiap monster sebagai bagian dari komputasi negara dunia berikutnya. Ini adalah hal yang wajar untuk dilakukan dalam bahasa fungsional, dan kompiler bebas untuk melakukan langkah 'terapkan ke setiap monster' secara paralel.

Dalam bahasa imperatif Anda akan lebih cenderung untuk mengulangi setiap monster, menerapkan efeknya pada dunia. Lebih mudah melakukannya dengan cara itu, karena Anda tidak ingin berurusan dengan kloning atau alias rumit. Kompilator tidak dapat melakukan perhitungan monster secara paralel dalam kasus itu, karena keputusan monster awal mempengaruhi keputusan monster selanjutnya.

Mendengarkan beberapa pembicaraan Rich Hickey - yang ini khususnya - meredakan kebingungan saya. Dalam satu ia menunjukkan bahwa tidak apa-apa proses konkuren mungkin tidak memiliki keadaan saat ini. Saya perlu mendengarnya. Apa yang saya mengalami kesulitan mencerna adalah bahwa program akan benar-benar baik-baik saja dengan mendasarkan keputusan pada snapshot dunia yang telah digantikan oleh yang lebih baru. Saya terus bertanya-tanya bagaimana FP bersamaan bisa mengatasi masalah mendasarkan keputusan pada kondisi lama.

Dalam aplikasi perbankan kita tidak akan pernah ingin mendasarkan keputusan pada snapshot negara yang sejak itu digantikan oleh yang lebih baru (terjadi penarikan).

Konkurensi itu mudah karena paradigma FP menghindari keadaan yang bisa berubah adalah klaim teknis yang tidak berusaha mengatakan apa-apa tentang manfaat logis dari mendasarkan keputusan pada keadaan yang berpotensi lama. FP akhirnya memodelkan perubahan negara. Tidak ada jalan keluar dari ini.

Para pendukung FP telah mengklaim bahwa konkurensi itu mudah karena paradigma mereka menghindari keadaan yang bisa berubah. Saya tidak mengerti.

Saya ingin menyinggung tentang pertanyaan umum ini sebagai seseorang yang merupakan orang baru yang fungsional tetapi telah sampai pada bola mata saya dalam efek samping selama bertahun-tahun dan ingin memitigasi mereka, untuk semua jenis alasan, termasuk lebih mudah (atau lebih khusus "lebih aman, kurang konkurensi kesalahan "). Ketika saya melirik rekan-rekan fungsional saya dan apa yang mereka lakukan, rumput tampak sedikit lebih hijau dan berbau lebih baik, setidaknya dalam hal ini.

Algoritma Seri

Yang mengatakan, tentang contoh spesifik Anda, jika masalah Anda bersifat serial dan B tidak dapat dieksekusi sampai A selesai, secara konsep Anda tidak dapat menjalankan A dan B secara paralel apa pun yang terjadi. Anda harus menemukan cara untuk memecahkan ketergantungan urutan seperti dalam jawaban Anda berdasarkan membuat gerakan paralel menggunakan keadaan permainan lama, atau menggunakan struktur data yang memungkinkan bagian-bagiannya dimodifikasi secara independen untuk menghilangkan ketergantungan urutan seperti yang diusulkan dalam jawaban lain , atau semacamnya. Tapi pasti ada bagian dari masalah desain konseptual seperti ini di mana Anda tidak bisa serta merta melakukan multithread semuanya dengan mudah karena semuanya tidak dapat diubah. Beberapa hal hanya akan bersifat serial sampai Anda menemukan cara cerdas untuk memutus ketergantungan pesanan, jika itu mungkin.

Konkurensi Lebih Mudah

Yang mengatakan, ada banyak kasus di mana kami gagal memparalelkan program yang melibatkan efek samping di tempat-tempat yang berpotensi meningkatkan kinerja secara signifikan hanya karena kemungkinan bahwa itu mungkin tidak aman. Salah satu kasus di mana menghilangkan keadaan berubah-ubah (atau lebih khusus, efek samping eksternal) banyak membantu seperti yang saya lihat adalah bahwa itu berubah "mungkin atau mungkin tidak aman-benang" menjadi "pasti aman-benang" .

Untuk membuat pernyataan itu sedikit lebih konkret, pertimbangkan bahwa saya memberi Anda tugas untuk mengimplementasikan fungsi pengurutan dalam C yang menerima komparator dan menggunakannya untuk mengurutkan array elemen. Ini dimaksudkan untuk digeneralisasi tetapi saya akan memberi Anda asumsi mudah bahwa itu akan digunakan terhadap input skala sedemikian (jutaan elemen atau lebih) yang pasti akan bermanfaat untuk selalu menggunakan implementasi multithreaded. Bisakah Anda multithread fungsi sortir Anda?

Masalahnya adalah bahwa Anda tidak bisa karena pembanding Anda menyortir fungsi panggilan mungkinmenyebabkan efek samping kecuali Anda tahu bagaimana penerapannya (atau paling tidak didokumentasikan) untuk semua kasus yang mungkin agak tidak mungkin tanpa menurunkan fungsi. Komparator dapat melakukan sesuatu yang menjijikkan seperti memodifikasi variabel global di dalamnya dengan cara non-atom. 99,9999% pembanding mungkin tidak melakukan ini, tetapi kami masih tidak dapat melakukan multithread fungsi umum ini hanya karena 0,00001% dari kasus yang dapat menyebabkan efek samping. Akibatnya, Anda mungkin harus menawarkan fungsi pengurutan berulir tunggal dan multithreaded dan meneruskan tanggung jawab kepada programmer yang menggunakannya untuk memutuskan mana yang akan digunakan berdasarkan keamanan benang. Dan orang-orang mungkin masih menggunakan versi single-threaded dan kehilangan peluang untuk melakukan multithread karena mereka mungkin juga tidak yakin apakah pembandingnya aman untuk thread,

Ada banyak sekali kekuatan otak yang dapat dilibatkan hanya dalam merasionalisasi keamanan benang tanpa membuang kunci di mana-mana yang dapat hilang jika kita memiliki jaminan keras bahwa fungsi tidak akan menimbulkan efek samping untuk saat ini dan di masa depan. Dan ada ketakutan: ketakutan praktis, karena siapa pun yang harus men-debug kondisi lomba beberapa kali terlalu banyak mungkin akan ragu-ragu untuk melakukan multithreading apa pun yang tidak dapat 110% yakin adalah thread-safe dan akan tetap seperti itu. Bahkan untuk yang paling paranoid (yang saya mungkin paling tidak batas), fungsi murni memberikan rasa lega dan percaya diri bahwa kita dapat dengan aman menyebutnya paralel.

Dan itulah salah satu kasus utama di mana saya melihatnya sangat bermanfaat jika Anda bisa mendapatkan jaminan yang sulit bahwa fungsi-fungsi tersebut aman untuk digunakan dengan bahasa fungsional murni. Yang lain adalah bahwa bahasa fungsional sering mempromosikan pembuatan fungsi yang bebas dari efek samping. Misalnya, mereka mungkin memberi Anda struktur data persisten di mana cukup efisien untuk memasukkan struktur data besar-besaran dan kemudian mengeluarkan yang baru dengan hanya sebagian kecil yang diubah dari aslinya tanpa menyentuh yang asli. Mereka yang bekerja tanpa struktur data seperti itu mungkin ingin memodifikasinya secara langsung dan kehilangan keamanan utas sepanjang jalan.

Efek samping

Yang mengatakan, saya tidak setuju dengan satu bagian dengan segala hormat kepada teman-teman fungsional saya (yang saya pikir sangat keren):

[...] karena paradigma mereka menghindari keadaan yang bisa berubah.

Itu belum tentu kekekalan yang membuat konkurensi begitu praktis seperti yang saya lihat. Ini fungsi yang menghindari efek samping. Jika suatu fungsi input array untuk mengurutkan, menyalinnya, dan kemudian bermutasi salinan untuk mengurutkan isinya dan output salinan, itu masih sama amannya dengan yang bekerja dengan beberapa jenis array yang tidak berubah bahkan jika Anda melewati input yang sama Array untuk itu dari beberapa utas. Jadi saya pikir masih ada tempat untuk tipe yang bisa berubah dalam membuat kode yang sangat ramah-konkurensi, bisa dikatakan, meskipun ada banyak manfaat tambahan untuk tipe yang tidak dapat diubah, termasuk struktur data persisten yang saya gunakan tidak begitu banyak untuk properti yang tidak dapat diubah tetapi untuk menghilangkan biaya karena harus menyalin segala sesuatu untuk membuat fungsi bebas dari efek samping.

Dan sering ada overhead untuk membuat fungsi bebas dari efek samping dalam bentuk pengocokan dan menyalin beberapa data tambahan, mungkin tingkat tipuan ekstra, dan mungkin beberapa GC pada bagian-bagian dari struktur data yang persisten, tetapi saya melihat salah satu teman saya yang memiliki mesin 32-core dan saya pikir pertukaran mungkin layak jika kita bisa lebih percaya diri melakukan lebih banyak hal secara paralel.