Bagaimana cara kerja bahasa pemrograman fungsional?

Jika bahasa pemrograman fungsional tidak dapat menyimpan status apa pun, bagaimana mereka melakukan hal-hal sederhana seperti membaca input dari pengguna? Bagaimana cara mereka "menyimpan" input (atau menyimpan data apa pun?)

Misalnya: bagaimana hal C sederhana ini diterjemahkan ke bahasa pemrograman fungsional seperti Haskell?

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

(Pertanyaan saya terinspirasi oleh posting yang luar biasa ini: "Eksekusi di Kerajaan Kata Benda" . Membacanya memberi saya pemahaman yang lebih baik tentang apa sebenarnya pemrograman berorientasi objek, bagaimana Java mengimplementasikannya dengan satu cara yang ekstrim, dan bagaimana bahasa pemrograman fungsional adalah kontras.)

Jika bahasa pemrograman fungsional tidak dapat menyimpan status apa pun, bagaimana mereka melakukan beberapa hal sederhana seperti membaca masukan dari pengguna (maksud saya bagaimana mereka "menyimpannya"), atau menyimpan data apa pun?

Saat Anda mengumpulkannya, pemrograman fungsional tidak memiliki status — tetapi itu tidak berarti tidak dapat menyimpan data. Perbedaannya adalah jika saya menulis pernyataan (Haskell) di sepanjang baris

let x = func value 3.14 20 "random"
in ...

Saya jamin bahwa nilai dari xselalu sama di... : tidak ada yang bisa mengubahnya. Demikian pula, jika saya memiliki fungsi f :: String -> Integer(fungsi yang mengambil string dan mengembalikan integer), saya yakin itu ftidak akan mengubah argumennya, atau mengubah variabel global apa pun, atau menulis data ke file, dan seterusnya. Seperti yang dikatakan sepp2k dalam komentar di atas, non-mutabilitas ini sangat membantu untuk penalaran tentang program: Anda menulis fungsi yang melipat, memutar, dan memutilasi data Anda, mengembalikan salinan baru sehingga Anda dapat menyatukannya, dan Anda dapat yakin bahwa tidak ada dari pemanggilan fungsi tersebut dapat melakukan apa saja yang "berbahaya". Anda tahu itu xselalu x, dan Anda tidak perlu khawatir bahwa seseorang menulis x := foo bardi suatu tempat di antara deklarasix dan penggunaannya, karena itu tidak mungkin.

Sekarang, bagaimana jika saya ingin membaca masukan dari pengguna? Seperti yang dikatakan KennyTM, idenya adalah bahwa fungsi tidak murni adalah fungsi murni yang melewati seluruh dunia sebagai argumen, dan mengembalikan hasil dan dunianya. Tentu saja, Anda tidak ingin benar-benar melakukan ini: untuk satu hal, itu sangat kikuk, dan untuk hal lain, apa yang terjadi jika saya menggunakan kembali objek dunia yang sama? Jadi ini entah bagaimana menjadi abstrak. Haskell menanganinya dengan tipe IO:

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

Ini memberitahu kita bahwa maintindakan IO yang tidak menghasilkan apa-apa; menjalankan tindakan ini adalah apa yang dimaksud dengan menjalankan program Haskell. Aturannya adalah bahwa tipe IO tidak pernah bisa lepas dari aksi IO; dalam konteks ini, kami memperkenalkan tindakan itu menggunakan do. Jadi, getLinemengembalikan an IO String, yang dapat dianggap dalam dua cara: pertama, sebagai tindakan yang, ketika dijalankan, menghasilkan string; kedua, sebagai string yang "tercemar" oleh IO karena diperoleh secara tidak murni. Yang pertama lebih tepat, tetapi yang kedua bisa lebih membantu. Yang <-mengambil Stringdari ); ini semua murni (tanpa IO), jadi kami memberinya nama . Kami kemudian dapat menggunakan keduanya dan dalam . Dengan demikian, kami telah menyimpan data tidak murni (dari dalam ) dan data murni (IO String dan menyimpannya dalam str-tapi karena kita berada di suatu tindakan IO, kita harus membungkusnya cadangan, sehingga tidak bisa "melarikan diri". Baris berikutnya mencoba membaca integer ( reads) dan mengambil pertandingan pertama yang berhasil (fst . headlet no = ...nostr...getLinestrlet no = ...).

Mekanisme untuk bekerja dengan IO ini sangat kuat: ini memungkinkan Anda memisahkan bagian algoritmik murni dari program Anda dari sisi interaksi pengguna yang tidak murni, dan menerapkannya pada level tipe. AndaminimumSpanningTreeFungsi tidak mungkin mengubah sesuatu di tempat lain dalam kode Anda, atau menulis pesan kepada pengguna Anda, dan seterusnya. Itu aman.

Ini semua yang perlu Anda ketahui untuk menggunakan IO di Haskell; jika hanya itu yang Anda inginkan, Anda bisa berhenti di sini. Tetapi jika Anda ingin mengerti mengapa itu berhasil, teruslah membaca. (Dan perhatikan bahwa hal ini akan spesifik untuk Haskell — bahasa lain mungkin memilih implementasi yang berbeda.)

Jadi ini mungkin tampak seperti tipuan, entah bagaimana menambahkan ketidakmurnian pada Haskell murni. Tapi ternyata tidak — ternyata kita bisa mengimplementasikan tipe IO seluruhnya dalam Haskell murni (selama kita diberi RealWorld). Idenya adalah ini: tindakan IO IO typesama dengan fungsi RealWorld -> (type, RealWorld), yang mengambil dunia nyata dan mengembalikan baik objek bertipe typedan yang dimodifikasi RealWorld. Kami kemudian mendefinisikan beberapa fungsi sehingga kami dapat menggunakan tipe ini tanpa menjadi gila:

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

Yang pertama memungkinkan kita untuk berbicara tentang tindakan IO yang tidak melakukan apa-apa: return 3merupakan tindakan IO yang tidak menanyakan dunia nyata dan hanya kembali 3. The >>=operator, diucapkan "mengikat", memungkinkan kita untuk menjalankan tindakan IO. Ini mengekstrak nilai dari tindakan IO, meneruskannya dan dunia nyata melalui fungsi, dan mengembalikan tindakan IO yang dihasilkan. Perhatikan bahwa >>=menegakkan aturan kami bahwa hasil tindakan IO tidak pernah diizinkan untuk lolos.

Kami kemudian dapat mengubah hal di atas mainmenjadi kumpulan aplikasi fungsi biasa berikut:

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

Lompatan waktu proses Haskell dimulai maindengan yang awal RealWorld, dan kami siap! Semuanya murni, hanya memiliki sintaksis yang mewah.

[ Sunting: Seperti yang ditunjukkan @Conal , ini sebenarnya bukan yang digunakan Haskell untuk melakukan IO. Model ini rusak jika Anda menambahkan konkurensi, atau memang cara apa pun bagi dunia untuk berubah di tengah tindakan IO, jadi Haskell tidak mungkin menggunakan model ini. Ini akurat hanya untuk komputasi sekuensial. Jadi, mungkin IO Haskell sedikit mengelak; bahkan jika tidak, itu pasti tidak se-elegan ini. Berdasarkan pengamatan @ Conal, lihat apa yang dikatakan Simon Peyton-Jones dalam Tackling the Awkward Squad [pdf] , bagian 3.1; ia menyajikan apa yang mungkin menjadi model alternatif di sepanjang garis ini, tetapi kemudian menjatuhkannya karena kerumitannya dan mengambil arah yang berbeda.]

Sekali lagi, ini menjelaskan (cukup banyak) bagaimana IO, dan mutabilitas secara umum, bekerja di Haskell; jika ini yang ingin Anda ketahui, Anda dapat berhenti membaca di sini. Jika Anda menginginkan satu dosis teori terakhir, teruslah membaca — tetapi ingat, pada titik ini, kami telah melangkah sangat jauh dari pertanyaan Anda!

Jadi satu hal lagi: ternyata struktur ini — tipe parametrik dengan returndan >>=- sangat umum; itu disebut monad, dando notasi return,, dan >>=bekerja dengan salah satunya. Seperti yang Anda lihat di sini, monad bukanlah sihir; semua yang ajaib adalah doblok berubah menjadi panggilan fungsi. The RealWorldjenis adalah satu-satunya tempat kita melihat sihir apapun. Jenis seperti [], konstruktor daftar, juga monad, dan tidak ada hubungannya dengan kode yang tidak murni.

Anda sekarang tahu (hampir) segalanya tentang konsep monad (kecuali beberapa hukum yang harus dipenuhi dan definisi matematika formal), tetapi Anda kekurangan intuisi. Ada banyak sekali tutorial monad online; Saya suka yang ini , tetapi Anda punya pilihan. Namun, ini mungkin tidak akan membantu Anda ; satu-satunya cara nyata untuk mendapatkan intuisi adalah melalui kombinasi penggunaan dan membaca beberapa tutorial pada waktu yang tepat.

Namun, Anda tidak membutuhkan intuisi itu untuk memahami IO . Memahami monad secara umum sangat penting, tetapi Anda dapat menggunakan IO sekarang. Anda bisa menggunakannya setelah saya menunjukkan mainfungsi pertama . Anda bahkan dapat memperlakukan kode IO seolah-olah itu dalam bahasa yang tidak murni! Tetapi ingatlah bahwa ada representasi fungsional yang mendasarinya: tidak ada yang curang.

(PS: Maaf tentang panjangnya. Saya pergi agak jauh.)

Banyak jawaban bagus di sini, tapi panjang. Saya akan mencoba memberikan jawaban singkat yang membantu:

• Bahasa fungsional meletakkan status di tempat yang sama dengan C: di variabel bernama dan di objek yang dialokasikan di heap. Perbedaannya adalah:

  • Dalam bahasa fungsional, "variabel" mendapatkan nilai awalnya saat masuk ke dalam cakupan (melalui pemanggilan fungsi atau let-binding), dan nilai itu tidak berubah setelahnya . Demikian pula, objek yang dialokasikan di heap segera diinisialisasi dengan nilai dari semua bidangnya, yang tidak berubah setelahnya.

  • "Perubahan status" ditangani tidak dengan memutasi variabel atau objek yang ada, tetapi dengan mengikat variabel baru atau mengalokasikan objek baru.

• IO bekerja dengan tipuan. Perhitungan efek samping yang menghasilkan string dijelaskan oleh fungsi yang menggunakan World sebagai argumen, dan mengembalikan pasangan yang berisi string dan Dunia baru. Dunia mencakup konten semua drive disk, riwayat setiap paket jaringan yang pernah dikirim atau diterima, warna setiap piksel di layar, dan hal-hal seperti itu. Kunci dari trik ini adalah akses ke Dunia dibatasi dengan hati-hati

  • Tidak ada program yang dapat membuat salinan Dunia (di mana Anda akan meletakkannya?)

  • Tidak ada program yang bisa membuang Dunia

  Menggunakan trik ini memungkinkan untuk menjadi satu, Dunia unik yang statusnya berkembang seiring waktu. Sistem run-time bahasa, yaitu tidak ditulis dalam bahasa fungsional, mengimplementasikan penghitungan efek samping dengan memperbarui Dunia unik di tempatnya alih-alih mengembalikan yang baru.

  Trik ini dijelaskan dengan indah oleh Simon Peyton Jones dan Phil Wadler dalam makalah penting mereka "Pemrograman Fungsional Imperatif" .

Saya memutuskan balasan komentar untuk jawaban baru, untuk memberi lebih banyak ruang:

Saya menulis:

Sejauh yang saya tahu, IOstory ( World -> (a,World)) ini adalah mitos ketika diterapkan pada Haskell, karena model tersebut hanya menjelaskan komputasi sekuensial murni, sementara IOtipe Haskell menyertakan konkurensi. Yang saya maksud dengan "urutan murni" adalah bahwa bahkan dunia (alam semesta) tidak diizinkan untuk berubah antara awal dan akhir perhitungan imperatif, selain karena perhitungan itu. Misalnya, saat komputer Anda bekerja keras, otak Anda dll tidak bisa. Konkurensi dapat ditangani oleh sesuatu yang lebih mirip World -> PowerSet [(a,World)], yang memungkinkan nondeterminisme dan interleaving.

Norman menulis:

@Conal: Saya pikir kisah IO menggeneralisasi dengan cukup baik ke nondeterminisme dan interleaving; kalo gw inget kan, ada penjelasan yang lumayan bagus di makalah "Awkward Squad". Tetapi saya tidak tahu tentang makalah yang bagus yang menjelaskan paralelisme yang sebenarnya dengan jelas.

@ Norman: Menggeneralisasi dalam arti apa? Saya menyarankan bahwa model / penjelasan denotasi yang biasanya diberikan,, World -> (a,World)tidak cocok dengan Haskell IOkarena tidak memperhitungkan nondeterminisme dan konkurensi. Mungkin ada model yang lebih kompleks yang cocok, seperti World -> PowerSet [(a,World)], tetapi saya tidak tahu apakah model seperti itu telah berhasil dan ditampilkan memadai & konsisten. Saya pribadi meragukan binatang seperti itu dapat ditemukan, mengingat itu IOdihuni oleh ribuan panggilan API penting yang diimpor oleh FFI. Dan dengan demikian, IOmemenuhi tujuannya:

Masalah terbuka: IOmonad telah menjadi sin- bin Haskell. (Setiap kali kami tidak memahami sesuatu, kami melemparkannya ke monad IO.)

(Dari pembicaraan POPL Simon PJ Mengenakan kemeja rambut Mengenakan kemeja rambut: retrospektif tentang Haskell .)

Dalam Bagian 3.1 dari Menangani Pasukan Canggung , Simon menunjukkan apa yang tidak berhasil type IO a = World -> (a, World), termasuk "Pendekatan tidak berskala dengan baik saat kita menambahkan konkurensi". Dia kemudian menyarankan model alternatif yang mungkin, dan kemudian meninggalkan upaya penjelasan denotasional, berkata

Namun kami malah akan mengadopsi semantik operasional, berdasarkan pendekatan standar untuk semantik dari proses bate.

Kegagalan untuk menemukan model denotasi yang tepat & berguna ini adalah akar dari mengapa saya melihat Haskell IO sebagai penyimpangan dari semangat dan manfaat mendalam dari apa yang kita sebut "pemrograman fungsional", atau yang secara lebih spesifik disebut Peter Landin sebagai "pemrograman denotatif" . Lihat komentar di sini.

Pemrograman fungsional berasal dari lambda Calculus. Jika Anda benar-benar ingin memahami pemrograman Fungsional, lihat http://worrydream.com/AlligatorEggs/

Ini adalah cara yang "menyenangkan" untuk belajar Kalkulus lambda dan membawa Anda ke dunia pemrograman Fungsional yang menarik!

Bagaimana mengetahui Lambda Calculus sangat membantu dalam pemrograman fungsional.

Jadi, Lambda Calculus adalah fondasi untuk banyak bahasa pemrograman dunia nyata seperti Lisp, Scheme, ML, Haskell, ....

Misalkan kita ingin mendeskripsikan sebuah fungsi yang menambahkan tiga ke masukan apa pun untuk melakukannya, kita akan menulis:

plus3 x = succ(succ(succ x)) 

Baca "plus3 adalah fungsi yang, jika diterapkan ke sembarang bilangan x, akan menghasilkan penerus penerus penerus x"

Perhatikan bahwa fungsi yang menambahkan 3 ke angka apapun tidak perlu dinamai plus3; nama "plus3" hanyalah singkatan praktis untuk menamai fungsi ini

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

Perhatikan kami menggunakan simbol lambda untuk suatu fungsi (saya pikir itu terlihat seperti Alligator, saya menebak dari situlah ide untuk telur Alligator berasal)

Simbol lambda adalah Alligator (fungsi) dan x adalah warnanya. Anda juga dapat menganggap x sebagai argumen (fungsi Kalkulus Lambda sebenarnya hanya seandainya memiliki satu argumen) selebihnya Anda dapat menganggapnya sebagai badan fungsi.

Sekarang pertimbangkan abstraksi:

g ≡ λ f. (f (f (succ 0)))

Argumen f digunakan dalam posisi fungsi (dalam panggilan). Kami menyebut ga fungsi tingkat tinggi karena mengambil fungsi lain sebagai masukan. Anda dapat menganggap fungsi lain memanggil f sebagai " telur ". Sekarang dengan mengambil dua fungsi atau " Alligators " yang telah kita buat, kita dapat melakukan sesuatu seperti ini:

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

Jika Anda perhatikan, Anda dapat melihat bahwa λ f Alligator kami memakan λ x Alligator kami dan kemudian λ x Alligator dan mati. Kemudian λ x Alligator kita terlahir kembali di telur Alligator λ f. Kemudian proses berulang dan λ x Alligator di kiri sekarang memakan λ x Alligator lainnya di kanan.

Kemudian Anda dapat menggunakan seperangkat aturan sederhana " Alligator " memakan " Alligators " untuk merancang tata bahasa dan dengan demikian lahirlah bahasa pemrograman Fungsional!

Jadi Anda dapat melihat jika Anda tahu Kalkulus Lambda Anda akan memahami cara kerja Bahasa Fungsional.

Teknik untuk menangani status di Haskell sangat mudah. Dan Anda tidak perlu memahami monad untuk mengatasinya.

Dalam bahasa pemrograman dengan status, Anda biasanya memiliki beberapa nilai yang disimpan di suatu tempat, beberapa kode dijalankan, dan kemudian Anda memiliki nilai baru yang disimpan. Dalam bahasa imperatif, negara bagian ini berada di suatu tempat "di latar belakang". Dalam bahasa fungsional (murni) Anda membuatnya eksplisit, jadi Anda secara eksplisit menulis fungsi yang mengubah status.

Jadi, alih-alih memiliki beberapa status tipe X, Anda menulis fungsi yang memetakan X ke X. Itu saja! Anda beralih dari memikirkan tentang negara bagian menjadi memikirkan tentang operasi apa yang ingin Anda lakukan di negara bagian tersebut. Anda kemudian dapat menyatukan fungsi-fungsi ini dan menggabungkannya dalam berbagai cara untuk membuat keseluruhan program. Tentu saja Anda tidak terbatas hanya memetakan X ke X. Anda dapat menulis fungsi untuk mengambil berbagai kombinasi data sebagai input dan mengembalikan berbagai kombinasi di akhir.

Monad adalah salah satu alat, di antara banyak alat, untuk membantu mengatur ini. Tetapi monad sebenarnya bukanlah solusi untuk masalah tersebut. Solusinya adalah memikirkan transformasi negara, bukan negara.

Ini juga berfungsi dengan I / O. Akibatnya apa yang terjadi adalah ini: alih-alih mendapatkan masukan dari pengguna dengan beberapa padanan langsung scanf, dan menyimpannya di suatu tempat, Anda malah menulis fungsi untuk mengatakan apa yang akan Anda lakukan dengan hasil scanfjika Anda memilikinya, dan kemudian meneruskannya berfungsi untuk I / O API. Itulah tepatnya yang >>=dilakukan saat Anda menggunakan IOmonad di Haskell. Jadi, Anda tidak perlu menyimpan hasil I / O di mana pun - Anda hanya perlu menulis kode yang menyatakan cara Anda ingin mengubahnya.

(Beberapa bahasa fungsional mengizinkan fungsi yang tidak murni.)

Untuk bahasa fungsional murni , interaksi dunia nyata biasanya dimasukkan sebagai salah satu argumen fungsi, seperti ini:

RealWorld pureScanf(RealWorld world, const char* format, ...);

Bahasa yang berbeda memiliki strategi yang berbeda untuk memisahkan dunia dari programmer. Haskell, misalnya, menggunakan monad untuk menyembunyikan worldargumen.

Tetapi bagian murni dari bahasa fungsional itu sendiri sudah lengkap Turing, artinya segala sesuatu yang bisa dilakukan di C juga bisa dilakukan di Haskell. Perbedaan utama dari bahasa imperatif adalah alih-alih mengubah keadaan di tempat:

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

Anda menggabungkan bagian modifikasi ke dalam panggilan fungsi, biasanya mengubah loop menjadi rekursi:

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}

Bahasa fungsional dapat menyelamatkan negara! Mereka biasanya hanya mendorong atau memaksa Anda untuk secara eksplisit melakukannya.

Misalnya, lihat Monad Negara Bagian Haskell .

mungkin berguna, Pemrograman Fungsi bagi kita semua

haskell:

main = do no <- readLn
          print (no + 1)

Anda tentu saja dapat menetapkan sesuatu ke variabel dalam bahasa fungsional. Anda tidak bisa mengubahnya (jadi pada dasarnya semua variabel adalah konstanta dalam bahasa fungsional).