Le codage numérique de l'église des nombres naturels est-il inutilement compliqué?

Question

La Structure et interprétation des programmes informatiques Livre I Lire

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

Cela m'a semblé assez compliqué et il m'a fallu beaucoup de temps pour le comprendre et en dériver un (λf.λx. f x) et deux (λf.λx. f (f x)).

Ne serait-il pas beaucoup plus simple de coder les nombres de cette façon à la place, zéro étant le lambda vide?

zero: λ
increment: λf. λ. f

Maintenant, il est trivial d'en dériver un (λ. λ) et deux (λ. λ. λ), etc.

Cela semble être une manière beaucoup plus évidente et intuitive de représenter des nombres avec Lambdas. Y a-t-il un problème avec cette approche et donc une bonne raison pour laquelle les chiffres de l'église fonctionnent comme ils le font? Cette approche est-elle déjà attestée?

Answer 1

Votre encodage (zéro: λx.x, une: λx.λx.x, deux: λx.λx.λx.x, etc.) facilite la définition de l'incrément et de la diminution, mais au-delà de cela, il devient assez difficile de développer des combinateurs pour votre encodage. Par exemple, comment définissez-vous isZero?

Une façon intuitive de penser au codage de l'église est qu'un chiffre n est représenté par l'action d'itérer n fois. Cela facilite le développement de combinateurs comme plus en utilisant simplement l'itération codée dans le nombre. Pas besoin de combinateurs fantaisistes pour la récursivité.

Dans le codage de l'église, chaque numéro a la même interface: il faut deux arguments. Pendant votre codage, chaque numéro est défini par le nombre d'arguments qu'il faut, ce qui rend vraiment difficile de fonctionner uniformément.

Une autre façon d'encoder les chiffres serait de penser aux nombres comme n = 0 | S n, et utilisez un codage de vanille pour les syndicats.

Answer 2

La syntaxe proposée pour les chiffres n'est pas valable dans le calcul de lambda, tandis que les chiffres de l'église sont en effet des constructions valides dans le calcul de lambda. C'est donc une raison possible pour laquelle les chiffres de l'église sont comme ils sont - le numéro de numéro doit adhérer au calcul lambda ' définition D'une manière qui permet également des opérations supplémentaires également définies dans le calcul Lambda (incrément, par exemple) pour fonctionner sur les nombres codés.