Apa perbedaan antara konsep dan batasan template?

96

Saya ingin tahu apa perbedaan semantik antara proposal konsep lengkap C ++ dan batasan template (misalnya, batasan seperti yang muncul di Dlang atau proposal konsep-lite baru untuk C ++ 1 tahun ).

Apa yang mampu dilakukan oleh konsep lengkap daripada yang tidak dapat dilakukan oleh batasan template?

Rayniery
sumber
2
Proposal kendala masuk ke ini.
chris
Saya teringat 4.8 Merancang Konsep , tetapi sebenarnya tidak banyak yang tercantum dalam cara bagaimana konsep lebih jauh membatasi. Jika ada, konsep Googling sekarang mungkin mengungkapkan beberapa perbedaan yang mudah terlihat setelah mendapatkan pemahaman yang lebih baik tentang batasan dari proposal.
chris
Konsep IMHO meningkatkan keterbacaan dan memberikan kemampuan program yang lebih jelas seperti yang diminta sejak lama oleh orang-orang seperti Alexander Stepanov dalam 'Elements of Programming'. Proposal ringan hanyalah langkah ke arah ini untuk meringankan beban kendala jenis enable_if aneh yang diperlukan saat ini. Lebih cepat lebih baik untuk pemrograman generik.
dirvine

Jawaban:

136

Informasi berikut sudah ketinggalan zaman. Ini perlu diperbarui sesuai dengan draf Konsep Lite terbaru.

Bagian 3 dari proposal kendala mencakup ini secara mendalam.

Proposal konsep telah diletakkan di belakang pembakar untuk sementara waktu dengan harapan bahwa kendala (yaitu konsep-lite) dapat menyempurnakan dan diterapkan dalam skala waktu yang lebih singkat, saat ini bertujuan untuk setidaknya sesuatu dalam C ++ 14. Proposal kendala dirancang untuk bertindak sebagai transisi yang mulus ke definisi konsep selanjutnya. Batasan adalah bagian dari proposal konsep dan merupakan blok bangunan yang diperlukan dalam definisinya.

Di Design of Concept Libraries untuk C ++ , Sutton dan Stroustrup mempertimbangkan hubungan berikut:

Konsep = Batasan + Aksioma

Untuk meringkas artinya dengan cepat:

  1. Constraint - Predikat atas properti suatu tipe yang dapat dievaluasi secara statis. Persyaratan sintaksis murni. Bukan abstraksi domain.
  2. Aksioma - Persyaratan semantik dari jenis yang dianggap benar. Tidak diperiksa secara statis.
  3. Konsep - Persyaratan umum dan abstrak dari algoritme pada argumennya. Didefinisikan dalam batasan dan aksioma.

Jadi jika Anda menambahkan aksioma (properti semantik) ke batasan (properti sintaksis), Anda mendapatkan konsep.


Konsep-Lite

Proposal konsep-ringan hanya memberi kita bagian pertama, kendala, tetapi ini adalah langkah penting dan perlu menuju konsep yang lengkap.

Kendala

Batasan adalah tentang sintaks . Mereka memberi kita cara membedakan properti suatu tipe secara statis pada waktu kompilasi, sehingga kita dapat membatasi tipe yang digunakan sebagai argumen template berdasarkan properti sintaksisnya. Dalam proposal kendala saat ini, mereka diekspresikan dengan subset dari kalkulus proposisional menggunakan penghubung logis seperti &&dan ||.

Mari kita lihat kendala dalam tindakan:

template <typename Cont>
  requires Sortable<Cont>()
void sort(Cont& container);

Di sini kita mendefinisikan template fungsi yang disebut sort. Penambahan baru adalah klausa yang dibutuhkan . Klausa require memberikan beberapa batasan pada argumen template untuk fungsi ini. Secara khusus, batasan ini mengatakan bahwa tipe Contharus berupa Sortabletipe. Hal yang rapi adalah dapat ditulis dalam bentuk yang lebih ringkas seperti:

template <Sortable Cont>
void sort(Cont& container);

Sekarang jika Anda mencoba meneruskan apa pun yang tidak dianggap Sortableuntuk fungsi ini, Anda akan mendapatkan kesalahan bagus yang segera memberi tahu Anda bahwa tipe yang disimpulkan untuk Tbukanlah Sortabletipe. Jika Anda telah melakukan ini di C ++ 11, Anda akan memiliki beberapa kesalahan yang mengerikan terlempar dari dalam yang sortfungsi yang tidak masuk akal untuk siapa pun.

Predikat kendala sangat mirip dengan sifat tipe. Mereka mengambil beberapa tipe argumen template dan memberi Anda beberapa informasi tentangnya. Constraints mencoba menjawab jenis pertanyaan berikut tentang type:

  1. Apakah tipe ini memiliki operator ini dan itu kelebihan beban?
  2. Apakah tipe ini dapat digunakan sebagai operan untuk operator ini?
  3. Apakah tipe ini memiliki sifat ini dan itu?
  4. Apakah ekspresi konstan ini sama dengan itu? (untuk argumen template non-tipe)
  5. Apakah tipe ini memiliki fungsi yang disebut yada-yada yang mengembalikan tipe tersebut?
  6. Apakah tipe ini memenuhi semua persyaratan sintaksis untuk digunakan seperti itu?

Namun, kendala tidak dimaksudkan untuk menggantikan sifat tipe. Sebaliknya, mereka akan bekerja sama. Beberapa sifat tipe sekarang dapat didefinisikan dalam istilah konsep dan beberapa konsep dalam istilah sifat tipe.

Contoh

Jadi yang penting tentang kendala adalah mereka tidak peduli tentang semantik sedikit pun. Beberapa contoh kendala yang baik adalah:

  • Equality_comparable<T>: Memeriksa apakah tipe memiliki ==kedua operan dari tipe yang sama.

  • Equality_comparable<T,U>: Memeriksa apakah ada ==operan dengan kiri dan kanan dari tipe yang diberikan

  • Arithmetic<T>: Memeriksa apakah tipenya adalah tipe aritmatika.

  • Floating_point<T>: Memeriksa apakah tipenya adalah tipe floating point.

  • Input_iterator<T>: Memeriksa apakah tipe mendukung operasi sintaksis yang harus didukung oleh iterator masukan.

  • Same<T,U>: Memeriksa apakah tipe yang diberikan sama.

Anda dapat mencoba semua ini dengan GCC konsep-lite khusus .


Beyond Concepts-Lite

Sekarang kita membahas segala hal di luar proposal konsep-ringan. Ini bahkan lebih futuristik dari masa depan itu sendiri. Segala sesuatu mulai saat ini tampaknya akan sedikit berubah.

Aksioma

Aksioma adalah tentang semantik . Mereka menentukan hubungan, invarian, jaminan kompleksitas, dan hal-hal lain semacam itu. Mari kita lihat contohnya.

Sementara Equality_comparable<T,U>batasan akan memberi tahu Anda bahwa ada operator== yang mengambil tipe Tdan U, itu tidak memberi tahu Anda apa arti operasi itu . Untuk itu, kita akan punya aksioma Equivalence_relation. Aksioma ini mengatakan bahwa ketika objek dari dua tipe ini dibandingkan dengan operator==pemberian true, objek-objek ini adalah setara. Ini mungkin tampak mubazir, tetapi sebenarnya tidak. Anda dapat dengan mudah mendefinisikan operator==bahwa sebagai gantinya berperilaku seperti file operator<. Anda akan jahat melakukan itu, tetapi Anda bisa.

Contoh lainnya adalah Greateraksioma. Baik dan bagus untuk mengatakan dua objek dengan tipe Tdapat dibandingkan dengan operator >dan <, tetapi apa artinya ? The Greateraksioma mengatakan bahwa jika dan hanya jika xlebih besar maka y, maka ykurang dari x. Spesifikasi yang diusulkan aksioma seperti itu terlihat seperti:

template<typename T>
axiom Greater(T x, T y) {
  (x>y) == (y<x);
}

Jadi aksioma menjawab jenis pertanyaan berikut:

  1. Apakah kedua operator ini memiliki hubungan ini satu sama lain?
  2. Apakah operator untuk tipe ini dan itu berarti demikian?
  3. Apakah operasi pada tipe itu memiliki kerumitan ini?
  4. Apakah hasil dari operator tersebut menyiratkan bahwa ini benar?

Artinya, mereka sepenuhnya peduli dengan semantik jenis dan operasi pada jenis tersebut. Hal-hal ini tidak dapat diperiksa secara statis. Jika ini perlu dicentang, suatu jenis harus dengan cara tertentu menyatakan bahwa ia mematuhi semantik ini.

Contoh

Berikut beberapa contoh umum aksioma:

  • Equivalence_relation: Jika dua objek dibandingkan ==, keduanya setara.

  • Greater: Kapanpun x > y, lalu y < x.

  • Less_equal: Kapanpun x <= y, lalu !(y < x).

  • Copy_equality: Untuk xdan ybertipe T: if x == y, sebuah objek baru dengan tipe yang sama dibuat dengan konstruksi salinan T{x} == ydan masih x == y(yaitu, tidak merusak).

Konsep

Sekarang konsep sangat mudah untuk didefinisikan; mereka hanyalah kombinasi dari kendala dan aksioma . Mereka menyediakan persyaratan abstrak atas sintaks dan semantik suatu tipe.

Sebagai contoh, pertimbangkan Orderedkonsep berikut :

concept Ordered<Regular T> {
  requires constraint Less<T>;
  requires axiom Strict_total_order<less<T>, T>;
  requires axiom Greater<T>;
  requires axiom Less_equal<T>;
  requires axiom Greater_equal<T>;
}

Pertama perhatikan bahwa untuk tipe template yang Takan Ordered, itu juga harus memenuhi persyaratan Regularkonsep. The Regularkonsep adalah persyaratan yang sangat dasar yang jenisnya adalah berkelakuan baik - itu dapat dibangun, dihancurkan, disalin dan dibandingkan.

Selain persyaratan tersebut, persyaratan Orderedyang Tmemenuhi satu kendala dan empat aksioma:

  • Batasan: OrderedJenis harus memiliki operator<. Ini dicentang secara statis sehingga harus ada.
  • Aksioma: Untuk xdan ydari tipe T:
    • x < y memberikan pemesanan total yang ketat.
    • Kapan xlebih besar dari y, ylebih kecil dari x, dan sebaliknya.
    • Bila xkurang dari atau sama dengan y, ytidak kurang dari x, dan sebaliknya.
    • Kapan xlebih besar dari atau sama dengan y, ytidak lebih besar dari x, dan sebaliknya.

Menggabungkan kendala dan aksioma seperti ini memberi Anda konsep. Mereka mendefinisikan persyaratan sintaksis dan semantik untuk tipe abstrak untuk digunakan dengan algoritma. Algoritma saat ini harus mengasumsikan bahwa tipe yang digunakan akan mendukung operasi tertentu dan mengekspresikan semantik tertentu. Dengan konsep, kami dapat memastikan bahwa persyaratan terpenuhi.

Dalam desain konsep terbaru , kompilator hanya akan memeriksa bahwa persyaratan sintaksis suatu konsep dipenuhi oleh argumen template. Aksioma dibiarkan tidak dicentang. Karena aksioma menunjukkan semantik yang tidak dapat dievaluasi secara statis (atau seringkali tidak mungkin untuk diperiksa seluruhnya), penulis tipe harus secara eksplisit menyatakan bahwa tipenya memenuhi semua persyaratan konsep. Ini dikenal sebagai pemetaan konsep dalam desain sebelumnya, tetapi sejak itu telah dihapus.

Contoh

Berikut beberapa contoh konsep:

  • Regular jenis dapat dibangun, dirusak, dapat disalin, dan dapat dibandingkan.

  • Orderedjenis dukungan operator<, dan memiliki total pemesanan yang ketat dan semantik pemesanan lainnya.

  • Copyabletipe adalah salinan yang dapat dibangun, dapat dirusak, dan jika xsama dengan ydan xdisalin, salinan juga akan dibandingkan dengan y.

  • Iteratorjenis jenis harus terkait value_type, reference, difference_type, dan iterator_categoryyang sendiri harus memenuhi konsep-konsep tertentu. Mereka juga harus mendukung operator++dan dapat dibedakan.

Jalan Menuju Konsep

Batasan adalah langkah pertama menuju fitur konsep lengkap C ++. Mereka adalah langkah yang sangat penting, karena menyediakan persyaratan tipe yang dapat diberlakukan secara statis sehingga kita dapat menulis fungsi dan kelas templat yang jauh lebih bersih. Sekarang kita dapat menghindari beberapa kesulitan dan keburukan std::enable_ifdan teman metaprogramming nya.

Namun, ada beberapa hal yang tidak dilakukan oleh proposal kendala:

  1. Ini tidak memberikan bahasa definisi konsep.

  2. Batasan bukanlah peta konsep. Pengguna tidak perlu secara khusus menjelaskan tipenya karena memenuhi batasan tertentu. Mereka secara statis diperiksa menggunakan fitur bahasa waktu kompilasi sederhana.

  3. Implementasi template tidak dibatasi oleh batasan pada argumen template mereka. Artinya, jika template fungsi Anda melakukan sesuatu dengan objek berjenis terbatas yang seharusnya tidak dilakukan, compiler tidak memiliki cara untuk mendiagnosisnya. Proposal konsep berfitur lengkap akan dapat melakukan ini.

Proposal kendala telah dirancang secara khusus sehingga proposal konsep lengkap dapat diperkenalkan di atasnya. Dengan sedikit keberuntungan, transisi itu seharusnya menjadi perjalanan yang cukup mulus. Kelompok konsep mencari untuk memperkenalkan batasan untuk C ++ 14 (atau dalam laporan teknis segera setelahnya), sementara konsep lengkap mungkin mulai muncul sekitar C ++ 17.

sftrabbit
sumber
5
Perlu dicatat bahwa concept-lite tidak memeriksa batasan terhadap implementasi template itu sendiri. Jadi Anda dapat mengklaim bahwa DefaultConstructable apa pun dapat digunakan, tetapi compiler tidak akan menghentikan Anda menggunakan copy konstruktor secara tidak sengaja. Proposal konsep yang lebih lengkap akan.
Nicol Bolas
24
Itu adalah konsep pertama ?!
Nicol Bolas
2
@sftrabbit, jawaban yang sangat bagus. Tapi saya punya pertanyaan: bagaimana kompilator akan memeriksa bahwa suatu tipe memenuhi persyaratan semantik sebuah konsep?
Rayniery
1
Akankah (dengan banyak ketidakpastian) 'aksioma' diperiksa selama run-time, atau mereka hanya akan berfungsi sebagai semacam tag janji?
Merah XIII
4
@ScarletAmaranth: Karena intinya adalah secara otomatis membuktikan teorema dalam waktu terbatas. Ada dua kendala untuk ini: 1. Membuktikan teorema apapun dalam waktu terbatas yang sangat sulit dalam teori, dan tidak mungkin dengan teknologi saat ini. 2. Anda tidak dapat membuktikan sebuah aksioma, kecuali jika bukti tersebut didasarkan pada aksioma lain. (Dalam hal ini secara matematis menjadi "bukan aksioma") Aksioma ini dimaksudkan untuk memberi tahu penyusun "Tentu saja Anda dapat membalikkan perbandingan jika Anda anggap berguna ...", atau "Ya, EmptySet yang digunakan di persimpangan selalu memberikan hasil yang sama. "
Laurent LA RIZZA
4

2 sen saya:

  1. Proposal concept-lite tidak dimaksudkan untuk melakukan "pemeriksaan jenis" penerapan template . Yaitu, Concepts-lite akan memastikan (secara nosional) kompatibilitas antarmuka di situs instantiation template. Mengutip dari makalah: "concept lite adalah perpanjangan dari C ++ yang memungkinkan penggunaan predikat untuk membatasi argumen template". Dan itu dia. Itu tidak mengatakan bahwa tubuh template akan diperiksa (secara terpisah) terhadap predikat. Itu mungkin berarti tidak ada gagasan kelas satu tentang arketipe ketika Anda berbicara tentang konsep-ringan. archtypes, jika saya ingat dengan benar, dalam concept-heavy proposal adalah tipe yang menawarkan tidak kurang dan tidak lebih untuk memuaskan implementasi template.

  2. concept-lite menggunakan fungsi-fungsi constexpr yang dimuliakan dengan sedikit trik sintaks yang didukung oleh compiler. Tidak ada perubahan dalam aturan pencarian.

  3. Pemrogram tidak diharuskan untuk menulis peta konsep.

  4. Terakhir, mengutip lagi "Proposal kendala tidak secara langsung membahas spesifikasi atau penggunaan semantik; itu ditargetkan hanya untuk memeriksa sintaks." Itu berarti aksioma tidak berada dalam ruang lingkup (sejauh ini).

Sumant
sumber