Mengapa invarian penting dalam Ilmu Komputer

Saya mengerti 'invarian' dalam arti harfiahnya. Saya juga mengenalinya ketika saya mengetik kode. Tapi saya rasa saya tidak mengerti pentingnya istilah ini dalam konteks ilmu komputer.

Setiap kali saya membaca percakapan \ kertas putih tentang desain bahasa dari programmer terkenal \ ilmuwan komputer, istilah 'invarian' terus bermunculan sebagai jargon; dan itu adalah bagian yang saya tidak mengerti. Apa yang istimewa dari ini?

Algoritma adalah proses yang berulang. Jika itu dapat diulang, itu harus memiliki atribut yang tidak berubah dengan pengulangan. Ini adalah invarian Anda. Invarian dikombinasikan dengan dan / atau beroperasi pada (beragam) data yang bervariasi yang akan dimasukkan ke dalam algoritma Anda.

Jadi inti dari pemrograman adalah untuk mengidentifikasi apa yang tidak berbeda - yang pada dasarnya adalah program Anda.

Dalam program berorientasi objek, ada anggapan bahwa setiap objek harus melakukan satu hal dengan baik. Ini pada dasarnya berarti bahwa (untuk OOP berbasis kelas) kelas mendefinisikan invarian untuk algoritma tunggal, bersama dengan place-holder (variabel) untuk setiap data varian yang mungkin diperlukan objeknya. Idealnya dalam OO, Anda akan mengisolasi apa yang bervariasi sebanyak mungkin, sehingga masing-masing objek sebagian besar invarian.

Gagasan invarian sangat terkait dengan 'efek samping'. Saya percaya ini dipromosikan oleh pendekatan Bertrand Meyer 'Desain oleh Kontrak (DbC)' untuk desain perangkat lunak.

DbC memperkaya Jenis Data Abstrak (tulang punggung kelas) dengan 3 gagasan penting, prasyarat, postkondisi, invarian . Itu mudah dijelaskan ketika merujuk ke prosedur, jadi saya akan mencoba menjelaskan sehubungan dengan itu:

1. Sebuah prasyarat mewakili data kondisi masukan untuk prosedur harus menghormati untuk memanggil prosedur itu. Prasyarat ini harus dihormati dan ditegakkan oleh klien dari prosedur khusus itu. Namun perancang prosedur mungkin membela dari klien yang tidak menghormati prasyarat dengan menyatakan kondisi itu sebagai baris pertama dalam prosedur. Misalnya memiliki metode double divide(double dividend, double divisor)prasyarat mungkin divisor != 0.

2. Sebuah postcondition mewakili kondisi pada data keluaran setelah kembali prosedur; sepenuhnya merupakan tugas perancang prosedur untuk menghormati kondisi akhir ini asalkan prasyarat tersebut dihormati; dalam gaya pemrograman pertahanan sebelum kembali, kondisi akhir dapat ditegaskan.

3. Sebuah invarian dapat dianggap sebagai baik prakondisi dan postcondition, tapi dengan pemahaman yang berbeda untuk prakondisi dan postcondition dari konsep di atas. Seorang invarian pada dasarnya mengatakan bahwa jika input memiliki kondisi tertentu terpenuhi sebelum prosedur dipanggil, maka kondisi tertentu tersebut valid setelah prosedur dipanggil. Misalnya invarian yang valid untuk suatu prosedur boolean search(int term, int array[])mungkin mengatakan bahwa keadaan arraysebelum panggilan sama dengan setelah panggilan.

Menegakkan invarian pada prosedur (dan bukan hanya prosedur) adalah hal yang hebat karena mengurangi efek samping ; ini berguna karena efek samping adalah kejahatan besar dalam pemrograman. Prosedur tertentu dapat mengubah keadaan argumen input, atau mengubah keadaan beberapa variabel global, atau bergantung pada beberapa variabel global; ini dapat menyebabkan situasi yang tidak menyenangkan di mana dua panggilan identik pada prosedur yang sama (dengan input yang sama) dapat menghasilkan output yang berbeda. Ini mengarah pada mengetahui sejarah panggilan dan sangat sulit untuk di-debug terutama dalam konteks multithreading.

Invarian adalah properti logis yang dipertahankan oleh beberapa operasi.

• Anda perlu invarian untuk alasan tentang loop. Karena Anda tidak tahu sebelumnya berapa banyak iterasi yang akan ada (atau Anda tidak perlu loop), setiap iterasi harus mempertahankan invarian, sehingga pada akhirnya Anda dapat membuktikan beberapa properti yang berguna tentang loop.

• Anda perlu invarian untuk alasan tentang properti data yang dienkapsulasi. Seringkali berbagai data di dalam modul atau objek perlu memenuhi properti tertentu untuk operasi yang benar (misalnya, daftar yang mewakili set harus selalu diurutkan). Anda ingin agar setiap fungsi atau metode yang beroperasi pada data mempertahankan properti ini, sehingga mereka juga invarian.

Dari apa yang saya tahu pentingnya invarian berasal dari kenyataan bahwa itu adalah blok bangunan untuk membuktikan bahwa suatu algoritma tidak menghitung fungsi tertentu. Misalnya Anda telah mengembangkan algoritma penyortiran baru tetapi bagaimana Anda bisa begitu yakin bahwa itu benar-benar diurutkan dengan setiap input atau dengan setiap output yang benar. Langkah selanjutnya adalah membuat invarian yang sesuai dengan alur algoritma dan membuktikan bahwa invarian menggunakan invarian.

Dalam konteks sistem tipe bahasa pemrograman, tipe invarian adalah tipe yang tidak dapat dikonversi. Sebagai contoh di java, ketika overloading suatu metode, semua parameter invarian, sedangkan tipe pengembaliannya adalah kovarian (mungkin sama atau subtipe).