Lambda Calculus

Lambda calculus e un sistem formal pentru descrierea functiilor si a computatiei, dezvoltat de Alonzo Church in anii 1930. E fundamentele matematice ale programarii functionale si o alternativa echivalenta ca putere cu Masina Turing.

Avansat 14 min 06 July 2026
lambda calculus Church funcțional Haskell programare

Ce este Lambda Calculus?

Inventat de Alonzo Church in 1932-1936, lambda calculus e cel mai mic limbaj de programare universal. Are doar trei constructii:

Cele trei reguli

  1. Variabila — $x$, $y$, $z$
  2. Abstragere — $\lambda x. M$ (definirea unei functii cu parametrul $x$ si corpul $M$)
  3. Aplicare — $M\ N$ (aplicarea functiei $M$ la argumentul $N$)

Exemple

  • $\lambda x. x$ — functia identitate
  • $\lambda x. \lambda y. x$ — primul argument (true in biserica Church)
  • $\lambda x. \lambda y. y$ — al doilea argument (false)
  • $\lambda f. \lambda x. f\ (f\ x)$ — aplica $f$ de doua ori (numeralul Church 2)

Puterea de calcul

Lambda calculus e Turing-complet — poate exprima orice calcul pe care un computer il poate face. E chiar echivalent cu Masina Turing (teza Church-Turing).

Programare functionala

Limbajele functionale (Haskell, Lisp, Scala, ML) se bazeaza direct pe lambda calculus:

  • Functii ca valori de prima clasa
  • Currying (functii cu mai multi parametri ∈ functii cu un parametru care returneaza functii)
  • Imutabilitate
  • Evaluare lenesa (lazy evaluation)