Если числа мы худо-бедно научились описывать, то с булеанами все не так просто. Спойлер: false := 0, true := 1 — не лучший способ кодирования. Вместо этого мы совместим булеаны с if'ами. Если в классических языках условия записываются как cond ? then : otherwise или then if cond else otherwise, то в λ-исчислении это пишется очень лаконично: cond then otherwise. Требовать, соответственно, мы будем того, что true x y -> x и false x y -> y. Реализация тривиальна:
true := \x. \y. x false := \x. \y. y
Всякие простые операции над булами тоже можно записать. Например, p && q — это то же самое, что p ? q : p (проверьте!). С "или" ситуация похожая. Другие операторы не сильно сложнее. Реализация:
and := \p. \q. p q p or := \p. \q. p p q not := \p. p false true xor := \p. \q. p (not q) q
Теперь хотелось бы связать числа и булеаны. Простейший способ это сделать — ввести предикат iszero. Тут все просто. Число — это шорткат для применения функции к аргументу несколько раз. Если это число 0, то этот аргумент не изменится, значит он должен быть true. Схема реализации:
iszero := \n. n (...) true
Если число не 0 — функция применится к аргументу. Функция, ясное дело, должна возвращать false, а аргумент нас вообще не интересует:
iszero := \n. n (\x. false) true
Простейшая структура данных в λ-исчислении — пара. Хотя, казалось бы, где вообще можно хранить данные, если есть только функции?
Здесь мы воспользуемся трюком. Пусть p — какая-нибудь пара, состоящая из двух элементов a и b. Тогда пара будет функцией, которая принимает callback-функцию f и вызывает ее от этих двух аргументов — a и b. Вот, например, пара из чисел 1 и 2:
\f. f 1 2
А вот функция, которая конструирует пару по двум своим аргументам:
pair := \a. \b. \f. f a b
Для получения первого или второго элемента пары в качестве callback-функции мы будем подавать функцию, которая принимает два аргумента и возвращает, соответственно, либо первый, либо второй.
first := \p. p (\a. \b. a) second := \p. p (\a. \b. b)
Пример: first (pair 5 7) -> 5, second (pair 5 7) -> 7.
Кстати, вам уже должны быть знакомы функции \a. \b. a и \a. \b. b — это же булеаны! Иначе говоря:
first := \p. p true second := \p. p false (pair 5 7) true -> 5 (pair 5 7) false -> 7
Это, безусловно, абъюз нотации, зато демонстрирует, что в разных контекстах могут появиться одинаковые функции.