Comment définir des nombres entiers positifs et négatifs et des nombres rationnels dans le lambda-calcul

Question

J'étudie le lambda-calcul et je ne possède que des connaissances de base à ce sujet. Je lis beaucoup de site et de papier et je comprends la façon dont la logique (T/F/et/ou), le prédicat et le successeur fonctionnent mais je ne sais pas comment accomplir d'autres choses en programmation en utilisant ce calcul lambda. Je veux savoir comment je pourrais définir des entiers positifs et négatifs en utilisant des paires de nombres naturels et des nombres rationnels comme des paires d'entiers dans le lambda-calcul.

Nous vous remercions de votre aide.

Answer 1

Vous devriez jeter un oeil au Church encoding. Par exemple, il définit les entiers comme des compteurs de boucle. Étant donné une fonction f et une x variable si:

• x est jamais mis en correspondance f, il est une identité (équivalent de 0)
• x mis en correspondance une fois à f, qui donne f x, il donne une boucle count (1)
• x mappé deux, ce qui donne f (f x), c'est deux boucles (2); etc.

Le codage d'église définit les nombres signés en termes de paires. Par conséquent, en utilisant seulement des fonctions et des combinaisons d'entre elles, l'encodage de l'Église englobe l'arithmétique et la logique.