bagaimana mengelola bahasa pemrograman fungsional murni tanpa pernyataan tugas?

Ketika membaca SICP yang terkenal itu, saya mendapati para penulis tampaknya agak enggan untuk memperkenalkan pernyataan penugasan kepada Skema di Bab 3. Saya membaca teks dan memahami mengapa mereka merasa begitu.

Karena Skema adalah bahasa pemrograman fungsional pertama yang pernah saya ketahui, saya agak terkejut bahwa ada beberapa bahasa pemrograman fungsional (bukan Skema tentu saja) yang dapat dilakukan tanpa tugas.

Mari gunakan contoh yang ditawarkan buku, bank accountcontoh. Jika tidak ada pernyataan tugas, bagaimana ini bisa dilakukan? Bagaimana mengubah balancevariabel? Saya bertanya demikian karena saya tahu ada beberapa yang disebut bahasa fungsional murni di luar sana dan menurut teori lengkap Turing, ini harus dilakukan juga.

Saya belajar C, Java, Python dan menggunakan banyak tugas di setiap program yang saya tulis. Jadi ini benar-benar pengalaman yang membuka mata. Saya benar-benar berharap seseorang dapat menjelaskan secara singkat bagaimana tugas-tugas dihindari dalam bahasa pemrograman fungsional dan apa dampak mendalam (jika ada) pada bahasa-bahasa ini.

Contoh yang disebutkan di atas ada di sini:

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

Ini mengubah balanceoleh set!. Bagi saya itu sangat mirip metode kelas untuk mengubah anggota kelas balance.

Seperti yang saya katakan, saya tidak terbiasa dengan bahasa pemrograman fungsional, jadi jika saya mengatakan sesuatu yang salah tentang mereka, jangan ragu untuk menunjukkannya.

Jika tidak ada pernyataan penugasan, bagaimana ini bisa dilakukan? Bagaimana mengubah variabel saldo?

Anda tidak dapat mengubah variabel tanpa semacam operator penugasan.

Saya bertanya demikian karena saya tahu ada beberapa yang disebut bahasa fungsional murni di luar sana dan menurut teori lengkap Turing, ini harus dilakukan juga.

Tidak terlalu. Jika suatu bahasa Turing lengkap, itu berarti ia dapat menghitung apa saja yang bisa dihitung oleh bahasa lengkap Turing lainnya. Itu tidak berarti bahwa ia harus memiliki setiap fitur yang dimiliki bahasa lain.

Ini bukan kontradiksi bahwa bahasa pemrograman Turing yang lengkap tidak memiliki cara untuk mengubah nilai variabel, asalkan untuk setiap program yang memiliki variabel yang dapat berubah, Anda dapat menulis program yang setara yang tidak memiliki variabel yang dapat diubah (di mana "setara" berarti itu menghitung hal yang sama). Dan sebenarnya setiap program bisa ditulis seperti itu.

Mengenai contoh Anda: Dalam bahasa yang murni fungsional Anda tidak akan bisa menulis fungsi yang mengembalikan saldo akun yang berbeda setiap kali dipanggil. Tetapi Anda masih dapat menulis ulang setiap program, yang menggunakan fungsi seperti itu, dengan cara yang berbeda.

Karena Anda meminta contoh, mari kita pertimbangkan program imperatif yang menggunakan fungsi make-withdraw Anda (dalam pseudo-code). Program ini memungkinkan pengguna untuk menarik dari akun, menyetornya atau meminta jumlah uang di akun:

account = make-withdraw(0)
ask for input until the user enters "quit"
    if the user entered "withdraw $x"
        account(x)
    if the user entered "deposit $x"
        account(-x)
    if the user entered "query"
        print("The balance of the account is " + account(0))

Berikut adalah cara untuk menulis program yang sama tanpa menggunakan variabel yang bisa berubah-ubah (Saya tidak akan repot-repot dengan IO yang transparan referensial karena pertanyaannya bukan tentang itu):

function IO_loop(balance):
    ask for input
    if the user entered "withdraw $x"
        IO_loop(balance - x)
    if the user entered "deposit $x"
        IO_loop(balance + x)
    if the user entered "query"
        print("The balance of the account is " + balance)
        IO_loop(balance)
    if the user entered "quit"
        do nothing

 IO_loop(0)

Fungsi yang sama juga dapat ditulis tanpa menggunakan rekursi dengan menggunakan lipatan atas input pengguna (yang akan lebih idiomatis daripada rekursi eksplisit), tapi saya tidak tahu apakah Anda sudah terbiasa dengan lipatan, jadi saya menulisnya dalam cara itu tidak menggunakan apa pun yang Anda belum tahu.

Anda benar bahwa itu sangat mirip metode pada objek. Itu karena itulah dasarnya. The lambdafungsi adalah penutupan yang menarik variabel eksternal balanceke dalam ruang lingkup. Memiliki beberapa penutupan yang menutup variabel eksternal yang sama dan memiliki banyak metode pada objek yang sama adalah dua abstraksi berbeda untuk melakukan hal yang sama persis, dan salah satu dapat diimplementasikan dalam hal yang lain jika Anda memahami kedua paradigma.

Cara bahasa fungsional murni menangani negara adalah dengan menyontek. Misalnya, di Haskell jika Anda ingin membaca input dari sumber eksternal, (yang tidak deterministik, tentu saja, dan tidak harus memberikan hasil yang sama dua kali jika Anda mengulanginya,) ia menggunakan trik monad untuk mengatakan "kami sudah mendapatkan variabel berpura-pura ini yang mewakili keadaan seluruh dunia , dan kita tidak dapat memeriksanya secara langsung, tetapi membaca input adalah fungsi murni yang mengambil keadaan dunia luar dan mengembalikan input deterministik bahwa keadaan yang tepat akan selalu memberikan, ditambah keadaan baru dunia luar. " (Itu penjelasan yang disederhanakan, tentu saja. Membaca tentang cara kerjanya sebenarnya akan merusak otak Anda.)

Atau dalam kasus masalah rekening bank Anda, alih-alih menetapkan nilai baru ke variabel, itu dapat mengembalikan nilai baru sebagai hasil fungsi, dan kemudian penelepon harus menghadapinya dalam gaya fungsional, umumnya dengan membuat kembali data apa pun yang merujuk nilai itu dengan versi baru yang mengandung nilai yang diperbarui. (Ini bukan operasi besar seperti mungkin terdengar jika data Anda diatur dengan jenis struktur pohon yang tepat.)

"Operator penugasan berganda" adalah salah satu contoh fitur bahasa yang, secara umum, memiliki efek samping, dan tidak sesuai dengan beberapa sifat berguna bahasa fungsional (seperti evaluasi malas).

Namun, itu tidak berarti bahwa penugasan secara umum tidak sesuai dengan gaya pemrograman fungsional murni (lihat diskusi ini misalnya), juga tidak berarti Anda tidak dapat membuat sintaks yang memungkinkan tindakan yang mirip penugasan secara umum, tetapi diimplementasikan tanpa efek samping. Membuat sintaks semacam itu, dan menulis program yang efisien di dalamnya, memakan waktu dan sulit.

Dalam contoh spesifik Anda, Anda benar - set! operator adalah tugas. Ini bukan operator efek samping gratis, dan ini adalah tempat di mana Skema istirahat dengan pendekatan fungsional murni untuk pemrograman.

Pada akhirnya, bahasa murni fungsional apa pun harus dihilangkan dengan pendekatan fungsional murni suatu saat - sebagian besar program yang bermanfaat memang memiliki efek samping. Keputusan kemana harus melakukannya biasanya adalah masalah kenyamanan, dan perancang bahasa akan mencoba memberi para programmer fleksibilitas tertinggi dalam memutuskan di mana harus memutuskan dengan pendekatan yang murni fungsional, yang sesuai untuk program dan domain masalah mereka.

Dalam bahasa yang murni fungsional, seseorang akan memprogram objek rekening bank sebagai fungsi transformator arus. Objek dianggap sebagai fungsi dari aliran permintaan tanpa batas dari pemilik akun (atau siapa pun) ke aliran tanggapan yang berpotensi tidak terbatas. Fungsi dimulai dengan saldo awal, dan memproses setiap permintaan dalam aliran input untuk menghitung saldo baru, yang kemudian diumpankan kembali ke panggilan rekursif untuk memproses sisa aliran. (Saya ingat bahwa SICP membahas paradigma stream-transformer di bagian lain buku ini.)

Versi yang lebih rumit dari paradigma ini disebut "pemrograman reaktif fungsional" yang dibahas di sini di StackOverflow .

Cara naif melakukan transformator arus memiliki beberapa masalah. Adalah mungkin (pada kenyataannya, sangat mudah) untuk menulis program kereta yang menjaga semua permintaan lama, membuang-buang ruang. Lebih serius, adalah mungkin untuk membuat respons terhadap permintaan saat ini bergantung pada permintaan di masa depan. Solusi untuk masalah ini sedang dikerjakan. Neel Krishnaswami adalah kekuatan di belakang mereka.

Penafian : Saya bukan milik gereja pemrograman fungsional murni. Sebenarnya, saya bukan milik gereja mana pun :-)

Tidak mungkin membuat program 100% fungsional jika seharusnya melakukan sesuatu yang bermanfaat. (Jika efek samping tidak diperlukan, maka seluruh pemikiran dapat direduksi menjadi waktu kompilasi yang konstan) Seperti contoh penarikan, Anda dapat membuat sebagian besar prosedur berfungsi tetapi pada akhirnya Anda akan memerlukan prosedur yang memiliki efek samping (input dari pengguna, output ke konsol). Yang mengatakan Anda dapat membuat sebagian besar kode Anda berfungsi dan bagian itu akan mudah diuji, bahkan secara otomatis. Kemudian Anda membuat beberapa kode penting untuk melakukan input / output / database / ... yang akan membutuhkan debugging, tetapi menjaga sebagian besar kode bersih itu tidak akan terlalu banyak bekerja. Saya akan menggunakan contoh penarikan Anda:

(define +no-founds+ "Insufficient funds")

;; functional withdraw
(define (make-withdraw balance amount)
    (if (>= balance amount)
        (- balance amount)
        +no-founds+))

;; functional atm loop
(define (atm balance thunk)
  (let* ((amount (thunk balance)) 
         (new-balance (make-withdraw balance amount)))
    (if (eqv? new-balance +no-founds+)
        (cons +no-founds+ '())
        (cons (list 'withdraw amount 'balance new-balance) (atm new-balance thunk)))))

;; functional balance-line -> string 
(define (balance->string x)
  (if (eqv? x +no-founds+)
      (string-append +no-founds+ "\n")
      (if (null? x)
          "\n"
          (let ((first-token (car x)))
            (string-append
             (cond ((symbol? first-token) (symbol->string first-token))
                   (else (number->string first-token)))
             " "
             (balance->string (cdr x)))))))

;; functional thunk to test  
(define (input-10 x) 10) ;; define a purly functional input-method

;; since all procedures involved are functional 
;; we expect the same result every time.
;; we use this to test atm and make-withdraw
(apply string-append (map balance->string (atm 100 input-10)))

;; no program can be purly functional in any language.
;; From here on there are imperative dirty procedures!

;; A procedure to get input from user is needed. 
;; Side effects makes it imperative
(define (user-input balance)
  (display "You have $")
  (display balance)
  (display " founds. How much to withdraw? ")
  (read))

;; We need a procedure to print stuff to the console 
;; as well. Side effects makes it imperative
(define (pretty-print-result x)
  (for-each (lambda (x) (display (balance->string x))) x))

;; use imperative procedure with atm.
(pretty-print-result (atm 100 user-input))

Dimungkinkan untuk melakukan hal yang sama di hampir semua bahasa dan menghasilkan hasil yang sama (lebih sedikit bug), meskipun Anda mungkin harus menetapkan variabel sementara dalam suatu prosedur dan bahkan bermutasi, tetapi itu tidak terlalu menjadi masalah selama prosedur sebenarnya berfungsi fungsional (parameternya sendiri yang menentukan hasilnya). Saya percaya Anda menjadi programmer yang lebih baik pada bahasa apa pun setelah Anda memprogram LISP kecil :)

Tugas adalah operasi yang buruk karena membagi ruang negara menjadi dua bagian, sebelum penugasan, dan setelah penugasan. Ini menyebabkan kesulitan melacak bagaimana variabel diubah selama eksekusi program. Hal-hal berikut dalam bahasa fungsional menggantikan tugas:

1. Parameter fungsi terhubung langsung ke nilai yang dikembalikan
2. memilih objek yang berbeda untuk dikembalikan alih-alih memodifikasi objek yang ada.
3. menciptakan nilai-nilai malas yang baru dievaluasi
4. daftar semua objek yang mungkin , bukan hanya yang perlu ada di memori
5. tidak ada efek samping