viernes, 15 de abril de 2011

Sabes programar en javascript...Y?

"Puedo escribir las funciones menos tristes esta noche."
picanteverde

Despues de tanto tiempo sin traerles nada divertido al blog, he decidido volver porque por suerte ahora tengo un trabajo donde puedo aprender cosas nuevas para traer por aca.
Hoy vamos a hablar de Y combinator (me encantaría escribir este post en ingles pero lo voy a hacer en castellano para contribuir un poco a la poquisima cantidad de articulos (de buen javascript) en este idioma).

Qué es el combinador Y?

Ademas de ser una empresa de Capital de riesgo de inversión y un operador matemático (por dios que estas leyendo) tambien conocido como Fixed Point Combinator
es uno de los artilugios más fascinantes de la ciencia de la computación y es muy simple de explicar (eso es mentira).

El Combinador Y es una funcion de alto orden que calcula el punto fijo (fixed point) de otra funcion.

Si no entendiste nada vamos por partes.

El punto fijo (fixed point) de una función f es un valor x tal que: f(x)=x
Por ejemplo 1 y 0 son puntos fijos de la función cuadrado, debido a que si
f(x)=x^2 entonces 1^2=1 y 0^2=0.
Ahora bien, eso es valido para funciones de primer orden (funciones en valores simples como enteros).

Para una función f de alto orden, un punto fijo es otra función p de forma que f(p)=p
y un combinador de punto fijo (combinador Y), es OTRA función g que produce una función punto fijo p para cualquier funcion f de forma que:
p=g(f), f(p)=p
ó
f(g(f))=g(f)

ya se a esta altura te estas arrepintiendo de haberte puesto a leer algo que no parece tener nada que ver con javascript pero ahora vamos a escribirlo en javascript, no porque sea útil en si, disculpen mi obtusa visión pero aún no logro comprenderlo tanto como para encontrarle una funcionalidad, es por eso que decidí escribir este post (de la misma forma que el post que estoy leyedo ).

Para qué sirve Y?

Y es comúnmente usado para permitir recursión anónima en lenguajes donde no se puede asumir que esté soportada.
Veamos un ejemplo con una función para calcular el factorial de un numero de forma recursiva.

var factorial = function(x){
return x == 0 ? 1 : x * factorial(x - 1);
};

alert(factorial(4)); //24

pero que pasaría si....

var factorial = function(x){
return x == 0 ? 1 : x * factorial(x - 1);
};

var fac=factorial;
factorial="nada";
alert(fac(4));


Deja de funcionar debido a que factorial llamado desde dentro de la función no es más la función misma, sino otra cosa.

Antes que nada voy a aclarar que javascript si permite recursividad anónima usando callee

var factorial = function(x){
return x == 0 ? 1 : x * arguments.callee(x - 1);
};

var fac=factorial;
factorial="nada";
alert(fac(4));


Peeeero si no pudiese, necesitaríamos el combinador Y, vamos a encontrarlo.

Supongamos que para evitar esto, pasamos una referencia de la función con la que debe realizar la recursividad, evitando así hacer cualquier tipo de referencia a alguna variable global.

var factorial = function(h, x){
return x == 0 ? 1 : x * h(h, x - 1);
};
alert(factorial(factorial, 4));// 24

Pero podemos precompilar el primer parametro de la función y devolver una función que reciba solo un parametro, y escribirla de la siguiente manera

var factorial = function(h){
return function(x){
return x == 0 ? 1 : x * h(h)(x - 1);
};
};

alert(factorial(factorial)(4));

Aquí yace la magia, factorial recibe una referencia a si misma y devuelve una función recursiva sobre su propia referencia, de ahí que [h(h)] devuelve una función recursiva sobre si misma. Por tanto debemos invocarla en la forma [factorial(factorial)](4), donde la función devuelta por factorial(factorial) es la función recursiva.

Hasta ahí todo bien, pero tenemos ese h(h)(x) en la definición de la función, en lugar de un simple q(x), entonces podemos crear otra función de envoltorio que cree una referencia a h(h), es simplemente para poder llamarla en la forma q(x)


var factorial = function(h){
return function(x){
var f = function (q,x){
return x == 0 ? 1 : x * q(x - 1);
};
return f(h(h), x);
};
};

alert(factorial(factorial)(4));

Ahora en la función f podemos realizar la misma precompilación del primer parametro que ya hicimos antes y obtener la siguiente función

var factorial = function(h){
return function(x){
var f = function(q){
return function(x){
return x == 0 ? 1 : x * q (x - 1);
};
};
return f(h(h))(x);
};
};

alert(factorial(factorial)(4));


pero ahora, la función f no posee ninguna referencia externa o global, asi que podemos sacarla afuera, y aún así funcionará.

var f = function(q){
return function(x){
return x == 0 ? 1 : x * q (x - 1);
};
};

var factorial = function (h){
return function (x){
return f(h(h))(x);
};
};

alert(factorial(factorial)(4));


Ahora llegamos a que f es nuestra función de la que queremos el punto fijo. el punto fijo es la función devuelta por factorial(factorial), entonces podemos escribir Y() para que nos la devuelva de la siguiente manera.

var Y = function (f){

var g = function (h){
return function(x){
return f(h(h))(x);
};
};

return g(g);
};

var factorial = function (q){
return function(x){
return x == 0 ? 1 : x * q(x - 1);
};
};

var factorial_recursivo = Y(factorial);

alert(factorial_recursivo(4));


Finalmente escrita en propósito general, quedaría


var Y = function(f){
return (function (g) {
return g(g);
})(function(h) {
return function(){
return f(h(h)).apply(null,arguments);
};
});
};

//Y LISTO!!!! ahora podemos escribir factorial así

var factorial = Y(function(recurse){
return function(x){
return x==0 ? 1 : x * recurse(x - 1);
};
});

alert(factorial(4)); //24!!!!!!!!



Lo más frustrante acerca del combinador Y es que una ves que lo derivaste, es imposible decir que hace, con solo mirar su código.
Si llegaste hasta aquí, sin marearte, FELICITACIONES!!!!!!!

6 comentarios:

  1. No leí el post, pero me alegra ver que retoma la actividad señor Alejandro. A ver si leemos más seguido.

    ResponderEliminar
  2. Te pasaste man... Lo lei, pero no lo pude entender, me lo llevo como tarea para casa...

    ResponderEliminar
  3. Muy bueno, me toco leer como 2 veces algunas partes y tomar papel y lápiz para tener mejor la secuencia. Realmente no creo que lo use, pero es bueno haber aprendido algo nuevo :)
    Excelente explicación.

    ResponderEliminar
  4. Y uno cree que sabe programar, lee este tipo de artículos y se pone a estudiar de nuevo hahaha

    Saludos

    ResponderEliminar