come un puro linguaggio di programmazione funzionale può gestire senza istruzioni di assegnazione?

26

Durante la lettura del famoso SICP, ho trovato gli autori piuttosto riluttanti a introdurre la dichiarazione di assegnazione su Scheme nel Capitolo 3. Ho letto il testo e capisco perché lo sentano così.

Poiché Scheme è il primo linguaggio di programmazione funzionale di cui io abbia mai saputo qualcosa, sono sorpreso che ci siano alcuni linguaggi di programmazione funzionali (non Scheme, naturalmente) che possono fare senza incarichi.

Utilizza l'esempio offerto dal libro, l'esempio bank account . Se non c'è una dichiarazione di assegnazione, come può essere fatto? Come modificare la variabile balance ? Lo chiedo perché so che ci sono alcuni cosiddetti linguaggi puramente funzionali e, secondo la teoria completa di Turing, anche questo può essere fatto.

Ho imparato C, Java, Python e uso molte assegnazioni in ogni programma che ho scritto. Quindi è davvero un'esperienza che apre gli occhi. Spero davvero che qualcuno possa spiegare brevemente come si evitano i compiti in quei linguaggi di programmazione funzionale e quale impatto profondo (se esiste) ha in queste lingue.

L'esempio sopra menzionato è qui:

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

Questo ha cambiato il balance di set! . Per me sembra molto simile a un metodo di classe per cambiare il membro della classe balance .

Come ho detto, non ho familiarità con i linguaggi di programmazione funzionale, quindi se ho detto qualcosa di sbagliato su di essi, sentitevi liberi di farlo notare.

    
posta Gnijuohz 12.04.2012 - 06:57
fonte

6 risposte

20

If there is no assignment statement,how can this be done?How to change the balance variable?

Non è possibile modificare le variabili senza alcun tipo di operatore di assegnazione.

I ask so because I know there are some so-called pure functional languages out there and according to the Turing complete theory,this must can be done too.

Non proprio. Se una lingua è completa, Turing significa che può calcolare tutto ciò che può essere calcolato da qualsiasi altra lingua completa di Turing. Ciò non significa che deve avere tutte le funzionalità di altri linguaggi.

Non è una contraddizione che un linguaggio di programmazione completo di Turing non abbia modo di modificare il valore di una variabile, purché per ogni programma che ha variabili mutabili, puoi scrivere un programma equivalente che non ha variabili mutabili (dove " equivalente "significa che calcola la stessa cosa). E infatti ogni programma può essere scritto in questo modo.

Per quanto riguarda il tuo esempio: in un linguaggio puramente funzionale, semplicemente non potresti scrivere una funzione che restituisce un diverso saldo del conto ogni volta che viene chiamato. Ma saresti comunque in grado di riscrivere ogni programma, che utilizza tale funzione, in un modo diverso.

Dato che hai chiesto un esempio, prendiamo in considerazione un programma imperativo che usa la funzione di estrapolazione (in pseudo-codice). Questo programma consente all'utente di ritirarsi da un account, depositarlo o interrogare la quantità di denaro nel conto:

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))

Ecco un modo per scrivere lo stesso programma senza usare variabili mutabili (non mi preoccuperò dell'IO referenzialmente trasparente perché la domanda non riguardava questo):

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)

La stessa funzione potrebbe anche essere scritta senza ricorrere alla ricorsione usando una piega sull'input dell'utente (che sarebbe più idiomatico della ricorsione esplicita), ma non so se hai già familiarità con le pieghe, quindi ho scritto in un modo che non usa nulla che non conosci ancora.

    
risposta data 12.04.2012 - 07:58
fonte
11

Hai ragione che assomiglia molto ad un metodo su un oggetto. Questo perché è essenzialmente quello che è. La funzione lambda è una chiusura che estrae la variabile esterna balance nel suo ambito. Avere più chiusure che si chiudono sulle stesse variabili esterne e avere più metodi sullo stesso oggetto sono due diverse astrazioni per fare esattamente la stessa cosa, e uno può essere implementato in termini dell'altro se si comprendono entrambi i paradigmi. / p>

Il modo in cui i linguaggi funzionali puri gestiscono lo stato è barando. Ad esempio, in Haskell se vuoi leggere l'input da una fonte esterna, (che è non deterministico, ovviamente, e non darà necessariamente lo stesso risultato due volte se lo ripeti,) usa un trucco monade per dire "abbiamo ha ottenuto quest'altra variabile finga che rappresenta lo stato dell'intero resto del mondo , e non possiamo esaminarla direttamente, ma l'input di lettura è una funzione pura che prende lo stato del mondo esterno e restituisce l'input deterministico che renderà sempre quello stato esatto, più il nuovo stato del mondo esterno. " (Questa è una spiegazione semplificata, ovviamente: leggere il modo in cui funziona in realtà ti spezzerà seriamente il cervello.)

O nel caso del tuo problema con il conto bancario, invece di assegnare un nuovo valore alla variabile, può restituire il nuovo valore come risultato della funzione, e quindi il chiamante deve occuparsene in uno stile funzionale, generalmente da ricreare tutti i dati che fanno riferimento a quel valore con una nuova versione contenente il valore aggiornato. (Questa operazione non è così ingombrante come potrebbe sembrare se i tuoi dati sono impostati con il giusto tipo di struttura ad albero.)

    
risposta data 12.04.2012 - 08:03
fonte
3

"Operatori di assegnazione multipla" è un esempio di una funzione linguistica che, in generale, ha effetti collaterali ed è incompatibile con alcune proprietà utili dei linguaggi funzionali (come la valutazione lazy).

Questo, tuttavia, non significa che l'assegnazione in generale sia incompatibile con uno stile di programmazione puramente funzionale (vedi questa discussione ad esempio), né significa che non è possibile costruire la sintassi che consente azioni che assomigliano a compiti in generale, ma che sono implementate senza effetti collaterali. Creare quel tipo di sintassi e scrivere programmi efficienti al suo interno richiede molto tempo e fatica.

Nel tuo esempio specifico, hai ragione - il set! l'operatore è un incarico. È non un operatore privo di effetti collaterali, ed è un luogo in cui Scheme rompe con un approccio puramente funzionale alla programmazione.

In definitiva, qualsiasi linguaggio puramente funzionale dovrà rompere con l'approccio puramente funzionale a volte - la stragrande maggioranza dei programmi utili do ha effetti collaterali. La decisione su dove farlo è di solito una questione di convenienza, ei progettisti di linguaggi cercheranno di offrire al programmatore la massima flessibilità nel decidere dove rompere con un approccio puramente funzionale, come appropriato per il loro programma e dominio problematico.

    
risposta data 12.04.2012 - 07:48
fonte
3

In un linguaggio puramente funzionale, si programmerebbe un oggetto di conto bancario come una funzione di trasformazione dello stream. L'oggetto è considerato come una funzione da un flusso infinito di richieste dai proprietari dell'account (o da chiunque) a un flusso potenzialmente infinito di risposte. La funzione inizia con un bilancio iniziale ed elabora ciascuna richiesta nel flusso di input per calcolare un nuovo saldo, che viene quindi ricondotto alla chiamata ricorsiva per elaborare il resto del flusso. (Ricordo che SICP discute il paradigma dello stream-transformer in un'altra parte del libro.)

Una versione più elaborata di questo paradigma è chiamata "programmazione reattiva funzionale" discussa qui su StackOverflow .

Il modo ingenuo di creare trasformatori di stream ha alcuni problemi. È possibile (in effetti, abbastanza facile) scrivere programmi buggy che mantengano tutte le vecchie richieste in giro, sprecando spazio. Più seriamente, è possibile fare in modo che la risposta alla richiesta corrente dipenda dalle richieste future. Le soluzioni a questi problemi sono attualmente in lavorazione. Neel Krishnaswami è la forza dietro di loro.

Disclaimer : non appartengo alla chiesa della pura programmazione funzionale. In realtà, io non appartengo a nessuna chiesa: -)

    
risposta data 15.04.2012 - 22:16
fonte
2

Non è possibile rendere un programma funzionante al 100% se si suppone che faccia qualcosa di utile. (Se gli effetti collaterali non sono necessari allora tutto il pensiero potrebbe essere ridotto a un tempo di compilazione costante) Come nell'esempio di prelievo è possibile rendere la maggior parte delle procedure funzionanti, ma alla fine avrete bisogno di procedure con effetti collaterali (input da parte dell'utente, uscita alla console). Detto questo, puoi rendere funzionale la maggior parte del tuo codice e quella parte sarà facile da testare, anche automaticamente. Quindi si crea un codice imperativo per l'input / output / database / ... che richiederebbe il debugging, ma mantenendo la maggior parte del codice pulito non sarà troppo lavoro. Userò il tuo esempio di prelievo:

(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))

È possibile fare lo stesso in quasi tutti i linguaggi e produrre gli stessi risultati (meno bug), anche se potresti dover impostare delle variabili temporanee all'interno di una procedura e persino modificare le cose, ma non importa per quanto tempo in quanto la procedura agisce in modo funzionale (i soli parametri determinano il risultato). Credo che diventi un programmatore migliore in qualsiasi lingua dopo aver programmato un piccolo LISP:)

    
risposta data 07.08.2012 - 00:13
fonte
1

L'assegnazione è un'operazione errata perché divide lo spazio degli stati in due parti, prima dell'assegnazione e dopo l'assegnazione. Ciò causa difficoltà nel tenere traccia di come le variabili vengono modificate durante l'esecuzione del programma. Le seguenti cose in lingue funzionali sostituiscono i compiti:

  1. Parametri di funzione collegati direttamente ai valori di ritorno
  2. scegliere oggetti diversi da restituire invece di modificare oggetti esistenti.
  3. creazione di nuovi valori valutati pigri
  4. elenca tutti gli possibili oggetti, non solo quelli che devono essere in memoria
  5. senza effetti collaterali
risposta data 12.04.2012 - 17:25
fonte