Séquençage ou continuation-passage dans pure lambda-calcul

Question

J'essaie de résoudre les exercices suivants donnés à ici .

Considérez la représentation numéro suivante. Comment définir l'addition?

|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

Les opérateurs successeurs et prédécesseurs sont faciles à définir:

Succ n = λx.n
Pred n = n (λx.x)

Une solution "évidente" pour définir l'addition consiste à utiliser l'opération successeur plus le test de zéro avec la combinaison de points fixe, quelque chose comme (yf) pour f donné ci-dessous (l'opérateur si et booléens sont définis comme d'habitude):

F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

mais définissant is0 semble non trivial. Le problème est qu'un chiffre | n | consomme n + 1 arguments, et n arguments sont simplement effacés par celui-ci. Par conséquent, si j'applique une telle fonction, il semble raisonnable d'arrêter sa demande lorsqu'il devient clair que le chiffre, par exemple. n'est pas une identité. Je suppose que c'est une sorte de continuation, mais je ne peux pas imaginer comment le modeler dans le pure Lambda-Calculus. Peut-être que quelqu'un connaît des conseils qui peuvent aider?

Un opérateur de séquençage peut également aider à définir l'addition. Si une application d'un chiffre | M | est retardée jusqu'à ce qu'un chiffre | n | est appliqué à tous les arguments tous les arguments, le résultat sera exactement Un chiffre | n + m | . Il existe peut-être une variante d'un tel combinateur de séquençage dans le pure lambda-calcul?

La réponse fournie par l'auteur de l'exercice utilise une opération non pure (à savoir isprocédée qui vérifie si son argument est une fonction).

upd upd: Il n'est pas difficile de faire un CPS en Lambda-Calculus (Détails pour CBV peut être trouvé ICI ). Semble que cela ne suffit pas pour résoudre le problème.

upd : si nous avons une version de fonctions de citation-eval pour le pure lambda-calcul, alors il doit y avoir une fonction $ EQ $ , qui reconnaît si les expressions Lambda citées sont syntaxiquement égales, et nous pouvons construire is0 en utilisant $ EQ $ . Mais je doute que $ eq $ est définible. La raison est "Lemma générique" (livre Barendregt, Lemme 14.3.24). Si nous étions en mesure de tester l'égalité sur les termes de la Lambda cités ( $ EQ $ ( ciote $ \ Omega $ ) ( ciote $ \ lambda xx $ )) retournerait $ False $ , et la généricité implique que ( $ eq $ ( devis $ \ lambda xx $ ) ( ciote $ \ lambda xx $ )) retournerait $ false $ . Cela contredit-il une possibilité de construire ciote dans le pure lambda-calcul?

Answer 1

Je ne pense pas que vous trouverez ce que vous recherchez dans le calcul de la Pure Lambda. La clé est cette déclaration que vous avez faite:

Un opérateur de séquençage peut également aider à définir l'addition. Si une application d'un chiffre | m | est retardé jusqu'à un chiffre | n | est appliqué à tous ses arguments, ...

Eh bien, les modèles du calcul de la Lambda sont censés être comme:

$$ u \ cong u ^ u $$

et le point de ce est que chaque valeur sémantique $ u \ in u $ peut être appliquée à quelque chose. Cela n'a donc aucun sens de parler de quelque chose d'être "appliqué à tous ses arguments". Il n'y a pas de valeur qui ne peut pas être appliquée à plus d'arguments dans le calcul de la Lambda pure.

Je ne sais pas la main d'un modèle / argument selon lequel cette représentation de Naturals rend impossible la mise en œuvre de IsZero, bien que certaines pensent à ce sujet ne semble pas improbable. Cependant, si cela doit être possible dans le calcul de la Lambda pure, il devra avoir de sens sémantiquement et ne sera pas basé sur des notions qui ne sont que syntaxiques.

Edit: Voici un esquisse d'un argument. Une définition de $ \ mathsf {iszero} $ doit éventuellement réduire comme:

$$ \ mathsf {iszero} \n\ rightquiGarrow ^ * n \ wrowighightarrow v $$

La raison est que s'appliquer à un certain nombre de valeurs est le seul mécanisme dans le calcul de la Lambda pour distinguer en réalité les chiffres. Il doit être le cas que: $$ 0 \ wrowighighterarrow v=mathsf {true} \\ \ mathsf {s} n \ wrowighighterarrow v=mathsf {faux} $$ Cependant, pour chaque $ \ WEWERIERARROWT v + k | \ wrowighightarrow v= | k | $$ (où $ | \ wrowighterarrow v | $ est la longueur de $ \ wrowighighterarrow v $ ). Mais seulement $ | 1 |=mathsf {faux} $ (si c'est la convention choisie). En anglais, il n'existe aucun lien avec le nombre de termes requis pour obtenir un booléen en appliquant un chiffre. Donc, il ne peut y avoir de $ \ wrowighightarrow v $ qui satisfait aux équations pour tous les chiffres et donc $ \ mathsf {iszero} $ ne peut pas être défini.

Answer 2

Le moyen le plus simple de définir l'addition dans la Lambda-Calculus est de traiter les chiffres comme s'il s'agissait d'une liste liée et de caténate les listes.Pour ce faire, il est nécessaire d'utiliser des variables supplémentaires pour remplacer les variables extérieures de chaque numéro. L'expression résultante du second numéro peut donc être substituée à la variable interne de l'expression résultante pour le premier nombre.Cela donne l'expression suivante pour addition:

  λw.λx.λy.λz.w y (x y z)