Codage de l'église - Church encoding

En mathématiques , l' encodage Church est un moyen de représenter les données et les opérateurs dans le calcul lambda . Les chiffres de l'Église sont une représentation des nombres naturels en notation lambda. La méthode porte le nom d' Alonzo Church , qui a d'abord encodé les données dans le calcul lambda de cette façon.

Les termes qui sont généralement considérés comme primitifs dans d'autres notations (comme les entiers, les booléens, les paires, les listes et les unions étiquetées) sont mappés à des fonctions d'ordre supérieur sous le codage Church. La thèse de Church-Turing affirme que tout opérateur calculable (et ses opérandes) peut être représenté sous le codage Church. Dans le calcul lambda non typé, le seul type de données primitif est la fonction.

Le codage Church n'est pas conçu comme une implémentation pratique des types de données primitifs. Son utilisation est de montrer que d'autres types de données primitifs ne sont pas nécessaires pour représenter un calcul. La complétude est représentationnelle. Des fonctions supplémentaires sont nécessaires pour traduire la représentation en types de données communs, pour l'affichage aux personnes. Il n'est pas possible en général de décider si deux fonctions sont égales en extension en raison de l' indécidabilité de l'équivalence du théorème de Church . La traduction peut appliquer la fonction d'une manière ou d'une autre pour récupérer la valeur qu'elle représente, ou rechercher sa valeur en tant que terme lambda littéral.

Le calcul lambda est généralement interprété comme utilisant l' égalité intentionnelle . Il existe des problèmes potentiels avec l'interprétation des résultats en raison de la différence entre la définition intensionnelle et extensionnelle de l'égalité.

Chiffres de l'église

Les chiffres d'église sont les représentations des nombres naturels sous le codage d'église. La fonction d'ordre supérieur qui représente l'entier naturel n est une fonction qui mappe n'importe quelle fonction à sa composition n- fold . En termes plus simples, la "valeur" du chiffre équivaut au nombre de fois que la fonction encapsule son argument. ${\style d'affichage f}$

${\displaystyle f^{\circ n}=\underbrace {f\circ f\circ \cdots \circ f} _{n{\text{ times}}}.\,}$

Tous les chiffres de l'Église sont des fonctions qui prennent deux paramètres. Les chiffres d'église 0 , 1 , 2 , ..., sont définis comme suit dans le calcul lambda .

En commençant par 0 n'appliquant pas du tout la fonction, passez à 1 appliquant la fonction une fois, 2 appliquant la fonction deux fois, 3 appliquant la fonction trois fois, etc. :

${\displaystyle {\begin{array}{r|l|l}{\text{Number}}&{\text{Définition de la fonction}}&{\text{Expression Lambda}}\\\hline 0&0\ f\ x =x&0=\lambda f.\lambda xx\\1&1\ f\ x=f\ x&1=\lambda f.\lambda xf\ x\\2&2\ f\ x=f\ (f\ x)&2=\lambda f.\lambda xf\ (f\ x)\\3&3\ f\ x=f\ (f\ (f\ x))&3=\lambda f.\lambda xf\ (f\ (f\ x))\ \\vdots &\vdots &\vdots \\n&n\ f\ x=f^{n}\ x&n=\lambda f.\lambda xf^{\circ n}\ x\end{array}}}$

Le chiffre d'église 3 représente l'action d'appliquer une fonction donnée trois fois à une valeur. La fonction fournie est d'abord appliquée à un paramètre fourni puis successivement à son propre résultat. Le résultat final n'est pas le chiffre 3 (sauf si le paramètre fourni est 0 et que la fonction est une fonction successeur ). La fonction elle-même, et non son résultat final, est le chiffre de l'Église 3 . Le chiffre de l'Église 3 signifie simplement faire n'importe quoi trois fois. C'est une démonstration ostentatoire de ce que l'on entend par "trois fois".

Calcul avec les chiffres de l'église

Les opérations arithmétiques sur les nombres peuvent être représentées par des fonctions sur les chiffres de l'Église. Ces fonctions peuvent être définies dans le calcul lambda , ou implémentées dans la plupart des langages de programmation fonctionnels (voir conversion d'expressions lambda en fonctions ).

La fonction d'addition utilise l'identité . ${\displaystyle \operatorname {plus} (m,n)=m+n}$${\displaystyle f^{\circ (m+n)}(x)=f^{\circ m}(f^{\circ n}(x))}$

${\displaystyle \operatorname {plus} \equiv \lambda m.\lambda n.\lambda f.\lambda xm\ f\ (n\ f\ x)}$

La fonction successeur est -équivalente à . ${\displaystyle \operatorname {succ} (n)=n+1}$${\displaystyle (\operatorname {plus} \ 1)}$

${\displaystyle \operatorname {succ} \equiv \lambda n.\lambda f.\lambda xf\ (n\ f\ x)}$

La fonction de multiplication utilise l'identité . ${\displaystyle \operatorname {mult} (m,n)=m*n}$${\displaystyle f^{\circ (m*n)}(x)=(f^{\circ n})^{\circ m}(x)}$

${\displaystyle \operatorname {mult} \equiv \lambda m.\lambda n.\lambda f.\lambda xm\ (n\ f)\ x}$

La fonction d'exponentiation est donnée par la définition des chiffres d'église, . Dans la définition substituer à obtenir et, ${\displaystyle \operatorname {exp} (m,n)=m^{n}}$${\style d'affichage n\ h\ x=h^{n}\ x}$${\displaystyle h\à m,x\à f}$${\style d'affichage n\ m\ f=m^{n}\ f}$

${\displaystyle \operatorname {exp} \ m\ n=m^{n}=n\ m}$

ce qui donne l'expression lambda,

${\displaystyle \operatorname {exp} \equiv \lambda m.\lambda nn\ m}$

La fonction est plus difficile à comprendre. ${\displaystyle \operatorname {pred} (n)}$

${\displaystyle \operatorname {pred} \equiv \lambda n.\lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu)}$

Un chiffre d'église applique une fonction n fois. La fonction prédécesseur doit renvoyer une fonction qui applique son paramètre n - 1 fois. Ceci est réalisé en construisant un conteneur autour de f et x , qui est initialisé d'une manière qui omet l'application de la fonction la première fois. Voir prédécesseur pour une explication plus détaillée.

La fonction de soustraction peut être écrite sur la base de la fonction prédécesseur.

${\displaystyle \operatorname {moins} \equiv \lambda m.\lambda n.(n\operatorname {pred} )\ m}$

Table des fonctions sur les chiffres de l'église

Fonction	Algèbre	Identité	Définition de la fonction	Expressions lambda
Successeur	${\style d'affichage n+1}$	${\style d'affichage f^{n+1}\ x=f(f^{n}x)}$	${\displaystyle \operatorname {succ} \ n\ f\ x=f\ (n\ f\ x)}$	${\displaystyle \lambda n.\lambda f.\lambda xf\ (n\ f\ x)}$	...
Une addition	${\style d'affichage m+n}$	${\style d'affichage f^{m+n}\ x=f^{m}(f^{n}x)}$	${\displaystyle \operatorname {plus} \ m\ n\ f\ x=m\ f\ (n\ f\ x)}$	${\displaystyle \lambda m.\lambda n.\lambda f.\lambda xm\ f\ (n\ f\ x)}$	${\displaystyle \lambda m.\lambda nn\operatorname {succ} m}$
Multiplication	${\style d'affichage m*n}$	${\displaystyle f^{m*n}\ x=(f^{m})^{n}\ x}$	${\displaystyle \operatorname {multiply} \ m\ n\ f\ x=m\ (n\ f)\ x}$	${\displaystyle \lambda m.\lambda n.\lambda f.\lambda xm\ (n\ f)\ x}$	${\displaystyle \lambda m.\lambda n.\lambda fm\ (n\ f)}$
Exponentiation	${\style d'affichage m^{n}}$	${\style d'affichage n\ m\ f=m^{n}\ f}$	${\displaystyle \operatorname {exp} \ m\ n\ f\ x=(n\ m)\ f\ x}$	${\displaystyle \lambda m.\lambda n.\lambda f.\lambda x.(n\ m)\ f\ x}$	${\style d'affichage \lambda m.\lambda nn\ m}$
Prédécesseur *	${\style d'affichage n-1}$	${\displaystyle \operatorname {inc} ^{n}\operatorname {con} =\operatorname {val} (f^{n-1}x)}$	${\displaystyle if(n==0)\ 0\ else\ (n-1)}$	${\displaystyle \lambda n.\lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu)}$
Soustraction *	${\displaystyle mn}$	${\displaystyle f^{mn}\ x=(f^{-1})^{n}(f^{m}x)}$	${\displaystyle \operatorname {moins} \ m\ n=(n\operatorname {pred} )\ m}$	...	${\displaystyle \lambda m.\lambda nn\operatorname {pred} m}$

* Notez que dans l'encodage Church,

• ${\displaystyle \operatorname {pred} (0)=0}$
• ${\displaystyle m<=n\to ​​mn=0}$

Dérivation de la fonction prédécesseur

La fonction prédécesseur utilisée dans l'encodage Church est,

${\displaystyle \operatorname {pred} (n)={\begin{cases}0&{\mbox{if }}n=0,\\n-1&{\mbox{autrement}}\end{cases}}}$.

Pour construire le prédécesseur, nous avons besoin d'un moyen d'appliquer la fonction 1 moins de temps. Un chiffre n applique la fonction f n fois à x . La fonction prédécesseur doit utiliser le chiffre n pour appliquer la fonction n -1 fois.

Avant d'implémenter la fonction prédécesseur, voici un schéma qui encapsule la valeur dans une fonction conteneur. Nous allons définir de nouvelles fonctions à utiliser à la place de f et x , appelées inc et init . La fonction conteneur est appelée value . Le côté gauche du tableau montre un chiffre n appliqué à inc et init .

${\displaystyle {\begin{array}{r|r|r}{\text{Number}}&{\text{Using init}}&{\text{Using const}}\\\hline 0&\operatorname {init } =\operatorname {valeur} \ x&\\1&\operatorname {inc} \ \operatorname {init} =\operatorname {value} \ (f\ x)&\operatorname {inc} \ \operatorname {const} =\operatorname {valeur} \ x\\2&\operatorname {inc} \ (\operatorname {inc} \ \operatorname {init} )=\operatorname {value} \ (f\ (f\ x))&\operatorname {inc} \ (\operatorname {inc} \ \operatorname {const} )=\operatorname {value} \ (f\ x)\\3&\operatorname {inc} \ (\operatorname {inc} \ (\operatorname {inc} \ \operatorname {init} ))=\operatorname {value} \ (f\ (f\ (f\ x)))&\operatorname {inc} \ (\operatorname {inc} \ (\operatorname {inc} \ \operatorname {const } ))=\operatorname {value} \ (f\ (f\ x))\\\vdots &\vdots &\vdots \\n&n\operatorname {inc} \ \operatorname {init} =\operatorname {value} \ (f^{n}\ x)=\operatorname {value} \ (n\ f\ x)&n\operatorname {inc} \ \operatorname {const} =\operatorname {value} \ (f^{n-1} \ x)=\o nom_utilisateur {valeur} \ ((n-1)\ f\ x)\\\end{tableau}}}$

La règle générale de récurrence est,

${\displaystyle \operatorname {inc} \ (\operatorname {value} \ v)=\operatorname {value} \ (f\ v)}$

S'il existe également une fonction pour récupérer la valeur du conteneur (appelée extract ),

${\displaystyle \operatorname {extrait} \ (\operatorname {value} \ v)=v}$

Ensuite, extract peut être utilisé pour définir la fonction samenum comme,

${\displaystyle \operatorname {samenum} =\lambda n.\lambda f.\lambda x.\operatorname {extract} \ (n\operatorname {inc} \operatorname {init} )=\lambda n.\lambda f.\ lambda x.\operatorname {extrait} \ (\operatorname {value} \ (n\ f\ x))=\lambda n.\lambda f.\lambda xn\ f\ x=\lambda nn}$

La fonction samenum n'est pas intrinsèquement utile. Cependant, comme inc délègue l'appel de f à son argument conteneur, nous pouvons faire en sorte que sur la première application, inc reçoive un conteneur spécial qui ignore son argument permettant de sauter la première application de f . Appelez ce nouveau conteneur initial const . Le côté droit du tableau ci-dessus montre les expansions de n inc const . Ensuite, en remplaçant init par const dans l'expression de la même fonction, nous obtenons la fonction prédécesseur,

${\displaystyle \operatorname {pred} =\lambda n.\lambda f.\lambda x.\operatorname {extract} \ (n\operatorname {inc} \operatorname {const} )=\lambda n.\lambda f.\ lambda x.\operatorname {extrait} \ (\operatorname {value} \ ((n-1)\ f\ x))=\lambda n.\lambda f.\lambda x.(n-1)\ f\ x =\lambda n.(n-1)}$

Comme expliqué ci-dessous, les fonctions inc , init , const , value et extract peuvent être définies comme,

${\displaystyle {\begin{aligned}\operatorname {value} &=\lambda v.(\lambda hh\ v)\\\operatorname {extract} k&=k\ \lambda uu\\\operatorname {inc} &= \lambda g.\lambda hh\ (g\ f)\\\operatorname {init} &=\lambda hh\ x\\\operatorname {const} &=\lambda ux\end{aligned}}}$

Ce qui donne l'expression lambda pour pred as,

${\displaystyle \operatorname {pred} =\lambda n.\lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu)}$

Une autre façon de définir pred

Pred peut également être défini à l'aide de paires :

${\displaystyle {\begin{aligned}\operatorname {f} =&\ \lambda p.\ \operatorname {pair} \ (\operatorname {second} \ p)\ (\operatorname {succ} \ (\operatorname {second } \ p))\\\operatorname {zero} =&\ (\lambda f.\lambda x.\ x)\\\operatorname {pc0} =&\ \operatorname {pair} \ \operatorname {zero} \ \ nomopérateur {zéro} \\\nomopérateur {pred} =&\ \lambda n.\ \nomopérateur {first} \ (n\ \nomopérateur {f} \ \nomopérateur {pc0} )\\\end{aligned}}}$

C'est une définition plus simple, mais conduit à une expression plus complexe pour pred. L'extension pour : ${\displaystyle \operatorname {pred} \operatorname {three} }$

${\displaystyle {\begin{aligned}\operatorname {pred} \operatorname {three} =&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {f} \ ( \operatorname {pair} \ \operatorname {zero} \ \operatorname {zero} ))))\\=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname { paire} \ \operatorname {zéro} \ \operatorname {un} )))\\=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {pair} \ \operatorname {un} \ \operatorname {deux} ))\\=&\ \operatorname {first} \ (\operatorname {pair} \ \operatorname {two} \ \operatorname {three} )\\=&\ \operatorname {two} \end{aligned} }}$

Division

La division des nombres naturels peut être mise en œuvre par,

${\displaystyle n/m=\operatorname {if} \ n\geq m\ \operatorname {then} \ 1+(nm)/m\ \operatorname {else} \ 0}$

Le calcul nécessite de nombreuses réductions bêta. A moins de faire la réduction à la main, cela n'a pas beaucoup d'importance, mais il est préférable de ne pas avoir à refaire ce calcul deux fois. Le prédicat le plus simple pour tester les nombres est IsZero, alors considérez la condition. ${\style d'affichage nm}$

${\displaystyle \operatorname {IsZero} \ (\operatorname {moins} \ n\ m)}$

Mais cette condition équivaut à , non . Si cette expression est utilisée, la définition mathématique de la division donnée ci-dessus est traduite en fonction sur les chiffres de l'Église comme, ${\style d'affichage n\leq m}$${\style d'affichage n<m}$

${\displaystyle \operatorname {divide1} \ n\ m\ f\ x=(\lambda d.\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (\operatorname {divide1} \ d\ m\ f\ x)))\ (\operatorname {moins} \ n\ m)}$

Comme souhaité, cette définition a un seul appel à . Cependant, le résultat est que cette formule donne la valeur de . ${\displaystyle \operatorname {moins} \ n\ m}$${\style d'affichage (n-1)/m}$

Ce problème peut être corrigé en ajoutant 1 à n avant d'appeler diviser . La définition de la division est alors,

${\displaystyle \operatorname {divide} \ n=\operatorname {divide1} \ (\operatorname {succ} \ n)}$

divise1 est une définition récursive. Le combinateur Y peut être utilisé pour implémenter la récursivité. Créez une nouvelle fonction appelée div by ;

• Dans le côté gauche ${\displaystyle \operatorname {divide1} \rightarrow \operatorname {div} \ c}$
• Dans le côté droit ${\displaystyle \operatorname {divide1} \rightarrow c}$

obtenir,

${\displaystyle \operatorname {div} =\lambda c.\lambda n.\lambda m.\lambda f.\lambda x.(\lambda d.\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (c\ d\ m\ f\ x)))\ (\operatorname {moins} \ n\ m)}$

Puis,

${\displaystyle \operatorname {divide} =\lambda n.\operatorname {divide1} \ (\operatorname {succ} \ n)}$

où,

${\displaystyle {\begin{aligned}\operatorname {divide1} &=Y\ \operatorname {div} \\\operatorname {succ} &=\lambda n.\lambda f.\lambda xf\ (n\ f\ x )\\Y&=\lambda f.(\lambda xf\ (x\ x))\ (\lambda xf\ (x\ x))\\0&=\lambda f.\lambda xx\\\operatorname {IsZero} &=\lambda nn\ (\lambda x.\operatorname {false} )\ \operatorname {true} \end{aligned}}}$

${\displaystyle {\begin{aligned}\operatorname {true} &\equiv \lambda a.\lambda ba\\\operatorname {false} &\equiv \lambda a.\lambda bb\end{aligned}}}$

${\displaystyle {\begin{aligned}\operatorname {moins} &=\lambda m.\lambda nn\operatorname {pred} m\\\operatorname {pred} &=\lambda n.\lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu)\end{aligned}}}$

Donne,

${\displaystyle \scriptstyle \operatorname {divide} =\lambda n.((\lambda f.(\lambda xx\ x)\ (\lambda xf\ (x\ x)))\ (\lambda c.\lambda n .\lambda m.\lambda f.\lambda x.(\lambda d.(\lambda nn\ (\lambda x.(\lambda a.\lambda bb))\ (\lambda a.\lambda ba))\ d\ ((\lambda f.\lambda xx)\ f\ x)\ (f\ (c\ d\ m\ f\ x)))\ ((\lambda m.\lambda nn(\lambda n.\ lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu))m)\ n\ m)))\ ((\lambda n .\lambda f.\lambda xf\ (n\ f\ x))\ n)}$

Ou sous forme de texte, en utilisant \ pour λ ,

divide = (\n.((\f.(\x.x x) (\x.f (x x))) (\c.\n.\m.\f.\x.(\d.(\n.n (\x.(\a.\b.b)) (\a.\b.a)) d ((\f.\x.x) f x) (f (c d m f x))) ((\m.\n.n (\n.\f.\x.n (\g.\h.h (g f)) (\u.x) (\u.u)) m) n m))) ((\n.\f.\x. f (n f x)) n))

Par exemple, 9/3 est représenté par

divide (\f.\x.f (f (f (f (f (f (f (f (f x))))))))) (\f.\x.f (f (f x)))

En utilisant une calculatrice de calcul lambda, l'expression ci-dessus se réduit à 3, en utilisant l'ordre normal.

\f.\x.f (f (f (x)))

Numéros signés

Une approche simple pour étendre les chiffres d'église aux nombres signés consiste à utiliser une paire d'églises, contenant des chiffres d'église représentant une valeur positive et une valeur négative. La valeur entière est la différence entre les deux chiffres de l'Église.

Un nombre naturel est converti en nombre signé par,

${\displaystyle \operatorname {convert} _{s}=\lambda x.\operatorname {pair} \ x\ 0}$

La négation est effectuée en échangeant les valeurs.

${\displaystyle \operatorname {neg} _{s}=\lambda x.\operatorname {pair} \ (\operatorname {second} \ x)\ (\operatorname {first} \ x)}$

La valeur entière est plus naturellement représentée si l'un des couples est nul. La fonction OneZero remplit cette condition,

${\displaystyle \operatorname {OneZero} =\lambda x.\operatorname {IsZero} \ (\operatorname {first} \ x)\ x\ (\operatorname {IsZero} \ (\operatorname {second} \ x)\ x\ (\operatorname {OneZero} \ \operatorname {pair} \ (\operatorname {pred} \ (\operatorname {first} \ x))\ (\operatorname {pred} \ (\operatorname {second} \ x)))) }$

La récursivité peut être implémentée à l'aide du combinateur Y,

${\displaystyle \operatorname {OneZ} =\lambda c.\lambda x.\operatorname {IsZero} \ (\operatorname {first} \ x)\ x\ (\operatorname {IsZero} \ (\operatorname {second} \ x )\ x\ (c\ \operatorname {pair} \ (\operatorname {pred} \ (\operatorname {first} \ x))\ (\operatorname {pred} \ (\operatorname {second} \ x)))) }$

${\displaystyle \operatorname {OneZero} =Y\operatorname {OneZ} }$

Plus et moins

L'addition est définie mathématiquement sur la paire par,

${\displaystyle x+y=[x_{p},x_{n}]+[y_{p},y_{n}]=x_{p}-x_{n}+y_{p}-y_{n} =(x_{p}+y_{p})-(x_{n}+y_{n})=[x_{p}+y_{p},x_{n}+y_{n}]}$

La dernière expression est traduite en lambda calcul comme,

${\displaystyle \operatorname {plus} _{s}=\lambda x.\lambda y.\operatorname {OneZero} \ (\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {first} \ x) \ (\operatorname {first} \ y))\ (\operatorname {plus} \ (\operatorname {second} \ x)\ (\operatorname {second} \ y)))}$

De même la soustraction est définie,

${\displaystyle xy=[x_{p},x_{n}]-[y_{p},y_{n}]=x_{p}-x_{n}-y_{p}+y_{n}=( x_{p}+y_{n})-(x_{n}+y_{p})=[x_{p}+y_{n},x_{n}+y_{p}]}$

donnant,

${\displaystyle \operatorname {moins} _{s}=\lambda x.\lambda y.\operatorname {OneZero} \ (\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {first} \ x) \ (\operatorname {second} \ y))\ (\operatorname {plus} \ (\operatorname {second} \ x)\ (\operatorname {first} \ y)))}$

Multiplier et diviser

La multiplication peut être définie par,

${\displaystyle x*y=[x_{p},x_{n}]*[y_{p},y_{n}]=(x_{p}-x_{n})*(y_{p}-y_ {n})=(x_{p}*y_{p}+x_{n}*y_{n})-(x_{p}*y_{n}+x_{n}*y_{p})=[ x_{p}*y_{p}+x_{n}*y_{n},x_{p}*y_{n}+x_{n}*y_{p}]}$

La dernière expression est traduite en lambda calcul comme,

${\displaystyle \operatorname {mult} _{s}=\lambda x.\lambda y.\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {mult} \ (\operatorname {first} \ x) \ (\operatorname {first} \ y))\ (\operatorname {mult} \ (\operatorname {second} \ x)\ (\operatorname {second} \ y)))\ (\operatorname {plus} \ (\ nomopérateur {mult} \ (\nomopérateur {premier} \ x)\ (\nomopérateur {second} \ y))\ (\nomopérateur {mult} \ (\nomopérateur {second} \ x)\ (\nomopérateur {premier} \ y)))}$

Une définition similaire est donnée ici pour la division, sauf que dans cette définition, une valeur dans chaque paire doit être zéro (voir OneZero ci-dessus). La fonction divZ nous permet d'ignorer la valeur qui a une composante nulle.

${\displaystyle \operatorname {divZ} =\lambda x.\lambda y.\operatorname {IsZero} \ y\ 0\ (\operatorname {divide} \ x\ y)}$

divZ est ensuite utilisé dans la formule suivante, qui est la même que pour la multiplication, mais avec mult remplacé par divZ .

${\displaystyle \operatorname {divide} _{s}=\lambda x.\lambda y.\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {divZ} \ (\operatorname {first} \ x) \ (\operatorname {first} \ y))\ (\operatorname {divZ} \ (\operatorname {second} \ x)\ (\operatorname {second} \ y)))\ (\operatorname {plus} \ (\ nomopérateur {divZ} \ (\nomopérateur {premier} \ x)\ (\nomopérateur {second} \ y))\ (\nomopérateur {divZ} \ (\nomopérateur {second} \ x)\ (\nomopérateur {premier} \ y)))}$

Nombres rationnels et réels

Les nombres réels rationnels et calculables peuvent également être codés dans le calcul lambda. Les nombres rationnels peuvent être codés comme une paire de nombres signés. Les nombres réels calculables peuvent être codés par un processus de limitation qui garantit que la différence par rapport à la valeur réelle diffère d'un nombre qui peut être rendu aussi petit que nécessaire. Les références données décrivent des logiciels qui pourraient, en théorie, être traduits en lambda calcul. Une fois les nombres réels définis, les nombres complexes sont naturellement encodés sous la forme d'une paire de nombres réels.

Les types de données et les fonctions décrits ci-dessus démontrent que tout type de données ou calcul peut être encodé dans le calcul lambda. C'est la thèse de Church-Turing .

Traduction avec d'autres représentations

La plupart des langages du monde réel prennent en charge les entiers natifs de la machine ; l' église et unchurch fonctions convertissent entre les nombres entiers non négatifs et leurs chiffres correspondants Eglise. Les fonctions sont données ici en Haskell , où le \correspond au du calcul Lambda. Les implémentations dans d'autres langages sont similaires.

type Church a = (a -> a) -> a -> a

church :: Integer -> Church Integer
church 0 = \f -> \x -> x
church n = \f -> \x -> f (church (n-1) f x)

unchurch :: Church Integer -> Integer
unchurch cn = cn (+ 1) 0

Église booléenne

Les booléens d'église sont l'encodage d'église des valeurs booléennes vrai et faux. Certains langages de programmation les utilisent comme modèle d'implémentation pour l'arithmétique booléenne ; les exemples sont Smalltalk et Pico .

La logique booléenne peut être considérée comme un choix. L'encodage Church du vrai et du faux est fonction de deux paramètres :

• true choisit le premier paramètre.
• false choisit le deuxième paramètre.

Les deux définitions sont connues sous le nom de booléens d'église :

${\displaystyle {\begin{aligned}\operatorname {true} &\equiv \lambda a.\lambda ba\\\operatorname {false} &\equiv \lambda a.\lambda bb\end{aligned}}}$

Cette définition permet aux prédicats (c'est-à-dire aux fonctions renvoyant des valeurs logiques ) d'agir directement comme des clauses if. Une fonction renvoyant un booléen, qui est ensuite appliqué à deux paramètres, renvoie soit le premier, soit le deuxième paramètre :

${\displaystyle \operatorname {predicate-} x\ \operatorname {then-clause} \ \operatorname {else-clause} }$

est évalué à la clause then si predicate-x est évalué à true , et à else-clause si predicate-x est évalué à false .

Parce que vrai et faux choisissent le premier ou le deuxième paramètre, ils peuvent être combinés pour fournir des opérateurs logiques. Notez qu'il existe plusieurs implémentations possibles de not .

${\displaystyle {\begin{aligned}\operatorname {and} &=\lambda p.\lambda qp\ q\ p\\\operatorname {ou} &=\lambda p.\lambda qp\ p\ q\\\ nom_opérateur {pas} _{1}&=\lambda p.\lambda a.\lambda bp\ b\ a\\\nom_opérateur {pas} _{2}&=\lambda pp\ (\lambda a.\lambda bb )\ (\lambda a.\lambda ba)=\lambda pp\operatorname {false} \operatorname {true} \\\operatorname {xor} &=\lambda a.\lambda ba\ (\operatorname {not} \ b )\ b\\\operatorname {if} &=\lambda p.\lambda a.\lambda bp\ a\ b\end{aligned}}}$

Quelques exemples:

${\displaystyle {\begin{aligned}\operatorname {and} \operatorname {true} \operatorname {false} &=(\lambda p.\lambda qp\ q\ p)\ \operatorname {true} \ \operatorname {false } =\operatorname {true} \operatorname {false} \operatorname {true} =(\lambda a.\lambda ba)\operatorname {false} \operatorname {true} =\operatorname {false} \\\operatorname {ou} \operatorname {true} \operatorname {false} &=(\lambda p.\lambda qp\ p\ q)\ (\lambda a.\lambda ba)\ (\lambda a.\lambda bb)=(\lambda a .\lambda ba)\ (\lambda a.\lambda ba)\ (\lambda a.\lambda bb)=(\lambda a.\lambda ba)=\operatorname {true} \\\operatorname {not} _{ 1}\ \operatorname {true} &=(\lambda p.\lambda a.\lambda bp\ b\ a)(\lambda a.\lambda ba)=\lambda a.\lambda b.(\lambda a. \lambda ba)\ b\ a=\lambda a.\lambda b.(\lambda cb)\ a=\lambda a.\lambda bb=\operatorname {false} \\\operatorname {not} _{2}\ \operatorname {true} &=(\lambda pp\ (\lambda a.\lambda bb)(\lambda a.\lambda ba))(\lambda a.\lambda ba)=(\lambda a.\lambda ba) (\lambda a.\lambda bb)( \lambda a.\lambda ba)=(\lambda b.(\lambda a.\lambda bb))\ (\lambda a.\lambda ba)=\lambda a.\lambda bb=\operatorname {false} \end {aligné}}}$

Prédicats

Un prédicat est une fonction qui renvoie une valeur booléenne. Le prédicat le plus fondamental est , qui renvoie si son argument est le chiffre de l'Église , et si son argument est un autre chiffre de l'Église : ${\displaystyle \operatorname {IsZero} }$${\displaystyle \operatorname {true} }$${\style d'affichage 0}$${\displaystyle \operatorname {false} }$

${\displaystyle \operatorname {IsZero} =\lambda nn\ (\lambda x.\operatorname {false} )\ \operatorname {true} }$

Le prédicat suivant teste si le premier argument est inférieur ou égal au second :

${\displaystyle \operatorname {LEQ} =\lambda m.\lambda n.\operatorname {IsZero} \ (\operatorname {moins} \ m\ n)}$,

En raison de l'identité,

${\displaystyle x=y\equiv (x\leq y\land y\leq x)}$

Le test d'égalité peut être mis en œuvre comme,

${\displaystyle \operatorname {EQ} =\lambda m.\lambda n.\operatorname {and} \ (\operatorname {LEQ} \ m\ n)\ (\operatorname {LEQ} \ n\ m)}$

Paires d'églises

Les paires d'églises sont le codage d'églises du type paire (deux tuples). La paire est représentée comme une fonction qui prend un argument de fonction. Lorsqu'on lui donne son argument, il appliquera l'argument aux deux composants de la paire. La définition en lambda calcul est,

${\displaystyle {\begin{aligned}\operatorname {pair} &\equiv \lambda x.\lambda y.\lambda zz\ x\ y\\\operatorname {first} &\equiv \lambda pp\ (\lambda x .\lambda yx)\\\operatorname {second} &\equiv \lambda pp\ (\lambda x.\lambda yy)\end{aligned}}}$

Par exemple,

${\displaystyle {\begin{aligned}&\operatorname {first} \ (\operatorname {pair} \ a\ b)\\=&(\lambda pp\ (\lambda x.\lambda yx))\ ((\ lambda x.\lambda y.\lambda zz\ x\ y)\ a\ b)\\=&(\lambda pp\ (\lambda x.\lambda yx))\ (\lambda zz\ a\ b)\ \=&(\lambda zz\ a\ b)\ (\lambda x.\lambda yx)\\=&(\lambda x.\lambda yx)\ a\ b=a\end{aligned}}}$

Lister les encodages

Une liste ( immuable ) est construite à partir de nœuds de liste. Les opérations de base sur la liste sont ;

Nous donnons ci-dessous quatre représentations différentes des listes :

• Construisez chaque nœud de liste à partir de deux paires (pour permettre des listes vides).
• Construisez chaque nœud de liste à partir d'une paire.
• Représentez la liste en utilisant la fonction de pli à droite .
• Représenter la liste en utilisant l'encodage de Scott qui prend les cas d'expression de correspondance comme arguments

Deux paires en tant que nœud de liste

Une liste non vide peut être implémentée par une paire d'Églises ;

• Contient d' abord la tête.
• Le deuxième contient la queue.

Cependant cela ne donne pas une représentation de la liste vide, car il n'y a pas de pointeur "null". Pour représenter null, la paire peut être enveloppée dans une autre paire, donnant des valeurs libres,

• First - Est le pointeur nul (liste vide).
• Second.First contient la tête.
• Second.Second contient la queue.

En utilisant cette idée, les opérations de base sur les listes peuvent être définies comme ceci :

Expression	La description
${\displaystyle \operatorname {nil} \equiv \operatorname {pair} \ \operatorname {true} \ \operatorname {true} }$	Le premier élément de la paire est vrai, ce qui signifie que la liste est nulle.
${\displaystyle \operatorname {isnil} \equiv \operatorname {first} }$	Récupérer l'indicateur nul (ou liste vide).
${\displaystyle \operatorname {cons} \equiv \lambda h.\lambda t.\operatorname {pair} \operatorname {false} \ (\operatorname {pair} h\ t)}$	Créez un nœud de liste, qui n'est pas nul, et donnez-lui une tête h et une queue t .
${\displaystyle \operatorname {head} \equiv \lambda z.\operatorname {first} \ (\operatorname {second} z)}$	deuxième.premier est la tête.
${\displaystyle \operatorname {tail} \equiv \lambda z.\operatorname {second} \ (\operatorname {second} z)}$	seconde.seconde est la queue.

Dans un nœud nil, on n'accède jamais à la seconde , à condition que la tête et la queue ne soient appliquées qu'aux listes non vides.

Une paire en tant que nœud de liste

Sinon, définissez

${\displaystyle {\begin{aligned}\operatorname {cons} &\equiv \operatorname {pair} \\\operatorname {head} &\equiv \operatorname {first} \\\operatorname {tail} &\equiv \operatorname { second} \\\operatorname {nil} &\equiv \operatorname {false} \\\operatorname {isnil} &\equiv \lambda ll(\lambda h.\lambda t.\lambda d.\operatorname {false} )\ nom_opérateur {vrai} \end{aligné}}}$

où la dernière définition est un cas particulier du général

${\displaystyle \operatorname {process-list} \equiv \lambda ll(\lambda h.\lambda t.\lambda d.\operatorname {head-and-tail-clause} )\operatorname {nil-clause} }$

Représenter la liste en utilisant le pli droit

Comme alternative à l'encodage à l'aide de paires Church, une liste peut être encodée en l'identifiant avec sa fonction de pli à droite . Par exemple, une liste de trois éléments x, y et z peut être codée par une fonction d'ordre supérieur qui, lorsqu'elle est appliquée à un combinateur c et une valeur n renvoie cx (cy (czn)).

${\displaystyle {\begin{aligned}\operatorname {nil} &\equiv \lambda c.\lambda nn\\\operatorname {isnil} &\equiv \lambda ll\ (\lambda h.\lambda t.\operatorname { false} )\ \operatorname {true} \\\operatorname {cons} &\equiv \lambda h.\lambda t.\lambda c.\lambda nc\ h\ (t\ c\ n)\\\operatorname {head } &\equiv \lambda ll\ (\lambda h.\lambda th)\ \operatorname {false} \\\operatorname {tail} &\equiv \lambda l.\lambda c.\lambda nl\ (\lambda h. \lambda t.\lambda gg\ h\ (t\ c))\ (\lambda tn)\ (\lambda h.\lambda tt)\end{aligned}}}$

Cette représentation de liste peut être donnée de type dans System F .

Représenter la liste en utilisant l'encodage Scott

Une représentation alternative est l'encodage Scott, qui utilise l'idée de continuations et peut conduire à un code plus simple. (voir aussi codage Mogensen-Scott ).

Dans cette approche, nous utilisons le fait que les listes peuvent être observées en utilisant une expression de filtrage de motifs. Par exemple, en utilisant la notation Scala , si listdésigne une valeur de type Listavec une liste vide Nilet un constructeur, Cons(h, t)nous pouvons inspecter la liste et calculer nilCodeau cas où la liste est vide et consCode(h, t)lorsque la liste n'est pas vide :

list match {
  case Nil        => nilCode
  case Cons(h, t) => consCode(h,t)
}

La 'liste' est donnée par la façon dont elle agit sur 'nilCode' et 'consCode'. Nous définissons donc une liste comme une fonction qui accepte de tels 'nilCode' et 'consCode' comme arguments, de sorte qu'au lieu de la correspondance de motif ci-dessus, nous pouvons simplement écrire :

${\displaystyle \operatorname {list} \ \operatorname {nilCode} \ (\operatorname {consCode} \ h\ t)}$

Notons par 'n' le paramètre correspondant à 'nilCode' et par 'c' le paramètre correspondant à 'consCode'. La liste vide est celle qui renvoie l'argument nil :

${\displaystyle \operatorname {nil} \equiv \lambda n.\lambda c.\ n}$

La liste non vide avec en-tête 'h' et queue 't' est donnée par

${\displaystyle \operatorname {cons} \ h\ t\ \ \equiv \ \ \lambda n.\lambda c.\ c\ h\ t}$

Plus généralement, un type de données algébrique avec des alternatives devient une fonction avec des paramètres. Lorsque le e constructeur a des arguments, le paramètre correspondant de l'encodage prend également des arguments. ${\style d'affichage m}$${\style d'affichage m}$${\style d'affichage i}$${\style d'affichage n_{i}}$${\style d'affichage n_{i}}$

L'encodage de Scott peut être effectué dans un lambda calcul non typé, alors que son utilisation avec des types nécessite un système de types avec récursivité et polymorphisme de type. Une liste avec le type d'élément E dans cette représentation qui est utilisée pour calculer des valeurs de type C aurait la définition de type récursive suivante, où '=>' désigne le type de fonction :

type List = 
  C =>                    // nil argument
  (E => List => C) =>     // cons argument
  C                       // result of pattern matching

Une liste qui peut être utilisée pour calculer des types arbitraires aurait un type qui quantifie sur C. Une liste générique dans Eprendrait également Ecomme argument de type.

Voir également

• Calcul lambda
• Système F pour les chiffres de l'Église dans un calcul dactylographié
• Encodage Mogensen-Scott
• Définition de Von Neumann des ordinaux - une autre façon de coder les nombres naturels : en tant qu'ensembles

Remarques

Les références

• Méta-programmation directement rééchissante
• Chiffres d'église et booléens expliqués par Robert Cartwright à l'Université Rice
• Fondements théoriques pour une « programmation totalement fonctionnelle » pratique (chapitres 2 et 5) Tout sur l'Église et d'autres encodages similaires, y compris comment les dériver et les opérations sur eux, à partir des premiers principes
• Quelques exemples interactifs de chiffres de l'Église
• Tutoriel Lambda Calculus Live : Algèbre booléenne