Введение в теорию программирования. Функциональный подход

       

Теоретические сведения


Согласно определению, комбинатором называется ламбда-выражение, не содержащее связанных переменных. Например, если в законе коммутативности

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.



Содержание раздела