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)
Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s