Комбинаторы

Теория комбинаторов была разработана до создания лямбда-исчисления, однако мы будем рассматривать ее в терминах лямбда-исчисления. Комбинатором будем называть лямбда-терм, не содержащий свободных переменных. Такой терм является замкнутым;т.е. он имеет фиксированный смысл независимо от значения любых переменных.

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

I является функцией идентичности, которая возващает свой аргумент. К служит для создания постоянных (константных) функций: применив его к аргументу а, получим функцию λх.а, которая возвращает а независимо от переданного ей аргумента. Комбинатор S является «разделяющим»: он использует две функции и аргумент и «разделяет» аргумент между функциями.

Теорема 3. Для любого лямбда-терма t существует терм t', не содержащий лямбда-абстракций и составленный из комбинаторов S, К, I и переменных, такой что FV(t') = FV(t) и t' = t.

Эту теорему можно усилить, поскольку комбинатор I может быть выражен в терминах S и К. Действительно, для любого А выполняется:

Применяя η -конверсию, получаем, что I = S К А для любого А. Будем использовать А = К. Таким образом, I = S К К, и I можно исключать из выражений, составленных из комбинаторов.

Мы представили комбинаторы как некоторые лямбда-термы, однако имеется теория, в которой они являются базовым понятием. Так же, как и в лямбда-исчислении, определяется формальный синтаксис, который вместо лямбда-абстракций содержит комбинаторы. Вместо правил α, β и η -конверсии, вводятся правила конверсии для выражений, содержащих комбинаторы, например К х у -> х. Как независимая теория, теория комбинаторов обладает многими аналогиями с лямбда-исчислением, в частности, для нее выполняется теорема Черча-Россера. Однако эта теория менее интуитивно понятна.

Комбинаторы представляют не только теоретический интерес. Лямбда-исчисление может рассматриваться как простой функциональный язык программирования, составляющий ядро реальных языков программирования, таких как ML или Haskell. Теорема 3 показывает, что лямбда-исчисление может быть «скомпилировано» в «машинный код» комбинаторов. Комбинаторы используются как метод реализации функциональных языков на уровне программного, а так же аппаратного обеспечения.