Estando un poco aburrido y sin nada que hacer, se me vino a la mente una extraña pieza de código que había visto por ahí, esta era la función Y combinatoria. donde la vi o porque de repente pensé en ella no importa, lo importante era que ya no me la podía sacar de la mente, era como cuando se escucha mucho una canción y luego sin pensarlo terminas repitiéndola una y otra vez en la mente; así que hice lo único que podía hacer, partirme el coco intentando entender que era lo que hacia y como lo hacia. Empece como siempre preguntándole al omnisciente Google, gracias al cual encontré artículos muy interesantes, pero el que me pareció mas interesante fue uno donde a modo de ejercicio mental se va obteniendo la función Y a partir del ya conocido factorial, pero todo iba bien hasta que como mas o menos a la mitad de la explicación me perdí, así que decidí realizar el mismo ejercicio pero a mi propia manera; el resultado de ese ejercicio es este post que me salio mas largo de lo que pensé; alguien puede argumentar que es una vil copia, pero me vale. Ahora si después de esta pequeña introducción manos a la obra. A continuación la ya mencionada función Y para que vayan viendo de lo que estoy hablando:
Antes de empezar debemos tener claro lo que es closure, hay muchos artículos en los que hablan sobre este tema, pero aquí daré una explicación a mi forma de entender. una closure (no encuentro una forma adecuada de traducirla al español) es la “propiedad” que tienen las funciones anidadas de tener acceso a las variable definida en la función en la cual están contenidas (siempre y cuando no la sobrescriban) aun después de que esta ultima sea “destruida”. Como sabemos todas la variables definidas dentro de una función (por medio de var) son locales a esta y al terminar su ejecución son “destruidas”. a continuación un ejemplo:
function f(){
var x = 2;
alert( 'x vale ' + x );
};
f();// alerta 'x = 2'
alert(x):// Error variable no definida
Como vemos la variable x solo existía en el interior f. Ahora viene lo divertido, ya que si creamos una función anidada y la retornamos para hacerla visible al exterior, esta seguirá teniendo acceso a x aun después de finalizada la ejecución de f:
function f(){
var x = 2;
alert( 'x = ' + x );
return function(n){
x += n;
alert('ahora x vale ' + x );
}
};
fclosure = f(); // alerta 'x vale 2'
alert('x vale '+ x):// Error x no esta definida fuera de f
/* fclosure aun tiene acceso a x */
fclosure(1);// alerta 'ahora x vale 3'
Creo que no hacen falta mas explicaciones, esto es closure; ya que quedo claro este concepto (eso creo) podemos continuar. Ahora si empezaremos con la función factorial he iremos avanzando hasta llegar paulatinamente a la definición de Y, como ya saben la función factorial luce algo así:
function factorial(n) {
return n < 2 ? 1 : n * factorial(n-1);
}
Como vemos la función factorial se llama a si misma usando su propio nombre, este es precisamente el “problema” que resuelve Y al permitir la recursion anónima en lenguajes donde no esta soportada nativamente. como una anotación aparte dejemos en claro que javascript permite la recursion anónima gracias a la propiedad callee del objeto arguments que esta disponible en el interior de todas las funciones como vemos a continuación:
// arguments.callee es una referencia a la propia funcion
(function(n){ return n<2 ? 1 : n * arguments.callee(n-1)})(4) // retorna 24
De esta forma definimos una función que se llama a si misma sin la necesidad de usar su propio nombre (lo cual seria imposible ya que no posee uno). una vez aclarado esto empecemos por eliminar la necesidad de crear recursion en la función factorial por medio de su nombre, esto se puede lograr creando una función que llamaremos curry la cual toma como argumento una función f que en este caso sera ella misma, curry retornara la función #1 (factorial) que gracias a una closure creada (suena feo) podrá acceder a f para iniciar la recursion:
curry = function(f) {
return function(n) { // #1
return n < 2 ? 1 : n * f(f)(n-1);// llamamos la función sin usar su nombre
};
};
curry(curry)(4); // pasamos como argumento la propia función
Con esto solucionamos el problema de utilizar el nombre de la función para crear la recursion, pero la parte f(f)(n-1) se ve algo antinatural, seria mejor algo como f(n-1); si pensamos bien, la solución mas lógica es crear otra función anidada (#2) dentro de #1 la cual tome como argumento el resultado de f(f), se vería así:
curry = function(f) {
return function(n) { // #1
function g(h, n) { // #2 toma el resultado de f(f) en h
return n < 2 ? 1 : n * h(n-1); // h == f(f)
};
return g(f(f), n); // pasamos como parámetro a f(f) y n
};
};
curry(curry)(4); // retorna 24
Podríamos decir que hemos terminado, pero el tener que llamar a factorial (#2) con un argumento de mas (h) no parece algo lógico, así que separamos estos argumentos gracias a una tercera función anidada:
curry = function(f) {
return function(n) { // #1
function g(h) { // #2 toma el resultado de f(f) en h
return function (n) { // #3 solo toma n
return n < 2 ? 1 : n * h(n-1); // h == f(f);
};
};
return g(f(f))(n); // ejecutamos #2
};
};
curry(curry)(4); // retorna 24
Si nos fijamos bien la función #2 (factorial) podría ser cualquier otra (eje. fibonacci), lo realmente importante es donde se ejecuta, para lo cual lo único necesario es tener acceso a ella ya sea por estar definida globalmente o por closure, como se desaconseja el uso de variables globales lo haremos de la segunda forma tomando la función curry y anidandola en otra función que llamaremos Y :), que recibirá como argumento alguna función f para que #2 pueda acceder a ella por closure y así poder ejecutarla, también cambiamos la forma de llamar a f y usaremos apply para poder usar funciones que reciban mas de un argumento:
function Y(f){ // f = cualquier función con el formato de #factorial
function curry(g) { // g == curry
return function() { // #1
return f(g(g)).apply(null, arguments);
};
};
return curry(curry); // ejecutamos curry
};
/* ¡funciona! */
fac = Y(function(f){ // f = funcion
return function(n) { // retornar una función
return n < 2 ? 1 : n * f(n-1); // acceder a f por closure
};
});
fac(4); // retorna 24
y así es como funciona Y, aunque generalmente se encuentra escrita de la siguiente forma:
function Y(f){
return (function(h) { // h = curry
return h(h); // ejecutamos curry
}(function (g) { // la que llame curry
return function() { // #1
return f(g(g)).apply(null, arguments);
};
}));
};
Pues eso era todo, aunque casi se me estalla un aneurisma, por fin entendí como funciona la bendita función Y. espero que a alguien mas le haya sido de utilidad este ejercicio y perdonaran los errores ortográficos y/o de redacción pero esto de la escritura no me va de a mucho.