Синтаксис термов

Как в математике невероятное количество направлений — анализ, ТФКП и т. д. — держится на нескольких аксиомах, которые принимаются на веру, так и в λ-исчислении всего три конструкции являются основой. Весь язык строится из переменной, абстракции и аппликации; всё остальное — числа, логика, структуры данных и рекурсия — появляется уже поверх них.

где $x$ — переменная; $(\lambda x.\,M)$ — абстракция: анонимная функция с параметром $x$ и телом $M$; $(M\,N)$ — аппликация: применение функции $M$ к аргументу $N$. При этом $N$ может быть любым термом: переменной $x$, другой аппликацией $(P\,Q)$ или целой абстракцией $(\lambda y.\,y)$. Например: $M\,x$, $M\,(P\,Q)$, $M\,(\lambda y.\,y)$.

Несколько важных замечаний: аппликация лево-ассоциативна: $M\,N\,P \equiv ((M\,N)\,P)$; тело абстракции простирается максимально вправо: $\lambda x.\,M\,N \equiv \lambda x.\,(M\,N)$; цепочка абстракций сокращается: $\lambda x\,y\,z.\,M \equiv \lambda x.\,\lambda y.\,\lambda z.\,M$.

Терм — это дерево: листья — переменные, внутренние узлы — абстракции и аппликации. Полезно приучить себя видеть терм как дерево, а не как строку.