Une évaluation du calcul lambda impliquant des chiffres de l'Église

Je comprends qu'un chiffre d'église ressemble à (... n fois ...) . Cela ne signifie rien de plus que "la fonction appliquée fois à la fonction ". $c_n$ $\lambda s. \lambda z. s$ $s\;z$ $s$ $n$ $z$

Une définition possible de la fonction est la suivante: . En regardant le corps, je comprends la logique derrière la fonction. Cependant, lorsque je commence à évaluer, je suis bloqué. Je vais l'illustrer avec un exemple: $\mathtt{times}$ $\mathtt{times} = \lambda m. \lambda n. \lambda s. m \; (n\; s)$

\begin{aligned} (λ m . λ n . λ s . m (n s)) (λ s . λ z . s s z) (λ s . λ z . s s s z) \\ \to^{*} & λ s . (λ s . λ z . s s z) ((λ s . λ z . s s s z) s)) \\ \to^{*} & λ s . (λ s . λ z . s s z) (λ z . s s s z) \\ \to^{*} & λ s . λ z . (λ z . s s s z) (λ z . s s s z) z \end{aligned}

$\begin{align*} (\lambda m. \lambda n. \lambda s. m \; (n\; s))(\lambda s.\lambda z.s\;s\;z)(\lambda s.\lambda z.s\;s\;s\;z) \mspace{-4em} \\ \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; ((\lambda s.\lambda z.s\;s\;s\;z)\; s)) \\ \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; (\lambda z.s\;s\;s\;z) \\ \to^*& \lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z \end{align*}$

Maintenant, dans cette situation, si j'applique d'abord , j'arrive au résultat souhaité. Cependant, si j'applique abord, comme je le dois parce que l'application est associative de gauche, j'obtiens un mauvais résultat: $(\lambda z.s\;s\;s\;z)\;z$ $(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)$

$\lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z \to \lambda s. \lambda z.(s\;s\;s\;(\lambda z.s\;s\;s\;z))\;\;z$

Je ne peux plus réduire cela. Qu'est-ce que je fais mal? Le résultat devrait être $\lambda s. \lambda z.s\;s\;s\;s\;s\;s\;z$

lambda-calculus church-numerals codd
la source

Les chiffres de l'Église dans votre premier mandat ne sont pas corrects. 2 est représenté par , pas .

λ s . λ z . s (s z)

$\lambda s. \lambda z. s (s z)$

λ s . λ z . s s z

$\lambda s. \lambda z. s s z$

Uday Reddy

Réponses:

Je pense que votre réduction est correcte (je ne l'ai cependant fait qu'observer). À la fin, vous ne pouvez pas appliquer à , cela n'apparaît jamais dans le terme. est , pas . Les fonctions du lambda-calcul prennent un seul argument; ils sont effectivement curry : une fonction à deux arguments est implémentée comme une fonction à un argument qui prend le premier argument et renvoie une nouvelle fonction à un argument qui prend le deuxième argument et renvoie le résultat. $(\lambda z. s s s z)$ $z$ $\lambda z. f f z$ $\lambda z. (f f) z$ $\lambda z. f (f z)$

Vous avez fait la même erreur lors de la définition des chiffres de l'Église. Le chiffre de l'Église pour est basé sur la composition d'une fonction fois. «La fonction appliquée fois à la fonction » . Ce que vous avez écrit est la fonction appliquée fois à la fonction et enfin à , ce qui ne me semble pas être un terme utile. $n$ $n$ $s$ $n$ $z$ $\lambda s. \lambda z. s (s ( … s \: z) … ))$ $s$ $n-1$ $s$ $z$

$2 \times 3$ est donc . Je vous laisse vérifier qu'il se réduit à . $(\lambda m n s. m (n s)) (\lambda s z. s (s \: z)) (\lambda s z. s (s (s \: z)))$ $\lambda s z. s (s (s (s (s (s \: z)))))$

Gilles 'SO- arrête d'être méchant'
la source

En ce qui concerne votre paragraphe, vous avez raison et j'en étais conscient. Cela m'a juste frappé que l'application correctement associative a donné le bon résultat. En ce qui concerne le deuxième paragraphe: vous avez raison. L'absence d'accolades était une erreur de ma part, encore une fois en raison de l'associativité gauche de l'application. Je vais à nouveau réduire le tout maintenant et voir si mon manque de bretelles a causé mon erreur!

codd

Ça faisait. Vous notant que ma notation impliquait un mauvais ordre d'application a résolu le problème! Accepter votre réponse.

codé le