Интернет магазин китайских планшетных компьютеров

Компьютеры - Лямбда-исчисление - Чистое

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

Аппликация и абстракция

В основу λ-исчисления положены две фундаментальные операции: аппликация и абстракция. Аппликация означает применение или вызов функции по отношению к заданному значению. Её обычно обозначают , где f — функция, а a — значение. Это соответствует общепринятой в математике записи f, которая тоже иногда используется, однако для λ-исчисления важно то, что f трактуется как алгоритм, вычисляющий результат по заданному входному значению. В этом смысле аппликация f к a может рассматриваться двояко: как результат применения f к a, или же как процесс вычисления . Последняя интерпретация аппликации связана с понятием β-редукции.

Абстракция или λ-абстракция в свою очередь строит функции по заданным выражениям. Именно, если — выражение, свободно содержащее x, тогда запись означает: λ функция от аргумента x, которая имеет вид t) обозначает функцию . Таким образом, с помощью абстракции можно конструировать новые функции. Требование, чтобы x свободно входило в t, не очень существенно — достаточно предположить, что , если это не так.