lunes, 20 de diciembre de 2010

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.

3 comentarios:

kenkeiras dijo...

Así que para esto mejor punteros que strings y arboles que hashes?

Está muy interesante todo el proceso del intérprete, siempre aparecen cosas que no se me habian ocurrido :D

Gadelan dijo...

Es mejor usar cadenas únicas (internas) de forma que la comparación de cadenas se reduce a una comparación entre punteros. Casi todos los lenguajes script de los que he leído el código fuente de sus intérpretes usan esto (LISP, Scheme, Ruby...)

No es mejor usar árboles que tablas hash en general. En este caso, el miniSL, como quiero que todo me quepa en unas 1000 líneas de código, saco ventaja de que el árbol no mueve los nodos (sólo modifica los punteros de enlace entre ellos) para la gestión de memoria. Casi todos los lenguajes que conozco usan tablas hash para tablas de símbolos y luego tienen algún otro sistema de gestión de memoria.

Nota: Esta gestión de memoria es de las cadenas, no de las celdas que, como veremos en la próxima entrada dedicada al miniSL se basa en recolección de basura. (Ya acabo la autopublicidad :-)

kenkeiras dijo...

Comprendo, gracias por la explicación :D

Publicar un comentario en la entrada