Comment fonctionne la multiplication lambda?

Question

A Tutorial Introduction to the Lambda Calculus

Cet article présente la fonction de multiplication

La multiplication de deux nombres x et y peut être calculée en utilisant la fonction suivante:

(λxyz.x (yz))

Le produit de 2 par 2 est alors:

(λxyz.x (yz)) 22

qui réduit à

(λz.2 (2z))

Le lecteur peut vérifier que par furt la réduction de cette expression, nous pouvons obtenir le résultat escompté 4.

Je ne sais pas comment (λz.2 (2z)) réduire à 4. Quelqu'un peut-il me montrer le processus? La fonction 2 dans lambda est λsz.s (s (z)), et le 4 est λsz.s (s (s (s)))).

Answer 1

Vous pouvez obtenir formellement le résultat en appliquant la substitution, comme dans les exemples précédents de la note que vous avez citée.

depuis:

2 ≡ λsz.s(s(z)) 

nous avons substituons la deuxième instance de celui-ci dans (λz.2(2z)) (en changeant les noms de variables pour éviter la capture des variables libres):

(λz.2((λxy.x(x(y)))z)) 

qui devient égal à (en remplaçant x avec z):

(λz.2(λy.z(z(y)))) 

alors nous appliquons à nouveau la définition de 2 (avec un nouveau changement de nom des variables):

(λz.((λwu.w(w(u)))(λy.z(z(y)))))) 

qui devient égal à (en remplaçant w avec λy.z(z(y))):

(λz.(λu.(((λy.z(z(y)))((λy.z(z(y)))u))))) 

maintenant nous pouvons répéter la substitution dans le rigthmost lambda, en substituant y avec u:

(λz.(λu.((λy.z(z(y)))(z(z(u)))))) 

et enfin nous pouvons un pply la dernière substitution, remplaçant y avec z(z(u):

(λz.(λu.z(z(z(z(u)))))) 

qui est 4.

Comme dernière remarque, notez que l'on pouvait convaincre par la justesse de la définition en considérant qu'un certain nombre n est une fonction avec deux arguments qui applique le premier argument n fois au second. Donc, (λz.2(2z)), est la fonction qui applique deux fois la fonction 2z, qui est la fonction qui s'applique deux fois z, de sorte que le résultat est la fonction qui applique quatre fois z à son argument.