jueves, 27 de enero de 2011

Escenas y escenas.

Como viene siendo habitual, de vez en cuando hablo sobre otros temas para descansar de la informática. Espero que se me disculpen estas pequeñas infidelidades.

Cuando estamos creando una historia lo más usual es que llegue un momento en el que tengamos la línea argumental completamente especificada. Sabemos qué va a ocurrir y cuándo. Qué personajes están involucrados y qué repercusión tienen sus actos. Sin embargo, hay que concretar todo lo ideado en escenas. Esta fase es el desglose en escenas (scene breakdown) o escaleta.

No puedo decir cómo se hace la escaleta porque, honestamente, no lo sé, pero sí que puedo dar una idea de las escenas con las que vamos a acabar. Son, resumidamente, de tres tipos.
  1. Escenas estructurantes. Son las escenas que dan información sobre la línea argumental. Hacen avanzar la historia o bien mostrando actos de los personajes o bien dándonos información. Ya sabéis, "Luke, yo soy tu padre" no es un acto en sí, pero es un gran trozo de información. Es interesante hacer notar también la llamada clausura. Es lo que no se muestra, pero que el lector o espectador se imagina. Una escena puede no mostrar nada directamente, pero seguir influyendo en la historia debido a que insta al lector a imaginar lo que ha ocurrido. ¿O alguien vio cómo mataron al caballo en El Padrino?
  2. Escenas caracterizantes. Estas escenas no transmiten nueva información sobre la línea argumental, pero sí sobre los personajes. Muestran un aspecto de su personalidad, o ponen a los personajes en una situación en la cual deben mostrar su personalidad. El ejemplo típico serían las escenas iniciales de las películas de James Bond. No suelen tener nada que ver con el resto de la película, pero dejan claro quién es el jefe. Una escena de este tipo también puede servir para crear un ambiente, una situación, describir un lugar o incluso sensaciones. Por ejemplo, esas escenas en las películas de terror que parece que va a pasar algo, que hay alguien en la casa, pero al final sólo es el vecino que ha perdido las llaves.
  3. Escenas irrelevantes. Escenas de relleno que pueden ser quitadas.
Rara vez una escena es de uno de estos tipos únicamente. Lo que sí está claro es que las escenas irrelevantes son las que aburren ya que no contribuyen a la historia. Entiendo que es importante detectar escenas de este tipo (o que sean en gran medida irrelevantes) y tratar de eliminarlas.

jueves, 20 de enero de 2011

¿Secuencial o Paralelo?

Este es un resumen de la charla de Guy Steele sobre paralelismo en Strange Loop.

SECUENCIALPARALELO
Se ejecuta un código A, luego se usa el resultado de A en otro código B.Se ejecutan los códigos A y B independientemente. Luego se mezclan los resultados.
Reusa el espacio. Sólo hay que almacenar un resultado.Usa espacio extra para desacoplar los cálculos.
Procesa una cosa cada vez y va acumulando resultados.Descompone y mezcla resultados. Divide y vencerás.
Requiere iniciar el acumulador con el elemento neutro de la operación.
acc=elem_neutro;
for(i=0; i<n; ++i)
   acc=acc @  x[i]
Requiere asociatividad en la operación para ir mezclando resultados. No se puede procesar en paralelo:
[$$ x_0 \star (x_1 \star (... )) $$]


Se basa en trucos para optimizar.
  • Reordenación de instrucciones.
  • Desplegado de bucles.
  • Reutilización de registros.
  • Ejecución especulativa.
  • Predicción de saltos.
  • etc. 
Se basa en propiedades algebraicas para optimizar.
  • Asociativa: La forma de agrupar operaciones no importa.
  • Conmutativa: El orden de los operandos no importa.
  • Idempotente: Las repeticiones no importan.
  • Identidad: El elemento neutro puede ser ignorado.
  • Cero: El resto de elementos puede ser ignorado. 

Así que hay que hacer que el programador deje de pensar en acumuladores y pase a pensar en propiedades algebraicas. Es decir, usar catamorfismos en vez de bucles. Los catamorfismos no son más que funciones que toman una estructura de datos y devuelven un valor a partir de ella con la propiedad de que son morfismos. En el caso de sumar una lista de números sería algo así como convertir la concatenación en suma.

[$$ f( [ 3, 5 ] .. [4, 7] ) = f( [3,5] ) + f( [4, 7] ) $$]

Esto significa a su vez que hay que buscar una operación con las propiedades algebraicas que deseemos (o podamos obtener), lo cual puede llevar a comprender más profundamente el problema.

La especificación del catamorfismo es similar al uso de sumatorios en matemáticas. No se especifica el orden de la suma, sólo que hay que sumar los elementos.

[$$ \sum_{i=1}^{n} {x_i} $$]

En programación esto se tendría que hacer usando funciones de alto nivel como fold pero asumiendo la asociatividad.

fold_assoc( suma, [3, 5, 4, 7] )

Así el compilador podría optimizar usando paralelismo sin que el programador tuviera que luchar con sincronizaciones y demás.

miércoles, 19 de enero de 2011

El BBVA le da un premio a Donald Knuth

Van un poco tarde porque este hombre lleva desde 1963 publicando libros, pero bueno. Todo sea por que se conozca algo más en España al creador de TeX, del algoritmo que convierte ecuaciones en reglas de reescritura confluentes, de otro que busca subcadenas y de El Arte de Programar Computadores.

Fuente: El Mundo

sábado, 15 de enero de 2011

miniSL parte 8 - El montículo

Llega el momento de pensar dónde y cómo almacenar las celdas en memoria. La forma en la que vamos a hacerlo es la siguiente. Usaremos un std::deque para reservar memoria. Los deques permiten ir añadiendo memoria conforme se necesite y no mueven los bloques de memoria una vez reservados.

De todas las celdas que hayamos reservado, usaremos unas y tendremos otras libres, sin usar. Utilizaremos la recolección de basura para pasar celdas antes usadas pero ahora ociosas a celdas sin usar y libres para su reciclado.

La recolección de basura es un procedimiento que puede ser o bien muy complejo o bien muy simple. En este caso, y teniendo en cuenta que miniSL intenta implementarlo todo de la forma más simple y reducida, nos inclinaremos por el algoritmo más simple de recolección de basura. El llamado mark and sweep (marca y barre).

El mark and sweep funciona en dos pasos. El primer paso detecta las celdas en uso. ¿Cómo hace eso? Muy simple. O bien es una celda raíz (que siempre está en uso) o bien nos referencian desde otra celda en uso. Estas celdas en uso son marcadas. El segundo paso es barrer (=reciclar) todas las celdas que no están marcadas y limpiar la marca en las que sí.



La siguiente figura muestra a) el conjunto raíz, b) los punteros entre celdas y c) las marcas. Las celdas que en c) no estén marcadas (las blancas) serán las reclamadas por el recolector de basura y pasarán a estar libres para un posterior uso.

En la implementación lo primero que tenemos es el std::deque de almacenamiento de celdas.

CELL_STORAGE m_Cells;

Recordemos que definíamos CELL_STORAGE así:

typedef std::deque<CELL> CELL_STORAGE;

También necesitamos saber si hay celdas libres. Las pondremos todas en una lista simplemente enlazada que empieza en el campo m_FirstUnused.

CELL* m_FirstUnused;

Para reservar una celda primero vemos si hay alguna libre. Si no, aumentamos el std::deque reservando memoria para una celda más. Esto no es muy económico ya que lo interesante habría sido devolver la memoria usada por las celdas libres. Estamos actuando más bien como un pool que como un gestor de memoria.

CELL& Script::CreateCell(CELL_TYPE ct, CELL* first, CELL* second)
{
 CELL* p;
 if(m_FirstUnused==NULL)
 {
  CELL c;
  m_Cells.push_back(c);
  p=&m_Cells.back();
 }
 else
 {
  p=m_FirstUnused;
  m_FirstUnused=p->next_unused;
 }
 p->mark=false;
 p->type=ct;
 p->head=first;
 p->tail=second;
 return *p;
}

El algoritmo de marcado es recursivo de manera que explora todo el grafo de referencias (punteros entre celdas) en profundidad. Dependiendo del tipo de celda, alguno o ninguno de sus campos serán referencias que hay que explorar. Evitamos los posibles ciclos no volviendo a marcar las celdas ya marcadas.

void Script::GCMark(CELL* c)
{
 if(c==NULL || c->mark)
 return;

 c->mark=true;

 switch(c->type)
 {
 case UNUSED:  throw L"Marking unused cell";
 case CONS_CTOR:  GCMark(c->head); GCMark(c->tail);  break;
 case LAMBDA_VAL: GCMark(c->code); GCMark(c->closure);  break;
 case COMBINE_CODE: GCMark(c->op);  GCMark(c->operands); break;

 case ENVIR_VAL:
  GCMark(c->parent_envir);
  for(ENVIR_TABLE::const_iterator i=c->envir_table->begin(); i!=c->envir_table->end(); ++i)
  {
   GCMark(i->first);
   GCMark(i->second);
  }
  break;
 }
}

El caso más laborioso es el de los entornos. En ellos hay que iterar su contenido y explorarlo para el marcado.
El borrado ocurre en la rutina de barrido. Es simple y su única dificultad radica en las celdas especiales que contienen algún dato externo. Ya vimos uno de estos casos en las cadenas internas. Las cadenas normales y los entornos son otros casos similares. Cada uno de ellos ha de tener un borrado específico.

int Script::GCSweep()
{
 int count=0;
 for(CELL_STORAGE::iterator i=m_Cells.begin(); i!=m_Cells.end(); ++i)
 {
  if(i->mark)
  {
   i->mark=false;
   continue;
  }

  if(i->type==UNUSED)
   continue;

  ++count;

  switch(i->type)
  {
  case STRING_LIT: delete i->string_val;      break;
  case ENVIR_VAL:  delete i->envir_table;      break;
  case NAME_CODE:  m_InternedStrings.erase(*i->string_val); break;
  }

  i->type=UNUSED;
  i->next_unused=m_FirstUnused;
  m_FirstUnused=&*i;
 }
 return count;
}

Como conjunto raíz vamos a tener únicamente el entorno global. Añadimos una referencia a la celda de entorno de que lo contenga y lo marcamos en la recolección de basura.

int Script::GarbageCollect()
{
 GCMark(m_GlobalEnvir);
 return GCSweep();
}

A partir de aquí hemos de recordar que el entorno global es una celda destacada. De hecho, estará referenciada en la clase Script.

CELL* m_GlobalEnvir;

El lector atento habrá visto que hemos retornado el número de celdas barridas en el recolector de basura. El retorno del número de celdas es un buen sistema para depurar el recolector de basura, pero no es el único. De hecho, nos ofrece poca información. Otro sistema que va a ser útil no sólo para el recolector de basura sino también para observar los resultados de las evaluaciones es la impresión de celdas. En la siguiente entrada nos dedicaremos a esta tarea.

lunes, 3 de enero de 2011

2010, el primer año ciberpunk de la historia

O eso es lo que dice Herb Sutter en su blog. Sus alegaciones son las siguientes:

Y tú que opinas, ¿somos ya ciberpunks o no?