Il calcolo lambda è un sistema formale che permette di definire e manipolare funzioni anonime, ovvero funzioni senza nome. Il calcolo lambda è stato inventato da Alonzo Church negli anni ’30 come strumento per lo studio della logica matematica e della computabilità. Il calcolo lambda è alla base di molti linguaggi di programmazione funzionale, come Haskell, Lisp e Scala, e ha influenzato anche linguaggi imperativi come Java e Python.
Il calcolo lambda si basa su tre concetti fondamentali: le variabili, le astrazioni e le applicazioni. Le variabili sono dei simboli che rappresentano dei valori. Le astrazioni sono delle espressioni che definiscono delle funzioni anonime, usando il simbolo λ seguito da una variabile (il parametro) e da un’altra espressione (il corpo della funzione) che ha lo scopo di dirci il valore di quella variabile. Le applicazioni sono delle espressioni che rappresentano l’invocazione di una funzione su un argomento, usando la notazione prefissa.
Ad esempio, un’espressione molto semplice è (λx.x+y)3, dove il simbolo λ sta per lambda, la prima x indica il parametro che deve essere modificato, l’espressione dopo il punto è il risultato finale mentre il numero alla fine dell’espressione è il valore che deve essere passato al parametro. Il risultato sarà 3 + y, mentre se avessimo scritto (λy.x+y)3 il risultato sarebbe stato x + 3.
Una funzione potrebbe restituire anche un’altra funzione: in questo caso l’espressione si scrive nella formula (λx.(λy.x+y)3. Vediamo i vari passaggi:
(λx.(λy.x+y)3
λx.(x+3)
Dato che non abbiamo altri valori da sostituire il risultato finale è x+3.
Il calcolo lambda permette di esprimere in modo conciso e elegante delle operazioni complesse, usando solo le tre regole sopra descritte. Il calcolo lambda è anche un modello di computazione universale, ovvero in grado di simulare qualunque altra macchina astratta. Il calcolo lambda ha quindi un grande valore teorico e pratico per lo studio dei linguaggi di programmazione e dei problemi computazionali.
Riduzione lambda
La riduzione lambda è una tecnica di programmazione funzionale che permette di semplificare le espressioni lambda eliminando le variabili libere. Una espressione lambda è una funzione anonima che può essere definita in linea, senza doverle dare un nome. Le variabili libere sono quelle variabili che appaiono in una espressione lambda ma che non sono né parametri né variabili locali della funzione.
Per esempio, consideriamo la seguente espressione lambda:
(λx.x + y)3
Questa funzione prende come parametro x e restituisce il valore di x + y. Tuttavia, mentre il valore di x sarà 3 come abbiamo visto precedentemente, y è una variabile libera, perché non è definita né come parametro né come variabile locale della funzione. Quindi, il valore di questa espressione dipende dal valore di y nell’ambiente in cui viene valutata.
La riduzione lambda consiste nel sostituire le variabili libere con i loro valori nell’ambiente di valutazione, ottenendo una espressione lambda equivalente ma più semplice. Per esempio, se nell’ambiente di valutazione y vale 2, possiamo ridurre la precedente espressione lambda a:
(λx.x + 2)3
(λx.3 + 2)
(λx.5) -> x = 5
Questa funzione non ha più variabili libere e restituisce sempre lo stesso valore, indipendentemente dall’ambiente in cui viene valutata.
La riduzione lambda può essere applicata anche a espressioni lambda più complesse, che contengono altre espressioni lambda al loro interno. In questo caso, bisogna fare attenzione a non sostituire le variabili che sono legate da altre espressioni lambda, perché altrimenti si potrebbero creare conflitti di nomi. Per esempio, consideriamo la seguente espressione lambda:
(λx.(λy.x + y)x)2
Questa funzione prende come parametro x e restituisce il valore di una altra funzione anonima che prende come parametro y e restituisce il valore di x + y. Questa altra funzione anonima viene applicata al valore di x stesso. Quindi, il valore finale di questa espressione è 2 + 2 = 4. Vediamo i passaggi:
(λx.(λy.x + y)x)2
In questo caso l’argomento 2 sostituirà tutte le variabili x:
λx(λy.2 + y)2
λx(2 + 2) -> x = 4
Se applicassimo la riduzione lambda a questa espressione senza fare attenzione, potremmo ottenere:
(λx.(λy.x + y)x)2
(λx.(λ2.x + 2)x)
Questa funzione è errata, perché non si può usare un numero come nome di un parametro. Inoltre, il valore finale sarebbe diverso, perché sarebbe x + 2 invece di 2 + 2.
Per evitare questo errore, dobbiamo tenere conto del fatto che quella y è una variabile legata dall’espressione lambda interna, e quindi non deve essere sostituita con il valore di x.
La riduzione lambda è utile per semplificare le espressioni lambda e per renderle più facilmente comprensibili e analizzabili. Inoltre, la riduzione lambda può essere usata come base per implementare altri meccanismi di programmazione funzionale, come la ricorsione o il currying.