Теоретические сведения
Согласно определению, комбинатором называется ламбда-выражение, не содержащее связанных переменных. Например, если в законе коммутативности
x+y = y+x
определить функцию
alpha(x,y) = x + y
и оператор С
(Cf)(x,y) = f(xy),
то данный закон примет следующий вид:
alpha = C alpha.
Формальная система комбинаторной логики естественным образом отображается на языки функционального программирования. В качестве иллюстрации определим SML-функции для базисных комбинаторов I, K, S:
fun Ix = x; fun Kxy = x; fun Sxyz = xz(yz);
Напомним, что характеристики перечисленных комбинаторных термов в рамках формальной системы комбинаторной логики имеют вид:
Ix = x, Sxyz = xz(yz), Kxy=x.
