Comment fonctionne le combinateur "(L L L ...)" Y de Jan Willem Klop?

Question

Je comprends what a Y Combinator is, mais je ne comprends pas cet exemple d'un combinateur « roman », du Wikipedia page:

 Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L) 

Where: 

    L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

Comment ça marche?

Answer 1

L'essence d'un combinateur à virgule fixe C est que C f se réduit à f (C f). Peu importe ce que vous prenez pour C aussi longtemps que cela. Ainsi, au lieu de

(\y f. f (y y f)) (\y f. f (y y f)) 

vous pouvez tout aussi bien prendre

(\y z f. f (y y y f)) (\y z f. f (y y y f)) (\y z f. f (y y y f)) 

Fondamentalement, vous besoin de quelque chose de la forme

C t1 t2 ... tN 

où ti = C pour certains i et

C = \x1 x2 .. xN f. f (xi u1 u2 ... xi ... u(N-1) f) 

Les autres termes tj et uj ne sont pas réellement "utilisés". Vous pouvez voir que L de Klop a cette forme (bien qu'il utilise le fait que tous ti sont L tels que le deuxième xi peut également être n'importe quel autre xj).