El combinador Y en C++ (I)

Una de las maravillas de la programación es que todo puede ser obtenido a partir de una sencilla regla (la beta-reducción) que se basa en la sustitución. Lo difícil es expresar todo lo que una máquina real hace (que de sustitución entiende más bien poco) en forma de sustituciones.

Una de las cosas que fue difícil de transformar en sustituciones fue la recursividad. El logro ocurrió cuando se descubrieron los combinadores de punto fijo. De estos combinadores el más sencillo es el combinador Y.

Una función recursiva es una que usa de sí misma para dar el resultado de una operación. La forma natural expresarlo es: f(x) = g(f, x). Para calcular f tenemos que hacer algún cálculo con x pero también con f.

El ejemplo paradigmático de la recursividad es la función factorial. Esta función se define recursivamente así:

f(x) =  x==0 ? 1 : x*f(x-1)

He usado el operador trinario ?: de C/C++ aunque estamos hablando en lenguaje matemático aún. Como se observa, la definición de f requiere del uso de f en la parte de la derecha. Puedo desplegar ese uso en la derecha para ver qué se obtiene.

Como f(x-1) =  x-1==0 ? 1 : (x-1)*f(x-2) llegaría a:

f(x) =  x==0 ? 1 : x*(   x-1==0 ? 1 : (x-1)*f(x-2)   )

Y de nuevo, con f(x-2) llego a:

f(x) =  x==0 ? 1 : x*(    x-1==0 ? 1 : (x-1)*(    x-2==0 ? 1 : (x-2)*f(x-3)    )     )

Repitiendo indefinidamente se continuará profundizándo paréntesis y paréntesis.

f(x) =  x==0 ? 1 : x*(    x-1==0 ? 1 : (x-1)*(    x-2==0 ? 1 : (x-2)*( .... )    )     )

El desplegado nos da idea de cómo son las funciones recursiva, encajándose una y otra vez dentro de sí misma. Sin embargo, lo que nos interesa es un único paso de esa recursión. Por eso, vamos a definir la función g correspondiente al factorial de la siguiente manera:

g(f, x) = x==0 ? 1 : x*f(x-1)

La función g, como depende de dos argumentos, puede currificarse. Por lo que tenemos que

f(x) = g(f)(x)

Esto significa que ahora tenemos que usar una abstracción lambda y empezar a usar funciones como valores. Lo haré primero con lenguaje natural para que sea más sencillo de entender.

g(f) = la función que toma un argumento x para devolver el valor x==0 ? 1 : x*f(x-1)

La forma de escribir lo de arriba es con expresiones lambda. Usando algo parecido a la notación de C++ aunque aún hablando de matemáticas lo de arriba sería:

g(f) = [](x) { x==0 ? 1 : x*f(x-1); }

Por otra parte, tenemos que un punto fijo es un valor que no es transformado por una función. El valor pordrá ser a su vez una función como ocurre con g. Huelga decir que cada función tendrá sus puntos fijos. Si el punto fijo de g fuera p entonces g(p)=p. Esto es muy interesante por que si p=f tendríamos que g(f)=f y por tanto g(f)(x)=f(x) que es lo que queremos calcular.

El problema resta ahora en hallar el punto fijo p de g. Porque no es inmediato obtener la función que es punto fijo de

g(f) = [](x) { x==0 ? 1 : x*f(x-1); }

En este momento es importante recordar que los puntos fijos son distintos para cada función. Como cada función g tendrá su punto fijo, puedo usar otra función que me los calcule. Llamaré a esta función P. Como P(g)=p y tenía que g(p)=p entonces

g( P(g) ) = P(g)

P es un combinador de punto fijo. El nombre "combinador" es el que se le da a las funciones que toman otras funciones como argumentos. Uno de estos combinadores es el combinador Y que destaca por su simplicidad.

Y(g) = [](t){g(t(t));} ( [](t){g(t(t));} )

A pesar de su "simplicidad" no es nada fácil ver qué hace esto. Usaremos una beta reducción (sustituir "t" en lo que hay entre llaves) para hacernos una idea. He puesto colores para que sea más sencillo seguir los cambios.

Y(g) = [](t){g(t(t));} ( [](t){g(t(t));} )

Y(g) = g(  [](t){g(t(t));} ( [](t){g(t(t));} )   )

Lo que queda dentro de g(...) es lo mismo que tenía antes por lo que sustituir sólo me introduce una aplicación de g. Siguiendo con este esquema rápidamente se observa que:

Y(g) = g( g( g( ... ) ) )

Como, además, g(f) = [](x) { x==0 ? 1 : x*f(x-1); }, lo que tendría es:

Y(g) = x==0 ? 1 : x* (x-1==0 ? 1 : (x-1)*( x-2==0 ? 1 : (x-2)*(...) ) ) 

Justamente la recursividad desplegada que se quería. En verdad, cualquier combinador de punto fijo, y no sólo el Y que es un caso especial, obtienen el resultado anterior.