Лямбда-исчисление. Аппликация, абстракция, редукция, преобразование.

Это простейший из семейства прототипных языков программирования, чистое λ-исчисление, термы которого, называемые также объектами (обами), или λ-термами, построены исключительно из переменных применением аппликации и абстракции. Изначально наличия каких-либо констант не предполагается.

Лямбда-исчисление: В основе лежит 2 операции: Аппликация: Означает применение или вызов функции по отношению к заданному значению )

где - алгоритм, вычисления по заданному входному значению

Абстракция: Строит функции по заданным выражением

Если это выражение свободно содержит х, тогда означает, что лямбда функция от аргумента х, которая имеет вид , означает функцию х->t[x] .

Редукция: Поскольку выражение обозначает функцию, ставящую в соответствие каждому значение , то для вычисления выражения

, в которое входят и аппликация и абстракция, необходимо выполнить подстановку числа 3 в терм вместо переменной . В результате получается . Это соображение в общем виде записывается как

.