[functional-programming] Come puoi fare qualcosa di utile senza uno stato mutabile?


7 Answers

Risposta breve: non puoi.

Allora, qual è il problema dell'immutabilità?

Se sei esperto in una lingua imperativa, allora sai che le "globali sono cattive". Perché? Perché introducono (o hanno il potenziale per introdurre) alcune dipendenze molto difficili da districare nel codice. E le dipendenze non sono buone; vuoi che il tuo codice sia modulare . Parti del programma non influenzano le altre parti il ​​meno possibile. E FP ti porta al Santo Graal della modularità: nessun effetto collaterale. Hai appena il tuo f (x) = y. Metti x dentro, tirati fuori. Nessuna modifica a x o qualsiasi altra cosa. FP ti fa smettere di pensare allo stato e iniziare a pensare in termini di valori. Tutte le tue funzioni ricevono semplicemente valori e producono nuovi valori.

Questo ha diversi vantaggi.

Prima di tutto, nessun effetto collaterale significa programmi più semplici, più facili da ragionare. Non c'è da preoccuparsi che l'introduzione di una nuova parte del programma interferisca e blocchi una parte esistente e funzionante.

In secondo luogo, ciò rende banalmente parallelo il programma (la parallelizzazione efficiente è un'altra questione).

In terzo luogo, ci sono alcuni possibili vantaggi in termini di prestazioni. Di 'che hai una funzione:

double x = 2 * x

Ora inserisci un valore di 3 in e ottieni un valore di 6. Ogni volta. Ma puoi farlo anche in modo imperativo, giusto? Sì. Ma il problema è che in caso di necessità, puoi fare ancora di più . Posso fare:

int y = 2;
int double(x){ return x * y; }

ma potrei anche farlo

int y = 2;
int double(x){ return x * (y++); }

Il compilatore imperativo non sa se avrò o meno effetti collaterali, il che rende più difficile l'ottimizzazione (ad esempio il doppio 2 non deve essere 4 ogni volta). Il funzionale sa che non lo farò - quindi, può ottimizzare ogni volta che vede "doppio 2".

Ora, anche se creare nuovi valori ogni volta sembra incredibilmente dispendioso per tipi di valori complessi in termini di memoria del computer, non deve essere così. Perché se hai f (x) = y, ei valori xey sono "per lo più uguali" (es. Alberi che differiscono solo in alcune foglie) allora x e y possono condividere parti di memoria - perché nessuno di loro muterà .

Quindi se questa cosa immutabile è così grande, perché ho risposto che non puoi fare nulla di utile senza uno stato mutevole. Bene, senza mutabilità, il tuo intero programma sarebbe una gigantesca funzione f (x) = y. E lo stesso vale per tutte le parti del programma: solo funzioni e funzioni in senso "puro". Come ho detto, questo significa f (x) = y ogni volta. Ad esempio, readFile ("myFile.txt") dovrebbe restituire sempre lo stesso valore di stringa. Non troppo utile.

Pertanto, ogni FP fornisce alcuni mezzi di stato mutante. I linguaggi funzionali "puri" (ad es. Haskell) lo fanno usando concetti alquanto spaventosi come le monadi, mentre quelli "impuri" (es. ML) lo consentono direttamente.

E, naturalmente, i linguaggi funzionali sono dotati di una serie di altri gadget che rendono la programmazione più efficiente, come le funzioni di prima classe, ecc.

Question

Ho letto un sacco di cose sulla programmazione funzionale ultimamente, e posso capirne la maggior parte, ma l'unica cosa che non riesco a capire è la codifica senza stato. Mi sembra che semplificare la programmazione rimuovendo lo stato mutabile sia come "semplificare" un'auto rimuovendo il cruscotto: il prodotto finito può essere più semplice, ma buona fortuna farlo interagire con gli utenti finali.

Quasi tutte le applicazioni utente a cui posso pensare implicano lo stato come un concetto centrale. Se scrivi un documento (o un post SO), lo stato cambia ad ogni nuovo input. Oppure, se giochi a un videogioco, ci sono tonnellate di variabili di stato, a cominciare dalle posizioni di tutti i personaggi, che tendono a muoversi costantemente. Come puoi fare qualcosa di utile senza tenere traccia dei cambiamenti dei valori?

Ogni volta che trovo qualcosa che discute di questo problema, è scritto in modo molto tecnico-funzionale, il che presuppone un pesante background FP che non ho. Qualcuno conosce un modo per spiegare questo a qualcuno con una buona, solida comprensione della codifica imperativa, ma chi è un n00b completo sul lato funzionale?

EDIT: Un sacco di risposte finora sembrano cercare di convincermi dei vantaggi dei valori immutabili. Ho capito quella parte. Ha perfettamente senso. Quello che non capisco è come tenere traccia dei valori che devono cambiare e cambiarsi costantemente, senza variabili mutabili.




Sono in ritardo con la discussione, ma volevo aggiungere alcuni punti per le persone che hanno difficoltà con la programmazione funzionale.

  1. I linguaggi funzionali mantengono gli stessi aggiornamenti di stato dei linguaggi imperativi, ma lo fanno passando lo stato aggiornato alle chiamate di funzione successive . Ecco un esempio molto semplice di percorrere una linea numerica. Il tuo stato è la tua posizione attuale.

Prima il modo imperativo (in pseudocodice)

moveTo(dest, cur):
    while (cur != dest):
         if (cur < dest):
             cur += 1
         else:
             cur -= 1
    return cur

Ora il modo funzionale (in pseudocodice). Mi sto appoggiando pesantemente all'operatore ternario perché voglio che le persone provenienti da sfondi imperativi siano effettivamente in grado di leggere questo codice. Quindi se non usi molto l'operatore ternario (l'ho sempre evitato nei miei giorni imperiosi) ecco come funziona.

predicate ? if-true-expression : if-false-expression

Puoi concatenare l'espressione ternaria mettendo una nuova espressione ternaria al posto della falsa espressione

predicate1 ? if-true1-expression :
predicate2 ? if-true2-expression :
else-expression

Quindi con questo in mente, ecco la versione funzionale.

moveTo(dest, cur):
    return (
        cur == dest ? return cur :
        cur < dest ? moveTo(dest, cur + 1) : 
        moveTo(dest, cur - 1)
    )

Questo è un esempio banale. Se questo spostasse le persone in un mondo di gioco, dovresti introdurre effetti collaterali come disegnare la posizione corrente dell'oggetto sullo schermo e introdurre un po 'di ritardo in ogni chiamata in base alla velocità con cui l'oggetto si muove. Ma non avresti ancora bisogno di uno stato mutabile.

  1. La lezione è che lo stato "mutato" delle lingue funzionali chiama la funzione con parametri diversi. Ovviamente questo non muta realmente nessuna variabile, ma è così che si ottiene un effetto simile. Questo significa che dovrai abituarti a pensare in modo ricorsivo se vuoi fare una programmazione funzionale.

  2. Imparare a pensare in modo ricorsivo non è difficile, ma richiede sia pratica che un kit di strumenti. Quella piccola sezione in quel libro "Impara Java" dove hanno usato la ricorsione per calcolare fattoriale non la taglia. È necessario un kit di strumenti come la creazione di processi iterativi dalla ricorsione (questo è il motivo per cui la ricorsione in coda è essenziale per il linguaggio funzionale), continuazioni, invarianti, ecc. Non si farebbe la programmazione OO senza conoscere modificatori di accesso, interfacce, ecc. per la programmazione funzionale.

La mia raccomandazione è di fare Little Schemer (nota che io dico "do" e non "read") e poi fare tutti gli esercizi in SICP. Quando hai finito, avrai un cervello diverso rispetto a quando hai iniziato.




In effetti è abbastanza facile avere qualcosa che assomiglia a uno stato mutevole anche in lingue senza stato mutabile.

Considera una funzione con tipo s -> (a, s) . Traducendo dalla sintassi di Haskell, significa una funzione che accetta un parametro di tipo " s " e restituisce una coppia di valori, di tipi " a " e " s ". Se s è il tipo del nostro stato, questa funzione accetta uno stato e restituisce un nuovo stato, e possibilmente un valore (puoi sempre restituire "unit" aka () , che è una specie di equivalente a " void " in C / C ++, come il tipo " a "). Se si concatenano più chiamate di funzioni con tipi come questo (ottenendo lo stato restituito da una funzione e passandola alla successiva), si ha uno stato "mutabile" (in realtà ci si trova in ogni funzione che crea un nuovo stato e si abbandona quello precedente ).

Potrebbe essere più facile capire se si immagina lo stato mutabile come lo "spazio" in cui si sta eseguendo il programma, e quindi si pensi alla dimensione temporale. All'istante t1, lo "spazio" si trova in una determinata condizione (ad esempio, qualche posizione di memoria ha il valore 5). In un istante successivo t2, si trova in una condizione diversa (ad esempio, la posizione di memoria ha ora il valore 10). Ognuna di queste "fette" di tempo è uno stato ed è immutabile (non puoi tornare indietro nel tempo per cambiarle). Quindi, da questo punto di vista, sei passato dallo spaziotempo completo a una freccia temporale (il tuo stato mutabile) a un insieme di fette di spaziotempo (diversi stati immutabili), e il tuo programma tratta semplicemente ogni fetta come valore e calcola ciascuna di loro come una funzione applicata alla precedente.

OK, forse non era più facile da capire :-)

Potrebbe sembrare inefficiente rappresentare esplicitamente l'intero stato del programma come un valore, che deve essere creato solo per essere scartato l'istante successivo (subito dopo la creazione di uno nuovo). Per alcuni algoritmi potrebbe essere naturale, ma quando non lo è, c'è un altro trucco. Invece di uno stato reale, puoi usare uno stato falso che non è altro che un indicatore (chiamiamo il tipo di questo stato di stato falso State# ). Questo stato falso esiste dal punto di vista della lingua e viene passato come qualsiasi altro valore, ma il compilatore lo omette completamente durante la generazione del codice macchina. Serve solo a segnare la sequenza di esecuzione.

Ad esempio, supponiamo che il compilatore ci fornisca le seguenti funzioni:

readRef :: Ref a -> State# -> (a, State#)
writeRef :: Ref a -> a -> State# -> (a, State#)

Traducendo da queste dichiarazioni tipo Haskell, readRef riceve qualcosa che assomiglia a un puntatore o un handle a un valore di tipo " a " e allo stato falso e restituisce il valore di tipo " a " puntato dal primo parametro e un nuovo stato falso writeRef è simile, ma cambia invece il valore puntato.

Se chiami readRef e poi lo passi, lo stato falso restituito da writeRef (forse con altre chiamate a funzioni non correlate nel mezzo, questi valori di stato creano una "catena" di chiamate di funzione), restituirà il valore scritto. Puoi chiamare writeRef nuovo con lo stesso puntatore / handle e scriverà nella stessa locazione di memoria - ma, dal momento che concettualmente sta restituendo uno stato nuovo (falso), lo stato (falso) è ancora imutabile (ne è stato creato uno nuovo) creato"). Il compilatore chiamerà le funzioni nell'ordine in cui dovrebbe chiamarle se ci fosse una variabile di stato reale che doveva essere calcolata, ma l'unico stato che c'è è lo stato completo (mutevole) dell'hardware reale.

(Coloro che sanno che Haskell noterà che ho semplificato molto le cose e ho omesso molti dettagli importanti.Per chi vuole vedere più dettagli, dai un'occhiata a Control.Monad.State dalla mtl e alla ST s e IO (aka ST RealWorld ).)

Potresti chiederti perché farlo in un modo così indiretto (invece di avere semplicemente uno stato mutabile nella lingua). Il vero vantaggio è che hai reified lo stato del tuo programma. Quello che prima era implicito (il tuo stato del programma era globale, tenendo conto di cose come l' azione a distanza ) è ora esplicito. Le funzioni che non ricevono e restituiscono lo stato non possono modificarlo o essere influenzato da esso; sono "puri". Ancora meglio, puoi avere thread di stato separati, e con un po 'di magia del tipo, possono essere usati per incorporare un calcolo imperativo all'interno di uno puro, senza renderlo impuro (la monade di ST in Haskell è quella normalmente usata per questo trucco lo State# cui sopra è in effetti State# s GHC, utilizzato dalla sua implementazione delle monadi ST e IO ).




Sono solo diversi modi di fare la stessa cosa.

Considera un semplice esempio come aggiungere i numeri 3, 5 e 10. Immagina di pensare a farlo modificando prima il valore di 3 aggiungendo 5 a esso, quindi aggiungendo 10 a quel "3", quindi emettendo il valore corrente di " 3 "(18). Ciò sembra palesemente ridicolo, ma è in sostanza il modo in cui spesso viene eseguita la programmazione imperativa basata sullo stato. In effetti, puoi avere molti "3" diversi che hanno il valore 3, eppure sono diversi. Tutto ciò sembra strano, perché siamo stati così radicati nell'idea, assolutamente enormemente ragionevole, che i numeri sono immutabili.

Ora pensate di aggiungere 3, 5 e 10 quando prendete i valori per essere immutabili. Aggiungi 3 e 5 per produrre un altro valore, 8, quindi aggiungi 10 a quel valore per produrre ancora un altro valore, 18.

Questi sono modi equivalenti per fare la stessa cosa. Tutte le informazioni necessarie esistono in entrambi i metodi, ma in forme diverse. In uno l'informazione esiste come stato e nelle regole per cambiare stato. Nell'altra l'informazione esiste in dati immutabili e definizioni funzionali.




Questo è il modo in cui FORTRAN funziona senza blocchi COMMON: scriverei i metodi con i valori passati e le variabili locali. Questo è tutto.

La programmazione orientata agli oggetti ci ha portato lo stato e il comportamento insieme, ma è stata una nuova idea quando l'ho incontrata per la prima volta da C ++ nel 1994.

Accidenti, ero un programmatore funzionante quando ero un ingegnere meccanico e non lo sapevo!







Bear in mind: functional languages are Turing complete. Therefore, any useful task you would perform in an imperitive language can be done in a functional language. At the end of the day though, I think there's something to be said of a hybrid approach. Languages like F# and Clojure (and I'm sure others) encourage stateless design, but allow for mutability when necessary.




Ecco come si scrive codice senza stato mutabile : invece di mettere lo stato mutevole in variabili mutabili, lo si inserisce nei parametri delle funzioni. E invece di scrivere loop, scrivi funzioni ricorsive. Quindi per esempio questo codice imperativo:

f_imperative(y) {
  local x;
  x := e;
  while p(x, y) do
    x := g(x, y)
  return h(x, y)
}

diventa questo codice funzionale (sintassi Scheme-like):

(define (f-functional y) 
  (letrec (
     (f-helper (lambda (x y)
                  (if (p x y) 
                     (f-helper (g x y) y)
                     (h x y)))))
     (f-helper e y)))

o questo codice Haskellish

f_fun y = h x_final y
   where x_initial = e
         x_final   = loop x_initial
         loop x = if p x y then loop (g x y) else x

Per quanto riguarda il motivo per cui ai programmatori funzionali piace fare questo (cosa che non hai chiesto), più pezzi del tuo programma sono senza stato, più modi ci sono per mettere insieme i pezzi senza avere nulla da rompere . Il potere del paradigma stateless non sta nell'essere apolidi (o nella purezza) di per sé , ma nella capacità che ti dà di scrivere funzioni potenti, riutilizzabili e combinarle.

Puoi trovare un buon tutorial con molti esempi nel documento di John Hughes. Perché la programmazione funzionale è importante .




Related