Является ли кодирование натуральных чисел Чёрчем излишне сложным?

Question

В книге Структура и интерпретация компьютерных программ , которую я читал, числа Чёрча представлены с помощью определения нуля и функции приращения

родовое слово

Мне это показалось довольно сложным, и мне потребовалось очень много времени, чтобы понять это и получить один (λf.λx. f x) и два (λf.λx. f (f x)).

Не было бы проще закодировать числа таким образом, если бы ноль был пустой лямбдой?

родовое слово

Теперь легко получить один (λ. λ) и два (λ. λ. λ) и так далее.

Это кажется гораздо более очевидным и интуитивно понятным способом представления чисел с помощью лямбда-выражений.Есть ли какие-то проблемы с этим подходом и, следовательно, веская причина, почему числа Черча работают именно так?Этот подход уже подтвержден?

Answer 1

Ваша кодировка (ноль: λx.x, один: λx.λx.x, два: λx.λx.λx.x и т. д.) позволяет легко определять приращение и декремент, но помимо этого становится довольно сложно разработать комбинаторы для вашей кодировки.Например, как бы вы определили isZero?

Интуитивно понятное представление о кодировке Чёрча состоит в том, что числовой кодовый кодовый код представлен действием повторения порождающего кодового кода.Это позволяет легко разрабатывать комбинаторы, такие как n, просто используя итерацию, закодированную в числе.Для рекурсии не нужны причудливые комбинаторы.

В кодировке Чёрча у каждого числа один и тот же интерфейс: он принимает два аргумента.В вашей кодировке каждое число определяется числом принимаемых аргументов, что усложняет единообразную работу.

Другой способ кодирования чисел - думать о числах как о n= 0 |S n и используйте обычную кодировку для союзов.

Answer 2

Предложенный синтаксис для числительных недопустим в лямбда-исчислении, тогда как числа Чёрча действительно являются допустимыми конструкциями в лямбда-исчислении.Так что это возможная причина того, почему числа Чёрча такие, какие они есть - кодировка чисел должна соответствовать лямбда-исчислению ' определение таким образом, чтобы разрешить дальнейшие операции, также определенные в лямбда-исчислении (например, приращение), для работы с закодированными числами.