Obsah
Lambda kalkul je teorie funkcí založená na velmi jednoduchém jazyce. Základní prvky tohoto jazyka (tzv. lambda výrazy) jsou pouze tři: proměnná, aplikace a abstrakce.
- Proměnná reprezentuje blíže nespecifikovanou hodnotu. Označuje se identifikátorem, např. x, y, z.
- Aplikace představuje volání funkce s jedním argumentem. Funkce i argument jsou zadány jako lambda výrazy ve tvaru (e1 e2).
- Funkce v lambda kalkulu jsou reprezentovány ve formě abstrakce tvořené proměnnou označující parametr a tělem ve tvaru lambda výrazu. Abstrakci můžeme zapisovat ve tvaru \x -> e, kde x je jméno parametru a e je lambda výraz tvořící tělo abstrakce.
Pokud se některá proměnná x vyskytuje v kontextu abstrakce \x -> e, říkáme, že je ve výrazu e vázaná. Není-li proměnná vázaná, pak ji označujeme jako volnou.
 | Příklad 2.1. |
| Mějme lambda výraz \f -> (f x). Potom v podvýrazu (f x) je proměnná f vázaná a proměnná x volná. |