Die Lambda-Kalkül ist ein formales System der mathematischen Logik zur Darstellung von Berechnungen auf Basis von Funktionsabstraktion und -anwendung mittels Variablenbindung und -substitution. Es handelt sich um ein universelles Berechnungsmodell, mit dem sich jede Turingmaschine simulieren lässt. Es bildet die theoretische Grundlage für funktionale Programmiersprachen wie Lisp, Haskell und 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`.
Trotz seiner spärlichen Syntax ist die Lambda-Rechnung Turing-vollständig. Sie kann Zahlen (Church-Zahlen), Boolesche Werte, Datenstrukturen und Kontrollflüsse (wie Rekursion) rein durch Funktionen darstellen. Dies zeigt, dass das Konzept einer Funktion für universelle Berechnungen ausreicht. Dies steht im Gegensatz zum Turingmaschinen-Modell, das auf Zustand und Mutation basiert. Der Church-Rosser-Satz ist eine Schlüsseleigenschaft der Lambda-Rechnung. Er besagt, dass die Reihenfolge der Reduktionen das Endergebnis nicht verändert (eine Eigenschaft, die als Konfluenz bezeichnet wird). Dies macht das Denken über das Programmverhalten wesentlich einfacher als in imperativen Modellen, bei denen die Reihenfolge der Zustandsänderungen entscheidend ist.
Lambda calculus has had a profound influence on Programmiersprache 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.