Pemrograman Fungsional, Deklaratif, dan Imperatif [ditutup]

Apa arti istilah pemrograman fungsional, deklaratif, dan imperatif?

Pada saat penulisan ini, jawaban pilihan teratas pada halaman ini tidak tepat dan kacau pada definisi deklaratif vs imperatif, termasuk jawaban yang mengutip Wikipedia. Beberapa jawaban menggabungkan istilah dengan cara yang berbeda.

Lihat juga penjelasan saya tentang mengapa pemrograman spreadsheet bersifat deklaratif, terlepas dari rumus yang memutasi sel.

Juga, beberapa jawaban mengklaim bahwa pemrograman fungsional harus merupakan bagian dari deklaratif. Pada titik itu tergantung jika kita membedakan "fungsi" dari "prosedur". Mari kita menangani imperatif vs deklaratif terlebih dahulu.

Definisi ekspresi deklaratif

Satu- satunya atribut yang mungkin dapat membedakan ekspresi deklaratif dari ekspresi imperatif adalah transparansi referensial (RT) dari sub-ekspresi. Semua atribut lain dibagi di antara kedua jenis ekspresi, atau diturunkan dari RT.

Bahasa deklaratif 100% (yaitu bahasa di mana setiap ekspresi yang mungkin adalah RT) tidak (di antara persyaratan RT lainnya) memungkinkan mutasi nilai yang disimpan, misalnya HTML dan sebagian besar Haskell.

Definisi ekspresi RT

RT sering disebut memiliki "tidak ada efek samping". Istilah efek tidak memiliki definisi yang tepat, sehingga beberapa orang tidak setuju bahwa "tidak ada efek samping" sama dengan RT. RT memiliki definisi yang tepat .

Karena setiap sub-ekspresi secara konseptual adalah pemanggilan fungsi, RT mensyaratkan bahwa implementasi suatu fungsi (yaitu ekspresi di dalam fungsi yang dipanggil) tidak boleh mengakses keadaan yang bisa berubah yang berada di luar fungsi (mengakses keadaan lokal yang bisa berubah adalah diizinkan). Sederhananya, fungsi (implementasi) harus murni .

Definisi fungsi murni

Fungsi murni sering dikatakan tidak memiliki efek samping. Istilah efek tidak memiliki definisi yang tepat, sehingga beberapa orang tidak setuju.

Fungsi murni memiliki atribut berikut.

• satu-satunya keluaran yang dapat diamati adalah nilai pengembalian.
• satu-satunya ketergantungan keluaran adalah argumen.
• argumen sepenuhnya ditentukan sebelum output apa pun dihasilkan.

Ingatlah bahwa RT berlaku untuk ekspresi (yang mencakup panggilan fungsi) dan kemurnian berlaku untuk (implementasi dari) fungsi.

Contoh tidak jelas dari fungsi tidak murni yang membuat ekspresi RT adalah konkurensi, tetapi ini karena kemurnian terputus pada lapisan abstraksi interupsi. Anda tidak perlu tahu ini. Untuk membuat ekspresi RT, Anda memanggil fungsi murni.

Atribut derivatif RT

Atribut lain yang dikutip untuk pemrograman deklaratif, misalnya kutipan dari tahun 1999 yang digunakan oleh Wikipedia, baik berasal dari RT, atau dibagi dengan pemrograman imperatif. Dengan demikian membuktikan bahwa definisi saya yang tepat benar.

Catatan, ketetapan nilai eksternal adalah bagian dari persyaratan untuk RT.

• Bahasa deklaratif tidak memiliki struktur kontrol perulangan, misalnya fordan while, karena karena kekekalan , kondisi loop tidak akan pernah berubah.

• Bahasa deklaratif tidak mengekspresikan aliran kontrol selain urutan fungsi yang disarang (alias dependensi logis), karena karena tidak dapat diubah, pilihan urutan evaluasi lainnya tidak mengubah hasilnya (lihat di bawah).

• Bahasa deklaratif mengekspresikan "langkah" logis (yaitu urutan fungsi panggilan RT bersarang), tetapi apakah setiap panggilan fungsi adalah semantik tingkat yang lebih tinggi (yaitu "apa yang harus dilakukan") bukan merupakan persyaratan pemrograman deklaratif. Perbedaan dari imperatif adalah bahwa karena kekekalan (yaitu lebih umum RT), "langkah-langkah" ini tidak dapat bergantung pada keadaan yang bisa berubah, melainkan hanya urutan relasional dari logika yang diekspresikan (yaitu urutan bersarangnya panggilan fungsi, alias sub-ekspresi ).

  Sebagai contoh, paragraf HTML <p>tidak dapat ditampilkan sampai sub-ekspresi (yaitu tag) dalam paragraf telah dievaluasi. Tidak ada keadaan yang bisa berubah, hanya ketergantungan urutan karena hubungan logis dari hierarki tag (bersarang dari sub-ekspresi, yang merupakan panggilan fungsi bersarang secara analog ).

• Dengan demikian ada atribut turunan dari kekekalan (lebih umum RT), bahwa ekspresi deklaratif, mengungkapkan hanya yang logis hubungan dari bagian-bagian konstituen (yaitu argumen fungsi sub-ekspresi) dan tidak negara bisa berubah hubungan.

Urutan evaluasi

Pilihan urutan evaluasi sub-ekspresi hanya dapat memberikan hasil yang bervariasi ketika salah satu dari panggilan fungsi tidak RT (yaitu fungsi tersebut tidak murni), misalnya beberapa keadaan yang dapat diubah eksternal ke suatu fungsi diakses dalam fungsi.

Sebagai contoh, diberikan beberapa ekspresi bersarang, misalnya f( g(a, b), h(c, d) ), evaluasi bersemangat dan malas argumen fungsi akan memberikan hasil yang sama jika fungsi f, gdan hmurni.

Sedangkan, jika fungsinya f,, gdan htidak murni, maka pilihan urutan evaluasi dapat memberikan hasil yang berbeda.

Catatan, ekspresi bertingkat adalah fungsi yang secara konseptual bersarang, karena operator ekspresi hanyalah panggilan fungsi yang menyamar sebagai awalan unary, postfix unary, atau notasi biner infix.

Tangensial, jika semua pengidentifikasi, misalnya a, b, c, d, yang berubah di mana-mana, negara eksternal untuk program tidak dapat diakses (yaitu I / O), dan tidak ada lapisan abstraksi kerusakan, maka fungsi selalu murni.

Omong-omong, Haskell memiliki sintaks yang berbeda f (g a b) (h c d),.

Rincian pesanan evaluasi

Fungsi adalah transisi status (bukan nilai tersimpan yang dapat berubah) dari input ke output. Untuk komposisi RT panggilan ke fungsi murni , urutan pelaksanaan transisi negara ini adalah independen. Transisi keadaan setiap pemanggilan fungsi tidak tergantung pada yang lain, karena kurangnya efek samping dan prinsip bahwa fungsi RT dapat digantikan oleh nilai yang di-cache . Untuk memperbaiki kesalahpahaman yang populer , komposisi monadik murni selalu bersifat deklaratif dan RT , terlepas dari kenyataan bahwa IOmonad Haskell dapat dikatakan tidak murni dan dengan demikian imperatif mempengaruhi Worldnegara di luar program (tetapi dalam arti peringatan di bawah ini, efek sampingnya) terisolasi).

Evaluasi yang bersemangat berarti argumen fungsi dievaluasi sebelum fungsi dipanggil, dan evaluasi malas berarti argumen tidak dievaluasi sampai (dan jika) mereka diakses di dalam fungsi.

Definisi : parameter fungsi dideklarasikan di situs definisi fungsi , dan argumen fungsi disediakan di situs panggilan fungsi . Ketahui perbedaan antara parameter dan argumen .

Secara konseptual, semua ekspresi yang (komposisi) fungsi panggilan, misalnya konstanta fungsi tanpa input, operator unary adalah fungsi dengan satu input, operator infiks biner adalah fungsi dengan dua input, konstruktor adalah fungsi, dan pernyataan bahkan kontrol (misalnya if, for, while) dapat dimodelkan dengan fungsi. The agar ini argumen fungsi (tidak bingung dengan pesanan panggilan fungsi bersarang) dievaluasi tidak dideklarasikan oleh sintaks, misalnya f( g() )bersemangat bisa mengevaluasi gkemudian fpada ghasil 's atau bisa mengevaluasi fdan hanya malas mengevaluasi gketika hasilnya diperlukan dalam f.

Peringatan, tidak ada bahasa lengkap Turing (yaitu yang memungkinkan rekursi tak terbatas) adalah deklaratif sempurna, misalnya evaluasi malas memperkenalkan memori dan ketidakpastian waktu. Tetapi efek samping ini karena pilihan urutan evaluasi terbatas pada konsumsi memori, waktu eksekusi, latensi, non-terminasi, dan histeresis eksternal sehingga sinkronisasi eksternal.

Pemrograman fungsional

Karena pemrograman deklaratif tidak dapat memiliki loop, maka satu-satunya cara untuk beralih adalah rekursi fungsional. Dalam pengertian inilah pemrograman fungsional terkait dengan pemrograman deklaratif.

Tetapi pemrograman fungsional tidak terbatas pada pemrograman deklaratif . Komposisi fungsional dapat dikontraskan dengan subtyping , terutama berkenaan dengan Masalah Ekspresi , di mana ekstensi dapat dicapai dengan menambahkan subtipe atau dekomposisi fungsional . Perpanjangan bisa merupakan campuran dari kedua metodologi.

Pemrograman fungsional biasanya membuat fungsi objek kelas satu, yang berarti tipe fungsi dapat muncul dalam tata bahasa di mana pun tipe lain mungkin. Hasilnya adalah bahwa fungsi dapat menginput dan beroperasi pada fungsi, sehingga menyediakan pemisahan-of-keprihatinan dengan menekankan komposisi fungsi, yaitu memisahkan ketergantungan antara subkomputasi dari perhitungan deterministik.

Misalnya, alih-alih menulis fungsi terpisah (dan menggunakan rekursi alih-alih loop jika fungsi tersebut juga harus bersifat deklaratif) untuk masing-masing jumlah tak terbatas dari tindakan khusus yang mungkin dapat diterapkan pada setiap elemen koleksi, pemrograman fungsional menggunakan iterasi yang dapat digunakan kembali. fungsi, misalnya map, fold, filter. Fungsi iterasi ini memasukkan fungsi tindakan khusus kelas satu. Fungsi iterasi ini mengulangi koleksi dan memanggil fungsi input aksi khusus untuk setiap elemen. Fungsi tindakan ini lebih ringkas karena tidak perlu lagi berisi pernyataan perulangan untuk mengulang koleksi.

Namun, perhatikan bahwa jika suatu fungsi tidak murni, maka itu benar-benar sebuah prosedur. Kita mungkin dapat berpendapat bahwa pemrograman fungsional yang menggunakan fungsi tidak murni, benar-benar pemrograman prosedural. Jadi jika kita setuju bahwa ekspresi deklaratif adalah RT, maka kita dapat mengatakan bahwa pemrograman prosedural bukan pemrograman deklaratif, dan dengan demikian kita dapat berdebat bahwa pemrograman fungsional selalu RT dan harus menjadi bagian dari pemrograman deklaratif.

Paralelisme

Komposisi fungsional ini dengan fungsi kelas satu dapat mengekspresikan kedalaman paralelisme dengan memisahkan fungsi independen.

Prinsip Brent: perhitungan dengan kerja w dan kedalaman d dapat diimplementasikan dalam PRAM prosesor-p dalam waktu O (maks (w / p, d)).

Baik konkurensi dan paralelisme juga membutuhkan pemrograman deklaratif , yaitu immutabilitas dan RT.

Jadi dari mana asumsi berbahaya yang berasal dari Parallelism == Concurrency? Ini adalah konsekuensi alami dari bahasa dengan efek samping: ketika bahasa Anda memiliki efek samping di mana-mana, maka setiap kali Anda mencoba untuk melakukan lebih dari satu hal pada suatu waktu Anda pada dasarnya memiliki non-determinisme yang disebabkan oleh interleaving efek dari setiap operasi . Jadi dalam bahasa efek samping, satu-satunya cara untuk mendapatkan paralelisme adalah konkurensi; Oleh karena itu tidak mengherankan bahwa kita sering melihat keduanya tergabung.

Urutan evaluasi FP

Perhatikan urutan evaluasi juga berdampak pada terminasi dan efek samping kinerja komposisi fungsional.

Eager (CBV) dan lazy (CBN) adalah duel kategoris [ 10 ], karena mereka memiliki urutan evaluasi terbalik, yaitu apakah fungsi luar atau dalam masing-masing dievaluasi terlebih dahulu. Bayangkan pohon terbalik, lalu bersemangat mengevaluasi dari cabang fungsi pohon menaiki hierarki cabang ke batang fungsi tingkat atas; sedangkan, malas mengevaluasi dari bagasi ke ujung cabang. Eager tidak memiliki produk konjungtif ("dan", a / k / a "produk" kategoris) dan lazy tidak memiliki coproducts disjungtif ("atau", a / k / a "jumlah" kategoris) [ 11 ].

Performa

• Bersemangat

  Seperti halnya non-terminasi, eager terlalu bersemangat dengan komposisi fungsional konjungtif, yaitu struktur kontrol komposisi tidak melakukan pekerjaan yang tidak perlu dilakukan dengan malas. Untuk contoh , bersemangat bersemangat dan tidak perlu memetakan seluruh daftar ke boolean, ketika terdiri dengan lipatan yang berakhir pada elemen pertama benar.

  Pekerjaan yang tidak perlu ini adalah penyebab "hingga" faktor tambahan yang diklaim dalam kompleksitas waktu berurutan antara bersemangat dan malas, keduanya dengan fungsi murni. Solusinya adalah dengan menggunakan functors (misalnya daftar) dengan konstruktor malas (yaitu bersemangat dengan produk-produk malas opsional), karena dengan keinginan ketidaksamaan keinginan berasal dari fungsi dalam. Ini karena produk merupakan tipe konstruktif, yaitu tipe induktif dengan aljabar awal pada fixpoint awal [ 11 ]

• Malas

  Seperti halnya non-terminasi, lazy terlalu malas dengan komposisi fungsional disjungtif, yaitu finalitas coinductive dapat terjadi lebih lambat dari yang diperlukan, menghasilkan kerja yang tidak perlu dan non-determinisme dari keterlambatan yang tidak terjadi dengan bersemangat [ 10 ] [ 11 ] . Contoh finalitas adalah pengecualian kondisi, waktu, non-terminasi, dan runtime. Ini adalah efek samping imperatif, tetapi bahkan dalam bahasa deklaratif murni (misalnya Haskell), terdapat keadaan dalam imperatif IO monad (catatan: tidak semua monad penting!) Tersirat dalam alokasi ruang, dan waktu adalah keadaan relatif terhadap imperatif dunia nyata. Menggunakan lazy bahkan dengan coproducts bersemangat ingin kebocoran "kemalasan" ke dalam coproducts batin, karena dengan malas kemalasan yang salah berasal dari fungsi luar(lihat contoh di bagian Non-terminasi, di mana == adalah fungsi operator biner luar). Ini karena coproducts terikat oleh finalitas, yaitu tipe koinduktif dengan aljabar akhir pada objek akhir [ 11 ].

  Malas menyebabkan ketidakpastian dalam desain dan debugging fungsi untuk latensi dan ruang, debugging yang mungkin di luar kemampuan mayoritas programmer, karena disonansi antara hirarki fungsi yang dinyatakan dan urutan-evaluasi evaluasi runtime. Fungsi murni malas dievaluasi dengan bersemangat, berpotensi dapat memperkenalkan non-terminasi yang sebelumnya tidak terlihat saat runtime. Sebaliknya, fungsi murni yang dievaluasi dengan malas, berpotensi dapat memperkenalkan ruang yang sebelumnya tidak terlihat dan ketidakpastian latensi saat runtime.

Non-pemutusan hubungan kerja

Pada waktu kompilasi, karena masalah Hentikan dan rekursi timbal balik dalam bahasa lengkap Turing, fungsi umumnya tidak dapat dijamin untuk berakhir.

• Bersemangat

  Dengan bersemangat tetapi tidak malas, untuk kata Head"dan" Tail, jika salah satu Headatau Tailtidak berakhir, maka masing-masing baik List( Head(), Tail() ).tail == Tail()atau List( Head(), Tail() ).head == Head()tidak benar karena sisi kiri tidak, dan sisi kanan tidak, berakhir.

  Padahal, dengan malas kedua belah pihak berakhir. Karena itu, eager terlalu bersemangat dengan produk-produk penghubung, dan non-terminate (termasuk pengecualian runtime) dalam kasus-kasus di mana itu tidak diperlukan.

• Malas

  Dengan malas tetapi tidak bersemangat, untuk disjungsi 1"atau" 2, jika ftidak berakhir, maka List( f ? 1 : 2, 3 ).tail == (f ? List( 1, 3 ) : List( 2, 3 )).tailitu tidak benar karena sisi kiri berakhir, dan sisi kanan tidak.

  Padahal, dengan penuh semangat kedua belah pihak tidak berakhir sehingga ujian kesetaraan tidak pernah tercapai. Jadi lazy terlalu malas dengan coproduct disjunctive, dan dalam kasus-kasus gagal untuk mengakhiri (termasuk pengecualian runtime) setelah melakukan lebih banyak pekerjaan daripada yang ingin dilakukan.

[ 10 ] Kelanjutan Deklaratif dan Dualitas Kategorikal, Filinski, bagian 2.5.4 Perbandingan CBV dan CBN, dan 3.6.1 CBV dan CBN di SCL.

[ 11 ] Kelanjutan Deklaratif dan Dualitas Kategorikal, Filinski, bagian 2.2.1 Produk dan coproducts, 2.2.2 Terminal dan objek awal, 2.5.2 CBV dengan produk malas, dan 2.5.3 CBN dengan coproduct yang bersemangat.

Sebenarnya tidak ada definisi objektif yang tidak ambigu untuk ini. Inilah cara saya mendefinisikannya:

Imperatif - Fokusnya adalah pada langkah apa yang harus diambil komputer daripada apa yang akan dilakukan komputer (mis. C, C ++, Java).

Deklaratif - Fokusnya adalah pada apa yang harus dilakukan komputer daripada bagaimana melakukannya (mis. SQL).

Fungsional - bagian dari bahasa deklaratif yang memiliki fokus berat pada rekursi

imperatif dan deklaratif menggambarkan dua gaya pemrograman yang berlawanan. imperatif adalah pendekatan "resep langkah demi langkah" tradisional sementara deklaratif lebih "ini yang saya inginkan, sekarang Anda mencari cara untuk melakukannya".

dua pendekatan ini terjadi sepanjang pemrograman - bahkan dengan bahasa yang sama dan program yang sama. umumnya pendekatan deklaratif dianggap lebih disukai, karena membebaskan programmer dari harus menentukan begitu banyak detail, sementara juga memiliki lebih sedikit kesempatan untuk bug (jika Anda menggambarkan hasil yang Anda inginkan, dan beberapa proses otomatis yang teruji dapat bekerja mundur dari itu ke tentukan langkah-langkahnya maka Anda mungkin berharap bahwa hal-hal lebih dapat diandalkan daripada harus menentukan setiap langkah dengan tangan).

di sisi lain, pendekatan imperatif memberi Anda lebih banyak kontrol level rendah - itu adalah "pendekatan micromanager" untuk pemrograman. dan itu dapat memungkinkan programmer untuk mengeksploitasi pengetahuan tentang masalah untuk memberikan jawaban yang lebih efisien. jadi bukan hal yang aneh jika beberapa bagian dari program ditulis dengan gaya yang lebih deklaratif, tetapi untuk bagian yang sangat cepat menjadi lebih penting.

seperti yang Anda bayangkan, bahasa yang Anda gunakan untuk menulis sebuah program memengaruhi seberapa deklaratif Anda - bahasa yang memiliki "kecerdasan" bawaan untuk mengetahui apa yang harus dilakukan mengingat deskripsi hasilnya akan memungkinkan deklaratif yang jauh lebih banyak pendekatan dari satu di mana programmer harus terlebih dahulu menambahkan kecerdasan semacam itu dengan kode imperatif sebelum dapat membangun lapisan yang lebih deklaratif di atas. jadi, misalnya, bahasa seperti prolog dianggap sangat deklaratif karena memiliki, built-in, proses yang mencari jawaban.

sejauh ini, Anda akan melihat bahwa saya belum menyebutkan pemrograman fungsional . itu karena itu istilah yang maknanya tidak terkait langsung dengan dua lainnya. pada pemrograman fungsionalnya yang paling sederhana berarti Anda menggunakan fungsi. khususnya, bahwa Anda menggunakan bahasa yang mendukung fungsi sebagai "nilai kelas pertama" - itu berarti Anda tidak hanya dapat menulis fungsi, tetapi Anda dapat menulis fungsi yang menulis fungsi (yang menulis fungsi yang ...), dan meneruskan fungsi ke fungsi. singkatnya - bahwa fungsinya sefleksibel dan umum seperti hal-hal seperti string dan angka.

mungkin tampak aneh, kemudian, fungsional, imperatif dan deklaratif sering disebutkan bersama. alasan untuk ini adalah konsekuensi dari mengambil ide pemrograman fungsional "secara ekstrim". sebuah fungsi, dalam arti paling murni, adalah sesuatu dari matematika - semacam "kotak hitam" yang mengambil beberapa input dan selalu memberikan hasil yang sama. dan perilaku semacam itu tidak memerlukan penyimpanan variabel yang berubah. jadi jika Anda merancang bahasa pemrograman yang tujuannya adalah untuk mengimplementasikan ide pemrograman fungsional yang sangat murni dan dipengaruhi secara matematis, Anda akhirnya menolak, sebagian besar, gagasan nilai yang dapat berubah (dalam arti teknis tertentu, terbatas, teknis).

dan jika Anda melakukan itu - jika Anda membatasi bagaimana variabel dapat berubah - maka hampir secara tidak sengaja Anda akhirnya memaksa programmer untuk menulis program yang lebih deklaratif, karena sebagian besar pemrograman imperatif menggambarkan bagaimana variabel berubah, dan Anda tidak bisa lagi lakukan itu! Jadi ternyata pemrograman fungsional - khususnya pemrograman dalam bahasa fungsional - cenderung memberikan kode deklaratif yang lebih banyak.

untuk meringkas, maka:

• imperatif dan deklaratif adalah dua gaya pemrograman yang berlawanan (nama yang sama digunakan untuk bahasa pemrograman yang mendorong gaya tersebut)

• pemrograman fungsional adalah gaya pemrograman di mana fungsi menjadi sangat penting dan, sebagai akibatnya, perubahan nilai menjadi kurang penting. kemampuan terbatas untuk menentukan perubahan nilai memaksa gaya yang lebih deklaratif.

jadi "pemrograman fungsional" sering digambarkan sebagai "deklaratif".

Pendeknya:

Sebuah bahasa imperatif specfies serangkaian instruksi bahwa mengeksekusi komputer dalam urutan (melakukan ini, maka lakukan itu).

Sebuah bahasa deklaratif menyatakan seperangkat aturan tentang apa output harus hasil dari yang input (misalnya. Jika Anda memiliki A, maka hasilnya adalah B). Mesin akan menerapkan aturan ini pada input, dan memberikan output.

Sebuah bahasa fungsional menyatakan satu set fungsi matematika / logika yang menentukan bagaimana masukan diterjemahkan ke output. misalnya. f (y) = y * y. itu adalah jenis bahasa deklaratif.

Imperatif: bagaimana mencapai tujuan kita

   Take the next customer from a list.
   If the customer lives in Spain, show their details.
   If there are more customers in the list, go to the beginning

Deklaratif: apa yang ingin kita capai

   Show customer details of every customer living in Spain

Pemrograman Imperatif berarti gaya pemrograman apa pun di mana program Anda disusun berdasarkan instruksi yang menjelaskan bagaimana operasi yang dilakukan oleh komputer akan terjadi .

Pemrograman Deklaratif berarti gaya pemrograman apa pun di mana program Anda adalah deskripsi masalah atau solusinya - tetapi tidak secara eksplisit menyatakan bagaimana pekerjaan akan dilakukan .

Pemrograman Fungsional adalah pemrograman dengan mengevaluasi fungsi dan fungsi fungsi ... Seperti pemrograman fungsional (yang didefinisikan secara ketat) berarti pemrograman dengan mendefinisikan fungsi matematika bebas efek samping sehingga merupakan bentuk pemrograman deklaratif tetapi bukan satu-satunya jenis pemrograman deklaratif .

Pemrograman Logika (misalnya dalam Prolog) adalah bentuk lain dari pemrograman deklaratif. Ini melibatkan komputasi dengan memutuskan apakah pernyataan logis itu benar (atau apakah itu dapat dipenuhi). Program ini biasanya serangkaian fakta dan aturan - yaitu deskripsi daripada serangkaian instruksi.

Term Rewriting (misalnya CASL) adalah bentuk lain dari pemrograman deklaratif. Ini melibatkan transformasi simbolik dari istilah aljabar. Ini benar-benar berbeda dari pemrograman logika dan pemrograman fungsional.

sangat penting - expressions menggambarkan urutan tindakan yang harus dilakukan (asosiatif)

deklaratif - ekspresi adalah deklarasi yang berkontribusi terhadap perilaku program (asosiatif, komutatif, idempoten, monotonik)

fungsional - ekspresi memiliki nilai hanya sebagai efek; semantik mendukung penalaran yang sama

Karena saya menulis jawaban saya sebelumnya, saya telah merumuskan definisi baru dari properti deklaratif yang dikutip di bawah ini. Saya juga mendefinisikan pemrograman imperatif sebagai properti ganda.

Definisi ini lebih unggul daripada yang saya berikan dalam jawaban saya sebelumnya, karena ini ringkas dan lebih umum. Tetapi mungkin lebih sulit untuk grok, karena implikasi teorema ketidaklengkapan yang berlaku untuk pemrograman dan kehidupan secara umum sulit bagi manusia untuk membungkus pikiran mereka.

Penjelasan yang dikutip dari definisi tersebut membahas tentang peran yang dimainkan oleh pemrograman fungsional murni dalam pemrograman deklaratif.

Semua jenis pemrograman yang eksotik cocok dengan taksonomi deklaratif versus imperatif berikut, karena definisi berikut mengklaim bahwa keduanya adalah dual.

Deklaratif vs. Imperatif

Properti deklaratif aneh, tumpul, dan sulit ditangkap dalam definisi yang tepat secara teknis yang tetap umum dan tidak ambigu, karena itu adalah gagasan naif bahwa kita dapat mendeklarasikan makna (alias semantik) dari program tanpa menimbulkan efek samping yang tidak diinginkan. Ada ketegangan yang melekat antara ekspresi makna dan penghindaran efek yang tidak diinginkan, dan ketegangan ini sebenarnya berasal dari teorema ketidaklengkapan. pemrograman dan alam semesta kita.

Itu terlalu menyederhanakan, secara teknis tidak tepat, dan sering ambigu untuk mendefinisikan deklaratif sebagai " apa yang harus dilakukan " dan imperatif sebagai " bagaimana melakukan " . Kasus ambigu adalah " apa " adalah " bagaimana " dalam suatu program yang menghasilkan suatu program - kompiler.

Jelaslah bahwa rekursi tak terbatas yang menjadikan bahasa Turing lengkap , juga analog dengan semantik — tidak hanya dalam struktur evaluasi sintaksis (alias semantik operasional). Ini secara logis adalah contoh analog dengan teorema Gödel— “ sistem aksioma lengkap juga tidak konsisten ”. Renungkan keanehan kontradiktif dari kutipan itu! Ini juga merupakan contoh yang menunjukkan bagaimana ekspresi semantik tidak memiliki dibuktikan sebuah terikat, sehingga kita tidak dapat membuktikan 2 bahwa program (dan analog semantik) berhenti alias teorema terputus-putus.

Teorema ketidaklengkapan berasal dari sifat dasar alam semesta kita, yang sebagaimana dinyatakan dalam Hukum Kedua Termodinamika adalah " entropi (alias # kemungkinan independen) cenderung mencapai maksimum selamanya ". Pengkodean dan desain suatu program tidak pernah selesai — itu hidup! —Karena ia berupaya memenuhi kebutuhan dunia nyata, dan semantik dunia nyata selalu berubah dan cenderung ke lebih banyak kemungkinan. Manusia tidak pernah berhenti menemukan hal-hal baru (termasuk kesalahan dalam program ;-).

Untuk secara tepat dan teknis menangkap gagasan yang diinginkan tersebut di dalam alam semesta yang aneh ini yang tidak memiliki keunggulan (merenungkan bahwa! Tidak ada "di luar" alam semesta kita), memerlukan definisi yang singkat tapi jelas-tidak-sederhana yang akan terdengar salah sampai dijelaskan dalam.

Definisi:

---

Properti deklaratif adalah tempat hanya ada satu set pernyataan yang mungkin yang dapat mengekspresikan setiap semantik modular tertentu.

Properti imperatif 3 adalah dual, di mana semantik tidak konsisten di bawah komposisi dan / atau dapat dinyatakan dengan variasi set pernyataan.

---

Definisi deklaratif ini khas lokal dalam lingkup semantik, artinya mengharuskan semantik modular mempertahankan makna konsistennya di mana pun dan bagaimana ia dipakai dan digunakan dalam lingkup global . Dengan demikian setiap semantik modular deklaratif harus secara intrinsik ortogonal untuk semua kemungkinan yang lain - dan bukan tidak mungkin (karena teorema ketidaklengkapan) algoritma global atau model untuk menyaksikan konsistensi, yang juga merupakan titik " Lebih Banyak Tidak Selalu Lebih Baik " oleh Robert Harper, Profesor Ilmu Komputer di Universitas Carnegie Mellon, salah satu desainer Standar ML.

Contoh semantik deklaratif modular ini mencakup fungsiApplicative kategori teori misalnya , pengetikan nominal, ruang nama, bidang isian, dan wrt ke tingkat operasional semantik kemudian pemrograman fungsional murni.

Dengan demikian bahasa deklaratif yang dirancang dengan baik dapat lebih jelas mengekspresikan makna , meskipun dengan beberapa kehilangan generalitas dalam apa yang dapat diekspresikan, namun keuntungan dalam apa yang dapat diekspresikan dengan konsistensi intrinsik.

Contoh definisi yang disebutkan di atas adalah sekumpulan formula dalam sel program spreadsheet — yang tidak diharapkan memberikan makna yang sama ketika dipindahkan ke sel kolom dan baris yang berbeda, yaitu pengidentifikasi sel diubah. Pengidentifikasi sel adalah bagian dari dan tidak berlebihan untuk makna yang dimaksudkan. Jadi setiap hasil spreadsheet adalah unik wrt ke pengidentifikasi sel dalam satu set rumus. Semantik modular yang konsisten dalam hal ini adalah penggunaan pengidentifikasi sel sebagai input dan output fungsi murni untuk formula sel (lihat di bawah).

Hyper Text Markup Language alias HTML — bahasa untuk halaman web statis — adalah contoh bahasa deklaratif yang sangat (tetapi tidak sempurna 3 ) yang (setidaknya sebelum HTML 5) tidak memiliki kemampuan untuk mengekspresikan perilaku dinamis. HTML mungkin bahasa yang paling mudah dipelajari. Untuk perilaku dinamis, bahasa skrip imperatif seperti JavaScript biasanya dikombinasikan dengan HTML. HTML tanpa JavaScript cocok dengan definisi deklaratif karena setiap jenis nominal (yaitu tag) mempertahankan makna yang konsisten di bawah komposisi dalam aturan sintaksis.

Definisi bersaing untuk deklaratif adalah sifat komutatif dan idempoten dari pernyataan semantik, yaitu bahwa pernyataan dapat disusun ulang dan digandakan tanpa mengubah artinya. Misalnya, pernyataan yang menetapkan nilai ke bidang bernama dapat disusun ulang dan diduplikasi tanpa mengubah arti program, jika nama-nama tersebut adalah modular wrt untuk urutan apa pun yang tersirat. Nama kadang-kadang menyiratkan pesanan, misalnya pengidentifikasi sel menyertakan posisi kolom dan baris mereka — memindahkan total pada spreadsheet mengubah artinya. Jika tidak, properti ini secara implisit memerlukan globalkonsistensi semantik. Secara umum tidak mungkin untuk mendesain semantik pernyataan sehingga mereka tetap konsisten jika dipesan secara acak atau digandakan, karena pesanan dan duplikasi bersifat intrinsik dengan semantik. Misalnya, pernyataan "Foo ada" (atau konstruksi) dan "Foo tidak ada" (dan kehancuran). Jika seseorang menganggap endemik acak yang tidak konsisten dari semantik yang dimaksudkan, maka seseorang menerima definisi ini sebagai cukup umum untuk properti deklaratif. Pada dasarnya definisi ini kosong sebagai definisi umum karena berusaha membuat konsistensi ortogonal untuk semantik, yaitu untuk menentang fakta bahwa alam semesta semantik tidak terikat secara dinamis dan tidak dapat ditangkap dalam paradigma koherensi global .

Membutuhkan sifat komutatif dan idempoten untuk (urutan evaluasi struktural) semantik operasional tingkat rendah mengubah semantik operasional menjadi semantik modular deklaratif terlokalisasi , misalnya pemrograman fungsional murni (termasuk rekursi alih-alih loop imperatif). Kemudian urutan operasional dari detail implementasi tidak berdampak (yaitu menyebar secara global ke) konsistensi semantik tingkat yang lebih tinggi. Misalnya, urutan evaluasi (dan secara teoritis juga duplikasi) formula spreadsheet tidak masalah karena output tidak disalin ke input sampai setelah semua output telah dihitung, yaitu analog dengan fungsi murni.

C, Java, C ++, C #, PHP, dan JavaScript tidak terlalu bersifat deklaratif. Sintaksis Copute dan sintaksis Python lebih deklaratif digabungkan dengan hasil yang dimaksudkan , yaitu semantik sintaksis yang konsisten yang menghilangkan yang asing sehingga orang dapat dengan mudah memahami kode setelah mereka melupakannya. Copute dan Haskell menegakkan determinisme semantik operasional dan mendorong " jangan ulangi diri sendiri " (KERING), karena mereka hanya memungkinkan paradigma fungsional murni.

---

2 Bahkan di mana kita dapat membuktikan semantik dari suatu program, misalnya dengan bahasa Coq, ini terbatas pada semantik yang diekspresikan dalam pengetikan , dan pengetikan tidak pernah dapat menangkap semua semantik dari suatu program — bahkan untuk bahasa yang tidak Turing lengkap, misalnya dengan HTML + CSS dimungkinkan untuk mengekspresikan kombinasi tidak konsisten yang dengan demikian memiliki semantik yang tidak ditentukan.

3 Banyak penjelasan yang salah mengklaim bahwa hanya pemrograman imperatif yang secara sintaksis memerintahkan pernyataan. Saya mengklarifikasi kebingungan ini antara pemrograman imperatif dan fungsional . Misalnya, urutan pernyataan HTML tidak mengurangi konsistensi maknanya.

Sunting: Saya memposting komentar berikut ke blog Robert Harper:

dalam pemrograman fungsional ... rentang variasi variabel adalah tipe

Bergantung pada bagaimana seseorang membedakan fungsional dari pemrograman imperatif, 'tugas' Anda dalam program imperatif juga mungkin memiliki tipe yang menempatkan batasan pada variabilitasnya.

Satu-satunya definisi non-muddled yang saat ini saya hargai untuk pemrograman fungsional adalah a) berfungsi sebagai objek dan tipe kelas, b) preferensi untuk rekursi atas loop, dan / atau c) fungsi murni — yaitu fungsi-fungsi yang tidak memengaruhi semantik yang diinginkan dari program ketika memoize ( _{^{sehingga pemrograman fungsional murni tidak ada dalam semantik denotasional tujuan umum karena dampak semantik operasional, misalnya alokasi memori}} ).

Properti idempoten dari fungsi murni berarti pemanggilan fungsi pada variabelnya dapat diganti dengan nilainya, yang biasanya tidak berlaku untuk argumen prosedur imperatif. Fungsi murni tampaknya merupakan deklaratif untuk transisi status tanpa komposisi antara tipe input dan hasil.

Tetapi komposisi fungsi murni tidak mempertahankan konsistensi seperti itu, karena dimungkinkan untuk memodelkan proses efek samping (keadaan global) dalam bahasa pemrograman fungsional murni, misalnya IOMonad Haskell dan terlebih lagi sama sekali tidak mungkin untuk mencegah melakukan hal tersebut di setiap bahasa pemrograman fungsional murni lengkap Turing.

Seperti yang saya tulis pada tahun 2012 yang nampak seperti konsensus komentar yang serupa di blog Anda baru-baru ini , bahwa pemrograman deklaratif adalah upaya untuk menangkap gagasan bahwa semantik yang dimaksudkan tidak pernah buram. Contoh semantik opak adalah ketergantungan pada urutan, ketergantungan pada penghapusan semantik tingkat tinggi pada lapisan semantik operasional (misalnya gips bukan konversi dan generik reified membatasi semantik level lebih tinggi ), dan ketergantungan pada nilai variabel yang tidak dapat diperiksa (terbukti) benar) oleh bahasa pemrograman.

Jadi saya telah menyimpulkan bahwa hanya bahasa lengkap non-Turing yang bisa bersifat deklaratif.

Dengan demikian satu atribut yang tidak ambigu dan berbeda dari bahasa deklaratif adalah keluarannya dapat dibuktikan mematuhi seperangkat aturan generatif yang dapat dihitung. Misalnya, untuk program HTML spesifik apa pun (mengabaikan perbedaan cara penerjemah berbeda) yang tidak ditulis skrip (mis. Turing tidak lengkap) maka variabilitas outputnya dapat dihitung. Atau lebih tepatnya program HTML adalah fungsi murni dari variabilitasnya. Ditto program spreadsheet adalah fungsi murni dari variabel inputnya.

Jadi sepertinya bagi saya bahwa bahasa deklaratif adalah antitesis dari rekursi tak terbatas , yaitu teorema ketidaklengkapan teorema self-referential kedua Gödel yang tidak dapat dibuktikan.

Lesie Lamport menulis dongeng tentang bagaimana Euclid mungkin bekerja di sekitar teorema ketidaklengkapan Gödel diterapkan pada bukti matematika dalam konteks bahasa pemrograman dengan untuk kesesuaian antara jenis dan logika (korespondensi Curry-Howard, dll).

Pemrograman imperatif: memberi tahu "mesin" bagaimana melakukan sesuatu, dan akibatnya apa yang Anda inginkan akan terjadi.

Pemrograman deklaratif: memberi tahu "mesin" apa yang Anda inginkan terjadi, dan membiarkan komputer mengetahui bagaimana melakukannya.

Contoh imperatif

function makeWidget(options) {
    const element = document.createElement('div');
    element.style.backgroundColor = options.bgColor;
    element.style.width = options.width;
    element.style.height = options.height;
    element.textContent = options.txt;

    return element;
}

Contoh deklaratif

function makeWidget(type, txt) {
    return new Element(type, txt);
}

Catatan: Perbedaannya bukanlah perbedaan atau kompleksitas atau abstraksi. Seperti yang dinyatakan, perbedaannya adalah bagaimana vs apa .

Saat ini, fokus baru: kita membutuhkan klasifikasi lama?

Aspek Imperatif / Deklaratif / Fungsional baik di masa lalu untuk mengklasifikasikan bahasa generik, tetapi di saat ini semua "bahasa besar" (seperti Java, Python, Javascript, dll.) Memiliki beberapa opsi (biasanya kerangka kerja ) untuk diekspresikan dengan "fokus lain" daripada yang utamanya (imperatif biasa), dan untuk mengekspresikan proses paralel, fungsi deklaratif, lambda, dll.

Jadi varian yang baik dari pertanyaan ini adalah "Aspek apa yang baik untuk mengklasifikasikan kerangka kerja hari ini?" ... Aspek penting adalah sesuatu yang dapat kita beri label "gaya pemrograman" ...

Fokus pada penggabungan data dengan algoritma

Contoh yang bagus untuk dijelaskan. Seperti yang dapat Anda baca tentang jQuery di Wikipedia ,

Himpunan fitur inti jQuery - Pilihan elemen DOM, traversal, dan manipulasi -, diaktifkan oleh mesin pemilihnya (...), menciptakan "gaya pemrograman" baru, algoritma peleburan, dan struktur data-DOM-struktur

Jadi jQuery adalah contoh terbaik (populer) dari fokus pada "gaya pemrograman baru" , yang tidak hanya berorientasi objek, adalah " Algoritma peleburan dan struktur data ". jQuery agak reaktif sebagai spreadsheet, tetapi tidak "berorientasi sel", adalah " berorientasi simpul DOM " ... Membandingkan gaya utama dalam konteks ini:

1. Tanpa fusi : dalam semua "bahasa besar", dalam ekspresi Fungsional / Deklaratif / Imperatif, yang biasa adalah "tanpa fusi" data dan algoritme, kecuali oleh beberapa orientasi objek, yang merupakan perpaduan dalam sudut pandang struktur aljabar yang ketat .

2. Beberapa fusi : semua strategi klasik fusi, saat ini memiliki beberapa kerangka kerja yang menggunakannya sebagai paradigma ... aliran data , pemrograman berbasis peristiwa (atau bahasa spesifik domain lama sebagai awk dan XSLT ) ... Seperti pemrograman dengan spreadsheet modern, mereka juga contoh gaya pemrograman reaktif .

3. Fusi besar : adalah "gaya jQuery" ... jQuery adalah bahasa khusus domain yang berfokus pada " algoritma peleburan dan struktur data-DOM ".
   PS: lainnya "bahasa query", sebagai XQuery, SQL (dengan PL sebagai pilihan ekspresi penting) juga data algorith-fusion contoh, tetapi mereka pulau , tanpa fusi dengan modul sistem lainnya ... musim semi , ketika menggunakan find()-variants dan klausa Spesifikasi , adalah contoh fusi yang baik.

Pemrograman deklaratif adalah pemrograman dengan mengekspresikan beberapa logika yang tidak lekang oleh waktu antara input dan output, misalnya, dalam pseudocode, contoh berikut akan bersifat deklaratif:

def factorial(n):
  if n < 2:
    return 1
  else:
    return factorial(n-1)

output = factorial(argvec[0])

Kami hanya mendefinisikan hubungan yang disebut 'faktorial' di sini, dan mendefinisikan hubungan antara output dan input sebagai hubungan itu. Seperti yang harus dibuktikan di sini, tentang bahasa terstruktur apa pun memungkinkan pemrograman deklaratif diperluas. Gagasan sentral dari pemrograman deklaratif adalah data yang tidak dapat diubah, jika Anda menetapkan variabel, Anda hanya melakukannya sekali, dan kemudian tidak pernah lagi. Lainnya, definisi yang lebih ketat mensyaratkan bahwa mungkin tidak ada efek samping sama sekali, bahasa-bahasa ini kadang-kadang disebut 'murni deklaratif'.

Hasil yang sama dalam gaya imperatif adalah:

a = 1
b = argvec[0]
while(b < 2):
  a * b--

output = a

Dalam contoh ini, kami menyatakan tidak ada hubungan logis statis abadi antara input dan output, kami mengubah alamat memori secara manual sampai salah satu dari mereka memegang hasil yang diinginkan. Harus jelas bahwa semua bahasa memungkinkan semantik deklaratif diperluas, tetapi tidak semua mengizinkan imperatif, beberapa bahasa deklaratif 'murni' mengizinkan efek samping dan mutasi sama sekali.

Bahasa deklaratif sering dikatakan untuk menentukan 'apa yang harus dilakukan', sebagai lawan dari 'bagaimana melakukannya', saya pikir itu adalah keliru, program deklaratif masih menentukan bagaimana seseorang harus mendapatkan dari input ke output, tetapi dengan cara lain, hubungan yang Anda tentukan harus dapat dihitung secara efektif (istilah penting, cari jika Anda tidak mengetahuinya). Pendekatan lain adalah pemrograman nondeterministic , yang benar-benar hanya menentukan kondisi apa hasil yang banyak bertemu, sebelum implementasi Anda hanya menghabiskan semua jalur pada coba-coba sampai berhasil.

Bahasa murni deklaratif termasuk Haskell dan Pure Prolog. Skala geser dari satu dan ke yang lain akan menjadi: Prolog Murni, Haskell, OCaml, Skema / Lisp, Python, Javascript, C--, Perl, PHP, C ++, Pascall, C, Fortran, Assembly

Beberapa jawaban yang baik di sini mengenai "jenis" yang dicatat.

Saya mengirimkan beberapa konsep tambahan, lebih "eksotis" yang sering dikaitkan dengan kerumunan pemrograman fungsional:

• Bahasa Spesifik Domain atau Pemrograman DSL : membuat bahasa baru untuk menangani masalah yang dihadapi.
• Meta-Programming : ketika program Anda menulis program lain.
• Pemrograman Evolusi : di mana Anda membangun sistem yang secara terus-menerus memperbaiki dirinya sendiri atau menghasilkan generasi-generasi sub-program yang lebih baik secara berturut-turut.

Saya pikir taksonomi Anda salah. Ada dua jenis yang berlawanan imperatif dan deklaratif. Fungsional hanyalah subtipe deklaratif. BTW, wikipedia menyatakan fakta yang sama.

Singkatnya, semakin gaya pemrograman menekankan Apa (yang harus dilakukan) mengaburkan detail Bagaimana (melakukannya), semakin banyak gaya yang dianggap deklaratif. Yang sebaliknya berlaku untuk imperatif. Pemrograman fungsional dikaitkan dengan gaya deklaratif.