lunes, 24 de agosto de 2009

Covariancia y contravariancia (III)

Regla general

Estamos llegando a una regla más o menos universal que es: lo que se escribe desde fuera del tipo se hace contravariante, lo que se lee desde fuera del tipo se hace covariante.

En una función: Se pasan (escriben) argumentos y se devuelve (lee) el retorno. Las funciones son contravariantes en los argumentos y covariantes en el retorno.

Esto tiene que matizarse y veremos por qué en el siguiente apartado.

Menos por menos es más

Ahora vamos a hacer un esfuerzo mental para pensar en lo que ocurre cuando pasamos una función a otra función.

La función "total_sillas" tiene el siguiente tipo:

total_sillas ::  (S -> int) -> int

Esta función conoce de alguna manera todas las sillas de mi casa y usa la función que se le pasa de argumento (la S -> int) para obtener alguna propiedad numérica de estas sillas. Finalmente, retorna la suma total de estos números.

La función "total_muebles" es igual, pero trabaja con los muebles.

total_muebles :: (M -> int) -> int

Como propiedades numéricas vamos a usar estas dos funciones:

cuenta_patas :: S -> int

altura_mueble :: M -> int

Ahora vamos a ver si una se puede usar donde la otra o no.

total_muebles(altura_mueble) // OK, mismo tipo

total_sillas(altura_muebles)//Bien,las sillas tienen altura

total_sillas(cuenta_patas) //OK, mismo tipo

total_muebles(cuenta_patas) //Mal, hay muebles sin patas

Así que puedo usar "total_sillas" donde usaba "total_muebles", es decir:

 S                 <:   M

(S -> int) -> int  <:  (M -> int) -> int

Lo que significa que ¡es covariante! Esto es muy curioso porque los argumentos de una función eran contravariantes, pero los argumentos de los argumentos que serían contra-contravariantes son covariantes.

La moraleja a recordar es: La contravariancia es como el menos en la multiplicación, menos por menos es más. O sea, contravariante de contravariante es covariante.

Esto nos lleva a una regla muy usada en la teoría de tipos que es: Será covariante si está a la izquierda de un número par de "->" y contravariante en caso contrario. Esta regla se puede ver en el capítulo dedicado a la teoría de tipos del manual de las ciencias de la computación escrito por Cardelli. En la página 28.

Escribiré "cov" cuando sea covariante y "con" cuando sea contravariante en estos ejemplos:

con ->  con -> cov   (Se asocia por la derecha)

(cov -> con) -> cov

con-> (cov -> con) -> cov

(cov -> cov -> con) -> cov

((con -> cov) -> con) ->cov

En la siguiente parte de este serial veremos cómo afecta la mutabilidad a la variancia de tipos mediante el uso de punteros.

Covariancia y contravariancia (II)

Las listas y otros contenedores

Las transformaciones de tipos más simples, y las que veremos aquí, son las de construcción de nuevos tipos. Vamos a empezar por un constructor de tipos simple. Pasar de un tipo T a una lista de este tipo L(T).

Entonces, una lista de muebles lm de es de tipo L(M) y una lista de sillas ls de tipo L(S). ¿Puedo usar una donde la otra? ¿Y al revés?

Está claro que puedo usar una lista de sillas cuando me pidan una lista de muebles, pero no al revés. Así que:

S    <: M
L(S) <: L(M)

Llegando a la conclusión de que esta transformación de tipos es covariante. En general esto pasa con todos los contenedores.

Los argumentos de las funciones

Las funciones son otros constructores de tipos. Si tengo un tipo T1 y otro tipo T2, el tipo de una función que toma un argumento T1 y devuelve un valor T2 será  T1 -> T2.

¿Son las funciones covariantes o contravariantes? Empezaremos por una función simple a ver qué ocurre.

fs :: S -> Int  //fs es una función que toma una silla y devuelve un Int
fm :: M -> int  //fm es una función que toma un mueble y devuelve un Int

Tengo las siguientes posibilidades:

fm(m) //OK: Mismo tipo
fs(m) //Uso fs donde usaba fm: Mal, requiero una silla y me dan un mueble
fs(s) //OK: Mismo tipo
fm(s) //Uso fm donde usaba fs: Bien, requiero un mueble y me dan una silla

Es decir, que puedo usar "fm" por "fs" pero no al revés.

S        <: M
S -> Int :> M -> int

Así que las funciones son contravariantes si nos fijamos en sus argumentos.

Los retornos de las funciones

Si hacemos lo propio con los retornos, ¿qué pasará?

fs :: Int -> S  //fs es una función que toma un Int y devuelve una silla
fm :: Int -> M  //fm es una función que toma un Int y devuelve un M
s=fs(1) //OK mismo tipo
s=fm(1) //Mal, no todos los muebles son sillas
m=fm(1) //OK mismo tipo
m=fs(1) //Bien, una silla es un mueble

Entonces

S        <: M
S -> Int <: M -> int

Así que las funciones son covariantes si nos fijamos en sus retornos.

Es importante destacar a partir de ahora que la variancia dependerá de en qué argumento del constructor de tipos nos fijamos. Así pues diremos que el constructor de funciones -> es contravariante en el tipo de su izquierda (el argumento) y covariante en el de la derecha (el retorno).

En la siguiente parte veremos qué ocurre si usamos funciones que tomen o devuelvan funciones. Lo que se denominan funciones de alto nivel.

Estrategias de evaluación

Estrategias de evaluación

Una de las cosas interesantes en la computación es que un mismo cálculo se puede efectuar de muchas maneras ¡incluso cuando es el mismo programa!

Un ejemplo sería el siguiente:

f(x)= 2*x

g(x)= 3*x

g(f(4)) = ?

Hay dos maneras de proceder. La primera sería pensar "como no conozco f(4), voy a calcularla y luego la sustituyo".

f(4)=2*4=8

g(f(4))=g(8)

Otra manera de pensar sería "como sé cómo funciona g, voy a usar esa receta haya lo que haya en su argumento".

g(f(4))=3*f(4)

Esto, que parece una tontería, tiene hasta varios nombres. La primera forma de proceder es lo que se llama el orden aplicativo, evaluación estricta o paso por valor de los argumentos. La segunda forma de proceder es lo que se llama el orden normal o paso por nombre de los argumentos.

Computaciones infinitas

¿Realmente merece la pena tanto follón por esta sutileza? La respuesta es que, si los programas de ordenador no se colgasen, no importaría. Pero los programas de ordenador pueden entrar en computaciones infinitas que no acaban.

Supongamos una función que no acaba ω(x). Es mejor nunca calcularla porque no vamos a terminar. Ahora, supongamos una función constante que ignora su argumento y siempre retorna 7. Es decir:

constante(x)=7

¿Qué ocurre si calculo  constante(ω(1))? Si uso el orden normal he de sustituir sin ver lo que hay dentro de los argumentos y, por tanto

constante(ω(1))=7

He llegado al resultado. Si uso el orden aplicativo, he de calcular primero los argumentos.

constante(ω(1))=constante( ...y se queda colgado calculando ω

No puedo calcular el valor de ω porque no termina. Así que dependiendo de la estrategia de evaluación que use podré o no podré calcular ciertos valores.

De la pereza y otros vicios

El orden normal es magnífico porque no evalúa lo que no tiene que evaluar, pero es muy ineficiente. Esto lo vamos a comprobar en el siguiente ejemplo en el que hemos definido la función h y usamos el orden normal:

h(x)=x*x*x*x

h(f(3))=f(3)*f(3)*f(3)*f(3)

Hemos de calcular f(3) cuatro veces cuando realmente sólo hacía falta una. Esto con el orden aplicativo no habría ocurrido:

h(f(3))=h(6)=6*6*6*6

La solución es modificar ligeramente el orden normal para obtener lo que se llama la evaluación perezosa (hay diversos tipos, este es uno de ellos). La evaluación perezosa registra cuando una misma expresión se usa en varios sitios a la vez de manera que, cuando se evalúa una de esas expresiones, automáticamente todas pasan a tener el valor del resultado. En el caso de arriba sería:

h(f(3))=f(3)*f(3)*f(3)*f(3)=6*6*6*6

He puesto en gris las copias que no se calculan sino que se ponen con el resultado que da la copia que sí se evalúa (en negro). De esta manera, se evitan los problemas de la evaluación estricta y del orden normal.

Como detalle final, existen otras estrategias de evaluación: paso por referencia, paso compartido, expansión de macros, etc. Hay un interesante (aunque algo confuso en algunos aspectos) artículo en la wikipedia.

Covariancia y contravariancia (I)

Covariancia y contravariancia en el álgebra lineal.
En el álgebra lineal el concepto de variancia tiene que ver con el tipo de transformación que realiza una cantidad bajo un cambio de base. Si la transformación es con la base será covariante, si es en contra de la base será contravariante.
Por ejemplo, si mi base es
[$$B=\left\{e_1,e_2\right\}$$]
y tengo un vector
[$$V=3 e_1 + 4 e_2$$]
Si cambio la base a
[$$B'=\left\{e'_1,e'_2\right\}=\left\{2e_1,4e_2\right\}$$]
Para que el vector siga siendo el mismo los componentes tienen que cambiar. Ahora
[$$V=\frac{3}{2}e'_1 + e'_2$$]
Los componentes son contravariantes porque compensan el cambio de base. Por ejemplo, el primer vector de la base creció al doble mientras que ese mismo componente se redujo a la mitad.
La base en sí es covariante aunque esto sea trivial.
Es importante aquí resaltar que un objeto matemático que se transforme de manera contraria a uno contravariante debe ser covariante. En ese sentido la contravariancia es como el menos en la multiplicación. Menos por menos es más. Contravariante de contravariante es covariante.
Covariancia y contravariancia en la teoría de tipos.
Aunque en la teoría de tipos la cosa es bastante distinta, ambos tipos de variancia provienen de la correspondiente variancia en las categorías. No voy a seguir por aquí. Quién quiera saber más debería leer este libro de Pierce.
Centrándonos en la teoría de tipos, la covariancia y contravariancia tiene que ver con la relación de herencia de los tipos. Si el tipo S (las sillas) es un refinamiento del tipo M (muebles) diremos que
[$$S <: M$$]
Esto es más o menos obvio. El tipo de las sillas es un refinamiento del tipo de los muebles. El tipo de las sillas es menor que el tipo de los muebles.
Si tengo una transformación de tipos T y el resultado es que
[$$T(S) <: T(M)$$]
Entonces la transformación es covariante. Sin embargo, si la transformación es
[$$T(S) :> T(M)$$]
diremos que es contravariante.
¿Para qué sirve esto? La respuesta en el siguiente post dedicado al tema.

viernes, 21 de agosto de 2009

Higiene en tu macro

El modelo de entornos

A la hora de sustituir nombres de variables por valores hay dos formas de proceder. La primera es el modelo de sustituciones propio del lambda-cálculo. Si x vale 3 cambio la x por el 3. Este modelo es válido cuando la x siempre vale 3. Si quiero que la x valga otra cosa necesito saber cuándo vale 3 y cuándo vale otra cosa.

En este punto entra la idea de entorno. Un entorno no es más que una serie de nombres con sus valores correspondientes. Podría ser algo como

x=3
y="hola"
z=λx.f(x)

En la variable z hay una cosa interesante. ¡Hay una x! Y la x valía 3... a no ser que esté en otro entorno. Eso es lo que ocurre. El lambda-cálculo se integra en el modelo de entornos haciendo que las abstracciones lambda tengan un pequeñito entorno dentro de ellas. Este entorno local se crea cuando se aplica la abstracción. Al calcular

z(7)

lo que ocurre es que creo un entorno nuevo donde los parámetros (la x) se vinculan a los argumentos (el 7)

x=7

Y, entonces, sustituyo:

z(7)=f(7)

Ahora tenemos otro problema: ¡f no está en ninguno de nuestros entornos! Cierto. Debe existir otro entorno donde esté f definida y ese entorno debe estar visible desde el entorno local de la lambda. Así pues, cada entorno puede tener un entorno padre donde busque los nombres que no encuentre en él mismo.

Los tres entornos, las funciones

Existen tres entornos que participan a la hora de calcular el valor de una función. Son:

  • El entorno de uso. Es decir, donde se realiza la aplicación de la función con sus argumentos.
  • El entorno local. Es ese donde se vinculan los argumentos a los parámetros. Es temporal, en cuanto se acabe de calcular la función, se olvida.
  • El entorno de definición. Es donde se creó la función, la abstracción lambda. Es donde está la f del ejemplo anterior.

En una función, el entorno padre del entorno local es el entorno de definición. Esto es lo que se llama la clausura léxica. Muchos lenguajes no soportan que un entorno tenga padre y, por tanto, usan los nombres de un entorno global.

El entorno local protege el entorno de uso de agresiones. Si una función tiene que usar un nombre para un cálculo parcial, ese nombre estará en el entorno local y morirá cuando la función termine de calcular. Si eso no fuera así tendríamos el siguiente problema.

funcion f(x) :=
{
 //Creo aquí un nombre que debería ser
 //temporal y oculto en f(x)
 y=x*x;
 retorna 2*y;
}
//Creo aquí un nombre que no tiene nada que ver
//con el anterior y porque estamos en otro entorno
y=7;
f(4);
//¿Cuánto vale aquí y?

Si y vale 7 significa que hemos protegido la y de fuera de f(x) de la y de dentro que vale 4*4=16.

Y las macros higiénicas

El no proteger estos símbolos da origen a lo que se llama falta de higiene porque ensuciamos los símbolos de fuera. Es una característica de los sistemas de macro tradicionales. Una macro es un conjunto de expresiones que se ponen, sin más miramientos, donde aparece el nombre de una macro.

Como ejemplo, una macro m definida así:

macro m :=
{
y=3; //Defino la y dentro del código.
f(z);
}

Y usada en un código así:

z=7;
m;
print(y); //Debería dar error, no he definido ninguna y en este código.

Da este resultado:

z=7;
y=3; //Contamino el entorno de fuera desde la macro.
f(z); //Uso la z de fuera en la macro ¿es esto deseable?.

print(y); //Captura la y de la macro en vez de estar sin definir.

Es completamente antihigiénico porque introducimos el símbolo y en el entorno de uso.

Las macros higiénicas evitan eso usando, como las funciones, un entorno local. Sería entonces algo parecido a:

z=7;
{
y=3; //No contamino el entorno de fuera
f(z); //¡¡No es una función porque puedo usar la z!!

}
print(y);

Las macros higiénicas pueden verse como una función en el que el entorno padre del entorno local no es el entorno de definición, sino el de uso.

jueves, 20 de agosto de 2009

La berenjena osmotizada

Hoy voy a tratar un tema algo offtopic: Las berenjenas y su sabor.
Las berenjenas tienen, al natural, un sabor amargo y picante. Particularmente, me desagrada mucho. Si se cocinan bien, las proteínas que dan esos sabores se desnaturalizarán y puede que se rompan también. Es decir, cambian las propiedades . Desafortunadamente rara vez se pueden eliminar todas esas moléculas sin quemar completamente la berenjena.
Un truco que me contaron es usar la osmosis con sal. La osmosis ocurre cuando dos volúmenes de agua están en contacto por una membrana que deja pasar sólo el agua. Luego, si echamos sal en uno de los dos volúmenes, este volúmen roba el agua al otro. Es decir, el agua intenta igualar las concentraciones atravesando la membrana.
La celulosa de la berenjena en mayor o menor medida hace de membrana así que si ponemos la berenjena (pelada y troceada) en un cuenco con agua salada entra en acción la osmosis. El agua que hay dentro de la berenjena va a intentar atravesar sus paredes de celulosa para ir al cuenco. Lo bueno es que también arrastrará las proteínas amargas esas fuera.
Entre otras moléculas, este procedimiento lleva fuera de la berenjena las moléculas que se ponen negras cuando se oxidan. Veremos que el agua del cuenco se va poniendo oscura. Cuando lleve un rato así, la tiramos y ¡hala! Ya tenemos berenjenas listas para cocinar. El sabor resultante será agradable y con amarguras y picores reducidos.

martes, 18 de agosto de 2009

Des contra de

Está extendido el uso de la palabra "decodificar" proveniente del inglés "decode". En español debería ser "descodificar" y la diferencia entre estas palabras proviene del prefijo que usan los idiomas para indicar "el verbo que hace lo contrario".

En inglés este prefijo es "de" y se usa en palabras como "deactivate" (desactivar), "decaffeinated" (descafeinado) o "demagnetize" (desmagnetizar). Obviamente, en español las palabras equivalentes empiezan por "des".

Sin embargo, la palabra "decodificar" ha tomado más arraigo de la cuenta. Probablemente, por malos traductores y la confusión con el prefijo "de" que aparece en algunas palabras españolas como "delimitar" (poner límites) o "defenestrar" (tirar por la ventana).

Existe también otra palabra de este tipo que se lee de vez en cuando en los libros de informática que es "dereferenciar" en vez de "desreferenciar". En inglés es "dereference". Esta palabra se usa cuando se obtiene el valor al que apunta una referencia. El clásico  *p  de C/C++.

La sorpresa es que "decodificar" está aceptado por el diccionario de la RAE con un tímido "1. tr. descodificar." Me pregunto: ¿Dónde quedó aquello de "limpia, pule y da esplendor"?

domingo, 9 de agosto de 2009

Punteros y demás hierbas

¿Qué maneras hay de referenciar un objeto en un programa? Que se me ocurran:

  • Referencia: Es la idea general de tener un valor que representa otra cosa. Realmente todos los mecanismos que vamos a ver son referencias. Nota: En algunos lenguajes como el C++ las referencias son concretamente una mezcla entre puntero y alias. 
  • Alias: Damos un nombre para el objeto. Usamos ese nombre para referenciarlo. Los alias no están reificados. Es decir, no existen durante la ejecución de un programa. Si así fuera, necesitaríamos algún tipo de almacén para guardar la relación nombre-objeto y estaríamos hablando de un identificador (ver más abajo). Entonces, un alias es un mecanismo externo al programa. Por ejemplo, los nombres de variables que viven en el compilador y se olvidan antes de llegar al programa ejecutable. Esta idea de "ser externo al programa" o "no sabido por el programa" lleva a la idea de alias como algo "no querido" que es el aliasing (múltiples referencias desconocidas para el mismo objeto).
  • Puntero: Es la dirección de memoria donde está el objeto. Generalmente los punteros son mala idea porque no abstraemos. Realmente nos da igual la dirección de memoria en concreto, lo que nos interesa es el objeto. Esto hace que haya limitaciones a la hora de usar el puntero. Por ejemplo, si el objeto se mueve a otra dirección de memoria, el puntero queda invalidado. El saber la dirección donde está el objeto significa que llegar a él es muy rápido. De complejidad O(1) (constante).
  • Índice: Si el objeto está en una colección lineal de objetos, se puede llegar al objeto en concreto sabiendo su posición dentro de la colección. Eso es el índice. En este caso no nos liamos con direcciones de memoria, aunque necesitamos una colección y que la colección esté ordenada de forma que podamos contar las posiciones. De hecho, nada impide que la colección esté en otro sitio en vez de memoria como un fichero en disco o en algún dispositivo de entrada/salida. Aunque, en general, se intenta que la complejidad de acceso al objeto sea O(1) (constante).
  • Identificador: Si el objeto está en un diccionario, se puede llegar al objeto en concreto sabiendo su clave dentro del diccionario. Eso es el identificador o asidor (handle) del objeto. Este identificador ya no tiene por qué ser numérico. Ahora puede ser un número (aunque no relacionado con una colección lineal), un nombre, una estructura compleja o cualquier cosa que sea comparable (y ordenable por motivos de eficiencia). Tampoco hay aquí problema con las relocalizaciones del objeto siempre y cuando se mantenga actualizado el diccionario. Eso sí, usualmente los identificadores tardan más en resolver la referencia (llegar al objeto) con una complejidad, en los casos usuales, de búsqueda en el diccionario. Sería O(log n) para árboles y O(n) amortizada para tablas hash.
  • Iterador: Es la abstracción de lo anterior. Un iterador es una posición, pero no de memoria. Es una posición abstracta. Podría ser un puntero, un índice, un identificador o cualquier otra cosa. El nombre de iterador proviene del hecho de que la operación más común que se suele realizar sobre él es "pasar a la siguiente posición" para recorrer colecciones (lo que se llama iterar). Sin embargo, su noción más abstracta es la de posición y existen iteradores que no iteran. Esta variedad hace que sea imposible dar una complejidad para los iteradores, cada tipo tendrá su complejidad a la hora de llegar al objeto que referencian.
  • Rangos: Extienen la idea de referencia a un objeto a referencias a colecciones de objeto. Como se sale un poco de la pregunta inicial, sólo dejaré constancia de su existencia.

sábado, 8 de agosto de 2009

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.

martes, 4 de agosto de 2009

EL interfaz vs LA interfaz

Tengo la costumbre de decir EL interfaz. Sin embargo, la palabra "faz" está claro que es femenina. Así que debería decirse LA interfaz. Por alguna extraña razón, sigo notando que no encaja "la" con "interfaz".

lunes, 3 de agosto de 2009

Azucar, sal y sacarina

El azúcar sintáctico es una pequeña adición a la gramática que, en vez de introducir una nueva semántica, símplemente replica una semántica ya expresada. Por ejemplo, si un lenguaje de programación tuviera algo como "add(x, y)" para sumar dos valores, un azúcar sintáctico sería escribir "x+y". Hace exáctamente lo mismo, pero facilita mucho las cosas.

Bien, hay también la llamada sal sintáctica. Esto es una sintaxis que fuerza el buen comportamiento del programador. Aunque generalmente sea visto por el programador como "un latazo". El ejemplo es el tener que escribir "end if" en vez de "end" en algunos lenguajes para recordar que ese "end" era de un "if". Además, el compilador se queja si no se emparejan los "if" con los "end if". Esto es bueno, permite detectar errores y despistes, pero es un latazo.

Finalmente, hay almas cándidas que creen que una idea suya es buenísima e implementan una sintaxis especial para algo que ya existe en el lenguaje, pero que puesta de esta nueva forma es mucho más fácil. Realmente, nadie usa esa sintaxis especial por lo que el azúcar sintáctico se queda sólo en sacarina sintáctica.