Как говорится, meet the true, pure, unspoilt Lambda =) Лямбда-исчисление как язык программирования: булёвские значения, чёрчевские нумералы. Основные арифметические и логические операции.
Булевская арифметика на Лямбде
Code
True = \x.\y.x
False = \x.\y.y
If = \c.\t.\e.c t e
Пример:
Code
If True A B = (\c.\t.\e.c t e) (\x.\y.x) A B = (\t.\e.(\x.\y.x) t e) A B = (\t.\e.t) A B = A
Далее для удобства вместо конструкции If Cond then A else B буду писать Cond?A:B.
Основные логические операции:
Code
Not = \x.x?False:True
Xor = \x.\y.x?(Not y):y
And = \x.\y.x?y:False
Or = \x.\y.x?True:y
Чёрчевские нумералы
Для представления чисел в лямбде введём следующую конструкцию:
Code
0 = False = \f.\x.x
1 = \f.\x.f x
2= \f.\x.f (f x)
...
n = \f.\x.f^n x
То есть это очень напоминает индуктивное определение: x - база, начало; f - переход к следующему. Тогда достаточно очевидно вытекают основные операции для работы с числами:
Code
Inc = \n.\f.\x.f (n f x)
Add = \m.\n.\f.\x.m f (n f x)
Mul = \m.\n.\f.\x.m (Add n) 0
Pow = \m.\n.\f.\x.m (Mul n) 1
IsZero = \n.n (\x.False) True
IsOdd = \n.n Not False
