sábado, 13 de diciembre de 2014

miniSL parte 24 - Expresiones infijas

Seguimos estudiando el analizador sintáctico de miniSL. Hemos empezado con las expresiones de mayor precedencia. Primarias en la parte 22. Postfijas en la 23. Prefijas también en la 23. Ahora vamos a ver las infijas.

Si bien hasta ahora cada tipo de expresión tenía una única precedencia, con las infijas esto no es así. Una expresión infija puede tener una precedencia distinta a la de otra expresión infija. La precedencia de cada expresión infija viene dada por los operadores que la componen. De hecho, hemos visto ya el algoritmo para analizar las expresiones infijas en este blog. Es el algoritmo de playa de agujas.

En miniSL la función que implementa este algoritmo es ReadInfixExpression(). En esta versión del algoritmo usamos la recursividad. No es la versión más eficiente, pero sí es la más sencilla de entender. La idea es mantener siempre la precedencia de la expresión que estamos analizando. Si el siguiente operador es de menor precedencia, no lo analizamos y dejamos que sea la función que nos ha llamado la que se encargue. Obviamente, la primera llamada deberá ser con la precedencia más baja posible.

CELL& Script::ReadInfixExpression(ISTREAM& i, int precedence)
{

En la variable a vamos a mantener la expresión analizada hasta ahora que tendrá la precedencia dada en precedence o una mayor. Empezamos con una expresión prefija que es justo la de mayor precedencia tras las infijas, por lo que aseguramos esta condición.

CELL* a=&ReadPrefixExpression(i);

Ahora vemos que el siguiente token de la entrada sea un operador. Es decir, un T_SYMBOL. Si no es un operador, el análisis de la expresión no puede continuar y finalizamos. En este bucle continuaremos mientras vayamos encontrando operadores. También debemos tener en cuenta que si lo que nos encontramos no es un operador, no debemos consumir ese token ya que otra función podría necesitarlo para continuar el análisis léxico. Por eso usamos peek().

TOKEN t;
while((t=PeekToken(i)).type==T_SYMBOL)
{

En este punto sabemos que estamos tratando con un operador. Obtengamos qué operador es, qué precedencia tiene y qué asociatividad.

STRING const& s=*t.data->string_val;
int prec=SymbolPrecedenceAndAssoc(s);
bool right_assoc=(prec&1)!=0;

Ahora viene la decisión comentada anteriormente y núcleo del algoritmo. Si la precedencia del operador es menor que la de la expresión actual (precedencia que tenemos almacenada en el parámetro precedence), retornamos lo que hayamos analizado hasta ahora y la función que nos ha llamado deberá hacerse cargo de ese operador con una precedencia tan baja. En el caso de que el operador sea exactamente de la misma precedencia que la expresión que estoy analizando, deberemos decidir si lo aglutinamos en esta expresión (por lo que continuamos el algoritmo aquí) o en la expresión superior (por lo que retornamos a la función llamante). Esto depende de la asociatividad del operador como veremos algo más abajo.

if(right_assoc ? prec<precedence : prec<=precedence)
return *a;

Una vez que hemos decidido que debemos procesar este operador, lo consumimos de la entrada.

ReadToken(i);

A continuación leemos el resto de la expresión con precedencia mayor (o igual en el caso de asociatividad por la derecha) que el operador recién leído. Cuando se encuentre con una precedencia menor, volverá a esta función y seguiremos comparando con la precedencia de precedence.

CELL& b=ReadInfixExpression(i, prec);

Llegados a este punto, tenemos dos expresiones y un operador. Construimos las celdas correspondientes. La celda a se aglutina por la izquierda y la celda b por la derecha. El resultado se vuelve a almacenar en a. Esto significa que siempre asociamos por la izquierda en este bucle. Por esto mismo retornábamos en caso de precedencias iguales si queríamos asociar por la derecha.

CELL& operands=CreateCell(CONS_CTOR, a, &CreateCell(CONS_CTOR, &b, &CreateCell(EMPTY_LIT)));
a=&CreateCell(COMBINE_CODE, t.data, &operands );
}

Este retorno es la salida cuando encontramos un token que no es un operador y salíamos del bucle.

return *a;
}

Con esta función completada sólo nos falta implementar la función que lee listas. Esta función ReadList() ha aparecido ya varias veces usada en las expresiones primarias y postfijas. La describiremos en la siguiente parte de esta serie.

domingo, 15 de junio de 2014

miniSL Parte 23 - Expresiones postfijas y prefijas

Esta es otra parte de la serie dedicada al mini-lenguaje MiniSL. Tal como veníamos haciendo en las partes anteriores, vamos a seguir ascendiendo por las reglas de analizador descendente recursivo. La regla que usa las expresiones primarias es la de las expresiones postfijas. Esta regla está implementada por la función ReadPostfixExpression().

CELL& Script::ReadPostfixExpression(ISTREAM& i)
{

Siguiendo nuestra sintaxis, una expresión postfija es una expresión primaria.

 CELL* p=&ReadPrimaryExpression(i);

Seguida de ninguna, una o varias llamadas de función. Estas llamadas deben empezar forzosamente por el carácter “(”. No podemos consumirlo porque si no es una llamada a función, podría ser otra cosa importante como un operador infijo. Así que sólo ojeamos el siguiente token con PeekToken(). Este procedimiento de mirar por adelantado es muy usual en el reconocimiento sintáctico y se denomina lookahead (mira hacia delante). Se detalló el funcionamiento de PeekToken() en la parte 17 de esta serie.

 TOKEN t=PeekToken(i);
 while(t.type==T_RAW && t.raw=='(')
 {

Una vez que estamos seguros de que lo que tenemos es una llamada a función, la consumimos. Primero el paréntesis de apertura. Luego leemos la lista de argumentos en una celda especial de combinación (como se explicó en la parte sexta de esta serie). Finalmente, consumimos el paréntesis de cierre.

  t=ReadToken(i);
  p=&CreateCell(COMBINE_CODE, p, &ReadList(i, ',', ')'));
  t=PeekToken(i);
 }

 return *p;
}

Lo que generamos es un árbol en el cual cada nodo es una celda de combinación (COMBINE_CODE) que representa una llamada a función y en sus argumentos añadimos una lista. Veremos las listas en la sección 25, pero ya sabemos que las listas se construyen con celdas del tipo CONS_CTOR y EMPTY_LIT.


Para la función ReadPrefixExpression(), lo que haremos será lo siguiente.

CELL& Script::ReadPrefixExpression(ISTREAM& i)
{
 if(PeekToken(i).type==T_SYMBOL)
 {

Si encontramos un símbolo, lo consumimos y llamamos recursivamente a esta función para el argumento de la función prefija.
  TOKEN t=ReadToken(i);
  CELL& expr=ReadPrefixExpression(i);

El resultado lo guardamos como un único argumento (una única celda CONS_CTOR) en una llamada (celda COMBINE_CODE).

  return CreateCell(COMBINE_CODE, t.data, &CreateCell(CONS_CTOR, &expr, &CreateCell(EMPTY_LIT)));
 }

Si no empezábamos por un símbolo es que hemos llegado a la expresión postfija.

 return ReadPostfixExpression(i);
}

Estas funciones son simples y lo único que hacen es seguir la gramática. De hecho, estas funciones son la parte más representativa de lo que es un reconocedor sintáctico descendiente recursivo. En la siguiente parte veremos algo un poco distinto y usaremos el algoritmo de playa de agujas para leer expresiones infijas.

domingo, 2 de febrero de 2014

miniSL parte 22 - Expresiones primarias

En esta entrada de la serie dedicada al mini-lenguaje de programación MiniSL vamos a ver las expresiones primarias. Las expresiones primarias son las expresiones que no están formadas por otras expresiones o no hay ambigüedad en su análisis porque están parentizadas. En el caso de MiniSL eso incluye los siguientes casos:
  • Una expresión entre paréntesis.
  • Una lista entre corchetes. 
  • Un nombre.
  • Un literal (cadena o entero).
La función que lee una expresión primaria es ReadPrimaryExpression(). Lo primero que hace esta función es leer el siguiente token y, según sea su tipo, procede de una forma u otra.

CELL& Script::ReadPrimaryExpression(ISTREAM& i)
{
 TOKEN t=ReadToken(i);
 switch(t.type)
 {

Los tokens T_RAW consistían en un único carácter. Este carácter podrá ser o bien un paréntesis de apertura “(” o un corchete de apertura “[”. En el primer caso estamos en una expresión entre paréntesis y en el segundo caso una lista. Como vemos, no hay ambigüedad posible.

 case T_RAW:
  switch(t.raw)
  {

En el caso de expresión entre paréntesis, leemos la expresión. Comprobamos que el paréntesis se cierra usando ConsumeRawToken() que ya vimos en las funciones de ayuda. Finalmente, retornamos la celda leída en la expresión interna como la correspondiente a la parentización.

  case '(':
   {
    CELL& x=ReadExpression(i);
    ConsumeRawToken(i, ')', L"Expecting closing round bracket");
    return x;
   }

En el caso de una lista, usamos la función ReadList() indicando que la lista se separa por comas y termina en corchete “]”. Veremos la función ReadList() en la parte 25 de esta serie.

  case '[': return ReadList(i, ',', ']');
  default: throw L"Unexpected token";
  }

Tanto en el caso de nombres como de literales es muy fácil devolver la celda ya que el token la generaba y guardaba.

 case T_NAME: return *t.data;
 case T_LITERAL: return *t.data;
 default:  throw L"Expecting a primary expression";
 }
}

Como observamos, lo hecho no es más que una regla de un reconocedor descendente recursivo. En la siguiente parte de esta serie nos dedicaremos a las expresiones postfijas y prefijas.

miércoles, 18 de diciembre de 2013

La historia de Mel

Una historia clásica de un pasado mejor. Nada mejor para estas fiestas navideñas. Citado de aquí.


Fuente: utastro!nather (Ed Nather), 21 de Mayo de 1983.



La historia de Mel


En un artículo reciente, hablando del lado macho de la programación, se hizo la simple y llana afirmación:

Los Verdaderos Programadores escriben en FORTRAN

Quizá lo hagan ahora, en esta era decadente de cerveza sin alcohol, calculadoras de bolsillo y programas "user-friendly" pero en los Viejos Buenos Tiempos, cuando el término "software" sonaba a broma y los Verdaderos Ordenadores estaban hechos de tambores y tubos de vacío los Verdaderos Programadores escribían en código máquina. No FORTRAN. No RATFOR. Ni siquiera ensamblador. Código máquina. Crudos, sin adornos, inescrutables números hexadecimales. Directamente

Toda una nueva generación de programadores creció en la ignorancia de este glorioso pasado, por lo que me siento obligado a describir, tan bien como me sea posible debido al salto generacional, cómo un Verdadero Programador escribía código.

Le llamaré Mel, porque ese era su nombre.


Conocí a Mel cuando empecé a trabajar para Royal McBee Computer Corp., una extinta subsidiaria de una compañía de maquinas de escribir. La empresa producía el LGP-30, un pequeño y barato (para los estándares de la época) ordenador con memoria de tambor, y empezaba a producir el RPC-4000, un ordenador con memoria de tambor mejorado, más grande y más rápido. Estos ordenadores costaban demasiado, y tampoco duraron mucho de todas formas (es por esto que no habéis oído hablar de la compañía ni del ordenador)


 Había sido contratado para escribir un compilador de FORTRAN para esta nuevo portento y Mel fue mi guía a sus maravillas. Mel no soportaba a los compiladores.

– ¿Si un programa no puede rescribir su propio código — preguntó — qué tiene de bueno?

Mel había escrito, en hexadecimal, el programa de ordenador más conocido que la compañía poseía. Corría sobre el LGP-30 y jugaba al blackjack con los compradores potenciales en las exposiciones de ordenadores. Su efecto era increíble. El stand del LGP-30 estaba siempre lleno en cada exposición, y los vendedores de IBM estaban allí de pie sin poder hacer otra cosa que hablar entre ellos. Si aquello servía para vender ordenadores o no era una pregunta que nadie se planteó nunca.

El trabajo de Mel era reescribir el programa de blackjack para el RPC-4000 (¿Portable? ¿Qué significa eso?). El nuevo ordenador tenia un sistema de direccionamiento de uno más uno, en donde cada instrucción máquina, aparte del código de operación y de la dirección del operando utilizado, tenía una segunda dirección que indicaba donde estaba la próxima instrucción en el tambor giratorio.
¡Una forma moderna de contarlo sería que cada instrucción estaba seguida de un GOTO! Pon eso en la pipa de Pascal y fúmatelo.

Mel amaba al RPC-4000 porque podría optimizar su código: es decir, localizar las instrucciones en el tambor de modo que cuando una hubiera terminado su trabajo, la próxima estuviera pasando por debajo de la cabeza lectora y, por lo tanto, estuviera disponible para su inmediata ejecución. Había un programa que se usaba para hacer eso, un "optimizador de código de ensamblador", pero Mel se oponía a usarlo.

– Nunca sabes donde va a poner las cosas — explicaba — por lo que deberías utilizar constantes separadas.

Tardé un buen tiempo antes de poder entender esa extraña frase. Como Mel conocía el valor numérico de cada código de operación, y había asignado sus propias direcciones en el tambor, cada instrucción que escribía podía también ser considerada como una constante numérica. Podía tomar una instrucción "add" anterior, por ejemplo, y multiplicar algo con ella, si tenía el valor numérico que necesitaba. Su código no era muy sencillo de modificar por otra persona que digamos.

Comparé los programas optimizados a mano de Mel con el mismo código pasado por el programa de optimización de código de ensamblador, y los de Mel siempre se ejecutaban más rápido. Esto era debido a que el sistema de programación "top-down" no había sido inventado aún, y Mel no lo habría utilizado de todas formas. Escribía las partes más internas de los bucles de su programa primero, para que se pudieran situar en las direcciones optimas del tambor. El optimizador de código ensamblador simplemente no era lo suficientemente listo para hacerlo de ese modo.

Mel nunca escribía bucles de espera, a pesar de que la Flexowriter requería un tiempo de espera entre los caracteres de salida para funcionar correctamente. Simplemente situaba las instrucciones en el tambor de forma que cada una ya hubiera pasado por debajo de cabeza cuando se necesitaba; de forma que el tambor debía realizar otra revolución completa para encontrar la instrucción que acababa de pasar. Acuñó un término inolvidable para este proceso. A pesar de que "óptimo" es un término absoluto, como "único", se convirtió en una costumbre hacerlo relativo: "no del todo óptimo" o "menos óptimo" o "o no muy óptimo". Mel llamaba a las localizaciones con mayor tiempo de espera las "más pésimas".

Después de terminar el programa de blackjack y conseguirlo ejecutar ("Incluso el inicializador está optimizado" dijo orgullosamente), recibió una Petición de Modificación desde el departamento de ventas. El programa utilizaba un elegante (y optimizado) generador de números aleatorios para barajar las "cartas" y repartirlas desde el "montón", y algunos de los vendedores creían que esto era demasiado justo, porque a veces los compradores perdían. Querían que Mel modificara el programa para que, cuando se cambiara un interruptor en el panel, pudieran cambiar la suerte y dejar al comprador ganar.

Mel protestó. Creía que la proposición era sencillamente deshonesta, que lo era, y que chocaba con su integridad personal como programador, lo que pasaba de veras, por lo que se negó a hacerlo. El Director de Ventas habló con Mel, igual que lo hizo el Gran Jefe, y, a petición del jefe, unos cuantos Compañeros Programadores. Mel finalmente se rindió y escribió el código, pero hizo la comprobación al revés, y, cuando el interruptor se pulsaba, el programa hacia trampas, ganando todo el rato. Mel estaba encantado con ello, proclamando que su subconsciente era incontrolablemente ético, y se negó estoicamente a arreglarlo

Después de que Mel dejara la compañía en busca de pa$to$ más verdes, el Gran Jefe me preguntó si podía mirar el código y ver si podía encontrar la comprobación y darle la vuelta. Un poco reticente acepté mirar. Seguir el código de Mel era una verdadera odisea.

A veces creo que programar es un arte, y su valor solo puede ser apreciado por otra persona versada en ese arcano arte; existen gemas maravillosas y brillantes ocultas a la vista y admiración humanas, algunas veces para siempre, por la naturaleza misma del proceso. Puedes aprender un montón sobre alguien sólo leyendo su código, incluso en hexadecimal. Mel era, creo, un genio incomprendido.

Quizá mi mayor conmoción fue cuando encontré un inocente bucle que no contenía ninguna condición. Nada. El sentido común me decía que tenía que ser un bucle cerrado, donde el programa se ejecutaría para siempre, sin fin. Sin embargo el control del programa pasaba a través de él hasta el otro extremo sin problemas. Me llevó dos semanas descubrir lo que sucedía.

El RPC-4000 tenía un dispositivo realmente moderno llamado registro índice. Permitía al programador escribir un bucle que utilizara una instrucción indexada en su interior; cada vez que se pasaba por ese punto el valor en el registro índice era añadido a la dirección del operando de aquella instrucción, por lo que se referiría al próximo dato de una serie. Sólo tenía que incrementar el registro índice cada vez. Mel nunca lo utilizó

En su lugar, él ponía la instrucción en un registro de la máquina, añadia uno a su dirección y la almacenaba de nuevo. Entonces ejecutaba la instrucción modificada, directamente desde el registro. El bucle estaba escrito de forma que este tiempo adicional de ejecución se tenía en cuenta, cuando la instrucción en curso terminaba la próxima estaba justo bajo la cabeza de lectura del tambor, lista para ser ejecutada. Pero el bucle no tenía comprobación.

La pista vital llegó cuando me di cuenta que el bit del registro índice, el bit que estaba entre la dirección y el código de operación en la palabra de la instrucción estaba activo… a pesar de que Mel nunca utilizaba el registro índice, dejándolo a cero todo el tiempo. Cuando la luz brilló, casi me cegó.

Mel había situado los datos en los que trabajaba cerca de la parte alta de la memoria, las direcciones más grandes que las instrucciones podían direccionar por lo que, después de que el último dato hubiera sido utilizado, incrementar la dirección de la instrucción haría que se desbordara. El acarreo añadiría uno al código de operación, cambiándolo a la siguiente instrucción en el juego: una instrucción de salto. Además la próxima instrucción de programa estaba en la dirección cero, y el programa seguiría felizmente su recorrido

No me he mantenido en contacto con Mel, por lo que no se si se rindió a los cambios que los tiempos han introducido en las técnicas de programación desde esos días desaparecidos hace mucho tiempo. Me gusta pensar que no lo hizo. De todas maneras me impresionó tanto aquello que dejé de buscar la comprobación, diciéndole al Gran Jefe que no podía encontrarla. No pareció sorprendido.

Cuando dejé la compañía el programa de blackjack seguía haciendo trampas si activabas el interruptor, y creo que es como debe ser. No me siento a gusto hackeado el código de un Verdadero Programador

Mel está de pie a la derecha

lunes, 21 de octubre de 2013

Magia circular

Los números complejos siempre me han parecido maravillosos. Descubro nuevas propiedades una y otra vez. La que traigo hoy es simple y misteriosa.

Supongamos que tengo una circunferencia [$C$] formada por los elementos [$z\in C$]. Entonces si hago la inversa de sus elementos, el conjunto que obtengo [$C'=\{1/z\mid z\in C\}$] es también una circunferencia.

La demostración se me ha resistido un poco, pero una vez descubierta, es hasta sencilla. Sea [$c$] el centro del círculo y [$R\ge 0$] su radio.[$$|z-c|=R$$][$$|z-c|^2=R^2$$] [$$(z-c)(z-c)^*=R^2$$][$$zz^*-cz^*-c^*z+cc^*=R^2$$]Ahora hago [$w=1/z$] por lo que llego a [$$\frac{1}{w} \frac{1}{w^*}-c \frac{1}{w^*} -c^* \frac{1}{w} +cc^*=R^2$$] Si asumo que [$w\ne 0$], es decir, [$z<\infty$], llego a [$$1-c w -c^*w^* +cc^*ww^*=R^2ww^*$$]Reordenando un poco [$$1-c w -c^*w^* +(cc^*- R^2 )ww^*=0$$] Y si asumo que [$cc^*\ne R^2$] (es decir [$|c|\ne R$]) llego hasta [$$ww^*-\frac{c w}{cc^*- R^2}-\frac{c^*w^*}{ (cc^*- R^2)^2 } + \frac{1}{ cc^*- R^2 } =0$$] [$$\left(w-\frac{c^*}{cc^*- R^2}\right) \left(w-\frac{c^*}{cc^*- R^2}\right)^*-\frac{cc^*}{ (cc^*- R^2)^2 } + \frac{1}{ cc^*- R^2 } =0$$]  [$$\left(w-\frac{c^*}{cc^*- R^2}\right) \left(w-\frac{c^*}{cc^*- R^2}\right)^* = \frac{R^2}{(cc^*- R^2)^2 }$$] ¡Y ya lo tenemos! [$$\left|w-\frac{c^*}{cc^*- R^2}\right|^2  = \frac{R^2}{ (cc^*- R^2)^2 }$$]  [$$\left|w-\frac{c^*}{cc^*- R^2}\right|  = \frac{R}{ cc^*- R^2 }$$]
La nueva circunferencia tiene de centro [$ \frac{c^*}{cc^*- R^2}$] y de radio [$ \frac{R}{ cc^*- R^2 } $].

Para los curiosos, las hipótesis de que [$z<\infty$] y que [$|c|\ne R$] aparecen porque estamos restringiéndonos a circunferencias. Si no las tomamos, llegamos a que circunferencias o rectas se transforman en circunferencias o rectas. Las rectas pueden ser vistas comocircunferencias con el centro en el infinito y por tanto se dice que transformamos circunferencias generalizadas en circunferencias generalizadas.

La mejor forma de ver esto es mediante la esfera de Riemann, pero ya lo dejamos para otro día.

sábado, 24 de agosto de 2013

¿Qué es eso de la programación asíncrona?

Llamadas síncronas

Gran parte del tiempo de las operaciones que realiza un programa en su ejecución se pierde esperando. Esperando que los datos lleguen del disco. Esperando que el usuario pulse una tecla. Esperando que el paquete se mande por red. Esperando, esperando y esperando.

La solución clásica a este problema es proporcionarle ese tiempo de espera a otro proceso de manera que se aproveche el uso de CPU. Nuestro proceso se bloquea mientras espera (y si va a esperar mucho incluso se quita de memoria y guarda en disco) y otro toma su lugar. Cuando llega la señal de que la espera ha terminado (y se queda la CPU libre) nuestro proceso se reanuda.

Existen diversas políticas de reparto del tiempo de CPU entre los distintos procesos para que este reparto sea lo más útil posible. Por ejemplo, primando al proceso con el que el usuario está trabajando.

Ahora bien. Desde el punto de vista del programa, ¿qué significa este sistema? Significa que cuando la llamada a una función que realiza una operación termina, la operación se ha completado y que, implícitamente, nuestro programa ha estado esperado a que terminase.

Debido a que la terminación de la operación y la reanudación del programa ocurren a la vez, se dice que estamos realizando llamadas síncronas.

f=leer_fichero()
//Hasta que no se lee el fichero no llegamos aquí
t=leer_teclado()
//Hasta que no se lee el teclado no llegamos aquí
buscar(f,t)
//Resto del programa

Llamadas asíncronas

La alternativa es no esperar, ser asíncronos. Debido a que no esperamos ocurren dos cosas:
  1. No bloqueamos la ejecución de nuestro programa. Por esta razón a las llamadas asíncronas también se les dice no bloqueantes y a las síncronas, bloqueantes.
  2. La llamada retorna antes de que se complete la operación y, por tanto, no puede devolver el resultado.
Bien. El punto 1 era lo requerido, ¿pero cómo solucionamos el punto 2? Existen varias opciones.
  • Pipes: conectar de alguna manera la operación con otra antes de solicitar su realización.
  • Polling: preguntar cada cierto tiempo a ver si se ha completado la operación. No suele ser buena idea ya que perdemos tiempo en preguntar.
  • Interrupción: esperar a una señal y que nuestro programa o el sistema ejecute, en el momento que se recibe la señal, un código en respuesta a la misma. Es importante ver aquí que este código está desligado del punto en el que se solicitó la operación mediante la llamada asíncrona.
  • Eventos/mensajes: es una mejora sobre polling. Cuando termina la operación se envía un mensaje que se encola. El programa no pregunta si una operación en concreto se ha completado. Sólo comprueba si ha llegado algún mensaje. Esto le indica que una operación de las muchas en curso se ha completado. Cada mensaje tiene un indicador de la operación completada y deberá ser respondido correspondientemente, de forma similar a como se hacía con las interrupciones.
  • Hebras o fibras: nos rendimos. Usamos llamadas síncronas, pero en vez de que bloqueen mi programa, doy opciones de por dónde se puede continuar la ejecución. En el caso de las hebras es el sistema operativo el que decide cómo planificar la ejecución, en el caso de la fibra es mi propio programa el que lo hace.
  • Sincronizar (p.ej. por futuros/promesa): nos rendimos definitivamente. Seguimos ejecutando como si nada mientras no necesitemos el resultado. En el momento que necesitemos el resultado, esperamos hasta tenerlo.
  • Retrollamadas: como interrupción, pero indico qué código hay que ejecutar en el momento de realizar la llamada asíncrona. Esto tiene el efecto de bifurcar el flujo de control y analizaremos esto en lo que resta de artículo.
Seguro que hay más métodos para solucionar el punto 2, pero o son menos conocidos o no los recuerdo ahora. Es más, de todos los métodos mencionados arriba los más usados son los cuatro últimos y, aún así, los mensajes empiezan ya a parecer algo antiguo. Destruyen la lógica del programa que se tiene que repartir en trocitos entre los distintos manejadores de eventos. Cualquiera que haya programado en win32 sabrá de lo que hablo.

Por otro lado, tanto sincronizar como las hebras/fibras es rendirse y esperar.


Retrollamadas

Lo que realmente está en auge son las retrollamadas (callbacks), sobre todo desde que C# incluyera soporte en el lenguaje para la programación asíncrona. Pero vayamos por partes. ¿Qué es esto de una retrollamada?

Usaremos el ejemplo de arriba.

f=leer_fichero()
t=leer_teclado()
buscar(f,t)
//Resto del programa

Con retrollamadas, en vez de esperar el resultado de las funciones, indico a estas funciones qué tienen que hacer cuando terminen.

leer_fichero_asincrono(usa_fichero)
leer_teclado_asincrono(usa_teclado)

//Resto del programa

Así, en el caso de leer_fichero_asincrono() lo que hago es decirle que, cuando termine de leer el fichero llame a la función usa_fichero(). Igualmente, con leer_teclado_asincrono(). Estas funciones usa_fichero() y usa_teclado() que se ejecutan cuando se completa la operación son las retrollamadas.

Acabadas las presentaciones, lo importante aquí es que la función  leer_fichero_asincrono() no espera y la ejecución continúa. Se ejecuta leer_teclado_asincrono() y tampoco espera, seguimos ejecutando lo que haya que ejecutar despues y, mientras, se lee del fichero y del teclado a la vez.

¿Y dónde está la función buscar() que es donde realmente hacemos algo con lo leído? Bueno, no podemos llamarla hasta que estemos seguros de que tanto el fichero como el teclado se han leído. Esa es la responsabilidad de usa_fichero() y usa_teclado() que deben guardar los datos, comprobar que están ambos y, si es así, llamar la función buscar() con ellos.

var f, t string;
func usa_fichero(rf) { f = rf; if t!="" {buscar(f,t)} }
func usa_teclado(rt) { t = rt; if f!="" {buscar(f,t)} }

//Resto del programa

Para eso guardamos los datos recibidos en dos variables visibles por ambas retrollamadas y cuando se comprueba que ambas cadenas se han leído, llama a buscar().


Funciones anónimas

El ejemplo anterior es algo engorroso ya que hay que definir una función por cada retrollamada que se quiera usar. Este hecho ha sido determinante para que no se usaran mucho las retrollamadas. Por fortuna, los lenguajes de programación van evolucionando y se han ido adaptando ideas que venían de lenguajes menos conocidos y académicos. Una de esas ideas son las funciones anónimas y sus clausuras léxicas.

Con funciones anónimas el código del ejemplo anterior se reduce lo suficiente como para que sea atractivo su uso.

var f, t string;

leer_fichero_asincrono(rf => { f = rf; if t!="" {buscar(f,t) } )
leer_teclado_asincrono(rt => { t = rt; if f!="" {buscar(f,t) } )

//Resto del programa

Aunque no hemos solucionado el detalle de que la función buscar() aparece escrita dos veces aunque sólo se llamará una. En este ejemplo es una pequeña tontería, pero en ejemplos mayores el grado de verbosidad aumenta y se dificulta el mantenimiento del programa.

Quiero resaltar aquí que una función asíncrona bifurca el flujo de control ya que van a ocurrir dos cosas a la vez: la operación que haga la función (se hará la retrollamada cuando se complete) y el resto del programa (ya que la función retorna inmediatamente). De manera que si escribo algo como esto:

asincrona( x => parte1(x) )
parte2()

La parte 1 y la parte 2 se ejecutan, a la vez o en momentos distintos, pero no en secuencia. Es más, una vez que la parte 1 se haya completado, ese flujo de control bifurcado muere sin hacer nada más. La parte 2 que es el resto del programa seguirá su ejecución hasta que muera cuando el proceso acabe.


Composición de retrollamadas

En el ejemplo anterior se hacían a la vez tres cosas:
  • La lectura del fichero
  • La lectura del teclado
  • La ejecución del resto del programa 
Hemos realizado una composición en paralelo de las operaciones. ¿Qué pasa si por la razón que sea debo leer el teclado después de leer el fichero? El ejemplo cambiaría tal y como sigue:

var f, t string;
leer_fichero_asincrono(f => { leer_teclado_asincrono(t => buscar(f,t)) })

//Resto del programa

En este caso lo que tenemos es una composición en serie (o secuencia) de las operaciones. Se hacen a la vez dos cosas:
  • La lectura del fichero y luego la del teclado
  • La ejecución del resto del programa
Si bien la composición en paralelo introducía duplicación de código y la necesidad de usar variables auxiliares, la composición en serie introduce el anidamiento sintáctico de las expresiones. En los programas reales ambos efectos conllevan un aumento de la verbosidad que se ha dado en llamar el infierno de las retrollamdas.


La solución del café helado

La manera más simple que he visto de resolver estos defectos es la que usa el lenguaje Iced Coffee Script. Básicamente introduce dos nuevas palabras clave await y defer. La palabra clave await marca el resto del código como una función anónima (que llamaré función anónima restante) y la palabra clave defer indica el punto donde introducir esa función anónima como retrollamada.

Empezaremos por un ejemplo más simple que sólo lee del teclado e imprime por pantalla. No sigo la sintaxis de Iced Coffee Script, sólo las ideas.

await leer_teclado_asincrono(defer(t))
imprime(t);

La palabra clave await toma el resto del código (que en este caso sólo es imprime(t)) y crea una función anónima con él. Esta función anónima sería algo como  t => imprime(t). Luego, sustituye en los defer esa función anónima. El resultado de esta traducción sintáctica (como si fuera una macro) es

leer_teclado_asincrono( t => imprime(t) )

Verdaderamente, hemos hecho el código más largo, pero hemos sacado la retrollamada del argumento de la función asíncrona y por tanto no estamos anidando estructuras sintácticas una dentro de otra. Si tuvieramos que componer secuencialmente varias llamadas es inmediato.

await leer_teclado_asincrono(defer(t))
await leer_fichero_asincrono(defer(f))
await leer_datos_asincrono(defer(d))
imprime(t,f,d)

Mientras que con retrollamadas sería un pequeño lío.

leer_teclado_asincrono(t => {
  leer_fichero_asincrono(f => {
    leer_datos_asincrono(d => {
      imprime(t,f,d)
    })
  })
})

Adicionalmente, el uso de la palabra clave defer permite la composición en paralelo.

await {
  leer_teclado_asincrono(defer(t))
  leer_fichero_asincrono(defer(f))
  leer_datos_asincrono(defer(d))
}
imprime(t,f,d)

Recordemos que al llamar a cualquiera de las tres funciones asíncronas, el programa no se detiene. Sólo espera (justo lo que significa await) cuando llega al final de bloque } y una vez se hayan completado las operaciones, se sigue con imprime().

Traducir esto a retrollamadas es bastante más complicado ya que necesitaríamos variables auxiliares y triplicar el código de llamada a imprime() o usar otra función auxiliar.


Continuaciones

El uso de await nos ha ocultado uno de los dos flujos de datos. Es fácil de recuperar si envolvemos todo en una función.

funcion lee_e_imprime_asincrono(){
  await leer_teclado_asincrono(defer(t))
  imprime(t)
}

lee_e_imprime_asincrono()
//Resto del código

Debo recordar aquí la versión traducida de lee_e_imprime _asincrono () que es

funcion lee_e_imprime_asincrono(){
  leer_teclado_asincrono( t => imprime(t) )
}

Lo hago para dejar claro que esta función es una función que retorna inmediatamente ya que llama a leer_teclado_asincrono() que hemos dicho que no esperaba a que se completase la lectura, sino que retornaba inmediatamente. Por eso la hemos nombrado con _asincrono al final.

Como retorna inmediatamente, se ejecuta el resto del código a la vez que se lee el teclado y se llama a imprime(). De nuevo, tenemos los dos flujos de control.

Ahora bien, si la función que acabo de crear es asíncrona... ¿por qué no acepta una retrollamada? La respuesta es que ¡debería hacerlo! Si no lo hace, desde el punto de uso sólo tenemos acceso a uno de los dos flujos de control.

lee_e_imprime_asincrono() //Falta acceso al flujo que pasa por imprime()

//Resto del código (obviamente tenemos acceso a este flujo desde aquí)

De hecho, esa retrollamada que deberíamos aceptar sería lo que hay que hacer una vez hayamos terminado con la lectura del teclado y sus retrollamadas asociadas (en este caso sólo es llamar a imprime()). Es decir, el acceso que nos falta al otro flujo de control.

funcion lee_e_imprime_asincrono(k funcion){
  await leer_teclado_asincrono(defer(t))
  imprime(t)
  k() //Continua ejecutando k
}

Ahora sí podemos componer por el otro flujo de control.

lee_e_imprime_asincrono(()=>imprime("hecho"))

//Resto del código

Este estilo de llamar a las funciones, donde manipulamos el flujo de control pasando funciones que deben ejecutarse una vez acabada las tareas que realice la función que llamamos, es el estilo de paso de continuaciones.


La alternativa C#

El problema del estilo de paso de continuaciones es que una función tiene una signatura distinta si es síncrona  o asíncrona.

funcion_sincrona(x,y,z)
funcion_asincrona(x,y,z, continuacion)

Además, nos obliga a que la continuación se conozca por anticipado. No podemos cambiarla. No podemos controlar la operación. Una vez que llamamos a la función asíncrona, perdemos el control.

Una manera de solucionarlo es, en vez de pasar la continuación, reificar la operación asíncrona y devolver un objeto que la represente. Este objeto acepta la continuación y una serie de operaciones que controlan la operación que se está realizando asíncronamente.

En C# ese objeto es de la clase Task. Esta clase permite definir la continuación con los métodos ContinueWith. Además, controla la operación que realiza la función que creó este objeto por ejemplo, esperando síncronamente, retardando, etc.

El ejemplo anterior (con la sintaxis que hemos seguido hasta ahora) usando esta idea sería:

funcion lee_e_imprime_asincrono(){
  await leer_teclado_asincrono(defer(t))
  imprime(t)
}

lee_e_imprime_asincrono().establece_continuacion(()=>imprime("hecho") )

//Resto del código

Como todo tiene su lado negativo, esta técnica dificulta la composición en paralelo. Hay que usar métodos explícitos y no se podrían poner varios defer (de hecho, C# ni siquiera usa defer). Es decir, se tiene que gestionar a mano la composición en paralelo de los objetos asíncronos.



Notas finales


Quedan algunos detalles que no voy a discutir. Este artículo se está alargando más de la cuenta. Por ejemplo, ¿cómo se llaman a las retrollamadas? ¿Quién lo hace? ¿Es el sistema operativo? ¿El propio programa?

Es más, ¿tenemos problemas de carreras con las retrollamadas? ¿Tengo que sincronizar el acceso?

Todo esto depende de la plataforma, pero en general se intenta que la retrollamada se realice desde la misma hebra y en ciertos puntos controlados para que no haya este tipo de problemas.

Otro tema que ha quedado en el aire es la definición formal de transformación de las palabras clave await/defer en otra función que usa clausuras. Realmente, sólo se usa una clausura y una máquina de estados. Esto es así porque un bloque await puede aparecer dentro de un bucle. En este caso lo que hay después del await vuelve delante con el bucle. ¿Cuál debe ser entonces la clausura?

También hemos dejado de lado ver qué ocurre con las excepciones o cancelaciones de una llamada asíncrona.

Quizás tratemos estos temas en otro post más adelante.

sábado, 17 de agosto de 2013

miniSL parte 21 - Lectura de números

Como ya adelanté en la entrada anterior, hoy vamos a ver cómo leer números. La función responsable de esto es ReadNumber().

CELL& Script::ReadNumber(ISTREAM& i)
{

Lo primero es leer un número hasta donde podamos leer. Iremos metiendo lo leído en la cadena s.

 STRING s;
 while(unsigned(i.peek())<256 && isdigit(i.peek()) && i.good())
  s+=i.get();

Si hemos llegado hasta una “x” o “X”, probablemente sea un número hexadecimal. Comprobaremos que empiece por “0x” o “0X” y pasamos a incorporar los dígitos hexadecimales en la variable s.
 if(i.peek()=='x' || i.peek()=='X')
 {
  if(s.compare(L"0")!=0) throw L"Hexadecimal numbers must begin with 0x";

  s+=i.get();
  while(unsigned(i.peek())<256 && isxdigit(i.peek()) && i.good())
   s+=i.get();
 }

Ahora tenemos el número leído y, si no ha habido error, vamos a convertirlo en un valor. Para eso vamos a usar la función wcstoul() que detecta automáticamente si el número empieza por “0x” o es decimal.

 if(i.bad()) throw L"Error while reading a number";

 wchar_t* e;
 int value=wcstoul(s.c_str(), &e, 0);

La función wcstoul() devuelve en la variable e el puntero al primer carácter que no formaría parte del número. Este puntero deberá dirigirse al final de la cadena y si no es así, ha ocurrido algo raro.

 if(e!=s.c_str()+s.size())
  throw L"Invalid number";

Por otra parte, si todo va bien, usamos CreateInteger() para generar la celda con el entero correspondiente.

 return CreateInteger(value);
}
La función CreateInteger() es muy simple. Crea una celda de tipo INT_LIT usando la función CreateCell() y le asigna el valor designado para el entero.

CELL& CreateInteger(int val)
{
 CELL& c=CreateCell(INT_LIT);
 c.int_val=val;
 return c;
}

En la próxima parte de esta serie del lenguaje MiniSL vamos a ver cómo analizar sintácticamente las expresiones primarias. Estas expresiones son las que no están formadas por otras expresiones por lo que no hay ambigüedad posible en su análisis.