El manantial de bits

Pasos en la profesión

2012-01-19T15:51:00.000+01:00

Una idea que quiero concretar antes de que se me olvide.

Sueños: En este momento sólo se tienen ideas de la profesión. Suele ocurrir cuando se es aún un niño.
Realización: Las ideas se concretan en obras. Si se quería ser alfarero, se realizan las primeras vasijas. Si se quería ser programador, se terminan los primeros programas.
Estudio: Siempre me ha llamado la atención que, sea cual sea la disciplina que se estudie, siempre hay una grandísima cantidad de temas de estudio. Ni que decir tiene que para progresar en la profesión, hay que estudiar. Aunque tampoco demasiado porque si no, no pasamos al siguiente punto.
Práctica: Generalmente el resultado de la realización de ideas no es lo que se tenía en mente. Hay que practicar para que el abismo entre imaginación y realidad se haga más somero. Este es el paso más difícil desde mi punto de vista, ya que se debe trabajar mucho pero no hay realimentación de resultados.
Mercado: Llega un momento en el que las obras realizadas se pueden mostrar al público e, incluso, algunas, vender. Estamos tocando el mercado. Empieza a haber resultados.
Profesión: Es cuando se pueden obtener ingresos regulares de lo que se crea y esos ingresos son suficientes para vivir.
Reconocimiento: El trabajo que se realiza es reconocido entre los que se dedican a lo mismo.
Éxito: Simplemente, los ingresos son muy superiores a lo que se necesita para vivir. Si se dejase de trabajar, seguiríamos teniendo ingresos por regalías o licencias.
Fama: El trabajo que se realiza es reconocido entre los que no se dedican a lo mismo.
Inmortalidad: El trabajo que se realiza sigue siendo reconocido generaciones después.

Es interesante dar un factor de filtrado a cada paso. Así, si de cada 10 que tienen ideas, 1 las realiza; el factor es de 10. De realización a práctica el factor puede ser de 5, pero de práctica a mercado creo que es 20 o más. De mercado a profesión puede ser de 5 o así. Es decir que, a bote pronto, una de cada 5000 personas puede vivir de sus sueños.

Es una estimación algo burda, pero tomándolo como un problema de Fermi el resultado nos puede dar a ver la dificultad de la tarea.

miniSL parte 17 - El analizador léxico

2011-12-01T12:43:00.001+01:00

Hasta aquí hemos visto la semántica de nuestro lenguaje script mínimo. A partir de ahora, empezamos con el reconocedor sintáctico. Debido a que nuestro lenguaje tiene una sintaxis no trivial, nos ocupará bastante tiempo describirlo. (Una sintaxis trivial es la del LISP)

Generalmente los reconocedores sintácticos se separan en dos partes (por ejemplo, el clásico LEX&YACC). La primera llamada analizador léxico (scanner o lexer) reconoce varios caracteres del fichero de entrada (por ejemplo 3, 5 y 6) y nos devuelve un elemento significativo llamado token (el número 356). La segunda parte es el analizador sintáctico propiamente dicho (llamado parser) que acepta los tokens y devuelve un AST. Veremos esta segunda parte más adelante y nos centramos en la generación de tokens.

En miniSL hay varios tipos de token que se listan en la enumeración TOKEN_TYPE.

enum TOKEN_TYPE { T_NONE, T_RAW, T_LITERAL, T_SYMBOL, T_NAME };

El tipo T_NONE indica que no se han reconocido los caracteres. Usamos T_RAW cuando el token es un único carácter (por ejemplo, una llave { o una coma , ). Es importante saber aquí que el final de fichero, un carácter llamado EOF, también se guarda en un token de tipo T_RAW. El tipo de token T_LITERAL indica o bien un número, o bien una cadena, en general una celda literal. Guardaremos el valor que corresponda en una celda del tipo adecuado. El token de tipo T_SYMBOL es un identificador formado por símbolos tales como +, <= o !=. Finalmente, T_NAME se usa para identificadores alfanuméricos como x, map o iterator. Tanto los tokens de tipo T_SYMBOL como los T_NAME guardan el identificador en una celda de tipo STRING_LIT.

La información del tipo de token y la información relativa al token se guardan en la estructura TOKEN que es la siguiente.

struct TOKEN
 {
  TOKEN() : type(T_NONE) {}
  TOKEN(TOKEN_TYPE t, CELL* d) : type(t), data(d) {}
  TOKEN(ISTREAM::int_type r) : type(T_RAW), raw(r) {}

  TOKEN_TYPE type;
  union
  {
   CELL* data;
   ISTREAM::int_type raw;
  };
 };

Los constructores fuerzan que cuando el TOKEN sea de tipo T_RAW, la información relacionada es un único carácter guardado en la variable miembro raw. En los otros tipos lo guardaremos en la celda apuntada por la variable miembro data. Esta estructura no es muy segura porque podríamos colar un T_RAW en el constructor que toma una celda. Vigilaremos que eso no ocurra.

Ahora queda leer los caracteres y generar el token correspondiente. De eso se encarga la función ReadToken(). La función ReadToken() devuelve el siguiente token leído y lo consume. De esta forma, cada vez que llamemos a ReadToken() avanzaremos por el fichero hasta obtener el carácter de fin de fichero EOF. Sin embargo, muchas veces no querremos avanzar por el fichero. Querremos únicamente saber cuál es el siguiente token, sin consumirlo. De esto se encarga la función PeekToken().

Nota: “Peek” en inglés significa “ojear” en el sentido de mirar a hurtadillas.

Script::TOKEN Script::PeekToken(ISTREAM& i)
{
 if(m_Ahead.type!=T_NONE)
  return m_Ahead;

 m_Ahead=ReadToken(i);
 return m_Ahead;
}

El funcionamiento de PeekToken() es muy simple porque se basa en ReadToken(). Primero, comprueba si ya hemos leído el siguiente token que se ha guardado en m_Ahead. Esta no es más que una variable miembro en la clase Script (para los que no recuerden la clase Script, ver la parte séptima).

TOKEN m_Ahead;

Si m_Ahead guarda ya el token leído, lo devuelve. Si m_Ahead no contiene el token leído, lo lee con ReadToken() y lo guarda en m_Ahead para siguientes PeekToken()s. De esta manera, llamar a PeekToken() varias veces, sólo llama a ReadToken() la primera vez y usa m_Ahead el resto.

¿Por qué es importante saber cómo funciona PeekToken() antes de saber cómo funciona ReadToken()? Muy sencillo. Si m_Ahead contiene un token y llamamos a ReadToken(), hay que vaciar m_Ahead. De esta forma se consume.

Script::TOKEN Script::ReadToken(ISTREAM& i)
{
 if(m_Ahead.type!=T_NONE)
 {
  TOKEN t=m_Ahead;
  m_Ahead.type=T_NONE;
  return t;
 }

A partir de este momento empieza, realmente la lectura de caracteres dentro de ReadToken(). La primera acción es saltarse el espacio en blanco. Nuestra sintaxis va a ignorar los espacios en blanco.

SkipWhitespace(i);

Luego, vamos a ojear el siguiente carácter. Podréis comprobar que no he inventado nada nuevo al llamar PeekToken() a mi función ya que la biblioteca estándar de C++ llama a esta función peek().

ISTREAM::int_type c=i.peek();

Según sea ese carácter, decidiremos leer un token de un tipo o de otro. Si es una doble comilla, será una cadena.

if(c=='"')     return TOKEN(T_LITERAL, &ReadString(i, false));

Si es un símbolo ASCII extendido, lo examinaremos. Para eso usamos la comparación c<256.

if(c<256)
 {
  if(isalpha(c) || c=='_') return ReadName(i);
  if(isdigit(c))    return TOKEN(T_LITERAL, &ReadNumber(i));
  if(CELL::IsSymbol(c))  return TOKEN(T_SYMBOL, &ReadSymbol(i));

Hasta aquí todo sencillo. Si es un carácter alfanumérico, lo leemos como un nombre. Si es un dígito, como un número. Si es un símbolo, como símbolo.

Pero ahora vamos a añadir una puerta trasera que ya ha sido muy útil. De hecho, nos ha permitido imprimir de manera uniforme los identificadores. Básicamente consiste en poner una arroba delante de una cadena. Entonces, en vez de cadena tomamos ese token como un identificador. Será lo mismo escribir mi_variable que @”mi_variable”. También añadiremos la sintaxis de arroba seguido de símbolo con la misma idea. Será lo mismo escribir 3+5 que @+(3,5).

if(c=='@') //Symbol or string as name
  {
   i.get();
   if(i.peek()=='"')    return TOKEN(T_NAME, &ReadString(i, true));
   if(CELL::IsSymbol(i.peek())) return TOKEN(T_NAME, &ReadSymbol(i));
   throw L"Expecting a symbol or a string after @";
  }
 }

Si el carácter no es ASCII extendido, será probablemente el carácter EOF así que lo guardamos como un token T_RAW. Además, si ninguna de las condiciones anteriores se dio, será un carácter ASCII extendido no usado por otro tipo de token. Deberá ser T_RAW también.

//Raw one-character token
 return TOKEN(i.get());
}

Nota: Esto no funciona con UTF-8 que sería lo suyo. Introduciríamos una complejidad que sobrepasa los objetivos de este pequeño lenguaje de script.

Y ya hemos leído el token. Ahora queda examinar todas esas funciones de ayuda que hemos utilizado. Empezaremos con SkipWhitespace() en la siguiente parte y seguiremos con ReadString() y demás más adelante.

Historia de la gestión de símbolos

2011-11-16T12:57:00.000+01:00

PARTE I: COMPILADOR Y VINCULADOR

Hoy en día damos por hecho muchas cosas que han costado muchos años descubrir, usar y pulir. Una de ellas es la gestión de los símbolos. Allá por los años cincuenta, si alguien quería hacer un programa debía escribir el código fuente y, como en estos años los compiladores eran muy simples, directamente te generaban el código ejecutable.

Usualmente el código fuente estaba en tarjetas perforadas y el ejecutable se quedaba en memoria, donde se ejecutaba.

Luego, conforme pasaban los años, los programas se iban haciendo más y más grandes. Recompilar todo cada vez era tedioso y para reutilizar un trozo de código hay que volverlo a escribir. La solución es partir los programas. El problema es que este compilador tan simple no me permite partir los programas.

La solución fue usar dos pasos a la hora de compilar. El primer paso es la compilación a un código intermedio que se denomina código objeto. El código objeto es como el código ejecutable, pero tiene marcas de dónde está cada objeto del código (lo que técnicamente se denomina un símbolo exportado). De ahí el nombre "código objeto". Luego, un segundo paso es el vinculador (o enlazador) que lee esas marcas del código objeto y como si fuera un puzle va componiendo el programa ejecutable final y completo.

Esto causa un problema porque... ¿cómo sabe el código fuente de la parte 1 lo que hay en el código fuente de la parte 2 si puede que incluso hayan sido programados por gente completamente distinta?

PARTE II: SÍMBOLOS Y SÍMBOLOS EXTERNOS

A finales de los sesenta apareción un lenguaje que aún hoy es de los más usados. El lenguaje C. Una de las virtudes del C es que soluciona el problema antes mencionado. La solución que se usa en C es permitir usar objetos sin definirlos. Esto se realiza mediante lo que se denomina la declaración del símbolo. La declaración da toda la información necesaria para usar el símbolo, pero no dice qué es. No lo define.

Lo más usual es declararlos y definirlos que es lo que pongo aquí como ejemplo:

int a=0;

double hipotenusa(double x, double y)
{
   return sqrt(x*x+y*y);
}

El código objeto generado por este código fuente de ejemplo tiene lo que técnicamente se denomina dos símbolos: El símbolo "a" y el símbolo "hipotenusa". Ambos están definidos, es decir, que hay un trozo de ese código objeto que se asigna al símbolo "a" y otro trozo de ese código objeto que se asigna al símbolo "hipotenusa". El trozo del símbolo "a" está a cero. El trozo del símbolo "hipotenusa" tiene el código ejecutable de la función hipotenusa.

El contenido del código objeto sería algo como

Símbolo	Objeto asignado
a	0
hipotenusa	{return sqrt(xx+yy);}

Para declarar sin definir los símbolos en C se usa lo siguiente:

extern int a;

double hipotenusa(double x, double y);

El código objeto generado por este código fuente de ejemplo tiene dos símbolos: "a" e "hipotenusa". Ninguno está definido, es decir, que este código objeto sólo tiene una lista de los símbolos sin asignarle ningún objeto. Los símbolos sin objeto asignado tienen que obtenerse del exterior cuando el vinculador recomponga el puzle. Son los llamados símbolos externos, porque se definen en algún otro lugar externo al código fuente donde los declaramos.

Símbolo	Objeto asignado
a	externo
hipotenusa	externo

PARTE III: USANDO SÍMBOLOS EXTERNOS

Ahora ya sabemos cómo declarar y definir una función en código fuente y cómo usarla desde otro código fuente. Bastará declararla sin definirla.

programa_parte1.c

/* Declaramos y definimos */
void mifuncion(void)
{
   puts("Esta función está programa_parte1.c");
}

programa_parte2.c

/* Declaramos pero no definimos (prototipo) */
void mifuncion(void);

void main(void)
{
   puts("Esta función está en programa_parte2.c");
   mifuncion(); /* Se usa mifuncion() con haberla sólo declarado */
}

Primero compilamos

Según el compilador la extensión del código objeto será .o .obj .coff, etc. Los códigos objetos generados serán algo así como muestran las siguientes tablas.

programa_parte1.obj

Símbolo	Objeto asignado
mifuncion	{puts("Esta función está programa_parte1.c");}

programa_parte2.obj

Símbolo	Objeto asignado
mifuncion	externo
main	{ puts("Esta función está en programa_parte2.c"); mifuncion(); }

Ahora pasamos el vinculador o enlazador.

El vinculador es lo suficientemente inteligente como para ver que el símbolo "mifuncion" está definido en la parte 1 y es un símbolo externo en la parte 2 donde se usa. Entonces, compone ambas partes haciendo que cuando la función main() llame a mifuncion() lo haga correctamente. Finalmente el símbolo "main" es especial y lo usa como punto de entrada del ejecutable.

PARTE IV: LOS FICHEROS DE INCLUSIÓN

Ahora sólo queda un detalle menor. ¿Vamos a tener que repetir

void mifuncion(void);

cada vez que queramos usar la función mifuncion()? ¿Qué pasará si lo que tengo en el código objeto no es una función sino una biblioteca de cincuenta, cien o mil funciones? ¿Voy a tener que escribir todas las que quiera usar una y otra vez en cada fichero fuente que escriba?

La solución es poner todas las declaraciones en un fichero de cabecera (.h del inglés header). E incluir el fichero con tooodas las definiciones. Esto nos ahorra el escribir cada vez todas las definiciones.

Este uso de los ficheros de inclusión es común en lenguajes como el C y el C++.

PARTE V: LOS MÓDULOS

Realmente, usar un fichero de inclusión es una tontería: ¡ya tenemos los símbolos en el código objeto! ¿No podríamos decir en el código fuente "toma los símbolos de este código objeto"? La respuesta es sí. Existen muchos lenguajes que lo hacen. Entre ellos Java y ActionScript3. A esta acción de extraer símbolos de un código objeto y usarlos en otro código fuente se denomina "importar símbolos". Al código objeto que exporta los símbolos de esta manera se le denomina módulo o paquete.

Existen un par de salvedades a este sistema. En primer lugar, el orden de compilación es importante. Debemos compilar los códigos fuentes de manera que cuando usemos un símbolo, el código objeto que lo contiene haya sido generado previamente. Esto significa que no podemos tener ciclos en el uso de referencia aunque algunos sistemas mezclan el compilador y el vinculador en un único paso para permitir estos ciclos. En segundo lugar, es importante cómo llamamos a los ficheros de código objeto y dónde los ubicamos en el sistema de fichero.

Esto último hace que sea necesaria una jerarquía en los nombres de los módulos, usualmente separados por puntos. Así, un símbolo del sistema de módulos de Java se escribe así "java.lang.NullPointerException" y significa algo como en el directorio "java", en el subdirectorio "lang", el fichero "NullPointerException". Este tipo de nombre de símbolos compuestos de varias partes se llaman nombres completamente cualificados.

Es usual en estos sistemas de módulos que cada fichero sólo pueda definir un símbolo. Aquél que coincide con el nombre del fichero. Hay aquí una rigidez. ¿Podríamos separar los nombres de los ficheros de los nombres de los símbolos?

PARTE VI: LOS ESPACIOS DE NOMBRE

Cuando usamos un nombre cualificado como "java.lang.NullPointerException" hemos pensado que "java" es un directorio, pero desde el punto de vista del programador no es más que un nombre que contiene otros nombres, entre ellos "lang". Asimismo "lang" contiene "NullPointerException". Por esta razón, es común llamar a "java" y a "java.lang" un espacio de nombres (namespace en inglés). En el caso de Java (y de AS3) los espacios de nombres están relacionados con los directorios.

Sin embargo, en C# y C++ no es así y pueden definirse espacios de nombres en el código fuente. Eso significa que los códigos objetos exportan los símbolos con sus nombres cualificados y el vinculador tiene que ser un poco más inteligente.

Modifiquemos el programa anterior para incluir un espacio de nombre llamado "miespacio" usando C++ y añadiré otra "mifuncion" en "otroespacio". El C++ es exótico porque usa :: para separar los nombres cualificados en vez del punto.

programa_parte1.cpp

/* Declaramos y definimos */
namespace miespacio
{
  void mifuncion(void)
  {
     puts("Esta función está programa_parte1.c y en miespacio");
  }
}

namespace otroespacio
{
  void mifuncion(void)
  {
     puts("Esta función está programa_parte1.c pero en otroespacio");
  }
}

programa_parte2.c

/* Declaramos pero no definimos (prototipo) dentro de miespacio*/
namespace miespacio { void mifuncion(void); }

void main(void)
{
   puts("Esta función está en programa_parte2.c");
   miespacio::mifuncion(); /* Se usa miespacio::mifuncion() pero no otroespacio::mifuncion() */
}

Si ahora miramos los códigos objeto encontramos los siguientes símbolos.

programa_parte1.obj

Símbolo	Objeto asignado
miespacio::mifuncion	{puts("Esta función está programa_parte1.c y en miespacio");}
otroespacio::mifuncion	{puts("Esta función está programa_parte1.c pero en otroespacio");}

programa_parte2.obj

Símbolo	Objeto asignado
miespacio::mifuncion	externo
main	{ puts("Esta función está en programa_parte2.c"); miespacio::mifuncion(); }

De esta manera no hay relación entre la ubicación del módulo en el sistema de ficheros y los espacios de nombre que contiene. Esto es importante porque ahora podemos mover el módulo de lugar dentro del disco y no hay que modificar el código fuente.

Semántica natural de LISP - parte 2 - LISP imperativo

2011-11-10T16:23:00.000+01:00

En la primera parte de esta serie homenaje a John McCarthy vimos una semántica de LISP sin permitir la modificación ni de los valores ni de las vinculaciones. Era un LISP funcional. En esta parte vamos a introducir esa posibilidad. Es por tanto un LISP imperativo.

La memoria y los contextos

En el momento que introducimos cambios, hemos de manejar estados. El estado con el que trabajaremos será la memoria [$M$]. Esta memoria será el conjunto libremente generado por [$$M::= \emptyset \mid M,m\Leftarrow c$$] Los identificadores [$m$] son las direcciones de memoria y los objetos sintácticos [$c$] son las celdas con el contenido de esa dirección. Veremos la sintaxis de las celdas más abajo.

Usaremos también los identificadores [$E$] como sinónimos a [$m$]. No son una nueva categoría, son la misma categoría sintáctica. Simplemente, vamos a usar [$E$] cuando hablemos de posiciones de memoria que guardan entornos. Esto nos hará mucho más legibles las ecuaciones y reglas a continuación.

Si bien recuerda el lector de la primera parte, esta definición de [$M$] es muy similar a la definición de contexto [$C$] que teníamos. Esta vez, nuestro contexto no podrá tener valores porque todo hemos de guardarlo en la memoria para que pueda ser modificado. Así pues, nuestro contexto ahora será [$$C::=\emptyset \mid C,x\leftarrow m$$] Donde [$x$] son los identificadores de variable.

Operaciones sobre memoria y contextos

Debido a la similitud entre la sintaxis de memoria y contexto, vamos a dar sus operaciones a la vez. La primera operación es el dominio que nos indica qué posiciones de memoria o qué identificadores de variable están en uso.

En primer lugar, la memoria vacía o el contexto vacío tienen un dominio vacío.

[$$dom(\emptyset)=\emptyset$$]

Para continuar, el dominio de la memoria o el contexto más una asignación de memoria o vinculación de variable se calcula recursivamente.

[$$dom(M,m\Leftarrow c)=dom(M)\cup\{m\}$$]

[$$dom(C,x\leftarrow m)=dom(C)\cup\{x\}$$]

La siguiente operación que vamos a especificar es la pertenencia a memoria o a contexto. El caso base es cuando la propia asignación o vinculación está en la parte más externa de la memoria o contexto.

[$$(m\Leftarrow c)\in(M,m\Leftarrow c)$$]

[$$ (x\leftarrow m)\in(M,x\leftarrow m) $$]

El caso recursivo ocurre cuando no se encuentra en esa posición externa.

[$$\frac{m\ne m'\;\;\;\;\;\; (m\Leftarrow c)\in M}{(m\Leftarrow c)\in(M,m'\Leftarrow c')}$$]

[$$\frac{x\ne x'\;\;\;\;\;\;(x\leftarrow c)\in C}{(x\leftarrow m)\in(C,x'\leftarrow m')}$$]

Finalmente, y dado que estamos hablando de mutaciones de memoria, tendremos que introducir las operaciones de cambio de memoria y de contexto. Es similar a la pertenencia, pero con una comprobación extra por si la dirección de memoria o variable que queremos modificar no está usada y, por tanto, hay que añadirla. Empecemos por esta regla extra.

[$$\frac{m\notin dom(M)}{M\langle m\Leftarrow c\rangle=M,m\Leftarrow c}$$]

[$$ \frac{x\notin dom(C)}{C\langle x\leftarrow m\rangle=C,x\leftarrow m}$$]

Cuando lo que queremos cambiar sí está en el dominio, hemos de buscarlo y cambiarlo.

[$$(M,m\Leftarrow c) \langle m\Leftarrow c'\rangle= (M,m\Leftarrow c') $$]	[$$ (M,x\leftarrow m) \langle x\leftarrow m'\rangle = (M,x\leftarrow m') $$]
[$$\frac{m\ne m'\;\;\;\;\;\; m' \in dom(M)}{ (M,m\Leftarrow c)\langle m'\Leftarrow c' \rangle = (M \langle m'\Leftarrow c' \rangle ,m\Leftarrow c) }$$]	[$$\frac{x\ne x'\;\;\;\;\;\; x'\in dom(C)}{(C,x\leftarrow m)\langle x'\leftarrow m'\rangle = (C \langle x'\leftarrow m'\rangle ,x\leftarrow m) }$$]

Celdas y entornos

Las celdas van a contener los valores del LISP funcional. Además, dado que las vinculaciones de variables van a poder ser modificadas, también vamos a introducir en ellas a los contextos. Su sintaxis es la que sigue [$$c::= l \mid x \mid (m.m) \mid \lambda^Emm \mid |p| \mid C $$] Es decir, que una celda podrá ser o bien un literal [$l$], o bien una variable [$x$], o bien un par [$(m.m)$], o bien una clausura [$\lambda^Emm$], o bien un valor predefinido [$|p|$], o bien un contexto [$C$]. Recordemos que la [$E$] no es más que una dirección de memoria como las [$m$].

Dentro de los literales incluimos la lista vacía que escribiremos [$()$]. Una lista de contextos es un entorno. La operación más importante en los entornos es la búsqueda de la vinculación de una variable. Lo haremos buscando en el contexto en posición de cabeza de la lista y luego, si no se encuentra, usando la recursión en el resto de la lista. Bastan dos reglas para realizar este procedimiento.

[$$\frac{E\Leftarrow(m'.E')\in M\;\;\;\;\;\;m'\Leftarrow C\in M\;\;\;\;\;\;x\leftarrow m\in C}{x\leftarrow m\in_M E}$$]

[$$\frac{ E\Leftarrow(m'.E')\in M\;\;\;\;\;\;m'\Leftarrow C\in M\;\;\;\;\;\;x\leftarrow m\notin C \;\;\;\;\;\; x \leftarrow m \in_M E' }{ x\leftarrow m\in_M E }$$]

Las dos reglas de arriba son muy similares. Primero, en ambas reglas, se comprueba que la dirección de memoria [$E$] sea un par y que su primer campo [$m'$] apunte a un contexto [$C$]. Luego, si encontramos la variable en [$C$], ahí está (primera regla) y, si no la encontramos, buscamos en el resto de la lista [$E'$] que es el llamado entorno padre (segunda regla).

Otra operación muy simple, y que más que nada es una abreviatura, es la introducción de un nuevo contexto en un entorno.[$$\frac{m' \notin dom(M)\cup\{m\}}{M\triangleright E\Leftarrow C\mid E' \triangleright M,m'\Leftarrow C, E\Leftarrow (m',E')}$$] Para empezar, usaremos [$M\triangleright$] a la izquierda y [$\triangleright M'$] a la derecha de un juicio cuando quiera indicar que la memoria [$M$] se cambia y como resultado obtenemos la memoria [$M'$]. En este caso, leemos el consecuente como "dada la memoria [$M$], obtengo el entorno [$E$] al introducir un nuevo contexto [$C$] en el entorno padre [$E'$] y la memoria con estos cambios es todo lo que hay a la derecha del [$\triangleright$]".

Relaciones auxiliares de evaluación

En la primera parte introdujimos un par de relaciones auxiliares de evaluación: la desestructuración o ajuste de patrones y el envoltorio. Hemos de adaptar ambas a la introducción de la memoria. Ahora hemos de explorar la memoria en vez de explorar valores. Todo esto hace las reglas un poco más largas, pero en el fondo son exactamente las mismas.

El ajuste de patrones sigue teniendo tres reglas: para literales (la llamaremos P-LIT), para variables (P-VAR) y para pares (P-PAIR).

[$$\frac{m\Leftarrow l\in M\;\;\;\;\;\;m'\Leftarrow l\in M}{C\{m\mid m'\}_M=C}$$]

[$$\frac{m\Leftarrow x\in M\;\;\;\;\;\; x\notin dom(C)}{C\{m\mid m'\}_M=(C,x\leftarrow m')}$$]

[$$\frac{m\Leftarrow (m_1.m_2)\in M\;\;\;\;\;\;m'\Leftarrow (m'_1.m'_2)\in M}{C\{m\mid m'\}_M= C\{m_1\mid m'_1\}_M \{m_2\mid m'_2\}_M }$$]

El envoltorio sigue teniendo sus dos reglas: para la lista vacía (la llamaremos W-EMPTY) y para el par (W-PAIR). Esta vez se complica un poco más porque hemos de acarrear las memorias de una evaluación a la siguiente. De esta forma los cambios en la primera evaluación afectan a la segunda evaluación.

[$$\frac{m\Leftarrow ()\in M}{M\triangleright E \vdash m \Downarrow m \triangleright M}$$]

[$$\frac{m\Leftarrow (m_1.m_2)\in M\;\;\;\;\;\; M\triangleright E \vdash m_1 \downarrow m_1' \triangleright M_1 \;\;\;\;\;\; M_1\triangleright E \vdash m_2 \Downarrow m_2' \triangleright M_2 \;\;\;\;\;\;\; m' \notin dom(M_2) }{ M\triangleright E \vdash m \Downarrow m' \triangleright M_2,m'\Leftarrow(m'_1.m'_2) } $$]

En definitiva, lo que hace el envoltorio es evaluar los operandos para obtener los argumentos. En el proceso crea una lista de argumentos.

La evaluación

Ya tenemos todo lo necesario para la evaluación. Es exactamente igual que la evaluación en la versión funcional sólo que acarreando memorias de una evaluación a la siguiente y usando entornos en vez de contextos.

[$$\frac{m\Leftarrow l\in M}{M\triangleright E\vdash m\downarrow m \triangleright M}$$]

La primera regla, que sigue siendo E-LIT, mira lo que hay en la dirección de memoria [$m$] y, si es un literal [$l$], devuelve la propia dirección de memoria como su resultado. Eso significa que el resultado de evaluar un literal es él mismo.

[$$ \frac{m\Leftarrow x\in M\;\;\;\;\;\; x\leftarrow m'\in_M E}{M\triangleright E \vdash m \downarrow m' \triangleright M} $$]

Esta segunda regla, E-VAR, mira lo que hay en la dirección de memoria y, si es una variable [$x$], busca su vinculación [$m'$] en el entorno [$E$] y devuelve esa vinculación. En ninguna de estas dos reglas se modifica la memoria.

[$$ \frac{\begin{array}{c}m\Leftarrow(m_1.m_2)\in M\;\;\;\;\;\;M\triangleright E\vdash m_1 \downarrow m'_1 \triangleright M_1 \;\;\;\;\;\; m'_1 \Leftarrow |p|\in M_1 \\ M_1 \triangleright E \vdash |p|m_2 \rightarrow_\delta m'_2 \triangleright M' \end{array}}{ M\triangleright E \vdash m \downarrow m' \triangleright M' } $$]

La regla E-PRE, que trata con los valores predefinidos, es algo más compleja. Primero, la regla observa que [$m$] apunta a un par [$(m_1.m_2)$] en la memoria. Eso significa que hay una combinación y hemos de evaluarla. Evalúa el operador [$m_1$] y observa que su resultado [$m'_1$] apunta a un valor predefinido [$|p|$]. Además, hemos modificado la memoria al evaluar el operador y hemos de buscar en [$M_1$]. Una vez que sabemos que es un valor predefinido, delegamos toda evaluación a la relación delta [$\rightarrow_\delta$] que se encarga de los valores predefinidos. La especificaremos más adelante.

[$$ \frac{ \begin{array}{c}m\Leftarrow(m_1.m_2)\in M\;\;\;\;\;\;M\triangleright E\vdash m_1 \downarrow m'_1 \triangleright M_1 \;\;\;\;\;\; m'_1 \Leftarrow \lambda^{E_c}m_f m_b\in M_1 \\ M_1 \triangleright E \vdash m_2 \Downarrow m'_2 \triangleright M_2 \;\;\;\;\;\; M_2 \triangleright E' \Leftarrow \emptyset\{m_f \mid m'_2 \}_{M_2} \mid E_c \triangleright M_3 \;\;\;\;\;\; M_3 \triangleright E' \vdash m_b \downarrow m' \triangleright M' \end{array}}{ M\triangleright E \vdash m \downarrow m' \triangleright M' } $$]

La última regla, E-APP, es la más compleja y usa prácticamente todas las relaciones auxiliares vistas hasta ahora. Explicaremos lo que hace paso a paso:

Los tres primeros antecedentes son exactamente iguales que los de la regla E-PRE. Es decir, comprobamos que es un par, evaluamos el primer componente y descubrimos que es, en este caso, una clausura con entorno de clausura en la dirección de memoria [$E_c$] con parámetros formales en la dirección de memoria [$m_f$] y el código a ejecutar en la dirección de memoria [$m_b$].
A continuación, evaluamos los operandos para obtener los argumentos. Esto es justamente lo que hace la relación de envoltorio. Es el primer antecedente de la segunda fila.
Una vez que tenemos los argumentos, usamos ajuste de patrones para generar un contexto en el cual estén vinculadas las variables de los parámetros formales [$m_f$] a los argumentos [$m'_2$]. Esta parte es [$\emptyset\{m_f\mid m'_2\}_{M_2}$].
Luego, ese contexto se introduce en un nuevo entorno [$E'$] usando como entorno padre el [$E_c$] para obtener la memoria [$M_3$]. Es lo que hace [$ M_2 \triangleright E' \Leftarrow \emptyset\{m_f \mid m'_2 \}_{M_2} \mid E_c \triangleright M_3 $]
Entonces, tenemos en la dirección de memoria [$E'$] el entorno donde evaluar el cuerpo de la clausura y obtener el resultado [$m'$] junto con la memoria final [$M'$]. Es lo que hace el último antecedente.

Para ver cómo funciona todo esto, haremos un ejemplo de evaluación.

Ejemplo de evaluación

Aunque va a ser un ejemplo muy simple, la memoria va a estar bastante llena. Para no liarnos voy a usar como identificadores de memoria los valores de la semántica funcional entre corchetes. De esta forma entendemos mejor qué hay en la dirección de memoria [$m_4$] si en vez de escribir [$m_4$] escribo [$[\lambda^{C_0}((x.y))x]$].

Entonces, nuestra memoria [$M_0$] va a ser la siguiente.

[$[C_0]$]	[$\Leftarrow$]	[$list\leftarrow [\lambda^{(C_0)}xx], car\leftarrow [\lambda^{(C_0)}((x.y))x] $]
[$ [\lambda^{(C_0)}xx] $]	[$\Leftarrow$]	[$ \lambda^{[(C_0)]}[x][x]$]
[$ [x] $]	[$\Leftarrow$]	[$x$]
[$ [\lambda^{(C_0)}((x.y))x] $]	[$\Leftarrow$]	[$\lambda^{[(C_0)]}[((x.y))][x]$]
[$ [((x.y))] $]	[$\Leftarrow$]	[$([(x.y)].[()])$]
[$ [(x.y)] $]	[$\Leftarrow$]	[$([x].[y])$]
[$ [y] $]	[$\Leftarrow$]	[$y$]
[$ [(car\ (list\ 1\ 2))] $]	[$\Leftarrow$]	[$([car].[((list\ 1\ 2))])$]
[$ [car] $]	[$\Leftarrow$]	[$car$]
[$ [((list\ 1\ 2))] $]	[$\Leftarrow$]	[$([(list\ 1\ 2)].[()])$]
[$ [(list\ 1\ 2)] $]	[$\Leftarrow$]	[$([list].[(1\ 2)])$]
[$ [()] $]	[$\Leftarrow$]	[$()$]
[$ [list] $]	[$\Leftarrow$]	[$list$]
[$ [(1\ 2)] $]	[$\Leftarrow$]	[$([1].[(2)])$]
[$ [1] $]	[$\Leftarrow$]	[$1$]
[$ [(2)] $]	[$\Leftarrow$]	[$([2].[()])$]
[$ [2] $]	[$\Leftarrow$]	[$2$]
[$ [(C_0)] $]	[$\Leftarrow$]	[$([C_0].[()])$]

Ahora vamos a querer evaluar la dirección de memoria [$m=[(car\ (list\ 1\ 2))]$] en el entorno [$E_0=[(C_0)]$] y usando la memoria [$M_0$]. Necesitaremos hallar los interrogantes de [$$ M_0\triangleright E_0 \vdash m \downarrow\ ????\ \triangleright\ ????$$] Deberemos proceder con la regla E-APP en la cual encontramos que [$[(car\ (list\ 1\ 2))]\Leftarrow ([car].[((list\ 1\ 2))])\in M_0$] Entonces, [$m_1=[car]$] y hemos de evaluar [$$ M_0 \triangleright E_0 \vdash m_1 \downarrow\ ????\ \triangleright\ ????$$] Hay que aplicar la regla E-VAR en la cual obtenemos como resultado la dirección de memoria [$[\lambda^{(C_0)}((x.y))(x)]$].

A continuación hemos de realizar el envoltorio. Aparcamos E-APP(car). Ahora, como [$[((list\ 1\ 2))]\Leftarrow ([(list\ 1\ 2).[()]) \in M_0$] es un par, hay que entrar en W-PAIR. Nos dice que evaluemos el primer componente del par que es[$[(list\ 1\ 2)]$]. Tendremos que usar E-APP otra vez.

Aparcamos W-PAIR(car) y E-APP(car) para entrar en E-APP(list). Como [$[(list\ 1\ 2)]\Leftarrow ([list].[(1\ 2)]) \in M_0$], la regla E-APP me dice que evalúe el primer componente del par. En este caso [$[list]$]. Aplicando E-VAR obtenemos que el resultado es la celda [$\lambda^{[(C_0)]}[x][x]$] y tengo que entrar en envoltorio otra vez.

Tenemos en suspenso E-APP(list), W-PAIR(car) y E-APP(car). Y estamos trabajando con W-PAIR para envolver [$[(1\ 2)]\Leftarrow ([1].[(2)])\in M_0$]. Esta regla me dice que evalúe el primer componente que por E-LIT es él mismo [$[1]$] y que vuelva a aplicar el envoltorio sobre el segundo componente [$[(2)]$]. Aparco este W-PAIR(1) y voy con W-PAIR otra vez.

En este punto están en suspenso W-PAIR(1), E-APP(list), W-PAIR(car) y E-APP(car). Seguimos trabajando con la memoria [$M_0$] y hemos de aplicar W-PAIR a [$[(2)]\Leftarrow ([2].[()])\in M_0$]. El resultado es que [$[2]$] se evalúa por E-LIT a él mismo y W-EMPTY me devuelve el propio [$[()]$].

Ahora ocurre una cosa muy importante. La regla W-PAIR modifica la memoria. Añade un par en una nueva dirección. El primer componente del par es el resultado de la evaluación del primer componente, que era [$[2]$] y el segundo, el del envoltorio, que era [$[()]$]. Entonces, mi nueva memoria será [$$M_1=M_0,m_0\Leftarrow ([2].[()])$$] y el resultado de W-PAIR es [$$ M_0 \triangleright E_0 \vdash [(2)] \Downarrow m_0 \triangleright M_1$$] Este cambio de memoria es importante porque ahora recuperamos W-PAIR(1) y usa [$M_1$] en vez de [$M_0$].

Nota: Escribo [$m_0$] en vez de [$[(2)]$] porque [$[(2)]$] ya está usado en [$M_0$] y se confundiría. Tenemos dos celdas con el mismo contenido en memoria.

Retomamos W_PAIR(1) y sigue en suspenso E-APP(list), W-PAIR(car) y E-APP(car). La regla W_PAIR vuelve a modificar la memoria. En este caso [$$M_2=M_1,m_1\Leftarrow ([1].m_0)$$] y lo que hemos demostrado es [$$ M_0 \triangleright E_0 \vdash [(1\ 2)] \Downarrow m_1 \triangleright M_2$$].

Retomamos E-APP(list) y sigue en suspenso W-PAIR(car) y E-APP(car). El siguiente antecedente de la regla E-APP es el que realiza el ajuste de patrones. En este caso hemos de ajustar [$\emptyset\{[x]\mid m_2\}_{M_2}$]. Es sencillo usando la regla P-VAR. El ajuste devuelve el contexto [$C_1=x\leftarrow m_2$].

A continuación, la regla E-APP introduce el nuevo contexto [$C_1$] en la memoria. La nueva memoria es [$$M_3=M_2, [C_1]\Leftarrow C_1, [(C_1 C_0)]\Leftarrow ([C_1].[(C_0)]$$] y el nuevo entorno está en [$[(C_1 C_0)]$]. En este nuevo entorno y con esta nueva memoria evaluamos el cuerpo de la clausura que era [$[x]$]. Usamos para ello la regla E-VAR y encontramos que [$x\leftarrow m_2 \in_{M_3} [(C_1 C_2)]$] por lo que el resultado es [$m_2$] con la propia memoria [$M_3$]. Entonces lo que hemos demostrado hasta ahora es que [$$ M_0 \triangleright E_0 \vdash [(list\ 1\ 2)] \downarrow m_2 \triangleright M_3 $$]

Retomemos W-PAIR(car) y mantengamos en suspenso E-APP(car). La regla W-PAIR, tras evaluar el primer componente del par, envuelve el segundo. Usando la regla W-EMPTY obtenemos [$[()]$] como resultado de este envoltorio. A continuación, modifica la memoria incluyendo un nuevo par en [$m_3$] con ambos resultados. Es decir que [$M_4=M_2,m_3\Leftarrow (m_2.[()])$] y hemos demostrado que [$$ M_0 \triangleright E_0 \vdash [((list\ 1\ 2))] \Downarrow m_3 \triangleright M_4$$]

Retomamos, por fin, E-APP(car). Hemos de realizar primero el ajuste de patrones en el cual obtenemos el contexto [$C_2=x\leftarrow [1],y\leftarrow m_1$]. Luego, incluimos un nuevo entorno en la memoria con ese contexto y con entorno padre el de la clausura. [$$M_5=M_4, [C_2]\Leftarrow C_2, [(C_2 C_0)]\Leftarrow ([C_2].[(C_0)])$$] Y, finalmente, evaluamos el cuerpo de la clausura. Es sencillo porque consta únicamente de una variable y aplicamos E-VAR. Demostramos, por fin, que [$$M_0 \triangleright E_0 \vdash [(car\ (list\ 1\ 2))] \downarrow [1] \triangleright M_5$$]

Valores predefinidos y formas especiales

Especificaremos muy pocas formas predefinidas. La más usual en un lenguaje imperativo es la evaluación en secuencia. Usaremos el valor predefinido [$|begin|$] para esta evaluación. Necesitamos tres reglas. La primera dice que la evaluación en secuencia de la lista vacía es la propia lista vacía.[$$\frac{m\Leftarrow ()\in M}{M\triangleright E \vdash |begin|m \rightarrow_\delta m \triangleright M}$$] La segunda regla indica que si la lista a evaluar en secuencia sólo tiene un elemento, el resultado es la evaluación de ese elemento. [$$\frac{m\Leftarrow (m_1.m_2)\in M \;\;\;\;\;\; m_2\Leftarrow () \in M \;\;\;\;\;\; M \triangleright E \vdash m_1 \downarrow m' \triangleright M'}{M\triangleright E \vdash m \rightarrow_\delta m' \triangleright M'}$$]Finalmente, si hay más de un elemento, evaluamos el primero y evaluamos en secuencia el resto.[$$\frac{m\Leftarrow (m_1.m_2)\in M \;\;\;\;\;\; m_2\Leftarrow () \notin M \;\;\;\;\;\; M \triangleright E \vdash m_1 \downarrow m'_1 \triangleright M_1 \;\;\;\;\;\; M_1 \triangleright E \vdash |begin|m_2 \rightarrow_\delta m' \triangleright M'}{M\triangleright E \vdash m \rightarrow_\delta m' \triangleright M'}$$]

Para definir una vinculación usamos el valor predefinido [$|def!|$].[$$\frac{m\Leftarrow (m_1.m_2) \in M \;\;\;\;\;\; m_1 \Leftarrow x \in M \;\;\;\;\;\; M \triangleright E \vdash |begin|m_2 \rightarrow_\delta m' \triangleright M'}{ M\triangleright E \vdash |def!|m \rightarrow_\delta m' \triangleright M' \langle E \Leftarrow x \leftarrow m'\rangle}$$] La relación auxiliar [$M \langle E \Leftarrow x \leftarrow m\rangle$] es la que realmente modifica la memoria con la nueva definición.[$$\frac{E\Leftarrow (m_1.E_2)\in M \;\;\;\;\;\; m_1 \Leftarrow C \in M}{M \langle E \Leftarrow x \leftarrow m\rangle = M\langle M_1 \Leftarrow C \langle x \leftarrow m \rangle \rangle}$$]

Es posible definir el valor predefinido [$|set!|$] que modifica una vinculación preexistente. La dificultad de esta definición estriba en hacerla recursiva (hacia el entorno padre) si no se halla la variable a modificar en el contexto actual.

El combinador Y en C++ (y II)

2011-10-28T13:02:00.001+02:00

La primera parte de esta serie está aquí.

Como se comentó en la primera parte, el combinador Y toma una función g que representa un paso de recursión y devuelve una función p que es el punto fijo de g. Esto del punto fijo no es más que la función recursiva obtenida aplicando g a sí misma infinitas veces. El problema con este planteamiento es que currificar en C++ es difícil. Por esta razón usaremos una versión de g que no esté currificada. El prototipo de esta función sería:

#include <functional>

int g(std::function<int(int)> f,int v);

El tipo de los objetos función en C++ es muy largo y escribir "std::function" cada vez va a emborronar el código. Usaré una macro para aligerar la notación.

#include <functional>

//F(X,Y) es X->Y
#define F(X,Y) std::function<Y(X)>

//F(X,Y,Z) es (X,Y)->Z
#define F2(X,Y,Z) std::function&lg;Z(X,Y)>

int g(F(int,int) f,int v);

Ahora vamos a tratar de definir el combinador Y. La mejor forma de hacerlo es, en vez de usar las funciones lambda de C++ que son muy tediosas, usando la ecuación recursiva que obtuvimos en la primera parte.

Y(g)=g(Y(g))

Como ahora tengo a g sin currificar, he de añadir un argumento extra. Queda así:

Y(g)=[](x){g(Y(g),x)}

Entonces, el código del combinador Y para los enteros sería

F(int,int) Y(  F2( F(int,int) ,int,int)  f)
{
    return [=](int x){return f(Y(f),x);};
}

Realmente la parte difícil es la de los tipos, aunque se pueden obtener poco a poco estudiando la expresión.

Cambiar los int por un tipo genérico nos da el combinador Y genérico en C++:

template<typename T>
F(T,T) Y(  F2( F(T,T) ,T,T)  f)
{
    return [=](T x){return f(Y(f),x);};
}

Ahora sólo tenemos que usarlo. Definimos para eso la función g del factorial y lo volcamos a la salida. El código final es el que sigue:

#include <functional>

#include <iostream>

//F(X,Y) es X->Y
#define F(X,Y) std::function<Y(X)>
 

//F(X,Y,Z) es (X,Y)->Z
#define F2(X,Y,Z) std::function&lg;Z(X,Y)>

int g(F(int,int) f,int v)
{
    return v==0 ? 1 : v * f(v-1);
}

template<typename T>
F(T,T) Y(  F2( F(T,T) ,T,T)  f)
{
    return [=](T x){return f(Y(f),x);};
}

int main(int argc,char** argv)
{
std::cout << Y<int>(g)(5) << std::endl;
    return 0;
}

En este punto sólo queda advertir al lector que es necesario usar un compilador compatible con el estándar de C++ de 2011.

Semántica natural de LISP - parte 1 - LISP funcional

2011-10-27T13:12:00.004+02:00

Como homenaje a McCarthy, voy a dedicar una serie de posts a descubrir la semántica natural del LISP. Empezaremos por un LISP reducido que llamaré LISP funcional en el cual no hay mutaciones de las vinculaciones de variables. Cualquiera que haya leído el SICP reconocerá que ésto se corresponde a la primera parte del libro.

La semántica natural o semántica de paso grande no es más que una relación que a cada programa [$t$] en un contexto [$C$] le proporciona un valor [$v$]. Escribiremos esta relación así [$$C \vdash t \downarrow v$$] y se lee "[$t$] se evalúa a [$v$] bajo el contexto [$C$]". Aunque antes debemos especificar claramente cuáles son las estructuras sintácticas que forman [$t$], [$C$] y [$v$].

Sintaxis

La sintaxis de los programas son términos [$t$] que son a su vez, o bien una variable [$x$], o bien un literal [$l$], o bien un par de términos [$(t.t)$]. Esto se escribe así: [$$t ::= x \mid l \mid ( t . t )$$] Dentro de los literales incluimos la lista vacía [$()$] que permite, junto con el par, formar listas. Una lista [$(1 2 3)$] es realmente [$(1.(2.(3.())))$]. Es decir, el primer componente del par es el término que está en la cabeza de la lista y el segundo componente es otra lista que representa al resto de los términos. Es común llamar a estos componentes "head" y "tail" (cabeza y cola en inglés) o "car" y "cdr". Estos dos últimos nombres tienen una historia más larga.

Los literales son símbolos como [$1, 53, "hola",$] etc. que tienen un valor en sí mismos. Las variables son símbolos como [$x, y, z,$] etc. que requieren un contexto para saber el valor que representan.

La sintaxis de los valores [$v$] es o bien un término [$t$], o bien una clausura [$\lambda ^C t t$], o bien una forma predefinida [$|p|$]. [$$v::=t\mid \lambda^C tt \mid |p|$$] Escribiremos las formas predefinidas entre barras para distinguirlas de las variables y literales, aunque el símbolo que sea [$p$] puede coincidir con ellos.

Los contextos no son más que una colección de vinculaciones de valores a variables.[$$ C::= \emptyset \mid C,x\leftarrow v$$] Construímos los contextos con el contexto vacío [$\emptyset$] al que le vamos agregando vinculaciones de la forma [$x\leftarrow v$]. Aunque la forma correcta de escribir un contexto sea [$\emptyset, x \leftarrow 5, y \leftarrow 8$], omitiremos el [$\emptyset$].

Operaciones sobre contextos

Vamos a necesitar un par de operaciones para trabajar con los contextos. Son muy simples. La primera es el dominio del contexto [$dom\ C$] que nos dice qué variables se han usado en un contexto. [$$ dom\ \emptyset = \emptyset $$][$$ dom(C,x\leftarrow v)=dom(C)\cup\{x\}$$]

La segunda operación busca una variable en un contexto. Lo escribiremos como una relación de pertenencia [$x\leftarrow v \in C$] para simplificar la lectura. [$$x\leftarrow v\in C,x\leftarrow v$$][$$\frac{x\ne x'\;\;\;\;\;\;x\leftarrow v\in C}{x\leftarrow v\in C,x'\leftarrow v'}$$]La primera línea es una regla tan obvia que lo mismo es difícil de entender: [$x\leftarrow v$] pertenece a [$C,x\leftarrow v$]. La segunda regla dice que [$x\leftarrow v$] pertenece a [$C,x'\leftarrow v'$] si [$x$] es distinta a [$x'$] y [$x\leftarrow v$] pertenece a [$C$]. Si llega un momento que [$C=\emptyset$], no podremos usar ninguna de las dos reglas (y por tanto [$x\leftarrow v$] no pertenecerá).

Ajuste de patrones

Llegará un momento en la evaluación en el cual tendremos que relacionar argumentos con parámetros. La forma más inteligente de hacerlo es usando el ajuste de patrones, también llamado asignación desestructurante. El ajuste de patrones que vamos a ver aquí es muy simple: toma un término y un valor, devolviendo las vinculaciones que deberían tener las variables del término para que se ajuste al valor proporcionado. Por ejemplo. Si quiero ajustar [$x$] y [$3$], lo escribiré así [$\{x\mid 3\}$] y el resultado será que la variable [$x$] ha de vincularse al valor [$3$]. Esta vinculación es la que hemos escrito [$x\leftarrow 3$] en los contextos. Como no tenemos contexto al que añadir la vinculación, lo incluiremos en nuestro ajsute de patrones. El resultado es que el ajuste de patrones es una relación [$C\{t\mid v\}=C$]. El ejemplo de arriba se podría completar entonces con [$$z\leftarrow 8\;\{x\mid 3\}=z\leftarrow 8,x\leftarrow 3$$]Más ejemplos serían [$$z\leftarrow 8\;\{(x\; y)\mid (3\;7)\}= z\leftarrow 8,x\leftarrow 3,y\leftarrow 7$$][$$\emptyset\{(x y. z)\mid(1 \; (2 \; 3) \; 4 \; 5 \; 6)\}=x\leftarrow 1,y\leftarrow(2\;3), z\leftarrow(4 \;5 \; 6)$$][$$x\leftarrow 5\{x\mid 5\}=???$$] En el último ejemplo no es posible calcular el ajuste de patrones porque [$x$] ya está definida. ¡Incluso si le vamos a dar el mismo valor! De esta manera cada contexto sólo tendrá una única aparición de cada variable.

Las reglas del ajuste de patrones son muy sencillas. En primer lugar, la regla D-LIT dice que los literales han de coincidir.[$$C\{l\mid l\}=C$$] La regla D-VAR modifica el contexto vinculando la variable, que no está definida previamente, al valor.[$$\frac{x\notin C}{C\{x\mid v\}=C,x\leftarrow v}$$] Finalmente, la regla D-PAIR es meramente estructural.[$$C\{(t_1.t_2)\mid(v_1.v_2)\}=C\{t_1\mid v_1\}\{t_2\mid v_2\}$$]

La evaluación

Llega la hora de dar la relación de evaluación [$C \vdash t \downarrow v$] que antes mencionábamos. Son cuatro reglas. La primera, que llamaremos E-LIT, es para saber el valor de un literal. Es muy sencillo porque es él mismo. [$$C \vdash l \downarrow l$$] La segunda (E-VAR) es para saber el valor de una variable. Necesitamos consultar el contexto.[$$\frac{x\leftarrow v \in C}{C \vdash x\downarrow v}$$] La tercera la usaremos para pares cuya cabeza se evalúe a un valor por predefinido. La llamaremos E-PRE. [$$\frac{C\vdash t_0 \downarrow |p| \;\;\;\;\;\; C\vdash (|p| t_1 \cdots t_n) \rightarrow_\delta v}{C\vdash (t_0 t_1 \cdots t_n)\downarrow v}$$] Aquí hemos usado una relación auxiliar [$C\vdash v\rightarrow_\delta v$] en la que introduciremos la semántica de los valores predefinidos (ver más abajo). Finalmente, la regla E-APP, formaliza el uso de una clausura.[$$\frac{C\vdash t_0 \downarrow \lambda^{C'}t't'' \;\;\;\;\;\; C\vdash (t_1 \cdots t_n) \Downarrow (v_1 \cdots v_n) \;\;\;\;\;\; C' \{ t' \mid (v_1 \cdots v_n) \}\vdash t''\downarrow v}{C\vdash (t_0 t_1 \cdots t_n) \downarrow v}$$] Hemos usado el ajuste de patrones en el último antecedente (a la derecha del todo.) También hemos usado una relación auxiliar [$ C\vdash (t_1 \cdots t_n) \Downarrow (v_1 \cdots v_n) $] que llamaremos de "envoltorio" que lo único que hace es evaluar una lista de términos, término a término, para obtener una lista de valores.

Las reglas de esta relación auxiliar de envoltorio son muy simples. Primero, la lista vacía se envuelve a sí misma. [$$C\vdash () \Downarrow ()$$] Y segundo, un par evalúa su cabeza y envuelve el resto. [$$\frac{C\vdash t_1 \downarrow v_1 \;\;\;\;\;\; C\vdash t_2 \Downarrow v_2}{C \vdash (t_1.t_2) \Downarrow (v_1.v_2)}$$] En general podemos ver la relación de envoltorio como una abreviatura de
[$$C\vdash t_1 \downarrow v_1 \;\;\;\;\;\; C\vdash t_2 \downarrow v_2 \;\;\;\;\;\; \cdots \;\;\;\;\;\; C\vdash t_n \downarrow v_n $$] que escribimos [$$ C\vdash (t_1t_2\cdots t_n) \Downarrow (v_1v_2\cdots v_n)$$]

Formas predefinidas

Las formas predefinidas nos pueden servir para trabajar con los literales. Por ejemplo, la suma se puede formalizar así (llamaremos a esta regla P-ADD): [$$\frac{C\vdash (t_1 \cdots t_n)\Downarrow (N_1 \cdots N_n) }{ C\vdash (|+| t_1 \cdots t_n)\rightarrow_\delta \sum_{k=1}^n{N_k} }$$] Donde los [$N$] mayúsculas han de ser literales de número como el [$3$] o el [$75.82$].

Entre todas las formas es especialmente importante la que genera clausuras. Llamaremos a este valor predefinido[$|\lambda|$] y se define con la regla P-LAMBDA [$$C\vdash (|\lambda| t_1 t_2) \rightarrow_\delta \lambda^Ct_1 t_2 $$] Con esta forma especial podemos definir funciones.

Ejemplos de evaluación

Si usamos un contexto inicial [$$C_0 = lambda \leftarrow |\lambda|, +\leftarrow |+|$$] tenemos suficiente potencia expresiva para calcular el doble de [$3$] (realmente, con lambda y usando la codificación de Church, tenemos la potencia expresiva de un modelo computacional Turing completo). Me he tomado algunas libertades para simplificar la derivación (no he usado la abreviatura del envoltorio y le he dado nombres a los contextos). El resultado es el que sigue (clic para ampliar):

En el contexto inicial podemos incluir más definiciones. Algunas funciones típicas son:[$$car\leftarrow \lambda^{C_0}((x.y))x$$][$$cdr\leftarrow\lambda^{C_0}((x.y))y$$][$$list\leftarrow\lambda^{C_0}xx$$][$$cons\leftarrow\lambda^{C_0}(x y)(x.y)$$] Con este nuevo contexto inicial podemos calcular el segundo elemento de la lista [$(1 2 3)$]. La derivación (omitiendo ya nombres de reglas) es la que sigue:

Hasta aquí por hoy. En la siguiente parte de esta serie permitiremos mutaciones en la vinculación de las variables.

Muere John McCarthy

2011-10-25T13:43:00.000+02:00

Estamos teniendo un mes bastante triste en el mundo de la informática. Primero, muere el carismático Jobs, luego el creador del lenguaje C, Dennis Ritchie, y ayer murió John McCarthy el creador del LISP (en 1959) y casi todas las tecnologías asociadas a él, entre otras:

Recolección de basura
Tipado dinámico y estructuras arborescentes para datos
Homoiconicidad y expresiones S
Abstracción de punteros
Computación simbólica
REPLs
Autocompiladores
Modelo de evaluación por entornos

Además, leo que inventó la lógica no monótona por circunscripción. Esta lógica viene a decir más o menos que si no enciende el televisor, no enciende la tostadora, no enciende la nevera y no enciende la estufa, lo que fallan son los fusibles. Esto que parece una tontería es uno de los puntales en inteligencia artificial. Campo al que se dedicó en vida. Descanse en paz.

El extraño caso del disco duro resucitado

2011-10-22T11:16:00.000+02:00

Se me fastidió el disco duro. Es una lata perder varios gigas de información. Antiguamente, si se te rompía un floppy, tampoco era un trauma. Eran 1.44 MB. La cosa ha cambiado. En la actualidad, cualquier fallo se lleva gigas y gigas por delante.

Afortunadamente los discos duros suelen fallar por motivos mecánicos. Las piezas se van deformando poco a poco. Los encajes son cada vez menos perfectos. El rozamiento va limando lentamente las zonas de fricción. ¿Por qué digo afortunadamente? Porque los discos duros suelen empezar a hacer ruidos raros antes de dejar de funcionar definitivamente. El mío, particularmente, además de los ruidos raros, dejaba de responder y se reiniciaba.

Así que, al primer ruido raro que oí, apagué el ordenador, desconecté el disco duro físicamente y empecé a buscar sustituto. Tras unos días de espera por el pedido (hace años que las tiendas de informática no tienen casi nada en stock), procedí a instalar el nuevo disco. Cada vez que me compro un disco nuevo es más silencioso, se calienta menos y tiene más capacidad. Es maravilloso. Mientras no fallen, claro.

Ahora quedaba el lento traspaso de la información del disco a punto de romperse al disco nuevo. Es un proceso muy tenso, ya que en cualquier momento el disco termina por romperse y pierdes lo que no hayas copiado. Un pequeño truco que he descubierto para hacer la espera algo menos tensa es poner el disco a punto de romperse en una caja externa conectado por USB. De esta manera, el SO se comporta de otra forma cuando el disco deja de responder. Cuando el disco no es extraíble, el SO se queda bloqueado; pero cuando es extraíble, te pregunta por si quieres reintentar la lectura. Esto es maravilloso cuando, después de varios minutos de copia de un fichero de varios gigas, el disco duro se reinicia solo. Si no fuera por que está en modo extraíble se perdería la información. En modo extraíble esperas a que se reinicie y le dices que reintente. Continua por el mismo sector por donde lo dejó.

El adaptador USB para discos duros que tengo es uno barato que estaba de oferta. Tan barato era que, en medio del tenso traspaso de información, algo explotó dentro de la fuente de alimentación con el consiguiente olorcillo a electrónica tostada y el típico humillo blanco. En principio, no era problemático porque tengo la fuente del propio PC a la pude conectar el disco duro directamente. Con eso conseguí salvar el 80% de la información... hasta que el disco duro dejó de funcionar definitivamente.

Como fui astuto a la hora de volcar la información, el 20% restante estaba en DVDs y, tras una breve búsqueda entre los DVDs medio olvidados, tenía recuperado todo lo que había perdido. Menos mal.

Una vez tranquilizado, me dispuse a arreglar la fuente de alimentación del adaptador USB. No sé qué tipo de fusible le habían puesto porque se había volatilizado. Con él un diodo de los gordos, de tres amperios. Con ayuda de los esquemáticos encontrados en internet pude comprobar que todos los semiconductores del primario y la mitad del secundario estaban en corto. Por un par de euros conseguí recambios equivalentes en la tienda de electrónica local. Puse más fusibles, por si las moscas, y más ajustados al valor nominal. Enchufé la fuente y empezó a funcionar de nuevo.

Para probar la fuente qué podría haber mejor que el disco duro recién roto. Como el fallo era mecánico, el PC debería reconocerlo aunque no pudiera acceder a la información. Bastaría con eso para comprobar que la alimentación era correcta. Sin embargo, en cuanto enchufé la alimentación, olí de nuevo a electrónica algo tostada. Muy sutilmente esta vez. Apagué con rapidez y procedí a probar el disco duro con la fuente del PC para comprobar si había pasado, definitivamente, a mejor vida electrónica.

¡Y empezó a funcionar sin fallo alguno!

Pero, ¿cómo puede ser? Medí los voltajes que daba la fuente de alimentación y en vez de 5V daba 8V; en vez de 12V daba 18V. ¿Cómo puede ser? ¿Un calentón eléctrico repara un fallo mecánico? Imposible. Las explicaciones que me vienen a la mente son muy rebuscadas: que los motores estuvieran algo sucios y al calentarse han disuelto algo la porquería que los bloqueaba, que se haya quemado el circuito que detecta que hay un fallo mecánico y por eso ahora es feliz, que el sobrevoltaje haya forzado la pieza mecánica y la haya vuelto a colocar en su sitio... Muy improbable todo.

La cosa es que ese disco duro resucitado venía en una caja externa de Maxtor. Lo he vuelto a montar ahí y está funcionando. O parece que lo hace...

No me fío y nunca me fiaré.

Muere un grande de la informática

2011-10-13T18:23:00.000+02:00

Hace unos días murió Dennis Ritchie, uno de los creadores del lenguaje más usado en la breve historia de la informática: el lenguaje C. Fue un premio Turing y uno de los desarrolladores de UNIX. Como tantas veces, su muerte ha pasado desapercibida en los medios generalistas.

miniSL parte 16 - El código hasta ahora

2011-10-09T10:56:00.000+02:00

Como prometí en la última entrada de esta serie, aquí está el código que tenemos desarrollado hasta ahora. Ya llevamos 425 líneas de código. Más o menos la mitad de toda la implementación. Faltan por desarrollar el reconocimiento sintáctico, las funciones nativas y el REPL. Empezaremos en la siguiente entrada con el reconocimiento sintáctico.

//Standard includes
#include <string>
#include <map>
#include <deque>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>

//Forward declarations
class Script;
struct CELL;

//
// Type declarations
//

typedef std::wstring STRING;
typedef std::wistream ISTREAM;
typedef std::wostream OSTREAM;
typedef std::map<STRING, CELL*> STRING_MAP;
typedef std::map<CELL*, CELL*> ENVIR_TABLE;
typedef std::deque<CELL> CELL_STORAGE;
typedef CELL& (*NATIVE) (Script& script, CELL& args, CELL& envir);


//
// CELL STRUCTURE
//

enum CELL_TYPE
{
 UNUSED, 

 //Literals
 EMPTY_LIT, INT_LIT, STRING_LIT,

 //Value constructors
 LAMBDA_VAL, NATIVE_VAL, ENVIR_VAL, BOOL_VAL, 

 //Code constructors
 NAME_CODE, COMBINE_CODE,

 //Value and code constructors
 CONS_CTOR
};

struct CELL
{
 CELL_TYPE type;
 bool mark;      //Garbage collection mark
 union
 {
  CELL* next_unused;   //UNUSED
  int int_val;    //INT_LIT
  bool bool_val;    //BOOL_VAL
  STRING const* string_val; //STRING_LIT
  CELL* head;     //CONS.
  CELL* code;     //LAMBDA_VAL. The cell must be a CONS_CTOR with parameters and body
  NATIVE native;    //NATIVE_VAL
  ENVIR_TABLE* envir_table; //ENVIR_VAL
  CELL* op;     //COMBINE_CODE. The cell must be code (Any *_CODE type or CONS or EMPTY)
 };

 union
 {
  CELL* tail;   //CONS. Must be CONS or EMPTY.
  CELL* closure;  //LAMBDA_VAL. The cell must be an environment (ENVIR_VAL)
  CELL* parent_envir; //ENVIR_VAL. The pointer may be NULL or an environment cell (ENVIR_VAL)
  CELL* operands;  //COMBINE_CODE. The cell must be a list of code.
 };

 void Print(OSTREAM& o)const;
 void PrintList(OSTREAM& o, STRING const& separator)const;
 static void PrintEscapedString(OSTREAM& o, STRING const& s);

 int GetInteger()const   { if(type==INT_LIT) return int_val; else throw L"Integer expected"; }
 bool GetBoolean()const   { if(type==BOOL_VAL) return bool_val; else throw L"Boolean expected"; }
 STRING const& GetString()const { if(type==STRING_LIT) return *string_val; else throw L"String expected"; }
};

//
// SCRIPT CLASS
//

class Script
{
public:
 Script() : m_FirstUnused(NULL) { m_GlobalEnvir=&CreateEnvir(NULL); }
 ~Script() { GCSweep(); GCSweep(); } //Sweep twice to delete everything

 CELL& CreateCell(CELL_TYPE ct, CELL* first=NULL, CELL* second=NULL);
 CELL& CreateInteger(int val){ CELL& c=CreateCell(INT_LIT); c.int_val=val; return c; }
 CELL& CreateBool(bool val) { CELL& c=CreateCell(BOOL_VAL); c.bool_val=val; return c; }
 CELL& CreateString(STRING const& val);
 CELL& CreateName(STRING const& val);
 CELL& CreateEnvir(CELL* parent);
 CELL& CreateNative(NATIVE native);

 ENVIR_TABLE& GlobalEnvirTable()const { return *m_GlobalEnvir->envir_table; }
 void DefineUsualSymbols();

 void DefineGlobalNative(STRING const& name, NATIVE nat)
 {
  (*m_GlobalEnvir->envir_table)[&CreateName(name)]=&CreateNative(nat);
 }

 CELL& Evaluate(CELL& c, CELL& envir);
 CELL& EvaluateInSequence(CELL& listc, CELL& envir);
 CELL& Evaluate(CELL& c)     { return Evaluate(c, *m_GlobalEnvir); }

 int GarbageCollect();
 static void GCMark(CELL* c);

 static CELL* FindName(CELL& name, CELL& envir);
 static void ChangeName(CELL& name, CELL& envir, CELL& value);

 void* m_User;
private:
 enum TOKEN_TYPE { T_NONE, T_RAW, T_LITERAL, T_SYMBOL, T_NAME };

 struct TOKEN
 {
  TOKEN() : type(T_NONE) {}
  TOKEN(TOKEN_TYPE t, CELL* d) : type(t), data(d) {}
  TOKEN(ISTREAM::int_type r) : type(T_RAW), raw(r) {}

  TOKEN_TYPE type;
  union
  {
   CELL* data;
   ISTREAM::int_type raw;
  };
 };

private:
 int GCSweep();

 CELL& ApplyLambda(CELL& code, CELL& args, CELL& closure, CELL& envir);
private:
 CELL* m_FirstUnused;
 CELL* m_GlobalEnvir;
 CELL_STORAGE m_Cells;
 STRING_MAP m_InternedStrings;
 TOKEN m_Ahead;
};

//
// (CELL) PRINTING
//

void CELL::Print(OSTREAM& o)const
{
 switch(type)
 {
 default:  o << L"{{**UNKNOWN**}}"; break;
 case UNUSED: o << L"{{**UNUSED**}}"; break;
 case INT_LIT: o << std::dec << int_val; break;
 case BOOL_VAL: o << (bool_val ? L"true" : L"false"); break;
 case LAMBDA_VAL:o << L"{{ "; code->Print(o); o << L" }}"; break;
 case NATIVE_VAL:o << L"{{NATIVE}}"; break;
 case STRING_LIT:PrintEscapedString(o, *string_val); break;
 case NAME_CODE: o << L"@"; PrintEscapedString(o, *string_val); break;

 case CONS_CTOR: case EMPTY_LIT:
  o << L"[";
  PrintList(o, L", ");
  o << L"]";
  break;

 case ENVIR_VAL: o << L"{{ENVIR ";
  for(ENVIR_TABLE::const_iterator i=envir_table->begin(); i!=envir_table->end(); ++i)
  {
   o << *i->first->string_val << L"= ";
   i->second->Print(o);
  }
  o << L"}}";
  break;

 case COMBINE_CODE:
  op->Print(o);
  o << L"(";
  operands->PrintList(o, L", ");
  o << L")";
  break;
 }
}

void CELL::PrintList(OSTREAM& o, STRING const& separator)const
{
 for(CELL const* c=this; c->type==CONS_CTOR; c=c->tail)
 {
  if(c!=this)
   o << separator;
  c->head->Print(o);
 }
}

void CELL::PrintEscapedString(OSTREAM& o, STRING const& s)
{
 o << L"\"";
 for(STRING::const_iterator i=s.begin(); i!=s.end(); ++i)
 {
  if(*i<32) o << L"\\x" << std::hex << (unsigned int)(unsigned)*i << L";";
  else  o << *i;
 }
 o << L"\"";
}


//
// ALLOCATION AND GARBAGE COLLECTION
//

CELL& Script::CreateCell(CELL_TYPE ct, CELL* first, CELL* second)
{
 CELL* p;
 if(m_FirstUnused==NULL)
 {
  CELL c;
  m_Cells.push_back(c);
  p=&m_Cells.back();
 }
 else
 {
  p=m_FirstUnused;
  m_FirstUnused=p->next_unused;
 }
 p->mark=false;
 p->type=ct;
 p->head=first;
 p->tail=second;
 return *p;
}

CELL& Script::CreateString(STRING const& val)
{
 CELL& c=CreateCell(STRING_LIT);
 c.string_val=new STRING(val);
 return c;
}

CELL& Script::CreateName(STRING const& val)
{
 STRING_MAP::const_iterator i=m_InternedStrings.find(val);
 if(i==m_InternedStrings.end())
 {
  CELL& c=CreateCell(NAME_CODE);
  i=m_InternedStrings.insert(std::make_pair(val, &c)).first;
  c.string_val=&i->first;
 }
 return *i->second;
}

CELL& Script::CreateEnvir(CELL* parent)
{
 CELL& c=CreateCell(ENVIR_VAL);
 c.envir_table=new ENVIR_TABLE;
 c.parent_envir=parent;
 return c;
}

CELL& Script::CreateNative(NATIVE native)
{
 CELL& c=CreateCell(NATIVE_VAL);
 c.native=native;
 return c;
}

int Script::GarbageCollect()
{
 GCMark(m_GlobalEnvir);
 return GCSweep();
}

void Script::GCMark(CELL* c)
{
 if(c==NULL || c->mark)
  return;

 c->mark=true;

 switch(c->type)
 {
 case UNUSED:  throw L"Marking unused cell";
 case CONS_CTOR:  GCMark(c->head); GCMark(c->tail);  break;
 case LAMBDA_VAL: GCMark(c->code); GCMark(c->closure);  break;
 case COMBINE_CODE: GCMark(c->op);  GCMark(c->operands); break;

 case ENVIR_VAL:
  GCMark(c->parent_envir);
  for(ENVIR_TABLE::const_iterator i=c->envir_table->begin(); i!=c->envir_table->end(); ++i)
  {
   GCMark(i->first);
   GCMark(i->second);
  }
  break;
 }
}

int Script::GCSweep()
{
 int count=0;
 for(CELL_STORAGE::iterator i=m_Cells.begin(); i!=m_Cells.end(); ++i)
 {
  if(i->mark)
  {
   i->mark=false;
   continue;
  }

  if(i->type==UNUSED)
   continue;

  ++count;

  switch(i->type)
  {
  case STRING_LIT: delete i->string_val;      break;
  case ENVIR_VAL:  delete i->envir_table;      break;
  case NAME_CODE:  m_InternedStrings.erase(*i->string_val); break;
  }

  i->type=UNUSED;
  i->next_unused=m_FirstUnused;
  m_FirstUnused=&*i;
 }
 return count;
}

//
// EVALUATION
//

CELL& Script::Evaluate(CELL& c, CELL& envir)
{
 CELL* aux;
 switch(c.type)
 {
  //Non evaluable
 case UNUSED: throw L"Evaluating an unused cell";
 default:  throw L"Evaluating an unknown cell";
 case LAMBDA_VAL:throw L"Evaluating a lambda value";
 case NATIVE_VAL:throw L"Evaluating a native";
 case ENVIR_VAL: throw L"Evaluating an environment";

  //Literals
 case INT_LIT: case BOOL_VAL: case STRING_LIT: case EMPTY_LIT:
  return c;

  //Code constructors
 case CONS_CTOR:  return CreateCell(CONS_CTOR, &Evaluate(*c.head, envir), &Evaluate(*c.tail, envir));

 case NAME_CODE: 
  if((aux=FindName(c, envir))==NULL)
   throw L"Unknown name";
  return *aux;

 case COMBINE_CODE:
  switch((aux=&Evaluate(*c.op, envir))->type)
  {
  case LAMBDA_VAL: return ApplyLambda(*aux->code, *c.operands, *aux->closure, envir);
  case NATIVE_VAL: return aux->native(*this, *c.operands, envir);
  default:   throw L"Non-combinable value";
  }
 }
}

CELL& Script::EvaluateInSequence(CELL& c, CELL& envir)
{
 CELL* aux=&CreateCell(EMPTY_LIT);
 for(CELL* p=&c; p->type==CONS_CTOR; p=p->tail)
  aux=&Evaluate(*p->head, envir);
 return *aux;
}

CELL* Script::FindName(CELL& name, CELL& envir)
{
 //Try to find the name in current environment
 ENVIR_TABLE::const_iterator i=envir.envir_table->find(&name);
 if(i!=envir.envir_table->end())
  return i->second;

 //Failed, try parent
 if(envir.parent_envir!=NULL)
  return FindName(name, *envir.parent_envir);

 //Failed also, not found
 return NULL;
}

void Script::ChangeName(CELL& name, CELL& envir, CELL& value)
{
 //Try to find the name in current environment
 ENVIR_TABLE::iterator i=envir.envir_table->find(&name);
 if(i!=envir.envir_table->end())
 {
  (*envir.envir_table)[&name]=&value;
  return;
 }

 //Failed, try parent
 if(envir.parent_envir!=NULL)
  return ChangeName(name, *envir.parent_envir, value);

 //Failed also, not found
 throw L"Name to be changed is undefined";
}

CELL& Script::ApplyLambda(CELL& code, CELL& args, CELL& closure, CELL& envir)
{
 CELL& new_envir=CreateEnvir(&closure);
 CELL* params=code.head;
 CELL* arguments=&args;
 while(params->type==CONS_CTOR && arguments->type==CONS_CTOR)
 {
  (*new_envir.envir_table)[params->head]=&Evaluate(*arguments->head, envir);
  params=params->tail, arguments=arguments->tail;
 }

 if((params->type!=CONS_CTOR) != (arguments->type!=CONS_CTOR))
  throw L"Invalid arity";

 return EvaluateInSequence(*code.tail->head, new_envir);
}

Todas las funciones están en CPS

2011-09-29T19:40:00.000+02:00

Hace algún tiempo hablé del CPS y las continuaciones. Había un detalle que hacía completamente incompatible el estilo CPS con el estilo normal de programación: toda función en CPS requiere un parámetro extra que es la continuación. Una función normal se definiría más o menos así:

doble(x) = x+x

Al hacer el cambio a CPS, y suponiendo que la suma es una operación predefinida que no se pasa a CPS, obtendríamos lo siguiente:

doble_CPS(x,k) = k(x+x)

La nueva función requiere ese argumento extra que es la continuación k. La continuación es una función que no regresa y que representa el resto de la computación. Lo que vamos a hacer con el resultado del doble.

Nota: El que una continuación no regrese es muy interesante desde el punto de vista de la teoría de tipos. Su tipo sería [$T\rightarrow \bot$] que es igual a [$¬ T$], pero dejaré una explicación más profunda para otra entrada más adelante.

Bien. Ahora pensemos qué pasa si tengo un lenguaje de programación en el cual la compilación va a un ensamblador genérico. Una llamada a la función doble, en ensamblador, sería algo así:

PUSH x
CALL doble

Primero insertamos el parámetro en la pila y luego llamamos a doble. Si la llamada fuera la versión CPS tendríamos algo así:

PUSH x
PUSH k
CALL doble_CPS

Esto impediría que un lenguaje cuyo compilador transformase el código a CPS interactuase con otro que no usase la transformación a CPS. En un caso se espera un argumento y en el otro dos.

Sin embargo, esto no es así. Prácticamente todos los procesasores reales (incluyendo el x86) son de estilo CPS y hay que decir, en cada llamada, cuál es la continuación. ¿Cómo? Observando con detenimiento la instrucción de llamada CALL de estos procesadores. La instrucción

CALL f

es equivalente a

PUSH l
JUMP f
l:

Donde l es una etiqueta, un indicador de dirección de código en ensamblador y JUMP una instrucción de salto. Esa es la continuación. La dirección de código l. Eso significa que podríamos llamar a la función doble en modo CPS de la siguiente forma.

PUSH x
PUSH k
JUMP doble

Las dos últimas instrucciones son el equivalente al CALL, pero diciendo que queremos que regrese, no a la instrucción inmediatamente posterior al salto, sino a la que sea k.

De esta manera se pueden mezclar funciones usuales con funciones en CPS. De hecho, las funciones usuales ya están en CPS sólo que "disfrazadas" por el uso de CALL.

Nota: Existe un pequeño detalle extra que es el uso exhaustivo que hace la transformación a CPS de las clausuras léxicas. Las funciones usuales guardan su entorno en la pila por lo que se destruye al salir de la función. Existen técnicas para evitar esto: los upvalues de LUA o en análisis de escape de la función para crear los entornos en el montículo en vez de la pila.

Semántica formal para clausuras léxicas

2011-09-26T13:18:00.000+02:00

El lambda cálculo es una herramienta asombrosa. En pocas líneas puedes definir un modelo de computación. Esta simplicidad permite transmitir ideas de manera formal con relativa facilidad. Por esa razón estuve pensando cómo explicar la clausura léxica de manera matemática.

El lambda cálculo con semántica natural

Empezaré por el lambda cálculo con semántica natural (también llamada operacional de paso grande). La sintaxis del lambda cálculo es muy sencilla. [$$t::=x\mid tt\mid \lambda x.t$$] Este tipo de definiciones sintácticas se leen así:

[$t::=$]	Un término (o expresión) es
[$x$]	o bien una variable
[$tt$]	o bien una aplicación de un término sobre otro
[$\lambda x.t$]	o bien una función que toma una variable y devuelve un valor calculado por un término. Esto es a lo que se llama una abstracción lambda o función anónima.

Nota: La aplicación se asocia por la izquierda. Entonces, en vez de escribir [$(((t_1 t_2) t_3) t_4)$] escribimos [$t_1 t_2 t_3 t_4$].

Lo que es la semántica es también muy fácil de expresar: un término se convierte en un valor mediante una relación binaria [$t\Downarrow v$]. Los valores [$v$] sólo son un tipo especial de término que se denominan formas normales (nosotros vamos a usar WNF). [$$v::= \lambda x.t \mid x v_1 \cdots v_n$$] Estas formas normales no se pueden reducir más con las reglas de evaluación con las que vamos a expresar la semántica. Estas reglas son las siguientes:

Regla E-VAR[$$x\Downarrow x$$]	Regla E-ABS[$$\lambda x.t \Downarrow \lambda x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}t_1 \Downarrow x v_1 \cdots v_k\\t_2 \Downarrow v \end{array}}{t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$]	Regla E-APABS [$$\frac{\begin{array}{c}t_1 \Downarrow \lambda x.t\\t_2 \Downarrow v \\ [x\leftarrow v]t\Downarrow v'\end{array}}{t_1 t_2 \Downarrow v'}$$]

Como se comprobará, las reglas E-VAR y E-ABS no son complicadas ya que tanto las variables como las abstracciones son valores. El núcleo de todo está en las aplicaciones.
Tanto la regla E-APVAL como la regla E-APABS tienen una forma que recuerda a las fracciones. Esta es una notación usual en lógica para especificar reglas de inferencia e indica que si lo de arriba, que es el antecedente, se cumple, entonces lo de abajo, el consecuente, se debe cumplir.

La regla E-APVAL toma dos términos aplicados el [$t_2$] al [$t_1$]. Si resulta que [$t_1$] tras evaluar tiene un valor que no es una abstracción, lo único que podemos hacer es poner el valor de [$t_2$] detrás de la forma normal, haciéndola un poco más larga. Esto tiene algo más de sentido si, por ejemplo, usamos una variable que se llame [$lista$] y evaluemos algo como [$(lista\ 1\ 7) (2+3)$]. El resultado es la propia [$lista\ 1\ 7$] con un añadido que es el valor de [$2+3$]. Es decir, que [$ (lista\ 1\ 7) (2+3) \Downarrow lista\ 1\ 7\ 5$].

La regla E-APABS también toma dos términos aplicados. Esta vez tiene que ocurrir que [$t_1$] se evalúa a una función [$\lambda x.t$]. Entonces, hay que aplicar el resultado de [$t_2$] que es [$v$] a la función. La forma de hacerlo es sustituir todas las apariciones de [$x$] en [$t$] por [$v$] y calcular el valor que nos da esto. La sustitución la hemos escrito como [$[x\leftarrow v]$].

Entonces, si queremos calcular el doble de 1+3, sería evaluar [$(\lambda x.x+x)(1+3)$]. Usando la regla E-APABS vemos que, efectivamente, [$t_1= \lambda x.x+x$] y que [$t_1 \Downarrow \lambda x.x+x $] gracias a la regla E-ABS. Entonces, [$t=x+x$]. Por otra parte, [$t_2=1+3$] y [$t_2 \Downarrow 4$]. Finalmente, la sustitución a realizar es [$[x\leftarrow 4]t = 4+4$]. La evaluación es [$4+4\Downarrow 8$] por lo que [$v'=8$] y podemos decir que ocho es el doble de cuatro: [$$(\lambda x.x+x)(1+3)\Downarrow 8$$]

Nota: ¿Cómo es que estamos usando sumas y números si no los hemos definido? Realmente, sí que lo están. El lambda cálculo permite codificar los números (y muchas más cosas) como funciones. Esta es la llamada codificación de Church.

El lambda cálculo sin sustituciones

El lambda cálculo es Turing completo. Esto quiere decir que cualquier función calculable se puede calcular en él. Esto, por otra parte, no significa que sea eficiente computacionalmente. De hecho, la sustitución es una operación muy costosa: hay que recorrer todo el término en el que queremos sustituir y comparar las variables y manipular grandes trozos de expresión. Las reglas exactas son estas:

[$$[x\leftarrow t]x=t$$]	[$$\frac{x\ne x'}{[x\leftarrow t]x'=x'}$$]
[$$[x\leftarrow t](t_1 t_2)=( [x\leftarrow t] t_1 ) ( [x\leftarrow t] t_2 )$$]	[$$[x\leftarrow t]\lambda x.t' = \lambda x. t' $$]

La última regla está más abajo y es la más divertida porque tiene que evitar capturar las variables. Para hacer esto debe explorar además del término donde se sustituye el término a sustituir. Más coste.
[$$\frac{\begin{array}{c}x\ne x'\\x'\notin fv(t)\end{array}}{[x\leftarrow t]\lambda x'.t' = \lambda x'. [x\leftarrow t] t' }$$] Todos los creadores de compiladores e intérpretes buscan los métodos más curiosos para evitar la sustitución. Uno de estos métodos es la evaluación por entornos, aunque hay más como las máquinas G, los supercombinadores, etc.

Nosotros vamos a usar la evaluación por entornos que es más simple. La idea es sencilla: no sustituimos, sólo apuntamos lo que hay que sustituir. Lo apuntamos en un entorno que es una colección de vinculaciones de ese tipo. [$$ E::= \emptyset \mid E, x=v $$] Añadimos el entorno a nuestra relación de evaluación de esta manera [$$ E \vdash t \Downarrow v$$] Se podría leer "bajo el entorno [$E$] el término [$t$] se evalúa a [$v$]".

La idea es sencilla, ahora hay que establecer las reglas de evaluación. Un primer intento podría ser éste:

Regla E-VAR[$$\frac{x=v \in E}{E\vdash x\Downarrow v}$$]	Regla E-ABS[$$E\vdash\lambda x.t \Downarrow \lambda x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}E \vdash t_1 \Downarrow x v_1 \cdots v_k\\ E \vdash t_2 \Downarrow v \end{array}}{E \vdash t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$]	Regla E-APABS [$$\frac{\begin{array}{c} E \vdash t_1 \Downarrow \lambda x.t\\ E \vdash t_2 \Downarrow v \\ E,x=v \vdash t\Downarrow v'\end{array}}{ E \vdash t_1 t_2 \Downarrow v'}$$]

El truco está en la nueva regla E-VAR que mira en el entorno el valor de la variable encontrada y en la regla E-APABS que introduce en el entorno la vinculación.

Desafortunadamente estas reglas no funcionan.

El problema se observa en la siguiente evaluación [$$\emptyset \vdash (\lambda y.\lambda x.y) 3 \Downarrow v'$$] La regla a aplicar sería E-APABS que me diría que [$$ y=3 \vdash \lambda x.y \Downarrow v'$$] La regla E-ABS terminaría la evaluación incorrectamente [$$ y=3 \vdash \lambda x.y \Downarrow \lambda x.y$$] en vez de la correcta [$\lambda x.3$]. Hay que evitar que se pierda el entorno en la regla E-ABS. Al perder el entorno la expresión [$\lambda x.y$] queda abierta con la variable [$y$] libre. La solución es cerrarla con una clausura. La clausura será léxica porque hemos ido descendiendo por las estructuras sintácticas arrastrando los entornos hasta aquí.

Incluyamos entonces un nuevo término a nuestra sintaxis: las clausuras léxicas. Que son la combinación de una abstracción lambda y un entorno. [$$ t::= x\mid tt \mid \lambda x.t \mid \lambda^E x.t $$] Ahora los valores son [$$ v::= \lambda^E x.t \mid x v_1 \cdots v_k$$] y las reglas de evaluación correctas serían

Regla E-VAR[$$\frac{x=v \in E}{E\vdash x\Downarrow v}$$]	Regla E-ABS[$$E\vdash\lambda x.t \Downarrow \lambda^E x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}E \vdash t_1 \Downarrow x v_1 \cdots v_k\\ E \vdash t_2 \Downarrow v \end{array}}{E \vdash t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$]	Regla E-APABS [$$\frac{\begin{array}{c} E \vdash t_1 \Downarrow \lambda^{E'} x.t\\ E \vdash t_2 \Downarrow v \\ E',x=v \vdash t\Downarrow v'\end{array}}{ E \vdash t_1 t_2 \Downarrow v'}$$]

He cambiado la regla E-ABS convirtiendo la abstracción (que es código) en la clausura léxica (que es un valor) y la regla E-APABS que ahora usa el entorno de la clausura en vez del entorno de llamada.

Si evaluamos otra vez [$$\emptyset \vdash (\lambda y.\lambda x.y) 3 \Downarrow v'$$] obtenemos que [$ v'=\lambda^{y=3}x.y$]. Lo cual me dice que hay una sustitución pendiente de [$y$] por el valor [$3$]. Esta sustitución se hará cuando se aplique la función. No se perderá.

Nota: Hay un pequeñísimo detalle a tener en cuenta en estas nuevas reglas. Si queremos hacer una lista como hicimos antes [$lista\ 1\ (1+1)$] no podremos evaluarla. Eso es así porque la variable [$lista$] no está en el entorno y no podremos aplicar la regla E-VAR. Una solución a esto es añadir un entorno inicial donde [$lista=lista$] de manera que [$ lista=lista \vdash lista\ 1\ (1+1) \Downarrow lista\ 1\ 2$]. Esto nos debe llevar a pensar que hay dos tipos de variables las de código ([$lista$][$=lista$]) y las de valor ([$lista=$][$lista$]). Haciendo que las variables de valor tengan también entorno ([$x^E$]) abrimos la puerta a las macros higiénicas.

miniSL parte 15 - Funciones auxiliares de evaluación

2011-09-24T12:37:00.001+02:00

En la última entrada sobre miniSL estuvimos estudiando la evaluación. La evaluación es directa en casi todos los casos. Únicamente cuando tenemos que ejecutar una función definida por el usuario (celda de tipo LAMBDA_VAL) necesitamos una función auxiliar.

Esta función es ApplyLambda() y lo que hace es tomar

El código del usuario que hay que ejecutar (esto está en la celda LAMBDA_VAL) que contiene también el nombre de los parámetros.
El código de los argumentos que se le pasa a la función (esto está en el código, en la celda COMBINE_CODE)
El entorno de clausura donde queremos que se evalúe el código del usuario (también está en la celda LAMBDA_VAL)
El entorno donde hay que evaluar los argumentos, ya que estos se evalúan en el entorno de llamada y no en el local.

CELL& Script::ApplyLambda(CELL& code, CELL& args, CELL& closure, CELL& envir)
{

Con estos valores, la función ApplyLambda() crea un entorno nuevo. El entorno local.

CELL& new_envir=CreateEnvir(&closure);

Luego, evalúa los argumentos en el entorno de llamada y los va introduciendo en este entorno local con los nombres de los parámetros que se declararon en el código. Si la función era f(a,b,c) y se llama con f(1+2,3+4,5+6), lo que ApplyLambda() hace es evaluar 1+2, obteniendo el valor 3, y vincular la variable a al valor 3 recién obtenido. Luego hace lo mismo vinculando b a 7 y c a 11. Esto se hace con este bucle.

CELL* params=code.head;
 CELL* arguments=&args;
 while(params->type==CONS_CTOR && arguments->type==CONS_CTOR)
 {
  (*new_envir.envir_table)[params->head]=&Evaluate(*arguments->head, envir);
  params=params->tail, arguments=arguments->tail;
 }

Bien podría ocurrir que nos sobren argumentos o parámetros. Es decir, que la aridad de la función no coincida con la de la llamada. Eso es un error.

if((params->type!=CONS_CTOR) != (arguments->type!=CONS_CTOR))
  throw L"Invalid arity";

Finalmente, evaluamos el código. El código es una secuencia y se debe evaluar como tal usando otra función auxiliar.

return EvaluateInSequence(*code.tail->head, new_envir);
}

La función auxiliar EvaluateInSequence() es sumamente sencilla. Evalúa una lista en secuencia y retorna el valor de la última expresión evaluada.

CELL& Script::EvaluateInSequence(CELL& c, CELL& envir)
{
 CELL* aux=&CreateCell(EMPTY_LIT);
 for(CELL* p=&c; p->type==CONS_CTOR; p=p->tail)
  aux=&Evaluate(*p->head, envir);
 return *aux;
}

Como se observa, lo más complicado (y lento) es ir vinculando en el entorno local los valores de los argumentos a los parámetros. De hecho, en los lenguajes de programación reales, se buscan convenios de llamada que eviten esto. Por ejemplo, introduciendo los valores de los argumentos en pila con cierto orden. De esta manera, la función llamada no tiene que buscar las variables por su nombre, que también es lento, sino por su posición en memoria que es mucho más rápido.

Con esto acabamos el núcleo del lenguaje. En la siguiente entrada pondré el código escrito hasta ahora y, a partir de entonces, empezaremos con el reconocimiento sintáctico del programa.

La intuición tras la transformada de Laplace

2011-09-21T22:04:00.000+02:00

Imaginemos que queremos hacer una derivada de una señal [$x(t)$].[$$\frac{d}{dt}x(t)$$] Las derivadas son operadores lineales. Eso quiere decir que si dividimos la señal en dos términos [$A_1 x_1(t)+A_2 x_2(t)$] tenemos [$$ \frac{d}{dt}x(t)=    A_1 \frac{d}{dt}x_1(t) + A_2 \frac{d}{dt}x_2(t) $$] Ya que estamos, seamos astutos. Busquémonos unos términos que se deriven con facilidad. Por ejemplo, [$A e^{st}$]. Si estos fueran los términos, tendríamos [$$x(t)=A_1 e^{s_1t} + A_2 e^{s_2t}$$] y entonces [$$ \frac{d}{dt}x(t)=    A_1 \frac{d}{dt}x_1(t) + A_2 \frac{d}{dt}x_2(t) = A_1 s_1 e^{s_1t} + A_2 s_2 e^{s_2t} $$]Mucho más fácil.

Todo esto está muy bien; pero es raro que una señal sea suma de dos exponenciales (bueno, quizás no sea tan raro). Una opción es hacer la suma infinita, lo cual abarca muchas más señales. Sin embargo, la opción buena, buena, buena es que sea una suma de densidades. Una integral. [$$ x(t)=\int_C{A(s)e^{st}ds}$$] El único truquillo es que la amplitud depende de la constante [$s$] que usemos en la exponencial. El contorno de integración [$C$] no nos interesa ahora. Cuando este contorno existe es que la señal puede representarse así. A veces, no existe. Es decir, que tampoco abarcamos todas las señales posibles, pero sí muchísimas. Todas las de interés.

¿Qué pasa cuando derivamos la señal [$x(t)$] descompuesta como una integral de exponenciales? La integral es lineal, la derivada también, la variable de derivación no está relacionada con la variable del diferencial... Todo esto nos permite mover la derivada bajo el signo de la integral. [$$ \frac{d}{dt}x(t)= \frac{d}{dt}\int_C{A(s)e^{st}ds} =   \int_C{ \frac{d}{dt} A(s)e^{st}ds} $$] Y ya tenemos lo que queríamos, la derivada de una exponencial que es ella misma por la derivada de su exponente. [$$ \frac{d}{dt}x(t)= \int_C{A(s)\ s\ e^{st}ds} $$] Buscando la similitud con   [$$ x(t)=\int_C{A(s)e^{st}ds}$$] es fácil ver que la derivada lo único que hace es multiplicar [$A(s)$] por [$s$]. ¡Mucho más fácil multiplicar que hacer la derivada!

Esa [$A(s)$] es casi la transformada de Laplace. Digo casi porque el contorno [$C$] introduce un factor de [$2\pi j$] que hay que compensar. Entonces, si llamo [$\mathcal{L}_{x(t)}(s)$] a la transformada de Laplace de [$x(t)$], tendré que    [$$ x(t)=\frac{1}{2\pi j}\int_C{ \mathcal{L} _{x(t)}(s)e^{st}ds}$$] Concretamente la expresión de arriba es la transformada inversa de Laplace. La transformada directa es más sencilla. [$$ \mathcal{L}_{x(t)}(s)=\int_0^\infty{x(t)e^{-st}dt}$$]

Incompatibilidades sintácticas

2011-09-15T10:36:00.000+02:00

Los operadores prefijos e infijos no pueden ser a la vez identificadores

Si ese fuera el caso, tendríamos la siguiente ambigüedad.

a b c //=> (a) b (c) si b fuera infijo
a b c //=> a (b c) si b fuera prefijo

Una solución a esto es restringir o bien los operadores infijos o bien los prefijos para que no puedan ser identificadores.

Las palabras clave de las sentencias no pueden ser identificadores

Parece una perogrullada, pero hay una razón para que sea así.

return + a //=> return (+a) si es palabra clave
return + a //=> (return) + (a) si es identificador

Una solución a esto es reservar ciertos identificadores como palabras clave. Otra solución es marcar de alguna manera los identificadores que queramos que sean introductores de sentencias.

La tensión entre la llamada por yuxtaposición y los operadores como identificadores

No pueden compartir la misma categoría sintáctica (identificadores) ya que su asociatividad es distinta.

a b c //=> (a b) c si es llamada por yuxtaposición (currificación)
a b c //=> a (b c) si b es un operador prefijo
a b c //=> (a) b (c) si b es un operadores infijo

Una solución es no tener llamada por yuxtaposición. Otra solución es restringir los operadores a símbolos.

+ - c //=> + (- c) OK. No se confunde. Si son símbolos, son prefijos.

Un operador no puede ser infijo, prefijo y postfijo a la vez

Si ese fuera el caso, tenemos la siguiente ambigüedad. Incluso con una categoría sintáctica distinta.

a + + b //=> (a +) + b si el primer más es tomado como postfijo
a + + b //=> a + (+ b) si el segundo más es tomado como prefijo

Llamada por yuxtaposición y tuplas son incompatibles con la sintaxis usual de llamada

Esto sólo es relevante si la semántica es distinta. Si la semántica es la misma, la ambigüedad confluye en un mismo significado.

f(a,b,c) //=> La función f aplicada por yuxtaposición a un argumento que es la tupla (a,b,c)
f(a,b,c) //=> La función f aplicada a tres argumentos que son a, b y c

Una solución a esto es usar otra sintaxis para las tuplas, por ejemplo [a,b,c].

Tuplas y parentización

Es una ambigüedad muy usual.

(1) //=> El número uno
(1) //=> Una tupla con un elemento que es el número uno

Algunos lenguajes como Python solucionan esto añadiendo una coma extra en el caso de ser una tupla y no una parentización.

(1,) //=> Una tupla en Python

¿Qué es una clausura léxica?

2011-09-09T20:54:00.002+02:00

Expresiones abiertas

Antes de ver qué es una clausura léxica debemos saber qué es una clausura y antes de saber qué es una clausura debemos saber qué es lo que cierra la clausura. Lo que la clausura cierra son expresiones abiertas. Ahora bien, ¿qué es una expresión abierta? Para responder a esta pregunta necesitamos saber antes qué es una variable ligada y una variable libre.

La forma más sencilla de explicarlo es mediante un mínimo ejemplo. Definamos dos funciones.

f= λx.x+3
g= λx.5x

Aunque hemos usado la misma variable “x” en ambas funciones, cada “x” tiene un significado distinto en cada función. No hay más que aplicar las funciones.

f(4) = 4+3
g(7) = 5·7

La “x” de la función “f” vale 4 y la “x” de la función “g” vale 7. Esto es así porque estas “x” son variables ligadas. La “x” de “x+3” está ligada a la “λx” de “f” y la “x” de “5x” está ligada a la “ λx” de “g”.

Otro ejemplo:

h = λx. x+y

En este caso la “x” de “x+y” está ligada a la “λx” de “h”. Por otra parte la “y” no está ligada, es una variable libre.

En “a+b” tanto “a” como “b” son variables libres y en “c+c” la “c” es una variable libre que aparece dos veces.

Se llaman expresiones cerradas a las que no tienen variables libres y se llaman expresiones abiertas a las que tienen variables libres.

“5+3” es una expresión cerrada.
“λx.2x” es una expresión cerrada.
“λx.x+x” es una expresión cerrada.
“λxy.2x+5y+3” es una expresión cerrada.
“a” es una expresión abierta (la variable “a” es libre).
“λy.y+x” es una expresión abierta (la variable “x” es libre).
“1+z” es una expresión abierta (la variable “z” es libre).

Clausuras

Realizar una clausura consiste en ligar las variables libres dándoles algún valor. Una clausura podría ser la clausura cero en la cual todas las variables libres toman el valor cero.

En esta clausura la expresión “3+x” es abierta, pero se cierra a “3+0”. Igualmente, la expresión “f= λx.x+y” que tiene de variable libre a la “y”, se cierra a “f= λx.x+0”.

Pero podríamos tener otro tipo de clausura. Por ejemplo, la que se usa en matemáticas que llamaremos aquí la clausura convencional. En esta clausura las variables libres toman el valor que hayan definido por nosotros los matemáticos.

La expresión “cos(3)” es abierta porque “cos” es una variable libre. Ahora bien, todo el mundo sabe que “cos” es el coseno por lo que cerramos la expresión ligando la variable “cos” con la función coseno.
En algunos casos la clausura convencional no nos sirve. Imaginemos que nos encontramos con la expresión “K(5)”. Leyendo las bibliotecas de funciones matemáticas nos damos cuenta que podría ser la función de Bessel o la función de Sturve o la integral elíptica de primer orden o varias cosas más.

La forma de resolverlo es haciendo una clausura global. En esta clausura ligamos explícitamente las variables a su significado siempre que no se diga lo contrario. Es lo que se suele hacer cuando definimos una función. El decir “f=λx.2x” significa que “f” es la función doble y, si más adelante tenemos “f(2)”, recordamos el significado de “f” que le dimos. Este tipo de clausura global es la que se usa en lenguajes de programación como el C.

Por cierto, cuando digo “f=λx.2x” no sólo estoy ligando “f” para la clausura global, también estoy ligando “x” en la expresión “2x”. Esta es la clausura local. En este punto, el lector con conocimiento de informática habrá identificado las clausuras con los entornos. Realmente la clausura es el entorno (el ligado de variables) más la expresión que se cierra.

La clausura léxica

El adjetivo “léxico” significa “relativo a las palabras de un lenguaje”. Es decir, que haremos la clausura según nos digan las palabras del lenguaje.

En los lenguajes de ordenador (y en las matemáticas) las expresiones se anidan unas dentro de otras. Así, la expresión “1+2” está dentro de la expresión “7+g(1+2)”. Esto da lugar a una estructura del propio lenguaje. La clausura léxica es la que respeta esa estructura.

{
define x=5 //Definimos “x”
define g(y)=x+y //Definimos “g”. La “x” es libre aquí
}

En este programa, la expresión “define g(y)=x+y” está dentro de la estructura superior “{ define x=5; define g(y)=x+y }”. En muchos lenguajes de programación las llaves {} se usan para mostrar la estructura del programa.

Cuando se define la función “g(y)”, la variable “y” está ligada, pero la “x” no. Sin embargo, siguiendo la estructura del programa, el valor de “x” está definido un poco más arriba. Esto quiere decir que la clausura léxica liga la variable “x” (dentro de la función de “g”) a la “x” que está definida fuera de esa definición, pero estructuralmente por encima de ella.

Podría uno pensar que la clausura léxica es un descontrol porque liga las variables como le da la gana. No es así. En este ejemplo, la clausura léxica no liga la “y” y un compilador daría un error.

{
define g(y)=y+7
define f(x)=x+y
}

No hay ligazón porque la expresión “define g(y)=y+7” no define la “y”, define la “g”. Además, la “y” de “g(y)” ya está ligada a la de “y+7”.

El siguiente diagrama muestra cómo, al realizar la clausura léxica, se van buscando estructura arriba las ligazones de variables.

La clausura léxica como valor

Una de las claves de la clausura léxica es que se son un valor. El ejemplo típico es el siguiente:

{
define f(x)=λy.x+y;
define a=f(2);
define b=f(5);
print a(4); //Imprime 6
print b(4); //Imprime 9
}

En este ejemplo la expresión “λy.x+y” es una expresión abierta y la clausura léxica de la misma nos dice que hemos de ligar la “x” a la de la “f(x)”. Sin embargo esta “x” es el argumento de una función así que el resultado de “f(2)” es la clausura léxica de la expresión “λy.x+y” ligando la “x” al “2”. Esto es un valor como la cadena “hola”, sólo que es algo más largo de describir.

De la misma forma “b” se define a la clausura léxica de la expresión “λy.x+y” ligando “x” al “5”. Dado que la expresión “λy.x+y” es la función que toma un “y” y devuelve “x+y”, podemos usar esa función. Es lo que se hace en los “print”.

En el primer “print” usamos la variable “a” cuyo valor era “ λy.x+y” ligando la “x” al “2”. Al aplicar “a(4)” le damos un valor a “y” así que el resultado es “x+4” ligando la “x” al “2” que a su vez es “6”. Lo que se imprime. El mismo razonamiento obtenemos para “b(4)”.

La clausura léxica y la asignación

Existe un pequeño detalle final y consiste en distinguir ligazón y asignación. Realmente, realmente al hacer “f(2)” en este último ejemplo no ligamos la “x” de “λy.x+y” a “2”. Lo que hacemos es ligar esa “x” a la de “f(x)” y, luego, al hacer “f(2)” asignamos la “x” de “f(x)” a “2”. El siguiente diagrama lo muestra.

Esta distinción es importante porque en los lenguajes imperativos se permite reasignar. Es lo que ocurre en este código.

{
define x=5;
define f(y)=x+y;
print f(3); //Imprime 8
x=7; //Reasignación de x
print f(3); //Imprime 10
}

Cuando el lenguaje es funcional estas distinciones no son importantes porque no se puede reasignar.

Lo que nunca me enseñaron: Los filtros de Cauer (y parte IV)

2011-08-25T15:57:00.000+02:00

Partes anteriores: 1, 2 y 3.

Las funciones elípticas de Jacobi

Las funciones elípticas de Jacobi son una generalización de las funciones trigonométricas. Hay doce funciones elípticas de Jacobi, pero sólo vamos a usar una que se llama [$cd$] y está relacionada con el coseno. Si bien el argumento de las funciones trigonométricas son ángulos, el argumento de las funciones elípticas de Jacobi es un valor [$u$] que no tiene una relación inmediata ni con los ángulos, ni áreas ni longitudes de arco.

Trigonometría en la elipse usando las funciones elípticas de Jacobi [$sd$], [$nd$] y [$cd$]. Hay más funciones elípticas de Jacobi, pero sólo nos será de utilidad la [$cd$].

El valor [$k^'$] se llama el comódulo elíptico y se relaciona con la excentricidad de la elipse [$k$], también llamada el módulo elíptico, de la siguiente forma. [$$ k^2+(k^')^2=1$$] Dependiendo de la excentricidad de la elipse sobre la que trabajemos las funciones de Jacobi cambian por lo que es usual presentarlas con dos argumentos.[$$cd(u,k),\ \ \ \ sd(u,k),\ \ \ \ nd(u,k)$$] En concreto, la función [$cd(u,k)$] es muy parecida al coseno cuando se observa su inversa. [$$ arccd(u,k)=\int_u^1{\frac{dt}{\sqrt{1-t^2}\sqrt{1-k^2 t^2}}}$$] Investigaremos el recorrido que hace esta función cuando [$u$] se mueve desde [$0$] hasta infinito. Empieza en [$$ arccd(0,k)=\int_0^1{\frac{dt}{\sqrt{1-t^2} \sqrt{1-k^2 t^2}}}$$] Este valor es conocido como la integral elíptica completa de primera especie de módulo [$k$] y se escribe usualmente como [$K(k)$].

Diagrama representando el valor real resultado de la integral completa de primera especie que es el valor del [$arccd$] de cero.

Conforme aumente [$u$] por los reales, decrecerá el [$arccd$] hasta que lleguemos a [$u=1$] donde los límites de la integral van a coincidir por lo que su valor será cero. Si hacemos el recorrido simétrico hacia los valores negativos, llegaremos a [$u=-1$] donde el valor de su [$arccd$] será [$2K(k)$].

Recorrido del valor de [$arccd$] con argumentos desde cero hasta uno (y simétrico por los negativos).

A partir de este punto, seguir integrando significa que la raíz [$\sqrt{1-t^2}$] va a resultar en valores imaginarios. Nuestro recorrido pasará a moverse verticalmente por la gráfica hasta que [$u=\frac{1}{k}$]. A partir de este valor, la raíz [$\sqrt{1-k^2 t^2}$] también se hace imaginaria. El valor del [$arccd$] en [$u=\frac{1}{k}$] es fácilmente calculable mediante un cambio de variables. [$$ arccd \left(\frac{1}{k},k\right)=\int_{\frac{1}{k}}^1{\frac{dt}{\sqrt{1-t^2}\sqrt{1-k^2 t^2}}}=\int_0^1{\frac{dt}{\sqrt{t^2-1}\sqrt{1-(k^')^2 t^2}}}=jK(k^' )$$] Trazando estos segmentos verticales del recorrido obtenemos el siguiente diagrama.

Recorrido del valor de [$arccd$] con argumentos desde cero hasta [$\frac{1}{k}$] (y simétrico por los negativos)

Finalmente, continuamos a partir de [$\frac{1}{k}$]. Ahora las dos raíces tienen el radicando negativo y son por tantos imaginarias, como [$j^2=-1$] el sentido de nuestro recorrido ha de ser opuesto al que inicialmente tenía. En el límite hacia el infinito será: [$$arccd(\infty,k)\rightarrow \int_\infty^1{\frac{dt}{\sqrt{1-t^2}\sqrt{1-k^2 t^2}}}=K(k)+jK(k^' )$$] Así que terminamos el recorrido de la siguiente manera.

Recorrido completo del valor de [$arccd$] con argumentos reales.

Sabiendo que al seguir este recorrido sobre la función [$cd(u,k)$] debemos obtener la función identidad, ganamos perspectiva de cómo es la función [$cd(u,k)$].

Secciones de cd

Su diagrama de polos y ceros se presenta a continuación y observamos que tiene dos periodos. El usual de [$4K(k)$] que se correspondería con el [$2\pi$] de las funciones trigonométricas y otro imaginario de [$2iK(k^' )$] que aparece por esa segunda raíz cuadrada en la integral. La zona sombreada es la que se repite periódicamente tanto horizontal como verticalmente.

Diagrama de polos, ceros y valores destacados de [$cd$].

Como hicimos con la función coseno, vamos a ver cómo es la función [$cd(u,k)$] en las tres secciones del recorrido de [$arccd(u,k)$]. Recordemos que en estas rectas la función [$cd(u,k)$] es real.

Tres secciones de la función [$cd$] por las rectas que va a seguir su [$arccd$]. En estas rectas el valor de [$cd$] es real y se representa a su derecha.

Para la rama negativa tenemos que [$$ cd(u+2K(k),k)=-cd(u,k)$$] Además, existe una propiedad de simetría entre [$cd(t,k)$] y [$cd(t+jK(k^' ),k)$] que usaremos más adelante. [$$cd(u+jK^' (k),k)=\frac{1}{k\ cd(u,k)}$$] En la DLMF podemos ver en 3D la función [$cd$] con sus polos bien distinguidos.

http://dlmf.nist.gov/22.3.F19.mag

La función racional elíptica

El lector astuto ya habrá imaginado que lo siguiente que vamos a hacer es [$$cd(n\ arccd(u ,k),k)$$] Como hicimos con los polinomios de Chebyshev, el recorrido del [$arccd$] queda ampliado [$n$] veces. Siguiéndolo, nos haremos una idea de cómo es esta función. Como antes, sólo seguiremos los valores positivos ya que los negativos son simétricos.

Recorrido de [$arccd$] ampliado tres veces sobre el diagrama de polos y ceros de [$cd$].

El resultado es una oscilación entre +1 y -1 en el primer segmento, otra oscilación entre 1 y 1/k en el segundo segmento y otra oscilación entre 1/k e infinito (cambiando de signo en cada infinito) en el tercer segmento.

Gráfica de la función [$cd(3\ arccd(x, k), k)$] con cada uno de los tramos coloreados.

Esta función no nos sirve como función [$F^2 (\omega)$] porque tendría oscilaciones en la banda de paso.

La función anterior al cuadrado como intento de aproximación a [$F^2(\omega)$]. La banda de transición es muy ancha y tiene oscilaciones.

Afortunadamente tenemos dos [$k$] a nuestra disposición, la del [$arccd$] que llamaremos [$k_a$] y la del [$cd$] que llamaremos [$k_c$]. Entonces, se define la función racional elíptica de la siguiente forma:[$$R_n (u,k_a,k_c )=cd\left(n\ \frac{K(k_c )}{K(k_a )} arccd(u ,k_a ),k_c \right)$$] La aparición del cociente [$\frac{K(k_c )}{K(k_a )}$] es necesaria para convertir el periodo real del [$arccd$] en el periodo real del [$cd$] que ahora son distintos al tener módulos distintos. Bueno, exactamente [$n$] veces ese periodo.
Por otra parte, ese n no lo queremos en el periodo imaginario. Querríamos tener [$$ R_n (u,k_a,k_c )=cd\left(\frac{K(k_c^' )}{K(k_a^' )} arccd(u ,k_a ),k_c \right)$$] ¡Y podemos tener ambas condiciones si elegimos con cuidado! [$$ n=\frac{K(k_a )K(k_c^' )}{K(k_a^' )K(k_c )} $$] De esta forma el recorrido queda multiplicado sólo en la dirección horizontal.

El recorrido que tomamos en la función elíptica racional con unos parámetros adecuados para que sólo se mueva medio periodo imaginario.

La gráfica de esta función es como sigue. En ella aparece tanto la [$k_a$] como la [$k_c$] explícitamente.

Gráfica de la función elíptica racional con módulos [$k_a$] y [$k_c$] (y la [$n$] adecuada según se comentó arriba).

Como ocurría con los polinomios de Chebyshev, esta función es real, aunque esta vez no puede expresarse como un polinomio ya que tiene polos (los infinitos). Debe expresarse como un cociente entre polinomios, de ahí que se llame función racional elíptica.

El filtro de Cauer

El filtro de Cauer o filtro elíptico es el que toma esa función racional elíptica como [$F(\omega)$]. La gráfica de su cuadrado es la que sigue.

La función racional elíptica como función [$F(\omega)$] de un filtro.

Ajustando para que se cumplan los requisitos de un filtro tenemos que [$$ F^2 (\omega)=\epsilon_p^2 R_n^2 \left(\frac{\omega}{\omega_p} ,\frac{\omega_p}{\omega_s} ,\epsilon_p \epsilon_s \right)$$] Donde hemos usado [$$k_a=\frac{\omega_p}{\omega_s}$$][$$ k_c=\epsilon_p \epsilon_s$$]

La función racional elíptica como función [$F(\omega)$] de un filtro con los parámetros ajustados a las especificaciones del filtro.

Así que un filtro de Cauer de orden [$n$] tiene la siguiente respuesta en frecuencia al cuadrado. [$$ |H(j\omega) |^2=\frac{1}{1+\epsilon_p^2 R_n^2 \left( \frac{\omega}{\omega_p} ,\frac{\omega_p}{\omega_s} ,\epsilon_p \epsilon_s \right)}$$] Realmente, su banda de transición es mucho más pequeña que lo trazado en las gráficas anteriores. La siguiente gráfica muestra la respuesta en frecuencia bien escalada.

Respuesta en frecuencia de un filtro de Cauer

Además, la condición de la no oscilación en la banda base y ajuste de periodos es precisamente la cota del orden del filtro. [$$ n\ge \frac{K(\frac{\omega_p}{\omega_s}) K^' (\epsilon_p \epsilon_s )}{K^' ( \frac{\omega_p}{\omega_s} )K( \epsilon_p \epsilon_s )}$$] Donde [$K^' (k)=K(k^' )$].
Ojo: una vez hallado [$n$] con la desigualdad, hemos de modificar algún requisito para que se cumpla la igualdad. Debemos tener la igualdad si no queremos oscilaciones en la banda de transición.

La búsqueda de la función de transferencia

Para obtener la función de transferencia necesitamos conocer los polos y los ceros de la misma. Ambos son sencillos de calcular. Hagamos el cambio [$\omega=-js$] y empecemos por los ceros de la función de transferencia. Ocurrirán cuando [$R_n^2$] tienda a infinito. Es decir, en los polos de [$R_n^2$]. [$$R_n^2 \left(\frac{-js_{cero}}{\omega_p} ,\frac{\omega_p}{\omega_s} ,\epsilon_p \epsilon_s \right)=\infty$$] [$$n \frac{K(\epsilon_p \epsilon_s )}{K(\frac{\omega_p}{\omega_s} )} arccd\left(\frac{-js_{cero}}{\omega_p} ,\frac{\omega_p}{\omega_s} \right)=arccd(\infty,\epsilon_p \epsilon_s )$$]
El miembro de la derecha es la localización de los polos de [$cd$]. Recordemos que hay dos periodos y, por la dirección del recorrido del [$arccd$] en la zona de los ceros, nos interesa el periodo real.[$$n \frac{K(\epsilon_p \epsilon_s )}{K(\frac{\omega_p}{\omega_s})} arccd\left(\frac{-js_{cero\ m}}{\omega_p} ,\frac{\omega_p}{\omega_s}\right)=(2m+1)K(\epsilon_p \epsilon_s )+jK^' (\epsilon_p \epsilon_s )$$]
Despejando llegamos a la expresión siguiente. [$$ s_{cero\ m}=j\omega_p cd\left(\frac{2m+1}{n} K\left(\frac{\omega_p}{\omega_s}\right)+jK^' \left(\frac{\omega_p}{\omega_s}\right),\frac{\omega_p}{\omega_s} \right)$$]Por la propiedad de simetría, se simplifica aún más. [$$ s_{cero\ m}=\frac{j \omega_s}{cd\left(\frac{2m+1}{n} K(\frac{\omega_p}{\omega_s}),\frac{\omega_p}{\omega_s} \right)}$$]
Para los ceros con los que nos quedamos en H(s), el valor de [$m$] se debe mover entre [$0$] y [$n-1$]. En algunos casos el cero aparecerá en el infinito. Eso significa que no debemos tenerlo en cuenta.
Para los polos hay que igualar [$\epsilon_p^2 R_n^2$] a menos uno. [$$ \epsilon_p^2 R_n^2 \left(\frac{\omega_{polo}}{\omega_p} , \frac{\omega_p}{\omega_s} ,\epsilon_p \epsilon_s \right)=-1$$][$$ R_n \left( \frac{\omega_{polo}}{\omega_p} , \frac{\omega_p}{\omega_s} ,\epsilon_p \epsilon_s \right) =\frac{j}{\epsilon_p}$$] Obtenemos una expresión similar a la que teníamos para los ceros. [$$ cd\left(n\ \frac{K(\epsilon_p \epsilon_s )}{K(\frac{\omega_p}{\omega_s})} arccd \left(\frac{-js_{polo}}{\omega_p} ,\frac{\omega_p}{\omega_s} \right),\epsilon_p \epsilon_s \right)=\frac{j}{\epsilon_p}$$]De nuevo elegimos el periodo real.[$$ n \frac{K(\epsilon_p \epsilon_s )}{K(\frac{\omega_p}{\omega_s})} arccd \left(\frac{-js_{polo\ m}}{\omega_p} ,\frac{\omega_p}{\omega_s}\right)=arccd\left(\frac{j}{\epsilon_p} ,\epsilon_p \epsilon_s \right)+2mK(\epsilon_p \epsilon_s )$$]Y despejamos[$$s_{polo\ m}=j \omega_p cd\left(\frac{K(\frac{\omega_p}{\omega_s})}{n\ K(\epsilon_p \epsilon_s ) } \left[arccd\left(\frac{j}{\epsilon_p} ,\epsilon_p \epsilon_s \right)+2mK(\epsilon_p \epsilon_s ) \right] ,\frac{\omega_p}{\omega_s}\right )$$]
Así podemos construir la magnitud de la función de transferencia al cuadrado a falta de la constante multiplicativa. [$$ |H(s) |^2=A^2 \frac{\prod{(s-s_{cero\ m})}}{\prod{(s-s_{polo\ m})}}$$] La constante se halla haciendo [$s=0$] en la expresión de [$|H(s) |^2$] basada en [$R_n^2$] e igualándola con la de arriba. [$$ |H(0) |^2=A^2 \frac{\prod{(0-s_{cero\ m})}}{\prod{(0-s_{polo\ m})}}=\frac{1}{1+\epsilon_p^2 R_n^2 (0,\frac{\omega_p}{\omega_s} ,\epsilon_p \epsilon_s ) }$$] Finalmente, se toman los polos con parte real menor que cero para conseguir que pueda ser realizado en la práctica.

Epílogo

Si el lector compara, para un mismo conjunto de especificaciones, los órdenes que se requieren de los filtros, verá que el filtro de Cauer mejora los otros dos tipos de filtros.

Debido a que el orden del filtro está relacionado con el número de componentes que se necesitan para hacer un circuito eléctrico del filtro, es inmediato llegar a la conclusión de que los filtros de Cauer son más económicos.

Esa es la razón por la que Cauer conseguía un filtro con las mismas prestaciones, pero con una bobina menos.

Lo que nunca me enseñaron: Los filtros de Cauer (parte III)

2011-08-22T00:08:00.004+02:00

La primera parte está aquí y la segunda parte aquí.

Los viajes del arcocoseno

Hasta aquí todo lo visto ha sido para entender el proceso de realización de un filtro. A partir de aquí empezamos a acercarnos a los filtros elípticos. Sin embargo, antes debemos pararnos a explorar los filtros de Chebyshev. Los filtros de Chebyshev son más simples porque usan para su expresión matemática la circunferencia en vez de la elipse. Deberían llamarse filtros circulares, pero ya se ha quedado el nombre de Chebyshev.

Lo primero que necesitamos para entender los filtros de Chebyshev es la definición de arcocoseno. [$$arccos(x)=\int_x^1{\frac{dt}{\sqrt{1-t^2}}}$$] Esta integral no es más que la longitud de arco de una circunferencia unitaria desde una abscisa [$x$]. (Nota: Por supuesto, es una función multivaluada. Tomaremos sólo la rama de la raíz principal aquí).

El arcocoseno no es más que la longitud del arco marcado.

Lo sorprendente es que esta integral, el arcocoseno, tiene sentido cuando [$x$] va más allá de [$\pm 1$]. Eso sí, hemos de usar números complejos porque el radicando que aparece en la raíz se hace negativo.
Dibujaremos el valor que toma el arcocoseno en el plano de Argand conforme [$x$] tome valores reales. Empezaremos por el arcocoseno de cero que es [$\pi/2$].

El arcocoseno de cero es [$\pi/2$].

Si vamos aumentando [$x$], llegamos hasta [$arccos(1)=0$] obteniendo únicamente números reales. Es el arcocoseno clásico. Igualmente, si disminuimos [$x$], llegamos hasta [$arccos(-1)=\pi$]. Esta simetría continuará por lo que no hablaremos más de los valores negativos de [$x$].

El recorrido desde el arcocoseno de cero al arcocoseno de uno (y menos uno).

En el punto [$arccos(1)=0$] ocurre que la raíz del integrando se anula. [$$\sqrt{1-t^2 }=0$$] Si seguimos moviendo [$x$] por la recta real, el arcocoseno entrará en el eje imaginario. A partir de aquí tenemos otras dos ramas, la raíz positiva y la negativa. Elegimos la positiva y recordamos para luego que hay simetrías.

El recorrido del valor del arcoseno de los números reales.

Las olas del coseno

En los complejos, el coseno es una función holomorfa. Una de sus particularidades es la periodicidad en el eje real. Si trazamos su diagrama de ceros (no tiene polos) y añadimos algunos puntos destacados en la línea real obtenemos lo siguiente.

Los valores destacados que toma el coseno cuando su argumento es un número complejo.

Si recorremos el plano de Argand por la línea real [$x=\sigma$], obtenemos la función coseno clásica. El lado más oscuro corresponde a los valores negativos.

Los valores del coseno cuando su argumento es un número real ([$\omega=0$])

Si recorremos el coseno por la recta imaginaria obtenemos el coseno hiperbólico. Es importante darse cuenta que por estos dos recorridos el coseno siempre proporciona un valor real.

Los valores del coseno cuando su argumento es un número imaginario ([$\sigma=0$])

Como era de esperar, al ser el arcocoseno la función inversa del coseno, si hacemos el recorrido del arcocoseno desde 0 hasta infinito, vamos visitando los argumentos cuyo coseno se mueve desde 0 hasta infinito.

Los valores del arcocoseno recorren los argumentos del coseno cuyo resultado es el argumento del arcocoseno. Son funciones inversas una de otra.

Los polinomios de Chebyshev

Los polinomios de Chebyshev se definen así: [$$C_n (x)=cos(n\ arccos(x) )$$] Para ver cómo son, observemos el recorrido de [$n\ arccos(x)$] sobre la función coseno. Es muy sencillo porque lo único que hacemos al multiplicar por [$n$] es ampliar fotográficamente [$n$] veces el recorrido del arcocoseno. En el siguiente diagrama usamos [$n=3$].

El polinomio de Chebyshev de orden tres se obtiene ampliando por tres el recorrido del arcocoseno (la gráfica de abajo) y, luego, realizar el coseno (las dos gráficas de arriba).

Ampliar tres veces el recorrido no cambia mucho el valor del coseno por la recta imaginaria. Lo hace más abrupto porque nos movemos más rápidamente hacia el infinito. En donde sí que hay un cambio es en la parte real donde tenemos tres cuartos de pi en vez de uno. Esto hace que se oscile en esa parte.

Recordemos que en estas rectas todos los valores del coseno son reales y que hay otra parte simétrica cuando [$t\lt 0$]. Con esto en mente podemos dibujar [$C_3$].

Polinomio de Chebyshev de orden tres.

Observando con cuidado el recorrido de arriba, vemos que atraviesa exactamente 3 ceros del coseno: el [$\pi/2$] y su simétrico en [$5 \pi/2$] y el [$3 \pi/2$] que es su propio simétrico. Además, no es casual que los puntos donde [$x=\pm 1$] tome el valor [$y= \pm 1$] ya que son los puntos de arcocoseno nulo.

Una manera fácil de calcular los polinomios de Chebyshev es la siguiente. [$$C_{n+1} (x)=cos(n\ arccos(x)+arccos(x) )=x C_n (x)+sin(n\ arccos(x) ) sin(arccos (x) )$$][$$ C_{n-1}(x)=cos(n\ arccos(x)-arccos(x) )=x C_n (x)-sin(n\ arccos(x) ) sin(arccos(x) )$$] Sumando se llega a [$C_{n+1} (x)+C_{n-1} (x)=2 x C_n (x)$] y despejando [$C_{n+1} (x)$] se obtiene la siguiente fórmula recursiva. [$$C_{n+1} (x)=2 C_n (x) - C_{n-1} (x)$$] Usando la definición se obtiene que [$C_0 (x)=1$] y [$C_1 (x)=x$] con lo que tenemos todos los datos para calcular el polinomio de Chebyshev del orden que queramos.

El filtro de Chebyshev

La función [$C_n^2 (\omega)$] es una buena aproximación de [$F^2 (\omega)$]. Dibujemos su gráfica para n=3.

El polinomio de Chebyshev de tercer grado al cuadrado como aproximación a [$F^2(\omega)$].

Para que cumpla los requisitos de un filtro hay que ajustarla un poco. [$$ F^2 (\omega)=\epsilon_p^2 C_n^2 \left(\frac{\omega}{\omega_p} \right)$$]

La función [$F^2(\omega)$] de un filtro de Chebyshev.

Así que un filtro de Chebyshev es el que tiene la siguiente respuesta en frecuencia al cuadrado. [$$ |H(j\omega) |^2=\frac{1}{1+\epsilon_p^2 C_n^2 \left(\frac{\omega}{\omega_p} \right)}$$] A partir de aquí procedemos como en el filtro de Butterworth. Calculamos [$\epsilon_s$], despejamos [$n$] para el orden; calculamos los polos de [$|H(s) |^2$] (este filtro no tiene ceros) y separamos los polos para obtener [$H(s)$].

Todo esto lo dejaremos para el lector que observará, entre otras cosas, que el orden requerido es menor en un filtro de Chebyshev que en un filtro de Butterworth para los mismos requisitos.

El lector curioso queda emplazado para explorar los filtros inversos de Chebyshev e intentar usar la misma técnica de inversión para los filtros de Butterworth.

Continúa y acaba en la cuarta parte.

Lo que nunca me enseñaron: Los filtros de Cauer (parte II)

2011-08-19T17:49:00.001+02:00

Parte 1 aquí.

El filtro de Butterworth

Aproximar la función [$F^2 (\omega)$] que debería valer 0 si [$\omega < \omega_p$] e infinito si [$\omega > \omega_s$] es muy sencillo. Todas las funciones monótonas (siempre crecientes) lo aproximan con más o menos éxito.

Una [$F^2 (\omega)$] muy usada es [$$F^2 (\omega)= \epsilon _p^2 \left(\frac{ \omega }{ \omega_p } \right)^{2n}$$] Este es el llamado filtro de Butterwoth. El número [$n$] es el orden del filtro. Debido a que debemos trabajar con polinomios, las potencias han de ser números naturales y, por tanto, el orden del filtro n debe ser un número natural. El orden del filtro está relacionado con el número de componentes eléctricos que va a tener nuestro circuito.

Construyamos su respuesta en frecuencia al cuadrado. [$$ |H(j\omega)|^2=\frac{1}{1+\epsilon_p^2 \left(\omega/\omega_p \right)^{2n}}$$] El filtrado de frecuencias que hace este filtro se muestra a continuación. Esta gráfica es la original del artículo de Butterworth de 1930 y representa [$|H(j\omega)|$] con [$\omega_p=1$].

Respuesta en frecuencia de un filtro de Butterworth tal cual aparecía en su artículo de 1930.

El valor [$\epsilon_p$] está explícitamente escrito en la ecuación, pero no sabemos nada de [$\epsilon_s$]. Hemos de usar la expresión de [$|H(j\omega) |^2$] para deducir qué valor tendremos para [$\epsilon_s$]. Bastará calcular la respuesta en frecuencia a la frecuencia [$\omega_s$]. [$$|H(j\omega_s ) |^2=\frac{1}{1+\epsilon_p^2 \left(\omega_s/\omega_p\right)^{2n}} = \frac{\epsilon_s^2}{1+\epsilon_s^2}$$][$$ \frac{1}{\epsilon_s^2}=\epsilon_p^2 \left(\frac{\omega_s}{\omega_p}\right)^{2n},\ \ \ \ \epsilon_s \epsilon_p=\left( \frac{\omega_p}{\omega_s}\right) ^n$$] Esta última expresión, muy simple gracias a la introducción de los épsilon en la parte anterior, relaciona el orden del filtro con los requisitos. Como el orden del filtro ha de ser un natural, es usual escribir la ecuación como una cota. [$$ n \ge \frac{log(\epsilon_s \epsilon_p)}{log \left( \frac{\omega_p}{\omega_s} \right) } $$]

Polos y ceros

La función [$|H(j\omega) |^2$] está relacionada con la respuesta en frecuencia del filtro [$|H(j\omega) |$] sin cuadrado, pero lo que nos interesa para poder implementar el filtro es la función de transferencia [$H(s)$] que abarca todos los complejos. Los pasos son los siguientes.

Primero, con un cambio de variables [$\omega=-js$], convertimos [$|H(j\omega) |^2$] en [$|H(s) |^2$]. [$$ |H(s)|^2=\frac{1}{1+\epsilon_p^2 \left(-js/\omega_p \right)^{2n}}$$]
A continuación, obtendremos la función [$|H(s) |^2$] como un cociente de dos polinomios. Escribiremos los polinomios factorizando sus raíces. [$$|H(s) |^2=A^2 \frac{\prod{s-s_{cero m} }}{\prod{s-s_{polo m} }}$$] Las raíces del numerador se llaman ceros porque cuando [$s$] sea un [$s_{cero}$], tendremos que [$|H(s) |^2=0$]. Las raíces del denominador se llaman polos porque cuando [$s$] tienda a un [$s_{polo}$], todo [$|H(s) |^2$] tiende a infinito. El por qué se llaman polos es obvio cuando se hace la gráfica en tres dimensiones.

Visión 3D de la función de transferencia de un filtro de Butterworth. Se observan los polos y la respuesta en frecuencia cuya parte positiva está remarcada en rojo.

Los filtros de Butterworth no tienen ceros. Esto ocurre porque el numerador de [$|H(s) |^2$] es uno. Pero sí tienen polos cuando el denominador se anula. Es decir, cuando [$F^2 (\omega)=-1$].[$$F^2 (-js_{polo} )=-1$$][$$\epsilon_p^2 \left(\frac{-js_{polo}}{\omega_p}\right)^{2n}=-1$$][$$\epsilon_p \left(\frac{-js_{polo}}{\omega_p}\right)^n=j$$][$$ \sqrt[n]{\epsilon_p}\frac{-js_{polo}}{\omega_p}=\sqrt[n]{j}$$][$$s_{polo}=\frac{j \omega_p}{\sqrt[n]{\epsilon_p}} \sqrt[n]{j}$$]
Usando las raíces de la unidad, llegamos a que los polos de [$|H(s) |^2$] yacen en un círculo. Como hay más de uno, los numeramos con un subíndice [$m$]. [$$s_{polo\ m}=\omega_p \epsilon_p^{\frac{-1}{n}} e^{j\left[\frac{p}{2}+\frac{p}{2n}+\frac{2p}{n} m\right]}$$] Es interesante localizar los polos en el plano de Argand (plano complejo). El siguiente diagrama muestra los polos de [$|H(s) |^2$] de un filtro de Butterworth de orden tres.

Distribución de los polos de la función de transferencia al cuadrado de un filtro de Butterworth de orden tres.

Obteniendo la función de transferencia

La simetría que aparece en el diagrama anterior es usual en [$|H(s) |^2$] y se llama simetría cuadrantal. Ocurre que [$$|H(s) |^2=|H(-s) |^2=|H(s^* ) |^2$$] por lo que la función [$|H(s) |^2$] queda completamente definida por lo que pase en sólo uno de sus cuadrantes. Esta simetría se usa para obtener [$H(s)$] a partir de [$|H(s) |^2$] mediante la siguiente ecuación: [$$|H(s) |^2=H(s)H(-s)$$] Recordemos que [$|H(s) |^2$] estaba descrita como un producto de polos y ceros. Entonces, podemos separar los polos que van para [$H(s)$] y los que van para [$H(-s)$].[$$ A^2 \frac{\prod{(s-s_{cero\ m})}}{\prod{(s-s_{polo\ m})}}=\left[A \frac{\prod{(s-s_{cero\ de\ H(s)\ m})}}{\prod{(s-s_{polo\ de\ H(s)\ m} )}}\right]\left[A \frac{\prod{(s-s_{cero\ de\ H(-s)\ m} )} }{\prod{(s-s_{polo\ de\ H(-s)\ m}) } }\right]$$] Lo que sí que hay que decidir es qué polos van para [$H(s)$] y qué polos van para [$H(-s)$]. Es fácil. Para que [$H(s)$] sea realizable físicamente y estable, hay que escoger los polos cuya parte real sea negativa. Y para que el filtro sea de fase mínima (menor dispersión) también cogeremos los ceros que tengan su parte real negativa.

Separación de los polos de [$|H(s)|^2$] que van para [$H(s)$] de los que van para [$H(-s)$].

Una vez tenemos [$H(s)$] podemos usar alguna de las técnicas de síntesis de circuitos para realizar el filtro.

Continúa en la parte tres.

Lo que nunca me enseñaron: Los filtros de Cauer (parte I)

2011-08-17T01:33:00.001+02:00

Introducción

Según cuenta Van Valkenburg (ver "Analog Filter Design" 1982, página 379), sobre 1935 los ingenieros de Bell Laboratories se llevaron una desagradable sorpresa. Su competencia alemana había sacado un teléfono al mercado que igualaba la calidad de sonido del suyo, pero usaba un inductor menos en los filtros.
En 1935 los inductores no eran lo que hoy. Un inductor pesaba su cuarto de kilo y costaba bastante. El que los alemanes hubieran conseguido eliminarlo sin deteriorar las características del dispositivo podría llevar la empresa americana a la ruina y no era época para tonterías con los alemanes.

Teléfono de 1930

Pero esa ruina no ocurrió. El inventor del método de diseño que hacía capaz ese ahorro, Wilhelm Cauer, estaba necesitado de dinero (supongo) y quiso vender sus patentes. Para eso dio unas conferencias y los muy avispados matemáticos de Bell Laboratories tomaron nota. Una familia de funciones matemáticas se mencionó varias veces: las funciones elípticas de Jacobi.

Cuenta la leyenda que durante las dos semanas siguientes el departamento entero de matemáticas de Bell Laboratories se encerró en la biblioteca pública de Nueva York, estudiando tales funciones. Si mal no recuerda Darlington, que lo sufrió en sus propias carnes, allí encontró el artículo original de Jacobi de 1829 escrito en latín. En él estaba todo: tablas, transformaciones, aproximaciones… ¡todo!

A fin de cuentas, Cauer fue estudiante de Hilbert en Göttingen. Dada la prominencia del maestro, seguramente había visto de sobra estas funciones elípticas y, simplemente, les había encontrado otra aplicación. Por ese motivo, a este tipo de filtros se los denomina filtros elípticos o filtros de Cauer.

David Hilbert y Wilhelm Cauer

Los filtros

Un filtro eléctrico no es más que un dispositivo que toma una señal eléctrica como la del teléfono y elimina algunas frecuencias. De esta manera podemos oír la voz sin los ruidos raros del ADSL introduciendo un filtro que elimine las frecuencias que usa el ADSL. Lógicamente, podremos usar otro filtro para quedarnos con el ADSL y quitar la voz. Así que, por un mismo cable y gracias a un par de filtros, tengo voz y datos.

Splitter de ADSL que no es más que un filtro para que no se oiga el ruido de los datos de ADSL en el audio del teléfono.

Esta no es más que una de las aplicaciones de los filtros. Hay muchísimas más: multiplexar, eliminar el aliasing, hacer efectos de sonido y ecualizar, compensar desfases, modular, demodular… y un sinfín más que no vamos a enumerar aquí porque lo que nos interesa es el trasfondo teórico de los filtros.

La función de transferencia y la respuesta en frecuencia

La forma que tienen los filtros de procesar las señales es mediante una función de transferencia [$H(s)$]. Esta función está definida en los números complejos y, para que pueda ser construida físicamente, ha de ser racional (P y Q son polinomios). [$$H(s)=\frac{P(s)}{Q(s)}$$] La magnitud de la función de transferencia en el eje imaginario es la respuesta en frecuencia. Esta respuesta es lo que nuestro filtro multiplicará a la amplitud cada frecuencia. Si su valor a una frecuencia es mayor que uno, esa frecuencia se amplifica. Si es menor que uno, se atenúa. Escribiremos esta magnitud así:[$$|H(j\omega)|$$] Donde [$\omega$] no es más que [$2\pi$] veces la frecuencia ([$\omega=2\pi f$]) para no tener que escribir [$2\pi$] cada vez que vayamos a usar un seno, coseno o exponencial compleja. La [$j$] es la constante imaginaria que, en ingeniería, se usa para no confundirla con la intensidad de corriente [$i$].

Es importante señalar aquí que para realizar el filtro necesitamos la función [$H(s)$] con [$s$] en todo el plano complejo, pero la respuesta en frecuencia que deseamos es sólo esa función en la recta imaginaria [$|H(j\omega)|\ \ $]. Gran parte del problema estriba en pasar de [$|H(j\omega)|\ \ $], lo que queremos, a [$H(s)$], cómo hacerlo.

Pero primero veamos qué queremos.

El filtro ideal y los filtros reales

Nos interesaría que la respuesta en frecuencia fuera ideal: todo lo que haya por encima de una frecuencia de corte [$\omega_c$] se elimina (se multiplica por 0 en la banda de rechazo) y todo lo que haya por debajo se preserva (se multiplica por 1 en la banda de paso). Eso significa que el [$|H(j\omega)|$] ideal tendría esta forma:

Un filtro ideal que elimina las frecuencias de la banda de rechazo y deja intactas las frecuencias de la banda de paso.

Sin embargo, esto no es posible porque las únicas funciones de transferencia que podemos realizar eléctricamente son funciones racionales (recordemos: cocientes de dos polinomios) y son funciones continuas excepto en asíntotas verticales. No es posible hacer el escalón discontinuo que vemos en la gráfica de arriba. Hay que transigir y permitir no tener exactamente un 1 o un 0 (a esto se le denomina rizado) y dejar una banda de transición entre las bandas de paso y de rechazo.

Forma de un filtro real donde se han especificado los requisitos del mismo: frecuencia de paso [$\omega_p$], frecuencia de rechazo [$\omega_s$], rizado de paso [$r_p$] y rizado de rechazo [$r_s$].

Ya no tenemos una frecuencia de corte, sino una frecuencia de paso [$\omega_p$] por debajo de la cual las frecuencias no se van a tocar mucho (entre [$1$] y [$r_p$]) y una frecuencia de rechazo [$\omega_s$] por encima de la cual no van a sobrevivir muchas frecuencias (como mucho se multiplica por [$r_s$] que será todo lo cercano a cero posible).

Nota: El subíndice s viene del inglés stopband.

Complicando para simplificar

Como vemos, todo el rango de trabajo está entre el [$0$] y el [$1$]. Si elevamos al cuadrado, seguimos estando entre [$0$] y [$1$]. Esto permite trabajar con la magnitud al cuadrado que es más sencilla de calcular y siempre es real positiva. [$$ |H(j\omega)|^2=H(j\omega) H^*(j\omega)=H(j \omega )H(-j \omega )$$] El asterisco indica complejo conjugado. La última igualdad saca provecho a que [$H(s)$] es racional con coeficientes reales y, por tanto, su parte imaginaria ha de ser hermítica.

Trabajar entre [$0$] e infinito es también más sencillo. ¿Por qué? Si el límite es el [$1$], nos podemos pasar de [$1$] y eso sería erróneo. Nos tendríamos que dedicar a comprobar que nuestros cálculos nunca superasen el uno y los complicaría. En cambio, si el límite es infinito, ¡no hay límite! Los cálculos no tienen necesidad de asegurar que haya un límite y se simplifican.

Forzaremos que la función [$|H(j\omega)|^2$] tenga esta forma: [$$ |H(j\omega)|^2=\frac{1}{1+F^2 ( \omega )}$$]Ahora, la función [$F^2 ( \omega )$] no tiene límite superior. A cambio, hemos de recalcular los rizados.

La misma respuesta en frecuencia de antes, pero con la transformación mencionada para trabajar entre [$0$] e infinito. Hay que hacer notar cómo se han modificado los parámetros que especificaban los rizados.

Estos nuevos parámetros [$\epsilon_s$] y [$\epsilon_p$] se relacionan con los rizados originales así: [$$r_p=\sqrt{\frac{1}{1+\epsilon_p^2}},\ \ \ \ r_s=\sqrt{\frac{\epsilon_s^2}{1+ \epsilon _s^2}}$$] Llamaremos a [$\omega_p,\epsilon_p,\omega_s$] y [$\epsilon_s$] los requisitos del filtro.

Hay que destacar que la función [$F^2 (\omega)$] sigue siendo una función racional y deberá ser el cociente de dos polinomios.

Continúa en parte dos.

miniSL parte 14 - La Evaluación

2011-08-01T20:32:00.000+02:00

Retomamos el lenguaje de script miniSL. Hasta ahora hemos definido los datos sobre los que vamos a tratar (las celdas) y hemos implementado las operaciones básicas sobre ellos: creación y destrucción. También hemos destacado algunos datos como el entorno global.

Ahora vamos a implementar la principal operación a realizar sobre los datos: tomar una celda que represente una expresión y calcular su valor (que será otra celda). Esto es lo que se llama la evaluación.

Existen varios modelos de evaluación. Aquí nos centraremos en la evaluación por entornos (se explica aquí y aquí). Este tipo de evaluación es realmente sencilla: si queremos saber el valor de una variable, hemos de buscarla en el entorno actual. Si no, buscamos en el entorno padre y así sucesivamente. Esto lo hace la función FindName() que se vio en la parte 10.

La evaluación de literales es inmediata: representan su propio valor (el 5 es el 5, la cadena “hola” es la cadena “hola”). La evaluación de combinaciones (aplicaciones de una función a argumentos) procede de la siguiente manera.

Se evalúa el operador (la función).
Se envían los operandos sin evaluar a la función.

Como hay dos tipos de funciones: la definida por el usuario y la nativa, tendremos que contemplar ambos casos. En principio, la definida por el usuario evaluará los operandos; pero veremos que las nativas necesitan sus operandos sin evaluar (en las partes 29,30 y siguientes).

La evaluación de una lista es la lista de sus miembros evaluados. Así, [1+2,5] es la lista [3,5]. La lista vacía es precisamente un literal porque no hay que evaluar nada para calcular su valor.

Cualquier otra celda no es considerada expresión y genera un error de ejecución.

El código de la función de evaluación es el siguiente:

CELL& Script::Evaluate(CELL& c, CELL& envir)
{
 CELL* aux;
 switch(c.type)
 {
  //Non evaluable
 case UNUSED: throw L"Evaluating an unused cell";
 default:  throw L"Evaluating an unknown cell";
 case LAMBDA_VAL:throw L"Evaluating a lambda value";
 case NATIVE_VAL:throw L"Evaluating a native";
 case ENVIR_VAL: throw L"Evaluating an environment";

  //Literals
 case INT_LIT: case BOOL_VAL: case STRING_LIT: case EMPTY_LIT:
  return c;

  //Code constructors
 case CONS_CTOR:  return CreateCell(CONS_CTOR, &Evaluate(*c.head, envir), &Evaluate(*c.tail, envir));

 case NAME_CODE: 
  if((aux=FindName(c, envir))==NULL)
   throw L"Unknown name";
  return *aux;

 case COMBINE_CODE:
  switch((aux=&Evaluate(*c.op, envir))->type)
  {
  case LAMBDA_VAL: return ApplyLambda(*aux->code, *c.operands, *aux->closure, envir);
  case NATIVE_VAL: return aux->native(*this, *c.operands, envir);
  default:   throw L"Non-combinable value";
  }
 }
}

Lo más complejo es la evaluación de la combinación. Esto es debido a los casos antes mencionados. Cuando tenemos una operación nativa, directamente llamamos a la función que la implementa. Si tenemos una operación definida por el usuario (lambda) usaremos una función auxiliar ApplyLambda() que veremos en la siguiente parte de esta serie.

The vessel with the pestle

2011-07-09T10:56:00.000+02:00

Como me he tomado algunas vacaciones, estoy buscando y viendo algunas de las películas que me gustaron de niño. Las veo en versión original para practicar el inglés. Realmente me he encontrado con algunas sorpresas muy agradables. Por ejemplo, he encontrado esta joya.

Activad los subtítulos donde pone CC.

Algunas palabrejas poco usuales del inglés que se usan en este contexto son:

Vessel: vasija
Pestle: mortero
Pellet: pastilla
Flagon: jarra
Brew: brebaje

Números binarios en C++

2011-06-29T11:25:00.000+02:00

En C++ (y en C y en otros muchos lenguajes de programación) hay tres formas de escribir números enteros literales.

En base 10 (decimal) cuando escribo algo como 1042348
En base 16 (hexadecimal) cuando prefijo 0x como en 0x3FFF
En base 8 (octal) cuando prefijo sólo 0 como en 0663

Cuando se programa en bajo nivel muchas veces es más directo escribir directamente en base 2 (binario), ¿pero cómo? Me he topado con la siguiente macro que lo consigue

#define Ob(x)  ((unsigned)Ob_(0 ## x ## uL))
#define Ob_(x) (x & 1 | x >> 2 & 2 | x >> 4 & 4 | x >> 6 & 8 |  \
 x >> 8 & 16 | x >> 10 & 32 | x >> 12 & 64 | x >> 14 & 128)

El truco se basa en dos pasos, el primero Ob (no es un cero, es una o) pone delante un 0 (que sí es un cero) y detrás un "uL". El "uL" es la forma que tenemos de decirle al C++ que el número es sin signo y largo. El cero, por otra parte, sí que es importante ya que nos va a convertir el número a octal. Lo que tenemos entonces es un número binario interpretado como un número octal. ¿Cómo afecta eso a su valor?

Un número binario se expresa de la siguiente forma [$$ n=\cdots + d_3 2^3 + d_2 2^2 + d_1 2^1 + d_0 2^0 $$] donde los [$d_i$] son los dígitos. Los dígitos serán o cero o uno. Al escribir el número binario como octal lo que hacemos es [$$ n=\cdots + d_3 8^3 + d_2 8^2 + d_1 8^1 + d_0 8^0 $$] pero aún con los dígitos en binario. Así que lo único que necesitamos es leer los bits de tres en tres ya que [$8=2^3$]. Justamente eso es lo que hace Ob_.

Por ejemplo:
Ob(1001) //Como binario es 9 en decimal
Ob_(01001uL) //Como octal es 513 en decimal y 1_000_000_001 en binario
9 //Tomando un bit de cada 3 en el 513

Clasificación de los bugs

2011-06-23T11:12:00.000+02:00

Leyendo a Walter Bright me he encontrado con la palabreja "heisenbug" que según él es un tipo de bug. Ya me imaginaba yo que tendría que haber una taxonomía de los bugs. El resumen de lo que he encontrado es este:

Bohrbug: Error sistemático que se da siempre cuando las condiciones lo propician.
Mandelbug: Error sistemático tan complejo que no parece sistemático, pero lo es.
Heisenbug: Error sistemático que desaparece cuando intentamos depurarlo. Ya sea por que estamos usando el depurador y cambia la estructura de la memoria, porque el código está compilado en modo de depuración o por otras razones.
Schrödinbug: Error oculto que, una vez descubierto, todo el mundo se tropieza con él.
Estadístico: Error que no se detecta en una única ejecución del programa, sino que hay que hacer una estadística de los resultados hasta darnos cuenta que no son como deberían ser. (Esto me recuerda a la minería de datos en los MMORPG)
Alfa bug: Error que ves una vez y no vuelves a ver. Lo que ocurría antiguamente cuando un rayo cósmico le daba a una celda de memoria.

Supongo que luego están los errores de condiciones de carrera, que aparecen cuando les da la gana si no se han sincronizado bien las hebras. Ya inventarán una palabreja para eso algún día.

El lío de las composiciones

2011-06-17T10:41:00.000+02:00

La composición en las relaciones

Una relación [$\le$] entre [$A$] y [$B$] es un subconjunto del conjunto cartesiano.[$$\le \subseteq A\times B$$]Cuando dos elementos [$a\in A$] y [$b\in B$] están relacionados escribimos [$$ a \le b \Leftrightarrow (a,b)\in \le$$] La composición de dos relaciones [$\le_1$] entre [$A$] y [$B$]; y [$\le_2$] entre [$B$] y [$C$] es [$\le_1 \circ \le_2$] definida así [$$ a \le_1\circ \le_2 c \Leftrightarrow \exists b\in B.a\le_1 b\le_2 c $$] Es interesante ver el parecido natural entre [$$ a \le_1\circ \le_2 c$$] y [$$ a\le_1 b\le_2 c $$] como si el [$\circ$] representase un elemento indefinido a buscar.

La composición en las funciones

Una función [$f:A\to B$] no es más que una relación en la cual [$$\forall a\in A.\exists ! b\in B. a f b $$] Para los que no lo hayan visto nunca [$\exists !$] significa "existe un único".
Bien, los problemas empiezan porque si existe un único [$b$] lo natural es representarlo por [$f$] y [$a$]. La forma de hacerlo es esta: [$$f(a)=b \Leftrightarrow a f b$$] ¿Por qué es problemático? Porque si pienso que una función es una relación y defino la composición de funciones como una composición de relaciones obtenemos [$$ (f\circ g)(a)=g(f(a)) $$] Invirtiéndose el orden de [$f$] y [$g$], lo que lía muchísimo. Así que lo que se hace es definir al revés la composición de funciones. [$$ (f\circ g)(a)=f(g(a)) $$] Por lo que deja de ser igual que la composición de relaciones.

Soluciones

Las que se me ocurren así a bote pronto son:

Usar una notación postfija para las funciones [$(a)f$] en vez de [$f(a)$]. De esta manera [$ (a)(f\circ g) =((a)f)g$] y el orden coincide con la composición de relaciones.
Invertir una de las dos composiciones. O bien [$ (f\circ g)(a)=g(f(a)) $] o bien [$ a \le_2\circ \le_1 c \Leftrightarrow \exists b\in B.a\le_1 b\le_2 c $]. Hagas lo que hagas, estás invirtiendo el orden natural de la notación y vas a liarte (el elemento [$a$] va primero a [$f$] y a [$\le_1$] que están lejos de él).
Usar dos notaciones. Por ejemplo, usar [$\le_1 ; \le_2 = \le_2 \circ \le_1$] y [$ f \circ g = g ; f $]. Esta solución la suele usar alguno que otro autor.
Definir las funciones al revés, [$\forall a\in A.\exists ! b\in B. b f a $] de forma que [$b=f(a) \Leftrightarrow b f a$]. Claro que también así vamos en contra de unos cuantos siglos de historia y habría que darle la vuelta a muchas definiciones como relaciones inyectivas.

Exponenciando la derivación

2011-06-09T11:29:00.000+02:00

Realmente para definir la exponencial (o cualquier otra función analítica) mediante una serie de potencias hacen falta pocas cosas.

Una operación de multiplicación por escalar
Una operación de suma
Una operación de potencia

Con estas tres operaciones podemos definir
[$$ e^x = \sum_{k=0}^\infty \frac{x^k}{k!} $$]
Los operadores lineales cumplen todas estas condiciones tomando la potencia como composición iterada.
[$$f^0=Id; f^{n+1}=f\circ f^n$$]
Un caso clásico es cuando las operaciones lineales están representadas por matrices.
Otro de estos operadores lineales es la derivación, que escribiremos [$D$]. Se puede realizar la exponencial de la derivación.
[$$e^D = \sum_{k=0}^\infty \frac{D^k}{k!} $$]
Para ver mejor sus efectos, aplicaremos el resultado de [$\alpha$] veces esta exponencial sobre [$x^n$].
[$$e^{\alpha D} x^n = \sum_{k=0}^\infty \frac{\alpha^k D^k}{k!} x^n $$]
Podemos derivar hasta [$n$] veces [$x^n$]
[$$\sum_{k=0}^n \frac{n! \alpha^k x^{n-k} }{k! (n-k)!}$$]
Es interesantísimo ver que lo obtenido es justamente el binomio de Newton.
[$$ \sum_{k=0}^n \frac{n! \alpha^k x^{n-k} }{k! (n-k)!} = (x+\alpha)^n $$]
Debido a que estamos trabajando con operadores lineales, podemos volver a usar una serie de potencias para aplicar la exponencial de la derivación sobre una función analítica arbitraria.
[$$ (e^{\alpha D} f)(x) = e^{\alpha D} \sum_{i=0}^\infty {a_i x^i} = \sum_{i=0}^\infty {a_i e^{\alpha D} x^i} = \sum_{i=0}^\infty {a_i (x+\alpha)^i} = f(x+\alpha) $$]
Así que la exponencial de la derivación no es más que una traslación.
Los físicos me dicen que acabo de descubrir que el operador de momento genera las traslaciones. ¡Vaya! Pues no lo sabía.

Espacios proyectivos

2011-05-26T15:53:00.001+02:00

Espacio Vectorial	Espacio Proyectivo
[$\mathbb{R}^2$]	[$P(\mathbb{R})$]
Los elementos de [$\mathbb{R}^2$], en coordenadas cartesianas, son pares de números reales [$(x,y)$] que representan puntos.	Los elementos de [$P(\mathbb{R})$], en coordenadas homogéneas, son pares de números reales [$(x,y)$] que representan rectas que pasan por el origen.

Dos puntos [$P=(x,y)$] y [$P'=(x',y')$] son iguales si y sólo si [$$x=x',\ y=y'$$] y lo escribiremos [$P=P'$].	Dos puntos [$P=(x,y)$] y [$P'=(x',y')$] están en la misma recta si y sólo si existe un [$k\in\mathbb{R}$] tal que [$$x=kx',\ y=ky'$$] y lo escribiremos [$P\equiv P'$].
[$$\mathbb{R}^2=\{(x,y)∣x,y\in\mathbb{R}\}$$]	[$$P(\mathbb{R})=(\mathbb{R}^2-\{(0,0)\})/\equiv $$] Si [$x=y=0$] no tenemos una recta por eso se ha excluido el punto [$(0,0)$] que no forma una recta.
Cada punto tiene dos grados de libertad, la abscisa [$x$] y la ordenada [$y$].	Cada recta sólo tiene un grado de libertad. La equivalencia entre rectas [$\equiv$] le quita un grado de libertad a [$(x,y)$] (precisamente, es el valor de [$k$] que hemos de hallar).
Usar una matriz para transformar puntos en otros genera aplicaciones lineales. [$$P'=AP$$]	Usar una matriz para transformar rectas en otras genera colineaciones. [$$P'≡AP$$] Es decir, existe un [$k\in\mathbb{R}$] tal que [$$P'=kAP$$]
Una matriz tiene cuatro grados de libertad cuando representa una aplicación lineal.	Una matriz tiene tres grados de libertad cuando representa una colineación.

Si la matriz es regular (no singular, con determinante no nulo), la transformación lineal es invertible.	Si la matriz es regular, la colineación se denomina homografía y representa proyecciones cónicas.
Al ser invertible forma un grupo. Concretamente el [$GL(2,\mathbb{R})$].	Al ser invertible forma un grupo. Concretamente el [$PGL(2,\mathbb{R})$].
	Es posible y deseable normalizar los puntos. Una forma de hacerlo es elegir de cada recta el punto cuya última coordenada sea uno. En este caso [$y=1$]. Esto se consigue eligiendo [$k$] adecuadamente. [$$(x,y)≡k(x,y)=\frac{1}{y}(x,y)=(\frac{x}{y},1)$$]
	Se comprueba con facilidad que esta normalización es una proyección perspectiva donde la línea [$y=1$] es el plano de proyección.
Todo esto se puede extender a 3 dimensiones usando [$\mathbb{R}^3$].	Todo esto se puede extender de proyectar en una línea en [$P(\mathbb{R})$] a proyectar en un plano en [$P^2(\mathbb{R})$]. Este plano sería, por ejemplo, la pantalla del monitor o el CCD de una cámara.

miniSL parte 13 - El entorno global

2011-05-23T14:59:00.000+02:00

En la parte anterior de esta serie hablamos del entorno global como conjunto raíz del recolector de basura. El código relacionado está en la parte octava de esta serie, en la función GarbageCollect(). También dijimos que el entorno global no es más que una celda destacada.

CELL* m_GlobalEnvir;

La creación de esa celda se va a realizar cuando iniciemos todo el sistema del lenguaje script. En el constructor de la clase Script.

Script() : m_FirstUnused(NULL) { m_GlobalEnvir=&CreateEnvir(NULL); }

Recordemos que m_FirstUnused se usaba para reutilizar las celdas recicladas por el recolector de basura.

Lo importante es que m_GlobalEnvir no va a cambiar y siempre va a ser un entorno. Vimos la función CreateEnvir() en la parte 11. En la parte 6 explicamos que una celda de entorno (de tipo ENVIR_VAL) sólo tiene un puntero a una tabla hash o árbol de búsqueda así que, como lo que vamos a hacer con este entorno es definir símbolos en él, sera muy útil obtener directamente la tabla del entorno global.

ENVIR_TABLE& GlobalEnvirTable()const { return *m_GlobalEnvir->envir_table; }

La mayor parte de símbolos que vamos a definir en la tabla del entorno global son operaciones nativas. La función DefineGlobalNative() nos ahorra tener que llamar a CreateName() y CreateNative() cada vez.

void DefineGlobalNative(STRING const& name, NATIVE nat)
 {
  (*m_GlobalEnvir->envir_table)[&CreateName(name)]=&CreateNative(nat);
 }

Finalmente, poblaremos la tabla del entorno global con la función DefineUsualSymbols(). Se declara así en la clase Script.

void DefineUsualSymbols();

Y se define así.

void Script::DefineUsualSymbols()
{
 DefineGlobalNative(L"=", &Native_Set);

 DefineGlobalNative(L"+", &Native_Add);
 DefineGlobalNative(L"-", &Native_Sub);
 DefineGlobalNative(L"*", &Native_Mul);
 DefineGlobalNative(L"&", &Native_BAnd);
 DefineGlobalNative(L"|", &Native_BOr);
 DefineGlobalNative(L"^", &Native_BXor);

 DefineGlobalNative(L"/", &Native_Div);
 DefineGlobalNative(L"%", &Native_Mod);

 DefineGlobalNative(L"==", &Native_Eq);
 DefineGlobalNative(L"!=", &Native_Ne);
 DefineGlobalNative(L"<", &Native_Lt);
 DefineGlobalNative(L"<=", &Native_Le);
 DefineGlobalNative(L">", &Native_Gt);
 DefineGlobalNative(L">=", &Native_Ge);

 DefineGlobalNative(L"if", &Native_If);
 DefineGlobalNative(L"let", &Native_Let);
 DefineGlobalNative(L"while", &Native_While);
 DefineGlobalNative(L"begin", &Native_Begin);
 DefineGlobalNative(L"define", &Native_Define);
 DefineGlobalNative(L"set", &Native_Set);
 DefineGlobalNative(L"lambda", &Native_Lambda);

 (*m_GlobalEnvir->envir_table)[&CreateName(L"true")]=&CreateBool(true);
 (*m_GlobalEnvir->envir_table)[&CreateName(L"false")]=&CreateBool(false);
}

La mayoría de estas funciones nativas (hemos prefijado el nombre con Native_ para distinguirlas claramente) todavía no están definidas. Lo haremos en las partes de la 26 a la 31.
Antes nos vamos a dedicar a la evaluación, puesto que tenemos ya especificado todo lo que hace falta para explicarla.

El punto de la pereza

2011-05-11T10:41:00.002+02:00

Hace unos días Bob Harper, que defiende SML con uñas y dientes, se dedicó a atacar a los elitistas del Haskell. Su idea era muy sencilla: los tipos de Haskell no son inductivos. Voy a intentar explicar esto de forma sencilla.

Tipos inductivos

Son los tipos cuyos valores se construyen con unos valores bases y unos constructores. El caso arquetípico son los números naturales.

El 0 es un valor base.
El siguiente número natural S(n), es un constructor que, dado un número, construye otro.

Con esto y la inducción estructural tenemos los números naturales (y podemos demostrar propiedades sobre ellos).

El cero es 0
El uno es S(0)
El dos es S(S(0))
Y así.

También es posible usar como argumento de un constructor el valor de otro tipo. Este otro tipo será un parámetro del nuevo tipo. De esa manera aterrizamos en los tipos algebraicos. Por ejemplo, las listas de valores de un tipo T que llamaremos L(T) será.

La lista vacía [] es un valor base.
El constructor de lista cons(V,R) toma un valor V de un tipo T y el resto de la lista R de tipo L(T).

Con esto y la inducción estructural, obtenemos las listas que queramos (y podemos demostrar propiedades sobre ellas).

Tomamos la lista vacía [] como valor base de una lista de enteros L(int)
Añadimos un entero cons(-3, [])
Añadimos otro entero cons(7, cons(-3, []) )

Todos estos tipos inductivos tienen una forma muy similar si se dibujan: son bosques de árboles (matemáticamente son órdenes parciales completos, también llamados dominios). En concreto, los números naturales son un árbol de una única rama.

Los números naturales son inductivos. El valor base es el 0, en un círculo, y el constructor es S(n), en rectángulos. De esta manera tenemos representados en la figura, de abajo arriba, los valores 0, S(0), S(S(0)), S(S(S(0))) y así sucesivamente.

Los booleanos son dos árboles sin ramas.

Los booleanos son dos valores base: true y false. No hay constructores. Estos tipos sin constructores suelen llamarse tipos enumerados.

Las listas de naturales son árboles con infinitas ramas ya que, cada vez que usamos un constructor con un natural distinto, generamos una nueva rama. Es difícil dibujar esto porque cada una de las infinitas ramas lleva a infinitos valores que, a su vez, vuelven a tener infinitas ramas. Con un poco de imaginación el diagrama sería algo así.

Lista de naturales. La lista vacía es el valor base [] que está abajo. A partir de él construimos infinitos valores, uno para cada natural. Serían las listas de un único natural. Asimismo, de cada uno de estos valores se obtienen otros infinitos valores. A este tipo de árboles infinitos pero con una estructura simple se los denomina árboles regulares.

Existen también los llamados tipos coinductivos en los cuales, en vez de tener una lista vacía (valores base) y usar constructores sobre ella, tenemos una lista llena (valores co-base) y usamos destructores (co-constructores) sobre ella. No hablaré mucho más de esto aquí.

Evaluación perezosa

La evaluación perezosa, de la que hablamos alguna que otra vez, consiste básicamente en no evaluar hasta que no sea estrictamente necesario. Un caso clásico es la multiplicación por cero.

0*(7+5)

¿Para qué sumar siete y cinco si sabemos que al final la multiplicación va a ser cero? Bueno, existe un motivo por el que evaluar los argumentos y son los efectos laterales. Si en vez de sumar dos números imprimiésemos un mensaje, la cosa cambia.

0*(print "hola")

Ahora sí que habría que imprimir "hola" aunque el resultado de esta multiplicación (si es que print devuelve un número, claro) sea cero. Pues bien, ocurre que en Haskell no hay efectos secundarios. Es un lenguaje funcional. En este lenguaje de programación sí que conviene no perder tiempo evaluando cosas que, al final, no se van a usar.

La idea fundamental de la crítica de Harper es que siempre existen los efectos secundarios. En concreto existe un efecto secundario que jamás puedes quitarte de encima en un lenguaje de programación Turing completo. Ese efecto es... que la computación no termine.

Imaginemos el siguiente programa:

f(x) = 1+f(x) //Esta computación no termina
0*f(3)

Si el lenguaje es estricto y evalúa f(3), nunca llega a ejecutar la multiplicación. Si el lenguaje es perezoso y no evalúa f(3), la multiplicación ha aceptado un valor que no es un número (de hecho ni siquiera es un valor, es no terminación) y lo ha tratado como si fuera un número. ¿Cuál es el tipo del argumento que ha aceptado la multiplicación?

Los lenguajes con evaluación perezosa cuelan entre los valores de sus tipos la no terminación. O mejor dicho, algo todavía sin evaluar que puede ser no terminación o puede ser un valor concreto. Este valor tan especial que se puede convertir en otro (o no) se corresponde con el mínimo de un orden parcial completo con mínimo. Este mínimo tiene el nombre de "punto" y se suele representar con el símbolo [$\bot$].

Si añadimos el punto a los tipos inductivos el resultado es que ¡no son inductivos! Los naturales y los booleanos quedan algo así.

Los naturales y booleanos con punto. El punto representa la no evaluación (con la no terminación como posibilidad). El punto está más allá de la inducción. No se pueden usar técnicas inductivas para demostrar propiedades de él.

Esto rompe la posibilidad de usar la inducción estructural porque el punto queda más allá, más arriba, del resto de valores. Así que, según Harper, usar la evaluación perezosa es equivalente a olvidarse de la inducción estructural y, con ella, poder demostrar con facilidad múltiples propiedades en nuestro programa.

Epílogo

Por supuesto, esto es todo cuestión de compromisos. Usar evaluación perezosa abre la puerta a tener tipos coinductivos con mucha facilidad. De hecho la "lista llena" de la que hablé antes es precisamente el punto [$\bot$]. Una computación que puede no terminar, una lista infinita, de la cual vamos extrayendo valores, como los iteradores. Esto permite cosas nuevas como el uso de la composición en estos tipos coinductivos, lo que abre la posibilidad a la reutilización de código.

La multiplicación de Gauss

2011-05-02T14:05:00.000+02:00

¿Cómo realizar una multiplicación compleja usando sólo tres productos reales?

La multiplicación usual requiere cuatro:
[$$ (a+bi)(c+di) = ac-bd + (ad+bc)i $$]
El truco lo descubrió Gauss por 1805
[$$ ac-bd = ac +bc -bc -bd = c(a+b) - b(c+d) $$]
[$$ ad+bc = ad +ac-ac +bc = c(a+b) +a(d-c) $$]

Como vemos, se reusa la multiplicación [$c(a+b)$].

Esto me lleva a recordar el algoritmo de Strassen para multiplicar matrices, pero ese es otro tema.

Transformación CPS

2011-04-29T21:05:00.001+02:00

Hace algún tiempo hablamos de las continuaciones. Además, dimos una semántica operacional para ellas. Ahora vamos a describir cómo se transforma un programa para que use continuaciones en todas sus llamadas a función. Esto es el estilo de paso de continuaciones (CPS) que permite eliminar la necesidad de usar una pila de llamadas. Es decir, la cadena dinámica.

El estilo de paso de continuaciones (CPS)

Para empezar, veamos cómo es eso del CPS. Supongamos la siguiente expresión.
[$$ f(g(a)) $$]
Lo primero que calculamos es el valor de [$a$]. Luego, el valor de [$g(a)$] y, finalmente, el valor de [$f(g(a))$]. El estilo CPS añade un argumento adicional a cada función que es la continuación, a la que le pasaremos el resultado cuando la función termine.

¿A dónde pasábamos el resultado de [$g(a)$]? A [$f$]. Así que, al hacer [$g$] CPS, la expresión de arriba queda
[$$ g(f, a) $$]
y se leería algo así como "calcula [$g(a)$] y pásale el resultado a [$f$]. El problema es que también tenemos que hacer CPS a [$f$] por lo que ahora [$f$] no toma un argumento, toma dos: la continuación y su argumento propiamente dicho. La solución es añadir una función anónima. La expresión de arriba con tanto [$g$] como [$f$] puestas en CPS sería así:
[$$g(\lambda x.f(k,x), a)$$]
El detalle es que [$k$] es la continuación de la expresión, que no sabemos cuál es porque no he dicho qué vamos a hacer después de calcular [$f(g(a))$]. Para destacar claramente que [$k$] es la continuación, que [$f(g(a))$] es la expresión original y que [$g(\lambda x.f(k,x), a)$] es la expresión transformada a CPS, vamos a usar la siguiente notación:
[$$ T\ [\ f(g(a))\mid k\ ]\ = g(\lambda x.f(k,x), a) $$]

La transformación de Plotkin

Bastará conocer las reglas de la transformación [$ T\ [\ ]$] para poder realizarla. Esto es a lo que se dedicó Plotkin en 1975 en el artículo "Call-by-name, call-by-value and the [$\lambda$]-calculus", aunque ha llovido mucho y la versión que presento aquí es bastante distinta a la original.

Lo primero que necesitamos es definir el lenguaje que vamos a transformar. Vamos a usar una variante del lambda cálculo sin currificar. Es muy sencilla: un valor es o bien una variable o bien una función anónima.
[$$ v::= x \mid \lambda (x_1,...,x_n).e $$]
Una expresión es o bien un valor o bien una aplicación (llamo [$s$] a las aplicaciones).
[$$ e::= v \mid s $$]
También llamaremos, [$k$] a una expresión. Una aplicación no es más que una llamada a función.
[$$ s::= e_0 (e_1,...,e_n) $$]
Para transformar un programa escrito con esta sintaxis hemos de dar la transformación para cada una de estas construcciones sintácticas. Si lo que tengo un valor, ya está calculado, sólo he de pasarlo a la continuación. ¡Pero ojo! Si es una función he de transformarla antes en CPS. De esto se va a encargar la transformación auxiliar [$ M[\ ]$].

Regla P-TV: [$ T\ [\ v\mid k\ ]= k(M[\ v\ ])$]

La transformación auxiliar es bien sencilla: si no es una función no hace nada, si es una función le añade el argumento de la continuación y transforma su cuerpo.

Regla P-MX: [$ M\ [\ x\ ]=x $]
Regla P-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid x\ ] $]

Finalmente, si lo que tenemos es una aplicación, vamos calculando su operador y argumentos hasta que, al final, podamos llamar a la función.

Regla P-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]=T[\ e_0 \mid \lambda x_0.T[\ e_1 \mid \lambda x_1.\ ...T[\ e_n \mid \lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]

Va a ser muy habitual encontrarnos con transformaciones anidadas del tipo [$...T[\ e\mid\lambda x.T[...$] ya que representan una secuencia de operaciones. El resultado de [$e$] se pasa a la continuación que empieza por [$\lambda x...$] lo que hace guardar el resultado de [$e$] en [$x$] y proseguir con la ejecución de la secuencia. Para facilitar la comprensión de una expresión en CPS vamos a poner como subíndice de una variable la expresión cuyo valor guarda.

Bien, ahora que tenemos las cuatro reglas de Plotkin vamos a probar a ver cómo transforma a [$f(g(a))$]. Vamos a hacerlo paso a paso.

Inicial: [$T[\ f(g(a)) \mid k\ ]$]
Regla P-TS: [$ T[\ f \mid \lambda x_f.T[\ g(a) \mid \lambda x_{g(a)}. x_f(k, x_{g(a)})\ ]\ ] $]
Regla P-TV: [$ (\lambda x_f.T[\ g(a) \mid \lambda x_{g(a)}. x_f(k, x_{g(a)})\ ]\ )(M[\ f\ ]) $]
Regla P-MV: [$ (\lambda x_f.T[\ g(a) \mid \lambda x_{g(a)} . x_f(k, x_{g(a)})\ ]\ )(f) $]
Regla P-TS: [$ (\lambda x_f.T[g \mid \lambda x_g.T[\ a \mid \lambda x_a. x_g( \lambda x_1. x_f(k, x_{g(a)}) , x_a)\ ]\ ]\ )(f) $]
Regla P-TV: [$ (\lambda x_f. (\lambda x_g.T[\ a \mid \lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a)\ ]\ )(M[\ g\ ]) )(f) $]
Regla P-MV: [$ (\lambda x_f. (\lambda x_g.T[\ a \mid \lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a)\ ]\ )(g) )(f) $]
Regla P-TV: [$ (\lambda x_f. (\lambda x_g. (\lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a) )(M[\ a\ ]\ ) )(g) )(f) $]
Regla P-MV: [$ (\lambda x_f. (\lambda x_g. (\lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a) )(a) )(g) )(f) $]

El resultado de esta expresión es sorprendentemente complejo. Además, parece que podríamos usar varias veces la regla beta para reducir un poco más la expresión.

Del anterior: [$ (\lambda x_f. (\lambda x_g. (\lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a) )(a) )(g) )(f) $]
Regla beta: [$ (\lambda x_g. (\lambda x_a. x_g( \lambda x_{g(a)}. f(k, x_{g(a)}) , x_a) )(a) )(g) $]
Regla beta: [$ (\lambda x_a. g( \lambda x_{g(a)}. f(k, x_{g(a)}) , x_a) )(a) $]
Regla beta: [$ g( \lambda x_{g(a)}. f(k, x_{g(a)}) , a) $]

Esto sí se parece a lo que teníamos inicialmente, el problema es que no podemos realizar reglas beta ya que estamos transformando código y ¿cómo sabemos qué lambdas son del código y qué lambdas son las introducidas por la transformación?

¡Ah!... Se me ocurre una idea. Podríamos etiquetarlas...

Nota: ¿Por qué no podemos realizar reglas beta en el código? Imaginemos la siguiente expresión [$(\lambda x.3)(f(x))$]. Si [$f(x)$] tiene efectos secundarios, al realizar la regla beta obtendríamos [$3$] y habríamos perdido los efectos secundarios.

La tranformación de alto nivel de Appel

Esta fue la idea que se le ocurrió a Appel en 1992 para su libro "Compiling with Continuations", pero no es tan sencilla. En primer lugar estaríamos tentados a etiquetar (con una rayita encima) las lambda que fueran introducidas por la transformación a CPS. Empecemos por la regla que las introduce: la P-TS que renombraremos a A-TS.

Regla A-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]=$][$T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar\lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]

El problema es que las [$\bar\lambda$] no son código, son funciones sobre el código (de ahí lo de alto nivel). Si dejáramos las cosas así obtendríamos
[$$ T[\ f(a)(b)\ ]=f(\bar\lambda x_{f(a)}.x_{f(a)}(k,b), a) $$]
Y eso no es código. No es código porque contiene un [$\bar\lambda$] que es una función sobre el código. No está en la sintaxis que pusimos al inicio.

La solución se obtiene forzando que las continuaciones se especifiquen siempre de forma indirecta, como una función sobre el código. En ese aspecto, cambiamos la regla P-ML de la siguiente forma (la nueva regla es la A-ML):

Regla P-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid x\ ] $]
Regla A-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid \bar\lambda x_0.x x_0\ ] $]

El truco está en que [$\bar\lambda x_0.x x_0$] convierte el código [$x$] en una función que toma código [$x_0$] y devuelve código [$x x_0$]. Como [$x$] va a ser la continuación, el efecto es pasarle [$x_0$] a la continuación. Justo lo que teníamos antes pero, esta vez, el [$\bar\lambda$] significa que estoy trabajando con funciones sobre código y no sobre código. Podré usar la regla beta para simplificarlas. Lo que buscábamos a la hora de etiquetar.

También hay que trastear la regla A-TS porque [$k$] no es código.

Regla P-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]= $][$ T[\ e_0 \mid \lambda x_0.T[\ e_1 \mid \lambda x_1.\ ...T[\ e_n \mid \lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]
Regla A-TS antigua (etiqueto lambdas): [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]= $][$ T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar \lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]
Regla A-TS nueva (arreglo [$k$]): [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]= $][$ T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar \lambda x_n. x_0(\lambda x.k x, x_1,...,x_n)\ ]\ ...\ ]\ ] $]

El truco de [$\lambda x.kx$] es que [$k$] es una función de código que tomará el código [$x$] y generará otro código que permanece dentro del cuerpo de [$\lambda x$]. El resultado es, por tanto, código. Para dejar claro qué variables son de código y qué variables son funciones sobre el código, también etiquetaremos estas últimas que incluirán ahora todas las continuaciones también.

Entonces, las reglas de transformación de alto nivel definitivas son las siguientes:

Regla A-MX: [$ M\ [\ x\ ]=x $]
Regla A-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid \bar\lambda x_0.x x_0 \ ] $]
Regla A-TV: [$ T\ [\ v\mid \bar k\ ]= k(M[\ v\ ])$]
Regla A-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid \bar k\ ]=$][$T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar\lambda x_n. x_0(\lambda x.\bar k x, x_1,...,x_n)\ ]\ ...\ ]\ ] $]
Regla beta: [$ (\bar\lambda (x_1,...x_n). e) (v_1,...,v_n) = [x_1 \rightarrow v_1,..., x_n \rightarrow v_n ]e $]

Mejoran mucho el resultado de la transformación a CPS. El único inconveniente es que debemos trabajar con funciones sobre código (de alto nivel). Así que, si [$k$] sin etiquetar es código, no puedo escribir
[$$ T[\ f(a)\mid k\ ]$$]
Tengo que escribir
[$$ T[\ f(a)\mid \bar\lambda x.k x\ ]$$]
y el resultado de esto no es todo lo perfecto que quisiéramos:
[$$ f( \lambda x.k x, a) $$]
Se me ocurre otra idea... ¿Y no podemos mezclar las reglas de Plotkin y de Appel para usar código o funciones sobre código cuando queramos?

La tranformación CPS híbrida

Separemos entonces [$T\ [\ ]$] en dos: una sin etiqueta y otra con etiqueta [$\bar T\ [\ ]$]. La versión sin etiqueta requiere que la continuación sea código [$T\ [\ e\mid k\ ]$] y la etiquetada requiere que sea una función sobre código [$\bar T\ [\ e\mid \bar k\ ]$]. La mezcla es sencilla.

Regla H-MX: [$ M\ [\ x\ ]=x $]
Regla H-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid x \ ] $]
Regla H-TV: [$ T\ [\ v\mid k\ ]= k(M[\ v\ ])$]
Regla H-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]=$][$\bar T[\ e_0 \mid \bar\lambda x_0. \bar T[\ e_1 \mid \bar\lambda x_1.\ ... \bar T[\ e_n \mid \bar\lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]
Regla H-FV: [$ \bar T\ [\ v\mid \bar k\ ]= \bar k(M[\ v\ ])$]
Regla H-FS: [$ \bar T\ [\ e_0(e_1,...,e_n) \mid \bar k\ ]=$] [$\bar T[\ e_0 \mid \bar\lambda x_0. \bar T[\ e_1 \mid \bar\lambda x_1.\ ... \bar T[\ e_n \mid \bar\lambda x_n. x_0(\lambda x.\bar k x, x_1,...,x_n)\ ]\ ...\ ]\ ] $]
Regla beta: [$ (\bar\lambda (x_1,...x_n). e) (v_1,...,v_n) = [x_1 \rightarrow v_1,..., x_n \rightarrow v_n ]e $]

Con estas reglas sí que conseguimos el objetivo deseado.
[$$ T\ [\ f(a)\mid k\ ]\ = f(k,a)$$]
[$$ T\ [\ f(g(a))\mid k\ ]\ = g(\lambda x.f(k,x), a) $$]
El único problemilla que tenemos es que trabajamos como en dos fases. En la primera fase quitamos las [$T$] (y [$\bar T$]) de en medio y en la segunda fase quitamos las [$\bar \lambda$] con la regla beta. Es posible hacerlo todo a la vez, pero aumenta lo suficiente la complejidad como para no explicarlo aquí (se basa en separar las [$e$] en [$v$] y en [$s$] y tratar cada caso con una regla distinta, específica).

Transformación CPS para lenguajes reales

Para finalizar vamos a apuntar brevemente cómo son las reglas de transformación CPS para un lenguaje de programación real, con asignación, selección, secuencia y demás primitivas.

AsignaciónT: [$ T\ [\ \mathrm{set}\ x\ e \mid k\ ]=\bar T[ e \mid \bar\lambda x_0. k ( \mathrm{set}\ x\ e)\ ] $]
AsignaciónF: [$ \bar T\ [\ \mathrm{set}\ x\ e \mid \bar k\ ]=\bar T[ e \mid \bar\lambda x_0. \bar k ( \mathrm{set}\ x\ e)\ ] $]
SelecciónT: [$ T\ [\ \mathrm{if}\ e_1\ e_2\ e_3 \mid k\ ]=\bar T[\ e_1 \mid \bar\lambda x_1. ( \mathrm{if}\ x_1\ T[\ e_2 \mid k\ ]\ T[\ e_3 \mid k\ ]\ ] $]
SelecciónF: [$ \bar T\ [\ \mathrm{if}\ e_1\ e_2\ e_3 \mid \bar k\ ]=\bar T[\ e_1 \mid \bar\lambda x_1. ( \mathrm{if}\ x_1\ \bar T[\ e_2 \mid \bar k\ ]\ \bar T[\ e_3 \mid \bar k\ ]\ ] $]
SecuenciaT: [$ T\ [\ e_1 ; e_2 \mid k \ ]= \bar T[\ e_1 \mid \bar\lambda x.T[\ e_2 \mid k\ ]\ ] $]
SecuenciaF: [$ \bar T\ [\ e_1 ; e_2 \mid \bar k \ ]= \bar T[\ e_1 \mid \bar\lambda x. \bar T[\ e_2 \mid \bar k\ ]\ ] $]

La selección duplica el código que hay en la continuación porque lo usa en dos sitios. Esto puede dar lugar a un código final más grande de lo deseable. La solución es postergar a tiempo de ejecución el paso de la continuación de la siguiente forma:

SelecciónT2: [$ T\ [\ \mathrm{if}\ e_1\ e_2\ e_3 \mid k\ ]=(\lambda x. \bar T[\ e_1 \mid \bar\lambda x_1. ( \mathrm{if}\ x_1\ T[\ e_2 \mid k\ ]\ T[\ e_3 \mid x\ ]\ ])(k) $]
SelecciónF2: [$ \bar T\ [\ \mathrm{if}\ e_1\ e_2\ e_3 \mid \bar k\ ]=(\lambda x. \bar T[\ e_1 \mid \bar\lambda x_1. ( \mathrm{if}\ x_1\ \bar T[\ e_2 \mid \bar x\ ]\ \bar T[\ e_3 \mid \bar k\ ]\ ])(\lambda x_0.\bar k x_0) $]

La clásica función call/cc se implementa así.

CallCCT: [$ T\ [\ \mathrm{calcc}\ | k\ ] = k (\lambda(x_0,x_1).x_1(x_0,\lambda(x_2,x_3).x_0(x_3))) $]
CallCCF: [$ \bar T\ [\ \mathrm{calcc} \ | \bar k\ ] = \bar k (\lambda(x_0,x_1).x_1(x_0,\lambda(x_2,x_3).x_0(x_3))) $]

Los let se pueden implementar como lambdas aplicados inmediatamente, pero los letrec, no. Asumimos que los letrec sólo pueden vincular valores. Entonces:

LetRecT: [$ T\ [\ \mathrm{letrec}\ x_1=v_1,...,x_n=v_n\ \mathrm{in}\ e \mid k\ ]=$][$\mathrm{letrec}\ x_1=M[\ v_1\ ],...,x_n=M[\ v_n\ ]\ \mathrm{in}\ T[\ e \mid k\ ] $]
LetRecF: [$ \bar T\ [\ \mathrm{letrec}\ x_1=v_1,...,x_n=v_n\ \mathrm{in}\ e \mid \bar k\ ]=$][$\mathrm{letrec}\ x_1=M[\ v_1\ ],...,x_n=M[\ v_n\ ]\ \mathrm{in}\ \bar T[\ e \mid \bar k\ ] $]

Referencias

Matt Might - How to compile with continuations
Mark Feeley - The 90 minute Scheme to C compiler

Modelos de memoria compartida

2011-04-27T19:40:00.009+02:00

Orden de programa

Un programa se compone de instrucciones.

1 x=A //Lee el valor de A
2 B=2 //Escribe un valor en B
3 y=B //Lee el valor de B

Usaré las letras mayúsculas (A,B,C) para las localizaciones de memoria y las minúsculas (a,b,c) para registros o valores que no estén en memoria. Como nos interesa el modelo de memoria, ignoraremos las operaciones que no trabajen con memoria. Para mayor facilidad usaremos números para cada instrucción.

Cuando se ejecuta un programa las instrucciones que se van ejecutando conforman una secuencia que se denomina traza. Se llama orden de programa a la relación de orden estricto que encadena las instrucciones según se ejecutan en una traza. Si escribimos esta relación como [$ \rightarrow_p $] entonces, el programa de arriba tiene la siguiente traza

[$$ 1 \rightarrow_p 2 \rightarrow_p 3 $$]

Nada extraño. Esta relación es un orden estricto y, en principio, total.

Modelo secuencialmente consistente (SC)

Cuando tenemos varios procesadores, cada uno de ellos ejecutando una hebra distinta, ¿cómo se reparten las instrucciones? ¿Y qué instrucciones se ejecutan antes que otras? Un modelo de memoria compartida responde a estas preguntas.

El modelo más simple es el secuencialmente consistente (SC) de Lamport. En este modelo las instrucciones de todos los procesadores se intercalan y el orden resultante de las mismas ha de ser un orden total que llamaremos de ocurrencia [$ \rightarrow_o $].

Si no pusiéramos más condiciones, este orden podría ser cualquiera, incluso sin respetar el orden de programa.

Por ejemplo, este programa con dos hebras

INICIALMENTE: A=B=0
HEBRA 1 HEBRA 2
1 x=A 11 y=B
2 B=1 12 A=1

Tiene el siguiente orden de programa

[$$ 1 \rightarrow_p 2 $$]
[$$ 11 \rightarrow_p 12 $$]

Sin condiciones adicionales, el orden de ocurrencia podría ser, por ejemplo

[$$ 2 \rightarrow_o 12 \rightarrow_o 1 \rightarrow_o 11 $$]

Nota: Tanto el orden [$ \rightarrow_p $] como el orden [$ \rightarrow_o $] son transitivos por lo que con el ejemplo de arriba también tendríamos [$ 2 \rightarrow_o 1, 2 \rightarrow_o 11, 12 \rightarrow_o 11 $]. Es usual no listar estas relaciones que se pueden derivar fácilmente de la primera.

Este orden daría como resultado x=y=1 lo cual es bastante contraintuitivo. El modelo SC tiene la siguiente restricción: si [$N$] y [$M$] son dos instrucciones y [$ N \rightarrow_p M $] entonces debe darse que [$ N \rightarrow_o M $]. Esta condición se expresa de la siguiente manera.

[$$ \frac{N \rightarrow_p M}{N \rightarrow_o M} $$]

Esto quiere decir que si en una hebra se ejecuta una instrucción antes que otra por el orden de programa (por ejemplo, la 11 antes de la 12) entonces ese mismo orden aparece en el orden de ocurrencia. Como en el ejemplo anterior teníamos que 12 ocurría antes que 11, excluimos este posible orden del modelo SC.

[$ 2 \rightarrow_o 12 \rightarrow_o 1 \rightarrow_o 11$] no es SC porque [$2 \rightarrow_o 1$] pero [$1 \rightarrow_p 2$]
[$ 11 \rightarrow_o 1 \rightarrow_o 2 \rightarrow_o 12 $] sí es SC y el resultado es un intuitivo x=y=0
[$ 1 \rightarrow_o 2 \rightarrow_o 11 \rightarrow_o 12 $] sí es SC y el resultado es otro intuitivo x=0, y=1

El dibujo típico del modelo secuencialmente consistente es una memoria compartida asignada únicamente a un procesador en cada momento.

Optimizaciones en compiladores y procesadores

Desafortunadamente las cosas no son tan sencillas. Generalmente el orden de programa es excesivamente restrictivo para realizar optimizaciones. Una optimización típica es la siguiente.

1 A=5
2 x=A
3 B=1

En el anterior programa, la instrucción 2 ha de esperar a que la instrucción 1 escriba el valor 5 en A. Un compilador o un procesador astuto reordena el programa de la siguiente forma.

11 A=5
12 B=1
13 x=A

En este programa transformado, la instrucción 12 se ejecuta mientras la instrucción 11 se está terminando. Esto evita que tengamos que esperar en la instrucción 13 tanto como hacíamos en la instrucción 2.

El problema es que el programador ha escrito las instrucciones 1,2,3 y no las 11,12,13. ¿Qué pasa si ejecutamos esto con otra hebra?

HEBRA 1 HEBRA 2
1 A=5 21 if(B=1)
2 x=A 22 A=7
3 B=1

Pensando en SC de ninguna manera podría ocurrir que x=7 ya que para cuando B=1, x ya tiene el valor 5 y por mucho que modifiquemos A=7, x ya no va a cambiar. Esto no es así si el procesador o el compilador reordena el programa de la hebra 1 sin que lo sepamos.

HEBRA 1 HEBRA 2
11 A=5 21 if(B=1)
12 B=1 22 A=7
13 x=A

Aunque el programador ha escrito 1,2,3, el compilador o el procesador lo reordena a 11,12,13 para optimizar la espera de la instrucción 2 tras la 1. Ahora bien, ¡esto ahora permite que x=7! El orden de ocurrencia para este bug sería

[$$ 11 \rightarrow_o 12 \rightarrow_o 21 \rightarrow_o 22 \rightarrow_o 13 $$]

Si el pobre programador intenta razonar sobre el orden del programa original 1,2,3 lo que vería sería

[$$ 1 \rightarrow_o 3 \rightarrow_o 21 \rightarrow_o 22 \rightarrow_o 2 $$]

que no es SC porque la instrucción 3 se ejecuta antes que la 2.

Relajando el modelo SC

Por esta razón el modelo SC no es útil: no permite al compilador o al procesador optimizar los programas sin dejar al programador con un difícil bug a resolver. La solución es exponer al programador un modelo más débil que se denomina un modelo relajado.

¿Cómo vamos a relajar ese modelo? Hay varias formas.

La primera es permitir reordenar las instrucciones de un programa y proporcionar al programador herramientas para decirle al compilador y al procesador cuándo no se pueden reordenar. Una de estas herramientas es una instrucción llamada barrera de memoria (memory fence) y lo único que significa es que es una barrera que las instrucciones no se la pueden saltar al ser reordenadas.

Con una barrera, el programa anterior quedaría así

HEBRA 1 HEBRA 2
1 A=5 21 if(B=1)
2 x=A 22 A=7
3 FENCE
4 B=1

Y ni el compilador ni el procesador podrían reordenar la instrucción 4 sobre la 3 o la 1 o la 2 bajo la 3. De esta manera, el programador se asegura de que leemos A antes de modificar B. Por otra parte, el compilador o el procesador son libres de realizar otras optimizaciones en otros sitios.

¿Pero en qué sitios? ¿Podría reordenar la instrucción 2 sobre la 1? Realmente no, porque necesitamos conocer A en la instrucción 2 y eso depende de la instrucción 1. A esta relación se la llama una dependencia y la escribiremos [$\rightarrow_d$]. Básicamente indica que un valor no se puede usar antes de que haya sido calculado. En un modelo de memoria relajado al menos se debe conservar la dependencia. Es decir,

[$$\frac{N \rightarrow_d M}{N \rightarrow_o M}$$]

Además, las barreras de memorias ordenan lo que ocurre antes y después de ellas.

[$$\frac{N \rightarrow_p M, N\ es\ FENCE}{N \rightarrow_o M},\ \ \frac{N \rightarrow_p M, M\ es\ FENCE}{N \rightarrow_o M}$$]

Entonces, en el programa anterior teníamos.

[$$1\rightarrow_p 2\rightarrow_p 3\rightarrow_p 4,11\rightarrow_p 12$$]
[$$1\rightarrow_d 2,11\rightarrow_d 12$$]
[$$3\ es\ FENCE$$]

Por la dependencia debe cumplirse que

[$$1\rightarrow_o 2,11\rightarrow_o 12$$]

y por barrera debe cumplirse que

[$$1\rightarrow_o 3,2\rightarrow_o 3,3\rightarrow_o 4$$]

Entonces, está claro que

[$1\rightarrow_o 11\rightarrow_o 2\rightarrow_o 12\rightarrow_o 3\rightarrow_o 4$] sí cumple con el modelo relajado
[$1\rightarrow_o 11\rightarrow_o 2\rightarrow_o 12\rightarrow_o 4\rightarrow_o 3$] no cumple con el modelo relajado porque [$4\rightarrow_o 3$]

Nota: La instrucción 12 no se ejecuta, pero de ejecutarse lo haría en la posición arriba puesta.
Nota: Sabemos que si [$4\rightarrow_o 3$] entonces no se da [$3\rightarrow_o 4$] porque estamos tratando con órdenes.

Otras barreras, otros modelos, otras instrucciones

Algunos compiladores y procesadores se restringen a reordenar instrucciones que son de cierto tipo. Los más usuales son

Reordena una escritura seguida de otra escritura (WW)
Reordena una lectura seguida de una escritura (RW)
Reordena una escritura seguida de una lectura (WR)
Reordena una lectura seguida de otra lectura (RR)

Eso permite además tener barreras de memoria selectivas que

Impida reordenar escrituras anteriores a la barrera con escrituras posteriores (WW)
Impida reordenar lecturas anteriores a la barrera con escrituras posteriores (RW)
Impida reordenar escrituras anteriores a la barrera con lecturas posteriores (WR)
Impida reordenar lecturas anteriores a la barrera con lecturas posteriores (RR)

Esto lleva permitirle al compilador y al procesador más optimizaciones. Existen más métodos de restringir la reordenación como instrucciones atómicas, sincronizaciones, bloqueos, etc. Eso sí, empieza a crearnos un zoológico de modelos de memoria que, sin embargo, se dan en la vida real. Por ejemplo,

Procesador o
Modelo de memoria Relaja WR Relaja WW Relaja RW Relaja RR
SC
IBM 360    Sí
TSO    Sí
PC    Sí
PSO    Sí Sí
WO       Sí Sí Sí Sí
RCsc       Sí Sí Sí Sí
RCpc       Sí Sí Sí Sí
Alpha    Sí Sí Sí Sí
RMO    Sí Sí Sí Sí
PowerPC    Sí Sí Sí Sí

Para más información http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.5742&rank=1

Divisiones y módulos enteros

2011-04-23T15:53:00.027+02:00

Supongamos que queremos saber si un número es impar. ¿Bastaría este código?

bool impar(int n)
{
 return (n%2) == 1;
}

Veamos. Introducimos el valor 5, hacemos la división por 2 y obtenemos el resto 1. Efectivamente, es impar. Ahora introduzcamos el valor -3, hacemos la división por 2 y obtenemos ¿qué resto? En mi implementación obtengo -1. Eso es un problema, pero ¿por qué sale -1? ¿No debería salir 1?

El operador de módulo % está muy relacionado con la división entera. La división entera se define de la siguiente manera. Sean cuatro números enteros [$n, d, c$] y [$r$] que llamaremos dividendo, divisor, cociente y resto. Esos cuatro números cumplen la siguiente ecuación.

[$$ n = dc + r $$]

Si, además, imponemos la siguiente inecuación, el cociente y el resto son únicos para cada par de dividendo y divisor.

[$$ 0\le r \lt \left| d \right| $$]

Esto es, básicamente, la llamada división euclídea. Matemáticamente este procedimiento de división es muy interesante y tiene muchas propiedades, pero carece de otras. En concreto, con esta división entera multiplicar divisor y dividendo por menos uno altera el resultado.

[$$ \frac{a}{b} \ne \frac{-a}{-b} $$]

Se puede probar con, por ejemplo, [$ \frac{7}{3} $] el cociente será [$2$] y el resto [$1$] mientras que [$ \frac{-7}{-3} $] tiene cociente [$3$] y resto [$2$]. No puedo obtener cociente [$2$] porque el resto tiene que ser positivo.

Entonces, usemos una división más intuitiva. Por ejemplo, hacemos la división en los reales y luego redondeamos. Ahora bien, hay varios tipos de redondeo. Los más usuales son el redondeo por truncamiento, por defecto, por exceso y al entero más cercano (con varias estrategias de desempate).

Según usemos un tipo de división u otra, obtendremos el resto (es decir, el resultado del operador %) de una forma u otra, pero todas mediante la ecuación anterior para mantener consistencia. Despejamos de ella el resto y esa es nuestra definición del operador %.

[$$ n\%d = r = n - dc = n - d \left[ \frac{n}{d} \right] $$]

La división entre corchetes representa el cociente que cambiará según elijamos uno u otro redondeo. El resumen está en esta tabla.

	Redondeo por truncamiento	Redondeo por defecto	Redondeo por exceso	Redondeo al más cercano	División euclídea
[$$\frac{3}{5}$$]	c=0 r=3	c=0 r=3	c=1 r=-2	c=1 r=-2	c=0 r=3
[$$\frac{-3}{5}$$]	c=0 r=-3	c=-1 r=2	c=0 r=-3	c=-1 r=2	c=-1 r=2
[$$\frac{3}{-5}$$]	c=0 r=3	c=-1 r=-2	c=0 r=3	c=-1 r=-2	c=0 r=3
[$$\frac{-3}{-5}$$]	c=0 r=-3	c=0 r=-3	c=1 r=2	c=1 r=2	c=1 r=2

Hay tres hechos importantes en esta tabla:

En el redondeo por truncamiento el signo del resto coincide con el signo del dividendo.
En el redondeo por defecto el signo del resto coincide con el signo del divisor (y en el redondeo por exceso con su opuesto).
En el redondeo al entero más cercano el resto es el más cercano a cero posible.

Nota: La división que utilizamos cuando usamos el AND binario (&) para calcular rápidamente un módulo [$ a\% 2^n = a \& (2^n -1) $] es o bien la por defecto o la euclídea (tanto el divisor como el resto son positivos en este caso).

Ahora sólo queda ver qué lenguaje de programación usa qué tipo de división y módulo. La siguiente tabla extraída de la Wikipedia lo lista.

Lenguaje	Operador	El resultado tiene el mismo signo que
ActionScript	`%`	Dividendo
Ada	`mod`	Divisor
Ada	`rem`	Dividendo
ASP	`Mod`	No definido
ALGOL-68	`%×`	Euclídea
AMPL	`mod`	Dividendo
AppleScript	`mod`	Dividendo
BASIC	`Mod`	No definido
bc	`%`	Dividendo
bash	`%`	Dividendo
C (ISO 1990)	`%`	Depende de implementación
C (ISO 1999)	`%`	Dividendo
C++	`%`	Depende de implementación
C#	`%`	Dividendo
CLARION	`%`	Dividendo
Clojure	`mod`	Divisor
ColdFusion	`%`	Dividendo
Common Lisp	`mod`	Divisor
Common Lisp	`rem`	Dividendo
D	`%`	Dividendo
Eiffel	`\\`	Dividendo
Erlang	`rem`	Dividendo
Euphoria	`mod`	Divisor
Euphoria	`remainder`	Dividendo
FileMaker	`Mod`	Divisor
Fortran	`mod`	Dividendo
Fortran	`modulo`	Divisor
GML (Game Maker)	`mod`	Dividendo
Go	`%`	Dividendo
Haskell	`mod`	Divisor
Haskell	`rem`	Dividendo
J	`\|~`	Divisor
Java	`%`	Dividendo
JavaScript	`%`	Dividendo
Just Basic	`MOD`	Dividendo
Lua 5	`%`	Divisor
Lua 4	`mod(x,y)`	Divisor
Liberty Basic	`MOD`	Dividendo
MathCad	`mod(x,y)`	Divisor
Maple (software)	`e mod m`	Divisor
Mathematica	`Mod`	Divisor
Microsoft Excel	`=MOD()`	Divisor
MATLAB	`mod`	Divisor
MATLAB	`rem`	Dividendo
Oberon	`MOD`	Divisor
Objective Caml	`mod`	Dividendo
Occam	`\`	Dividendo
Pascal (Delphi)	`mod`	Dividendo
Pascal (ISO-7185 and ISO-10206)	`mod`	Euclídea
Perl	`%`	Divisor
PHP	`%`	Dividendo
PL/I	`mod`	Divisor (ANSI PL/I)
PowerBuilder	`mod(x,y)`	?
PowerShell	`%`	Dividendo
Prolog (ISO 1995)	`mod`	Divisor
Prolog (ISO 1995)	`rem`	Dividendo
Python	`%`	Divisor
RealBasic	`MOD`	Dividendo
R	`%%`	Divisor
RPG	`%REM`	Dividendo
Ruby	`%, modulus()`	Divisor
Ruby	`remainder()`	Dividendo
Scheme	`modulo`	Divisor
Scheme	`remainder`	Dividendo
Scheme R⁶RS	`mod`	Euclídea
Scheme R⁶RS	`mod0`	Más cercano a cero
SenseTalk	`modulo`	Divisor
SenseTalk	`rem`	Dividendo
Smalltalk	`\\`	Divisor
SQL (SQL:1999)	`mod(x,y)`	Dividendo
Standard ML	`mod`	Divisor
Standard ML	`Int.rem`	Dividendo
Stata	`mod(x,y)`	Euclídea
Tcl	`%`	Divisor
Torque Game Engine	`%`	Dividendo
Turing (programming language)	`mod`	Divisor
Verilog (2001)	`%`	Dividendo
VHDL	`mod`	Divisor
VHDL	`rem`	Dividendo
Visual Basic	`Mod`	Dividendo
x86 Assembly	`IDIV`	Dividendo
ADEP_AUTO language	`MODULO(x,y)`	Divisor

También existe el mismo problema relacionado con la operación equivalente en los reales (flotantes). Esta es la tabla en este caso.

Lenguaje	Operador	El resultado tiene el mismo signo que
C (ISO 1990)	`fmod`	?
C (ISO 1999)	`fmod`	Dividendo
C (ISO 1999)	`remainder`	Más cercano a cero
C++	`std::fmod`	?
C#	`%`	Dividendo
D	`%`	?
Common Lisp	`mod`	Divisor
Common Lisp	`rem`	Dividendo
Go	`math.Fmod`	Dividendo
Haskell (GHC)	`Data.Fixed.mod'`	Divisor
Java	`%`	Dividendo
JavaScript	`%`	Dividendo
Objective Caml	`mod_float`	Dividendo
Perl	`POSIX::fmod`	Dividendo
PHP	`fmod`	Dividendo
Python	`%`	Divisor
Python	`math.fmod`	Dividendo
Ruby	`%, modulus()`	Divisor
Ruby	`remainder()`	Dividendo
Scheme R⁶RS	`flmod`	Euclídea
Scheme R⁶RS	`flmod0`	Más cercano a cero
Standard ML	`Real.rem`	Dividendo

Bueno. Entonces. Al final. ¿Cómo sé si un número es impar o no? Lo mejor es aprovechar que el resto cero es igual en todas las implementaciones y hacer algo así.

bool impar(int n)
{
 return (n%2) != 0;
 }

miniSL parte 12 - Limitaciones y uso del recolector de basura

2011-04-19T20:55:00.001+02:00

Hasta ahora hemos hablado del montículo, las celdas y cómo crearlas. Sin embargo, no hemos visto cómo se usa la recolección de basura implementada y, tampoco, sus limitaciones.

La recolección de basura sirve para detectar celdas no usadas y marcarlas como tales. La forma de hacerlo es muy sencilla. Tenemos un conjunto raíz que son celdas que sabemos a ciencia cierta que son usadas de forma. A partir de ese conjunto exploramos qué otras celdas usan. El resto son celdas sin usar. Este algoritmo se denomina mark and sweep (marca y barre). El código para esto se adelantó en la parte 8, pero queda por saber cómo se usa exactamente.

Lo importante son las limitaciones del algoritmo de recolección de basura implementado en miniSL. Son las siguientes.

El algoritmo de mark and sweep usado detiene la ejecución. Aunque este es el menor de nuestros problemas como veremos más adelante.
El algoritmo usado sólo usa el entorno global (lo veremos con más detalle en la siguiente parte) como el conjunto raíz. Esto quiere decir que no podemos llamar el algoritmo en medio de la ejecución del código porque la celda que contiene el entorno local de la función no forma parte del conjunto raíz.
En concreto, no podríamos lanzar el recolector de basura cuando notemos que nos hemos quedado sin memoria. Por ejemplo, en el caso de entrar en la línea 6 de la función Script::CreateCell(). Por esa razón, hemos de reservar una nueva celda y no reutilizar una antigua.
La estructura del recolector de basura no es incremental. El algoritmo mark and sweep usa dos conjuntos de celdas: las marcadas (usadas) y las no marcadas (no usadas). Para poder hacer un recolector de basura incremental hacen falta tres conjuntos llamados de celdas blancas, grises y negras.
Debido a todo esto, el propio miniSL no puede llamar al recolector de basura. Lo tiene que hacer la aplicación que use el script.

Ni que decir tiene que estas limitaciones hacen el lenguaje miniSL inútil en la vida real, pero simplifican muchísimo el código. Nosotros lo que haremos será llamar al recolector de basura en cada ciclo del bucle de lectura-evaluación-impresión o (REPL).
Este bucle será ahora:

Lectura de una expresión.
Evaluación de la expresión.
Impresión del resultado.
Recolección de basura.

Veremos el REPL en la parte 32, ya que antes hemos de definir cómo evaluamos y cómo leemos una expresión. Hasta ahora sólo sabemos imprimir las celdas.

En la siguiente entrada nos centraremos en el conjunto raíz de nuestro recolector de basura. Es decir, en el entorno global que contiene los símbolos definidos más generales.

Grados de confianza gatunos

2011-04-15T19:41:00.000+02:00

Como bien saben los que me siguen, de vez en cuando hago una excursión por temas no informáticos. Esta vez en el mundo de los gatos. Responderé a la pregunta ¿cómo sé si mi gato tiene confianza en mí o no?

El gato amistoso de Shu es de grado 4.

Cierta persona me dijo una vez que los grados son los siguientes.

Desconfiado. El gato se aleja si te acercas a él. No tendrá menos de dos o tres metros de distancia entre tú y él.
Próximo. Te puedes acercar a él, pero no se dejará tocar. O sólo se dejará tocar muy poco tiempo.
Mimoso. El gato se deja tocar, acariciar y rascar, pero sin hacer cosas raras. Cualquier movimiento, mirada, ruido, etc. hará que salga pitando. En general no es buena idea mirar a los ojos a los gatos. Es mejor parpadear lentamente para decir "no te estoy cazando".
Escalador. Una vez que está cómodo cerca de ti, el gato puede querer subirse encima. Generalmente no lo intentará cuando estés de pie. Podrá ser sobre las rodillas o sobre la barriga si estás tumbado.
Observador. El gato se deja coger y deja que te pongas en pie con él. Si al gato no le gusta, se echará al suelo. Algunos gatos incluso te piden que los cojas poniendo sus patitas en tus rodillas. Realmente, una vez que se acostumbran, les encanta observar las cosas desde arriba.
Confiado. El gato se deja coger y deja que andes con él. Algunos gatos pueden llegar incluso a abrazarse a ti. Este es el grado máximo, pero cualquier tontería hará que el gato pierda confianza y luego es difícil volverla a ganar. Así que mucho mimo.

Nota final: El ronroneo no es muy fiable. No siempre significa que el gato está contento. También puede ser que quiera algo, o que se haya olvidado que está ronroneando y siga ahí runrun.

Infija, prefija, postfija y circunfija

2011-04-11T19:31:00.006+02:00

Expresión infija. Es la usual. El operando (+) aparece entre los operadores (1 y 2).

[$$ 1 + 2 $$]

Expresión prefija. El operador aparece antes de los operadores.

[$$ + 1 2 $$]

Es la forma natural en el lenguaje de programación Haskell. Variante de esta es también [$ +(1,2) $] donde es más natural usar un operador alfabético como [$ f(1,2) $].

Expresión postfija. El operador aparece detrás de los operadores.

[$$ 1 2 + $$]

Expresión circunfija. El operador rodea a los operadores. Esto es típico en los paréntesis.

[$$ (1 2) $$]

Es la forma usual del LISP. Otra variante es con los operadores separados por coma o similar.

Frecuencia fraccional

2011-04-07T11:12:00.000+02:00

El problema

Supongamos que tenemos un evento que se dispara a una frecuencia dada [$f_0$] (por ejemplo, una frecuencia de muestreo). Llamaremos eventos básicos a estos eventos. Es fácil comprobar que puedo generar otros eventos derivados a partir de estos eventos básicos. Bastará tomar una frecuencia divisora [$f=f_0/k$] y lanzar un evento derivado cada [$k$] eventos básicos. Por ejemplo, si [$k=3$] tengo un evento derivado cada tres eventos básicos.

Si trazamos el número de evento básico en el eje de abscisas y el número de evento derivado en el eje de ordenadas, obtenemos una línea. En este caso, de pendiente [$1/3=f/f_0$].

¿Pero qué ocurriría si la frecuencia es una fracción cualquiera de [$f_0$] y no exactamente un divisor?

El algoritmo

En este caso a veces tendremos que contar [$k$] eventos básicos y otras veces [$k+1$]. No obtenemos una frecuencia exacta, pero en promedio sí será la [$f$] deseada. Pagamos un jitter por tener una frecuencia que no es divisora de la frecuencia básica.

Lo interesante aquí es que seguimos obteniendo una recta, aunque ya no está centrada en el origen y tampoco tiene una pendiente [$1/k$]. Si llamo [$0\le r<1$] a la altura de intersección con el eje de ordenadas y [$t$] al número de evento básico (en definitiva, es el tiempo transcurrido) mi recta es

[$$y=r+\frac{f}{f_0}t$$]

El primer evento derivado se tendrá que lanzar cuando la recta corte a la línea [$y=1$]. Es decir

[$$1=r+\frac{f}{f_0}t$$]

Debido a que el resultado puede no ser un número entero, hemos de redondear al siguiente evento básico que llamaremos [$t_1$].

[$$t_1=\left \lceil \frac{1-r}{f/f_0} \right \rceil$$]

Ya sabemos cuándo lanzar el siguiente evento derivado: será en el evento básico [$t_1$]. Lo interesante aquí es que puedo trasladar de nuevo todo al origen de coordenadas y calcular el valor [$r$] para el siguiente evento derivado empezando desde cero. Usando exactamente las mismas ecuaciones.

Este nuevo valor de [$r$], que llamaré [$r_1$], será el valor de [$r$] en [$t_1$] pero restando [$1$] para volver al origen de coordenadas.

[$$r_1=r+\frac{f}{f_0}t_1-1$$]

Con lo que el algoritmo sería

Iniciamos con [$r=0$] y el valor [$f=f_0$] de frecuencia que deseemos.
Calculamos [$t_1$] y [$r_1$] a partir del valor de [$r, f$] y [$f_0$].
Esperamos [$t_1$] eventos básicos antes de lanzar un evento derivado.
Hacemos [$r \leftarrow r_1$] y vamos al paso 2

La implementación

Este algoritmo está muy bien, pero hay un detalle de implementación. Tanto el valor [$f/f_0$] como el valor [$r$] están en el intervalo [$[0,1)$]. No es descabellado usar una notación de coma fija para representarlo en [$n$] bits. Entonces, usando el subíndice [$p$] para la coma fija,

[$$f_p=2^n \frac{f}{f_0} $$]
[$$r_p=2^n r$$]

Y las ecuaciones quedan

[$$t_1=\left \lceil \frac{2^n-r_p}{f_p} \right \rceil $$]
[$$r_1=r_p+f_p t_1-2^n$$]

La ecuación de [$t_1$] tiene un problema: el redondeo por exceso. Generalmente las divisiones enteras tienen redondeo por defecto. Es fácil hacer la conversión sumando el denominador menos uno.

[$$t_1=\left \lceil \frac{2^n-r_p}{f_p} \right \rceil=\left \lfloor \frac{2^n-r_p+f_p-1}{f_p} \right \rfloor $$]

Y un paso más es darnos cuenta que [$2^n-1-r_p$] no es más que el complemento a uno de [$r_p$] que notaremos [$ \sim r_p $].

[$$t_1=\left \lfloor \frac{\sim r_p+f_p}{f_p} \right \rfloor $$]

La ecuación de [$r_1$] puede simplificarse también ya que sumar o restar [$2^n$] no tiene efecto en aritmética módulo [$2^n$] por lo que llegamos a

[$$r_1=r_p+f_p t_1$$]

El algoritmo sigue siendo el mismo.

Reunión del C++ Standards Committee en Madrid

2011-03-22T09:46:00.000+01:00

Es la primera vez en la historia que el comité de estandarización del C++ se reúne en España. Durante unos días, del 21 al 26 de marzo de 2011, estarán en tierras hispanas. En teoría, pero sólo en teoría, las reuniones son públicas. Por si os queréis animar, toda la información está aquí.

Mónadas en un plis-plás

2011-03-16T14:23:00.000+01:00

Como no hay blog de informática teórica que se precie sin un tutorial de mónadas, y aprovechando que Milewski está dedicándole unos posts a esto, voy a explicar cómo entendí lo de las mónadas (si es que lo entendí, claro).

De los efectos secundarios y de cómo evitarlos

Supongamos esta función.

int f(int x)
{
a=x+2;
return x*3;
}

Realmente, está haciendo dos cosas: retornar el triple y asignar el argumento más dos a una variable externa “a”. Esta segunda acción es lo que se llama un efecto secundario porque modifica el estado global del programa. En este caso, el valor de “a”.

Muchas veces no es conveniente tener efectos secundarios: se simplifica la concurrencia, se permite la transparencia referencial, se permiten más optimizaciones, facilita la comprensión del programa, etc. Si queremos evitar que la función “f” tenga efectos secundarios la única solución es forzar a que éstos sean devueltos también por el retorno. Llamaremos a esta nueva función “F” para distinguirla de la original “f” con efectos secundarios.

El problema ahora es que tenemos que devolver dos tipos. Además, no hemos dicho nada de que la función “f” pueda hacer más de una asignación. Tampoco hemos hablado de cómo cambia este nuevo retorno el estado global. Lo mejor es abstraernos de todos estos detalles y decir que “F” devuelve asignaciones y un entero. Inventaremos el tipo “A<int>” para eso usando un constructor de tipos "A".

Así que “F” vuelve a ser una función normal y corriente con un tipo a devolver exótico que engloba tanto el retorno normal (el entero) como los efectos secundarios (las asignaciones).

¡Pero hemos perdido una operación fundamental en la programación! ¿Cómo hacemos composiciones? ¿Cómo hacemos cosas como “f(f(5))”? Ahora que los tipos no coinciden, ¡no es posible escribir “F(F(5))”!

La solución pasa por hacer explícita la aplicación. ¿Pero qué es una aplicación explícita?

De la aplicación explícita y las restricciones que la composición le impone

En esta sección sólo hablaremos de cosas conocidas: funciones puras sin efectos secundarios. Llamaremos “g” y “h” a estas funciones puras. Nos olvidaremos por ahora del tipo “A<int>” y de las funciones “f” y “F” con efectos secundarios.

La aplicación explícita es sencillamente escribir “apply(x, g)” en vez de escribir “g(x)”.

Es únicamente un cambio en la notación, pero nos permite estudiar las propiedades de “apply” y realizar cosas tan potentes como la defuncionalización (de la que no hablaremos aquí). En concreto, para que “apply” sea coherente con la composición, debe mantener sus dos propiedades: elemento neutro y asociativa.

Para el elemento neutro hemos de introducir una función identidad. La llamaremos “id” y devuelve su argumento sin hacer nada de nada.

int id(int v) {return v;} //Función identidad de los enteros

Obviamente, componer esta función no debe hacer nada.

apply(x, id) == x
apply(id(x), g) == g(x)

Para la asociativa introduciremos una función compuesta “h” que aplique consecutivamente dos funciones “g1” y “g2”. En notación matemática escribiríamos [$h=g_2 \circ g_1$].

int h(int v) { return apply(g1(v), g2); }

Entonces, aplicar esta función compuesta “h” es igual que aplicar consecutivamente “g1” y “g2”.

apply(v, h) == apply(apply(v, g1), g2)

Con esto estamos seguros de que “apply” se comporta correctamente para la composición y podemos volver a pensar cómo solucionar el problema de la composición de la función “F”.

Nota: La propiedad asociativa aquí expuesta no parece ser la propiedad asociativa de toda la vida, pero si usamos “@” como operador infijo para el “apply” y la composición, entonces la propiedad queda algo así como “v@(g1@g2) = (v@g1)@g2” lo cual sí que se parece ya a la propiedad asociativa usual.

De la mezcla de efectos secundarios con aplicaciones explícitas

Lo interesante de hacer explícita la aplicación es que podemos adaptar el tipo de la misma a nuestros requisitos. Llamaremos “bind” a la aplicación con el tipo “A<int>” sobre funciones de tipo “int -> A<int>”, para no confundirla con “apply” que funciona sobre “int” y funciones “int -> int” únicamente.

apply: int -> (int->int) -> int
bind: A<int> -> (int -> A<int> ) -> A<int>

El truco está en que “bind(xx, F)” toma los efectos secundarios de “xx” y los mezcla con los efectos secundarios del resultado de “F” para luego devolverlos en su resultado.

Pero queda el asunto de la composición que nos forzó a introducir el “bind”: debe cumplir exactamente las mismas propiedades que “apply”.

La única salvedad es que “id” no debe ser la función identidad de los enteros. Tenemos que mantener el tipo “int -> A<int>” en las funciones. Así que se ha de convertir en una función que toma un entero y devuelve un “A<int>” de la manera más neutra posible. Es decir, sin efectos secundarios. También vamos a cambiar el nombre de esta función para no confundirla con la “id” original y la vamos a llamar “unit”.

Pues bien. Estas tres cosas son una mónada:

Un constructor de tipo como “A” que dado un tipo de retorno como “int” devuelve un tipo “A<int>” que engloba tanto ese tipo de retorno como los efectos secundarios.
Un par de funciones “bind” y “unit” que tienen los tipos antes mencionados.
Que se cumplan las propiedades de elemento neutro y asociativa.

Nota: El lector con conocimientos de álgebra habrá pensado “¿Elemento neutro y asociativa? ¿No era esto lo que definía un monoide? ¿Tiene que ver con el nombre de mónada?”. La respuesta es sí. Un monoide es lo que se forma con “int->int” donde el tipo de entrada es igual al tipo de salida. Una mónada es la generalización donde los tipos no son siempre iguales.

De los lugares en los que habitan las mónadas

La parquedad de los requisitos de las mónadas hace que aparezcan por todos los lados y no únicamente como modelo de efectos secundarios. Son en general un modelo de computación (ver ejemplo 1.1 en el articulo original de Moggi para una lista de cosas que puede modelar una mónada).

Por ejemplo, los punteros con NULL se usan generalmente como mónadas. El constructor de tipo está claro que es el de los punteros. De “int” pasamos a “int*”. La función “unit” es simplemente obtener la dirección de un entero.

int a;
int* p=&a; // p=unit(a)

La función “bind” consiste en comprobar que el puntero no es NULL.

return p==NULL ? NULL : p->OperaYDevuelvePuntero() ;
// return bind(p, OperaYDevuelvePuntero);

Es fácil comprobar las propiedades correspondientes con estas operaciones, pero aún hay más. Cualquier colección iterable es una mónada. Sí, así a lo bestia: vectores, conjuntos, listas, mapas, tablas hash, etc. Todos son mónadas. El constructor de tipo es el de la colección que queramos. Por ejemplo, “vector<int>”.

La función “unit” es bien sencilla: la colección con un único elemento.

vector<int> v;
v.push_back(3);
// v=unit(3)

La función “bind” es equivalente a iterar y mezclar.

vector<int> r;
foreach (x in v) r.append(Procesa(x));
// r=bind(v, Procesa)

Ojo que “Procesa” devuelve un vector y “append” mezcla vectores. Si “Procesa” fuera obtener la lista de divisores, entonces

bind([1, 6, 21], Procesa) = [1, 1, 2, 3, 6, 1, 3, 7, 21]

Esta propiedad del “bind” de separar, iterar y combinar es la que le da tanta utilidad. De hecho, debido a esto, “Procesa” también serviría para filtrar, transformar, unir y casi cualquier otra operación que se quiera realizar con la colección. Lo que no quita para que también la colección tenga sus operaciones propias no monádicas.

Pero con todo esto habría ya material para otra entrega en la que tendríamos que hablar de comprensiones monádicas, la notación “do” y empezar a usar muchas funciones anónimas.

miniSL parte 11 - Operaciones sobre el montículo

2011-03-13T13:46:00.001+01:00

Ya hemos descrito el montículo en la parte octava. Ahora vamos a realizar dos tipos de operaciones sobre él. El primer grupo es el de las operaciones de reserva de memoria, mientras que el segundo grupo son las operaciones de liberado de memoria. En este post veremos las del primer grupo.
Inicialmente tenemos la creación de una celda genérica con dos referencias.

CELL& Script::CreateCell(CELL_TYPE ct, CELL* first, CELL* second)
{
 CELL* p;
 if(m_FirstUnused==NULL)
 {
  CELL c;
  m_Cells.push_back(c);
  p=&m_Cells.back();
 }
 else
 {
  p=m_FirstUnused;
  m_FirstUnused=p->next_unused;
 }
 p->mark=false;
 p->type=ct;
 p->head=first;
 p->tail=second;
 return *p;
}

Somos astutos y antes de reservar memoria (con el push_back) vemos si tenemos alguna celda libre ya reservada. Esto es algo ineficiente porque la celda que reservemos no vuelve a liberarse realmente, sólo se apunta como liberada. Todo sea por ser simples en la implementación.
Para crear celdas de otros tipos, primero creamos una celda genérica con Script::CreateCell y luego cambiamos sus campos específicos. Por ejemplo, para una cadena no interna.

CELL& Script::CreateString(STRING const& val)
{
 CELL& c=CreateCell(STRING_LIT);
 c.string_val=new STRING(val);
 return c;
}

En el caso de una cadena interna hemos de recurrir a las técnicas comentadas en la parte séptima. En concreto, usaremos el mapa m_InternedStrings para comprobar si ya tenemos o no la cadena internada. Si es así, la usamos. Si no, la creamos y la guardamos en el m_InternedStrings.

CELL& Script::CreateName(STRING const& val)
{
 STRING_MAP::const_iterator i=m_InternedStrings.find(val);
 if(i==m_InternedStrings.end())
 {
  CELL& c=CreateCell(NAME_CODE);
  i=m_InternedStrings.insert(std::make_pair(val, &c)).first;
  c.string_val=&i->first;
 }
 return *i->second;
}

Aquí se ve el truco comentado en la parte séptima: se usa la propia clave del mapa como la cadena interna. Esto nos fuerza a realizar la inserción en dos partes. Primero la celda de tipo NAME_CODE sin ningún puntero iniciado y, luego, se inicia el puntero string_val a la dirección de la clave i->first.

Para crear un entorno necesitamos crear adicionalmente su tabla de símbolos.

CELL& Script::CreateEnvir(CELL* parent)
{
 CELL& c=CreateCell(ENVIR_VAL);
 c.envir_table=new ENVIR_TABLE;
 c.parent_envir=parent;
 return c;
}

Y más sencillo aún son las funciones nativas porque son trozos de código que no se elimina nunca. En este caso necesitamos una función especial meramente porque el tipo es NATIVE y no CELL.

CELL& Script::CreateNative(NATIVE native)
{
 CELL& c=CreateCell(NATIVE_VAL);
 c.native=native;
 return c;
}

Con esto está la creación de celdas completada. En el siguiente apartado veremos cómo se usa el recolector de basura (garbage collector) del cual ya adelantamos algo en la parte octava.

Estándar WebGL 1.0 publicado

2011-03-04T10:40:00.000+01:00

Llevamos unos días con noticias sobre nuevos estándares que no paramos. Ayer, tres de marzo, salió otro estándar. Esta vez es WebGL, un contexto de renderización para el elemento CANVAS de HTML5. Cada vez los programadores de Javascript sobre la web tienen más y más recursos multimedia. ¿Será capaz el HTML5 de desbancar a otros sistemas como Flash o Silverlight como se proponía?

Tenemos finalistas para el SHA-3

2011-03-03T11:03:00.000+01:00

Los SHA (secure hash algorithm) son una serie de algoritmos establecidos por la Agencia Americana de Tecnología para la criptografía. Si no sabes mucho de criptografía, puedes aprender todo lo que hace falta saber en una hora. Parece ser que según van saliendo los algoritmos se van buscando sus fallos y, por ejemplo, ya te avisan de que no uses el SHA-1 y que vayas pasándote al SHA-2. Es probable que de aquí a poco también empiecen a aparecer grietas en este último por lo que es importante ir preparándose para el SHA-3.

El SHA-3 no está decidido aún, pero el concurso ha llegado a su final donde sólo quedan cinco candidatos posibles. Los nombres de los algoritmos son:

BLAKE
Grøstl
JH
Keccak
Skein

Para los curiosos que quieran saber qué es lo que cuenta para que un algoritmo de hash criptográfico sea bueno, el informe de su evaluación está aquí.

Unicode 6.0

2011-03-02T16:58:00.000+01:00

Hace unos días se publicó la nueva versión del estándar Unicode. No hay cambios significativos, únicamente la introducción de nuevos caracteres. La lista diferencial de cambios está aquí y las tablas de códigos completas aquí.

Minipost para el ahorro de energía

2011-02-27T11:13:00.000+01:00

Simplificando mucho.

	¿Se apaga la CPU?	¿Se apaga la RAM?	¿Se cierra la sesión?
Encendido	No	No	No
Suspendido (Modo S3)	Sí	No	No
Hibernado (Modo S4)	Sí	Sí	No
Apagado	Sí	Sí	Sï

Nota: Para los modos ver ACPI.

miniSL parte 10 - Extracción de valores

2011-02-23T13:53:00.000+01:00

Si imprimir los valores de una celda fue fácil, obtenerlos va a ser aún más fácil. Podríamos leer directamente los campos de una celda, pero es más conveniente encapsular las operaciones más comunes en una única función miembro de CELL que lance una excepción si algo va mal.

int GetInteger()const
{
 if(type==INT_LIT)
  return int_val;
 throw L"Integer expected";
}

bool GetBoolean()const
{
 if(type==BOOL_VAL)
  return bool_val;
 throw L"Boolean expected";
}

STRING const& GetString()const
{
 if(type==STRING_LIT)
  return *string_val;
 throw L"String expected";
}

El único caso no trivial aparece cuando queremos explorar o modificar los entornos. Recordemos que cada celda de entorno tiene una tabla de símbolos (un ENVIR_TABLE que era un typedef de std::map<CELL*, CELL*>) en el campo envir_table y un entorno padre en el campo parent_envir. Estas complejidades son necesarias para código con una forma similar a esta:

> define(a, 5)
[]
> define(f, lambda([x],[x+a]))
[]
> f(3)
8

Cuando se definen a y f, se hace en el entorno global. Cuando se llama a f(3) se crea un nuevo entorno local donde x se vincula a 3. ¿Pero cuánto vale a en el entorno local? ¡No está definida en el entorno local, está definida en el entorno global! La solución es crear un enlace, el del entorno padre, de la forma indicada en el diagrama de abajo.

De esta manera están disponibles tanto la a como la propia f dentro del cuerpo de la f. De todo esto, lo único que necesitamos por ahora son dos funciones en la clase Script. La primera hace la búsqueda de un nombre que se realiza siempre de la misma forma. Primero, buscamos en el entorno actual y, si no se encuentra, repetimos recursivamente buscando en el entorno padre.

CELL* Script::FindName(CELL& name, CELL& envir)
{
 //Try to find the name in current environment
 ENVIR_TABLE::const_iterator i=envir.envir_table->find(&name);
 if(i!=envir.envir_table->end())
  return i->second;

 //Failed, try parent
 if(envir.parent_envir!=NULL)
  return FindName(name, *envir.parent_envir);

 //Failed also, not found
 return NULL;
}

La segunda, para cambiar un nombre, hace casi lo mismo: buscamos el nombre en el entorno actual cambiándolo si lo encontramos y, si no lo encontramos, llamamos recursivamente la función en el entorno padre. Si no hay entorno padre es que el nombre no estaba definido.

void Script::ChangeName(CELL& name, CELL& envir, CELL& value)
{
 //Try to find the name in current environment
 ENVIR_TABLE::iterator i=envir.envir_table->find(&name);
 if(i!=envir.envir_table->end())
 {
  (*envir.envir_table)[&name]=&value;
  return;
 }

 //Failed, try parent
 if(envir.parent_envir!=NULL)
  return ChangeName(name, *envir.parent_envir, value);

 //Failed also, not found
 throw L"Name to be changed is undefined";
}

También necesitaremos la operación de definición de un nombre en el entorno actual como hace define, sin buscar en los entornos padre, pero coincide exactamente con la operación básica de inserción en std::map así que, aunque sea algo incorrecto al romper la abstracción sobre la implementación, usaremos directamente la clase std::map.

Hasta ahora sólo hemos explicado cómo leer una celda. En la siguiente entrada hablaremos de la creación de celdas.

Purgando conocimiento

2011-02-15T10:28:00.001+01:00

Leo en Reddit que los administradores de Wikipedia se están dedicando a hacer purga de los lenguajes de programación menos conocidos como Nemerle (una maravilla de lenguaje basado en macros), Factor (de hecho leo el blog de su creador), Alice ML y otros.

Me causa una gran pena porque conocí estos lenguajes (y otros más) gracias a la Wikipedia. Quizás haya que ser de una universidad americana para que te tengan en cuenta.

Edit: Parece que Factor aún no ha caído. Los otros dos están borrados ya.
Edit2: 19-02-2011 Nemerle ha vuelto a aparecer, pero Alice ML sigue borrado.

¿Especificación de requisitos o especificación de requerimientos?

2011-02-10T13:26:00.000+01:00

Otro caso en el que usar Google no nos ayuda a discernir cuál está bien o cual está mal. Si usamos "requerimientos" obtenemos más o menos las mismas páginas que si usamos "requisitos".

Por otra parte, el diccionario lo dice claramente: "requisito" es la circunstancia que se debe dar mientras que "requerimiento" es la acción de requerir algo (es sinónimo de "petición", "demanda", etc.)

Resumiendo:

"Especificación de requisitos" es la especificación de las circunstancias que se deben dar (para que el programa sea correcto).
"Especificación de requerimientos" sería la especificación de las peticiones o demandas. Obviamente, esta es la que se usa mal.

Las tres cosas que diferencian funciones y macros

2011-02-08T15:40:00.000+01:00

Hace tiempo hablé sobre las similitudes entre funciones y macros. Esta vez voy a hablar de sus diferencias.

Hay tres cosas que una macro puede hacer y una función no.

1) El control del flujo de ejecución

Una función no puede controlar qué pasa con sus argumentos. No puede controlar si se evalúan o no. No puede recuperarse de un error si uno de sus argumentos falla. No puede hacer nada. De hecho, cuando evaluamos

f(1+2, 3*4)

Lo que ocurre es que primero evaluamos los argumentos.

f(3, 12)

Y luego le pasamos el control a "f" que hará lo que tenga que hacer. Esto no es problema en un lenguaje funcional ya que no vamos a tener efectos secundarios de ningún tipo, pero sí que lo es en un lenguaje con efectos secundarios.

haz_dos_veces(print("a"))

Si "haz_dos_veces" es una función, vamos a evaluar primero los argumentos. Se imprimirá una vez "a" y pasaremos el resultado (posiblemente de tipo unitario) a la función que, haga lo que haga, no va a poder reimprimir la "a".

En el caso de que tuviéramos referencias a funciones entonces todo cambia. Ahora se puede pasar en el argumento la referencia a la función que hace lo que yo quiero.

define_funcion f() { print("a") }
haz_dos_veces(f)

Ahora sí que "haz_dos_veces" puede llamar dos veces a la función pasada e imprimir "a" dos veces. Así que cuando hay referencias a funciones esta diferencia entre macros y funciones no cuenta tanto; pero cuenta porque hay que envolver en una función el código que queremos pasar.

Las macros pueden hacerlo sin envolver nada.

define_macro haz_dos_veces(f) { f; f }
haz_dos_veces(print("a"))

Se expande a

print("a");print("a")

2) Manejo de entornos

El ejemplo más claro de esta posibilidad es la definición de símbolos en el entorno dinámico, aunque no sea lo más seguro y fácil de entender.

define_macro haz_a_cero() { a=0; }
a=1;
haz_a_cero(); //Expande a a=0
print(a) //Imprime 0 porque ha sido modificado por la macro

Si fuera una función, hacer "a" valer cero dentro de la función sólo modifica el entorno local de la función.

define_funcion haz_a_cero() { a=0; }
a=1;
haz_a_cero();
print(a) //Imprime 1 porque no se ha modificado nada

Como ocurría con el apartado anterior, si tenemos referencias a variables (punteros), una función podría simular este comportamiento.

define_funcion haz_cero(x) {*x=0; }
a=1;
haz_cero(&a);
print(a) //Imprime 0

Sin embargo, la inspección del entorno la hemos tenido que hacer en la llamada con el "&a". La función no puede elegir qué símbolo va a cambiar. Si hubiéramos pasado "&b" la función no se quejaría y cambiaría "b". Con la macro esto no ocurría ya que ella misma inspeccionaba el entorno dinámico.

3) Procesado de código

Esta es la diferencia realmente grande. Los argumentos de una macro pueden significar algo completamente distinto a lo que se cree porque la macro puede procesar el código y cambiarlo. Por ejemplo, la macro "bromista" cambia los "+" por "-".

bromista(5+3) //Expande a 5-3

Con este tipo de transformaciones lo que realmente tenemos es la capacidad de modificar la semántica. En cierta forma, estamos ya acostumbrados. Supongamos un lenguaje en el que tengamos que declarar variables antes de usarlas, como JavaScript.

f(a=3); //Error, a no definido.
var a=3; //Define a y le da el valor 3

El significado de "=" cuando se evalúa y cuando se escribe tras "var" es distinto. Si contemplamos "var" como una macro, lo que hace es buscar expresiones con la forma identificador-igual-valor. Para cada una de esas expresiones (en vez de evaluarlas como hizo la función "f"), define la variable en el entorno y le da ese valor.

Es esta capacidad de analizar y transformar el código de sus argumentos lo que hacen las macros únicas y superiores a las funciones.

miniSL parte 9 - Imprimiendo celdas

2011-02-02T13:02:00.001+01:00

La impresión de celdas en miniSL es relativamente sencilla usando un algoritmo recursivo. Según el tipo de celda, imprimimos su contenido tal y como se describió en la quinta parte de esta serie.

void CELL::Print(OSTREAM& o)const
{
 switch(type)
 {
 default:  o << L"{{**UNKNOWN**}}"; break;
 case UNUSED: o << L"{{**UNUSED**}}"; break;
 case INT_LIT: o << std::dec << int_val; break;
 case BOOL_VAL: o << (bool_val ? L"true" : L"false"); break;
 case LAMBDA_VAL:o << L"{{ "; code->Print(o); o << L" }}"; break;
 case NATIVE_VAL:o << L"{{NATIVE}}"; break;

Hasta aquí ningún extraño aparte de usar una llamada recursiva para imprimir el contenido del código en las funciones lambda. Para imprimir las cadenas debemos tener cuidado ya que pueden contener caracteres de control que no son imprimibles y hay que escaparlos.

case STRING_LIT:PrintEscapedString(o, *string_val); break;
 case NAME_CODE: o << L"@"; PrintEscapedString(o, *string_val); break;

Es importante notar que los nombres no son únicamente cadenas. Las cadenas se evalúan a sí mismas mientras que los nombres se evalúan buscándolos en el entorno actual. Para distinguirlos bien, pondremos el prefijo @ delante de ellos. De esta manera permitimos usar nombres con espacios o símbolos en ellos. Veremos que será muy útil para extender la sintaxis.

La impresión de las listas la vamos a hacer en la función CELL::PrintList() para así poder reutilizar el código a la hora de imprimir celdas COMBINE_CODE.

case CONS_CTOR: case EMPTY_LIT:
  o << L"[";
  PrintList(o, L", ");
  o << L"]";
  break;
 case COMBINE_CODE:
  op->Print(o);
  o << L"(";
  operands->PrintList(o, L", ");
  o << L")";
  break;

Finalmente, la impresión de un entorno se realiza iterando sobre él.

case ENVIR_VAL: o << L"{{ENVIR ";
  for(ENVIR_TABLE::const_iterator i=envir_table->begin(); i!=envir_table->end(); ++i)
  {
   o << *i->first->string_val << L"= ";
   i->second->Print(o);
  }
  o << L"}}";
  break;
 }
}

Nos queda por implementar entonces, la impresión de listas y de cadenas escapadas. Ambas funciones son relativamente directas.

void CELL::PrintList(OSTREAM& o, STRING const& separator)const
{
 for(CELL const* c=this; c->type==CONS_CTOR; c=c->tail)
 {
  if(c!=this)
   o << separator;
  c->head->Print(o);
 }
}

void CELL::PrintEscapedString(OSTREAM& o, STRING const& s)
{
 o << L"\"";
 for(STRING::const_iterator i=s.begin(); i!=s.end(); ++i)
 {
  if(*i<32) o << L"\\x" << std::hex << (unsigned int)(unsigned)*i << L";";
  else  o << *i;
 }
 o << L"\"";
}

Por ejemplo, la impresión de una lista, una función lambda y un booleano se ve así:

[1, 2, 3]
{{ [[@"x"], [@"+"(@"x", @"x")]] }}
true

Se observa que tanto la lista como el booleano es directamente código, pero la función lambda es un valor que no es representable directamente en código. Por eso lo vamos a escribir entre dobles llaves. Estos valores deben obtenerse como el resultado de una llamada. De hecho, también se pueden imprimir celdas del tipo COMBINE_CODE que son precisamente esas llamadas. Así, f(x,y) se imprimiría así:

@"f"(@"x", @"y")

De esta manera podemos ver los valores y el código que tenemos en el montículo, pero no nos basta con verlos. Debemos también poder utilizarlos. Para eso vamos a introducir una serie de funciones que nos permita extraer valores. Estas funciones van a ser también muy sencillas. Las dejaremos para la siguiente entrada.

Escenas y escenas.

2011-01-27T11:01:00.000+01:00

Como viene siendo habitual, de vez en cuando hablo sobre otros temas para descansar de la informática. Espero que se me disculpen estas pequeñas infidelidades.

Cuando estamos creando una historia lo más usual es que llegue un momento en el que tengamos la línea argumental completamente especificada. Sabemos qué va a ocurrir y cuándo. Qué personajes están involucrados y qué repercusión tienen sus actos. Sin embargo, hay que concretar todo lo ideado en escenas. Esta fase es el desglose en escenas (scene breakdown) o escaleta.

No puedo decir cómo se hace la escaleta porque, honestamente, no lo sé, pero sí que puedo dar una idea de las escenas con las que vamos a acabar. Son, resumidamente, de tres tipos.

Escenas estructurantes. Son las escenas que dan información sobre la línea argumental. Hacen avanzar la historia o bien mostrando actos de los personajes o bien dándonos información. Ya sabéis, "Luke, yo soy tu padre" no es un acto en sí, pero es un gran trozo de información. Es interesante hacer notar también la llamada clausura. Es lo que no se muestra, pero que el lector o espectador se imagina. Una escena puede no mostrar nada directamente, pero seguir influyendo en la historia debido a que insta al lector a imaginar lo que ha ocurrido. ¿O alguien vio cómo mataron al caballo en El Padrino?
Escenas caracterizantes. Estas escenas no transmiten nueva información sobre la línea argumental, pero sí sobre los personajes. Muestran un aspecto de su personalidad, o ponen a los personajes en una situación en la cual deben mostrar su personalidad. El ejemplo típico serían las escenas iniciales de las películas de James Bond. No suelen tener nada que ver con el resto de la película, pero dejan claro quién es el jefe. Una escena de este tipo también puede servir para crear un ambiente, una situación, describir un lugar o incluso sensaciones. Por ejemplo, esas escenas en las películas de terror que parece que va a pasar algo, que hay alguien en la casa, pero al final sólo es el vecino que ha perdido las llaves.
Escenas irrelevantes. Escenas de relleno que pueden ser quitadas.

Rara vez una escena es de uno de estos tipos únicamente. Lo que sí está claro es que las escenas irrelevantes son las que aburren ya que no contribuyen a la historia. Entiendo que es importante detectar escenas de este tipo (o que sean en gran medida irrelevantes) y tratar de eliminarlas.

¿Secuencial o Paralelo?

2011-01-20T11:01:00.002+01:00

Este es un resumen de la charla de Guy Steele sobre paralelismo en Strange Loop.

SECUENCIAL	PARALELO
Se ejecuta un código A, luego se usa el resultado de A en otro código B.	Se ejecutan los códigos A y B independientemente. Luego se mezclan los resultados.
Reusa el espacio. Sólo hay que almacenar un resultado.	Usa espacio extra para desacoplar los cálculos.
Procesa una cosa cada vez y va acumulando resultados.	Descompone y mezcla resultados. Divide y vencerás.
Requiere iniciar el acumulador con el elemento neutro de la operación. acc=elem_neutro; for(i=0; i<n; ++i) acc=acc @ x[i]	Requiere asociatividad en la operación para ir mezclando resultados. No se puede procesar en paralelo: [$$ x_0 \star (x_1 \star (... )) $$]

Se basa en trucos para optimizar. Reordenación de instrucciones. Desplegado de bucles. Reutilización de registros. Ejecución especulativa. Predicción de saltos. etc.	Se basa en propiedades algebraicas para optimizar. Asociativa: La forma de agrupar operaciones no importa. Conmutativa: El orden de los operandos no importa. Idempotente: Las repeticiones no importan. Identidad: El elemento neutro puede ser ignorado. Cero: El resto de elementos puede ser ignorado.

Así que hay que hacer que el programador deje de pensar en acumuladores y pase a pensar en propiedades algebraicas. Es decir, usar catamorfismos en vez de bucles. Los catamorfismos no son más que funciones que toman una estructura de datos y devuelven un valor a partir de ella con la propiedad de que son morfismos. En el caso de sumar una lista de números sería algo así como convertir la concatenación en suma.

[$$ f( [ 3, 5 ] .. [4, 7] ) = f( [3,5] ) + f( [4, 7] ) $$]

Esto significa a su vez que hay que buscar una operación con las propiedades algebraicas que deseemos (o podamos obtener), lo cual puede llevar a comprender más profundamente el problema.

La especificación del catamorfismo es similar al uso de sumatorios en matemáticas. No se especifica el orden de la suma, sólo que hay que sumar los elementos.

[$$ \sum_{i=1}^{n} {x_i} $$]

En programación esto se tendría que hacer usando funciones de alto nivel como fold pero asumiendo la asociatividad.

fold_assoc( suma, [3, 5, 4, 7] )

Así el compilador podría optimizar usando paralelismo sin que el programador tuviera que luchar con sincronizaciones y demás.

El BBVA le da un premio a Donald Knuth

2011-01-19T10:56:00.000+01:00

Van un poco tarde porque este hombre lleva desde 1963 publicando libros, pero bueno. Todo sea por que se conozca algo más en España al creador de TeX, del algoritmo que convierte ecuaciones en reglas de reescritura confluentes, de otro que busca subcadenas y de El Arte de Programar Computadores.

Fuente: El Mundo

miniSL parte 8 - El montículo

2011-01-15T13:06:00.002+01:00

Llega el momento de pensar dónde y cómo almacenar las celdas en memoria. La forma en la que vamos a hacerlo es la siguiente. Usaremos un std::deque para reservar memoria. Los deques permiten ir añadiendo memoria conforme se necesite y no mueven los bloques de memoria una vez reservados.

De todas las celdas que hayamos reservado, usaremos unas y tendremos otras libres, sin usar. Utilizaremos la recolección de basura para pasar celdas antes usadas pero ahora ociosas a celdas sin usar y libres para su reciclado.

La recolección de basura es un procedimiento que puede ser o bien muy complejo o bien muy simple. En este caso, y teniendo en cuenta que miniSL intenta implementarlo todo de la forma más simple y reducida, nos inclinaremos por el algoritmo más simple de recolección de basura. El llamado mark and sweep (marca y barre).

El mark and sweep funciona en dos pasos. El primer paso detecta las celdas en uso. ¿Cómo hace eso? Muy simple. O bien es una celda raíz (que siempre está en uso) o bien nos referencian desde otra celda en uso. Estas celdas en uso son marcadas. El segundo paso es barrer (=reciclar) todas las celdas que no están marcadas y limpiar la marca en las que sí.

La siguiente figura muestra a) el conjunto raíz, b) los punteros entre celdas y c) las marcas. Las celdas que en c) no estén marcadas (las blancas) serán las reclamadas por el recolector de basura y pasarán a estar libres para un posterior uso.

En la implementación lo primero que tenemos es el std::deque de almacenamiento de celdas.

CELL_STORAGE m_Cells;

Recordemos que definíamos CELL_STORAGE así:

typedef std::deque<CELL> CELL_STORAGE;

También necesitamos saber si hay celdas libres. Las pondremos todas en una lista simplemente enlazada que empieza en el campo m_FirstUnused.

CELL* m_FirstUnused;

Para reservar una celda primero vemos si hay alguna libre. Si no, aumentamos el std::deque reservando memoria para una celda más. Esto no es muy económico ya que lo interesante habría sido devolver la memoria usada por las celdas libres. Estamos actuando más bien como un pool que como un gestor de memoria.

CELL& Script::CreateCell(CELL_TYPE ct, CELL* first, CELL* second)
{
 CELL* p;
 if(m_FirstUnused==NULL)
 {
  CELL c;
  m_Cells.push_back(c);
  p=&m_Cells.back();
 }
 else
 {
  p=m_FirstUnused;
  m_FirstUnused=p->next_unused;
 }
 p->mark=false;
 p->type=ct;
 p->head=first;
 p->tail=second;
 return *p;
}

El algoritmo de marcado es recursivo de manera que explora todo el grafo de referencias (punteros entre celdas) en profundidad. Dependiendo del tipo de celda, alguno o ninguno de sus campos serán referencias que hay que explorar. Evitamos los posibles ciclos no volviendo a marcar las celdas ya marcadas.

void Script::GCMark(CELL* c)
{
 if(c==NULL || c->mark)
 return;

 c->mark=true;

 switch(c->type)
 {
 case UNUSED:  throw L"Marking unused cell";
 case CONS_CTOR:  GCMark(c->head); GCMark(c->tail);  break;
 case LAMBDA_VAL: GCMark(c->code); GCMark(c->closure);  break;
 case COMBINE_CODE: GCMark(c->op);  GCMark(c->operands); break;

 case ENVIR_VAL:
  GCMark(c->parent_envir);
  for(ENVIR_TABLE::const_iterator i=c->envir_table->begin(); i!=c->envir_table->end(); ++i)
  {
   GCMark(i->first);
   GCMark(i->second);
  }
  break;
 }
}

El caso más laborioso es el de los entornos. En ellos hay que iterar su contenido y explorarlo para el marcado.
El borrado ocurre en la rutina de barrido. Es simple y su única dificultad radica en las celdas especiales que contienen algún dato externo. Ya vimos uno de estos casos en las cadenas internas. Las cadenas normales y los entornos son otros casos similares. Cada uno de ellos ha de tener un borrado específico.

int Script::GCSweep()
{
 int count=0;
 for(CELL_STORAGE::iterator i=m_Cells.begin(); i!=m_Cells.end(); ++i)
 {
  if(i->mark)
  {
   i->mark=false;
   continue;
  }

  if(i->type==UNUSED)
   continue;

  ++count;

  switch(i->type)
  {
  case STRING_LIT: delete i->string_val;      break;
  case ENVIR_VAL:  delete i->envir_table;      break;
  case NAME_CODE:  m_InternedStrings.erase(*i->string_val); break;
  }

  i->type=UNUSED;
  i->next_unused=m_FirstUnused;
  m_FirstUnused=&*i;
 }
 return count;
}

Como conjunto raíz vamos a tener únicamente el entorno global. Añadimos una referencia a la celda de entorno de que lo contenga y lo marcamos en la recolección de basura.

int Script::GarbageCollect()
{
 GCMark(m_GlobalEnvir);
 return GCSweep();
}

A partir de aquí hemos de recordar que el entorno global es una celda destacada. De hecho, estará referenciada en la clase Script.

CELL* m_GlobalEnvir;

El lector atento habrá visto que hemos retornado el número de celdas barridas en el recolector de basura. El retorno del número de celdas es un buen sistema para depurar el recolector de basura, pero no es el único. De hecho, nos ofrece poca información. Otro sistema que va a ser útil no sólo para el recolector de basura sino también para observar los resultados de las evaluaciones es la impresión de celdas. En la siguiente entrada nos dedicaremos a esta tarea.

2010, el primer año ciberpunk de la historia

2011-01-03T18:00:00.000+01:00

O eso es lo que dice Herb Sutter en su blog. Sus alegaciones son las siguientes:

Primer ataque cibermilitar entre países. En concreto, el sabotaje de las centrifugadoras de uranio enriquecido de Iran por parte del gusano informático Stuxnet.
Organizaciones no gubernamentales beligerantes en la red. Como Wikileaks y sus filtraciones. El resultado ha sido la presión por parte de los EEUU a las empresas que gestionaban la financiación a esta organización (Visa, Mastercard, Paypal...)
Grupos de ciberataque como Anonymous que, en represalia por los bloqueos arriba mencionados, atacaron las empresas que los realizaron.
Ciberdisidentes perseguidos. En este caso el propio fundador de Wikileaks con extrañas imputaciones en un oscuro caso de acoso sexual y altas fianzas tras su detención.
Los computadores empiezan a ver. Hasta ahora una imagen era únicamente una amalgama de píxeles de los cuales era difícil que el ordenador entendiera algo. A partir de la aparición de Kinect y su mapa de profundidad, el ordenador no sólo mira sino que también ve y entiende lo que ve. Además, hackeado por un español.
Incremento exponencial del cibercrimen. En concreto, en 2010 se ha creado el 34% de todo el malware jamás creado.

Y tú que opinas, ¿somos ya ciberpunks o no?

Por qué no existe el compresor perfecto o los nidos de las palomas

2010-12-26T17:56:00.000+01:00

Supongamos que existe un compresor que toma cualquier cadena de bits y la comprime en otra cadena con menos bits. Llamaremos [$c(x)$] al algoritmo compresor y [$d(x)$] al descompresor.

Está claro que

[$$c(0)=\epsilon$$]

Puesto que la cadena vacía [$\epsilon$] es la única cadena con menos longitud que la cadena [$0$]. ¡Pero también es inmediato para la cadena [$1$]!

[$$c(1)=\epsilon$$]

Entonces, ¿cuánto es [$ d(\epsilon) $]? Porque sólo podrá ser una de las dos cadenas iniciales, pero no las dos.

Esto es el llamado principio del palomar. Sólo tenemos una cadena de longitud cero para almacenar dos cadenas de longitud uno. Si en un palomar hay más pichones que nidos, en algún nido habrá dos pichones (y no podremos descomprimirlos).

Por tanto, no existe el compresor perfecto. Habrá cadenas que comprima y otras que expanda. El truco está en que comprima las cadenas más usadas y expanda las menos usadas.

miniSL parte 7 - Las cadenas internas

2010-12-20T13:25:00.000+01:00

El intérprete que estamos desarrollando es un intérprete basado en entornos. Esto quiere decir que cuando encontremos una variable y queramos saber su valor, vamos a buscar el nombre de la variable en el entorno actual. El entorno será un diccionario (std::map) de forma que habrá que comparar las cadenas del nombre de la variable y las claves almacenadas en el diccionario.

Comparar cadenas es un algoritmo de complejidad O(n) lo que significa que va a ralentizar todo el proceso. Para solucionar esto la estrategia más común es usar lo que se llaman cadenas internas (interned string). De cada cadena interna sólo va a haber una única copia de forma que podamos usar su dirección para comparar cadenas. Así que la comparación de cadenas se reduce a una comparación de punteros.

Para convertir una cadena a su cadena interna bastará buscar la copia única o, si no existe aún, crearla.
STRING_MAP es el diccionario que a cada cadena le asigna una única copia. Esta copia será una celda del tipo NAME_CODE. De hecho, la única diferencia entre NAME_CODE y STRING_VAL es que en el primer caso la cadena es interna y en el segundo no (puede haber copias).

ENVIR_TABLE es ahora la tabla de símbolos que relaciona un NAME_CODE (el nombre de la variable) con un valor. Cada entorno tendrá un ENVIR_TABLE y un puntero opcional al entorno padre.

La clase Script, que contendrá todo el estado del intérprete del lenguaje que estamos creando, también tendrá que guardar el diccionario de cadenas internas. Lo haremos con la siguiente declaración de variable miembro privada.

STRING_MAP m_InternedStrings;

Los casos de uso serán buscar o crear una cadena interna y borrarla. El valor de la cadena es accesible mediante CELL::string_val.

La creación es algo más compleja que la destrucción ya que hemos de comprobar si ya está la cadena en nuestro diccionario.

CELL& Script::CreateName(STRING const& val)
{
 STRING_MAP::const_iterator i=m_InternedStrings.find(val);
 if(i==m_InternedStrings.end())
 {
  CELL& c=CreateCell(NAME_CODE);
  i=m_InternedStrings.insert(std::make_pair(val, &c)).first;
  c.string_val=&i->first;
 }
 return *i->second;
}

Aprovechamos que la implementación de std::map es un árbol (y no mueve los nodos por memoria una vez creados) para usar la propia cadena que hace de clave como la única copia de la cadena. Por esa razón hacemos c.string_val=&i->first. Esto no podría hacerse si la implementación fuera una tabla hash ya que estas tablas cambian de tamaño y requieren cambiar de posición de memoria las claves.

La destrucción, por otro lado, es sencilla.

m_InternedStrings.erase(*i->string_val);

Aunque hay que ver esta línea en el contexto del recolector de basura. Dedicaremos la siguiente entrada a implementar el recolector de basura.