Pada artikel ini saya akan memberi tahu Anda tentang salah satu opsi currying dan aplikasi parsial fungsi di C ++ yang merupakan favorit pribadi saya. Saya juga akan menunjukkan implementasi pilot saya sendiri untuk hal ini dan menjelaskan titik kari tanpa rumus matematika yang rumit, membuatnya sangat sederhana untuk Anda. Kita juga akan melihat apa yang ada di bawah kap perpustakaan kari.hpp yang akan kita gunakan untuk fungsi kari. Bagaimanapun, ada banyak hal yang menarik di dalam, jadi selamat datang!
Kari
Jadi, apa itu kari? Saya kira itu adalah salah satu kata yang Anda dengar dari programmer Haskell sepanjang waktu (setelah monad , tentu saja). Pada dasarnya, definisi istilah ini cukup sederhana, sehingga pembaca yang telah menulis pada bahasa jenis ML atau Haskell , atau yang tahu apa artinya dari tempat lain, merasa bebas untuk melewati bagian ini.
Currying - adalah teknik mengubah fungsi yang mengambil argumen N menjadi satu fungsi, yang mengambil argumen tunggal dan mengembalikan fungsi argumen berikutnya, dan terus berjalan sampai kita mengembalikan fungsi argumen terakhir, yang akan mewakili hasil keseluruhan. Saya pikir ini membantu jika saya menunjukkan kepada Anda contoh:
int sum2(int lhs, int rhs) { return lhs + rhs; }
Di sini kita memiliki fungsi penambahan biner. Dan bagaimana jika kita ingin mengubahnya menjadi fungsi variabel tunggal? Ini sebenarnya sangat sederhana:
auto curried_sum2(int lhs) { return [=](int rhs) { return sum2(lhs, rhs); }; }
Tidak, apa yang kita lakukan? Kami mengambil nilai berdasarkan argumen tunggal yang disebut lambda yang pada gilirannya mengambil argumen kedua dan melakukan penambahan itu sendiri. Sebagai hasilnya, kita dapat menerapkan fungsi curried_sum2 ke argumen kita satu per satu:
Dan itu sebenarnya inti dari operasi kari. Tentu saja, dimungkinkan untuk melakukannya dengan fungsi apa pun - ini akan bekerja dengan cara yang sama. Kami akan mengembalikan fungsi curiga argumen N-1 setiap kali kami mengambil nilai dari argumen lain:
auto sum3(int v1, int v2, int v3) { return v1 + v2 + v3; } auto curried_sum3(int v1) { return [=](int v2){ return [=](int v3){ return sum3(v1, v2, v3); }; }; }
Aplikasi sebagian
Aplikasi parsial - adalah cara memanggil fungsi argumen N ketika mereka hanya mengambil sebagian dari argumen dan mengembalikan fungsi lain dari argumen yang tersisa.
Dalam hal ini perlu dicatat bahwa dalam bahasa seperti Haskell proses ini bekerja secara otomatis, di belakang punggung seorang programmer. Apa yang kami coba lakukan di sini adalah untuk melakukannya secara eksplisit, sum3 untuk memanggil fungsi sum3 kita seperti ini: sum3(38,3)(1) atau mungkin seperti ini: sum3(38)(3,1) . Selain itu, jika satu fungsi mengembalikan fungsi lain yang telah dikerjakan, ia dapat juga dipanggil menggunakan daftar argumen fungsi pertama. Mari kita lihat contohnya:
int boo(int v1, int v2) { return v1 + v2; } auto foo(int v1, int v2) { return kari::curry(boo, v1 + v2); }
Kami sebenarnya memiliki sedikit kemajuan di sini, menunjukkan contoh penggunaan kari.hpp , jadi ya, itu yang terjadi.
Menetapkan tujuan
Sebelum kita menulis sesuatu, penting (atau diinginkan) untuk memahami apa yang ingin kita miliki pada akhirnya. Dan kami ingin memiliki kesempatan untuk menjelajah dan menerapkan sebagian fungsi apa pun yang dapat dipanggil dalam C ++. Yaitu:
- lambdas (termasuk yang generik)
- objek fungsi (functors)
- fungsi dari arity apa pun (termasuk templat)
- fungsi variadik
- metode kelas
Fungsi variadik dapat digulung dengan menentukan jumlah argumen yang ingin kita gulir. Interaksi standar dengan std :: bind dan hasilnya juga diinginkan. Dan tentu saja, kita membutuhkan kesempatan untuk menerapkan fungsi multi-variabel dan memanggil fungsi bersarang sehingga sepertinya kita telah bekerja dengan satu fungsi yang digulung.
Dan kita tidak boleh melupakan kinerja juga. Kita perlu meminimalkan biaya komputasi pembungkus, transfer argumen dan penyimpanannya. Ini berarti kita harus memindahkan alih-alih menyalin, menyimpan hanya apa yang benar-benar kita butuhkan, dan mengembalikan (dengan menghapus lebih lanjut) data secepat mungkin.
Penulis, Anda sudah mencoba untuk menciptakan std::bind satu lagi!
Ya dan tidak. std::bind tidak diragukan lagi adalah alat yang ampuh dan terbukti, dan saya tidak bermaksud untuk menulis pembunuh atau alternatifnya. Ya, itu dapat digunakan untuk aplikasi sebagian currying dan eksplisit (dengan menentukan dengan tepat argumen apa yang kami terapkan, dan di mana, dan berapa banyak). Tapi itu pasti itu bukan pendekatan yang paling nyaman, belum lagi itu tidak selalu berlaku karena kita harus mengetahui arity fungsi dan menulis binding spesifik tergantung pada itu. Sebagai contoh:
int foo(int v1, int v2, int v3, int v4) { return v1 + v2 + v3 + v4; }
API
namespace kari { template < typename F, typename... Args > constexpr decltype(auto) curry(F&& f, Args&&... args) const; template < typename F, typename... Args > constexpr decltype(auto) curryV(F&& f, Args&&... args) const; template < std::size_t N, typename F, typename... Args > constexpr decltype(auto) curryN(F&& f, Args&&... args) const; template < typename F > struct is_curried; template < typename F > constexpr bool is_curried_v = is_curried<F>::value; template < std::size_t N, typename F, typename... Args > struct curry_t { template < typename... As > constexpr decltype(auto) operator()(As&&... as) const; }; }
kari::curry(F&& f, Args&&... args)
Mengembalikan objek fungsi tipe curry_t (fungsi curry_t ) dengan argumen argumen opsional yang diterapkan atau dengan hasil penerapan argumen ke fungsi yang diberikan f (apakah fungsinya adalah nullary, atau argumen yang ditransfer cukup untuk menyebutnya).
Jika parameter f berisi fungsi yang telah dikerjakan, ia mengembalikan salinannya dengan argumen yang diterapkan.
kari::curryV(F&& f, Args&&... args)
Memungkinkan untuk menjelajah fungsi dengan sejumlah variabel argumen. Setelah itu fungsi-fungsi ini dapat dipanggil menggunakan () operator tanpa argumen. Sebagai contoh:
auto c0 = kari::curryV(std::printf, "%d + %d = %d"); auto c1 = c0(37, 5); auto c2 = c1(42); c2();
Jika f parameter berisi fungsi yang telah digulung, ia mengembalikan salinannya dengan jenis aplikasi yang diubah untuk jumlah variabel variabel dengan argumen yang diterapkan args .
kari::curryN(F&& f, Args&&... args)
Memungkinkan untuk menjelajah fungsi dengan jumlah variabel argumen dengan menentukan angka pasti N dari argumen yang ingin kita terapkan (kecuali yang diberikan dalam args ). Sebagai contoh:
char buffer[256] = {'\0'}; auto c = kari::curryN<3>(std::snprintf, buffer, 256, "%d + %d = %d"); c(37, 5, 42); std::cout << buffer << std::endl;
Jika parameter f berisi fungsi yang telah dikerjakan, ia mengembalikan salinannya dengan jenis aplikasi yang diubah untuk argumen N dengan argumen yang digunakan argumen.
kari::is_curried<F>, kari::is_curried_v<F>
Beberapa struktur bantu untuk memeriksa apakah suatu fungsi telah dikerjakan. Sebagai contoh:
const auto l = [](int v1, int v2){ return v1 + v2; }; const auto c = curry(l);
kari::curry_t::operator()(As&&... as)
Operator memungkinkan aplikasi fungsi kari penuh atau sebagian. Mengembalikan fungsi kari argumen tersisa dari fungsi awal F , atau nilai fungsi ini diperoleh dengan penerapannya di tumpukan argumen lama dan argumen baru as . Sebagai contoh:
int foo(int v1, int v2, int v3, int v4) { return v1 + v2 + v3 + v4; } auto c0 = kari::curry(foo); auto c1 = c0(15, 20);
Jika Anda memanggil fungsi curryV tanpa argumen menggunakan curryV atau curryN , itu akan dipanggil jika ada cukup argumen. Jika tidak, itu akan mengembalikan fungsi yang diterapkan sebagian. Sebagai contoh:
auto c0 = kari::curryV(std::printf, "%d + %d = %d"); auto c1 = c0(37, 5); auto c2 = c1(42);
Detail implementasi
Ketika memberi Anda detail implementasi, saya akan menggunakan C ++ 17 untuk menjaga agar teks artikelnya singkat dan menghindari penjelasan yang tidak perlu dan menumpuk SFINAE , serta contoh implementasi yang harus saya tambahkan dalam C ++ 14 standar. Semua ini dapat Anda temukan di repositori proyek, di mana Anda juga dapat menambahkannya ke favorit Anda :)
make_curry(F&& f, std::tuple<Args...>&& args)
Fungsi bantu yang membuat objek fungsi curry_t atau menerapkan fungsi yang diberikan f ke argumen args .
template < std::size_t N, typename F, typename... Args > constexpr auto make_curry(F&& f, std::tuple<Args...>&& args) { if constexpr ( N == 0 && std::is_invocable_v<F, Args...> ) { return std::apply(std::forward<F>(f), std::move(args)); } else { return curry_t< N, std::decay_t<F>, Args... >(std::forward<F>(f), std::move(args)); } } template < std::size_t N, typename F > constexpr decltype(auto) make_curry(F&& f) { return make_curry<N>(std::forward<F>(f), std::make_tuple()); }
Sekarang, ada dua hal menarik tentang fungsi ini:
- kami menerapkannya pada argumen hanya jika itu dapat diaktifkan untuk argumen ini dan aplikasi counter
N adalah nol - jika fungsi tidak dapat dipanggil, kami menganggap panggilan ini sebagai aplikasi parsial dan membuat objek fungsi
curry_t berisi fungsi dan argumen
struct curry_t
Objek fungsi seharusnya menyimpan simpanan argumen dan fungsi yang akan kita panggil saat menerapkannya pada akhirnya. Objek ini adalah apa yang akan kita panggil dan terapkan sebagian.
template < std::size_t N, typename F, typename... Args > struct curry_t { template < typename U > constexpr curry_t(U&& u, std::tuple<Args...>&& args) : f_(std::forward<U>(u)) , args_(std::move(args)) {} private: F f_; std::tuple<Args...> args_; };
Ada sejumlah alasan mengapa kita menyimpan simpanan argumen args_ di std :: tuple :
1) situasi dengan std :: ref ditangani secara otomatis untuk menyimpan referensi ketika kita perlu, secara default berdasarkan nilai
2) aplikasi fungsi yang sesuai dengan argumennya ( std :: apply )
3) readymade, jadi Anda tidak harus menulisnya dari awal :)
Kami telah menyimpan objek yang kami panggil dan fungsi f_ berdasarkan nilainya juga, dan berhati-hati saat memilih jenis ketika membuat satu (saya akan memperluas masalah ini di bawah), atau memindahkan, atau menyalinnya menggunakan referensi universal di konstruktor.
Parameter templat N bertindak sebagai penghitung aplikasi untuk fungsi variadik.
curry_t::operator()(const As&...)
Dan, tentu saja, hal yang membuat semuanya berfungsi - operator yang memanggil objek fungsi.
template < std::size_t N, typename F, typename... Args > struct curry_t {
Operator panggilan memiliki empat fungsi kelebihan beban.
Sebuah fungsi tanpa parameter yang memungkinkan untuk mulai menerapkan fungsi variadic (dibuat oleh curryV atau curryN ). Di sini kita mengurangi penghitung aplikasi menjadi nol, sehingga memperjelas bahwa fungsi tersebut siap untuk diterapkan, dan kemudian kita memberikan semua yang diperlukan untuk fungsi make_curry .
Fungsi argumen tunggal yang mengurangi penghitung aplikasi sebanyak 1 (jika tidak nol) dan menempatkan argumen baru kami di tumpukan argumen args_ dan mentransfer semua ini ke make_curry .
Fungsi variadik yang sebenarnya merupakan trik untuk aplikasi parsial berbagai argumen. Apa yang dilakukannya adalah menerapkannya secara rekursif, satu per satu. Sekarang, ada dua alasan mengapa mereka tidak dapat diterapkan sekaligus:
- penghitung aplikasi dapat turun ke nol sebelum tidak ada argumen yang tersisa
- fungsi
f_ dapat dipanggil lebih awal dan mengembalikan fungsi curried lainnya, sehingga semua argumen selanjutnya akan ditujukan untuk itu
Fungsi terakhir bertindak sebagai jembatan antara memanggil curry_t menggunakan lvalue dan memanggil fungsi menggunakan rvalue .
Tag fungsi ref-kualifikasi membuat seluruh proses hampir ajaib. Singkatnya, dengan bantuan mereka, kami mengetahui bahwa sebuah objek dipanggil menggunakan rvalue reference dan kami hanya bisa memindahkan argumen alih-alih menyalinnya di fungsi memanggil akhir make_curry . Kalau tidak, kita harus menyalin argumen agar masih memiliki kesempatan untuk memanggil fungsi ini lagi, memastikan argumen masih ada.
Bonus
Sebelum melanjutkan ke kesimpulan, saya ingin menunjukkan kepada Anda beberapa contoh gula sintaksis yang mereka miliki di kari.hpp yang dapat dikualifikasikan sebagai bonus.
Bagian operator
Programmer yang sudah bekerja dengan Haskell harus terbiasa dengan bagian operator yang memungkinkan untuk memberikan deskripsi singkat tentang operator yang diterapkan. Misalnya, struktur (*2) , menghasilkan fungsi argumen tunggal, mengembalikan hasil perkalian argumen ini dengan 2. Jadi, yang saya inginkan adalah mencoba menulis sesuatu seperti itu di C ++. Tidak lebih cepat dikatakan daripada dilakukan!
using namespace kari::underscore; std::vector<int> v{1,2,3,4,5}; std::accumulate(v.begin(), v.end(), 0, _+_);
Komposisi fungsi
Dan tentu saja saya tidak akan menjadi gila jika saya belum mencoba menulis komposisi fungsi . Sebagai operator komposisi saya memilih operator * sebagai yang terdekat (dengan melihatnya) dari semua simbol yang tersedia untuk tanda komposisi dalam matematika. Saya menggunakannya untuk menerapkan fungsi yang dihasilkan untuk argumen juga. Jadi, itulah yang saya dapat:
using namespace kari::underscore;
- komposisi fungsi
(*2) dan (+2) diterapkan ke 4 . (4 + 2) * 2 = 12 - fungsi
(*2) diterapkan ke 4 dan kemudian kami menerapkan (+2) untuk hasilnya. (4 * 2 + 2) = 10
Cara yang sama Anda dapat membangun komposisi yang cukup rumit dalam gaya pointfree , tetapi ingatlah hanya programmer Haskell yang akan memahami ini :)
Kesimpulan
Saya pikir sudah cukup jelas sebelumnya bahwa tidak perlu menggunakan teknik ini dalam proyek nyata. Tapi tetap saja, saya harus menyebutkan itu. Lagipula, tujuan saya adalah membuktikan diri dan memeriksa standar C ++ yang baru. Apakah saya dapat melakukan ini? Dan akankah C ++? Ya, saya kira, Anda baru saja melihat bahwa kami berdua telah melakukan itu. Dan saya sangat berterima kasih kepada semua orang yang membaca semuanya.