Por qué no existe el compresor perfecto o los nidos de las palomas

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

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.

C++: Conceptos y traits

Toda esta entrada es una especie de resumen personal de la presentación de Bartosz Milewski que podéis ver aquí más algunas ideas extra de mi propia cosecha.

Conceptos mediante traits

Antes de nada hay que entender que los template en C++ no pueden compilarse inmediatamente porque no sabemos los tipos que vamos a tener cuando instanciemos el template.

El problema podría ser resuelto si forzamos a que estos tipos cumplan un contrato, una interfaz. La idea es hacerlo mediante los llamados conceptos. Por ejemplo, un tipo sobre el que podamos comprobar la igualdad, tendría un concepto parecido a este:

concept Eq<T>
{
 bool operator==(T const& l, T const& r);
}

Ahora podríamos agregar tipos que cumplen ese concepto mediante lo que se denomina una asignación de concepto (concept_map).

concept_map Eq<int>
{
 bool operator==(int const& l, int const& r) { return l==r; }
}

Hay que notar que el == de los enteros no es inmediatamente Eq ya que el concepto Eq podría significar algo más que "tiene igual". Podría significar "tiene igual y es reflexivo, simétrico y transitivo" por lo que sólo el programador sabe si puede o no hacer un concept_map en función de la semántica del concepto.

La idea es que ahora, en un template, se pueda usar el igual del concepto en vez del igual de la clausura dinámica.

template<Eq T>
T f(T const& a, T const& b)
{
 return a==b ? a : b;
}

El == este sería el del concepto Eq y no una función que haya que esperar a tener el tipo T para encontrarla en tiempo de instanciación. Por tanto, este template se podría comprobar estáticamente en declaración. Sin saber si T es un int u otra cosa.

La manera de implementar algo parecido en el C++ actual (aunque sin la ventaja de la comprobación en declaración) es mediante el uso de traits. En vez de tener Eq como un concepto (ya que el C++ actual carece de ellos) lo tendremos como una clase Eq<T> que significa "el tipo T es del concepto Eq". Para que el tipo T sea del concepto Eq deberá demostrarse que el operador == es parte de ese tipo.

template<typename T>
class Eq
{
public:
static bool operator==(T const& l, T const& r);
};

El concept_map no es más que una especialización demostrando que int se ajusta a lo requerido. El compilador de C++ actual no lo comprueba así que hemos de ser cuidadosos.

template<>
class Eq<int>
{
public:
static bool operator==(int const& l, int const& r) { return l==r; }
};

Finalemente, cuando usemos estos sucedáneos de conceptos, hay que usar la clase trait en vez de utilizar directamente el operador ==. En el caso de los conceptos puros el uso del == del concepto era implícito.

template<typename T>
void f(T a, T b)
{
return Eq<T>::operator ==(a, b) ? a : b;
}

Lo importante aquí es que es posible mediante esta técnica el separar la comprobación del template de su instanciación. Desafortunadamente, este conocimiento ha llegado a la comunidad de C++ unos veinte años después de que se estandarizaran los templates (como ya he comentado en una entrada anterior, incorrectamente). Aunque usemos Eq<T>::operator ==(a, b), el compilador tomará esta expresión como dependiente y no la comprobará estáticamente.

Extensión hipotética de C++

Esto no quiere decir que no se puedan introducir. Sólo quiere decir que hay que tener muchísimo más cuidado en cómo se hace puesto que interacciona con otras características del C++ de maneras indeseadas lo cual llevó a retirar los conceptos del estándar actual.

Una manera posible de introducirlo, pienso, sería subsanando las dos carencias que hemos comentado arriba.

1. Comprobar que las especializaciones implementan el template general. 
2. Evitar que se tomen como expresiones dependientes las que usen estos templates comprobados. 

Postulemos entonces una pequeña variación en C++ introduciendo unos templates cuyas especializaciones tengan que implementar su interfaz forzosamente. Usaremos la hipotética sintaxis abstract template.

abstract template<typename T>
class Eq
{
public:
static bool operator==(T const& l, T const& r);
};

Con esta hipotética sintaxis el compilador se quejaría de especializaciones como estas:

//ERROR: Eq<T> es abstract y su especialización Eq<int> no implementa ==
template<> class Eq<int>
{
public:
 static bool operator<(int const& l, int const& r) { return l<r; }
};

//ERROR: El segundo argumento de operator == no es de tipo adecuado.
template<> class Eq<int>
{
public:
 static bool operator==(int const& l, float const& r) { return l<r; }
};

Como el compilador sólo va a permitir las especializaciones que cumplan con el abstract template, tiene suficiente información para comprobar las expresiones que usen este abstract template, hayan sido especializadas o no. Por esta razón no es necesario que el uso de los abstract template sean dependientes.

template<typename T>
void f(T a, T b)
{
return Eq<T>::operator ==(a, b) ? a : b;
}

La expresión Eq<T>::operator ==(a, b), aunque depende de T, como lo hace a través de un abstract template, no es dependiente y se puede comprobar ahora. De hecho, se comprueba que operator== es miembro de Eq y tiene el tipo adecuado, por tanto, la función template f() es correcta. ¡Y lo sabemos antes de instanciar T!

Estas modificaciones que propongo son en principio seguras ya que si no introduces ningún abstract template todo sigue siendo compatible. No rompe ningún código. Son fáciles de realizar puesto que es añadir una pequeña regla en la definición de expresión dependiente y la comprobación de que se implementa una interfaz es bastante parecida a la de las funciones virtuales puras (aunque hay detalles y en los detalles está el diablo).

Otra cosa es que no cumpla todos los objetivos que se esperaban de los conceptos como su uso implícito. Vayamos por partes. Esto es un primer paso, veremos como solucionar el siguiente en otro momento.

Nota: Podríamos recurrir a la vinculación dinámica en vez de a un trait y tener

template<typename T>
class Eq
{
public:
 bool (*operator==)(T const& l, T const& r); //Sin static
};

Que se usaría así

template<typename T>
void f(Eq<T>& demo, T a, T b)
{
return demo.operator ==(a, b) ? a : b;
}

Ahora bien, ¿para qué retardar la decisión a tiempo de ejecución? Muy sencillo. Este cambio permite compilar el template y generar código. Esto es lo que se llama compilación separada y aceleraría los tiempos de compilación. Como siempre, hay un compromiso entre perder algo de tiempo de ejecución o perder algo de tiempo de compilación.

Expresiones dependientes en templates de C++

El código

Existe un aspecto poco conocido a la hora de usar los templates de C++ que son las expresiones dependientes. Éstas dan un susto de vez en cuando a quienes las usan ya que son una mala implementación de las clausuras estáticas. El código ofensivo es el siguiente.

void f() { std::cout<<"A"; }

template<typename T>
struct B {
 void f() { std::cout<<"B"; }
};

template<typename T>
struct D : public B<T> {
 void g()
 {
  f();  //¿Imprime "A" o "B"?
 }
};

int main()
{
 D<char>::g();
}

Si llamamos a D<t>::g(), ¿se imprime "A" o se imprime "B"? Si se imprimiera "A" significa que se está usando el entorno global y si se imprime "B" significa que se está usando el entorno de la estructura D (que hereda de B). Esto está relacionado con la pregunta, ¿cuándo se compila/comprueba D? D se compila/comprueba parte cuando se declara (en el código de arriba donde pone template<typename T> struct D hasta la llave de cierre }; ) y parte cuando se instancia (cuando se hace T=char en D<char>::g() ).

Las clausuras 

Teniendo en cuenta que main() está en el entorno global y la estructura D es el entorno local de la definición de g(), el problema aquí es distinguir entre la clausura dinámica o la clausura estática. La clausura dinámica significa que si no encontramos la definición de un nombre en una declaración, buscamos en el contexto donde se está usando esa declaración (en D<char>::g()) . La clausura estática busca en el contexto donde se está declarando la declaración (en template...).

En los lenguajes basados en entorno, como el LISP o el Scheme, se usa la clausura estática, también llamada clausura léxica. Esto impide comprobar con facilidad si nuestra declaración es correcta porque no tenemos aún los tipos a los que vamos a instanciar (el char). Claro que esto no es problema ni en LISP ni en Scheme porque son lenguajes dinámicos.

La decisión 

La "solución" de los creadores de C++ fue separar la declaración del template en dos partes: la parte dependiente de los parámetros de tipos (los T) y la parte independiente de los mismos. La parte independiente puede comprobarse estáticamente, mientras que la parte dependiente se deja para cuando se conozca el argumento de tipo para la instanciación (el char).

El gran problema es que comprobar significa también buscar las declaraciones de los nombres y, en el caso de arriba, según f() sea del contexto estático o dinámico será la que imprime "A" o imprime "B".

Es fácil ver que la herencia de la clase D es B<T> y, efectivamente, depende de T por lo que no se va a buscar ningún nombre hasta el momento de instanciación ( D<char>::g() ). Antes de la instanciación está la declaración ( desde template<typename T> struct D hasta la llave de cierre }; ) y resulta que el f() que hay dentro de la declaración de g() no depende de T. Eso significa que se busca el nombre ahí, en declaración y el que encuentra es el que imprime "A" ya que el que imprime "B" depende de T a través de la herencia y no lo va a ver hasta la instanciación.

El resultado, contraintuitivo, es que imprime "A". Si tu compilador imprime "B", no se ajusta al estándar. Puedes ver más de esto en el FAQ del C++.

La historia se repite

Todo el lío fue la decisión, desde mi punto de vista errónea, de intentar comprobar el template en declaración, antes de tener los argumentos de tipos para instanciar. En el 90% de los casos al final no puedes comprobarlo en declaración porque casi todo va a depender de T, ¡que para algo se ha puesto! Así que la ganancia de separar las expresiones en dependientes e independientes es mínima y la pena es que se ha introducido la clausura dinámica por la puerta de atrás. La clausura dinámica es recordada amargamente por los programadores de LISP ya que hizo perder veinte años de investigación probando cosas como las FEXPR que al final tuvieron que ser descartadas.

In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained (John McCarthy, History of Lisp)

Si se hubiera usado la clausura léxica, estos problemas no habrían surgido ya que se habría seguido la idea de sustitución (de hecho, esa fue la razón por la que se inventó la clausura léxica) y los costes habrían sido prácticamente los mismos que los que pagamos ahora.



El problema es que ahora estamos atados. De eso hablaré en otra entrada.