Programmazione funzionale

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. Solitamente questo approccio viene usato maggiormente in ambiti accademici piuttosto che industriali. 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.

lezione Programmazione funzionale
	Tipo: lezione
	Materia: Linguaggi di programmazione

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 deve 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, e 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 '30 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 '50. 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. Il linguaggio Scheme fu un successivo tentativo di semplificare e migliorare il LISP. Negli anni '70, all'Università di Edimburgo fu creato il linguaggio ML e all'Università di Kent David Turner creò il linguaggio Miranda. Il linguaggio Haskell fu creato e rilasciato alla fine degli anni '80 come tentativo di mettere insieme molte delle idee della ricerca sulla programmazione funzionale.

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. Nel seguente esempio:

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

non si può eliminare getchar() come si è fatto per sqrt(2), dato che in C, getchar() può restituire due valori diversi per due chiamate diverse.

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 sono parte del linguaggio 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.

Proprio per la necessità del mondo informatico moderno di sviluppare programmi velocemente e esenti da bug, anche a scapito di un po' di efficienza, anche i linguaggi imperativi moderni stanno includendo queste tecniche di gestione automatica dei compiti di basso livello. 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 pigra può essere meno efficiente dato che bisogna tener traccia delle funzioni non ancora valutate ma, comunque, rende più semplice la programmazione in molti modi.

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 originale né i Lisp moderni, come il Common Lisp, sono puramente funzionali. Le varianti del Lisp includono il Logo, lo Scheme e Dylan. Esempi di linguaggi funzionali moderni sono l'Haskell e i linguaggi della famiglia ML, quali SML e OCaml. Altri sono l'Erlang, Mathematica, il Clean e Miranda.

Altri linguaggio, 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 ((EN) homepage del progetto).

Lezioni correlate

Riferimenti

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

Collegamenti esterni

(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
(EN) Functional programming, materiale introduttivo a cura di Dan Bensen

Questo articolo include parti di un articolo inserito su Nupedia il 19 giugno 2001: reviewed and approved by the Computers group; editor, Michael Witbrock; lead reviewer, Nancy Tinkham; lead copyeditors, Ruth Ifcher and Larry Sanger.