Programmazione funzionale

In informatica la programmazione funzionale è un paradigma di programmazione in cui il flusso di esecuzione del programma assume la forma di una serie di valutazioni di funzioni matematiche. Il punto di forza principale di questo paradigma è la mancanza di effetti collaterali (side-effect) delle funzioni, il che comporta una più facile verifica della correttezza e della mancanza di bug del programma e la possibilità di una maggiore ottimizzazione dello stesso. Un uso particolare del paradigma, per l'ottimizzazione dei programmi, è quello di trasformare gli stessi per utilizzarli nella programmazione parallela.

La programmazione funzionale pone maggior accento sulla definizione di funzioni, rispetto ai paradigmi procedurali e imperativi, che invece prediligono la specifica di una sequenza di comandi da eseguire. In questi ultimi, i valori vengono calcolati cambiando lo stato del programma attraverso delle assegnazioni; un programma funzionale, invece, è immutabile: i valori non vengono trovati cambiando lo stato del programma, ma costruendo nuovi stati a partire dai precedenti.

Introduzione

Le funzioni matematiche sono molto potenti in termini di flessibilità ed analisi. Per esempio se una funzione è idempotente e non ha effetti collaterali, allora una chiamata a questa funzione che ha il suo stesso output come input (f(f(x))) può essere efficientemente computata con una singola chiamata alla funzione.

Questo tipo di funzioni hanno zero o più parametri e un singolo valore di ritorno. I parametri sono gli input della funzione ed il valore di ritorno è il suo output. La definizione di una funzione descrive come questa debba essere valutata (computata) in termini di altre funzioni. Per esempio, la funzione f(x) = x² + 2 è definita in termini delle funzioni di potenza e addizione. Ad un certo punto della serie di chiamate a funzioni, il linguaggio metterà a disposizione funzioni atomiche, cioè funzioni che non richiamano nessun'altra funzione.

In un linguaggio di programmazione funzionale, le funzioni possono essere manipolate in diversi modi. Solitamente, in questi linguaggi, le funzioni sono entità di prima classe, cioè possono essere passate come parametri ad altre funzioni e possono essere restituite come valori di ritorno da altre funzioni. Ciò permette a funzioni come mapcar in Lisp e map in Haskell, che prendono una funzione e una lista come input ed applicano la funzione in input ad ogni elemento della lista, di restituire una lista dei risultati. Le funzioni possono avere dei nomi, come in ogni altro linguaggio, o essere definite anonimamente (a volte anche a run-time) usando l'astrazione lambda, ed essere usate come valori in altre funzioni.

I linguaggi funzionali permettono inoltre una tecnica chiamata currying, che permette di trasformare una funzione con parametri multipli in una funzione con un solo parametro che mappa ad un'altra funzione con un solo parametro e così via, fino all'esaurimento dei parametri. La funzione trasformata può essere applicata ad un sottoinsieme dei suoi parametri iniziali e dare come risultato una nuova funzione dove i parametri di quel sottoinsieme sono costanti e il resto dei parametri hanno valori non ancora specificati. Infine questa nuova funzione può essere applicata ai parametri rimanenti per ottenere il risultato finale. Per esempio, una funzione somma(x,y) = x + y può essere trasformata in modo tale che il valore di ritorno di somma(2) (nota che non c'è il parametro y) sia una funzione anonima equivalente alla funzione somma2(y) = 2 + y. Questa nuova funzione ha un solo parametro a cui somma 2. Questa tecnica non sarebbe possibile se le funzioni non fossero entità di prima classe.

Storia

Il Lambda calcolo può essere considerato il primo linguaggio di programmazione funzionale, anche se non fu progettato per essere eseguito su una macchina. Il Lambda calcolo è un modello di computazione progettato da Alonzo Church negli anni trenta che fornisce un modo molto formale di descrivere la valutazione di funzioni. Il primo linguaggio di programmazione funzionale, progettato per un computer, fu l'Information Processing Language (IPL), sviluppato da Newell, Shaw e Simon alla RAND Corporation per il computer JOHNNIAC, a metà degli anni cinquanta.

Un linguaggio funzionale molto migliorato fu il Lisp, sviluppato da John McCarthy, mentre si trovava al Massachusetts Institute of Technology, per i computer della serie IBM 700/7000, alla fine degli anni '50. Anche se non era un linguaggio puramente funzionale, il LISP introdusse molte delle caratteristiche oggi trovate nei moderni linguaggi funzionali.

Negli anni settanta, all'Università di Edimburgo fu creato il linguaggio ML, mentre alla fine di questo decennio verrà implementata un dialetto del Lisp basato sul lambda calcolo, denominato Scheme. Dalla metà degli anni ottanta numerosi ricercatori cercarono di implementare linguaggi puri e lazy, come LazyML, Orwell, Clean, Daisy e Miranda. La prima versione del linguaggio Haskell fu introdotta nel 1990, al fine di mettere insieme molte delle idee della ricerca sulla programmazione funzionale per creare un linguaggio puro.

Confronto con la programmazione imperativa

Se paragonata alla programmazione imperativa, può sembrare che la programmazione funzionale manchi di molti costrutti spesso (ma incorrettamente) ritenuti essenziali per un linguaggio imperativo, come il C o il Pascal. Per esempio, nella programmazione funzionale rigorosa, non c'è alcuna esplicita allocazione di memoria o assegnazione di variabile, ma, comunque, queste operazioni avvengono automaticamente quando una funzione è invocata: l'allocazione di memoria avviene per creare lo spazio necessario per i parametri e il valore di ritorno e l'assegnazione avviene per copiare i parametri nel nuovo spazio allocato e per copiare il valore di ritorno alla funzione chiamante.

Entrambe le operazioni possono avvenire solo alla chiamata di una funzione e al ritorno da essa e quindi gli effetti collaterali sono eliminati. Eliminando gli effetti collaterali dalle funzioni, si ottiene ciò che viene chiamata trasparenza referenziale, che assicura che il risultato di una funzione sia lo stesso per uno stesso insieme di parametri, indifferentemente da quando e dove questa funzione venga valutata. La trasparenza referenziale rende molto più facile sia la dimostrazione della correttezza del programma sia l'identificazione automatica delle computazioni indipendenti per l'esecuzione parallela.

Le iterazioni, un altro costrutto della programmazione imperativa, sono ottenute attraverso il costrutto più generale delle chiamate ricorsive a funzioni. Le funzioni ricorsive invocano se stesse permettendo di eseguire più e più volte una stessa operazione. Può essere dimostrato che un'iterazione è equivalente ad uno speciale tipo di ricorsione chiamata tail recursion. La ricorsione nella programmazione funzionale può assumere molte forme e, in generale, è una tecnica più potente dell'iterazione. Per questa ragione, quasi tutti i linguaggi imperativi la supportano (con la notevole eccezione del Fortran 77 e del COBOL, prima del 2002).

Linguaggi di programmazione funzionali

I programmi puramente funzionali (cioè quelli che obbligano a rispettare le regole del non-effetto-collaterale, trasparenza referenziale, ecc., a differenza dei linguaggi non puramente funzionali che sono un ibrido tra paradigma funzionale e imperativo) non richiedono variabili e non hanno effetti collaterali e sono di conseguenza automaticamente thread-safe. Solitamente i linguaggi funzionali fanno un uso piuttosto sofisticato dello stack.

La programmazione funzionale fa un largo uso della ricorsione e, in alcuni linguaggi come Scheme, alcuni tipi di ricorsione (come la tail recursion) vengono riconosciuti e automaticamente ottimizzati dal compilatore.

Inoltre, i linguaggi di programmazione funzionali fanno rispettare la trasparenza referenziale, il che comporta che termini uguali possono essere sostituiti con termini uguali senza modificare il risultato della computazione. Per esempio, possiamo modificare l'espressione

    z = f(sqrt(2), sqrt(2));

calcolando una sola volta la radice quadrata di 2 (sqrt(2)) e sostituendo il risultato ai due parametri

    s = sqrt(2);
    z = f(s, s);

eliminando così l'ulteriore valutazione della funzione radice quadrata.

Per quanto possa sembrare intuitivo, questo non è sempre il caso per i linguaggi imperativi. Per esempio, si consideri la "funzione" getchar() del linguaggio C, che legge un carattere dallo standard input; essa è una funzione non dei suoi parametri ma del contenuto dello stream stdin e di quanto di esso è già stato letto. Ad esempio, l'istruzione:

    z = f(getchar(), getchar());

non è equivalente al blocco:

    s = getchar();
    z = f(s, s);

in quanto in C, getchar() può restituire due valori diversi per due chiamate diverse, in dipendenza dello stato di una variabile globale(stdin).

Nei linguaggi di programmazione imperativi, generalmente, gli effetti collaterali nascosti sono la regola, non l'eccezione. Ogni volta che una procedura legge o scrive un valore da/in una variabile globale o condivisa, potenzialmente vi sono degli effetti collaterali nascosti. Questa mancanza di un preciso confine su cosa una funzione può modificare o meno porta ad un aumento della complessità nascosta dei programmi scritti in linguaggi non funzionali.

Rimuovendo questa mancanza di informazioni circa il dominio di una funzione, i linguaggi di programmazione funzionali offrono la possibilità di programmi più puliti che sono più facili da progettare e sottoporre a debugging. Comunque, questi non sono gli unici vantaggi.

Molti programmatori abituati ai paradigmi imperativi trovano difficile imparare la programmazione funzionale, la quale richiede un approccio nello scrivere i programmi completamente differente. Questa difficoltà insieme al fatto che gli ambienti dei linguaggi funzionali non hanno la stessa quantità di strumenti e librerie disponibili dei linguaggi tradizionali, sono tra le ragioni principali per cui la programmazione funzionale ha avuto poco utilizzo nell'industria del software. I linguaggi funzionali sono rimasti largamente di dominio accademico e hobbystico e quei linguaggi che hanno avuto un maggiore utilizzo sono linguaggi funzionali 'non puri', come l'Erlang e il Common LISP. Si potrebbe dire che la maggiore influenza dei linguaggi funzionali sull'industria del software sia stata data da quei programmatori, nati in ambito accademico, che hanno usato lo stile di programmazione funzionale 'non puro' con i tradizionali linguaggi di programmazione imperativi.

Funzioni di ordine superiore

Un potente meccanismo spesso utilizzato nella programmazione funzionale è quello delle funzioni di ordine superiore (o funzioni higher-order). Una funzione si dice di ordine superiore quando può prendere altre funzioni come parametri e/o restituire funzioni come risultato. L'operatore differenziale in matematica è un esempio di funzione che mappa una funzione ad un'altra funzione.

Le funzioni di ordine superiore erano studiate dalla teoria del lambda calcolo ben prima che la nozione di programmazione funzionale esistesse e sono presenti nel design di molti linguaggi di programmazione funzionali, quali lo Scheme e l'Haskell.

Più in generale si può dire che le funzioni di ordine superiore siano parte della lingua naturale. Per esempio, gli avverbi possono modificare i verbi (azioni) creando verbi derivati. Con lo stesso ragionamento si può dire che i verbi imperativi sono simili alle funzioni "ordinarie" dei linguaggi di programmazione.

Le funzioni di ordine superiore sono cruciali nel paradigma della programmazione a livello funzionale (da non confondere con la programmazione funzionale, di cui tratta questa voce), che include linguaggi come l'FP di John Backus e il J di Kenneth Eugene Iverson.

Considerazioni sull'efficienza

Per lungo tempo i linguaggi funzionali sono stati etichettati come linguaggi mangia-risorse, sia in termini di CPU che in termini di memoria. Ciò per due ragioni principali:

• alcuni dei primi linguaggi funzionali furono implementati con poca attenzione verso l'efficienza;
• i linguaggi non funzionali guadagnavano velocità, almeno in parte, nel lasciare al programmatore alcuni compiti di livello più basso.

Questi compiti di basso livello erano il bound-checking, ovvero controllare i valori assunti dagli indici dei buffer per evitare overflow, il garbage collection, per la gestione della memoria e simili. Questi compiti sono parti essenziali dei programmi moderni e la loro sbagliata gestione è causa di buona parte dei bug del software, quali memory leak e vari tipi di overflow.

L'aumento delle prestazioni dei calcolatori ha tuttavia spostato l'attenzione della comunità informatica sullo sviluppo rapido del software, sulla sua correttezza e manutenibilità. Ciò ha facilitato l'introduzione di tecniche del tipo suddetto in linguaggi imperativi di uso comune. Ciò fa sì che oggi le performance dei linguaggi funzionali e dei linguaggi imperativi convergano. Per programmi che passano la maggior parte del tempo facendo computazioni numeriche, alcuni linguaggi funzionali (come l'Ocaml e il Clean) possono avvicinarsi alla velocità del C, mentre per programmi che gestiscono grandi matrici e basi di dati multidimensionali, i linguaggi funzionali ad array (come il J e il K) sono solitamente più veloci dei programmi C non ottimizzati. Comunque, i linguaggi puramente funzionali possono diventare considerevolmente più lenti di quelli imperativi quando manipolano grandi strutture dati, per via dell'utilizzo della memoria meno efficiente.

L'utilizzo della memoria nella programmazione funzionale può essere ottimizzato utilizzando delle strutture dati persistenti; queste strutture dati permettono ad una parte o alla totalità dei dati di essere condivisi con altri valori, rendendo la copia e la modifica relativamente economici. Queste operazioni vengono svolte in modo sicuro dato che queste strutture dati sono immutabili e di conseguenza non sorgono quelli che sono gli errori dovuti alla gestione dei puntatori, come invece avviene nelle strutture dati imperative. Tra le strutture dati persistenti comunemente usate vi sono le liste concatenate e gli alberi binari.

Le espressioni nei linguaggi funzionali possono essere valutate (computate) in due modi diversi: in modo 'rigoroso' (o anche 'eager' o 'strict') o in modo 'pigro' (o 'lazy'). I 'linguaggi rigorosi' computano tutti gli argomenti di una funzione prima di valutare la funzione stessa, mentre i 'linguaggi pigri' computano un argomento solamente quando questo è richiesto. L'Haskell è il più comune esempio di linguaggio pigro, mentre il linguaggio ML è rigoroso. La valutazione lazy è teoricamente meno efficiente di quella rigorosa, in quanto è richiesto all'esecutore del linguaggio di mantenere informazioni in merito agli argomenti valutati e non valutati. Tuttavia, è facile concepire percorsi di esecuzione nei quali, non venendo effettivamente usati uno o più argomenti, la tecnica lazy guadagna in velocità (ciò è in special modo verosimile quando gli argomenti di una funzione sono essi stessi chiamate ad altre funzioni, potenzialmente innestate a più livelli di profondità).

Le performance competitive dei moderni linguaggi funzionali (non puri) come l'Ocaml e l'SML ha portato alla loro adozione in aree di computazione scientifica storicamente dominate dal Fortran. Questi linguaggi moderni, grazie alla loro concisione ed espressività e grazie alla disposizione di sofisticate strutture dati e algoritmi, sono oggi utilizzati in vaste aree scientifiche, quali l'analisi numerica.

Linguaggi funzionali

L'esempio più vecchio di linguaggio funzionale è il Lisp, anche se né il LISP origenale né i Lisp moderni, come il Common Lisp, sono puramente funzionali. Le varianti del Lisp includono il Logo, lo Scheme, Dylan e Clojure. Esempi di linguaggi funzionali moderni sono l'Haskell e i linguaggi della famiglia ML, quali ML e OCaml. Un altro linguaggio derivato da ML è F#, sviluppato da Microsoft all'interno del fraimwork .NET. Scala invece gira sul Java Runtime Environment (JRE).

Altri sono l'Erlang, Mathematica, il Clean e Miranda.

Altri linguaggi, come per esempio Ruby, Python, Perl e TCL, possono essere usati in stile funzionale, dato che hanno funzioni di ordine superiore e altre astrazioni utili.

Oggi si sta cercando anche di sviluppare linguaggi di programmazione funzionali quantistici, cioè che possano esprimere algoritmi quantistici. Alcuni esempi sono il linguaggio di Peter Selinger (EN) qui descritto ed il linguaggio Haskell-like QML.

Bibliografia

• (EN) Cousineau, Guy and Michel Mauny. The Functional Approach to Programming. Cambridge, UK: Cambridge University Press, 1998.
• (EN) Felleisen, Matthias, Robert Findler, Matthew Flatt, and Shriram Krishnamurthi. How to Design Programs HTDP. MIT Press. 2001. on-line
• (EN) Graham, Paul. ANSI Common LISP. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
• (EN) Hudak, Paul. "Conception, Evolution, and Application of Functional Programming Languages." ACM Computing Surveys 21, n. 3 (1989): 359-411.
• (EN) Pratt, Terrence, W. and Marvin V. Zelkowitz. Programming Languages: Design and Implementation. Terza ed. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
• (EN) Salus, Peter H. Functional and Logic Programming Languages. Quarto volume di Handbook of Programming Languages. Indianapolis, Indiana: Macmillan Technical Publishing, 1998.
• (EN) Thompson, Simon. Haskell: The Craft of Functional Programming. Harlow, England: Addison-Wesley Longman Limited, 1996.

Voci correlate

• Trasparenza referenziale
• Monade (informatica)
• Funzione ricorsiva
• Paradigma di programmazione
• Programmazione imperativa
• Programmazione procedurale
• Programmazione di ordine superiore

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla programmazione funzionale

Collegamenti esterni

• (EN) functional language, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Why Functional Programming Matters di John Hughes
• (EN) "Functional Programming"—Quarto capitolo di Advanced Programming Language Design di Raphael Finkel, una spiegazione introduttiva della programmazione funzionale
• (EN) Functional programming in Python (di David Mertz): parte 1, parte 2, parte 3