Bagaimana cara memverifikasi / membuktikan ortogonalitas suatu bahasa pemrograman?

Saya tahu konsep ortogonalitas, tetapi dari sudut pandang bahasa pemrograman, apakah ada cara untuk memverifikasi / membuktikannya?

Misalnya dalam C #, seseorang dapat menggunakan publicatau staticuntuk tanda tangan metode. Anda dapat menggunakan salah satu atau keduanya dan mereka tidak akan saling mengganggu, sehingga mereka saling orthogonal, bukan?

Pertanyaan saya adalah, bagaimana cara saya melanjutkan sisa fitur, terutama fitur yang tidak saling terkait?

Apakah semua fitur harus hidup berdampingan / menumpuk bersama?

Apakah ada bahasa pemrograman yang 100% ortogonal?

Saya tidak yakin bahwa ortogonalitas dapat berfungsi sebagai metrik yang berguna atau valid jika bahasa tujuan umum tingkat tinggi seperti C #, karena memerlukan perbedaan "operasi" dan "operan" - bagian kecil dari bahasa yang tidak mudah dibedakan dalam bahasa tingkat tinggi seperti C #.

Pemahaman saya tentang ortogonal didasarkan pada bahasa Assembler di mana ortogonalitas dari set instruksi CPU atau mikrokontroler tertentu tertentu menunjukkan apakah ada beberapa kendala pada operasi yang dilakukan oleh CPU ini atau pengontrol tergantung pada tipe data. Pada masa-masa awal ini penting karena tidak setiap CPU mendukung operasi pada angka fraksional atau angka dengan panjang yang berbeda dll.

Dalam hal ini saya lebih suka memeriksa ortogonalitas Bahasa Menengah Umum menggunakan bahasa Stack Machine sebagai target untuk kompiler C #, bukan C # itu sendiri.

Jika Anda benar-benar tertarik pada ortogonalitas C # dan saya tidak salah di sini (untuk tujuan apa pun) saya akan menyarankan melihat ke arah beberapa algoritma pemrograman genetik . Anda dapat menggunakannya untuk menghasilkan program yang berbeda dari set kata kunci yang diberikan (bahkan yang tidak berarti) dan Anda hanya dapat secara otomatis memeriksa apakah itu dapat dikompilasi. Ini akan membantu Anda untuk secara otomatis melihat elemen bahasa apa yang dapat digabungkan bersama dan memperoleh beberapa aspek dari metrik orthogonality Anda.

Istilah "orthogonality" adalah istilah awam untuk gagasan matematika yang tepat: istilah bahasa membentuk aljabar awal (lihat di Wikipedia).

Ini pada dasarnya berarti "ada korespondensi 1-1 antara sintaks dan makna". Ini berarti: ada persis satu cara untuk mengekspresikan sesuatu, dan, jika Anda dapat menaruh ekspresi di tempat tertentu, maka Anda dapat menempatkan ekspresi lain di sana juga.

Cara lain untuk berpikir tentang "ortogonal" adalah bahwa sintaksanya mematuhi prinsip substitusi. Misalnya jika Anda memiliki pernyataan dengan slot untuk ekspresi, maka ekspresi apa pun dapat diletakkan di sana dan hasilnya masih merupakan program yang valid secara sintaksis. Selanjutnya, jika Anda mengganti

Saya ingin menekankan bahwa "makna" tidak menyiratkan hasil komputasi. Jelas, 1 + 2 dan 2 + 1 sama dengan 3. Namun ketentuannya berbeda, dan menyiratkan perhitungan yang berbeda walaupun memiliki hasil yang sama. Artinya berbeda, sama seperti dua algoritma berbeda.

Anda mungkin pernah mendengar "pohon sintaksis abstrak" (AST). Kata "abstrak" di sini berarti tepat "ortogonal". Secara teknis kebanyakan AST sebenarnya tidak abstrak!

Mungkin Anda pernah mendengar tentang bahasa pemrograman "C"? Notasi tipe C tidak abstrak. Mempertimbangkan:

int f(int);

Jadi di sini adalah tipe deklarasi fungsi kembali int. Jenis pointer ke fungsi ini diberikan oleh:

int (*)(int)

Catatan, Anda tidak dapat menulis jenis fungsinya! Notasi tipe C menyebalkan! Itu tidak abstrak. Itu bukan ortogonal. Sekarang, misalkan kita ingin membuat fungsi yang menerima tipe di atas, bukan int:

int (*) ( int (*)(int) )

Semua baik-baik saja .. tapi .. bagaimana jika kita ingin mengembalikannya sebagai gantinya:

int (*)(int) (*) (int)

Aduh! Tidak valid Mari kita tambahkan parens:

(int (*)(int)) (*) (int)

Aduh! Itu juga tidak berhasil. Kita harus melakukan ini (itu satu-satunya cara!):

typedef int (intintfunc*) (int);
intintfunc (*)(int)

Sekarang tidak masalah, tetapi harus menggunakan typedef di sini buruk. C menyebalkan. Itu tidak abstrak. Itu bukan ortogonal. Inilah cara Anda melakukan ini dalam ML, yaitu:

 int -> (int -> int)

Kami mengutuk C di tingkat sintaksis.

Ok, sekarang mari kita belasan C ++. Kami dapat memperbaiki kebodohan di atas dengan templat dan mendapatkan notasi seperti ML (kurang lebih):

fun<int, int>
fun< fun<int,int>, int>

tetapi sistem tipe aktual pada dasarnya cacat oleh referensi: jika Tsuatu tipe, maka apakah T&suatu tipe? Jawabannya adalah waffly: pada tingkat sintaksis, jika Anda memiliki tipe U = T &, maka U & diizinkan tetapi itu hanya berarti T &: referensi ke referensi adalah referensi asli. Ini menyebalkan! Ini melanggar persyaratan keunikan secara semantik. Lebih buruk: T & & tidak diizinkan secara sintaksis: ini melanggar prinsip substitusi. Jadi referensi C ++ memecah ortogonalitas dalam dua cara berbeda, tergantung pada waktu pengikatan (analisis parsing atau tipe). Jika Anda ingin memahami bagaimana melakukan ini dengan benar .. tidak ada masalah dengan petunjuk!

Hampir tidak ada bahasa nyata yang ortogonal. Bahkan Skema, yang berpura-pura memiliki kejelasan ekspresi, tidak. Namun banyak bahasa yang baik dapat dinilai memiliki "cukup dekat dengan basis fitur ortogonal" dan itu adalah rekomendasi yang baik untuk sebuah bahasa, diterapkan baik pada sintaksis maupun semantik yang mendasarinya.

Membuktikan ortogonalitas terbukti negatif. Ini berarti Anda tidak memiliki konstruksi yang tidak ortogonal, yang berarti jauh lebih mudah untuk membuktikan sesuatu yang tidak ortogonal daripada yang ada.

Dalam praktiknya, kebanyakan orang berbicara tentang ortogonalitas bahasa pemrograman dalam hal derajat alih-alih menjadi sepenuhnya ortogonal atau tidak. Ketika pengetahuan dari melakukan sesuatu dalam satu konteks diterjemahkan ke konteks lain dan "melakukan apa yang Anda harapkan," bahasa itu dikatakan lebih ortogonal. LISP dianggap sangat ortogonal karena semuanya adalah daftar, tetapi saya tidak berpikir dapat dikatakan itu 100% ortogonal karena beberapa redudansi yang membuatnya lebih mudah digunakan. C ++ dianggap tidak terlalu orthogonal karena ada banyak "gotcha" kecil di mana ia tidak bekerja seperti yang Anda pikirkan.

Peringatan, saya tidak tahu apa-apa tentang topik ini.

Pandangan sekilas ke Wikipedia nampaknya mengindikasikan bahwa Orthogonality sebagian besar diarahkan pada pola desain dan desain sistem. Dalam hal bahasa pemrograman, entri menunjukkan bahwa set instruksi bersifat ortogonal jika ada satu dan hanya satu instruksi untuk setiap tindakan yang mungkin, atau lebih tepatnya, tidak ada instruksi yang tumpang tindih dengan yang lain.

Untuk C #, saya akan membayangkan bahwa itu adalah ortogonal, di mana sebagian besar trik sintaks ( foreachterlintas dalam pikiran) hanyalah ujung depan untuk versi konstruksi dasar yang dibentuk secara khusus ( foreachmenjadi forloop). Secara keseluruhan, bahasa hanya benar-benar mendukung melakukan hal-hal dalam satu cara, meskipun gula sintaksis menyediakan cara tambahan untuk melakukannya. Dan terakhir, semuanya dikompilasi hingga MSIL(atau apa pun namanya sekarang ini) dan MSILkemungkinan ortogonal.

Jika Anda membuat peringatan bahwa bahan gula sintaksis pada dasarnya adalah "pembungkus" untuk melakukannya dengan "cara yang sulit" Anda dapat menganalisis berbagai fitur bahasa, menghilangkan gula, dan melihat apakah ada konstruksi yang benar-benar tumpang tindih. Jika tidak, saya bayangkan Anda bisa mendeklarasikan bahasa orthogonal.

Dua sen saya.

Pertanyaan saya adalah, bagaimana cara saya melanjutkan sisa fitur, terutama fitur yang tidak saling terkait?

Anda terus melakukan apa yang Anda lakukan, menghitung semua kombinasi yang berfungsi atau dilarang.

Itu saja. Cukup menyakitkan untuk dilakukan.

Apakah semua fitur harus hidup berdampingan / menumpuk bersama?

Jika semua fitur dapat dipartisi menjadi subset terpisah yang tidak saling mengganggu, maka tentu saja, semua akan masuk akal.

Semua struktur data bekerja dengan semua tipe primitif. Semua operator ekspresi bekerja dengan semua tipe. Itu adalah definisi umum dari orthogonality. Tetapi Anda mungkin menginginkan lebih (atau kurang)

Namun, kadang-kadang, ada kasus khusus karena sistem operasi atau perpustakaan lama yang tidak ortogonal.

Selain itu, beberapa jenis sama sekali tidak sangat cocok. Misalnya Python memungkinkan Anda untuk membandingkan dua objek kamus untuk "memesan". Tetapi hampir tidak ada definisi yang masuk akal tentang "pemesanan" di antara kamus. Python mendefinisikan satu, tapi itu cukup bisa diperdebatkan. Apakah kasus khusus itu membuat kamus gagal dalam ujian ortogonalitas?

Seberapa ortogonal "cukup orthogonal"? Apa yang perlu Anda lihat agar bahagia dengan tingkat ortogonalitas dalam bahasa Anda.

Daftar fitur yang tidak lazim memang panjang di sebagian besar bahasa pemrograman, misalnya

• konflik kelas anonyous dengan refleksi java
• konflik penghapusan generik dan tipe dengan refleksi java
• array agak berbeda dengan objek lain, karena tipe khusus mereka, meskipun mereka adalah objek.
• metode statis vs contoh tidak sama, misalnya Anda tidak dapat mengganti metode statis
• kelas bersarang adalah setelah-pikiran
• dampak pengetikan dinamis vs statis pada strategi pengiriman pesan (lihat misalnya kasus tepi ini di C #)
• dll.

Itu hanya beberapa yang muncul di benak saya, tetapi ada banyak yang lain, dan juga dalam bahasa lain.

Sulit untuk memastikan bahwa tidak ada gangguan halus antara fitur bahasa. Seperti yang ditunjukkan CAR Hoare dalam makalahnya "Petunjuk tentang Pemrograman Desain Bahasa":

Bagian dari desain bahasa terdiri dari inovasi. Aktivitas ini mengarah ke fitur bahasa baru secara terpisah. Bagian paling sulit dari desain bahasa terletak pada integrasi : memilih serangkaian fitur bahasa yang terbatas dan memolesnya hingga hasilnya adalah kerangka kerja sederhana yang konsisten yang tidak memiliki tepi yang lebih kasar.

Mungkin, langkah yang baik untuk meningkatkan ortogonalitas adalah menyatukan konsep (yang mengarah ke jawaban @ karl-bielfeld). Jika semuanya, katakan daftar atau objek, kemungkinan konflik akan berkurang. Atau alih-alih memiliki kelas bertingkat setelah dipikirkan, jadikan fitur inti.

Sebagian besar makalah bahasa pemrograman membuktikan sifat-sifat tertentu dari bahasa tersebut (misalnya mengetikkan tingkat kesehatan) pada subset ("inti") dari bahasa yang diformalkan. Di sini kita harus melakukan yang sebaliknya, buktikan bahwa semua fitur menulis dengan aman. Juga, itu berarti seseorang harus mendefinisikan apa artinya "menulis". Apakah ini berarti "lari"? (Dalam hal ini, tautan di atas tentang tepi case dengan pengetikan dinamis dan statis aman). Apakah itu berarti "aman"? Apakah ini bisa diprediksi dari sudut pandang pengembang?

Semua itu sangat menarik - tetapi juga sangat menantang.