¿Puede alguien explicar el Y Combinator?

Question

El combinador Y es un concepto de la programación funcional, tomado del cálculo lambda. Es un combinador de punto fijo. Un combinador de punto fijo $G$ es una función de orden superior (un funcional, en lenguaje matemático) que, dada una función $f$ devuelve un punto fijo de $f$ . En lenguaje matemático,

$$f(G(f)) = G(f)$$

Esto puede considerarse la ecuación definitoria de un combinador de punto fijo.

Tenga en cuenta que $f$ puede ser una función cuyo rango y dominio son a su vez espacios de funciones -- de hecho este es el uso más común de un combinador de punto fijo: se puede definir una función $\alpha$ especificando que es el punto fijo de otra función $f$ y, a continuación, calcular $\alpha$ como $G(f)$ .

Como matemáticos estamos acostumbrados a que las funciones tengan nombres, por ejemplo $f:x\mapsto x^2$ es la función llamada $f$ que mapea $x$ a $x^2$ . Pero no hay ninguna razón por la que no se pueda tener una función anónima. Como el cálculo lambda trata mucho con ellas, hay una notación especial para ellas:

$$\lambda x.x^2$$

es la función que toma $x$ a $x^2$ para que, por ejemplo $(\lambda x.x^2)(2) = 4$ . Cuando no hay ambigüedad, podemos escribir la aplicación de la función por concatenación: $(\lambda x.x^2) 2 = 4$ y si definimos $f = \lambda x.x^2$ entonces $f\; 2 = 4$ .

Bien, ahora llegamos al meollo de la cuestión. El combinador Y es una función de orden superior (funcional) definida como

$$Y = \lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))$$

Puedo seguir a través del álgebra y ver que esto es efectivamente un combinador de punto fijo:

$$\begin{align} Y\; g & = (\lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))) \; g \\ & = (\lambda x. g (x\;x)) \; (\lambda x. g (x\;x)) \\ & = (\lambda y. g (y\;y)) \; (\lambda x. g (x\;x)) \\ & = g \; (\lambda x. g (x\;x)) (\lambda x. g (x\;x)) \\ & = g\; (Y\; g) \end{align}$$

pero no tengo ninguna intuición en cuanto a por qué funciona, o cómo se le podría haber ocurrido a alguien. Más aún, no veo cómo se puede utilizar en la práctica para calcular funciones como puntos fijos de funcionales.

¿Alguien tiene una buena explicación "intuitiva"?

Answer 1

El $Y$ es una función que toma una función $f$ y devuelve algo aplicado a sí mismo (concretamente $\lambda x.f(xx)$ ). Así que si queremos hacer $Y(f)$ un punto fijo de $f$ , $Y(f)$ tiene que ser igual a $f(Y(f))$ . Por lo tanto, queremos que algunos $a$ tal que $aa = f(aa)$ . Ahora, $a$ tiene acceso a sí mismo (se aplica a sí mismo). Por ello, podemos crear directamente un $a$ . $$aa=f(aa)$$ $$a=\lambda a.f(aa)$$ $$a=\lambda x.f(xx)$$ $$Y=\lambda f.aa=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$ Esencialmente, al aplicar $a$ a sí mismo, está dando $a$ una referencia a sí mismo, lo que le permite utilizarlo de forma recursiva. Sin embargo, $a$ es sólo un valor intermedio - no es la función recursiva en sí misma, ya que todavía necesita una referencia a sí misma para hacer la recursión. La página web $Y$ elimina completamente esta necesidad al encontrar el punto fijo, dando a una función su forma final y recursiva.

Answer 2

Si conoces el argumento diagonal de Cantor, puedes descubrir el combinador Y.

Teorema de Cantor Dejemos que $A,B$ sean conjuntos y supongamos que existe una función sin punto fijo $f \colon B \to B$ . Entonces, no hay suryección $A \to (A \to B)$ .

Observación. Normalmente, $B$ es un $2$ -de elementos, de modo que $A \to B = \mathcal{P}(A)$ y $f$ es la función que invierte los dos valores.

Prueba. Dejemos que $g \colon A \to (A \to B)$ sea una función. Encontraremos alguna función $h \colon A \to B$ tal que $h$ no es a imagen y semejanza de $g$ .

Utilizamos el argumento diagonal : definir $h$ que será dada por $$h(a) = f(g(a)(a))\,.$$ Entonces, si $a'$ es cualquier elemento de $A$ tenemos que $$h(a') = f(g(a')(a')) \ne g(a')(a')\,,$$ (ya que $f$ es libre de puntos fijos), y por lo tanto que $h\ne g(a')$ . Por lo tanto, ya que $a'$ era arbitraria, $h$ debe estar fuera de la imagen de $g$ . $\Box$

Ahora bien, no se dice así a menudo, pero el argumento diagonal de Cantor se aplica en realidad a toda clase de teorías de tipos distintas de la de conjuntos y funciones, incluso a la no tipificada $\lambda$ -Cálculo. Sin embargo, las consecuencias son muy diferentes.

Escribe $\Lambda$ para la recopilación de todos los $\lambda$ -términos. (Técnicamente, estamos empleando el truco de pensar en los $\lambda$ -cálculo como un tipo $\lambda$ -cálculo con un solo tipo $\Lambda$ satisfaciendo $\Lambda \to \Lambda = \Lambda$ .)

Queremos tomar $A=B=\Lambda$ en nuestro argumento anterior. Pero, ¿qué debería hacer una función de $\lambda$ -términos a $\lambda$ -términos ser? Pues no es más que un $\lambda$ -¡Término mismo! Por lo tanto, hay absolutamente es una sobreproyección $$\Lambda \to (\Lambda \to \Lambda)\,.$$ Es la función de identidad.

¿No contradice esto el argumento de Cantor? La respuesta es no - ya que la conclusión del argumento es falsa, entonces una de las hipótesis debe ser falsa. Y en este caso, la única hipótesis que puede fallar es la existencia de una función sin punto fijo $\Lambda \to \Lambda$ .

Así es - no hay ningún punto fijo libre $\lambda$ -Término. Pero como el argumento anterior es completamente constructivo, podemos hacerlo aún mejor: podemos construir ese punto fijo nosotros mismos llevando a cabo el argumento a la inversa.

Primero hagamos esto en general, y luego veremos cómo funcionan las cosas en el modo no tipado $\lambda$ -Cálculo. Todo en el siguiente argumento surge como resultado directo de escribir los pasos de la prueba anterior a la inversa.

Contrapositivo al teorema de Cantor Dejemos que $g \colon A \to (A \to B)$ sea una suryección. Entonces no hay ninguna función libre de puntos fijos $f \colon B \to B$ .

Prueba. Considere la función $h \colon A \to B$ dado por $$h(a) = f(g(a)(a))\,.$$ Desde $g$ es suryente, hay algún $a'$ tal que $g(a')=h$ . Entonces tenemos $$g(a')(a') = h(a') = f(g(a')(a'))\,,$$ y por lo tanto $g(a')(a')$ es un punto fijo de la función $f$ . $\Box$

¿Cómo funciona esto en el caso de la versión no tipificada de $\lambda$ -¿Cálculo? Pues bien, esta vez nuestra proyección $g$ es la función de identidad, por lo que $h$ se convierte en $$h = \lambda x.f(x\,x)\,.$$ Desde $g$ es la función de identidad, podemos elegir $a' = h$ . Entonces nuestra expresión final para el punto fijo es $$h\,h = (\lambda x.f(x\,x))(\lambda x.f(x\,x))\,.$$ Y, en efecto, tenemos $$(\lambda x.f(x\,x))(\lambda x.f(x\,x)) = f((\lambda x.f(x\,x))(\lambda x.f(x\,x)))\,.$$ ¡Hay más! Podemos $\lambda$ -abstraer el $f$ para darnos un propósito general combinador de puntos fijos . $$\lambda f.(\lambda x.f(x\,x))(\lambda x.f(x\,x))$$ Hola, viejo amigo.

Answer 3

El $Y$ combinador puede definirse también de forma Turing. Utilicemos nombres de variables menos formales pero más descriptivos para definir el combinador: $$\begin{align} A &= \lambda \text{self}.\lambda f.f\ (\text{self}\ \text{self}\ f);\\ Y &= A\ A. \end{align}$$

El $A$ se puede considerar como una función que se toma a sí misma como primer argumento y la función objetivo, cuyo punto fijo se quiere encontrar, como segundo. Devuelve la función aplicada a $A\ A\ f$ tal y como queríamos.

Entonces, un combinador arbitrario F que se define en términos de sí mismo como $$F\ x\ y = F\ y\ x\ F$$ puede definirse en términos de $Y$ y algún otro combinador $F_r$ . Específicamente, $$F\ x\ y = F\ y\ x\ F$$ equivale a $$F = \lambda x.\lambda y.F\ y\ x\ F,$$ que a su vez se deduce de $$F = (\lambda \text{self}.\lambda x.\lambda y.\text{self}\ y\ x\ \text{self}) F.$$ Por último, llamemos a la subexpresión resultante $$F_r = \lambda \text{self}.\lambda x.\lambda y.\text{self}\ y\ x\ \text{self}.$$ Entonces $F = Y\ F_r$ .