Является ли церковная цифровая кодировка натуральных чисел излишне сложной?

Question

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

zero: λf. λx. x
increment: λf. λx. f ((n f) x)

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

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

zero: λ
increment: λf. λ. f

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

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

Answer 1

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

Интуитивно понятный способ размышления о кодировке Церкви заключается в том, что цифра n представлена ​​действием итерации n раз.Это облегчает разработку комбинаторов, таких как plus, просто используя итерацию, закодированную в числе.Нет необходимости в причудливых комбинаторах для рекурсии.

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

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

Answer 2

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