Pemrograman Fungsional dan Komputasi Ilmiah

Saya minta maaf jika ini pertanyaan yang tidak jelas, tetapi begini:

Selama beberapa tahun terakhir, pemrograman fungsional telah menerima banyak perhatian di komunitas Rekayasa Perangkat Lunak. Banyak yang sudah mulai menggunakan bahasa seperti Scala dan Haskell dan mengklaim sukses atas bahasa pemrograman dan paradigma lain. Pertanyaan saya adalah: sebagai ahli komputasi / komputasi ilmiah berkinerja tinggi, haruskah kita tertarik pada pemrograman fungsional? Haruskah kita berpartisipasi dalam revolusi kecil ini?

Apa pro dan kontra pemrograman fungsional dalam domain kerja SciComp?

Saya hanya melakukan sedikit pemrograman fungsional, jadi ambil jawaban ini dengan sebutir garam.

Pro:

• Pemrograman fungsional terlihat sangat matematis; ini adalah paradigma yang bagus untuk mengekspresikan beberapa konsep matematika
• Ada perpustakaan yang baik tersedia untuk hal-hal seperti verifikasi formal program dan pembuktian teorema, sehingga dimungkinkan untuk menulis program yang beralasan tentang program - aspek ini baik untuk reproduksibilitas
• Anda dapat melakukan pemrograman fungsional dalam Python dan C ++ melalui ekspresi lambda; Anda juga dapat melakukan pemrograman fungsional dalam Julia dan Mathematica
• Tidak banyak orang yang menggunakannya, sehingga Anda bisa menjadi perintis. Sama seperti ada pengadopsi awal MATLAB, Python, R, dan sekarang Julia, harus ada pengadopsi awal pemrograman fungsional agar dapat menangkap

Kekurangan:

• Bahasa yang biasanya dianggap sebagai bahasa pemrograman fungsional, seperti Haskell, OCaml (dan dialek ML lainnya), dan Lisp umumnya dianggap sebagai relatif lambat untuk bahasa yang digunakan untuk komputasi ilmiah yang kritis terhadap kinerja. OCaml, paling banter, sekitar setengah secepat C.
• Bahasa-bahasa ini tidak memiliki infrastruktur perpustakaan dibandingkan dengan bahasa yang biasa digunakan dalam ilmu komputasi (Fortran, C, C ++, Python); jika Anda ingin memecahkan PDE, itu cara yang lebih mudah untuk melakukannya dalam bahasa yang lebih umum digunakan dalam ilmu komputasi daripada yang tidak.
• Tidak banyak komunitas sains komputasi yang menggunakan bahasa pemrograman fungsional seperti halnya menggunakan bahasa prosedural, yang berarti Anda tidak akan mendapatkan banyak bantuan untuk mempelajarinya atau men-debug-nya, dan orang-orang mungkin akan memberi Anda omong kosong untuk menggunakannya (layak atau tidak)
• Gaya pemrograman fungsional berbeda dari gaya yang digunakan dalam pemrograman prosedural, yang biasanya diajarkan di kelas-kelas ilmu komputer pengantar dan di "-tipe MATLAB untuk Ilmuwan dan Insinyur" -type kelas

Saya pikir banyak keberatan di bagian "Kontra" dapat diatasi. Sebagaimana titik diskusi umum pada situs Stack Exchange ini, waktu pengembang lebih penting daripada waktu eksekusi. Bahkan jika bahasa pemrograman fungsional lambat, jika porsi kinerja kritis dapat didelegasikan ke bahasa prosedural yang lebih cepat dan jika peningkatan produktivitas dapat ditunjukkan melalui pengembangan aplikasi yang cepat, maka mereka mungkin layak digunakan. Perlu dicatat di sini bahwa program yang diimplementasikan dalam Python murni, MATLAB murni, dan R murni jauh lebih lambat daripada implementasi program yang sama di C, C ++, atau Fortran. Bahasa seperti Python, MATLAB, dan R populer justru karena mereka memperdagangkan kecepatan eksekusi untuk produktivitas, dan bahkan kemudian, Python dan MATLAB keduanya memiliki fasilitas untuk mengimplementasikan antarmuka ke kode yang dikompilasi dalam C atau C ++ sehingga kode kinerja-kritis dapat diimplementasikan untuk dieksekusi dengan cepat. Sebagian besar bahasa memiliki antarmuka fungsi asing ke C, yang akan cukup untuk berinteraksi dengan sebagian besar perpustakaan yang menarik bagi para ilmuwan komputasi.

Haruskah Anda tertarik pada pemrograman fungsional?

Itu semua tergantung pada apa yang Anda anggap keren. Jika Anda adalah tipe orang yang bersedia untuk menentang konvensi dan Anda bersedia menjalani slog penginjilan kepada orang-orang tentang kebajikan apa pun yang ingin Anda lakukan dengan pemrograman fungsional, saya akan mengatakan untuk itu . Saya akan senang melihat orang melakukan hal-hal keren dengan pemrograman fungsional dalam ilmu komputasi, jika tidak ada alasan lain selain membuktikan semua penentang yang salah (dan akan ada banyak penentang). Jika Anda bukan tipe orang yang ingin berurusan dengan sekelompok orang yang meminta Anda, "Mengapa di neraka Anda menggunakan bahasa pemrograman fungsional bukan (insert bahasa pemrograman favorit mereka prosedural di sini)?", Maka saya takkan' tidak repot.

Ada beberapa penggunaan bahasa pemrograman fungsional untuk pekerjaan intensif simulasi. Perusahaan perdagangan kuantitatif Jane Street menggunakan OCaml untuk pemodelan keuangan dan pelaksanaan strategi perdagangannya. OCaml juga digunakan dalam FFTW untuk menghasilkan beberapa kode C yang digunakan di perpustakaan. Liszt adalah bahasa khusus domain yang dikembangkan di Stanford dan diimplementasikan di Scala yang digunakan untuk memecahkan PDE. Pemrograman fungsional jelas digunakan dalam industri (tidak harus dalam ilmu komputasi); masih harus dilihat apakah akan lepas landas dalam ilmu komputasi.

Saya mungkin memiliki perspektif unik tentang ini karena saya adalah seorang praktisi HPC dengan latar belakang perhitungan ilmiah serta pengguna bahasa pemrograman fungsional. Saya tidak ingin menyamakan HPC dengan perhitungan ilmiah, tetapi ada banyak persimpangan, dan itulah sudut pandang yang saya ambil dalam menjawab ini.

Bahasa fungsional tidak mungkin diadopsi dalam HPC untuk saat ini terutama karena pengguna dan pelanggan HPC benar-benar peduli untuk mencapai kinerja puncak sedekat mungkin. Memang benar bahwa ketika kode ditulis dengan cara fungsional secara alami memperlihatkan paralelisme yang dapat dieksploitasi, tetapi dalam HPC itu tidak cukup. Paralelisme hanyalah satu bagian dari teka-teki dalam mencapai kinerja tinggi, Anda juga harus memperhitungkan berbagai detail mikro-arsitektur dan melakukan ini umumnya memerlukan kontrol yang sangat halus atas pelaksanaan kode, bahwa kontrol tidak tersedia dalam bahasa fungsional yang saya tahu.

Yang mengatakan, saya punya harapan besar ini dapat berubah. Saya telah memperhatikan tren bahwa para peneliti mulai menyadari bahwa banyak dari optimasi mikro-arsitektur ini dapat diotomatisasi (sampai batas tertentu). Ini telah menghasilkan kebun binatang teknologi kompiler sumber-ke-sumber di mana pengguna memasukkan "spesifikasi" dari komputasi yang mereka inginkan, dan kompiler mengeluarkan kode C atau Fortran yang menyadari bahwa perhitungan dengan optimasi dan paralelisme yang diperlukan untuk secara efisien gunakan arsitektur target. Secara kebetulan inilah yang digunakan oleh bahasa fungsional untuk melakukan: memodelkan dan menganalisis bahasa pemrograman. Bukan kebetulan bahwa pengadopsi utama pertama bahasa fungsional adalah pengembang kompiler. Dengan beberapa pengecualian penting saya belum melihat ini benar-benar bertahan, tetapi idenya ada,

Saya ingin menambahkan satu aspek ke dua jawaban lainnya. Selain ekosistem, pemrograman fungsional memberikan peluang besar untuk eksekusi paralel seperti komputasi multithreading atau terdistribusi. Sifat kekekalannya yang melekat membuatnya cocok untuk paralelisme, yang umumnya menyulitkan dalam * bleep * ketika datang ke bahasa imperatif.

Karena peningkatan kinerja perangkat keras dalam beberapa tahun terakhir telah difokuskan pada penambahan core pada prosesor alih-alih mendorong frekuensi yang lebih tinggi, komputasi paralel menjadi jauh lebih populer (saya yakin Anda semua tahu ini).

Hal lain yang disebutkan Geoff adalah waktu pengembang seringkali lebih penting daripada waktu eksekusi. Saya bekerja untuk sebuah perusahaan yang membangun SaaS yang intensif secara komputasi dan kami melakukan tes kinerja awal ketika memulai, mengadu C ++ vs Java. Kami menemukan bahwa C ++ memberikan sekitar 50% pengurangan waktu eksekusi di atas Jawa (ini untuk geometri komputasi dan angka-angka kemungkinan besar akan bervariasi tergantung pada aplikasi), tetapi kami tetap menggunakan Java karena pentingnya waktu pengembang dan berharap bahwa optimisasi dan peningkatan kinerja perangkat keras di masa depan akan membantu kami membuatnya di pasar. Saya dapat mengatakan dengan keyakinan bahwa jika kami memilih sebaliknya, kami tidak akan tetap berbisnis.

Ok, tapi Java bukan bahasa pemrograman fungsional, jadi apa hubungannya dengan apa pun, Anda mungkin bertanya. Nah, nanti ketika kami menggunakan lebih banyak pendukung paradigma fungsional dan tersandung pada perlunya kelumpuhan, kami semakin memindahkan bagian-bagian dari sistem kami ke Scala, yang menggabungkan aspek-aspek positif dari pemrograman fungsional dengan kekuatan imperatif dan bergabung dengan baik dengan Jawa. Ini sangat membantu kami ketika meningkatkan kinerja sistem kami dengan sakit kepala minimal dan mungkin akan terus menuai manfaat dari peningkatan kinerja lebih lanjut dalam bisnis perangkat keras ketika lebih banyak core dijejalkan ke dalam prosesor masa depan.

Perhatikan bahwa saya sepenuhnya setuju dengan kontra yang disebutkan dalam jawaban lain, tetapi saya berpikir bahwa fasilitasi eksekusi paralel adalah pro yang begitu kuat sehingga tidak bisa disebutkan.

Geoff telah memberikan tinjauan yang baik tentang alasan yang saya tambahkan sedikit selain menekankan salah satu poinnya: ekosistem. Apakah Anda menganjurkan pemrograman fungsional atau paradigma lain, salah satu pertanyaan penting yang harus Anda atasi adalah bahwa ada sejumlah besar perangkat lunak yang dapat dibangun oleh orang lain sehingga Anda harus menulis ulang. Contohnya adalah MPI, PETSc atau Trilinos untuk aljabar linier, atau salah satu pustaka elemen hingga - semua ditulis dalam C atau C ++. Ada banyak inersia dalam sistem, mungkin bukan karena semua orang berpikir bahwa C / C ++ sebenarnya adalah bahasa terbaik untuk menulis perangkat lunak komputasi, tetapi karena banyak orang telah menghabiskan bertahun-tahun dalam hidup mereka menciptakan sesuatu yang berguna untuk banyak orang.

Saya pikir sebagian besar orang komputasi akan setuju bahwa ada banyak nilai dalam mencoba bahasa pemrograman baru dan mengevaluasi kesesuaian mereka untuk masalah ini. Tetapi ini akan menjadi waktu yang sulit dan sepi karena Anda tidak akan dapat menghasilkan hasil yang bersaing dengan apa yang dilakukan orang lain. Ini juga dapat memberi Anda reputasi sebagai seseorang yang memulai langkah berikutnya ke paradigma pemrograman yang berbeda. Hei, hanya butuh C ++ sekitar 15 tahun untuk mengganti Fortran!

Ringkasan singkatnya adalah itu

1. Komputasi numerik menggunakan mutabilitas / efek samping untuk mencapai sebagian besar percepatan dan mengurangi alokasi (banyak struktur pemrograman fungsional memiliki data yang tidak dapat diubah)
2. Evaluasi malas bisa kasar untuk digunakan dengan kode numerik.
3. Entah Anda sedang mengembangkan sebuah paket di mana turun ke tingkat terendah untuk kinerja benar-benar penting (C / Fortran atau sekarang Julia) (dalam ini Anda juga dapat mengedit kode assembler seperlunya), atau Anda menulis skrip yang menggunakan pustaka cepat ini jadi Anda cenderung peduli dengan waktu pengembangan (dan Anda memilih Julia / MATLAB / Python / R). Bahasa fungsional cenderung duduk di jalan tengah yang aneh yang membantu dalam disiplin ilmu lain, tetapi tidak membantu di sini.
4. $x_n$$x_{n+1}$

Fakta-fakta ini bersama-sama membuat pemrograman fungsional tampaknya tidak perlu bagi sebagian besar pengguna.

Saya pikir menarik untuk dicatat bahwa penggunaan pemrograman fungsional dalam Ilmu Komputasi bukanlah hal baru. Sebagai contoh, makalah ini dari tahun 1990 menunjukkan bagaimana meningkatkan kinerja program numerik yang ditulis dalam Lisp (mungkin bahasa pemrograman fungsional paling awal) menggunakan evaluasi parsial. Karya ini adalah bagian dari rantai alat yang digunakan dalam makalah tahun 1992 oleh GJ Sussman (dari ketenaran SICP ) dan J Wisdom yang memberikan bukti numerik tentang perilaku kacau Tata Surya . Rincian lebih lanjut tentang perangkat keras dan perangkat lunak yang terlibat dalam perhitungan itu dapat ditemukan di sini .

R adalah bahasa fungsional & juga bahasa statistik (& sekarang pembelajaran Mesin) dan sebenarnya bahasa nomor 1 untuk statistik. Ini bukan bahasa HPC: itu tidak digunakan untuk tradisional "angka-angka" seperti simulasi fisika dll. Tetapi dapat dibuat untuk berjalan pada kelompok besar (misalnya melalui MPI) untuk simulasi statistik besar-besaran (MCMC) pembelajaran mesin.

Mathematica juga merupakan bahasa fungsional tetapi domain intinya adalah komputasi simbolik daripada komputasi numerik.

Di Julia Anda juga dapat memprogram dalam gaya fungsional (di sebelah prosedural & rasa OO (multi-dispatch)) tetapi tidak murni (struktur data dasar semua bisa berubah (kecuali untuk tupel), meskipun ada beberapa perpustakaan dengan kekal struktur data fungsional.Yang lebih penting, ini jauh lebih lambat daripada gaya prosedural sehingga tidak banyak digunakan.

Saya tidak akan menyebut Scala bahasa fungsional melainkan hibrida objek-fungsional. Anda dapat menggunakan banyak konsep fungsional dalam Scala. Scala penting untuk komputasi Cloud karena Spark ( https://spark.apache.org/ ).

Perhatikan bahwa Fortran modern sebenarnya memiliki beberapa elemen pemrograman fungsional: ia memiliki semantik pointer yang ketat (tidak seperti C), Anda dapat memiliki fungsi murni (tanpa efek samping) (& tandai seperti itu) dan Anda dapat memiliki imutabilitas. Bahkan memiliki pengindeksan cerdas di mana Anda dapat menentukan kondisi untuk indeks matriks. Ini adalah permintaan seperti dan biasanya hanya ditemukan dalam bahasa tingkat tinggi seperti R dari LINQ di C # atau melalui fungsi filter urutan yang lebih tinggi dalam bahasa fungsional. Jadi Fortran tidak terlalu buruk sama sekali, bahkan memiliki beberapa fitur yang cukup modern (misalnya co-array) tidak ditemukan dalam banyak bahasa. Bahkan dalam versi Fortran masa depan saya lebih suka melihat lebih banyak fitur fungsional ditambahkan daripada fitur-OO (yang sekarang biasanya terjadi) karena OO di Fortran benar-benar canggung dan jelek.

Kelebihan adalah "alat" yang dibangun dalam setiap bahasa fungsional: Sangat mudah untuk menyaring data, sangat mudah untuk beralih pada data dan jauh lebih mudah untuk menghasilkan solusi yang jelas dan ringkas untuk masalah Anda.

Satu-satunya yang Con adalah, bahwa Anda harus memikirkan jenis pemikiran baru ini: Mungkin perlu waktu untuk mempelajari apa yang harus Anda ketahui. Orang lain dalam domain SciComp tidak benar-benar menggunakan bahasa itu, yang berarti Anda tidak bisa mendapatkan banyak dukungan :(

Jika Anda tertarik pada bahasa fungsional-ilmiah, saya mengembangkannya https://ac1235.github.io

Berikut adalah argumen saya mengapa pemrograman fungsional dapat , dan harus digunakan untuk ilmu komputasi. Manfaatnya sangat besar, dan kontra dengan cepat hilang. Dalam pikiranku hanya ada satu con:

Con : kurangnya dukungan bahasa di C / C ++ / Fortran

Setidaknya dalam C ++, con ini menghilang - karena C ++ 14/17 telah menambahkan fasilitas yang kuat untuk mendukung pemrograman fungsional. Anda mungkin harus menulis sendiri kode pustaka / dukungan, tetapi bahasanya adalah teman Anda. Sebagai contoh, berikut adalah pustaka (peringatan: plug) yang melakukan larik multi-dimensi yang tidak dapat diubah di C ++: https://github.com/jzrake/ndarray-v2 .

Juga, di sini ada tautan ke buku bagus tentang pemrograman fungsional dalam C ++, meskipun tidak berfokus pada aplikasi sains.

Berikut ini ringkasan saya tentang apa yang saya yakini sebagai pro:

Pro :

• Kebenaran
• Dapat dimengerti
• Performa

Dalam hal kebenaran , program fungsional secara nyata berpose : mereka memaksa Anda untuk mendefinisikan dengan benar keadaan minimum variabel fisika Anda, dan fungsi yang memajukan status itu ke depan dalam waktu:

int main()
{
    auto state = initial_condition();

    while (should_continue(state))
    {
        state = advance(state);
        side_effects(state);
    }
    return 0;
}

Memecahkan persamaan diferensial parsial (atau ODE) sangat cocok untuk pemrograman fungsional; Anda hanya menerapkan fungsi murni ( advance) ke solusi saat ini untuk menghasilkan yang berikutnya.

Dalam pengalaman saya, perangkat lunak simulasi fisika pada umumnya dibebani oleh manajemen negara yang buruk . Biasanya, setiap tahapan algoritma beroperasi pada beberapa bagian dari keadaan bersama (efektif global). Ini menyulitkan, atau bahkan tidak mungkin, untuk memastikan urutan operasi yang benar, membuat perangkat lunak rentan terhadap bug yang dapat bermanifestasi sebagai kesalahan-kesalahan, atau lebih buruk lagi, istilah kesalahan yang tidak merusak kode Anda, tetapi secara diam-diam membahayakan integritas ilmu pengetahuannya. keluaran. Mencoba untuk mengelola keadaan bersama dalam simulasi fisika juga menghambat multi-threading - yang merupakan masalah untuk masa depan, karena superkomputer bergerak ke arah jumlah inti yang lebih tinggi, dan penskalaan dengan MPI sering kali lebih baik pada ~ 100 ribu tugas. Sebaliknya, pemrograman fungsional membuat paralelisme memori bersama menjadi sepele, karena kekekalan.

Kinerja juga ditingkatkan dalam pemrograman fungsional karena evaluasi algoritma yang malas (dalam C ++, ini berarti menghasilkan banyak jenis pada waktu kompilasi - seringkali satu untuk setiap aplikasi fungsi). Tapi itu mengurangi overhead dari akses dan alokasi memori, serta menghilangkan pengiriman virtual - memungkinkan kompiler untuk mengoptimalkan seluruh algoritma dengan melihat sekaligus semua objek fungsi yang menyusunnya. Dalam praktiknya, Anda akan bereksperimen dengan pengaturan titik evaluasi yang berbeda (di mana hasil algoritma di-cache ke buffer memori) untuk mengoptimalkan penggunaan alokasi CPU vs memori. Ini agak mudah karena lokalitas yang tinggi (lihat contoh di bawah) dari tahapan algoritma dibandingkan dengan apa yang biasanya akan Anda lihat dalam modul atau kode berbasis kelas.

Program fungsional lebih mudah dipahami sejauh mereka meremehkan keadaan fisika. Bukan berarti sintaks mereka mudah dimengerti oleh semua kolega Anda! Penulis harus berhati-hati untuk menggunakan fungsi-fungsi yang disebutkan dengan baik, dan para peneliti pada umumnya harus terbiasa melihat algoritma yang diungkapkan secara fungsional daripada secara prosedural. Saya akui bahwa tidak adanya struktur kontrol dapat membuat tidak nyaman bagi beberapa orang, tetapi saya tidak berpikir itu akan menghentikan kita untuk pergi ke masa depan yang dapat melakukan sains dengan kualitas yang lebih baik di komputer.

Di bawah ini adalah advancefungsi sampel , diadaptasi dari kode volume hingga menggunakan ndarray-v2paket. Perhatikan to_sharedoperator - ini adalah poin evaluasi yang saya singgung sebelumnya.

auto advance(const solution_state_t& state)
{
    auto dt = determine_time_step_size(state);
    auto du = state.u
    | divide(state.vertices | volume_from_vertices)
    | nd::map(recover_primitive)
    | extrapolate_boundary_on_axis(0)
    | nd::to_shared()
    | compute_intercell_flux(0)
    | nd::to_shared()
    | nd::difference_on_axis(0)
    | nd::multiply(-dt * mara::make_area(1.0));

    return solution_state_t {
        state.time + dt,
        state.iteration + 1,
        state.vertices,
        state.u + du | nd::to_shared() };
}