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 ${\displaystyle x}$ on λ-term.
• Kui ${\displaystyle t}$ on λ-term ja ${\displaystyle x}$ on muutuja, siis ${\displaystyle \lambda x.t}$ on λ-term, mis on abstraktsioon.
• Kui ${\displaystyle t}$ ja ${\displaystyle s}$ on λ-termid, siis ${\displaystyle ts}$ on λ-term, mis on aplikatsioon.^[1]

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

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