Las tres cosas que diferencian funciones y macros

Hace tiempo hablé sobre las similitudes entre funciones y macros. Esta vez voy a hablar de sus diferencias.

Hay tres cosas que una macro puede hacer y una función no.

1) El control del flujo de ejecución

Una función no puede controlar qué pasa con sus argumentos. No puede controlar si se evalúan o no. No puede recuperarse de un error si uno de sus argumentos falla. No puede hacer nada. De hecho, cuando evaluamos

f(1+2, 3*4)

Lo que ocurre es que primero evaluamos los argumentos.

f(3, 12)

Y luego le pasamos el control a "f" que hará lo que tenga que hacer. Esto no es problema en un lenguaje funcional ya que no vamos a tener efectos secundarios de ningún tipo, pero sí que lo es en un lenguaje con efectos secundarios.

haz_dos_veces(print("a"))

Si "haz_dos_veces" es una función, vamos a evaluar primero los argumentos. Se imprimirá una vez "a" y pasaremos el resultado (posiblemente de tipo unitario) a la función que, haga lo que haga, no va a poder reimprimir la "a".

En el caso de que tuviéramos referencias a funciones entonces todo cambia. Ahora se puede pasar en el argumento la referencia a la función que hace lo que yo quiero.

define_funcion f() { print("a") }
haz_dos_veces(f)

Ahora sí que "haz_dos_veces" puede llamar dos veces a la función pasada e imprimir "a" dos veces. Así que cuando hay referencias a funciones esta diferencia entre macros y funciones no cuenta tanto; pero cuenta porque hay que envolver en una función el código que queremos pasar.

Las macros pueden hacerlo sin envolver nada.

define_macro haz_dos_veces(f) { f; f }
haz_dos_veces(print("a"))

Se expande a

print("a");print("a")


2) Manejo de entornos

El ejemplo más claro de esta posibilidad es la definición de símbolos en el entorno dinámico, aunque no sea lo más seguro y fácil de entender.

define_macro haz_a_cero() { a=0; }
a=1;
haz_a_cero(); //Expande a   a=0
print(a) //Imprime 0 porque ha sido modificado por la macro

Si fuera una función, hacer "a" valer cero dentro de la función sólo modifica el entorno local de la función.

define_funcion haz_a_cero() { a=0; }
a=1;
haz_a_cero();
print(a) //Imprime 1 porque no se ha modificado nada

Como ocurría con el apartado anterior, si tenemos referencias a variables (punteros), una función podría simular este comportamiento.

define_funcion haz_cero(x) {*x=0; }
a=1;
haz_cero(&a);
print(a) //Imprime 0

Sin embargo, la inspección del entorno la hemos tenido que hacer en la llamada con el "&a". La función no puede elegir qué símbolo va a cambiar. Si hubiéramos pasado "&b" la función no se quejaría y cambiaría "b". Con la macro esto no ocurría ya que ella misma inspeccionaba el entorno dinámico.


3) Procesado de código

Esta es la diferencia realmente grande. Los argumentos de una macro pueden significar algo completamente distinto a lo que se cree porque la macro puede procesar el código y cambiarlo. Por ejemplo, la macro "bromista" cambia los "+" por "-".

bromista(5+3) //Expande a  5-3

Con este tipo de transformaciones lo que realmente tenemos es la capacidad de modificar la semántica. En cierta forma, estamos ya acostumbrados. Supongamos un lenguaje en el que tengamos que declarar variables antes de usarlas, como JavaScript.

f(a=3); //Error, a no definido. 
var a=3; //Define a y le da el valor 3

El significado de "=" cuando se evalúa y cuando se escribe tras "var" es distinto. Si contemplamos "var" como una macro, lo que hace es buscar expresiones con la forma identificador-igual-valor. Para cada una de esas expresiones (en vez de evaluarlas como hizo la función "f"), define la variable en el entorno y le da ese valor.

Es esta capacidad de analizar y transformar el código de sus argumentos lo que hacen las macros únicas y superiores a las funciones.

miniSL parte 9 - Imprimiendo celdas

La impresión de celdas en miniSL es relativamente sencilla usando un algoritmo recursivo. Según el tipo de celda, imprimimos su contenido tal y como se describió en la quinta parte de esta serie.

void CELL::Print(OSTREAM& o)const
{
 switch(type)
 {
 default:  o << L"{{**UNKNOWN**}}"; break;
 case UNUSED: o << L"{{**UNUSED**}}"; break;
 case INT_LIT: o << std::dec << int_val; break;
 case BOOL_VAL: o << (bool_val ? L"true" : L"false"); break;
 case LAMBDA_VAL:o << L"{{ "; code->Print(o); o << L" }}"; break;
 case NATIVE_VAL:o << L"{{NATIVE}}"; break;

Hasta aquí ningún extraño aparte de usar una llamada recursiva para imprimir el contenido del código en las funciones lambda. Para imprimir las cadenas debemos tener cuidado ya que pueden contener caracteres de control que no son imprimibles y hay que escaparlos.

case STRING_LIT:PrintEscapedString(o, *string_val); break;
 case NAME_CODE: o << L"@"; PrintEscapedString(o, *string_val); break;

Es importante notar que los nombres no son únicamente cadenas. Las cadenas se evalúan a sí mismas mientras que los nombres se evalúan buscándolos en el entorno actual. Para distinguirlos bien, pondremos el prefijo @ delante de ellos. De esta manera permitimos usar nombres con espacios o símbolos en ellos. Veremos que será muy útil para extender la sintaxis.

La impresión de las listas la vamos a hacer en la función CELL::PrintList() para así poder reutilizar el código a la hora de imprimir celdas COMBINE_CODE.

case CONS_CTOR: case EMPTY_LIT:
  o << L"[";
  PrintList(o, L", ");
  o << L"]";
  break;
 case COMBINE_CODE:
  op->Print(o);
  o << L"(";
  operands->PrintList(o, L", ");
  o << L")";
  break;

Finalmente, la impresión de un entorno se realiza iterando sobre él.

case ENVIR_VAL: o << L"{{ENVIR ";
  for(ENVIR_TABLE::const_iterator i=envir_table->begin(); i!=envir_table->end(); ++i)
  {
   o << *i->first->string_val << L"= ";
   i->second->Print(o);
  }
  o << L"}}";
  break;
 }
}

Nos queda por implementar entonces, la impresión de listas y de cadenas escapadas. Ambas funciones son relativamente directas.

void CELL::PrintList(OSTREAM& o, STRING const& separator)const
{
 for(CELL const* c=this; c->type==CONS_CTOR; c=c->tail)
 {
  if(c!=this)
   o << separator;
  c->head->Print(o);
 }
}

void CELL::PrintEscapedString(OSTREAM& o, STRING const& s)
{
 o << L"\"";
 for(STRING::const_iterator i=s.begin(); i!=s.end(); ++i)
 {
  if(*i<32) o << L"\\x" << std::hex << (unsigned int)(unsigned)*i << L";";
  else  o << *i;
 }
 o << L"\"";
}

Por ejemplo, la impresión de una lista, una función lambda y un booleano se ve así:

[1, 2, 3]
{{ [[@"x"], [@"+"(@"x", @"x")]] }}
true

Se observa que tanto la lista como el booleano es directamente código, pero la función lambda es un valor que no es representable directamente en código. Por eso lo vamos a escribir entre dobles llaves. Estos valores deben obtenerse como el resultado de una llamada. De hecho, también se pueden imprimir celdas del tipo COMBINE_CODE que son precisamente esas llamadas. Así, f(x,y) se imprimiría así:

@"f"(@"x", @"y")

De esta manera podemos ver los valores y el código que tenemos en el montículo, pero no nos basta con verlos. Debemos también poder utilizarlos. Para eso vamos a introducir una serie de funciones que nos permita extraer valores. Estas funciones van a ser también muy sencillas. Las dejaremos para la siguiente entrada.

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.

¿Secuencial o Paralelo?

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

SECUENCIAL	PARALELO
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.

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

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.

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:

• Primer ataque cibermilitar entre países. En concreto, el sabotaje de las centrifugadoras de uranio enriquecido de Iran por parte del gusano informático Stuxnet.
• Organizaciones no gubernamentales beligerantes en la red. Como Wikileaks y sus filtraciones. El resultado ha sido la presión por parte de los EEUU a las empresas que gestionaban la financiación a esta organización (Visa, Mastercard, Paypal...)
• Grupos de ciberataque como Anonymous que, en represalia por los bloqueos arriba mencionados, atacaron las empresas que los realizaron.
• Ciberdisidentes perseguidos. En este caso el propio fundador de Wikileaks con extrañas imputaciones en un oscuro caso de acoso sexual y altas fianzas tras su detención.
• Los computadores empiezan a ver. Hasta ahora una imagen era únicamente una amalgama de píxeles de los cuales era difícil que el ordenador entendiera algo. A partir de la aparición de Kinect y su mapa de profundidad, el ordenador no sólo mira sino que también ve y entiende lo que ve. Además, hackeado por un español.
• Incremento exponencial del cibercrimen. En concreto, en 2010 se ha creado el 34% de todo el malware jamás creado.

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