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.