Apa yang invarian, bagaimana mereka digunakan, dan apakah Anda pernah menggunakannya dalam program Anda?

48

Saya membaca Coders at Work , dan di dalamnya ada banyak pembicaraan tentang invarian. Sejauh yang saya mengerti, invarian adalah suatu kondisi yang berlaku sebelum dan sesudah ekspresi. Mereka, antara lain, berguna dalam membuktikan bahwa loop itu benar, jika saya ingat kursus Logika saya dengan benar.

Apakah uraian saya benar, atau apakah saya melewatkan sesuatu? Apakah Anda pernah menggunakannya dalam program Anda? Dan jika demikian, apa manfaatnya bagi mereka?

invariants Gablin
sumber
en.wikipedia.org/wiki/Invariant_(computer_science)
Robert Harvey
@ Robert Harvey: Ya, saya baru saja membaca itu. Tetapi bagi saya tampaknya invarian hanya berguna ketika Anda mencoba untuk membuktikan sesuatu. Apakah ini benar (tidak ada permainan kata-kata)?
Gablin
Itu pemahaman saya; ketika Anda mencoba untuk alasan tentang program Anda, untuk membuktikan kebenarannya.
Robert Harvey
3
@ user9094: Pernyataan adalah pernyataan bahwa ada sesuatu yang benar pada titik tertentu dalam runtime, dan diwakili dalam kode. Invarian adalah pernyataan (orang berharap beralasan) yang akan selalu benar setiap kali itu berlaku, dan tidak diwakili dalam kode itu sendiri.
David Thornley
1
Invarian memang berguna untuk membuktikan kebenaran, tetapi mereka tidak terbatas pada kasus itu. Mereka juga berguna untuk pemrograman defensif dan selama debugging. Mereka tidak hanya membantu membuktikan kode Anda benar, mereka membantu alasan tentang kode dan menemukan lokasi bug yang dekat dengan asal.
Oddthinking

Jawaban:

41

Dalam OOP, invarian adalah sekumpulan pernyataan yang harus selalu berlaku selama masa objek agar program valid. Itu harus benar dari ujung konstruktor ke awal destruktor setiap kali objek saat ini tidak menjalankan metode yang mengubah keadaannya.

Contoh invarian adalah bahwa salah satu dari dua variabel anggota harus nol. Atau bahwa jika seseorang memiliki nilai yang diberikan, maka himpunan nilai yang diizinkan untuk yang lain adalah ini atau itu ...

Saya kadang-kadang menggunakan fungsi anggota objek untuk memeriksa bahwa invarian memegang. Jika bukan ini masalahnya, sebuah penegasan diajukan. Dan metode ini disebut pada awal dan keluar dari setiap metode yang mengubah objek (dalam C ++, ini hanya satu baris ...)

Xavier Nodet
sumber
11
+1 untuk menyebutkan invarian tidak harus benar di tengah metode eksekusi.
Oddthinking
1
@Ohdthinking Sebaiknya hindari itu jika memungkinkan. Akan mudah untuk memasuki keadaan yang melanggar invarian dan lupa untuk mengembalikan semuanya dengan benar sebelum kembali. Pengecualian juga bisa membuat Anda kesulitan.
Alexander
3
@Alexander: Untuk invarian non-sepele, hampir mustahil untuk dihindari. Jika Anda perlu memperbarui lebih dari satu variabel dalam suatu metode, seperti dijelaskan dalam jawaban, ada titik di mana hanya satu yang telah diperbarui dan invariannya salah. Ada cukup banyak kendala dalam menulis kode yang baik tanpa menambahkan yang baru.
Berpikir
@Otuk Berpikir Ya, ini sering kali tidak terhindarkan. Tetapi misalnya, jika ada sekelompok variabel yang secara logis dimiliki bersama (misalnya array, dan indeks item "terpilih" dalam array), maka mungkin layak mengekstraknya ke suatu jenis. Dari sana, mutasi dari array atau tipe dapat diekspresikan sebagai penugasan tunggal dari instance baru dari tipe itu
Alexander
13

Ya, hal-hal yang saya lihat di utas ini semuanya hebat, tetapi saya memiliki definisi tentang 'invarian' yang telah sangat membantu saya di tempat kerja.

Invarian adalah aturan logis apa pun yang harus dipatuhi selama pelaksanaan program Anda yang dapat dikomunikasikan kepada manusia, tetapi tidak untuk kompiler Anda.

Definisi ini bermanfaat karena memecah kondisi menjadi dua kelompok: mereka yang dapat dipercayai oleh pembuat kompiler, dan mereka yang harus didokumentasikan, dibahas, dikomentari, atau dikomunikasikan kepada kontributor agar mereka dapat berinteraksi dengan basis kode tanpa memperkenalkan bug .

Juga, definisi ini sangat membantu karena memungkinkan Anda untuk menggunakan generalisasi, "Invarian buruk".

Sebagai contoh, shifter dalam mobil transmisi manual direkayasa untuk menghindari invarian. Jika saya mau, saya bisa membuat transmisi dengan satu tuas untuk setiap gigi. Tuas ini bisa maju ("bertunangan") atau kembali ("terlepas"). Dalam sistem seperti itu, saya telah membuat "invarian", yang mungkin didokumentasikan seperti itu:

"Sangat penting bahwa gigi yang saat ini sedang digunakan dilepaskan sebelum gigi yang berbeda digunakan. Untuk menggunakan dua gigi pada saat yang sama akan menyebabkan tekanan mekanis yang akan merobek transmisi. Selalu melepaskan gigi yang saat ini sedang terlibat sebelum menggunakan yang lain."

Jadi, orang mungkin menyalahkan transmisi yang rusak pada mengemudi yang ceroboh. Mobil modern, bagaimanapun, menggunakan tongkat tunggal yang berputar di sekitar gigi. Ini dirancang sedemikian rupa sehingga, pada mobil stick-shift modern, tidak mungkin untuk menggunakan dua roda gigi secara bersamaan.

Dengan cara ini, kita dapat mengatakan bahwa transmisi telah direkayasa untuk 'menghapus invarian', karena tidak mengizinkan dirinya untuk dikonfigurasikan secara mekanis dengan cara yang melanggar aturan logis.

Setiap invarian semacam ini yang Anda hapus dari kode Anda merupakan peningkatan, karena ini menurunkan beban kognitif untuk bekerja dengannya.

Daniel Burbank
sumber
1
Jika invarian adalah aturan logis apa pun yang harus dipatuhi selama pelaksanaan program Anda, dan aturan logis Anda adalah bahwa tidak ada dua roda gigi yang dapat digunakan pada saat yang sama, maka bukan merupakan invarian bahwa tidak ada dua roda gigi yang dapat bergerak bersamaan. waktu? Tanpa invarian ini, transmisi Anda bisa di dua gigi pada saat yang sama, dan dengan demikian merobek sendiri. Pertama, bukankah satu tongkat shifter benar-benar menegakkan invarian itu? Kedua, mengapa seorang invarian secara intrinsik baik atau buruk?
Dustin Cleveland
1
Perbandingan dengan roda gigi mobil sangat jelas bagi saya. Terima kasih!
Marecky
"Invarian adalah aturan logis apa pun yang harus dipatuhi selama pelaksanaan program Anda yang dapat dikomunikasikan kepada manusia, tetapi tidak untuk kompiler Anda." - Saya sangat suka ini, ringkas dan mudah diingat.
ZeroKnight
@DustinCleveland Saya berpikir bahwa dalam contoh ini, mekanisme di balik stick stick adalah 'compiler' yang 'menegakkan' aturan, sedangkan driver yang mungkin menyebabkan insiden adalah salah satu dari banyak klien yang harus mengkonsumsi dan mengingat informasi yang telah "didokumentasikan, dibahas, dikomentari, atau dikomunikasikan."
ebernard
Penjelasan yang brilian! Saya benar-benar mengerti sekarang alasan mengapa invarian dalam kode Anda adalah praktik yang buruk.
Ben C Wang
3

Invarian (dalam akal sehat) berarti beberapa kondisi yang harus benar pada titik waktu tertentu atau bahkan selalu ketika program Anda dieksekusi. misalnya PreConditions dan PostConditions dapat digunakan untuk menyatakan beberapa kondisi yang harus benar ketika suatu fungsi dipanggil dan ketika ia kembali. Invarian objek dapat digunakan untuk menyatakan bahwa suatu objek harus memiliki status valid sepanjang waktu objek itu ada. Ini adalah desain berdasarkan prinsip kontrak.
Saya telah menggunakan invarian secara informal menggunakan cek dalam kode. Tetapi baru-baru ini saya bermain dengan perpustakaan kontrak kode untuk. Net yang secara langsung mendukung invarian.

softveda
sumber
3

Berdasarkan kutipan berikut dari Coders At Work ...

Tetapi begitu Anda mengetahui invarian yang dipertahankannya, Anda dapat melihat, ah, jika kami mempertahankan invarian itu, maka kami akan mendapatkan waktu pencarian log.

... Saya kira "invarian" = "kondisi yang ingin Anda pertahankan untuk memastikan efek yang diinginkan".

Tampaknya invarian memiliki dua pengertian yang berbeda secara halus:

  1. Sesuatu yang tetap sama.
  2. Sesuatu yang Anda coba pertahankan, untuk mencapai tujuan X (seperti "waktu pencarian log" di atas).

Jadi aku seperti sebuah pernyataan; 2 seperti alat untuk membuktikan kebenaran, kinerja, atau properti lainnya - saya pikir. Lihat artikel Wikipedia untuk contoh 2 (membuktikan kebenaran solusi untuk teka-teki MU).

Sebenarnya indra ke-3 yang invarian adalah:

.3. Apa yang seharusnya dilakukan oleh program (atau modul atau fungsi); dengan kata lain, tujuannya.

Dari wawancara Coders At Work yang sama:

Tetapi apa yang membuat perangkat lunak besar dapat dikelola adalah memiliki beberapa invarian global atau pernyataan gambaran besar tentang apa yang seharusnya dilakukan dan hal-hal apa yang seharusnya benar.

Jonathan Aquino
sumber
1

Invarian adalah seperti aturan atau asumsi yang dapat digunakan untuk mendikte logika program Anda.

Misalnya, Anda memiliki beberapa aplikasi perangkat lunak yang melacak akun pengguna. Anggap juga bahwa pengguna dapat memiliki beberapa akun, tetapi untuk alasan apa pun Anda perlu membedakan antara akun utama pengguna dan akun "alias".

Ini bisa menjadi catatan DB atau sesuatu yang lain, tetapi untuk sekarang mari kita asumsikan setiap akun pengguna diwakili oleh objek kelas.

class userAccount {private char * pUserName; karakter pribadi * pParentAccountUserName;

...}

Invarian mungkin adalah asumsi bahwa jika pParentAccountUserName adalah NULL atau kosong maka objek ini adalah akun induk. Anda dapat menggunakan invarian ini untuk membedakan berbagai jenis akun. Mungkin ada metode yang lebih baik untuk membedakan berbagai jenis akun pengguna, jadi perlu diingat ini hanyalah contoh untuk menunjukkan bagaimana invarian dapat digunakan.

Pemda
sumber
Invarian memeriksa keadaan suatu program. Itu bukan keputusan desain.
Xavier Nodet
3
Invarian tidak memeriksa apa pun. Anda dapat memeriksa status program untuk melihat apakah invarian yang BENAR atau SALAH, tetapi invarian sendiri "tidak melakukan" apa pun.
Pemdas
2
Biasanya, di C ++ Anda akan melihat beberapa jenis invarian kelas seperti anggota x harus kurang dari 25 dan lebih besar dari 0. Itu adalah invarian. Setiap pemeriksaan terhadap invarian itu adalah pernyataan. Dalam contoh yang saya miliki di atas, invarian saya adalah jika pParentAccountUserName adalah NULL atau kosong maka itu adalah akun induk. Invarian adalah keputusan yang dirancang.
Pemdas
Bagaimana Anda memeriksa bahwa jika pParentAccountUserName adalah NULL atau kosong, objek ini adalah akun induk? Pernyataan Anda hanya menentukan apa yang seharusnya mewakili nilai null / kosong. Yang invarian adalah bahwa sistem sesuai dengan itu, yaitu bahwa pParentAccountUserName hanya bisa nol atau kosong jika itu adalah akun induk. Ini perbedaan yang halus.
Cameron
1

Berasal dari latar belakang fisika, dalam fisika kita memiliki invarian, yang pada dasarnya jumlah yang tidak bervariasi di seluruh perhitungan / simulasi. Misalnya, dalam fisika, untuk sistem tertutup, total energi dilestarikan. Atau lagi dalam fisika, jika dua partikel bertabrakan, fragmen yang dihasilkan harus mengandung persis energi yang mereka mulai, dan momentum yang persis sama (kuantitas vektor). Biasanya tidak ada cukup banyak invarian untuk secara spesifik menentukan hasilnya. Misalnya dalam tabrakan 2 partikel, kami memiliki empat invarian, tiga komponen momentum, dan komponen energi, tetapi sistem memiliki enam derajat kebebasan (enam angka untuk menggambarkan keadaannya). Para invarian harus dilestarikan dalam kesalahan pembulatan, tetapi konservasi mereka tidak membuktikan solusinya benar.

Jadi biasanya, hal-hal ini penting sebagai pemeriksaan kewarasan, tetapi dengan sendirinya mereka tidak dapat membuktikan kebenaran.

Omega Centauri
sumber
1
-1 Invarian dalam fisika berbeda. Menghitung solusi tidak sama dengan membuktikan bahwa suatu algoritma itu benar. Untuk yang terakhir, invarian dapat membuktikan kebenaran.
aaronasterling