Lambda-arvutus

Lambda-arvutus (λ-arvutus) on formaalne arvutuste esitusviis. Seda kasutatakse matemaatilises loogikas ja funktsionaalprogrammeerimises.

Lambda-termid

Avaldis λ-arvutuses koosneb kolme tüüpi λ-termidest:

• Muutuja $x$ on λ-term.
• Kui $t$ on λ-term ja $x$ on muutuja, siis $\lambda x.t$ on λ-term, mis on abstraktsioon.
• Kui $t$ ja $s$ on λ-termid, siis $ts$ on λ-term, mis on aplikatsioon.

Abstraktsioon on λ-arvutustes funktsiooni kirjeldus kujul $\lambda x.t$, kus $x$ on funktsiooni sisend ja $t$ avaldis, mida arvutatakse. Näiteks $\lambda x.x+2$ tähistab funktsiooni $f(x)=x+2$. Kirjeldatud funktsioon on anonüümne ehk nimetu.

Aplikatsioon $ts$ tähistab funktsiooni $t$ väljakutsumist sisendiga $s$. Näiteks $\lambda x.x+23$ tähistab funktsiooni $\lambda x.x+2$ väljakutset sisendiga $3$: $f(x)=x+2=3+2=5$.