Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It forms the theoretical basis for functional programming languages like Lisp, Haskell, and F#.
Der in den 1930er Jahren von Alonzo Church entwickelte Lambda-Kalkül bietet ein minimalistisches, aber dennoch leistungsstarkes Framework zur Definition und Anwendung von Funktionen. Seine gesamte Syntax besteht aus nur drei Komponenten: Variablen (z. B. `x`), Abstraktionen und Anwendungen. Eine Abstraktion, auch Lambda-Funktion genannt, ist eine anonyme Funktionsdefinition, geschrieben als [latex]lambda xM[/latex], wobei `x` der Eingabeparameter und `M` der Funktionskörper ist. Eine Anwendung, geschrieben als `MN`, repräsentiert die Anwendung der Funktion `M` auf das Argument `N`. Berechnungen im Lambda-Kalkül erfolgen über einen Prozess namens Beta-Reduktion. Dabei wird die Anwendung einer Lambda-Funktion auf ein Argument aufgelöst, indem das Argument durch die gebundene Variable im Funktionskörper ersetzt wird. Beispielsweise reduziert sich die Anwendung von [latex](lambda x.x+1)[/latex] auf `3` zu `3+1`.
Despite its sparse syntax, lambda calculus is Turing complete. It can represent numbers (Church numerals), booleans, data structures, and control flow (like recursion) purely through functions. This demonstrates that the concept of a function is sufficient for universal computation. This contrasts with the Turing machine model, which is based on state and mutation. The Church-Rosser theorem is a key property of lambda calculus, stating that the order in which reductions are applied does not change the final result, a property known as confluence. This makes reasoning about program behavior much simpler than in imperative models where the order of state changes is critical.
Der Lambda-Kalkül hat einen tiefgreifenden Einfluss auf Programmiersprache Lambda-Kalkül ist der direkte Vorfahre des funktionalen Programmierparadigmas. Konzepte, die heute in vielen Sprachen üblich sind, wie Funktionen erster Klasse (die Funktionen als Daten behandeln), Funktionen höherer Ordnung (die andere Funktionen als Argumente entgegennehmen), Closures (Funktionen, die ihre lexikalische Umgebung erfassen) und Currying, haben alle ihren Ursprung im Lambda-Kalkül. Sprachen wie Lisp gehörten zu den ersten, die diese Ideen implementierten, und moderne Sprachen von Haskell über JavaScript bis Python haben sie tief in ihr Design integriert.
Verwandt mit: Lambda-Kalkül, funktionale Programmierung, Alonzo Church, Beta-Reduktion, Funktionen höherer Ordnung, Lisp, Haskell, formale Systeme, Berechenbarkeit, Typentheorie.