String reverse (String arg) (if (arg.length == 0) (return arg;) else (return reverse (arg.substring (1, arg.length)) + arg.substring (0, 1);))
Questa funzione è piuttosto lenta perché richiama se stessa. In questo caso è possibile una perdita di memoria, poiché gli oggetti temporanei vengono creati molte volte. Ma questo è uno stile funzionale. Potrebbe mostrarti strano come le persone possano programmare in quel modo. Beh, stavo per dirtelo.

Vantaggi della programmazione funzionale

Probabilmente pensi che io non possa argomentare per giustificare la funzione mostruosa di cui sopra. Quando ho iniziato a studiare la programmazione funzionale, lo pensavo anch'io. Mi sbagliavo. Ci sono ottimi argomenti per questo stile. Alcuni di loro sono soggettivi. Ad esempio, i programmatori affermano che i programmi funzionali sono più facili da capire. Non darò tali argomenti, perché tutti sanno che la facilità di comprensione è una cosa molto soggettiva. Fortunatamente per me, ci sono ancora un sacco di argomenti oggettivi.

Test dell'unità

Poiché ogni simbolo in FP è immutabile, le funzioni non hanno effetti collaterali. Non è possibile modificare i valori delle variabili, inoltre, una funzione non può modificare un valore al di fuori del suo ambito, e quindi influenzare altre funzioni (come può accadere con i campi di classe o le variabili globali). Ciò significa che l'unico risultato di una funzione è il valore restituito. E l'unica cosa che può influenzare il valore restituito sono gli argomenti passati alla funzione.

Eccolo, il sogno azzurro degli unit tester. Puoi testare ogni funzione nel tuo programma usando solo gli argomenti che vuoi. Non è necessario chiamare le funzioni nell'ordine corretto o ricreare lo stato esterno corretto. Tutto quello che devi fare è passare argomenti che corrispondano ai casi limite. Se tutte le funzioni del tuo programma superano i test unitari, puoi essere molto più sicuro della qualità del tuo software rispetto ai linguaggi di programmazione imperativi. In Java o C ++, il controllo del valore restituito non è sufficiente: la funzione può modificare lo stato esterno, che deve essere verificato. Non c'è questo problema in FP.

Debug

Se un programma funzionale non si comporta come previsto, il debug è un gioco da ragazzi. È sempre possibile riprodurre il problema, poiché l'errore nella funzione non dipende dal codice estraneo eseguito in precedenza. In un programma imperativo, l'errore appare solo per un po'. Dovrai eseguire una serie di passaggi non correlati ai bug perché la funzione dipende dallo stato esterno e dagli effetti collaterali di altre funzioni. In FP, la situazione è molto più semplice: se il valore restituito è sbagliato, lo sarà sempre, indipendentemente da quali parti di codice siano state eseguite in precedenza.

Una volta riprodotto il bug, trovare la fonte è banale. È anche carino. Non appena interrompi l'esecuzione del programma, avrai l'intero stack di chiamate di fronte a te. Puoi visualizzare gli argomenti di chiamata di ogni funzione, proprio come in un linguaggio imperativo. Con la differenza che questo non basta in un programma imperativo, perché le funzioni dipendono dai valori di campi, variabili globali e stati di altre classi. Una funzione in FP dipende solo dai suoi argomenti e questa informazione è proprio davanti ai tuoi occhi! Inoltre, in un programma imperativo, il controllo del valore restituito non è sufficiente per stabilire se una parte di codice si comporta correttamente. Dovrai dare la caccia a dozzine di oggetti al di fuori della funzione per assicurarti che tutto funzioni correttamente. Nella programmazione funzionale, tutto ciò che devi fare è guardare il valore di ritorno!

Mentre cammini nello stack, noti gli argomenti passati e i valori restituiti. Non appena il valore di ritorno si discosta dalla norma, approfondisci la funzione e vai avanti. Questo viene ripetuto più volte finché non trovi la fonte dell'errore!

Multithreading

Il programma funzionale è subito pronto per la parallelizzazione senza alcuna modifica. Non devi preoccuparti di deadlock o condizioni di gara perché non hai bisogno di blocchi! Non un singolo pezzo di dati in un programma funzionale viene modificato due volte dallo stesso flusso o da altri diversi. Ciò significa che puoi facilmente aggiungere thread al tuo programma senza nemmeno pensare ai problemi inerenti ai linguaggi imperativi.

Se questo è il caso, allora perché i linguaggi di programmazione funzionale sono usati così raramente nelle applicazioni multithread? Più spesso di quanto pensi, in realtà. Ericsson ha sviluppato un linguaggio funzionale chiamato Erlang da utilizzare su switch di telecomunicazione tolleranti ai guasti e scalabili. Molte persone hanno notato i vantaggi di Erlang e hanno iniziato a usarlo. Si tratta di sistemi di telecomunicazioni e di controllo del traffico che non si scalano facilmente come i tipici sistemi sviluppati a Wall Street. In generale, i sistemi scritti in Erlang non sono scalabili e affidabili come i sistemi Java. I sistemi Erlang sono super affidabili.

La storia del multithreading non finisce qui. Se stai scrivendo un'applicazione essenzialmente a thread singolo, il compilatore può comunque ottimizzare un programma funzionale per utilizzare più CPU. Diamo un'occhiata al prossimo pezzo di codice.

Un compilatore di linguaggio funzionale può analizzare il codice, classificare le funzioni che creano stringhe s1 e s2 come funzioni che richiedono tempo ed eseguirle in parallelo. Questo non può essere fatto in un linguaggio imperativo, perché ogni funzione può cambiare lo stato esterno e il codice subito dopo la chiamata può dipendere da esso. In FP, l'analisi automatica delle funzioni e la ricerca di candidati idonei per la parallelizzazione è banale come un inline automatico! In questo senso, lo stile funzionale della programmazione soddisfa le esigenze del futuro. Gli sviluppatori di hardware non possono più far funzionare la CPU più velocemente. Invece, stanno aumentando il numero di core e rivendicando un aumento di quattro volte della velocità dell'elaborazione multithread. Naturalmente, dimenticano di dire molto bene nel tempo che il tuo nuovo processore mostrerà un aumento solo nei programmi sviluppati pensando al parallelismo. Ce ne sono pochissimi tra i software imperativi. Ma il 100% dei programmi funzionali è pronto per il multithreading.

Distribuzione a caldo

Ai vecchi tempi, dovevi riavviare il computer per installare gli aggiornamenti di Windows. Molte volte. Dopo aver installato una nuova versione del lettore multimediale. Ci sono stati cambiamenti significativi in ​​Windows XP, ma la situazione è ancora lontana dall'ideale (oggi ho eseguito Windows Update al lavoro e ora il fastidioso promemoria non mi lascerà in pace fino al riavvio). Sui sistemi Unix, il modello di aggiornamento era migliore. Per installare gli aggiornamenti, dovevi fermare alcuni componenti, ma non l'intero sistema operativo. Sebbene la situazione sembri migliore, non è ancora accettabile per un'ampia classe di applicazioni server. I sistemi di telecomunicazione devono essere accesi il 100% delle volte, perché se, a causa dell'aggiornamento, una persona non può chiamare un'ambulanza, si possono perdere vite umane. Anche le aziende con Wall Street non vogliono spegnere i server durante il fine settimana per installare gli aggiornamenti.

Idealmente, è necessario aggiornare tutte le parti necessarie del codice senza arrestare il sistema in linea di principio. Nel mondo imperativo, questo è impossibile [trans. in Smalltalk è possibilissimo]. Immagina di scaricare una classe Java al volo e ricaricare una nuova versione. Se lo facessimo, allora tutte le istanze della classe diventerebbero non operative, perché lo stato in cui si trovavano andrebbe perso. Dovremmo scrivere codice complicato per il controllo della versione. Dovresti serializzare tutte le istanze create della classe, quindi distruggerle, creare istanze della nuova classe, provare a caricare i dati serializzati nella speranza che la migrazione vada bene e le nuove istanze siano valide. E inoltre, il codice di migrazione deve essere scritto manualmente ogni volta. E il codice di migrazione deve anche preservare i collegamenti tra gli oggetti. In teoria va bene, ma in pratica non funzionerà mai.

In un programma funzionale, tutto lo stato è memorizzato nello stack come argomenti di funzione. Questo rende le distribuzioni a caldo molto più semplici! Fondamentalmente, tutto ciò che devi fare è calcolare la differenza tra il codice sul server di produzione e la nuova versione e installare le modifiche nel codice. Il resto verrà fatto automaticamente dagli strumenti linguistici! Se pensi che questa sia fantascienza, pensaci due volte. Gli ingegneri di Erlang hanno aggiornato i loro sistemi per anni senza fermarli.

Proof computing e ottimizzazione (prove e ottimizzazioni assistite dalla macchina)

Un'altra proprietà interessante dei linguaggi di programmazione funzionale è che possono essere studiati matematicamente. Poiché un linguaggio funzionale è un'implementazione di un sistema formale, tutte le operazioni matematiche utilizzate su carta possono essere applicate a programmi funzionali. Il compilatore, ad esempio, può convertire un pezzo di codice in un pezzo equivalente, ma più efficiente, dimostrando matematicamente la loro equivalenza. I database relazionali effettuano queste ottimizzazioni da anni. Nulla ti impedisce di utilizzare tecniche simili nei normali programmi.

Inoltre, puoi utilizzare strumenti matematici per dimostrare la correttezza delle sezioni dei tuoi programmi. Se vuoi, puoi scrivere strumenti che analizzano il codice e creano automaticamente Unit test per casi limite! Questa funzionalità è preziosa per i sistemi solidi come una roccia. Quando si sviluppano sistemi per il monitoraggio dei pacemaker o la gestione del traffico aereo, questi strumenti sono essenziali. Se i tuoi sviluppi non sono nell'area delle applicazioni critiche, gli strumenti di verifica automatica ti daranno comunque un enorme vantaggio rispetto ai tuoi concorrenti.

Funzioni di ordine superiore

Ricorda, quando ho parlato dei vantaggi di FP, ho notato che "tutto sembra bello, ma è inutile se devo scrivere in un linguaggio goffo in cui tutto è definitivo". Questa era un'illusione. L'uso di final dappertutto sembra goffo solo in linguaggi di programmazione imperativi come Java. I linguaggi di programmazione funzionale operano con altri tipi di astrazioni, in modo tale da dimenticare che una volta amavi cambiare le variabili. Uno di questi strumenti sono le funzioni di ordine superiore.

In FP, una funzione non è la stessa di una funzione in Java o C. È un superset: possono essere le stesse delle funzioni Java e anche di più. Supponiamo di avere una funzione in C:

Int add (int i, int j) (return i + j;)
In FP, questo non è lo stesso di una normale funzione C. Estendiamo il nostro compilatore Java per supportare questa notazione. Il compilatore deve trasformare la dichiarazione della funzione nel seguente codice Java (ricorda che la finale implicita è ovunque):

Classe add_function_t (int add (int i, int j) (return i + j;)) add_function_t add = new add_function_t ();
Il simbolo di aggiunta non è realmente una funzione. È una piccola classe con un metodo. Ora possiamo passare add come argomento ad altre funzioni. Possiamo scriverlo su un altro simbolo. Possiamo creare istanze di add_function_t in fase di runtime e verranno raccolte nella spazzatura se non sono più necessarie. Le funzioni diventano oggetti di base come numeri e stringhe. Le funzioni che operano su funzioni (prendetele come argomenti) sono chiamate funzioni di ordine superiore. Non lasciare che ti spaventi. Il concetto di funzioni di ordine superiore è quasi lo stesso del concetto di classi Java che operano l'una sull'altra (possiamo passare le classi ad altre classi). Possiamo chiamarle "classi di ordine superiore", ma nessuno si preoccupa di questo, perché Java non ha una rigida comunità accademica alle spalle.

Come e quando dovresti usare le funzioni di ordine superiore? Sono contento che tu l'abbia chiesto. Scrivi il tuo programma come un pezzo di codice grande e monolitico senza preoccuparti della gerarchia delle classi. Se vedi che un pezzo di codice viene ripetuto in posti diversi, lo sposti in una funzione separata (fortunatamente, le scuole insegnano ancora come farlo). Se noti che parte della logica nella tua funzione deve comportarsi in modo diverso in alcune situazioni, crei una funzione di ordine superiore. Confuso? Ecco un esempio del mondo reale dal mio lavoro.

Supponiamo di avere un pezzo di codice Java che riceve un messaggio, lo trasforma in vari modi e lo invia a un altro server.

Void handleMessage (Message msg) (// ... msg.setClientCode ("ABCD_123"); // ... sendMessage (msg);) // ...)
Ora immagina che il sistema sia cambiato e che ora devi distribuire i messaggi tra due server anziché uno. Tutto rimane invariato, tranne il codice client: il secondo server vuole ricevere questo codice in un formato diverso. Come affrontiamo questa situazione? Possiamo controllare dove dovrebbe andare il messaggio e impostare il codice client corretto in base a quello. Ad esempio così:

Class MessageHandler (void handleMessage (Message msg) (// ... if (msg.getDestination (). Equals ("server1") (msg.setClientCode ("ABCD_123");) else (msg.setClientCode ("123_ABC") ;) // ... inviaMessage (msg);) // ...)
Ma questo approccio non si adatta bene. Man mano che vengono aggiunti nuovi server, la funzione crescerà in modo lineare e apportare modifiche diventerà un incubo. L'approccio orientato agli oggetti consiste nel sottoclassare la generica superclasse MessageHandler e sottoclassare la logica di definizione del codice client:

Classe astratta MessageHandler (void handleMessage (Message msg) (// ... msg.setClientCode (getClientCode ()); // ... sendMessage (msg);) abstract String getClientCode (); // ...) classe MessageHandlerOne estende MessageHandler (String getClientCode () (return "ABCD_123";)) class MessageHandlerTwo estende MessageHandler (String getClientCode () (restituisce "123_ABCD";))
Ora, per ogni server, possiamo creare un'istanza della classe corrispondente. L'aggiunta di nuovi dal server diventa più conveniente. Ma per un cambiamento così piccolo, troppo testo. Ho dovuto creare due nuovi tipi solo per aggiungere il supporto per un codice client diverso! Ora facciamo lo stesso nella nostra lingua con il supporto per le funzioni di ordine superiore:

Class MessageHandler (void handleMessage (Message msg, Function getClientCode) (// ... Message msg1 = msg.setClientCode (getClientCode ()); // ... sendMessage (msg1);) // ...) String getClientCodeOne ( ) (restituisce "ABCD_123";) String getClientCodeTwo () (restituire "123_ABCD";) Gestore MessageHandler = new MessageHandler (); handler.handleMessage (someMsg, getClientCodeOne);
Non abbiamo creato nuovi tipi né abbiamo complicato la gerarchia delle classi. Abbiamo appena passato la funzione come parametro. Abbiamo ottenuto lo stesso effetto della controparte orientata agli oggetti, con solo pochi vantaggi. Non ci siamo vincolati a nessuna gerarchia di classi: possiamo passare qualsiasi altra funzione in fase di runtime e modificarla in qualsiasi momento, mantenendo un alto livello di modularità con meno codice. In sostanza, il compilatore ha creato per noi la colla orientata agli oggetti! Allo stesso tempo, vengono mantenuti tutti gli altri vantaggi di FP. Naturalmente, le astrazioni offerte dai linguaggi funzionali non finiscono qui. Le funzioni di ordine superiore sono solo l'inizio

curry

La maggior parte delle persone che incontro ha letto i Design Patterns della Gang of Four. Qualsiasi programmatore che si rispetti dirà che il libro non è legato a nessun linguaggio di programmazione in particolare, e gli schemi sono applicabili allo sviluppo del software in generale. Questa è un'affermazione nobile. Ma purtroppo è lontano dalla verità.

I linguaggi funzionali sono incredibilmente espressivi. In un linguaggio funzionale, non hai bisogno di modelli di progettazione perché il linguaggio è di così alto livello che puoi facilmente iniziare a programmare in concetti che escludono tutti i modelli di programmazione conosciuti. Uno di questi modelli è l'adattatore (in che modo è diverso da Facade? Sembra che qualcuno abbia bisogno di stampare più pagine per soddisfare i termini del contratto). Questo modello non è necessario se la lingua supporta il currying.

Il modello Adapter viene spesso applicato all'unità di astrazione "standard" in una classe Java. Nei linguaggi funzionali, il modello viene applicato alle funzioni. Il pattern prende un'interfaccia e la trasforma in un'altra interfaccia, in base a determinati requisiti. Ecco un esempio di un pattern Adapter:

Int pow (int i, int j); int quadrato (int i) (return pow (i, 2);)
Questo codice adatta l'interfaccia di una funzione che eleva un numero a una potenza arbitraria all'interfaccia di una funzione che eleva al quadrato un numero. Negli ambienti accademici, questa tecnica più semplice è chiamata currying (dal nome del logico Haskell Curry, che eseguì una serie di trucchi matematici per formalizzare il tutto). Poiché le funzioni sono comunemente usate come argomenti in FP, il currying è usato molto spesso per portare le funzioni a un'interfaccia che è necessaria in un posto o nell'altro. Poiché l'interfaccia di una funzione sono i suoi argomenti, il currying viene utilizzato per ridurre il numero di argomenti (come nell'esempio sopra).

Questo strumento è integrato nei linguaggi funzionali. Non è necessario creare manualmente una funzione che ricopra l'originale. Un linguaggio funzionale farà tutto per te. Come al solito, espandiamo il nostro linguaggio aggiungendovi il curry.

Quadrato = int pow (int i, 2);
Con questa riga creiamo automaticamente una funzione quadrata con un argomento. La nuova funzione chiamerà pow, sostituendo 2 per il secondo argomento. Da una prospettiva Java, sarebbe simile a questo:

Classe square_function_t (int square (int i) (return pow (i, 2);)) square_function_t square = new square_function_t ();
Come puoi vedere, abbiamo appena scritto un wrapper sulla funzione originale. In FP, il curry è solo un modo semplice e conveniente per creare involucri. Ti concentri sull'attività e il compilatore scrive il codice necessario per te! È molto semplice e succede ogni volta che vuoi usare il pattern Adapter (wrapper).

Valutazione pigra

La valutazione pigra (o pigra) è una tecnica interessante che diventa possibile una volta afferrata la filosofia funzionale. Abbiamo già visto il seguente pezzo di codice quando abbiamo parlato di multithreading:

String s1 = alquantoLongOperation1 (); String s2 = alquantoLongOperation2 (); Stringa s3 = concatena (s1, s2);
Nei linguaggi di programmazione imperativi, l'ordine di valutazione non solleva alcun problema. Poiché ogni funzione può influenzare o dipendere da uno stato esterno, è necessario osservare un chiaro ordine di chiamate: prima, alquantoLongOperation1, poi alquantoLongOperation2, e concatenare alla fine. Ma non tutto è così semplice nei linguaggi funzionali.

Come abbiamo visto in precedenza, someLongOperation1 e alquantoLongOperation2 possono essere avviati contemporaneamente, perché è garantito che le funzioni non siano interessate e non dipendano dallo stato globale. Ma cosa succede se non vogliamo eseguirli contemporaneamente, dobbiamo chiamarli in sequenza? La risposta è no. Questi calcoli dovrebbero essere eseguiti solo se qualche altra funzione dipende da s1 e s2. Non abbiamo nemmeno bisogno di eseguirli finché ne abbiamo bisogno all'interno della concatenazione. Se invece di concatenare sostituiamo una funzione che, a seconda della condizione, usa uno dei due argomenti, allora il secondo argomento non deve nemmeno essere calcolato! Haskell è un esempio di linguaggio informatico pigro. Haskell non garantisce alcun ordinamento delle chiamate (per niente!), Perché Haskell esegue il codice secondo necessità.

La valutazione pigra ha diversi vantaggi e alcuni svantaggi. Nella prossima sezione, discuteremo i meriti e spiegherò come andare d'accordo con gli svantaggi.

Ottimizzazione

La valutazione pigra offre un enorme potenziale di ottimizzazione. Un compilatore pigro tratta il codice esattamente come un matematico studia le espressioni algebriche: può annullare alcune cose, annullare l'esecuzione di determinate sezioni del codice, modificare l'ordine delle chiamate per una maggiore efficienza, persino organizzare il codice in modo tale da ridurre il numero di errori, garantendo l'integrità del programma. Questo è il più grande vantaggio quando si descrive un programma con rigorose primitive formali: il codice obbedisce a leggi matematiche e può essere studiato con metodi matematici.

Astrazione delle strutture di controllo

La valutazione pigra fornisce un livello di astrazione così alto che diventano possibili cose incredibili. Ad esempio, immagina di implementare la seguente struttura di controllo:

A meno che (stock.isEuropean ()) (sendToSEC (stock);)
Vogliamo che la funzione sendToSEC venga eseguita solo se il fondo (azionario) non è europeo. Come puoi implementare a meno che? Senza una valutazione pigra, avremmo bisogno di un sistema macro, ma in linguaggi come Haskell, questo non è necessario. Possiamo dichiarare a meno che come una funzione!

Void a meno che (condizione booleana, codice elenco) (if (! Condizione) codice;)
Nota che il codice non verrà eseguito se condition == true. Nei linguaggi forti, questo comportamento non può essere ripetuto, poiché gli argomenti verranno valutati prima a meno che non venga chiamato.

Strutture dati infinite

I linguaggi pigri ti consentono di creare infinite strutture di dati, che sono molto più difficili da creare in linguaggi rigorosi [trans. - non in Python]. Ad esempio, immagina una sequenza di Fibonacci. Ovviamente, non possiamo calcolare una lista infinita in un tempo finito e conservarla comunque in memoria. In linguaggi forti come Java, scriveremmo semplicemente una funzione che restituisca un membro arbitrario di una sequenza. In linguaggi come Haskell, possiamo astrarre e dichiarare semplicemente un elenco infinito di numeri di Fibonacci. Poiché la lingua è pigra, verranno calcolate solo le parti necessarie dell'elenco che vengono effettivamente utilizzate nel programma. Ciò consente di astrarre da un gran numero di problemi e di osservarli da un livello superiore (ad esempio, è possibile utilizzare le funzioni di elaborazione di elenchi su sequenze infinite).

Screpolatura

Certo, il formaggio gratis è solo in una trappola per topi. La valutazione pigra presenta una serie di svantaggi. Questi sono principalmente gli svantaggi della pigrizia. In realtà, è spesso necessario un ordine di calcolo diretto. Prendiamo ad esempio il seguente codice:

In un linguaggio pigro, nessuno garantisce che la prima riga verrà eseguita prima della seconda! Questo significa che non possiamo fare I/O, non possiamo usare normalmente le funzioni native (dopotutto, devono essere chiamate in un certo ordine per tener conto dei loro effetti collaterali), e non possiamo interagire con il mondo esterno! Se introduciamo un meccanismo per snellire l'esecuzione del codice, allora perderemo il vantaggio del rigore matematico del codice (e quindi perderemo tutte le chicche della programmazione funzionale). Per fortuna non tutto è ancora perduto. I matematici si sono messi al lavoro e hanno escogitato alcuni trucchi per assicurarsi che le istruzioni fossero nell'ordine corretto senza perdere il loro spirito funzionale. Abbiamo il meglio di entrambi i mondi! Tali tecniche includono la continuazione, le monadi e la tipizzazione dell'unicità. In questo articolo lavoreremo con le continuazioni e rimanderemo le monadi e la digitazione univoca alla prossima volta. È interessante notare che la continuazione è una cosa molto utile, che viene utilizzata non solo per specificare un rigoroso ordine di calcoli. Parleremo anche di questo.

continuazioni

Le continuazioni della programmazione svolgono lo stesso ruolo del Codice Da Vinci nella storia umana: la sorprendente rivelazione del più grande mistero dell'umanità. Beh, forse non proprio così, ma sicuramente strappano i veli, dato che un tempo hai imparato a mettere la radice di -1.

Quando abbiamo esaminato le funzioni, abbiamo appreso solo metà della verità, perché siamo partiti dal presupposto che una funzione restituisca un valore alla funzione chiamante. In questo senso, la continuazione è una generalizzazione delle funzioni. La funzione non deve restituire il controllo al punto da cui è stata chiamata, ma può tornare in qualsiasi punto del programma. Continua è un parametro che possiamo passare a una funzione per indicare il punto di ritorno. Sembra molto più spaventoso di quanto non sia in realtà. Diamo un'occhiata al seguente codice:

Int i = somma (5, 10); int j = quadrato (i);
La funzione add restituisce il numero 15, che viene scritto in i, nel punto in cui è stata chiamata la funzione. Il valore di i viene quindi utilizzato nella chiamata al quadrato. Si noti che il compilatore pigro non può modificare l'ordine di valutazione, poiché la seconda riga dipende dal risultato della prima. Possiamo riscrivere questo codice usando il Continuation Passing Style (CPS) quando add restituisce un valore alla funzione square.

Int j = somma (5, 10, quadrato);
In questo caso, add riceve un argomento aggiuntivo, una funzione che verrà chiamata dopo che add avrà finito di funzionare. In entrambi gli esempi, j sarà 225.

Questa è la prima tecnica che permette di specificare l'ordine di esecuzione di due espressioni. Torniamo al nostro esempio di I/O.

System.out.println ("Inserisci il tuo nome:"); System.in.readLine ();
Queste due righe sono indipendenti l'una dall'altra e il compilatore è libero di cambiarne l'ordine a piacimento. Ma se lo riscriviamo in CPS, così facendo aggiungiamo la dipendenza richiesta e il compilatore dovrà eseguire calcoli uno dopo l'altro!

System.out.println ("Inserisci il tuo nome:", System.in.readLine);
In tal caso, println chiamerà readLine con il suo risultato e restituirà il risultato readLine alla fine. In questa forma, possiamo essere sicuri che queste funzioni verranno chiamate a turno e che readLine verrà chiamato del tutto (dopotutto, il compilatore si aspetta di ricevere il risultato dell'ultima operazione). Nel caso di Java, println restituisce void. Ma se venisse restituito un valore astratto (che può servire come argomento per readLine), allora questo risolverebbe il nostro problema! Naturalmente, l'allineamento di tali catene di funzioni compromette notevolmente la leggibilità del codice, ma è possibile combatterlo. Possiamo aggiungere elementi sintattici al nostro linguaggio che ci consentiranno di scrivere espressioni come al solito e il compilatore concatenerà automaticamente i calcoli. Ora possiamo eseguire calcoli in qualsiasi ordine senza perdere i vantaggi di FP (compresa la possibilità di studiare il programma utilizzando metodi matematici)! Se questo ti confonde, ricorda che le funzioni sono solo istanze di una classe con un singolo membro. Riscrivi il nostro esempio in modo che println e readLine siano entrambe istanze di classe in modo che tu possa capirlo meglio.

Ma i vantaggi dei sequel non finiscono qui. Possiamo scrivere un intero programma usando CPS, in modo che ogni funzione venga chiamata con un parametro aggiuntivo, una continuazione, in cui viene passato il risultato. In linea di principio, qualsiasi programma può essere tradotto in CPS, se si pensa a ciascuna funzione come a un caso speciale di continuazioni. Questa conversione può essere eseguita automaticamente (in effetti, molti compilatori lo fanno).

Non appena convertiamo il programma nella forma CPS, diventa chiaro che ogni istruzione ha una continuazione, la funzione in cui verrà passato il risultato, che in un normale programma sarebbe un call point. Prendiamo qualsiasi istruzione dall'ultimo esempio, ad esempio aggiungi (5,10). In un programma scritto in forma CPS, è chiaro quale sarà una continuazione: questa è una funzione che add chiamerà alla fine del lavoro. Ma quale sarà il seguito del programma non-CPS? Certo, possiamo convertire il programma in CPS, ma è necessario?

Si scopre che questo non è necessario. Dai un'occhiata da vicino alla nostra conversione CPS. Se inizi a scrivere un compilatore per esso, scoprirai che la versione CPS non ha bisogno di uno stack! Le funzioni non restituiscono mai nulla, nel senso tradizionale della parola "ritorno", chiamano semplicemente un'altra funzione, sostituendo il risultato dei calcoli. Non è necessario inserire (push) gli argomenti nello stack prima di ogni chiamata e poi riportarli indietro. Possiamo semplicemente memorizzare gli argomenti in un pezzo fisso di memoria e usare jump invece della normale chiamata. Non abbiamo bisogno di memorizzare gli argomenti originali, perché non ne avremo mai più bisogno, perché le funzioni non restituiscono nulla!

Pertanto, i programmi in stile CPS non necessitano di uno stack, ma contengono un argomento aggiuntivo, sotto forma di funzione da chiamare. I programmi non in stile CPS non hanno argomenti aggiuntivi, ma usano uno stack. Cosa viene memorizzato nello stack? Solo argomenti e un puntatore alla posizione di memoria in cui la funzione dovrebbe restituire. Bene, hai indovinato? Lo stack memorizza le informazioni sulle continuazioni! Un puntatore a un punto di ritorno sullo stack equivale a una funzione da chiamare nei programmi CPS! Per sapere quale estensione è la somma (5,10), è sufficiente prendere il punto di ritorno dalla pila.

Non è stato difficile. Una continuazione e un puntatore a un punto di ritorno sono in realtà la stessa cosa, solo la continuazione è specificata in modo esplicito e quindi potrebbe differire da dove è stata chiamata la funzione. Se ricordi che una continuazione è una funzione e una funzione nel nostro linguaggio è compilata in un'istanza di una classe, allora capirai che un puntatore a un punto di ritorno sullo stack e un puntatore a una continuazione sono in realtà la stessa cosa , perché la nostra funzione (come istanza di una classe ) è solo un puntatore. Ciò significa che in qualsiasi momento nel tuo programma, puoi richiedere la continuazione corrente (in effetti, le informazioni dallo stack).

Ok, ora abbiamo una buona idea di quale sia l'attuale sequel. Cosa significa? Se prendiamo la continuazione corrente e la salviamo da qualche parte, salviamo così lo stato attuale del programma - lo congeliamo. Questo è simile all'ibernazione del sistema operativo. L'oggetto di continuazione memorizza le informazioni necessarie per riprendere l'esecuzione del programma dal punto in cui è stato richiesto l'oggetto di continuazione. Il sistema operativo fa questo ai tuoi programmi tutto il tempo quando cambia contesto tra i thread. L'unica differenza è che tutto è sotto il controllo del sistema operativo. Se richiedi un oggetto di continuazione (in Scheme, questo viene fatto chiamando la funzione call-with-current-continuation), allora riceverai un oggetto con la continuazione corrente - lo stack (o nel caso di CPS - la funzione di la prossima chiamata). Puoi salvare questo oggetto in una variabile (o anche su disco). Se scegli di "riavviare" il programma con questa continuazione, lo stato del tuo programma viene "convertito" allo stato in cui si trovava quando è stato preso l'oggetto di continuazione. È come passare a un thread sospeso o riattivare il sistema operativo dopo l'ibernazione. Con l'eccezione che puoi farlo molte volte di seguito. Dopo che il sistema operativo si è riattivato, le informazioni sull'ibernazione vengono distrutte. In caso contrario, sarebbe possibile ripristinare lo stato del sistema operativo dallo stesso punto. È quasi come viaggiare nel tempo. Con i sequel, te lo puoi permettere!

In quali situazioni sono utili le continuazioni? Di solito se stai cercando di emulare lo stato nei sistemi senza di esso intrinsecamente. Le continuazioni sono molto utilizzate nelle applicazioni Web (come il framework Seaside Smalltalk). ASP.NET di Microsoft fa di tutto per mantenere lo stato tra le richieste e semplificarti la vita. Se C# supportava le continuazioni, la complessità di ASP.NET potrebbe essere ridotta della metà salvando la continuazione e ripristinandola alla richiesta successiva. Dal punto di vista di un programmatore Web, non ci sarebbero interruzioni: il programma continuerebbe sulla riga successiva! Le continuazioni sono un'astrazione incredibilmente utile per risolvere alcuni problemi. Con sempre più fat client tradizionali che si spostano sul Web, l'importanza dei sequel aumenterà solo nel tempo.

Corrispondenza del modello

Il pattern matching non è un'idea così nuova o innovativa. In effetti, ha poco a che fare con la programmazione funzionale. L'unico motivo per cui è spesso associato a FP è che per qualche tempo i linguaggi funzionali hanno pattern matching, ma quelli imperativi no.

Iniziamo la nostra conoscenza con il Pattern matching con il seguente esempio. Ecco la funzione per calcolare i numeri di Fibonacci in Java:

Int fib (int n) (if (n == 0) restituisce 1; if (n == 1) restituisce 1; restituisce fib (n - 2) + fib (n - 1);)
Ed ecco un esempio in un linguaggio simile a Java con supporto per il pattern matching

Int fib (0) (ritorno 1;) int fib (1) (ritorno 1;) int fib (int n) (ritorno fib (n - 2) + fib (n - 1);)
Qual è la differenza? Il compilatore esegue la ramificazione per noi.

Pensa, l'importanza è grande! In effetti, l'importanza non è grande. È stato notato che un gran numero di funzioni contiene complessi costrutti di switch (questo è in parte vero per i programmi funzionali) e si è deciso di evidenziare questo punto. La definizione della funzione è suddivisa in diverse varianti e il modello viene impostato al posto degli argomenti della funzione (è simile all'overload del metodo). Quando viene chiamata una funzione, il compilatore confronta al volo gli argomenti con tutte le definizioni e seleziona quella più appropriata. Di solito la scelta ricade sulla definizione di funzione più specializzata. Ad esempio int fib (int n) può essere chiamato quando n è 1, ma non lo farà, perché int fib (1) è una definizione più specializzata.

Il pattern matching è solitamente più complesso del nostro esempio. Ad esempio, il complesso sistema di Pattern matching permette di scrivere il seguente codice:

Int f (int n< 10) { ... } int f(int n) { ... }
Quando può essere utile il pattern matching? L'elenco di questi casi è sorprendentemente lungo! Ogni volta che si utilizzano costrutti if annidati complessi, la corrispondenza dei modelli può funzionare meglio con meno codice. Un buon esempio viene in mente con la funzione WndProc, che è implementata in ogni programma Win32 (anche se è nascosta al programmatore dietro un'alta recinzione di astrazioni). In genere, la corrispondenza dei modelli può persino controllare il contenuto delle raccolte. Ad esempio, se passi un array a una funzione, puoi selezionare tutti gli array in cui il primo elemento è 1 e il terzo elemento è maggiore di 3.

Un altro vantaggio della corrispondenza dei modelli è che se si apportano modifiche, non è necessario scavare in un'unica enorme funzione. Hai solo bisogno di aggiungere (o modificare) alcune definizioni di funzione. Quindi, ci liberiamo di un intero strato di schemi dal famoso libro della Banda dei Quattro. Più complesse e ramificate sono le condizioni, più utile sarà il pattern matching. Una volta che inizi a usarli, ti chiedi come avresti potuto farne a meno prima.

chiusure

Finora, abbiamo discusso le caratteristiche della FP nel contesto dei linguaggi "puramente" funzionali - linguaggi che sono l'implementazione del lambda calcolo e non contengono caratteristiche che contraddicono il sistema formale di Church. Tuttavia, molte caratteristiche dei linguaggi funzionali vengono utilizzate al di fuori del lambda calcolo. Sebbene l'implementazione del sistema assiomatico sia interessante dal punto di vista della programmazione in termini di espressioni matematiche, potrebbe non essere sempre applicabile nella pratica. Molte lingue preferiscono utilizzare elementi di linguaggi funzionali senza aderire a una rigida dottrina funzionale. Alcuni di questi linguaggi (ad esempio Common Lisp) non richiedono che le variabili siano definitive: i loro valori possono essere modificati. Non richiedono nemmeno che le funzioni dipendano solo dai loro argomenti: le funzioni possono accedere allo stato al di fuori del loro ambito. Tuttavia, includono anche funzionalità come funzioni di ordine superiore. Il passaggio di una funzione in un linguaggio non puro è leggermente diverso dall'operazione analoga all'interno del lambda calcolo e richiede una caratteristica interessante chiamata chiusura lessicale. Diamo un'occhiata al seguente esempio. Ricorda che in questo caso le variabili non sono definitive e la funzione può accedere a variabili al di fuori del suo ambito:

Funzione makePowerFn (int power) (int powerFn (int base) (return pow (base, power);) return powerFn;) Function square = makePowerFn (2); quadrato (3); // restituisce 9
La funzione make-power-fn restituisce una funzione che accetta un argomento e lo eleva a una potenza specifica. Cosa succede quando proviamo a valutare il quadrato (3)? La variabile power è fuori portata per powerFn perché makePowerFn è già uscito e il suo stack è stato distrutto. Come funziona il quadrato allora? Il linguaggio deve preservare in qualche modo il valore della potenza affinché la funzione quadrato funzioni. E se creiamo un'altra funzione cubo che eleva il numero alla terza potenza? La lingua dovrà memorizzare due valori di potenza per ogni funzione creata in make-power-fn. Il fenomeno della memorizzazione di questi valori è chiamato chiusura. La chiusura fa più che memorizzare gli argomenti della funzione top. Ad esempio, una chiusura potrebbe assomigliare a questa:

Funzione makeIncrementer () (int n = 0; int incremento () (return ++ n;)) Funzione inc1 = makeIncrementer (); Funzione inc2 = makeIncrementer (); inc1 (); // restituisce 1; inc1 (); // restituisce 2; inc1 (); // restituisce 3; inc2 (); // restituisce 1; inc2 (); // restituisce 2; inc2 (); // restituisce 3;
Durante l'esecuzione, i valori di n vengono salvati e i contatori vi hanno accesso. Inoltre, ogni contatore ha la propria copia di n, nonostante il fatto che dovrebbero essere scomparsi dopo l'esecuzione della funzione makeIncrementer. Come fa il compilatore a compilarlo? Cosa sta succedendo dietro le quinte delle chiusure? Per fortuna abbiamo un passaggio magico.

Tutto è fatto in modo abbastanza logico. A prima vista, è chiaro che le variabili locali non obbediscono più alle regole di ambito e la loro durata è indefinita. Ovviamente non sono più archiviati nello stack: devono essere conservati nell'heap. La chiusura viene quindi eseguita come una normale funzione di cui abbiamo discusso in precedenza, tranne per il fatto che ha un riferimento aggiuntivo alle variabili circostanti:

Classe some_function_t (SymbolTable parentScope; // ...)
Se la chiusura fa riferimento a una variabile che non è nell'ambito locale, prende in considerazione l'ambito padre. È tutto! La chiusura collega il mondo funzionale al mondo OOP. Ogni volta che crei una classe che memorizza uno stato e lo passi da qualche parte, ricorda le chiusure. Una chiusura è solo un oggetto che crea "attributi" al volo, portandoli fuori dall'ambito in modo da non doverlo fare da soli.

Ora cosa?

Questo articolo rappresenta solo la punta dell'iceberg della programmazione funzionale. Puoi scavare più a fondo e vedere qualcosa di veramente grande e, nel nostro caso, anche buono. In futuro, ho intenzione di scrivere sulla teoria delle categorie, le monadi, le strutture dati funzionali, il sistema dei tipi nei linguaggi funzionali, il multithreading funzionale, i database funzionali e molti altri. Se riesco a scrivere (e imparare strada facendo) circa la metà di questi argomenti, la mia vita non sarà sprecata. Fino ad allora, Google- il tuo fedele amico.

La programmazione funzionale implica il calcolo dei risultati delle funzioni dai dati iniziali e dei risultati di altre funzioni e non implica una memorizzazione esplicita dello stato del programma. Di conseguenza, non implica la mutabilità di questo stato (a differenza dell'imperativo, dove uno dei concetti di base è una variabile che memorizza il suo valore e consente di cambiarlo durante l'esecuzione dell'algoritmo).

In pratica, la differenza tra una funzione matematica e il concetto di "funzione" nella programmazione imperativa è che le funzioni imperative possono fare affidamento non solo su argomenti, ma anche sullo stato delle variabili esterne alla funzione, nonché avere effetti collaterali e modificare lo stato delle variabili esterne. Pertanto, nella programmazione imperativa, quando si chiama la stessa funzione con gli stessi parametri, ma in fasi diverse dell'esecuzione dell'algoritmo, è possibile ottenere dati di output diversi a causa dell'effetto dello stato delle variabili sulla funzione. E in un linguaggio funzionale, quando una funzione viene chiamata con gli stessi argomenti, otteniamo sempre lo stesso risultato: l'output dipende solo dall'input. Ciò consente agli ambienti di esecuzione di programmi in linguaggi funzionali di memorizzare nella cache i risultati delle funzioni e chiamarli in un ordine non determinato dall'algoritmo e parallelizzarli senza alcuna azione aggiuntiva da parte del programmatore (vedi sotto)

Linguaggi di programmazione funzionale

• LISP - (John McCarthy,) e molti dei suoi dialetti, i più moderni dei quali sono:
• Erlang - (Joe Armstrong,) un linguaggio funzionale con supporto per i processi.
• APL è il precursore dei moderni ambienti di calcolo scientifico come MATLAB.
• (Robin Milner, Standard ML e Objective CAML sono noti dei dialetti in uso oggi).
• - linguaggio funzionale della famiglia ML per la piattaforma .NET
• Miranda (David Turner, che in seguito sviluppò il linguaggio Haskell).
• Nemerle è un linguaggio ibrido funzionale/imperativo.
• Haskell è puramente funzionale. Prende il nome da Haskell Curry.

Le versioni iniziali non ancora completamente funzionanti di Lisp e APL hanno dato contributi speciali alla creazione e allo sviluppo della programmazione funzionale. Le versioni successive di Lisp come Scheme, così come varie versioni di APL, supportavano tutte le proprietà ei concetti di un linguaggio funzionale.

Di norma, l'interesse per i linguaggi di programmazione funzionale, specialmente quelli puramente funzionali, era più scientifico che commerciale. Tuttavia, linguaggi notevoli come Erlang, OCaml, Haskell, Scheme (dopo il 1986) e specific (statistica), Mathematica (matematica simbolica) e K (analisi finanziaria) e XSLT (XML) hanno trovato la loro strada nella programmazione commerciale industria. Linguaggi dichiarativi diffusi come SQL e Lex/Yacc contengono alcuni elementi di programmazione funzionale, ad esempio sono cauti nell'uso delle variabili. I linguaggi dei fogli di calcolo possono anche essere considerati funzionali, perché nelle celle dei fogli di calcolo è specificato un array di funzioni, di regola, che dipende solo da altre celle e se si desidera modellare le variabili, è necessario ricorrere alle capacità del linguaggio imperativo macro.

Storia

Il primo linguaggio funzionale è stato Lisp, creato da John McCarthy alla fine degli anni Cinquanta e implementato inizialmente per l'IBM 700/7000 (Inglese) russo ... Lisp ha introdotto molti dei concetti di un linguaggio funzionale, sebbene professi qualcosa di più del semplice paradigma di programmazione funzionale. Ulteriore sviluppo di Lisp sono stati linguaggi come Scheme e Dylan.

Concetti

Alcuni concetti e paradigmi sono specifici della programmazione funzionale e sono per lo più estranei alla programmazione imperativa (compresa la programmazione orientata agli oggetti). Tuttavia, i linguaggi di programmazione sono solitamente un ibrido di diversi paradigmi di programmazione, quindi i linguaggi di programmazione "prevalentemente imperativi" possono utilizzare alcuni di questi concetti.

Funzioni di ordine superiore

Le funzioni di ordine superiore sono funzioni che possono accettare come argomenti e restituire altre funzioni. I matematici spesso chiamano tale funzione un operatore, ad esempio l'operatore derivato o l'operatore integrale.

Le funzioni di ordine superiore consentono di utilizzare il currying, la trasformazione di una funzione da una coppia di argomenti in una funzione che accetta i suoi argomenti uno alla volta. Questa trasformazione ha preso il nome in onore di H. Curry.

Funzioni pure

Le funzioni che non hanno effetti collaterali di I/O e memoria sono chiamate funzioni pure (dipendono solo dai propri parametri e restituiscono solo il proprio risultato). Le funzioni pure hanno diverse proprietà utili, molte delle quali puoi usare per ottimizzare il tuo codice:

• Se il risultato di una funzione pura non viene utilizzato, può essere rimosso senza danneggiare altre espressioni.
• Il risultato di una chiamata a una funzione pura può essere memorizzato, ovvero archiviato in una tabella di valori insieme agli argomenti della chiamata. Se successivamente la funzione viene chiamata con gli stessi argomenti, il suo risultato può essere preso direttamente dalla tabella senza essere calcolato (a volte questo è chiamato principio di trasparenza dei riferimenti). La memorizzazione, al costo di un piccolo consumo di memoria, può aumentare significativamente le prestazioni e ridurre l'ordine di crescita di alcuni algoritmi ricorsivi.
• Se non vi è alcuna dipendenza dai dati tra due funzioni pure, l'ordine del loro calcolo può essere modificato o parallelizzato (in altre parole, il calcolo delle funzioni pure soddisfa i principi thread-safe)
• Se l'intero linguaggio non consente effetti collaterali, è possibile utilizzare qualsiasi criterio di calcolo. Questo dà al compilatore la libertà di combinare e riorganizzare la valutazione delle espressioni nel programma (ad esempio, per escludere strutture ad albero).

Sebbene la maggior parte dei compilatori per linguaggi di programmazione imperativi riconosca le funzioni pure e rimuova le sottoespressioni comuni per le chiamate di funzioni pure, non possono sempre farlo per le librerie precompilate, che generalmente non forniscono queste informazioni. Alcuni compilatori, come gcc, forniscono al programmatore parole chiave per indicare funzioni pure per scopi di ottimizzazione. Fortran 95 consente di designare le funzioni come "pure".

ricorsione

Le funzioni ricorsive possono essere generalizzate con funzioni di ordine superiore utilizzando, ad esempio, catamorfismo e anamorfismo (o "convoluzione" e "svolgimento"). Funzioni di questo tipo svolgono il ruolo di qualcosa come un ciclo nei linguaggi di programmazione imperativi.

Approccio alla valutazione degli argomenti

I linguaggi funzionali possono essere classificati in base a come vengono elaborati gli argomenti di una funzione durante la sua valutazione. Tecnicamente, la differenza sta nella semantica denotazionale dell'espressione. Ad esempio, con un approccio rigoroso alla valutazione dell'espressione

Stampa (len ([2 +1, 3 * 2, 1/0, 5 -4]))

l'output sarà un errore, poiché c'è una divisione per zero nel terzo elemento della lista. Con un approccio libero, il valore dell'espressione sarà 4, poiché per calcolare la lunghezza di un elenco, i valori dei suoi elementi, in senso stretto, non sono importanti e potrebbero non essere calcolati affatto. In rigoroso ordine di calcolo (applicativo), i valori di tutti gli argomenti vengono calcolati in anticipo prima di valutare la funzione stessa. Con un approccio libero (normale ordine di valutazione), i valori degli argomenti non vengono calcolati fino a quando non è necessario il loro valore durante la valutazione della funzione.

Di norma, viene implementato un approccio lassista sotto forma di una riduzione del grafico. Il calcolo fluente è l'impostazione predefinita in diversi linguaggi puramente funzionali, inclusi Miranda, Clean e Haskell.

FP in linguaggi non funzionali

In linea di principio, non ci sono ostacoli alla scrittura di programmi in stile funzionale in linguaggi che tradizionalmente non sono considerati funzionali, proprio come i programmi orientati agli oggetti possono essere scritti in linguaggi strutturati. Alcuni linguaggi imperativi supportano i costrutti tipici dei linguaggi funzionali, come le funzioni di ordine superiore e le comprensioni di lista, rendendo più semplice l'utilizzo dello stile funzionale in questi linguaggi. Un esempio potrebbe essere la programmazione funzionale in Python.

Stili di programmazione

I programmi imperativi tendono a enfatizzare la sequenza dei passaggi per eseguire alcune azioni, ei programmi funzionali alla disposizione e composizione delle funzioni, spesso non indicando l'esatta sequenza dei passaggi. Un semplice esempio di due soluzioni allo stesso problema (usando lo stesso linguaggio Python) lo illustra.

#stile imperativo obiettivo = # crea una lista vuota per elemento in source_list: # per ogni elemento della lista sorgente trans1 = G (elemento) # applica la funzione G() trans2 = F (trans1) # applica la funzione F() target.append (trans2) # aggiungi l'elemento trasformato all'elenco

La versione funzionale ha un aspetto diverso:

#stilefunzionale # I linguaggi FP hanno spesso una funzione compose () incorporata compose2 = lambda A, B: lambda x: A (B (x)) target = mappa (compose2 (F, G), source_list)

A differenza dello stile imperativo, che descrive i passaggi che portano a un obiettivo, lo stile funzionale descrive la relazione matematica tra i dati e un obiettivo.

Peculiarità

La caratteristica principale della programmazione funzionale, che determina sia i vantaggi che gli svantaggi di questo paradigma, è che implementa modello di calcolo senza stato... Se un programma imperativo in qualsiasi fase dell'esecuzione ha uno stato, cioè un insieme di valori di tutte le variabili, e produce effetti collaterali, allora un programma puramente funzionale non ha né tutto né parti dello stato e non produce effetti collaterali effetti. Ciò che viene fatto nei linguaggi imperativi assegnando valori alle variabili si ottiene nei linguaggi funzionali passando espressioni ai parametri delle funzioni. Una conseguenza immediata è che un programma puramente funzionale non può modificare i dati che già possiede, ma può solo generarne di nuovi copiando e/o espandendo quelli vecchi. La conseguenza dello stesso è l'abbandono dei loop a favore della ricorsione.

punti di forza

Miglioramento dell'affidabilità del codice

Il lato interessante del calcolo stateless è che il codice è più affidabile grazie alla struttura chiara e all'assenza della necessità di tenere traccia degli effetti collaterali. Qualsiasi funzione funziona solo con dati locali e funziona sempre con essi allo stesso modo, indipendentemente da dove, come e in quali circostanze viene chiamata. L'impossibilità di mutare i dati quando li si utilizza in punti diversi del programma elimina la comparsa di errori difficili da trovare (come, ad esempio, l'assegnazione accidentale di un valore errato a una variabile globale in un programma imperativo).

Comoda organizzazione dei test unitari

Poiché una funzione nella programmazione funzionale non può generare effetti collaterali, gli oggetti non possono essere modificati né all'interno dell'ambito né all'esterno (a differenza dei programmi imperativi, in cui una funzione può impostare una variabile esterna letta dalla seconda funzione). L'unico effetto della valutazione di una funzione è il risultato che restituisce e l'unico fattore che influisce sul risultato sono i valori degli argomenti.

Pertanto, è possibile testare ogni funzione in un programma semplicemente valutandola da diversi insiemi di valori di argomento. In questo caso, non devi preoccuparti di chiamare le funzioni nell'ordine corretto o della corretta formazione dello stato esterno. Se una qualsiasi funzione in un programma supera i test unitari, puoi essere sicuro della qualità dell'intero programma. Nei programmi imperativi la verifica del valore di ritorno di una funzione non è sufficiente: la funzione può modificare lo stato esterno, anch'esso da verificare, cosa che non dovrebbe essere eseguita nei programmi funzionali.

Capacità di ottimizzazione della compilazione

La caratteristica positiva tradizionalmente citata della programmazione funzionale è quella di consentire di descrivere un programma nella forma cosiddetta "dichiarativa", quando una sequenza rigida di esecuzione di molte operazioni necessarie per calcolare il risultato non è specificata esplicitamente, ma è generata automaticamente in il processo di calcolo delle funzioni. Questa circostanza, così come l'assenza di stati, consente di applicare metodi piuttosto complessi di ottimizzazione automatica a programmi funzionali.

Funzionalità di concorrenza

Un altro vantaggio dei programmi funzionali è che forniscono le più ampie possibilità per la parallelizzazione automatica dei calcoli. Poiché l'assenza di effetti collaterali è garantita, in qualsiasi chiamata di funzione è sempre possibile valutare due parametri diversi in parallelo: l'ordine in cui vengono valutati non può influire sul risultato della chiamata.

Screpolatura

Gli svantaggi della programmazione funzionale derivano dalle stesse caratteristiche. L'assenza di assegnazioni e la loro sostituzione con la generazione di nuovi dati porta alla necessità di un'allocazione costante e della liberazione automatica della memoria, quindi un garbage collector altamente efficiente diventa un componente obbligatorio nel sistema di esecuzione di un programma funzionale. Un modello di calcolo allentato porta a un ordine imprevedibile delle chiamate di funzione, che crea problemi nell'I/O, dove l'ordine delle operazioni è importante. Inoltre, è ovvio che le funzioni di input nella loro forma naturale (ad esempio getchar dalla libreria standard del linguaggio) non sono pure perché possono restituire valori diversi per gli stessi argomenti e sono necessari alcuni ritocchi per eliminarlo .

Per superare le carenze dei programmi funzionali, i primi linguaggi di programmazione funzionale includevano non solo mezzi puramente funzionali, ma anche meccanismi di programmazione imperativi (assegnazione, ciclo, "PROGN implicito" erano già in LISP). L'utilizzo di tali strumenti consente di risolvere alcuni problemi pratici, ma significa allontanarsi dalle idee (e dai vantaggi) della programmazione funzionale e scrivere programmi imperativi in ​​linguaggi funzionali. Nei linguaggi funzionali puri, questi problemi vengono risolti con altri mezzi, ad esempio, in Haskell, l'I/O viene implementato utilizzando le monadi, un concetto non banale mutuato dalla teoria delle categorie.

Guarda anche

• anamorfismo
• catamorfismo

Note (modifica)

1. A. Field, P. Harrison Programmazione funzionale: Per. dall'inglese - M.: Mir, 1993 .-- 637 p., Ill. ISBN 5-03-001870-0. P. 120 [Capitolo 6: Fondamenti matematici: -calcolo].
2. Indice della comunità di programmazione di Tiobe
3. Paul Huduck (Inglese) russo (settembre 1989). "Concezione, evoluzione e applicazione di linguaggi di programmazione funzionale" (PDF). Sondaggi ACM Computing 21 (3): 359-411. DOI: 10.1145 / 72551.72554.
4. Roger Penrose Capitolo 2: Lambda Calculus di Church // La nuova mente del re. Sui computer, il pensiero e le leggi della fisica = La nuova mente dell'imperatore: riguardo ai computer, alle menti e alle leggi della fisica. - Editoriale URSS, 2003 .-- ISBN 5-354-00005-X+ ristampa ISBN 978-5-382-01266-7; 2011 r.
5. McCarthy, John (giugno 1978). Storia di Lisp. In ACM SIGPLAN Conferenza sulla storia dei linguaggi di programmazione: 217-223. DOI: 10.1145 / 800025.808387.
6. , cap. 3.Lambda calcolo come linguaggio di programmazione
7. Nelle sue memorie, Herbert Simon (1991), Modelli della mia vita pp. 189-190 ISBN 0-465-04640-1 afferma che il suo, Al. Newell e Cliff Shaw che sono "spesso indicati come i genitori dell'intelligenza artificiale" per aver scritto il programma Logic Theorist (Inglese) russo dimostrando automaticamente il teorema di Principia Mathematica (Inglese) russo... Per raggiungere questo obiettivo, hanno dovuto inventare un linguaggio e un paradigma che, in retrospettiva, possono essere visti come programmazione funzionale.
8. Storia dei linguaggi di programmazione: IPL
9. XIV. Sessione APL // Storia del linguaggio di programmazione / Richard L. Wexelbblat. - Stampa accademica, 1981. - S. 661-693. - 749 pagg.
10. Scarica PDF: "Tecniche di programmazione funzionale, V. A. Potapenko" p. 8 "Funzioni di ordini superiori".
11. GCC, Dichiarazione degli attributi delle funzioni
12. XL Fortran per AIX, V13.1> Language Reference, procedure pure (Fortran 95)
13. Ottimizzazione della chiamata in coda

Ho sempre voluto scrivere una serie di articoli sulla programmazione funzionale per questa rivista e sono molto contento di averne finalmente avuto l'opportunità. Anche se la mia serie sull'analisi dei dati è tutt'altro che finita :). Non annuncerò i contenuti dell'intera serie, dirò solo che oggi parleremo di diversi linguaggi di programmazione che supportano lo stile funzionale e le corrispondenti tecniche di programmazione.

Linguaggi di programmazione che non tutti conoscono

Ho iniziato a programmare da bambino, e all'età di venticinque anni mi sembrava di sapere e capire tutto. La programmazione orientata agli oggetti è diventata una parte del mio cervello, ogni libro immaginabile sulla programmazione industriale è stato letto. Ma avevo ancora la sensazione di essermi perso qualcosa, qualcosa di molto sottile ed estremamente importante. Fatto sta che, come tanti negli anni Novanta, a scuola mi insegnavano a programmare in Pascal (eh si, gloria al Turbo Pascal 5,5! - ndr), poi c'era il C e il C++. Fortran University e poi Java come strumento principale al lavoro. Conoscevo Python e pochi altri linguaggi, ma era tutto sbagliato. E non ho avuto una formazione seria nel campo dell'informatica. Un giorno, durante un volo attraverso l'Atlantico, non riuscivo a dormire e volevo leggere qualcosa. In qualche modo magicamente avevo a portata di mano un libro sul linguaggio di programmazione Haskell. Mi sembra che sia stato allora che ho capito il vero significato dell'espressione "la bellezza richiede sacrificio".

Ora, quando la gente mi chiede come ho imparato Haskell, dico così: in aereo. Questo episodio ha cambiato il mio atteggiamento nei confronti della programmazione in generale. Naturalmente, dopo la prima conoscenza, molte cose non mi sembravano del tutto chiare. Ho dovuto sforzarmi e studiare la questione più a fondo. E si sa, dieci anni dopo, molti elementi funzionali sono entrati a far parte dei linguaggi industriali, funzioni lambda esiste già anche in Java, tipo inferenza- in C++, corrispondenza del modello- a Scala. Molte persone pensano che questa sia una sorta di svolta. E in questa serie di articoli ti parlerò delle tecniche di programmazione funzionale che utilizzano diversi linguaggi e delle loro caratteristiche.

Gli utenti di Internet fanno spesso tutti i tipi di elenchi e top per il divertimento del pubblico. Ad esempio, "un elenco di libri che dovresti leggere fino ai trent'anni". Se il mio compito fosse quello di fare un elenco di libri sulla programmazione che dovresti leggere fino a quando non ti sei girato un po' lì, allora il primo posto andrebbe sicuramente al libro di Abelson e Sassman "La struttura e l'interpretazione dei programmi per computer"... A volte mi sembra persino che il compilatore o l'interprete qualunque il linguaggio dovrebbe fermare chiunque non abbia letto questo libro.

Quindi, se esiste un linguaggio con cui iniziare a conoscere la programmazione funzionale, è Lisp. In generale, questa è un'intera famiglia di linguaggi, che include un linguaggio che è abbastanza popolare ora per la JVM chiamato Clojure... Ma come primo linguaggio funzionale, non è particolarmente adatto. Per questo è meglio usare la lingua schema, che è stato sviluppato al MIT e fino alla metà degli anni 2000 è stato il linguaggio principale per l'insegnamento della programmazione. Sebbene il corso introduttivo con lo stesso titolo del libro in questione sia stato ora sostituito da un corso Python, è ancora rilevante.

Cercherò di parlare brevemente del linguaggio Scheme e, in generale, dell'idea alla base dei linguaggi di questo gruppo. Nonostante il fatto che Lisp sia molto antico (di tutti i linguaggi di alto livello, solo Fortran è più vecchio), è stato in esso che molti dei metodi di programmazione utilizzati oggi sono diventati disponibili per la prima volta. In quanto segue, userò il nome Lisp per fare riferimento a un'implementazione specifica, Scheme.

Sintassi in due minuti

La sintassi in Lisp è, uh, un po' controversa. Il fatto è che l'idea alla base della sintassi è estremamente semplice ed è costruita sulla base del cosiddetto S-espressioni... Questa è una notazione di prefisso in cui l'espressione 2 + 3 a cui sei abituato è scritta come (+ 2 3). Può sembrare strano, ma in pratica offre alcune possibilità in più. A proposito, anche (+ 2 10 (* 3.14 2)) funziona :). Pertanto, l'intero programma è una raccolta di elenchi che utilizzano la notazione del prefisso. Nel caso di Lisp, il programma stesso e l'albero della sintassi astratta - "se sai cosa intendo" - non sono essenzialmente diversi. Questa notazione rende l'analisi dei programmi Lisp molto semplice.
Dato che stiamo parlando di un linguaggio di programmazione, allora va detto come definire le funzioni in questo linguaggio.

Qui occorre fare una piccola digressione. C'è una sottigliezza, il cui significato è sottovalutato nella letteratura moderna. È tuttavia necessario separare la funzione in senso matematico e la funzione, come la intendiamo nella programmazione funzionale. Il fatto è che in matematica le funzioni sono oggetti dichiarativi, mentre in programmazione servono per organizzare il processo di calcolo, cioè, in un certo senso, sono conoscenze piuttosto imperative, conoscenze che rispondono alla domanda "come?" Ecco perché Abelson e Sussman nel loro libro separano molto attentamente questo e chiamano funzioni nelle procedure di programmazione. Questo non è accettato nella moderna letteratura sulla programmazione funzionale. Ma ti consiglio comunque vivamente di separare questi due significati della parola "funzione" almeno nella tua testa.

Il modo più semplice per definire una funzione è scrivere il codice seguente. Cominciamo con l'oscenamente semplice:

(definire (radici quadrati a b c) (let ((D (- (* b b) (* 4 a c)))) (se (< D 0) (list) (let ((sqrtD (sqrt D))) (let ((x1 (/ (- (- b) sqrtD) (* 2.0 a))) (x2 (/ (+ (- b) sqrtD) (* 2.0 a)))) (list x1 x2))))))

Sì, questo è esattamente quello che pensavi: risolvere un'equazione quadratica in Scheme. Ma questo è più che sufficiente per distinguere tutte le caratteristiche della sintassi. Qui sq-roots è il nome di una funzione da tre parametri formali.

A prima vista, ci sono troppe parentesi nel costrutto let usato per definire le variabili locali. Ma non è questo il caso, definiamo prima l'elenco delle variabili e poi l'espressione in cui vengono utilizzate queste variabili. Qui (elenco) è un elenco vuoto che viene restituito quando non ci sono radici e (elenco x1 x2) è un elenco di due valori.

Ora sulle espressioni. Nella nostra funzione sq-roots, abbiamo usato il costrutto if. È qui che entra in gioco la programmazione funzionale.

Il punto è che, a differenza dei linguaggi imperativi come il C, nei linguaggi funzionali if è un'espressione, non un operatore. In pratica, ciò significa che non può avere un altro ramo. Perché l'espressione dovrebbe sempre contare.

Non puoi parlare di sintassi senza parlarne zucchero sintattico... Nei linguaggi di programmazione, lo zucchero sintattico è chiamato costrutto che non è necessario, ma rende solo il codice più facile da leggere e riutilizzare. Cominciamo con un classico esempio dal linguaggio C. Molte persone sanno che gli array non sono un mezzo di espressione richiesto, poiché ci sono dei puntatori. Sì, in effetti, gli array sono implementati tramite puntatori e a [i] per il linguaggio C è uguale a * (a + i). Questo esempio è generalmente abbastanza insolito, con un effetto divertente associato ad esso: poiché l'operazione di addizione rimane commutativa nel caso dei puntatori, l'ultima espressione è la stessa di * (i + a), e questo può essere ottenuto rimuovendo lo zucchero sintattico dalle espressioni i [a]! L'operazione per rimuovere lo zucchero sintattico in inglese si chiama una parola speciale desugare.

Tornando al linguaggio Scheme, c'è un importante esempio di zucchero sintattico. Per definire le variabili, come nel caso delle funzioni, si usa la parola chiave (in Lisp e Scheme questa è chiamata una forma speciale) define. Ad esempio, (definire pi 3.14159) definisce la variabile pi. In generale, puoi definire le funzioni allo stesso modo:

(definire quadrato (lambda (x) (* x x)))

questo è lo stesso di

(definire (quadrato x) (* x x))

L'ultima riga sembra un po' più leggibile rispetto all'espressione lambda. Tuttavia, è chiaro che è sufficiente avere la prima opzione e la seconda è facoltativa. Perché il primo è più importante? Perché una delle proprietà più basilari dei linguaggi funzionali è che le funzioni in essi contenute sono oggetti di prima classe. Quest'ultimo significa che le funzioni possono essere passate come argomento e restituite come valore.

Se guardi let dal punto di vista di un'espressione lambda, puoi facilmente vedere la seguente corrispondenza:

(let ((x 5) (y 2)) (* x y)) (applica (lambda (x y) (* x y)) (lista 5 2))

Programmazione funzionale

I linguaggi funzionali sono pulito e sporco... I linguaggi funzionali puri sono relativamente rari, questi includono principalmente Haskell e Pulito... Non ci sono effetti collaterali nelle lingue pure. In pratica questo significa che non c'è assegnazione e I/O nella forma a cui siamo abituati. Ciò crea una serie di difficoltà, sebbene nelle lingue già menzionate ciò sia risolto in modo abbastanza intelligente e in queste lingue scrivono codice con molto I / O. Linguaggi come Lisp, OCaml o Scala consentono funzioni con effetti collaterali e, in tal senso, questi linguaggi sono spesso più pratici.

Il nostro compito è apprendere le tecniche di base della programmazione funzionale in Scheme. Pertanto, scriveremo codice puramente funzionale, senza utilizzare il generatore di numeri casuali, I/O e la funzione set! , che consentirà di modificare i valori delle variabili. Puoi leggere tutto questo nel libro. SICP... Ora soffermiamoci sul più essenziale per noi.

La prima cosa che confonde un principiante nella programmazione funzionale è la mancanza di loop. Ma per quanto riguarda? A molti di noi viene insegnato che la ricorsione è un male. Ciò è sostenuto dal fatto che la ricorsione nei linguaggi di programmazione convenzionali è solitamente implementata in modo inefficiente. Il punto è che, nel caso generale, si dovrebbe distinguere tra ricorsione come tecnica, cioè chiamare una funzione da se stessa, e ricorsione come processo. I linguaggi funzionali supportano l'ottimizzazione della ricorsione della coda o, come si dice a volte, la ricorsione dell'accumulatore. Questo può essere illustrato con un semplice esempio.

Abbiamo due funzioni: succ e prev. Il primo restituisce un numero 1 in più rispetto all'argomento e il secondo restituisce 1 in meno. Proviamo ora a definire l'operazione di addizione in due modi:

(define (add xy) (if (eq? y 0) x (add (succ x) (prev y)))) (define (add-1 xy) (if (eq? y 0) x (succ (add- 1 x (precedente)))))

Qual è la differenza tra il primo e il secondo caso? Il fatto è che se consideriamo il metodo di calcolo per il primo caso in passaggi, puoi vedere quanto segue:

(aggiungi 3 4) => (aggiungi 4 3) => (aggiungi 5 2) => (aggiungi 6 1) => (aggiungi 7 0) => 7

Nel secondo caso avremo qualcosa del genere:

(add-1 3 4) => (succ (add-1 3 3)) => (succ (succ (add-1 3 2))) => (succ (succ (succ (add-1 3 1)) )) => (succ (succ (succ (succ (add-1 3 0))))) => (succ (succ (succ (succ 3)))) => (succ (succ (succ 4))) => (succ (succ 5)) => (succ 6) => 7

Nonostante il fatto che in entrambi i casi il risultato sia lo stesso, il processo di calcolo è fondamentalmente diverso. Nel primo caso, la quantità di memoria utilizzata non cambia e nel secondo cresce linearmente. Il primo processo è iterativo, e secondo - ricorsivo... Quindi, per scrivere programmi efficienti in linguaggi funzionali, è necessario utilizzare la ricorsione in coda per evitare l'overflow dello stack.

Elenchi

Uno degli elementi più importanti della programmazione funzionale, insieme alla ricorsione, è le liste... Forniscono la base per strutture dati complesse. Come con altri linguaggi funzionali, gli elenchi sono collegati singolarmente in modo testa e coda. La funzione cons viene utilizzata per creare l'elenco e le funzioni car e cdr vengono utilizzate per accedere rispettivamente all'inizio e alla fine dell'elenco. Quindi, la lista (list 1 2 3) non è altro che (cons 1 (cons 2 (cons 3 "()))). Qui" () è una lista vuota. Pertanto, una tipica funzione di elaborazione dell'elenco ha il seguente aspetto:

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst))))))

Questa funzione somma semplicemente gli elementi della lista. Ecco come appaiono molte funzioni di elaborazione delle liste, in un prossimo articolo spiegherò perché. Per ora, nota solo che se sostituiamo il primo argomento in aggiunta con 1, otteniamo una funzione che calcola la lunghezza dell'elenco.

Funzioni di ordine superiore

Poiché le funzioni possono essere passate come argomenti e restituite come valori, è una buona idea trovare un uso per questo. Considera il seguente esempio classico:

(define (map f lst) (if (null? lst) lst (cons (f (car lst)) (map f (cdr lst))))))

La funzione map applica la funzione f a ogni elemento nell'elenco. Per quanto strano possa sembrare, ora possiamo esprimere la funzione per calcolare la lunghezza della lunghezza della lista in termini di somma e mappa:

(define (length lst) (sum (map (lambda (x) 1) lst)))

Se all'improvviso hai deciso che tutto questo è in qualche modo troppo semplice, allora pensiamo a questo: come realizzare un'implementazione di elenchi utilizzando funzioni di ordine superiore?

Cioè, devi implementare le funzioni cons, car e cdr in modo che soddisfino la seguente relazione: per qualsiasi lista lst, è vero che il valore (cons (car lst) (cdr lst)) è lo stesso di lst . Questo può essere fatto come segue:

(define (cons x xs) (lambda (pick) (if (eq? pick 1) x xs))) (define (car f) (f 1)) (define (cdr f) (f 2))

Come funziona? Qui la funzione cons restituisce un'altra funzione che ha un parametro e, a seconda di questo, restituisce il primo o il secondo argomento. È facile verificare che il rapporto richiesto sia soddisfatto per queste funzioni.

Utilizzo di quote e metaprogrammazione

Una bella caratteristica del linguaggio Lisp lo rende incredibilmente conveniente per scrivere programmi che convertono altri programmi. Il punto è che un programma è costituito da elenchi e un elenco è la struttura dati principale nel linguaggio. C'è un modo per "citare" semplicemente il testo del programma in modo che venga percepito come un elenco di atomi.

Atomi sono solo espressioni di caratteri, ad esempio ("ciao" mondo), che è lo stesso di "(ciao mondo), o in forma completa (citazione (ciao mondo)). Sebbene la maggior parte dei dialetti Lisp abbia stringhe , a volte puoi cavartela con quote. Ancora più importante, questo approccio può semplificare la generazione del codice e l'elaborazione del programma.

Per prima cosa, proviamo a capire i calcoli simbolici. Di solito, questo è inteso come un sistema di computer algebra in grado di gestire oggetti simbolici, formule, equazioni e altri oggetti matematici complessi (ce ne sono molti di questi sistemi, i principali esempi sono i sistemi acero e matematica).

Puoi provare a implementare la differenziazione simbolica. Penso che tutti coloro che sono vicini al diploma di scuola superiore immaginino le regole della differenziazione (anche se in realtà tutto è un po 'più complicato - qui calcoleremo la derivata parziale, considerando semplicemente le altre variabili come costanti, ma questo non complica l'essenza della questione affatto).

Quindi ti darò solo un codice di esempio che mostrerebbe l'essenza della questione, lasciando i dettagli al lettore (che, spero, studierà attentamente il libro "La struttura e l'interpretazione dei programmi per computer").

(define (deriv exp var) (cond ((numero? exp) 0) ((variable? exp) (if (stessa variabile? exp var) 1 0)) ((sum? exp) (make-sum (deriv ( addend exp) var) (deriv (augend exp) var))) ((product? exp) (make-sum (make-product (moltiplicatore exp) (deriv (moltiplicand exp) var)) (make-product (deriv (moltiplicatore) exp) var) (multiplicand exp)))) (else (errore "tipo di espressione sconosciuto - DERIV" exp))))

Qui la funzione deriva è l'implementazione dell'algoritmo di differenziazione come si fa a scuola. Questa funzione richiede l'implementazione del numero? , variabile? e così via, che permettono di comprendere quale natura abbia questo o quell'elemento espressivo. È inoltre necessario implementare funzioni aggiuntive make-product e make-sum. Qui usiamo il cond di costruzione, che ci è ancora sconosciuto, che è un analogo dell'istruzione switch nei linguaggi di programmazione come C e Java.

Prima di passare all'implementazione delle funzionalità mancanti, vale la pena notare che la programmazione funzionale spesso utilizza un approccio allo sviluppo dall'alto verso il basso. Questo è quando vengono scritte prima le funzioni più generali e poi le piccole funzioni responsabili dei dettagli di implementazione.

(define (variabile? x) (simbolo? x)) (define (stessa variabile? v1 v2) (and (variabile? v1) (variabile? v2) (eq? v1 v2))) (define (make-sum a1 a2) (lista "+ a1 a2)) (definisci (marca-prodotto m1 m2) (lista" * m1 m2)) (definisci (somma? x) (e (coppia? x) (eq? (auto x) "+ ))) (define (addend s) (cadr s)) (define (augend s) (caddr s)) (define (prodotto? x) (e (coppia? x) (eq? (auto x) "*)) ) (definisci (moltiplicatore p) (cadr p)) (definisci (moltiplicando p) (cadr p))

L'implementazione di queste funzioni non richiede commenti particolari, con la possibile eccezione delle funzioni cadr e caddr. Queste non sono altro che funzioni che restituiscono rispettivamente il secondo e il terzo elemento dell'elenco.

Se utilizzi l'interprete Scheme interattivo, puoi facilmente assicurarti che il codice risultante funzioni correttamente, ma senza semplificare le espressioni:

(deriv "(+ x 3)" x) => (+ 1 0) (deriv "(* (* xy) (+ x 3))" x) => (+ (* (* xy) (+ 1 0 )) (* (+ (* x 0) (* 1 a)) (+ x 3)))

Per casi banali (ad esempio, moltiplicazione per 0), il problema della semplificazione è abbastanza facile da risolvere. Questa domanda è lasciata al lettore. La maggior parte degli esempi in questo articolo sono presi dal libro SICP, quindi in caso di difficoltà puoi semplicemente fare riferimento alla fonte (il libro è di pubblico dominio).

Come ogni dialetto, Lisp ha grandi capacità di metaprogrammazione, principalmente legate all'uso delle macro. Sfortunatamente, questo problema richiede un'analisi in un articolo separato.

Scriviamo una funzione che rimuova lo zucchero sintattico dalla definizione della funzione come discusso in precedenza:

(define (desugar-define def) (let ((fn-args (cadr def)) (body (cadr def))) (let ((name (car fn-args)) (args (cdr fn-args))) (list "define name (list" lambda args body)))))

Questa funzione funziona alla grande con definizioni di funzioni ben formate:

(desugar-define "(define (succ x) (+ x 1))) => (define succ (lambda (x) (+ x 1)))

Tuttavia, questo non funziona per definizioni normali come (definire x 5).
Se vogliamo rimuovere lo zucchero sintattico in un grande programma contenente molte definizioni diverse, dobbiamo implementare un controllo aggiuntivo:

(define (zuccherato? def) (and (eq? (car def) "define) (list? (cadr def))))

Tale controllo può essere integrato direttamente nella funzione desugar-define, facendo in modo che se la definizione non ha bisogno di rimuovere lo zucchero sintattico, semplicemente non cambia (questo banale esercizio rimane per il lettore). Quindi puoi avvolgere l'intero programma in un elenco e utilizzare map:

(mappa dezugar-definisci prog)

Conclusione

In questo articolo, non mi sono posto il compito di raccontare Scheme in alcun dettaglio. Prima di tutto, volevo mostrare alcune caratteristiche interessanti del linguaggio e attirare il lettore allo studio della programmazione funzionale. Questo meraviglioso linguaggio, per tutta la sua semplicità, ha il suo fascino e caratteristiche che rendono la programmazione molto divertente. Per quanto riguarda lo strumento per lavorare con Scheme, i forti di spirito possono oscillare a Schema MIT e il resto: usa il fantastico ambiente di apprendimento Dott. Racchetta... In uno dei seguenti articoli, ti mostrerò sicuramente come scrivere il tuo interprete Scheme.

Calcolo pigro

Nei linguaggi di programmazione tradizionali (come C++), una chiamata di funzione valuta tutti gli argomenti. Questo metodo per chiamare una funzione è chiamato call-by-value. Se un argomento non è stato utilizzato nella funzione, il risultato dei calcoli viene perso, quindi i calcoli sono stati sprecati. In un certo senso, l'opposto di call-by-value è call-by-value. In questo caso, l'argomento viene valutato solo se è necessario per calcolare il risultato. Un esempio di questo comportamento è l'operatore di congiunzione, tutto dello stesso C++ (&&), che non calcola il valore del secondo argomento se il primo argomento è falso.

Se un linguaggio funzionale non supporta il calcolo pigro, viene chiamato rigoroso. In tali lingue, infatti, l'ordine di valutazione è rigorosamente definito. Esempi di linguaggi rigorosi includono Scheme, Standard ML e Caml.

Le lingue che usano la valutazione pigra sono chiamate lassiste. Haskell è un linguaggio sciolto, proprio come Gofer e Miranda, per esempio. Le lingue lassiste sono spesso pure.

Molto spesso, i linguaggi rigorosi includono un mezzo per supportare alcune funzionalità utili inerenti ai linguaggi non rigorosi, come gli elenchi infiniti. Standard ML viene fornito con un modulo speciale per supportare il calcolo posticipato. E Objective Caml supporta anche la parola riservata aggiuntiva pigro e costrutti per elenchi di valori necessari.

Questa sezione fornisce una breve descrizione di alcuni (pochissimi) linguaggi di programmazione funzionali.

§ Lisp(Elenco elaboratore). È considerato il primo linguaggio di programmazione funzionale. Utipato. Contiene molte proprietà imperative, ma in generale incoraggia lo stile funzionale della programmazione. Utilizza call-by-value nei calcoli. Esiste un dialetto orientato agli oggetti della lingua: CLOS.

§ NUOTO(Se capisci cosa intendo). Un prototipo di linguaggio funzionale. Sviluppato da Landin negli anni '60 del XX secolo per dimostrare cosa può essere un linguaggio di programmazione funzionale. Insieme al linguaggio, Landin ha anche sviluppato una macchina virtuale speciale per eseguire programmi su ISWIM. Questa macchina virtuale chiamata per valore è chiamata macchina SECD. La sintassi del linguaggio ISWIM è la base per la sintassi di molti linguaggi funzionali. La sintassi di ML è simile alla sintassi ISWIM, in particolare Caml.

§ schema... Un dialetto Lisp destinato alla ricerca scientifica nel campo dell'informatica. Durante lo sviluppo di Scheme, l'accento è stato posto sull'eleganza e la semplicità del linguaggio. Questo rende la lingua molto più piccola del Common Lisp.

§ ML(Metalingua). Una famiglia di linguaggi rigorosi con un sistema di tipo polimorfico avanzato e moduli parametrizzabili. Il ML viene insegnato in molte università occidentali (alcune anche come primo linguaggio di programmazione).

§ Standard ML... Uno dei primi linguaggi di programmazione funzionale tipizzati. Contiene alcune proprietà imperative, come i riferimenti a valori modificabili, e quindi non è pulito. Utilizza call-by-value nei calcoli. Un'implementazione molto interessante della modularità. Potente sistema di tipo polimorfico. L'ultimo standard del linguaggio è lo Standard ML-97, per il quale esistono definizioni matematiche formali della sintassi, nonché semantica statica e dinamica del linguaggio.

§ Luce di cammello e Obiettivo Caml... Come Standard ML appartiene alla famiglia ML. Obiettivo Caml differisce da Caml Light principalmente nel supporto per la classica programmazione orientata agli oggetti. Simile a Standard ML, è rigoroso, ma ha un supporto integrato per la valutazione pigra.

§ Miranda... Sviluppato da David Turner come linguaggio funzionale standard utilizzando il calcolo pigro. Ha un rigoroso sistema di tipo polimorfico. Come ML, viene insegnato in molte università. Ha avuto una grande influenza sugli sviluppatori del linguaggio Haskell.

§ Haskell... Una delle lingue lassiste più comuni. Ha un sistema di digitazione molto sviluppato. Il sistema dei moduli è un po' meno sviluppato. L'ultimo standard linguistico è Haskell-98.

§ Gofer(Buono per il ragionamento equazionale). Un dialetto semplificato di Haskell. Progettato per insegnare la programmazione funzionale.

§ Pulito... Appositamente progettato per la programmazione parallela e distribuita. La sintassi è simile a quella di Haskell. Pulito. Utilizza calcoli pigri. Il compilatore viene fornito con un set di librerie I/O che consentono di programmare un'interfaccia utente grafica sotto Win32 o MacOS.

Ricordiamo che la caratteristica più importante dell'approccio funzionale è il fatto che qualsiasi programma sviluppato in un linguaggio di programmazione funzionale può essere considerato come una funzione, i cui argomenti possono essere anche funzioni.

L'approccio funzionale ha dato origine a un'intera famiglia di linguaggi, il cui antenato, come già notato, era il linguaggio di programmazione LISP. Successivamente, negli anni '70, è stata sviluppata la versione originale del linguaggio ML, che successivamente si è sviluppata, in particolare, in SML, oltre a una serie di altri linguaggi. Di questi, forse il più "giovane" è il linguaggio Haskell, nato abbastanza di recente, negli anni '90.

Un importante vantaggio dell'implementazione di linguaggi di programmazione funzionale è l'allocazione dinamica automatizzata della memoria del computer per l'archiviazione dei dati. Allo stesso tempo, il programmatore elimina la necessità di controllare i dati e, se necessario, può eseguire la funzione "raccolta spazzatura" - pulendo la memoria di quei dati che il programma non ha più bisogno.

Nell'approccio funzionale, i programmi complessi sono costruiti aggregando funzioni. In questo caso, il testo del programma è una funzione, alcuni dei cui argomenti possono essere considerati funzioni. Pertanto, il riutilizzo del codice si riduce alla chiamata della funzione precedentemente descritta, la cui struttura, contrariamente alla procedura del linguaggio imperativo, è matematicamente trasparente.

Poiché la funzione è un formalismo naturale per i linguaggi di programmazione funzionale, l'implementazione di vari aspetti della programmazione relativi alle funzioni è notevolmente semplificata. La scrittura di funzioni ricorsive diventa intuitivamente trasparente, ad es. funzioni che chiamano se stesse come argomento. Diventa anche naturale implementare l'elaborazione di strutture dati ricorsive.

A causa dell'implementazione del meccanismo di corrispondenza dei modelli, i linguaggi di programmazione funzionale come ML e Haskell sono utili per l'elaborazione simbolica.

Naturalmente, i linguaggi di programmazione funzionale non sono privi di alcuni inconvenienti.

Spesso questi includono una struttura del programma non lineare e un'efficienza di attuazione relativamente bassa. Tuttavia, il primo inconveniente è piuttosto soggettivo e il secondo è stato superato con successo dalle moderne implementazioni, in particolare da alcuni degli ultimi traduttori del linguaggio SML, incluso un compilatore per l'ambiente Microsoft .NET.

Lo sviluppo di software professionale in linguaggi di programmazione funzionale richiede una profonda comprensione della natura di una funzione.

Si noti che il termine "funzione" nella formalizzazione matematica e nell'implementazione del software significa concetti diversi.

Quindi, una funzione matematica f con un dominio di definizione A e un intervallo di valori B è l'insieme delle coppie ordinate

tale che se

(a, b 1) f e (a, b 2) f,

A sua volta, una funzione in un linguaggio di programmazione è una costruzione di questo linguaggio che descrive le regole per convertire un argomento (il cosiddetto parametro effettivo) in un risultato.

Per formalizzare il concetto di "funzione", è stata costruita una teoria matematica, nota come lambda calcolo. Più precisamente, questo calcolo dovrebbe essere chiamato calcolo delle conversioni lambda.

La conversione è intesa come la trasformazione di oggetti di calcolo (e nella programmazione - funzioni e dati) da una forma all'altra. La sfida originale in matematica era sforzarsi di semplificare la forma delle espressioni. In programmazione, questo particolare compito non è così essenziale, anche se, come vedremo in seguito, l'uso del lambda calcolo come formalizzazione iniziale può aiutare a semplificare il tipo di programma, ad es. portare all'ottimizzazione del codice del programma.

Inoltre, le conversioni forniscono un passaggio alle designazioni di nuova introduzione e, quindi, consentono di rappresentare l'area disciplinare in una forma più compatta o più dettagliata, o, in termini matematici, di modificare il livello di astrazione rispetto all'area disciplinare. Questa possibilità è ampiamente utilizzata anche dai linguaggi di programmazione orientata agli oggetti e strutturalmente modulari nella gerarchia di oggetti, frammenti di programma e strutture dati. L'interazione dei componenti dell'applicazione in .NET si basa sullo stesso principio. È in questo senso che il passaggio a nuove designazioni è uno degli elementi più importanti della programmazione in generale, ed è il lambda calcolo (a differenza di molti altri rami della matematica) che è un modo adeguato per formalizzare le ridenominazioni.

Sistemiamo l'evoluzione delle teorie alla base dell'approccio moderno al lambda calcolo.

Considera l'evoluzione dei linguaggi di programmazione che si sviluppano nell'ambito dell'approccio funzionale.

I primi linguaggi di programmazione funzionale, che hanno origine dal classico linguaggio LISP (LIST Processing), erano progettati per elaborare le liste, cioè. informazioni simboliche. Allo stesso tempo, i tipi principali erano un elemento atomico e un elenco di elementi atomici e l'enfasi principale era sull'analisi del contenuto dell'elenco.

Lo sviluppo dei primi linguaggi di programmazione erano linguaggi di programmazione funzionali con tipizzazione forte, un tipico esempio qui è il classico ML e il suo diretto discendente SML. Nei linguaggi fortemente tipizzati, ogni costrutto (o espressione) deve avere un tipo.

Tuttavia, nei successivi linguaggi di programmazione funzionale non è necessaria l'inferenza esplicita del tipo e i tipi di espressioni inizialmente non definite, come in SML, possono essere dedotti (prima dell'avvio del programma) in base ai tipi di espressioni ad essi associati.

Il passo successivo nello sviluppo dei linguaggi di programmazione funzionale è stato il supporto delle funzioni polimorfiche, ad es. funzioni con argomenti parametrici (analoghi di una funzione matematica con parametri). In particolare, il polimorfismo è supportato nei linguaggi SML, Miranda e Haskell.

Allo stato attuale dello sviluppo, sono emersi linguaggi di programmazione funzionale della "nuova generazione" con le seguenti caratteristiche avanzate: pattern matching (Scheme, SML, Miranda, Haskell), polimorfismo parametrico (SML) e il cosiddetto "lazy " (se necessario) calcolo (Haskell, Miranda, SML).

La famiglia dei linguaggi di programmazione funzionale è piuttosto numerosa. Ciò è evidenziato non tanto dall'elenco significativo dei linguaggi, quanto dal fatto che molti linguaggi hanno dato origine a intere direzioni nella programmazione. Ricordiamo che LISP ha dato origine a un'intera famiglia di linguaggi: Scheme, InterLisp, COMMON Lisp, ecc.

Il linguaggio di programmazione SML non ha fatto eccezione, creato sotto forma di ML da R. Milner al MIT (Massachusetts Institute of Technology) ed era originariamente destinato all'inferenza logica, in particolare, alla dimostrazione di teoremi. Il linguaggio è fortemente tipizzato e manca di polimorfismo parametrico.

Tre linguaggi moderni con capacità praticamente identiche (polimorfismo parametrico, corrispondenza di modelli, calcoli "pigri") sono diventati contemporaneamente lo sviluppo del "classico" ML. Questo è il linguaggio SML sviluppato nel Regno Unito e negli Stati Uniti, CaML, creato da un gruppo di scienziati francesi presso l'INRIA Institute, SML / NJ è un dialetto SML del New Jersey e uno sviluppo russo - mosml (dialetto "Mosca" ML ).

La vicinanza alla formalizzazione matematica e l'orientamento funzionale iniziale hanno portato ai seguenti vantaggi dell'approccio funzionale:

1. semplicità di test e verifica del codice del programma basata sulla possibilità di costruire una prova matematica rigorosa della correttezza dei programmi;

2. unificazione della presentazione del programma e dei dati (i dati possono essere incapsulati nel programma come argomenti di funzioni, la valutazione o il calcolo del valore della funzione può essere eseguita secondo necessità);

3. digitazione sicura: sono escluse le operazioni sui dati non validi;

4. digitazione dinamica: è possibile rilevare errori di digitazione in fase di runtime (l'assenza di questa proprietà nei primi linguaggi di programmazione funzionale può portare a un overflow della RAM del computer);

5. indipendenza dell'implementazione del software dalla rappresentazione dei dati macchina e dall'architettura di sistema del programma (il programmatore si concentra sui dettagli dell'implementazione e non sulle caratteristiche della rappresentazione dei dati macchina).

Si noti che la realizzazione dei vantaggi offerti dai linguaggi di programmazione funzionale dipende in modo significativo dalla scelta della piattaforma software e hardware.

In caso di scelta della tecnologia .NET come piattaforma software, praticamente indipendentemente dall'implementazione hardware, il programmatore o il project manager software riceve inoltre i seguenti vantaggi:

1.Integrazione di vari linguaggi di programmazione funzionale (massimizzando i vantaggi di ciascuno dei linguaggi, in particolare, Scheme fornisce un meccanismo di corrispondenza dei modelli e SML offre la capacità di calcolare secondo necessità);

2. integrazione di diversi approcci alla programmazione basati sulla Common Language Infrastructure, o CLI (in particolare, è possibile utilizzare C# per fornire i vantaggi di un approccio orientato agli oggetti e SML - funzionale, come in questo corso);

3. sistema di tipizzazione comune unificato Common Type System, CTS (gestione uniforme e sicura dei tipi di dati nel programma);

4. un sistema multistadio e flessibile per garantire la sicurezza del codice del programma (in particolare, basato sul meccanismo di assemblaggio).

Le caratteristiche principali dei linguaggi di programmazione funzionale che li distinguono sia dai linguaggi imperativi che dai linguaggi di programmazione logici sono la trasparenza per riferimento e il determinismo. Nei linguaggi funzionali, c'è una dispersione significativa in parametri come la digitazione, le regole di calcolo. In molte lingue, l'ordine di valutazione è rigorosamente definito. Ma a volte i linguaggi rigorosi forniscono supporto per alcuni elementi utili inerenti ai linguaggi non rigorosi, come gli elenchi infiniti (Standard ML ha un modulo speciale per supportare il calcolo pigro). Al contrario, i linguaggi lassisti consentono in alcuni casi il calcolo energetico.

Ad esempio, Miranda ha una semantica pigra, ma consente di specificare costruttori forti etichettando gli argomenti del costruttore in un certo modo.

Molti linguaggi di programmazione funzionale moderni sono linguaggi fortemente tipizzati (digitazione forte). La digitazione forte offre maggiore sicurezza. Molti bug possono essere corretti in fase di compilazione, quindi la fase di debug e il tempo di sviluppo complessivo sono ridotti. La digitazione forte consente al compilatore di generare codice più efficiente e quindi di accelerare l'esecuzione del programma. Insieme a questo, ci sono linguaggi funzionali tipizzati dinamicamente. Il tipo di dati in tali lingue è determinato in fase di esecuzione (Capitolo 3). A volte sono chiamati "senza tipo". I loro vantaggi includono il fatto che i programmi scritti in queste lingue hanno una maggiore generalità. Lo svantaggio può essere considerato l'attribuzione di molti errori alla fase di esecuzione del programma e la connessa necessità di utilizzare funzioni di controllo del tipo e la corrispondente riduzione della generalità del programma. Le lingue digitate tendono a generare codice più "affidabile", mentre le lingue digitate sono più "generali".

Il prossimo criterio con cui si possono classificare i linguaggi di programmazione funzionale può essere la presenza di meccanismi imperativi. Allo stesso tempo, è consuetudine chiamare "puri" i linguaggi di programmazione funzionale privi di meccanismi imperativi e quelli con essi - "impuri". Nella panoramica dei linguaggi di programmazione funzionale di seguito, i linguaggi di programmazione saranno indicati come "pratici" e "accademici". Per linguaggi "pratici" intendiamo linguaggi che hanno un'applicazione commerciale (erano usati per sviluppare applicazioni reali o erano sistemi di programmazione commerciali). I linguaggi di programmazione accademici sono popolari nei circoli di ricerca e nell'educazione informatica, ma praticamente non esistono applicazioni commerciali scritte in tali linguaggi. Rimangono solo uno strumento per la ricerca teorica nel campo dell'informatica e sono ampiamente utilizzati nel processo educativo.

L'elenco dei linguaggi di programmazione funzionale più diffusi è riportato di seguito utilizzando i seguenti criteri: informazioni generali; digitando; tipo di calcolo; purezza.

Lisp comune. La versione Lisp, che dal 1970 può essere considerata lo standard del linguaggio, grazie al supporto dell'Artificial Intelligence Laboratory del MIT, è senza tipo, energica, con un ampio insieme di inclusioni imperative che consentono l'assegnazione e la distruzione delle strutture. Pratico. Basti pensare che l'editor di grafica vettoriale AutoCAD è stato scritto in Lisp.

Schema. Un dialetto Lisp destinato alla ricerca informatica e all'insegnamento della programmazione funzionale. A causa della mancanza di inclusioni imperative, la lingua è molto più piccola del Common Lisp. Risale al linguaggio sviluppato da J. McCarthy nel 1962. Accademico, senza tipo, energico, puro.

Rif. Una famiglia di lingue sviluppata da V.F. Turchin. Il membro più anziano di questa famiglia è stato realizzato per la prima volta nel 1968 in Russia. È ancora ampiamente utilizzato nei circoli accademici. Contiene elementi di programmazione logica (matching pattern). Pertanto, Refal viene proposto come linguaggio di autoapprendimento in questo tutorial.

Miranda. Fortemente tipizzato, supporta i tipi di dati utente e il polimorfismo. Sviluppato da Turner sulla base dei precedenti linguaggi SALS e KRC. Ha una semantica pigra. Nessuna inclusione imperativa.

Haskell. Lo sviluppo della lingua è avvenuto alla fine del secolo scorso. Ampiamente conosciuto negli ambienti accademici. In alcune università occidentali è usata come lingua principale per gli studenti. Uno dei linguaggi funzionali più potenti. Linguaggio pigro. Un linguaggio puramente funzionale. digitato. Haskell è un ottimo strumento per apprendere e sperimentare tipi di dati funzionali complessi. I programmi scritti in Haskell hanno una dimensione significativa del codice oggetto e una bassa velocità di esecuzione.

Pulito. Un dialetto di Haskell adattato alle esigenze della programmazione pratica. Come Haskell, è un linguaggio pigro e puramente funzionale che contiene classi di tipi. Ma Clean contiene anche caratteristiche interessanti che non hanno equivalenti Haskell. Ad esempio, le funzioni imperative in Clean si basano su tipi univoci, ispirati alla logica lineare. Clean contiene meccanismi che possono migliorare significativamente l'efficienza dei programmi. Tra questi meccanismi, il calcolo differito è chiaramente soppresso. L'implementazione Clean è un prodotto commerciale, ma è disponibile una versione gratuita per scopi di ricerca e didattici.

ML (Meta Linguaggio). Sviluppato da un gruppo di programmatori guidati da Robert Milier a metà degli anni '70. a Edimburgo (Edinburgh Logic for Computable Functions). L'idea alla base del linguaggio era quella di creare un meccanismo per la costruzione di prove formali in un sistema di logica per funzioni calcolabili. Nel 1983 il linguaggio è stato rivisto con concetti come moduli. È diventato noto come ML standard. ML è un linguaggio fortemente tipizzato con tipizzazione statica ed esecuzione di programmi applicativi. Ha guadagnato molta popolarità nei circoli di ricerca e nel campo dell'educazione informatica.

String reverse (String arg) (if (arg.length == 0) (return arg;) else (return reverse (arg.substring (1, arg.length)) + arg.substring (0, 1);))
Questa funzione è piuttosto lenta perché richiama se stessa. In questo caso è possibile una perdita di memoria, poiché gli oggetti temporanei vengono creati molte volte. Ma questo è uno stile funzionale. Potrebbe mostrarti strano come le persone possano programmare in quel modo. Beh, stavo per dirtelo.

Vantaggi della programmazione funzionale

Probabilmente pensi che io non possa argomentare per giustificare la funzione mostruosa di cui sopra. Quando ho iniziato a studiare la programmazione funzionale, lo pensavo anch'io. Mi sbagliavo. Ci sono ottimi argomenti per questo stile. Alcuni di loro sono soggettivi. Ad esempio, i programmatori affermano che i programmi funzionali sono più facili da capire. Non darò tali argomenti, perché tutti sanno che la facilità di comprensione è una cosa molto soggettiva. Fortunatamente per me, ci sono ancora un sacco di argomenti oggettivi.

Test dell'unità

Poiché ogni simbolo in FP è immutabile, le funzioni non hanno effetti collaterali. Non è possibile modificare i valori delle variabili, inoltre, una funzione non può modificare un valore al di fuori del suo ambito, e quindi influenzare altre funzioni (come può accadere con i campi di classe o le variabili globali). Ciò significa che l'unico risultato di una funzione è il valore restituito. E l'unica cosa che può influenzare il valore restituito sono gli argomenti passati alla funzione.

Eccolo, il sogno azzurro degli unit tester. Puoi testare ogni funzione nel tuo programma usando solo gli argomenti che vuoi. Non è necessario chiamare le funzioni nell'ordine corretto o ricreare lo stato esterno corretto. Tutto quello che devi fare è passare argomenti che corrispondano ai casi limite. Se tutte le funzioni del tuo programma superano i test unitari, puoi essere molto più sicuro della qualità del tuo software rispetto ai linguaggi di programmazione imperativi. In Java o C ++, il controllo del valore restituito non è sufficiente: la funzione può modificare lo stato esterno, che deve essere verificato. Non c'è questo problema in FP.

Debug

Se un programma funzionale non si comporta come previsto, il debug è un gioco da ragazzi. È sempre possibile riprodurre il problema, poiché l'errore nella funzione non dipende dal codice estraneo eseguito in precedenza. In un programma imperativo, l'errore appare solo per un po'. Dovrai eseguire una serie di passaggi non correlati ai bug perché la funzione dipende dallo stato esterno e dagli effetti collaterali di altre funzioni. In FP, la situazione è molto più semplice: se il valore restituito è sbagliato, lo sarà sempre, indipendentemente da quali parti di codice siano state eseguite in precedenza.

Una volta riprodotto il bug, trovare la fonte è banale. È anche carino. Non appena interrompi l'esecuzione del programma, avrai l'intero stack di chiamate di fronte a te. Puoi visualizzare gli argomenti di chiamata di ogni funzione, proprio come in un linguaggio imperativo. Con la differenza che questo non basta in un programma imperativo, perché le funzioni dipendono dai valori di campi, variabili globali e stati di altre classi. Una funzione in FP dipende solo dai suoi argomenti e questa informazione è proprio davanti ai tuoi occhi! Inoltre, in un programma imperativo, il controllo del valore restituito non è sufficiente per stabilire se una parte di codice si comporta correttamente. Dovrai dare la caccia a dozzine di oggetti al di fuori della funzione per assicurarti che tutto funzioni correttamente. Nella programmazione funzionale, tutto ciò che devi fare è guardare il valore di ritorno!

Mentre cammini nello stack, noti gli argomenti passati e i valori restituiti. Non appena il valore di ritorno si discosta dalla norma, approfondisci la funzione e vai avanti. Questo viene ripetuto più volte finché non trovi la fonte dell'errore!

Multithreading

Il programma funzionale è subito pronto per la parallelizzazione senza alcuna modifica. Non devi preoccuparti di deadlock o condizioni di gara perché non hai bisogno di blocchi! Non un singolo pezzo di dati in un programma funzionale viene modificato due volte dallo stesso flusso o da altri diversi. Ciò significa che puoi facilmente aggiungere thread al tuo programma senza nemmeno pensare ai problemi inerenti ai linguaggi imperativi.

Se questo è il caso, allora perché i linguaggi di programmazione funzionale sono usati così raramente nelle applicazioni multithread? Più spesso di quanto pensi, in realtà. Ericsson ha sviluppato un linguaggio funzionale chiamato Erlang da utilizzare su switch di telecomunicazione tolleranti ai guasti e scalabili. Molte persone hanno notato i vantaggi di Erlang e hanno iniziato a usarlo. Si tratta di sistemi di telecomunicazioni e di controllo del traffico che non si scalano facilmente come i tipici sistemi sviluppati a Wall Street. In generale, i sistemi scritti in Erlang non sono scalabili e affidabili come i sistemi Java. I sistemi Erlang sono super affidabili.

La storia del multithreading non finisce qui. Se stai scrivendo un'applicazione essenzialmente a thread singolo, il compilatore può comunque ottimizzare un programma funzionale per utilizzare più CPU. Diamo un'occhiata al prossimo pezzo di codice.

Un compilatore di linguaggio funzionale può analizzare il codice, classificare le funzioni che creano stringhe s1 e s2 come funzioni che richiedono tempo ed eseguirle in parallelo. Questo non può essere fatto in un linguaggio imperativo, perché ogni funzione può cambiare lo stato esterno e il codice subito dopo la chiamata può dipendere da esso. In FP, l'analisi automatica delle funzioni e la ricerca di candidati idonei per la parallelizzazione è banale come un inline automatico! In questo senso, lo stile funzionale della programmazione soddisfa le esigenze del futuro. Gli sviluppatori di hardware non possono più far funzionare la CPU più velocemente. Invece, stanno aumentando il numero di core e rivendicando un aumento di quattro volte della velocità dell'elaborazione multithread. Naturalmente, dimenticano di dire molto bene nel tempo che il tuo nuovo processore mostrerà un aumento solo nei programmi sviluppati pensando al parallelismo. Ce ne sono pochissimi tra i software imperativi. Ma il 100% dei programmi funzionali è pronto per il multithreading.

Distribuzione a caldo

Ai vecchi tempi, dovevi riavviare il computer per installare gli aggiornamenti di Windows. Molte volte. Dopo aver installato una nuova versione del lettore multimediale. Ci sono stati cambiamenti significativi in ​​Windows XP, ma la situazione è ancora lontana dall'ideale (oggi ho eseguito Windows Update al lavoro e ora il fastidioso promemoria non mi lascerà in pace fino al riavvio). Sui sistemi Unix, il modello di aggiornamento era migliore. Per installare gli aggiornamenti, dovevi fermare alcuni componenti, ma non l'intero sistema operativo. Sebbene la situazione sembri migliore, non è ancora accettabile per un'ampia classe di applicazioni server. I sistemi di telecomunicazione devono essere accesi il 100% delle volte, perché se, a causa dell'aggiornamento, una persona non può chiamare un'ambulanza, si possono perdere vite umane. Anche le aziende con Wall Street non vogliono spegnere i server durante il fine settimana per installare gli aggiornamenti.

Idealmente, è necessario aggiornare tutte le parti necessarie del codice senza arrestare il sistema in linea di principio. Nel mondo imperativo, questo è impossibile [trans. in Smalltalk è possibilissimo]. Immagina di scaricare una classe Java al volo e ricaricare una nuova versione. Se lo facessimo, allora tutte le istanze della classe diventerebbero non operative, perché lo stato in cui si trovavano andrebbe perso. Dovremmo scrivere codice complicato per il controllo della versione. Dovresti serializzare tutte le istanze create della classe, quindi distruggerle, creare istanze della nuova classe, provare a caricare i dati serializzati nella speranza che la migrazione vada bene e le nuove istanze siano valide. E inoltre, il codice di migrazione deve essere scritto manualmente ogni volta. E il codice di migrazione deve anche preservare i collegamenti tra gli oggetti. In teoria va bene, ma in pratica non funzionerà mai.

In un programma funzionale, tutto lo stato è memorizzato nello stack come argomenti di funzione. Questo rende le distribuzioni a caldo molto più semplici! Fondamentalmente, tutto ciò che devi fare è calcolare la differenza tra il codice sul server di produzione e la nuova versione e installare le modifiche nel codice. Il resto verrà fatto automaticamente dagli strumenti linguistici! Se pensi che questa sia fantascienza, pensaci due volte. Gli ingegneri di Erlang hanno aggiornato i loro sistemi per anni senza fermarli.

Proof computing e ottimizzazione (prove e ottimizzazioni assistite dalla macchina)

Un'altra proprietà interessante dei linguaggi di programmazione funzionale è che possono essere studiati matematicamente. Poiché un linguaggio funzionale è un'implementazione di un sistema formale, tutte le operazioni matematiche utilizzate su carta possono essere applicate a programmi funzionali. Il compilatore, ad esempio, può convertire un pezzo di codice in un pezzo equivalente, ma più efficiente, dimostrando matematicamente la loro equivalenza. I database relazionali effettuano queste ottimizzazioni da anni. Nulla ti impedisce di utilizzare tecniche simili nei normali programmi.

Inoltre, puoi utilizzare strumenti matematici per dimostrare la correttezza delle sezioni dei tuoi programmi. Se vuoi, puoi scrivere strumenti che analizzano il codice e creano automaticamente Unit test per casi limite! Questa funzionalità è preziosa per i sistemi solidi come una roccia. Quando si sviluppano sistemi per il monitoraggio dei pacemaker o la gestione del traffico aereo, questi strumenti sono essenziali. Se i tuoi sviluppi non sono nell'area delle applicazioni critiche, gli strumenti di verifica automatica ti daranno comunque un enorme vantaggio rispetto ai tuoi concorrenti.

Funzioni di ordine superiore

Ricorda, quando ho parlato dei vantaggi di FP, ho notato che "tutto sembra bello, ma è inutile se devo scrivere in un linguaggio goffo in cui tutto è definitivo". Questa era un'illusione. L'uso di final dappertutto sembra goffo solo in linguaggi di programmazione imperativi come Java. I linguaggi di programmazione funzionale operano con altri tipi di astrazioni, in modo tale da dimenticare che una volta amavi cambiare le variabili. Uno di questi strumenti sono le funzioni di ordine superiore.

In FP, una funzione non è la stessa di una funzione in Java o C. È un superset: possono essere le stesse delle funzioni Java e anche di più. Supponiamo di avere una funzione in C:

Int add (int i, int j) (return i + j;)
In FP, questo non è lo stesso di una normale funzione C. Estendiamo il nostro compilatore Java per supportare questa notazione. Il compilatore deve trasformare la dichiarazione della funzione nel seguente codice Java (ricorda che la finale implicita è ovunque):

Classe add_function_t (int add (int i, int j) (return i + j;)) add_function_t add = new add_function_t ();
Il simbolo di aggiunta non è realmente una funzione. È una piccola classe con un metodo. Ora possiamo passare add come argomento ad altre funzioni. Possiamo scriverlo su un altro simbolo. Possiamo creare istanze di add_function_t in fase di runtime e verranno raccolte nella spazzatura se non sono più necessarie. Le funzioni diventano oggetti di base come numeri e stringhe. Le funzioni che operano su funzioni (prendetele come argomenti) sono chiamate funzioni di ordine superiore. Non lasciare che ti spaventi. Il concetto di funzioni di ordine superiore è quasi lo stesso del concetto di classi Java che operano l'una sull'altra (possiamo passare le classi ad altre classi). Possiamo chiamarle "classi di ordine superiore", ma nessuno si preoccupa di questo, perché Java non ha una rigida comunità accademica alle spalle.

Come e quando dovresti usare le funzioni di ordine superiore? Sono contento che tu l'abbia chiesto. Scrivi il tuo programma come un pezzo di codice grande e monolitico senza preoccuparti della gerarchia delle classi. Se vedi che un pezzo di codice viene ripetuto in posti diversi, lo sposti in una funzione separata (fortunatamente, le scuole insegnano ancora come farlo). Se noti che parte della logica nella tua funzione deve comportarsi in modo diverso in alcune situazioni, crei una funzione di ordine superiore. Confuso? Ecco un esempio del mondo reale dal mio lavoro.

Supponiamo di avere un pezzo di codice Java che riceve un messaggio, lo trasforma in vari modi e lo invia a un altro server.

Void handleMessage (Message msg) (// ... msg.setClientCode ("ABCD_123"); // ... sendMessage (msg);) // ...)
Ora immagina che il sistema sia cambiato e che ora devi distribuire i messaggi tra due server anziché uno. Tutto rimane invariato, tranne il codice client: il secondo server vuole ricevere questo codice in un formato diverso. Come affrontiamo questa situazione? Possiamo controllare dove dovrebbe andare il messaggio e impostare il codice client corretto in base a quello. Ad esempio così:

Class MessageHandler (void handleMessage (Message msg) (// ... if (msg.getDestination (). Equals ("server1") (msg.setClientCode ("ABCD_123");) else (msg.setClientCode ("123_ABC") ;) // ... inviaMessage (msg);) // ...)
Ma questo approccio non si adatta bene. Man mano che vengono aggiunti nuovi server, la funzione crescerà in modo lineare e apportare modifiche diventerà un incubo. L'approccio orientato agli oggetti consiste nel sottoclassare la generica superclasse MessageHandler e sottoclassare la logica di definizione del codice client:

Classe astratta MessageHandler (void handleMessage (Message msg) (// ... msg.setClientCode (getClientCode ()); // ... sendMessage (msg);) abstract String getClientCode (); // ...) classe MessageHandlerOne estende MessageHandler (String getClientCode () (return "ABCD_123";)) class MessageHandlerTwo estende MessageHandler (String getClientCode () (restituisce "123_ABCD";))
Ora, per ogni server, possiamo creare un'istanza della classe corrispondente. L'aggiunta di nuovi dal server diventa più conveniente. Ma per un cambiamento così piccolo, troppo testo. Ho dovuto creare due nuovi tipi solo per aggiungere il supporto per un codice client diverso! Ora facciamo lo stesso nella nostra lingua con il supporto per le funzioni di ordine superiore:

Class MessageHandler (void handleMessage (Message msg, Function getClientCode) (// ... Message msg1 = msg.setClientCode (getClientCode ()); // ... sendMessage (msg1);) // ...) String getClientCodeOne ( ) (restituisce "ABCD_123";) String getClientCodeTwo () (restituire "123_ABCD";) Gestore MessageHandler = new MessageHandler (); handler.handleMessage (someMsg, getClientCodeOne);
Non abbiamo creato nuovi tipi né abbiamo complicato la gerarchia delle classi. Abbiamo appena passato la funzione come parametro. Abbiamo ottenuto lo stesso effetto della controparte orientata agli oggetti, con solo pochi vantaggi. Non ci siamo vincolati a nessuna gerarchia di classi: possiamo passare qualsiasi altra funzione in fase di runtime e modificarla in qualsiasi momento, mantenendo un alto livello di modularità con meno codice. In sostanza, il compilatore ha creato per noi la colla orientata agli oggetti! Allo stesso tempo, vengono mantenuti tutti gli altri vantaggi di FP. Naturalmente, le astrazioni offerte dai linguaggi funzionali non finiscono qui. Le funzioni di ordine superiore sono solo l'inizio

curry

La maggior parte delle persone che incontro ha letto i Design Patterns della Gang of Four. Qualsiasi programmatore che si rispetti dirà che il libro non è legato a nessun linguaggio di programmazione in particolare, e gli schemi sono applicabili allo sviluppo del software in generale. Questa è un'affermazione nobile. Ma purtroppo è lontano dalla verità.

I linguaggi funzionali sono incredibilmente espressivi. In un linguaggio funzionale, non hai bisogno di modelli di progettazione perché il linguaggio è di così alto livello che puoi facilmente iniziare a programmare in concetti che escludono tutti i modelli di programmazione conosciuti. Uno di questi modelli è l'adattatore (in che modo è diverso da Facade? Sembra che qualcuno abbia bisogno di stampare più pagine per soddisfare i termini del contratto). Questo modello non è necessario se la lingua supporta il currying.

Il modello Adapter viene spesso applicato all'unità di astrazione "standard" in una classe Java. Nei linguaggi funzionali, il modello viene applicato alle funzioni. Il pattern prende un'interfaccia e la trasforma in un'altra interfaccia, in base a determinati requisiti. Ecco un esempio di un pattern Adapter:

Int pow (int i, int j); int quadrato (int i) (return pow (i, 2);)
Questo codice adatta l'interfaccia di una funzione che eleva un numero a una potenza arbitraria all'interfaccia di una funzione che eleva al quadrato un numero. Negli ambienti accademici, questa tecnica più semplice è chiamata currying (dal nome del logico Haskell Curry, che eseguì una serie di trucchi matematici per formalizzare il tutto). Poiché le funzioni sono comunemente usate come argomenti in FP, il currying è usato molto spesso per portare le funzioni a un'interfaccia che è necessaria in un posto o nell'altro. Poiché l'interfaccia di una funzione sono i suoi argomenti, il currying viene utilizzato per ridurre il numero di argomenti (come nell'esempio sopra).

Questo strumento è integrato nei linguaggi funzionali. Non è necessario creare manualmente una funzione che ricopra l'originale. Un linguaggio funzionale farà tutto per te. Come al solito, espandiamo il nostro linguaggio aggiungendovi il curry.

Quadrato = int pow (int i, 2);
Con questa riga creiamo automaticamente una funzione quadrata con un argomento. La nuova funzione chiamerà pow, sostituendo 2 per il secondo argomento. Da una prospettiva Java, sarebbe simile a questo:

Classe square_function_t (int square (int i) (return pow (i, 2);)) square_function_t square = new square_function_t ();
Come puoi vedere, abbiamo appena scritto un wrapper sulla funzione originale. In FP, il curry è solo un modo semplice e conveniente per creare involucri. Ti concentri sull'attività e il compilatore scrive il codice necessario per te! È molto semplice e succede ogni volta che vuoi usare il pattern Adapter (wrapper).

Valutazione pigra

La valutazione pigra (o pigra) è una tecnica interessante che diventa possibile una volta afferrata la filosofia funzionale. Abbiamo già visto il seguente pezzo di codice quando abbiamo parlato di multithreading:

String s1 = alquantoLongOperation1 (); String s2 = alquantoLongOperation2 (); Stringa s3 = concatena (s1, s2);
Nei linguaggi di programmazione imperativi, l'ordine di valutazione non solleva alcun problema. Poiché ogni funzione può influenzare o dipendere da uno stato esterno, è necessario osservare un chiaro ordine di chiamate: prima, alquantoLongOperation1, poi alquantoLongOperation2, e concatenare alla fine. Ma non tutto è così semplice nei linguaggi funzionali.

Come abbiamo visto in precedenza, someLongOperation1 e alquantoLongOperation2 possono essere avviati contemporaneamente, perché è garantito che le funzioni non siano interessate e non dipendano dallo stato globale. Ma cosa succede se non vogliamo eseguirli contemporaneamente, dobbiamo chiamarli in sequenza? La risposta è no. Questi calcoli dovrebbero essere eseguiti solo se qualche altra funzione dipende da s1 e s2. Non abbiamo nemmeno bisogno di eseguirli finché ne abbiamo bisogno all'interno della concatenazione. Se invece di concatenare sostituiamo una funzione che, a seconda della condizione, usa uno dei due argomenti, allora il secondo argomento non deve nemmeno essere calcolato! Haskell è un esempio di linguaggio informatico pigro. Haskell non garantisce alcun ordinamento delle chiamate (per niente!), Perché Haskell esegue il codice secondo necessità.

La valutazione pigra ha diversi vantaggi e alcuni svantaggi. Nella prossima sezione, discuteremo i meriti e spiegherò come andare d'accordo con gli svantaggi.

Ottimizzazione

La valutazione pigra offre un enorme potenziale di ottimizzazione. Un compilatore pigro tratta il codice esattamente come un matematico studia le espressioni algebriche: può annullare alcune cose, annullare l'esecuzione di determinate sezioni del codice, modificare l'ordine delle chiamate per una maggiore efficienza, persino organizzare il codice in modo tale da ridurre il numero di errori, garantendo l'integrità del programma. Questo è il più grande vantaggio quando si descrive un programma con rigorose primitive formali: il codice obbedisce a leggi matematiche e può essere studiato con metodi matematici.

Astrazione delle strutture di controllo

La valutazione pigra fornisce un livello di astrazione così alto che diventano possibili cose incredibili. Ad esempio, immagina di implementare la seguente struttura di controllo:

A meno che (stock.isEuropean ()) (sendToSEC (stock);)
Vogliamo che la funzione sendToSEC venga eseguita solo se il fondo (azionario) non è europeo. Come puoi implementare a meno che? Senza una valutazione pigra, avremmo bisogno di un sistema macro, ma in linguaggi come Haskell, questo non è necessario. Possiamo dichiarare a meno che come una funzione!

Void a meno che (condizione booleana, codice elenco) (if (! Condizione) codice;)
Nota che il codice non verrà eseguito se condition == true. Nei linguaggi forti, questo comportamento non può essere ripetuto, poiché gli argomenti verranno valutati prima a meno che non venga chiamato.

Strutture dati infinite

I linguaggi pigri ti consentono di creare infinite strutture di dati, che sono molto più difficili da creare in linguaggi rigorosi [trans. - non in Python]. Ad esempio, immagina una sequenza di Fibonacci. Ovviamente, non possiamo calcolare una lista infinita in un tempo finito e conservarla comunque in memoria. In linguaggi forti come Java, scriveremmo semplicemente una funzione che restituisca un membro arbitrario di una sequenza. In linguaggi come Haskell, possiamo astrarre e dichiarare semplicemente un elenco infinito di numeri di Fibonacci. Poiché la lingua è pigra, verranno calcolate solo le parti necessarie dell'elenco che vengono effettivamente utilizzate nel programma. Ciò consente di astrarre da un gran numero di problemi e di osservarli da un livello superiore (ad esempio, è possibile utilizzare le funzioni di elaborazione di elenchi su sequenze infinite).

Screpolatura

Certo, il formaggio gratis è solo in una trappola per topi. La valutazione pigra presenta una serie di svantaggi. Questi sono principalmente gli svantaggi della pigrizia. In realtà, è spesso necessario un ordine di calcolo diretto. Prendiamo ad esempio il seguente codice:

In un linguaggio pigro, nessuno garantisce che la prima riga verrà eseguita prima della seconda! Questo significa che non possiamo fare I/O, non possiamo usare normalmente le funzioni native (dopotutto, devono essere chiamate in un certo ordine per tener conto dei loro effetti collaterali), e non possiamo interagire con il mondo esterno! Se introduciamo un meccanismo per snellire l'esecuzione del codice, allora perderemo il vantaggio del rigore matematico del codice (e quindi perderemo tutte le chicche della programmazione funzionale). Per fortuna non tutto è ancora perduto. I matematici si sono messi al lavoro e hanno escogitato alcuni trucchi per assicurarsi che le istruzioni fossero nell'ordine corretto senza perdere il loro spirito funzionale. Abbiamo il meglio di entrambi i mondi! Tali tecniche includono la continuazione, le monadi e la tipizzazione dell'unicità. In questo articolo lavoreremo con le continuazioni e rimanderemo le monadi e la digitazione univoca alla prossima volta. È interessante notare che la continuazione è una cosa molto utile, che viene utilizzata non solo per specificare un rigoroso ordine di calcoli. Parleremo anche di questo.

continuazioni

Le continuazioni della programmazione svolgono lo stesso ruolo del Codice Da Vinci nella storia umana: la sorprendente rivelazione del più grande mistero dell'umanità. Beh, forse non proprio così, ma sicuramente strappano i veli, dato che un tempo hai imparato a mettere la radice di -1.

Quando abbiamo esaminato le funzioni, abbiamo appreso solo metà della verità, perché siamo partiti dal presupposto che una funzione restituisca un valore alla funzione chiamante. In questo senso, la continuazione è una generalizzazione delle funzioni. La funzione non deve restituire il controllo al punto da cui è stata chiamata, ma può tornare in qualsiasi punto del programma. Continua è un parametro che possiamo passare a una funzione per indicare il punto di ritorno. Sembra molto più spaventoso di quanto non sia in realtà. Diamo un'occhiata al seguente codice:

Int i = somma (5, 10); int j = quadrato (i);
La funzione add restituisce il numero 15, che viene scritto in i, nel punto in cui è stata chiamata la funzione. Il valore di i viene quindi utilizzato nella chiamata al quadrato. Si noti che il compilatore pigro non può modificare l'ordine di valutazione, poiché la seconda riga dipende dal risultato della prima. Possiamo riscrivere questo codice usando il Continuation Passing Style (CPS) quando add restituisce un valore alla funzione square.

Int j = somma (5, 10, quadrato);
In questo caso, add riceve un argomento aggiuntivo, una funzione che verrà chiamata dopo che add avrà finito di funzionare. In entrambi gli esempi, j sarà 225.

Questa è la prima tecnica che permette di specificare l'ordine di esecuzione di due espressioni. Torniamo al nostro esempio di I/O.

System.out.println ("Inserisci il tuo nome:"); System.in.readLine ();
Queste due righe sono indipendenti l'una dall'altra e il compilatore è libero di cambiarne l'ordine a piacimento. Ma se lo riscriviamo in CPS, così facendo aggiungiamo la dipendenza richiesta e il compilatore dovrà eseguire calcoli uno dopo l'altro!

System.out.println ("Inserisci il tuo nome:", System.in.readLine);
In tal caso, println chiamerà readLine con il suo risultato e restituirà il risultato readLine alla fine. In questa forma, possiamo essere sicuri che queste funzioni verranno chiamate a turno e che readLine verrà chiamato del tutto (dopotutto, il compilatore si aspetta di ricevere il risultato dell'ultima operazione). Nel caso di Java, println restituisce void. Ma se venisse restituito un valore astratto (che può servire come argomento per readLine), allora questo risolverebbe il nostro problema! Naturalmente, l'allineamento di tali catene di funzioni compromette notevolmente la leggibilità del codice, ma è possibile combatterlo. Possiamo aggiungere elementi sintattici al nostro linguaggio che ci consentiranno di scrivere espressioni come al solito e il compilatore concatenerà automaticamente i calcoli. Ora possiamo eseguire calcoli in qualsiasi ordine senza perdere i vantaggi di FP (compresa la possibilità di studiare il programma utilizzando metodi matematici)! Se questo ti confonde, ricorda che le funzioni sono solo istanze di una classe con un singolo membro. Riscrivi il nostro esempio in modo che println e readLine siano entrambe istanze di classe in modo che tu possa capirlo meglio.

Ma i vantaggi dei sequel non finiscono qui. Possiamo scrivere un intero programma usando CPS, in modo che ogni funzione venga chiamata con un parametro aggiuntivo, una continuazione, in cui viene passato il risultato. In linea di principio, qualsiasi programma può essere tradotto in CPS, se si pensa a ciascuna funzione come a un caso speciale di continuazioni. Questa conversione può essere eseguita automaticamente (in effetti, molti compilatori lo fanno).

Non appena convertiamo il programma nella forma CPS, diventa chiaro che ogni istruzione ha una continuazione, la funzione in cui verrà passato il risultato, che in un normale programma sarebbe un call point. Prendiamo qualsiasi istruzione dall'ultimo esempio, ad esempio aggiungi (5,10). In un programma scritto in forma CPS, è chiaro quale sarà una continuazione: questa è una funzione che add chiamerà alla fine del lavoro. Ma quale sarà il seguito del programma non-CPS? Certo, possiamo convertire il programma in CPS, ma è necessario?

Si scopre che questo non è necessario. Dai un'occhiata da vicino alla nostra conversione CPS. Se inizi a scrivere un compilatore per esso, scoprirai che la versione CPS non ha bisogno di uno stack! Le funzioni non restituiscono mai nulla, nel senso tradizionale della parola "ritorno", chiamano semplicemente un'altra funzione, sostituendo il risultato dei calcoli. Non è necessario inserire (push) gli argomenti nello stack prima di ogni chiamata e poi riportarli indietro. Possiamo semplicemente memorizzare gli argomenti in un pezzo fisso di memoria e usare jump invece della normale chiamata. Non abbiamo bisogno di memorizzare gli argomenti originali, perché non ne avremo mai più bisogno, perché le funzioni non restituiscono nulla!

Pertanto, i programmi in stile CPS non necessitano di uno stack, ma contengono un argomento aggiuntivo, sotto forma di funzione da chiamare. I programmi non in stile CPS non hanno argomenti aggiuntivi, ma usano uno stack. Cosa viene memorizzato nello stack? Solo argomenti e un puntatore alla posizione di memoria in cui la funzione dovrebbe restituire. Bene, hai indovinato? Lo stack memorizza le informazioni sulle continuazioni! Un puntatore a un punto di ritorno sullo stack equivale a una funzione da chiamare nei programmi CPS! Per sapere quale estensione è la somma (5,10), è sufficiente prendere il punto di ritorno dalla pila.

Non è stato difficile. Una continuazione e un puntatore a un punto di ritorno sono in realtà la stessa cosa, solo la continuazione è specificata in modo esplicito e quindi potrebbe differire da dove è stata chiamata la funzione. Se ricordi che una continuazione è una funzione e una funzione nel nostro linguaggio è compilata in un'istanza di una classe, allora capirai che un puntatore a un punto di ritorno sullo stack e un puntatore a una continuazione sono in realtà la stessa cosa , perché la nostra funzione (come istanza di una classe ) è solo un puntatore. Ciò significa che in qualsiasi momento nel tuo programma, puoi richiedere la continuazione corrente (in effetti, le informazioni dallo stack).

Ok, ora abbiamo una buona idea di quale sia l'attuale sequel. Cosa significa? Se prendiamo la continuazione corrente e la salviamo da qualche parte, salviamo così lo stato attuale del programma - lo congeliamo. Questo è simile all'ibernazione del sistema operativo. L'oggetto di continuazione memorizza le informazioni necessarie per riprendere l'esecuzione del programma dal punto in cui è stato richiesto l'oggetto di continuazione. Il sistema operativo fa questo ai tuoi programmi tutto il tempo quando cambia contesto tra i thread. L'unica differenza è che tutto è sotto il controllo del sistema operativo. Se richiedi un oggetto di continuazione (in Scheme, questo viene fatto chiamando la funzione call-with-current-continuation), allora riceverai un oggetto con la continuazione corrente - lo stack (o nel caso di CPS - la funzione di la prossima chiamata). Puoi salvare questo oggetto in una variabile (o anche su disco). Se scegli di "riavviare" il programma con questa continuazione, lo stato del tuo programma viene "convertito" allo stato in cui si trovava quando è stato preso l'oggetto di continuazione. È come passare a un thread sospeso o riattivare il sistema operativo dopo l'ibernazione. Con l'eccezione che puoi farlo molte volte di seguito. Dopo che il sistema operativo si è riattivato, le informazioni sull'ibernazione vengono distrutte. In caso contrario, sarebbe possibile ripristinare lo stato del sistema operativo dallo stesso punto. È quasi come viaggiare nel tempo. Con i sequel, te lo puoi permettere!

In quali situazioni sono utili le continuazioni? Di solito se stai cercando di emulare lo stato nei sistemi senza di esso intrinsecamente. Le continuazioni sono molto utilizzate nelle applicazioni Web (come il framework Seaside Smalltalk). ASP.NET di Microsoft fa di tutto per mantenere lo stato tra le richieste e semplificarti la vita. Se C# supportava le continuazioni, la complessità di ASP.NET potrebbe essere ridotta della metà salvando la continuazione e ripristinandola alla richiesta successiva. Dal punto di vista di un programmatore Web, non ci sarebbero interruzioni: il programma continuerebbe sulla riga successiva! Le continuazioni sono un'astrazione incredibilmente utile per risolvere alcuni problemi. Con sempre più fat client tradizionali che si spostano sul Web, l'importanza dei sequel aumenterà solo nel tempo.

Corrispondenza del modello

Il pattern matching non è un'idea così nuova o innovativa. In effetti, ha poco a che fare con la programmazione funzionale. L'unico motivo per cui è spesso associato a FP è che per qualche tempo i linguaggi funzionali hanno pattern matching, ma quelli imperativi no.

Iniziamo la nostra conoscenza con il Pattern matching con il seguente esempio. Ecco la funzione per calcolare i numeri di Fibonacci in Java:

Int fib (int n) (if (n == 0) restituisce 1; if (n == 1) restituisce 1; restituisce fib (n - 2) + fib (n - 1);)
Ed ecco un esempio in un linguaggio simile a Java con supporto per il pattern matching

Int fib (0) (ritorno 1;) int fib (1) (ritorno 1;) int fib (int n) (ritorno fib (n - 2) + fib (n - 1);)
Qual è la differenza? Il compilatore esegue la ramificazione per noi.

Pensa, l'importanza è grande! In effetti, l'importanza non è grande. È stato notato che un gran numero di funzioni contiene complessi costrutti di switch (questo è in parte vero per i programmi funzionali) e si è deciso di evidenziare questo punto. La definizione della funzione è suddivisa in diverse varianti e il modello viene impostato al posto degli argomenti della funzione (è simile all'overload del metodo). Quando viene chiamata una funzione, il compilatore confronta al volo gli argomenti con tutte le definizioni e seleziona quella più appropriata. Di solito la scelta ricade sulla definizione di funzione più specializzata. Ad esempio int fib (int n) può essere chiamato quando n è 1, ma non lo farà, perché int fib (1) è una definizione più specializzata.

Il pattern matching è solitamente più complesso del nostro esempio. Ad esempio, il complesso sistema di Pattern matching permette di scrivere il seguente codice:

Int f (int n< 10) { ... } int f(int n) { ... }
Quando può essere utile il pattern matching? L'elenco di questi casi è sorprendentemente lungo! Ogni volta che si utilizzano costrutti if annidati complessi, la corrispondenza dei modelli può funzionare meglio con meno codice. Un buon esempio viene in mente con la funzione WndProc, che è implementata in ogni programma Win32 (anche se è nascosta al programmatore dietro un'alta recinzione di astrazioni). In genere, la corrispondenza dei modelli può persino controllare il contenuto delle raccolte. Ad esempio, se passi un array a una funzione, puoi selezionare tutti gli array in cui il primo elemento è 1 e il terzo elemento è maggiore di 3.

Un altro vantaggio della corrispondenza dei modelli è che se si apportano modifiche, non è necessario scavare in un'unica enorme funzione. Hai solo bisogno di aggiungere (o modificare) alcune definizioni di funzione. Quindi, ci liberiamo di un intero strato di schemi dal famoso libro della Banda dei Quattro. Più complesse e ramificate sono le condizioni, più utile sarà il pattern matching. Una volta che inizi a usarli, ti chiedi come avresti potuto farne a meno prima.

chiusure

Finora, abbiamo discusso le caratteristiche della FP nel contesto dei linguaggi "puramente" funzionali - linguaggi che sono l'implementazione del lambda calcolo e non contengono caratteristiche che contraddicono il sistema formale di Church. Tuttavia, molte caratteristiche dei linguaggi funzionali vengono utilizzate al di fuori del lambda calcolo. Sebbene l'implementazione del sistema assiomatico sia interessante dal punto di vista della programmazione in termini di espressioni matematiche, potrebbe non essere sempre applicabile nella pratica. Molte lingue preferiscono utilizzare elementi di linguaggi funzionali senza aderire a una rigida dottrina funzionale. Alcuni di questi linguaggi (ad esempio Common Lisp) non richiedono che le variabili siano definitive: i loro valori possono essere modificati. Non richiedono nemmeno che le funzioni dipendano solo dai loro argomenti: le funzioni possono accedere allo stato al di fuori del loro ambito. Tuttavia, includono anche funzionalità come funzioni di ordine superiore. Il passaggio di una funzione in un linguaggio non puro è leggermente diverso dall'operazione analoga all'interno del lambda calcolo e richiede una caratteristica interessante chiamata chiusura lessicale. Diamo un'occhiata al seguente esempio. Ricorda che in questo caso le variabili non sono definitive e la funzione può accedere a variabili al di fuori del suo ambito:

Funzione makePowerFn (int power) (int powerFn (int base) (return pow (base, power);) return powerFn;) Function square = makePowerFn (2); quadrato (3); // restituisce 9
La funzione make-power-fn restituisce una funzione che accetta un argomento e lo eleva a una potenza specifica. Cosa succede quando proviamo a valutare il quadrato (3)? La variabile power è fuori portata per powerFn perché makePowerFn è già uscito e il suo stack è stato distrutto. Come funziona il quadrato allora? Il linguaggio deve preservare in qualche modo il valore della potenza affinché la funzione quadrato funzioni. E se creiamo un'altra funzione cubo che eleva il numero alla terza potenza? La lingua dovrà memorizzare due valori di potenza per ogni funzione creata in make-power-fn. Il fenomeno della memorizzazione di questi valori è chiamato chiusura. La chiusura fa più che memorizzare gli argomenti della funzione top. Ad esempio, una chiusura potrebbe assomigliare a questa:

Funzione makeIncrementer () (int n = 0; int incremento () (return ++ n;)) Funzione inc1 = makeIncrementer (); Funzione inc2 = makeIncrementer (); inc1 (); // restituisce 1; inc1 (); // restituisce 2; inc1 (); // restituisce 3; inc2 (); // restituisce 1; inc2 (); // restituisce 2; inc2 (); // restituisce 3;
Durante l'esecuzione, i valori di n vengono salvati e i contatori vi hanno accesso. Inoltre, ogni contatore ha la propria copia di n, nonostante il fatto che dovrebbero essere scomparsi dopo l'esecuzione della funzione makeIncrementer. Come fa il compilatore a compilarlo? Cosa sta succedendo dietro le quinte delle chiusure? Per fortuna abbiamo un passaggio magico.

Tutto è fatto in modo abbastanza logico. A prima vista, è chiaro che le variabili locali non obbediscono più alle regole di ambito e la loro durata è indefinita. Ovviamente non sono più archiviati nello stack: devono essere conservati nell'heap. La chiusura viene quindi eseguita come una normale funzione di cui abbiamo discusso in precedenza, tranne per il fatto che ha un riferimento aggiuntivo alle variabili circostanti:

Classe some_function_t (SymbolTable parentScope; // ...)
Se la chiusura fa riferimento a una variabile che non è nell'ambito locale, prende in considerazione l'ambito padre. È tutto! La chiusura collega il mondo funzionale al mondo OOP. Ogni volta che crei una classe che memorizza uno stato e lo passi da qualche parte, ricorda le chiusure. Una chiusura è solo un oggetto che crea "attributi" al volo, portandoli fuori dall'ambito in modo da non doverlo fare da soli.

Ora cosa?

Questo articolo rappresenta solo la punta dell'iceberg della programmazione funzionale. Puoi scavare più a fondo e vedere qualcosa di veramente grande e, nel nostro caso, anche buono. In futuro, ho intenzione di scrivere sulla teoria delle categorie, le monadi, le strutture dati funzionali, il sistema dei tipi nei linguaggi funzionali, il multithreading funzionale, i database funzionali e molti altri. Se riesco a scrivere (e imparare strada facendo) circa la metà di questi argomenti, la mia vita non sarà sprecata. Fino ad allora, Google- il tuo fedele amico.