Il lambda calcolo è un sistema formale di logica matematica per esprimere calcoli basati sull'astrazione di funzioni e sull'applicazione tramite binding e sostituzione di variabili. È un modello di calcolo universale che può essere utilizzato per simulare qualsiasi macchina di Turing. Costituisce la base teorica per linguaggi di programmazione funzionale come Lisp, Haskell e F#.
Developed by Alonzo Church in the 1930s, lambda calculus provides a minimalist yet powerful framework for defining and applying functions. Its entire syntax consists of just three components: variables (e.g., `x`), abstractions, and applications. An abstraction, or lambda function, is an anonymous function definition, written as [latex]\lambda x.M[/latex], where `x` is the input parameter and `M` is the body of the function. An application, written as `M N`, represents applying function `M` to argument `N`. Computation in lambda calculus proceeds through a process called beta reduction, where an application of a lambda function to an argument is resolved by substituting the argument for the bound variable within the function’s body. For example, applying [latex](\lambda x.x+1)[/latex] to `3` reduces to `3+1`.
Nonostante la sua sintassi scarna, il lambda calcolo è Turing completo. Può rappresentare numeri (numeri di Church), booleani, strutture dati e flussi di controllo (come la ricorsione) esclusivamente tramite funzioni. Ciò dimostra che il concetto di funzione è sufficiente per il calcolo universale. Ciò contrasta con il modello della macchina di Turing, che si basa su stato e mutazione. Il teorema di Church-Rosser è una proprietà chiave del lambda calcolo, che afferma che l'ordine in cui vengono applicate le riduzioni non modifica il risultato finale, una proprietà nota come confluenza. Ciò rende il ragionamento sul comportamento del programma molto più semplice rispetto ai modelli imperativi in cui l'ordine dei cambiamenti di stato è critico.
Lambda calculus has had a profound influence on linguaggio di programmazione design. It is the direct ancestor of the functional programming paradigm. Concepts that are now common in many languages, such as first-class functions (treating functions as data), higher-order functions (functions that take other functions as arguments), closures (functions that capture their lexical environment), and currying, all have their roots in lambda calculus. Languages like Lisp were among the first to implement these ideas, and modern languages from Haskell to JavaScript and Python have integrated them deeply into their design.