Чистое лямбда-исчисление? Вот грамматика для всего языка:
e ::= x | e1 e2 | \x . e
Все, что у вас есть, это переменные, приложение функций и создание функций. По мощности это эквивалентно машине Тьюринга. Для таких конструкций, как
, существуют хорошо известные кодировки (обычно "церковные кодировки").
- если-то-иначе
- во время дел
- рекурсия
и такие типы данных, как
- Booleans
- 1019 * целые числа *
- запись
- списки, деревья и другие рекурсивные типы
Кодирование в лямбда-исчислении может быть очень увлекательным - наши студенты сделают это на курсе иностранных языков будущей весной.