Hitung jika suatu fungsi murni

Sesuai Wikipedia:

Dalam pemrograman komputer, fungsi dapat digambarkan sebagai murni jika kedua pernyataan ini tentang fungsi ditahan: Fungsi selalu mengevaluasi nilai hasil yang sama mengingat nilai argumen yang sama. Nilai hasil fungsi tidak dapat bergantung pada informasi atau keadaan tersembunyi yang dapat berubah saat eksekusi program berlangsung atau antara berbagai eksekusi program, juga tidak dapat bergantung pada input eksternal dari perangkat I / O. Evaluasi hasil tidak menyebabkan efek samping atau keluaran yang dapat diamati secara semantik, seperti mutasi objek yang dapat berubah atau keluaran ke perangkat I / O.

Saya bertanya-tanya apakah mungkin untuk menulis fungsi yang menghitung apakah suatu fungsi murni atau tidak. Contoh kode dalam Javascript:

function sum(a,b) {
    return a+b;
}

function say(x){
    console.log(x);
}

isPure(sum) // True
isPure(say) // False

Ya, itu mungkin, tergantung pada bahasanya.

Dalam JavaScript, Anda dapat mengetahui apakah suatu fungsi murni dengan kriteria berikut:

• Hanya membaca parameter dan penduduk lokal;

• Itu hanya menulis penduduk setempat;

• Pada non-lokal, ini hanya memanggil fungsi murni;

• Semua fungsi yang dipanggil secara implisit murni, misalnya toString,; dan

• Itu hanya menulis properti lokal jika mereka tidak alias non-lokal.

Aliasing tidak dapat ditentukan dalam JavaScript dalam kasus umum, karena Anda selalu dapat mencari properti dari objek secara dinamis ( object["property"]). Asalkan Anda tidak pernah melakukan itu, dan Anda memiliki sumber seluruh program, maka saya pikir masalahnya mudah ditelusuri. Anda juga akan memerlukan informasi tentang fungsi asli mana yang memiliki efek samping, seperti console.logatau sebagian besar apa pun yang melibatkan DOM.

Istilah "murni" juga dapat menggunakan beberapa klarifikasi. Bahkan dalam bahasa pemrograman yang sangat, diketik secara statis, murni fungsional, di mana semua fungsi secara transparan transparan, suatu fungsi masih dapat gagal untuk diakhiri. Jadi ketika kita berbicara tentang id :: a -> a, apa yang sebenarnya kita katakan bukanlah:

Diberikan beberapa nilai tipe a, fungsi idmenghasilkan nilai tipe a.

Melainkan:

Mengingat beberapa nilai dari jenis a, fungsi idtidak tidak menghasilkan nilai yang tidak tipe a.

Karena implementasi yang valid idadalah error "Not implemented!". Seperti yang ditunjukkan oleh Peteris, nontotalitas ini dapat dilihat sebagai semacam ketidakmurnian. Koka adalah bahasa pemrograman fungsional — dengan sintaks yang dimodelkan pada JavaScript — yang dapat menyimpulkan kemungkinan efek seperti divergensi (nonterminasi), transparansi referensial, melempar pengecualian, dan tindakan I / O.

Tidak. Anda dapat dengan mudah memeriksa apakah suatu fungsi hanya melakukan operasi "murni-aman", seperti yang dijelaskan dalam jawaban Jon Purdy, tetapi itu IMO tidak cukup untuk menjawab pertanyaan.

Pertimbangkan fungsi ini:

function possiblyPure(x) {
    if (someCheck(x)) {
        return x+1; // pure code path
    }
    else {
        console.log("I'm so unpure..."); // unpure code path
    }
}

Jelas, jika someChecktidak pasti, demikian juga possiblyPure. Tetapi, jika someCheckmurni dan mengembalikan trueuntuk setiap nilai yang mungkin x, possiblyPureadalah murni, karena jalur kode tidak murni tidak dapat dijangkau!

Dan inilah bagian yang sulit: menentukan apakah someCheckmengembalikan benar untuk setiap input yang mungkin. Mencoba menjawab pertanyaan itu dengan segera membawa Anda ke ranah masalah terputus-putus dan masalah serupa yang belum diputuskan.

EDIT: Bukti bahwa itu tidak mungkin

Ada beberapa ketidakpastian apakah fungsi murni harus diakhiri pada setiap input yang mungkin. Tetapi dalam kedua kasus, masalah penghentian dapat digunakan untuk menunjukkan bahwa pemeriksaan kemurnian tidak mungkin.

Kasus A) Jika fungsi murni diperlukan untuk menghentikan setiap input yang mungkin, Anda harus menyelesaikan masalah penghentian untuk menentukan apakah fungsi tersebut murni atau tidak. Karena ini diketahui tidak mungkin, dengan definisi ini, kemurnian tidak dapat dihitung.

Kasus B) Jika fungsi murni dibolehkan untuk tidak berhenti pada beberapa input, kita dapat membangun sesuatu seperti itu: Mari kita asumsikan bahwa isPure(f)menghitung jika fadalah string yang mendefinisikan fungsi murni.

function halts(f) {
   var fescaped = f.replace(/\"/g, '\\"');
   var upf = 'function() { '+f+'("'+fescaped+'\); console.log("unpure"); }';
   return isPure(upf);
}

Sekarang isPureharus menentukan apakah fberhenti pada sumbernya sendiri sebagai input. Jika berhenti, upftidak murni; jika itu tidak berakhir, upfadalah murni iff fadalah murni.

Jika isPureberfungsi seperti yang diharapkan (mengembalikan hasil yang benar dan berakhir pada setiap input), kami akan menyelesaikan masalah penghentian (*)! Karena ini diketahui mustahil, isPuretidak bisa ada.

(*) untuk fungsi JavaScript murni, yang cukup untuk menyelesaikannya untuk mesin turing juga.

Pertanyaan stackoverflow ini memiliki jawaban oleh yfeldblum yang relevan di sini. (Dan memiliki downvote untuk beberapa alasan saya tidak bisa mengerti. Apakah etiket buruk untuk memperbaiki sesuatu yang berusia 3 tahun?) Dia memberikan bukti bahwa apakah suatu fungsi murni dapat direduksi ke masalah penghentian dalam komentar.

Saya pikir dari sudut pandang praktis itu tidak akan terlalu sulit untuk beberapa bahasa jika Anda membiarkan fungsi kembali ya, tidak, atau mungkin. Saya menonton video tentang Clojure beberapa hari yang lalu, dan pembicara telah melakukan sejumlah contoh pengotor dalam basis kode dengan mencari sekitar 4 string yang berbeda (seperti "ref"). Karena penekanan Clojure pada kemurnian dan pemisahan hal-hal yang tidak murni, itu sepele, tetapi itu tidak persis apa yang Anda cari.

Jadi, secara teori tidak mungkin, secara praktis mungkin jika Anda mengubah sedikit pertanyaan, dan saya pikir betapa sulitnya akan sangat tergantung pada bahasa. Bahasa yang lebih sederhana / lebih bersih dengan fokus pada keabadian dan refleksi yang baik akan lebih mudah.

Pertanyaan yang bagus

Yang terbaik yang dapat Anda lakukan dalam praktik, dengan asumsi tidak ada kemampuan untuk mendengarkan tindakan i / o untuk memanggil fungsi sesering mungkin. Kemudian lihat apakah nilai kembali konsisten.

Tetapi Anda tidak dapat melakukan ini secara umum. Dapat diperdebatkan, program non-stop adalah non-murni, dan kami tidak dapat memutuskan masalah penghentian.

Tidak mungkin dalam kasus umum. Lihat menghentikan masalah . Secara singkat, tidak mungkin untuk menulis sebuah program yang, mengingat fungsi dan input yang berubah-ubah, menentukan apakah program tersebut akan berhenti atau berjalan selamanya. Jika berjalan selamanya, itu bukan fungsi murni yang sesuai dengan definisi yang Anda berikan.