Apakah ada definisi kanonik tentang fungsi “murni”?

9

StackOverflow menunjuk saya ke sini, jadi pertanyaannya mungkin sedikit dalam istilah awam.

Wikipedia mendefinisikan fungsi murni sebagai

Dalam pemrograman komputer, suatu fungsi dapat digambarkan sebagai fungsi murni jika kedua pernyataan ini tentang fungsi tersebut:

  1. Fungsi selalu mengevaluasi nilai hasil yang sama dengan 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.
  2. 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.

Namun tampaknya tidak mengutip sumber apa pun - sehingga sulit untuk mengatakan apakah ini merupakan definisi yang diterima, atau siapa yang mendefinisikannya dengan cara ini.

Ketika saya melihat apa yang dilakukan bahasa ketika mereka menyertakan sintaks / anotasi untuk fungsi "murni", ada beberapa pendekatan yang berbeda:

  1. Di D , satu-satunya batasan adalah non-mutasi negara global. Fungsi "Murni" dapat mengubah argumennya.
  2. Dalam GCC ada dua jenis "murni": pure(tidak ada efek samping, tetapi dapat membaca keadaan global) dan const(sangat murni sesuai definisi wikipedia).
  3. Dalam C # , itu didefinisikan sebagai "tidak membuat perubahan status yang terlihat" (apa pun itu).
  4. Haskell mengikuti definisi Wikipedia.

Jadi pertanyaan saya adalah: adakah definisi kanonik fungsi murni?
Dan jika ada, apa sumbernya?

terminology functional-programming semantics Andrey Shchekin
sumber
Terkait perspektif historis, meski sepertinya tidak ada yang memberikan jawaban yang pasti atau bersumber.
Guildenstern
1
Ini tidak layak jawaban tetapi di sini adalah definisi saya: jika x = y (dengan definisi itu) maka fx = fy adalah benar dan f menyebabkan tidak ada perubahan terukur secara eksternal dalam keadaan (yaitu semua perubahan dalam keadaan internal ke x, y, dan f). Haskell mengambil keuntungan dari ini. Ini mengimplementasikan evaluasi malas dengan memutasi thunks dan menggantinya dengan fungsi yang segera mengembalikan hasilnya. Itu jika Anda mengevaluasi (fx) itu mungkin benar-benar berubah f dan x di bawah tenda tetapi Anda tidak pernah tahu.
Jake

Jawaban:

3

Sebagaimana dicatat dalam makalah ini Imperative Functional Programming , (1993) oleh Peyton-Jones dan Wadler (di antara kelompok peneliti yang menciptakan Haskell):

Kami fokus pada solusi murni fungsional, yang mengesampingkan efek samping, karena dua alasan. Pertama, tidak adanya efek samping memungkinkan penggunaan penalaran dan transformasi program yang tidak terbatas ...

fokusnya adalah tidak adanya efek samping untuk memungkinkan transformasi program (yaitu optimisasi kompiler).

Apa efek sampingnya? Makalah ini pada gilirannya menunjuk ke Mengintegrasikan pemrograman fungsional dan imperatif (1986) oleh Gifford dan Lucassen, yang menyebutkan empat jenis kelas efek : Murni, Fungsi, Pengamat dan Prosedur. Jadi, istilah "fungsi murni" berasal dari tulisan ini.

  • PURE adalah referensi yang transparan: tidak menyebabkan efek samping, nilainya tidak dipengaruhi oleh efek samping, dan mengembalikan nilai yang sama setiap kali dievaluasi.

Namun perlu dicatat bahwa Peyton-Jones dan Wadler menyebutkan kekurangan dalam pendekatan ini. Yang perlu diperhatikan, kata mereka, adalah bahasa pemrograman Clean yang menggunakan tipe linier untuk memperkenalkan efek samping dengan cara yang aman (yaitu aman untuk kompiler). Pada dasarnya, thread ini Dunia sebagai variabel dalam semua fungsi terkait I / O, termasuk titik masuk utama .

Dengan itu, dimungkinkan untuk memiliki bahasa fungsional murni yang berinteraksi dengan dunia dan memiliki efek samping (I / O, OS, sistem Windowing, dll), bertentangan dengan sebagian definisi wikipedia Anda. Seseorang dapat mengatakan bahwa Haskell memiliki Bersih sebagai salah satu pengaruhnya; meskipun ia berangkat dari tipe linier dan menggunakan tipe-level konstruk (monad) lain untuk menjamin linieritas, yaitu referensi tunggal setiap saat.

carlosayam
sumber
"Pada dasarnya, utas Dunia sebagai variabel ...". Apakah yang Anda maksud sebenarnya adalah "utas". Apakah ada akun informal ini di web?
babou
Saya menggunakan "threading" sebagai metafora. Artinya, Anda harus meneruskan variabel Dunia dari satu fungsi ke fungsi lainnya. Dan pengetikan linier berarti bahwa variabel Dunia tersebut tidak digunakan lebih dari sekali. Ini menyiratkan, misalnya bahwa untuk membuka file di dalam suatu fungsi yang Anda ingin lakukan (f_handle, world2) = fopen file_name, world(pseudocode) dan panggilan berikutnya harus digunakan world2. Pada intinya program dilihat sebagai operasi di Semesta secara keseluruhan. Dengan kata lain, tidak ada efek samping ketika Anda beroperasi di Semesta :-)
carlosayam
Threading the World, seperti yang Anda katakan, tampaknya menjadi cara standar (seingat saya) untuk berurusan dengan lingkungan dalam semantik denotasional. Jadi kuncinya adalah linearitas. Tapi kemudian, semotika denotasional (DS) seharusnya murni fungsional, tanpa kendala linearitas. Saya kira DS adalah abstraksi matematis dan tidak memiliki keraguan tentang juggling banyak Dunia. Komputasi adalah fisik, dan linearitas memungkinkan evolusi dunia, tetapi hanya satu Dunia yang bisa ada pada satu waktu (yang mungkin mengurutkan evaluasi). Apakah semantik dari 2 program Clean yang dijalankan secara bersamaan :-)?
babou
Apakah kertas Gifford dan Lucassen dapat diakses di web?
babou
Saya mendapat akses melalui Uni.
carlosayam
-1

Definisi Wikipedia adalah kanonik. Dua persyaratan penting adalah:

  • Nilai balik dan perilaku fungsi adalah fungsi deterministik dari argumen yang secara eksplisit diteruskan ke fungsi.

  • Doa fungsi tidak memiliki efek samping yang dapat diamati.

Sebenarnya, D dan gcc seharusnya tidak menggunakan kata "murni" seperti yang mereka lakukan; ini merupakan penyalahgunaan terminologi standar.

DW
sumber