martes, 12 de febrero de 2013

miniSL parte 19 - Lectura de cadenas

Continuamos con la implementación de un mini lenguaje de script. En esta entrada vamos a hablar de la función que lee cadenas. Hemos mezclado en una misma función la lectura de cadenas y la creación de nombres.

Esta función es de las más complejas ya que tenemos que tratar con el escape de símbolos, incluyendo símbolos hexadecimales.

Empecemos por el principio y continuemos poco a poco.

La función devolverá una celda. Debido a que, según sea un nombre o no, la celda será STRING_LIT o NAME_CODE y no lo sabríamos por adelantado; hemos de añadir un flag create_name que indique a la función si quiere una cosa u otra.

CELL& Script::ReadString(ISTREAM& i, bool create_name)
{

Lo primero es quitar las dobles comillas con las que empieza la cadena.

i.get();

Y vamos a ir leyendo mientras no encontremos el cierre de las comillas o haya habido un error. Usaremos la varible s para ir guardando lo que vayamos leyendo.

STRING s;
while(i.peek()!='"' && i.good())
{

Aquí empiezan las complicaciones, si encontramos una barra de escape, debemos leer el siguiente carácter y actuar en consecuencia.

if(i.peek()=='\\')
{
i.get();
switch(i.get())
{

Los primeros casos son los códigos de control que se traducen directamente al C/C++. Para los curiosos, los códigos de control se listan en esta página.

case 'a': s+=L"\a"; break;
case 'b': s+=L"\b"; break;
case 'f': s+=L"\f"; break;
case 'n': s+=L"\n"; break;
case 'r': s+=L"\r"; break;
case 't': s+=L"\t"; break;
case 'v': s+=L"\v"; break;
case '\'': s+=L"'"; break;
case '"': s+=L"\""; break;
case '\\': s+=L"\\"; break;

En nuestro lenguaje vamos a variar algunas cosas. Por ejemplo, no usamos la comilla simple, pero sí quiero escapar la interrogación.

case '?': s+=L"?"; break;

Si empieza por una equis, entramos en la descripción hexadecimal del carácter escapado. Vamos a ir leyendo dígitos hexadecimales y guardarlos en la variable x.

case 'x':
{
STRING x;
while(unsigned(i.peek())<256 && isxdigit(i.peek()) && i.good())
x.push_back(i.get());
if(x.empty()) throw L"Expecting a hexadecimal digit after \\x";

Usamos la función wcstoul para convertir lo leído en un número hexadecimal. Sólo vamos a permitir hasta el primer plano del UNICODE.

int n=wcstoul(x.c_str(), NULL, 16);
if(n>0xFFFF) throw L"Invalid hexadecimal character";

Metemos el carácter en la cadena que estamos construyendo y comprobamos que le sigue un punto y coma. Tampoco es usual tener esto en C, pero quita ambigüedades y añade robustez.

s.push_back(wchar_t(n));

if(i.get()!=';')
throw L"Expecting semicolon after hex escape sequence";
}
break; 

En otro caso, no conocemos la secuencia de escape.

default: throw L"Unknown escape sequence";
}
}

Si no era una secuencia de escape, lo introduce directamente en la cadena. Esto puede ser problemático porque copia directamente cualquier cosa, incluso las que no se ven, del código fuente a la cadena; pero como es un mini lenguaje, vamos a asumirlo.

else
s+=i.get();
}

Finalmente, comprobamos algunas cosas como que terminemos en unas comillas o que no haya habido algún error.

if(i.bad())   throw L"Error while reading a string";
if(i.get()!='"') throw L"Unexpected end of file inside a string";

A la hora de retornar la celda, según sea el flag pasado, creamos una cadena o un nombre. Realmente, ahora me doy cuenta que es un error haberlo hecho así y es mejor usar composición de funciones. Para la siguiente versión.

return create_name ? CreateName(s) : CreateString(s);
}

La siguiente parte de esta serie se va a dedicar a leer nombres y símbolos.

sábado, 2 de febrero de 2013

Coma serial, agujeros de gusano, gotos desnudos, e implícitos por tipo

Funciones

Llamemos a una función. Una función que está en un lugar distante del código.
Si sigo el flujo de control (dibujado en rojo abajo) y el flujo de datos (en azul), ambos van paralelos. Es decir, el valor de a (dato) se lleva a la función doble (control) y se trae de vuelta el resultado (dato) al retornar (control).
La variable a es local. Eso quiere decir que fuera de mi trocito de código no se ve. Por eso necesitamos pasar la variable a a la función doble. ¿Qué pasaría si a fuera global y sí se viese en todo el programa incluida la función doble?

Variables globales

En este caso, no hace falta pasar la variable global a ninguna función, puesto que ya se ve desde allí.
Ahora, una vez guardado el dato 3 en la variable global a, está disponible en cualquier punto del programa. No hace falta pasarlo como argumento a la función doble. El flujo de datos a través de la variable global a se ha ocultado.

Ahora bien, ¿qué ocurre si otro trozo de código ejecuta doble en vez del que estoy usando como ejemplo?
Primero, el flujo de control llegará y asignará el dato 3 a la variable global a. Luego, el programa seguirá funcionando. Algún tiempo o mucho tiempo después, el flujo de control llegará al trozo de código en el que se ejecuta doble y se recupera el valor de la variable global a.

La variable global ha hecho que el dato 3 se pase de una punta a la otra del programa sin que haya relación directa entre esos dos trozos de código. Si no vemos la definición de doble, el uso de la variable global a dentro de doble no es tan obvio. No aparece ni en sus parámetros ni en sus argumentos. El efecto es el de un dato que se teleporta de un lugar a otro del programa.

Beam me up, Scotty!


Entra en un lugar del universo y sale por otro completamente distinto. Como los agujeros de gusano, pero mucho peor ya que puede haber más de dos extremos en una variable global.

Que alguien busque un error en un programa lleno de variables globales con datos que se teleportan de un lado a otro sin relación directa es muy, muy difícil.

Conclusión lógica: mejor evitar el uso de variables globales porque separan el flujo de datos del flujo de control.

Se considera al goto dañino

Hay ríos de tinta (y de bits) explicando que la instrucción goto debe ser evitada a toda costa y, además, su uso es síntoma de mal código. Muchas veces se toma demasiado al pie de la letra el título del artículo de Dijkstra que puso este problema sobre la mesa, pero sin terminar de leer el artículo por completo y viendo el porqué de la mala fama del goto.

Realmente no siempre el goto es malo. Veamos la razón. El goto es el caso complementario a una variable global. En la variable global era el flujo de datos el que saltaba de una punta a otra del código, con el goto es el flujo de control el que salta.
Como goto no permite pasar datos al lugar donde salta, el flujo de datos se acaba en el goto y empieza en el lugar donde llega. Este lugar es llamado la etiqueta. Llamaremos a este tipo de goto un goto desnudo.

¿Y si quiero pasar datos desde un goto desnudo hasta su etiqueta? Muy sencillo: debemos usar las variables globales.
Es más, si usamos gotos desnudos, no nos queda otra opción que usar variables globales. Las variables globales implican saltos en el flujo de datos: lo que entra en una variable global puede aparecer en la otra punta del código. Además, los gotos implican saltos en el flujo de control: la etiqueta de destino de un goto puede estar en la otra punta del código. Las dos cosas juntas hacen que la comprensión de un programa no trivial sea imposible.

Conclusión: los gotos desnudos son malos porque nos fuerzan a usar variables globales. Realmente, la raíz de todo mal está en las variables globales ya que los gotos pueden modificarse para que no sea necesario el uso de estas variables.

Restricción de saltos

¿Cómo podemos restringir el uso de los goto para que sea seguro? La primera lección la da el lenguaje C: un goto sólo puede saltar a una etiqueta que esté en su misma función.

void g(void)
{
y:
  puts(“ups!”);
}

void f(void)
{
  int a;
x:
  a=rand();
  if(a==0) goto x;  //OK: x está en f
  else     goto y;  //ERROR: y está en otra función
  printf(“%d\n”,a);
}

De esta forma antes y después del goto están visibles las variables locales de la función. No hace falta usar variables globales ya que la comunicación se realiza mediante variables locales.

Otra lección proviene de la teoría de lenguajes y consiste en añadir al goto un parámetro. Llamaremos a este goto vestido.

goto x(3);

Y en la etiqueta recogemos el argumento.

x(a):
print(a);

La etiqueta se comporta en cierta manera como una función que nunca retorna. Esto se acerca al concepto de continuación. También, con las continuaciones, pasamos los datos como si fuera una función y no necesitamos variables globales.

Evitamos la raíz de todo mal: las variables globales y sus agujeros de gusano.

Nota: Una continuación es un valor de forma similar a lo que las clausuras son a las funciones, por lo que el goto vestido no es exactamente una continuación.

Implícitos

Sin embargo, no tener variables globales es tedioso a la hora de escribir un programa porque hay que ir arrastrando el contexto que antes mantenía la variable global.

Propongamos este simple ejemplo:

Dato d; //Mi dato d que voy a usar como variable global

void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b)
{
  //Esta función hace otras cosas con a y b pero, al final usa h
  h(d)
}
void f(AlgunasCosas x, OtrasCosas y)
{
  //Esta función hace cosas con x e y, pero al final llama a g
  g(a,b)
}
int main()
{
  //Prepara x e y
  //Preparo mi dato d
  f(x,y)
}

La función h usa d. Por ese motivo se dice que d es contexto de h. Como d es global no tenemos problemas en escribirla en cualquier parte del código, incluida h. ¿Qué pasaría si d no pudiera ser global? Tendríamos que ponerla en main(), pasársela a f y propagarla hasta llegar a h. Es decir, tenemos que escribir el contexto en los parámetros de las funciones que lo usan.

Esto es justamente lo que deseamos hacer: que el flujo de datos y de control vayan paralelos.

void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, Dato d)
{
  //Esta función hace otras cosas con a y b pero, al final usa h
  h(d)
}
void f(AlgunasCosas x, OtrasCosas y, Dato d)
{
  //Esta función hace cosas con x e y, pero al final llama a g
  g(a,b,d)
}
int main()
{
  //Prepara x e y
  Dato d; //Mi dato d que voy a usar como variable local
  //Preparo mi dato d
  f(x,y,d)
}

En las funciones f y g hemos tenido que añadir el dato para transmitirlo hasta la función h. Cada vez que usemos f o g, hemos de añadir d ¡y eso pueden ser muchas, muchas veces! ¿Cómo solucionarlo sin variables globales?

La mejor forma que he visto es mediante argumentos implícitos. Una característica del lenguaje de programación Scala. Consiste en añadir la palabra clave implicit en los parámetros que se comportan como propagadores de contexto.

void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, implicit Dato d)
{
  //Esta función hace otras cosas con a y b pero, al final usa h
  h(d)
}
void f(AlgunasCosas x, OtrasCosas y, implicit Dato d)
{
  //Esta función hace cosas con x e y, pero al final llama a g
  g(a,b,d)
}
int main()
{
  //Prepara x e y
  Dato d; //Mi dato d que voy a usar como variable local
  //Preparo mi dato d
  f(x,y,d)
}

Hasta ahora nada cambia, pero declarar un parámetro como implícito significa que es opcional y, si no se pone, se busca el llamado valor implícito de ese tipo de datos en el entorno actual. La forma de declarar un valor implícito es también con la palabra clave implicit.

void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, implicit Dato d)
{
  //Esta función hace otras cosas con a y b pero, al final usa h
  h(d)
}
void f(AlgunasCosas x, OtrasCosas y, implicit Dato d)
{
  //Esta función hace cosas con x e y, pero al final llama a g
  g(a,b,d)
}
int main()
{
  //Prepara x e y
  Dato d; //Mi dato d que voy a usar como variable local
  //Preparo mi dato d
  implicit d; //Usa d como el valor implícito para Dato
  f(x,y) //El implícito para el tipo Dato es d.
         //Entonces, es como llamar a f(x,y,d)
}

Nota: ¿Por qué Scala asocia un valor implícito al tipo Dato y no, por ejemplo, a cada nombre de manera que si no escribo el argumento implícito busque la variable con nombre “d”? ¿No es muy rebuscado buscar el valor implícito según sea el tipo del parámetro? La respuesta es bastante teórica. Este mecanismo introduce una dependencia de valores desde los tipos y esto es muy útil para otras muchas cosas como los conceptos (también llamados clases de tipos).

Lo interesante es que un parámetro implícito es directamente el valor implícito en el entorno de la función, por lo que tampoco hace falta escribir g(a,b,d).

void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, implicit Dato d)
{
  //Esta función hace otras cosas con a y b pero, al final usa h
  h(d)
}
void f(AlgunasCosas x, OtrasCosas y, implicit Dato d)
{
  //Esta función hace cosas con x e y, pero al final llama a g
  g(a,b) //d es implícito aquí también
}
int main()
{
  //Prepara x e y
  Dato d; //Mi dato d que voy a usar como variable local
  //Preparo mi dato d
  implicit d; //Usa d como un implícito para Dato
  f(x,y) //El implícito para el tipo Dato es d.
         //Entonces, es como llamar a f(x,y,d)
}

Por supuesto, en este ejemplo sólo nos hemos ahorrado escribir d dos veces, pero en un programa real suele haber muchos más usos de este tipo de parámetros. Así que con estos parámetros implícitos se soslaya el inconveniente de no poder usar variables globales.

La coma serial

Una bagatela para finalizar. El título de esta entrada se llama "Coma serial, agujeros de gusano, gotos desnudos, e implícitos por tipo". Un lector atento habrá visto una escritura inusual de la enumeración. Concretamente usando la coma antes de la conjunción.

Este tipo de uso de la coma no es común en el español, pero en inglés sí que lo es. Se denomina la coma de Oxford, la coma de Harvard o la coma serial. Se usa para evitar ambigüedades como estas:

"Dedicado a mis padres, Juan y Ana." Bien. Los padres son Juan y Ana.
"Dedicado a mis padres, Juan, y Ana." Mmmm.... Los padres no son Juan y Ana. ¿Verdad?

En el caso del título podía confundirse "e implícitos por tipo " como si los goto fueran, además de desnudos, implícitos por tipo. No es el caso. Los implícitos por tipo son otra cosa. Para evitar la ambigüedad, usé la coma serial.