Apakah fungsi murni memoized itu sendiri dianggap murni?

47

Katakanlah fn(x)adalah fungsi murni yang melakukan sesuatu yang mahal, seperti mengembalikan daftar faktor utama x.

Dan katakanlah kita membuat versi memoised dari fungsi yang sama yang disebut memoizedFn(x). Selalu mengembalikan hasil yang sama untuk input yang diberikan, tetapi tetap menyimpan cache pribadi dari hasil sebelumnya untuk meningkatkan kinerja.

Secara formal, memoizedFn(x)dianggap murni?

Atau adakah nama lain atau istilah kualifikasi yang digunakan untuk merujuk fungsi semacam itu dalam diskusi KB? (Yaitu fungsi dengan efek samping yang dapat mempengaruhi kompleksitas komputasi panggilan berikutnya tetapi yang mungkin tidak mempengaruhi nilai kembali.)

terminology pure-function callum
sumber
24
Mungkin itu tidak murni untuk puritan, tetapi "cukup murni" untuk orang pragmatis ;-)
Doc Brown
2
@DocBrown Saya setuju, hanya ingin tahu apakah ada istilah yang lebih formal untuk 'cukup murni'
callum
13
Menjalankan fungsi murni kemungkinan besar akan memodifikasi cache instruksi prosesor, prediksi cabang dll. Tapi itu mungkin "cukup murni" untuk purist juga - atau Anda bisa melupakan fungsi murni sama sekali.
gnasher729
10
@callum Tidak, tidak ada definisi formal "cukup murni". Ketika berdebat tentang kemurnian dan kesetaraan semantik dari dua panggilan "referensial transparan", Anda harus selalu menyatakan semantik mana yang akan Anda terapkan. Pada beberapa detail implementasi tingkat rendah, ia akan selalu rusak dan memiliki efek atau timing memori yang berbeda. Itu sebabnya Anda harus pragmatis: tingkat detail seperti apa yang berguna untuk alasan tentang kode Anda?
Bergi
3
Kemudian demi pragmatisme, saya akan mengatakan bahwa kemurnian tergantung pada apakah Anda menganggap waktu komputasi sebagai bagian dari output atau tidak. funcx(){sleep(cached_time--); return 0;}mengembalikan val yang sama setiap kali, tetapi akan tampil berbeda
Mars

Jawaban:

41

Iya. Versi memo dari fungsi murni juga merupakan fungsi murni.

Yang diperhatikan kemurnian fungsi hanyalah efek yang parameter input pada nilai balik fungsi (melewati input yang sama harus selalu menghasilkan output yang sama) dan efek samping apa pun yang relevan dengan status global (mis. Teks ke terminal atau UI atau jaringan) . Waktu komputasi dan penggunaan memori tambahan tidak relevan dengan fungsi kemurnian.

Tembolok dari fungsi murni hampir tidak terlihat oleh program; bahasa pemrograman fungsional diperbolehkan untuk secara otomatis mengoptimalkan fungsi murni ke versi memoized fungsi jika dapat menentukan bahwa itu akan bermanfaat untuk melakukannya. Dalam praktiknya, secara otomatis menentukan kapan memoisasi bermanfaat sebenarnya adalah masalah yang cukup sulit, tetapi optimasi seperti itu akan valid.

Lie Ryan
sumber
19

Wikipedia mendefinisikan "Fungsi Murni" sebagai fungsi yang memiliki properti berikut:

  • Its nilai kembali adalah sama untuk argumen yang sama (tidak ada variasi dengan variabel lokal statis, variabel non-lokal, argumen referensi bisa berubah atau masukan aliran dari perangkat I / O).

  • Evaluasi tidak memiliki efek samping (tidak ada mutasi variabel statis lokal, variabel non-lokal, argumen referensi yang dapat diubah atau aliran I / O).

Akibatnya, fungsi murni mengembalikan output yang sama dengan input yang sama, dan tidak memengaruhi apa pun di luar fungsi tersebut. Untuk tujuan kemurnian, tidak masalah bagaimana fungsi menghitung nilai kembalinya, asalkan mengembalikan output yang sama dengan input yang sama.

Bahasa murni yang berfungsi seperti Haskell secara rutin menggunakan memoisasi untuk mempercepat suatu fungsi dengan menyimpan hasil yang sebelumnya dihitung.

Robert Harvey
sumber
16
Saya mungkin melewatkan sesuatu, tetapi bagaimana Anda akan menyimpan cache tanpa efek samping?
val
1
Dengan menyimpannya di dalam fungsi.
Robert Harvey
4
"tidak ada mutasi variabel statis lokal" tampaknya mengecualikan variabel lokal persisten antara panggilan juga.
val
3
Ini sebenarnya tidak menjawab pertanyaan, bahkan jika Anda tampaknya menyiratkan bahwa ya, itu murni.
Mars
6
@val Anda benar: kondisi ini perlu sedikit rileks. Memo yang berfungsi murni yang ia maksudkan tidak memiliki mutasi yang terlihat dari data statis apa pun. Apa yang terjadi adalah bahwa hasilnya kemudian dihitung dan dihafal pertama kali fungsi dipanggil, dan mengembalikan nilai yang sama setiap kali dipanggil. Banyak bahasa memiliki ungkapan untuk itu: static constvariabel lokal dalam C ++ (tetapi bukan C), atau struktur data yang dievaluasi malas di Haskell. Ada satu syarat lagi yang Anda butuhkan: inisialisasi harus aman-utas.
Davislor
7

Ya, fungsi memoized murni biasanya disebut sebagai pure. Ini sangat umum dalam bahasa-bahasa seperti Haskell, di mana hasil memoise, dievaluasi malas, tidak berubah adalah fitur bawaan.

Ada satu peringatan penting: fungsi memoizing harus aman dari thread, atau Anda mungkin akan mendapatkan kondisi balapan ketika dua thread mencoba untuk memanggilnya.

Salah satu contoh ilmuwan komputer yang menggunakan istilah "murni fungsional" dengan cara ini adalah posting blog ini oleh Conal Elliott tentang memoisasi otomatis:

Mungkin secara mengejutkan, memoisasi dapat diimplementasikan secara sederhana dan murni secara fungsional dalam bahasa fungsional yang malas.

Ada banyak contoh dalam literatur peer-review, dan telah berlangsung selama beberapa dekade. Sebagai contoh, makalah ini dari tahun 1995, "Menggunakan Memoisasi Otomatis sebagai Alat Rekayasa Perangkat Lunak dalam Sistem AI Dunia Nyata," menggunakan bahasa yang sangat mirip di bagian 5.2 untuk menggambarkan apa yang sekarang kita sebut sebagai fungsi murni:

Memoisasi hanya berfungsi untuk fungsi yang sebenarnya, bukan prosedur. Yaitu, jika hasil suatu fungsi tidak sepenuhnya dan ditentukan secara deterministik oleh parameter inputnya, menggunakan memoisasi akan memberikan hasil yang salah. Jumlah fungsi yang dapat di-memoize dengan sukses akan ditingkatkan dengan mendorong penggunaan gaya pemrograman fungsional di seluruh sistem.

Beberapa bahasa imperatif memiliki idiom serupa. Misalnya, static constvariabel dalam C ++ diinisialisasi hanya sekali, sebelum nilainya digunakan, dan tidak pernah bermutasi.

Davislor
sumber
3

Tergantung bagaimana Anda melakukannya.

Biasanya orang ingin menulis memo dengan mematikan semacam kamus cache. Ini memiliki semua masalah yang terkait dengan mutasi yang tidak murni, seperti harus khawatir tentang konkurensi, khawatir tentang cache yang tumbuh terlalu besar, dll.

Namun, Anda dapat memo tanpa mutasi memori yang tidak murni. Salah satu contoh adalah dalam jawaban ini , di mana saya melacak nilai-nilai yang di-memo secara eksternal melalui lengthsargumen.

Dalam tautan yang diberikan Robert Harvey , evaluasi malas digunakan untuk menghindari efek samping.

Teknik lain yang kadang-kadang terlihat adalah menandai memoisasi secara eksplisit sebagai efek samping yang tidak murni dalam konteks suatu IOtipe, seperti dengan fungsi memoisasi efek kucing .

Yang terakhir ini memunculkan poin bahwa kadang-kadang tujuannya hanya merangkum mutasi daripada menghilangkannya. Sebagian besar programmer fungsional menganggapnya "cukup murni" untuk membuat pengotor eksplisit dan dienkapsulasi.

Jika Anda ingin istilah untuk membedakannya dari fungsi yang benar-benar murni, saya pikir itu cukup dengan hanya mengatakan "memoized dengan kamus yang bisa diubah." Itu membuat orang tahu bagaimana menggunakannya dengan aman.

Karl Bielefeldt
sumber
Saya tidak berpikir salah satu solusi yang lebih murni memecahkan masalah di atas: Meskipun Anda kehilangan kekhawatiran tentang konkurensi, Anda juga kehilangan peluang untuk dua panggilan bersamaan seperti collatz(100)dan collatz(200)untuk bekerja sama. Dan IIUIC, masalah dengan cache tumbuh terlalu besar tetap (meskipun Haskell mungkin punya beberapa trik bagus untuk ini?).
maaartinus
Catatan: IOmurni. Semua metode yang tidak murni IOdan Kucing dinamai unsafe. Async.memoizejuga murni, jadi kita tidak harus puas dengan "cukup murni" :)
Samuel
2

Biasanya, fungsi yang mengembalikan daftar tidak murni sama sekali karena memerlukan alokasi penyimpanan dan dengan demikian dapat gagal (misalnya dengan melemparkan pengecualian, yang tidak murni). Bahasa yang memiliki tipe nilai dan dapat mewakili daftar sebagai tipe nilai ukuran-terikat mungkin tidak memiliki masalah ini. Karena alasan ini, teladan Anda mungkin tidak murni.

Secara umum, jika memoisasi dapat dilakukan dengan cara yang bebas kesalahan-kasus (mis. Dengan memiliki penyimpanan yang dialokasikan secara statis untuk hasil memo, dan sinkronisasi internal untuk mengontrol akses ke mereka jika bahasa mengakui utas), masuk akal untuk mempertimbangkan fungsi seperti itu murni.

R ..
sumber
0

Anda dapat menerapkan memoisasi tanpa efek samping menggunakan monad negara .

[State monad] pada dasarnya adalah fungsi S => (S, A), di mana S adalah tipe yang mewakili negara Anda dan A adalah hasil fungsi yang dihasilkan - Negara Kucing .

Dalam kasus Anda negara akan menjadi nilai memoized atau tidak sama sekali (yaitu Haskell Maybeatau Scala Option[A]). Jika nilai memoized hadir maka dikembalikan sebagai A, jika Atidak dihitung dan dikembalikan sebagai keadaan transisi dan hasilnya.

Samuel
sumber