sábado, 30 de abril de 2011

1, 2, 3..... TODOS A LA CHURCH!

"Estoy escribiendo la función que nunca nadie escribió.... pero no puedo terminarla"


Cuando hablamos de Javascript hablamos de funciones lambda, pero... de donde viene ese lambda?.

El calculo lambda es un sistema formal introducido por Alonzo Church allá por los años 30 para modelar la matemática (WOW! Que ambición!) pero se volvió suceptible a la paradoja de Russell y entonces lo uso para estudiar la computabilidad.
Ahora... cómo es el calculo lambda?
Bueno Alonzo introdujo algunos conceptos muy complejos en las funciones, conceptos que ya estaban ahi pero que nadie habia notado.


Los tres conceptos del cálculo lambda

Dada la función suma(x,y)=x+y Church nota los siguientes puntos

Las funciones no necesitan ser explícitamente nombradas: esto es: suma(x,y)=f(x,y)=s(x,y)=x+y, no importa el nombre de la función, sino lo que esta hace.

El nombre que se le asigne a los parámetros es irrelevante: quiere decir que suma(x,y)=x+y === suma(u,v)u+v (simple)

Toda función que recibe más de un argumento puede ser reescrita como una función que recibe un solo argumento que devuelve otra función que recibe un argumento, que devuelve otra función que recibe un argumento, que devuelve otra......(asi sucesivamente).... hasta que la ultima es la que realiza la operación: Y aqui ya necesitamos de la notación de javascript para ver de que estamos hablando

function suma(x,y){
return x+y;
}

function sumador(x){
return function(y){
return x+y;
}
}

var sumador5 = sumador(5);

alert(suma(5,4)); //9

alert(sumador5(4)); //9

a este proceso se le conoce como currificación (nombre horrible) me quedo con el ingles currying, concepto del que ya hemos hablado en este post

Con estas tres observaciones Church decide expresar sus números para realizar una aritmética básica, para ello define la función Identidad de la forma

function I(x){
return x;
}

Ahora bien, los números de Church propiamente dichos se expresan así:

El número N de Church es una función que recibe una función f como parámetro y devuelve otra función que compone la función f, N veces consigo misma.
es decir

function churchOne(f){
return function(x){
return f(x);
};
}

function churchTwo(f){
return function(x){
return f(f(x));
};
}

function churchTree(f){
return function(x){
return f(f(f(x)));
};
}

Sin embargo sería aburridisimo expresar los números de esa forma, por tanto define una funcion Sucesor que es una función que recibe un número de Church N como parámetro y devuelve el siguiente número de Church (N+1)
El sucesor de Church se escribe de la siguiente forma

function churchSucc (n) {
return function (f) {
return function (x) {
return f(n(f)(x));
};
};
}

Además tambien define el cero de Church como una función que recibe una función f como parámetro y devuelve la función Identidad (caprichoso el cero) , de la forma

function churchZero (f){
return I;
}

Pero.... de que esta hablando Church, pues bien para que se den una idea, si f(x)=x+1 , entonces el calculo lambda se vuelve la aritmética común, de esta forma podemos probar el siguiente programa completo para ver los números de Church en toda su gloria

function I (x) {
return x;
};
function churchZero (f) {
return I;
};

function churchSucc (n) {
return function (f) {
return function (x) {
return f(n(f)(x));
};
};
}

function f(x){
return x+1;
}

alert(f(0));//1
alert(I(f)(0)); //1

alert(churchZero(f)(0)); //0

var churchOne=churchSucc(churchZero);
alert(churchOne(f)(0));//1

var churchTwo=churchSucc(churchOne);
alert(churchTwo(f)(0));//2


alert(churchSucc(churchSucc(churchSucc(churchZero)))(f)(0));//3


Entonces vemos que el mismo churchSucc es una función suceptible de ser utilizada con los mismos numeros de Church para hallar números de Church superiores

alert( churchTwo(churchSucc)(churchTwo)(f)(0) );//4


Entonces vemos que se puede volver realmente muy interesante la composición sucesiva de una función.
Por ahora los dejos solamente con los números y volveremos luego con algunos operadores.
Si te cansaste de leer Church a lo largo del post, te dejo el resultado de la siguiente función

function f(x){
return x+'Church ';
}

var churchTen =churchSucc(churchSucc(churchSucc(churchSucc(churchSucc(churchSucc(churchSucc(churchSucc(churchSucc(churchSucc(churchZero))))))))));
alert( churchTen(f)(''));

//Church Church Church Church Church Church Church Church Church Church

jajajaa
que lo disfrutes!
Articulo fuente de la implementación Javascript (al que aprovechamos y le dimos una manito)

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!!!!!!!