LCME Суббота, 18.11.2017, 15:06
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Форум » Билеты к экзаменам » Программирование » 03 Лямбда как язык программирования
03 Лямбда как язык программирования
freidomДата: Воскресенье, 27.12.2009, 18:18 | Сообщение # 1
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: Offline
Как говорится, 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
 
Форум » Билеты к экзаменам » Программирование » 03 Лямбда как язык программирования
Страница 1 из 11
Поиск:

Copyright Freidom © 2017 Хостинг от uCoz