Dalam pemrograman fungsional bagaimana seseorang mencapai modularitas melalui hukum matematika?

Saya membaca dalam pertanyaan ini bahwa pemrogram fungsional cenderung menggunakan bukti matematika untuk memastikan bahwa program mereka bekerja dengan benar. Ini terdengar jauh lebih mudah dan lebih cepat daripada pengujian unit, tetapi berasal dari latar belakang OOP / Unit Testing yang belum pernah saya lihat.

Bisakah Anda menjelaskannya kepada saya dan memberi saya contoh?

Sebuah bukti jauh lebih sulit di dunia OOP karena efek samping, warisan tak terbatas, dan nullmenjadi anggota dari setiap jenis. Kebanyakan bukti bergantung pada prinsip induksi untuk menunjukkan bahwa Anda telah menutupi setiap kemungkinan, dan ketiga hal itu membuat lebih sulit untuk dibuktikan.

Katakanlah kita menerapkan pohon biner yang mengandung nilai integer (demi menjaga sintaksisnya lebih sederhana, saya tidak akan membawa pemrograman generik ke dalam ini, meskipun itu tidak akan mengubah apa pun.) Dalam Standar ML, saya akan mendefinisikan seperti ini:

datatype tree = Empty | Node of (tree * int * tree)

Ini memperkenalkan jenis baru yang disebut treeyang nilainya dapat datang tepat dua varietas (atau kelas, tidak menjadi bingung dengan konsep OOP kelas) - Emptynilai yang tidak membawa informasi, dan Nodenilai - nilai yang membawa 3-tuple yang pertama dan terakhir elemen adalah trees dan yang elemen tengahnya adalah a int. Perkiraan terdekat dengan deklarasi ini di OOP akan terlihat seperti ini:

public class Tree {
    private Tree() {} // Prevent external subclassing

    public static final class Empty extends Tree {}

    public static final class Node extends Tree {
        public final Tree leftChild;
        public final int value;
        public final Tree rightChild;

        public Node(Tree leftChild, int value, Tree rightChild) {
            this.leftChild = leftChild;
            this.value = value;
            this.rightChild = rightChild;
        }
    }
}

Dengan peringatan bahwa variabel jenis Pohon tidak pernah bisa null.

Sekarang mari kita menulis fungsi untuk menghitung tinggi (atau kedalaman) dari pohon, dan menganggap kita memiliki akses ke maxfungsi yang mengembalikan lebih besar dari dua angka:

fun height(Empty) =
        0
 |  height(Node (leftChild, value, rightChild)) =
        1 + max( height(leftChild), height(rightChild) )

Kami telah mendefinisikan heightfungsi berdasarkan kasus - ada satu definisi untuk Emptypohon dan satu definisi untuk Nodepohon. Kompiler tahu berapa banyak kelas pohon yang ada dan akan mengeluarkan peringatan jika Anda tidak mendefinisikan kedua kasus. Ekspresi Node (leftChild, value, rightChild)dalam fungsi tanda tangan mengikat nilai-nilai dari 3-tupel untuk variabel leftChild, valuedan rightChildmasing-masing sehingga kita bisa merujuk kepada mereka dalam definisi fungsi. Ini mirip dengan mendeklarasikan variabel lokal seperti ini dalam bahasa OOP:

Tree leftChild = tuple.getFirst();
int value = tuple.getSecond();
Tree rightChild = tuple.getThird();

Bagaimana kami dapat membuktikan bahwa kami telah menerapkan heightdengan benar? Kita dapat menggunakan induksi struktural , yang terdiri dari: 1. Buktikan yang heightbenar dalam kasus dasar dari treetipe kita ( Empty) 2. Dengan asumsi bahwa panggilan rekursif heightadalah benar, buktikan bahwa heightitu benar untuk kasus non-dasar ) (ketika pohon itu sebenarnya a Node).

Untuk langkah 1, kita bisa melihat bahwa fungsi selalu mengembalikan 0 ketika argumen adalah Emptypohon. Ini benar dengan definisi ketinggian pohon.

Untuk langkah 2, fungsi kembali 1 + max( height(leftChild), height(rightChild) ). Dengan asumsi bahwa panggilan rekursif benar-benar mengembalikan ketinggian anak-anak, kita dapat melihat bahwa ini juga benar.

Dan itu melengkapi buktinya. Langkah 1 dan 2 menggabungkan semua kemungkinan. Perhatikan, bagaimanapun, bahwa kita tidak memiliki mutasi, tidak ada null, dan ada dua jenis pohon. Singkirkan ketiga kondisi itu dan buktinya cepat menjadi lebih rumit, jika tidak praktis.

EDIT: Karena jawaban ini telah naik ke atas, saya ingin menambahkan contoh yang kurang sepele dari bukti dan menutupi induksi struktural sedikit lebih teliti. Di atas kami membuktikan bahwa jika heightkembali , nilai pengembaliannya benar. Kami belum membuktikannya selalu mengembalikan nilai. Kita dapat menggunakan induksi struktural untuk membuktikan ini juga (atau properti lainnya.) Sekali lagi, selama langkah 2, kita diizinkan untuk mengasumsikan properti memegang panggilan rekursif selama panggilan rekursif semua beroperasi pada anak langsung dari pohon.

Suatu fungsi bisa gagal mengembalikan nilai dalam dua situasi: jika itu melempar pengecualian, dan jika itu berulang selamanya. Pertama mari kita buktikan bahwa jika tidak ada pengecualian yang dilemparkan, fungsi berakhir:

1. Buktikan bahwa (jika tidak ada pengecualian yang dilemparkan) fungsi berakhir untuk kasing dasar ( Empty). Karena kita mengembalikan 0 tanpa syarat, itu berakhir.

2. Buktikan bahwa fungsi berakhir pada case non-base ( Node). Ada tiga fungsi panggilan di sini: +, max, dan height. Kami tahu itu +dan maxmengakhiri karena mereka adalah bagian dari perpustakaan standar bahasa dan mereka didefinisikan seperti itu. Seperti yang disebutkan sebelumnya, kami diizinkan untuk menganggap properti yang kami coba buktikan benar pada panggilan rekursif selama mereka beroperasi pada subtree langsung, jadi panggilan untuk heightmengakhiri juga.

Itu menyimpulkan buktinya. Perhatikan bahwa Anda tidak akan dapat membuktikan pemutusan dengan uji unit. Sekarang yang tersisa adalah menunjukkan bahwa heighttidak ada pengecualian.

1. Buktikan bahwa heighttidak melempar pengecualian pada kasus dasar ( Empty). Mengembalikan 0 tidak dapat menghasilkan pengecualian, jadi kami selesai.
2. Buktikan bahwa heighttidak melempar pengecualian pada case non-base ( Node). Asumsikan sekali lagi bahwa kita tahu +dan maxtidak membuang pengecualian. Dan induksi struktural memungkinkan kita untuk menganggap panggilan rekursif tidak akan melempar baik (karena beroperasi pada anak-anak langsung pohon itu). Tapi tunggu! Fungsi ini rekursif, tetapi tidak ekor rekursif . Kita bisa menghancurkan tumpukan! Bukti percobaan kami telah menemukan bug. Kita bisa memperbaikinya dengan mengubah heightmenjadi ekor rekursif .

Saya harap ini menunjukkan bukti tidak harus menakutkan atau rumit. Bahkan, setiap kali Anda menulis kode, Anda secara informal membuat bukti di kepala Anda (jika tidak, Anda tidak akan yakin bahwa Anda baru saja mengimplementasikan fungsinya.) Dengan menghindari nol, mutasi yang tidak perlu, dan warisan tak terbatas, Anda dapat membuktikan bahwa intuisi Anda adalah memperbaikinya dengan cukup mudah. Pembatasan ini tidak sekeras yang Anda kira:

• null adalah cacat bahasa dan menghilangkannya adalah baik tanpa syarat.
• Mutasi kadang-kadang tidak dapat dihindari dan perlu, tetapi dibutuhkan jauh lebih jarang daripada yang Anda pikirkan - terutama ketika Anda memiliki struktur data yang persisten.
• Adapun memiliki jumlah kelas yang terbatas (dalam arti fungsional) / subclass (dalam arti OOP) vs jumlah yang tidak terbatas dari mereka, itu adalah subjek yang terlalu besar untuk satu jawaban . Cukuplah untuk mengatakan ada trade design di sana - kemampuan kebenaran versus fleksibilitas ekstensi.

1. Jauh lebih mudah untuk beralasan tentang kode ketika semuanya tidak berubah . Akibatnya, loop lebih sering ditulis sebagai rekursi. Secara umum, lebih mudah untuk memverifikasi kebenaran dari solusi rekursif. Seringkali, solusi seperti itu juga akan membaca sangat mirip dengan definisi matematis masalah.

   Namun, ada sangat sedikit motivasi untuk melakukan pembuktian formal yang sebenarnya dalam kebanyakan kasus. Bukti sulit, butuh banyak waktu (manusia), dan ROI rendah.

2. Beberapa bahasa fungsional (khususnya dari keluarga ML) memiliki sistem tipe yang sangat ekspresif yang dapat memberikan jaminan yang jauh lebih lengkap bahwa sistem tipe C-style (tetapi beberapa ide seperti generik telah menjadi umum dalam bahasa mainstream juga). Ketika suatu program melewati pemeriksaan jenis, ini adalah semacam bukti otomatis. Dalam beberapa kasus, ini akan dapat mendeteksi beberapa kesalahan (misalnya, melupakan kasus dasar dalam rekursi, atau lupa untuk menangani kasus-kasus tertentu dalam kecocokan pola).

   Di sisi lain, sistem tipe ini harus dijaga sangat terbatas agar dapat didekati . Jadi dalam arti tertentu, kami mendapatkan jaminan statis dengan memberikan fleksibilitas - dan pembatasan ini adalah alasan mengapa makalah akademis yang rumit di sepanjang baris " Solusi monadik untuk masalah yang diselesaikan, di Haskell " ada.

   Saya menikmati kedua bahasa yang sangat liberal, dan bahasa yang sangat terbatas, dan keduanya memiliki kesulitan masing-masing. Tetapi bukan itu masalahnya bahwa seseorang akan “lebih baik”, masing-masing hanya lebih nyaman untuk jenis tugas yang berbeda.

Maka harus ditunjukkan bahwa bukti dan pengujian unit tidak dapat dipertukarkan. Keduanya memungkinkan kita untuk membatasi kebenaran program:

• Pengujian menempatkan batas atas pada kebenaran: Jika pengujian gagal, program salah, jika tidak ada tes gagal, kami yakin bahwa program akan menangani kasus yang diuji, tetapi mungkin masih ada bug yang belum ditemukan.

  int factorial(int n) {
    if (n <= 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 6;
    return -1;
  }
  
  assert(factorial(0) == 1);
  assert(factorial(1) == 1);
  assert(factorial(3) == 6);
  // oops, we forgot to test that it handles n > 3…
  

• Bukti menempatkan batas bawah pada kebenaran: Mungkin tidak mungkin untuk membuktikan sifat-sifat tertentu. Sebagai contoh, mungkin mudah untuk membuktikan bahwa suatu fungsi selalu mengembalikan angka (itulah yang dilakukan sistem tipe). Tetapi mungkin tidak mungkin untuk membuktikan bahwa angkanya akan selalu < 10.

  int factorial(int n) {
    return n;  // FIXME this is just a placeholder to make it compile
  }
  
  // type system says this will be OK…
  

Kata peringatan mungkin ada di sini:

Meskipun pada umumnya benar apa yang ditulis orang lain di sini - singkatnya, bahwa sistem tipe canggih, ketidakberlakuan dan transparansi referensial banyak berkontribusi pada ketepatan - bukan karena pengujian tidak dilakukan di dunia fungsional. Sebaliknya !

Ini karena kami memiliki alat seperti Quickcheck, yang menghasilkan kasus uji secara otomatis dan acak. Anda hanya menyatakan undang-undang yang harus dipatuhi suatu fungsi, dan kemudian quickcheck akan memeriksa undang-undang ini untuk ratusan kasus uji acak.

Anda lihat, ini sedikit lebih tinggi daripada pemeriksaan kesetaraan sepele pada beberapa kasus uji.

Berikut adalah contoh dari implementasi pohon AVL:

--- A generator for arbitrary Trees with integer keys and string values
aTree = arbitrary :: Gen (Tree Int String)


--- After insertion, a lookup with the same key yields the inserted value        
p_insert = forAll aTree (\t -> 
             forAll arbitrary (\k ->
               forAll arbitrary (\v ->
                lookup (insert t k v) k == Just v)))

--- After deletion of a key, lookup results in Nothing
p_delete = forAll aTree (\t ->
            not (null t) ==> forAll (elements (keys t)) (\k ->
                lookup (delete t k) k == Nothing))

Hukum kedua (atau properti) dapat kita baca sebagai berikut: Untuk semua pohon yang berubah-ubah t, yang berikut berlaku: jika ttidak kosong, maka untuk semua kunci kpohon itu akan memegang yang melihat ke atas kdi pohon yang merupakan hasil dari penghapusan kdari t, hasilnya akan Nothing(yang menunjukkan: tidak ditemukan).

Ini memeriksa fungsionalitas yang tepat untuk penghapusan kunci yang ada. Hukum apa yang harus mengatur penghapusan kunci yang tidak ada? Kami tentu saja ingin agar pohon yang dihasilkan sama dengan pohon yang kami hapus. Kami dapat mengekspresikan ini dengan mudah:

p_delete_nonexistant = forAll aTree (\t ->
                          forAll arbitrary (\k -> 
                              k `notElem` keys t ==> delete t k == t))

Dengan cara ini, pengujian sangat menyenangkan. Dan selain itu, setelah Anda belajar membaca properti quickcheck, mereka berfungsi sebagai spesifikasi yang dapat diuji mesin .

Saya tidak benar-benar mengerti apa yang dimaksud jawaban tertaut dengan "mencapai modularitas melalui hukum matematika", tetapi saya pikir saya memiliki gagasan tentang apa yang dimaksud.

Lihat Functor :

Kelas Functor didefinisikan seperti ini:

 class Functor f where
   fmap :: (a -> b) -> f a -> f b

Itu tidak datang dengan kasus uji, tetapi dengan beberapa hukum yang harus dipenuhi.

Semua instance Functor harus mematuhi:

 fmap id = id
 fmap (p . q) = (fmap p) . (fmap q)

Sekarang katakanlah Anda menerapkan Functor( sumber ):

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

Masalahnya adalah untuk memverifikasi bahwa implementasi Anda memenuhi hukum. Bagaimana Anda melakukannya?

Salah satu pendekatan adalah menulis kasus uji. Keterbatasan mendasar dari pendekatan ini adalah bahwa Anda memverifikasi perilaku dalam jumlah kasus yang terbatas (semoga sukses secara mendalam menguji fungsi dengan 8 parameter!), Dan lulus tes tidak dapat menjamin apa pun kecuali tes lulus.

Pendekatan lain adalah dengan menggunakan penalaran matematis, yaitu bukti, berdasarkan pada definisi aktual (bukan pada perilaku dalam sejumlah kasus tertentu). Idenya di sini adalah bahwa bukti matematika mungkin lebih efektif; Namun, ini tergantung pada seberapa setuju program Anda dengan bukti matematika.

Saya tidak dapat membimbing Anda melalui bukti formal yang sebenarnya bahwa Functorcontoh di atas memenuhi hukum, tetapi saya akan mencoba dan memberikan garis besar seperti apa buktinya:

1. fmap id = id
   • jika kita punya Nothing
     • fmap id Nothing= Nothingoleh bagian 1 dari implementasi
     • id Nothing= Nothingdengan definisiid
   • jika kita punya Just x
     • fmap id (Just x)= Just (id x)= Just xdengan bagian 2 dari implementasi, kemudian oleh definisiid
2. fmap (p . q) = (fmap p) . (fmap q)
   • jika kita punya Nothing
     • fmap (p . q) Nothing= Nothingdengan bagian 1
     • (fmap p) . (fmap q) $ Nothing= (fmap p) $ Nothing= Nothingoleh dua aplikasi bagian 1
   • jika kita punya Just x
     • fmap (p . q) (Just x)= Just ((p . q) x)= Just (p (q x))dengan bagian 2, lalu dengan definisi.
     • (fmap p) . (fmap q) $ (Just x)= (fmap p) $ (Just (q x))= Just (p (q x))oleh dua aplikasi bagian dua

"Waspadalah terhadap bug dalam kode di atas; Saya hanya membuktikannya benar, tidak mencobanya." - Donald Knuth

Di dunia yang sempurna, pemrogram sempurna dan tidak melakukan kesalahan, jadi tidak ada bug.

Dalam dunia yang sempurna, ilmuwan komputer dan ahli matematika juga sempurna, dan jangan melakukan kesalahan juga.

Tetapi kita tidak hidup di dunia yang sempurna. Jadi kita tidak bisa mengandalkan programmer untuk tidak membuat kesalahan. Tetapi kita tidak dapat berasumsi bahwa ilmuwan komputer mana pun yang memberikan bukti matematis bahwa suatu program benar tidak membuat kesalahan dalam bukti itu. Jadi saya tidak akan memperhatikan siapa pun yang mencoba membuktikan bahwa kodenya berfungsi. Tulis unit-test dan tunjukkan pada saya bahwa kode berperilaku sesuai dengan spesifikasi. Hal lain tidak akan meyakinkan saya tentang apa pun.