Знакомство с λ-исчислением

Лямбда-исчисление заложено в основу многих функциональных языков программирования, таких как LISP, предоставляя особый язык, подходящий для описания любой символической информации. Выражения в нем представляют собой либо функцию, либо применение одного выражения как функции к другому.

Так, например, ноль определяется в лямбда-исчислении как функция (здесь и далее используется вариант записи, используемый в языке Python)

lambda x: lambda y: y,

а оператор увеличения на единицу вводится как функция

lambda n: lambda f: lambda x: f ((n (f)) (x)).

Нетрудно убедиться, что тогда 1 соответствует выражению

lambda x: lambda y: x (y),

2 соответствует

lambda x: lambda y: x (x (y)),

и так далее.

Об этих и других интересных вещах, касающихся лямбда-исчисления, можно прочесть на странице Википедии.