Haciendo un intérprete de LISP (IX)

Hasta ahora hemos usado los entornos sin definir claramente cómo son. Ahora lo haremos.

Entornos

Un entorno no es más que un mapa de las cadenas (nombres) a las celdas de un montículo. Adicionalmente, los entornos deben poder usar nombres de entornos ya creados. Entornos padres.

class Environment
{
public:
 Environment(Cell* parent) : m_Parent(parent) {}

 Cell& FindBond(STRING name)const;
 Cell& Bind(Heap& heap, std::wstring const& name, NATIVE native);
 Cell& Bind(Heap& heap, std::wstring const& name, Cell& cell);

 void Print(std::wostream& o, std::wstring const& indent, int depth=10)const;

public:
 Cell* m_Parent;
 typedef std::map<string, Cell*> BONDMAP;
 BONDMAP m_Bonds;
};

Hemos usado un pequeño atajo para incluir funciones nativas.

Cell& Environment::Bind(Heap& heap, std::wstring const& name, NATIVE native)
{
 Cell& r=heap.CreateNative(native);
 m_Bonds[heap.GetStringFromPool(name)]=&r;
 return r;
}

Cell& Environment::Bind(Heap& heap, std::wstring const& name, Cell& cell)
{
 m_Bonds[heap.GetStringFromPool(name)]=&cell;
 return cell;
}

Buscando en el entorno padre

La búsqueda en un entorno no debe fallar si no se encuentra el nombre deseado. En ese caso hemos de recurrir al entorno padre. Esta es una forma de extender el entorno padre de manera sencilla.

Cell& Environment::FindBond(STRING name)const
{
 BONDMAP::const_iterator i=m_Bonds.find(name);
 if(i==m_Bonds.end() || i->second==NULL)
 {
  if(m_Parent==NULL)
   throw std::runtime_error("Unknown symbol");

  return m_Parent->GetEnvironment().FindBond(name);
 }

 return *i->second;
}

El resultado es una función de búsqueda recursiva, pero sin mayor dificultad.

Haciendo un intérprete de LISP (VIII)

En este mensaje vamos a ver cómo funciona la aplicación de una función lambda.

Creación del entorno local

El primer paso en la aplicación de una función lambda es crear un entorno local. Esto es necesario para dos cosas. La primera es aislar la evaluación de la función del entorno de uso de la función. Si lo lo aisláramos, se podría definir un símbolo en el entorno de uso. Lo que es antihigiénico. También usamos el entorno local para vincular el resultado de la evaluación de los argumentos a los nombres de los parámetros.

Cell& Lambda::Apply(Heap& heap, Cell& args, Cell& envir)const
{
 Cell& local_cell=heap.CreateEnvironment(&m_Closure);
 Environment& local=local_cell.GetEnvironment();

La creación de un entorno ha de estar sujeta a la gestión de memoria. Por esa razón lo creamos en una celda y, dentro de la celda, tenemos el objeto Environment que es realmente el entorno. Para simplificar futuros uso en la aplicación, le damos el nombre "local" al propio entorno.

Vinculación de los resultados de los argumentos

Ahora debemos ir argumento por argumento evaluándolos en el entorno de uso. El resultado de cada evaluación debe ser vinculada a cada parámetro. Así pues, necesitamos dos listas: la de los argumentos y la de los parámetros.

 Cell const *a, *p;

Las iremos recorriendo a la vez. Desde el principio hasta que una de las dos no sea un CT_PAIR. En ese momento terminaremos. Si no hemos terminado, avanzamos en ambas a la vez.

 for(a=&args, p=&m_Params; a->IsPair() && p->IsPair(); a=&a->GetTail(), p=&p->GetTail())

El interior del bucle debe primero evaluar el argumento y luego vincularlo. Es importante recordar aquí que estamos apuntando a una lista y para obtener el elemento que hay en cabeza de la lista hay que ir a su cabeza.

 local.Bind(heap, *p->GetHead().GetName(), heap.Evaluate(a->GetHead(),envir));

Los parámetros han de ser nombres así que si no lo son GetName() fallará con una excepción. La evaluación es en "envir". Este es el entorno de uso desde el que se llama a la función. El método "Bind" queda por ser definido pero lo que hace es relacionar el nombre pasado con el valor pasado (celda pasada).

Una comprobación de aridad

En este punto puede ocurrir que haya más argumentos que parámetros o más parámetros que argumentos. En ambos casos es un error y debemos lanzarlo.

 if((a->IsEmpty())!=(p->IsEmpty()))
  throw std::runtime_error("Incorrect arity");

Como vemos, es fácil de detectar ya que basta con que una de las dos listas no esté vacía. Como sabemos que una de las dos no es un CT_PAIR y que ambas son listas, la comprobación se simplifica a lo puesto arriba.

La evaluación del cuerpo

Ya tenemos el entorno local con los parámetros vinculados a los valores de los argumentos correspondientes. Eso significa que si evaluamos ahora el cuerpo y nos encontramos con un nombre de parámetro, al estar vinculado al valor del argumento, se evaluará a dicho valor.

 return heap.Evaluate(m_Body, local_cell);
}

Ni que decir tiene que al evaluar dentro de una aplicación abrimos la puerta a la recursividad. Esto es deseable.

Esto es el núcleo de cualquier LISP. En los siguientes posts veremos algunos detalles menores: la implementación de los entornos (y el método Bind), evaluación de secuencias y poco más.

Haciendo un intérprete de LISP (VII)

Hasta ahora hemos hablado de cómo almacenar valores (las celdas), cómo representarlos (las expresiones S), cómo pasar de la representación al valor (la evaluación) y cómo calcular un valor a partir de unos argumentos (la aplicación de una función). Falta un paso fundamental: poder definir las funciones.

En este post y el siguiente nos dedicaremos a esto.

El lambda cálculo

Los modelos de computación trabajan en base a un concepto muy simple: las sustituciones de una cosa por otra. Dependiendo de qué sustituyamos y qué reglas usemos para sustituir obtendremos un tipo de computación u otro. La definición de funciones en LISP se basa en el lambda cálculo. En este cálculo las sustituciones son de una variable por un término.

La sintaxis del lambda cálculo es muy simple:

t ::= x\ |\ t t\ |\ \lambda x.t

La x son las variables. Las dos t son dos términos yuxtapuestos y representan la aplicación. Finalmente la lambda destaca la variable a sustituir en el término que precede. Es decir, el lambda cálculo separa la sustitución en dos partes: abstracción y aplicación.

La regla fundamental del lambda cálculo es la beta reducción. No es más que la sustitución de la variable por el argumento aplicado.

(\lambda x. t) s \rightarrow t[x/s]

En el LISP se usa otra técnica similar. Para empezar se usa el orden aplicativo (primero se calcula el valor de s y luego se aplica). En vez de sustituir, vinculamos la x al valor del argumento recién calculado. Luego, cuando evaluemos t y nos encontremos con el nombre x, usamos ese valor. Realmente es como si sustituyamos con la aparición intermedia del entorno. Veremos más adelante que esto es muy útil.

La clausura léxica

La descripción de arriba deja un pequeño resquicio problemático. Al no sustituir sino vincular los nombres con valores, cabe la posibilidad de hacer referencia a nombres no definidos. Esto ya lo he hablado alguna que otra vez en mensajes previos. La solución es dejar que cada entorno donde se vinculen nombres a valores tenga un entorno padre. El entorno padre de la aplicación de argumentos ha de ser el entorno de definición.

De esta manera cualquier uso de un nombre que no sea un parámetro es capturado y no dará error. Es lo que se denomina la clausura léxica.

El resultado de todo esto es que una vez definamos una función usando una abstracción lambda (lo que he llamado una función lambda) necesitamos tres cosas:

1. El término de la abstracción (que se evalúa tras las vinculaciones)
2. Los nombres de los parámetros a vincular con los valores de los argumentos
3. El entorno padre del entorno que vincula los nombres anteriores (la clausura léxica)

Nuestro objeto Lambda estará compuesto de estas tres cosas.

El objeto Lambda

La estructura de este objeto será:

class Lambda
{
protected:
Cell& m_Params;
Cell& m_Body;
Cell& m_Closure;
}

Y las operaciones que queremos realizar sobre él son dos: crearlo y aplicarlo a unos argumentos.

public:
Lambda(Cell& params, Cell& body, Cell& closure)
: m_Params(params), m_Body(body), m_Closure(closure) {}

Cell& Apply(Heap& heap, Cell& args, Cell& envir)const;

Realmente la creación es muy simple: sólo hay que recordar estas tres cosas. La aplicación tiene algo más de trabajo ya que, al usar un orden aplicativo, hemos de evaluar los argumentos antes de vincularlos. Además, la vinculación requiere la creación de un nuevo entorno y la aplicación requiere una evaluación del cuerpo de la abstracción lambda.

Haciendo un intérprete de LISP (VI)

El resultado de una evaluación era o bien un valor muy fácilmente calculable (literal, error, nombre) o bien una aplicación de una función (nativa o lambda) a unos argumentos. En este post veremos cómo realizar una función nativa.

La interfaz de la función nativa

Si recordamos del último post, había tres cosas que pasábamos con la aplicación de la función nativa: El montículo por si queríamos reservar más celdas; la lista de argumentos y el entorno por si necesitamos calcular el valor de un nombre. Así que la interfaz de una función nativa debe ser:

typedef Cell& (*NATIVE)(Heap& heap, Cell& args, Cell& envir);

Es importante recordar aquí que los argumentos no están evaluados. Se pasaban directamente (ver en el último post). Será un detalle a tener en cuenta.

Una función para sumar enteros

Como uno de los tipos de literales que tenemos son los enteros, hagamos una pequeña función nativa que sume enteros. Sabemos empezarla con la interfaz de arriba.

Cell& FOL_Add(Heap& heap, Cell& args, Cell& envir)
{

Luego hemos de pensar en evaluar los argumentos. Si son literales no hay problemas (se evalúan a ellos mismos), pero si tenemos dos sumas anidadas hay que evaluar. Así pues necesitamos dos cosas: los argumentos y el resultado parcial de la suma.

 Cell* qa=&args;
 INTEGER result=0;

Lo que vamos a hacer es ir recorriendo la lista de argumentos sin evaluar (qa) e ir añadiendo los resultados de la evaluación de los argumentos a result. Como una lista es una cadena de pares, el código sería así:

 while(qa->IsPair())
 {
  result+=heap.Evaluate(qa->GetHead(), envir).GetInteger();
  qa=&qa->GetTail();
 }

Finalmente, el resultado es un entero pero lo tenemos en una variable, no en una celda. Hay que crear la celda y retornarla. Usamos el montículo para eso.

 return heap.CreateInteger(result);
}

Con lo que sólo faltaría probar la función nativa.

El bucle de lectura-evaluación-impresión

Un intérprete LISP hace tres cosas en ciclo y de forma indefinida. Primero, lee una expresión S. Luego, la evalúa obteniendo un resultado. Finalmente, la imprime. Hasta ahora sólo hemos hablado de la evaluación. La lectura y la impresión son asuntos menores.

Otro aspecto importante es que no podemos usar la función nativa directamente. Hay que darle primero un nombre. Para eso necesitamos manipular entornos. Tampoco es excesivamente difícil y lo veremos algo más adelante. Si le damos el nombre "add" a la función nativa de arriba, interactuamos con el intérprete de la siguiente manera:

> (add 13 72)

85

>

En los siguientes posts hablaré de qué es una celda CT_LAMBDA, cómo generarlas y cómo usarlas. Esto nos deparará algunas interesantes sorpresas como las clausuras léxicas.

Haciendo un intérprete de LISP (V)

En los posts anteriores vimos unas estructuras muy simples para almacenar valores de nuestro LISP. Estas estructuras son las celdas. Las celdas estaban gestionadas por un montículo (heap) con el cual podíamos crear nuevas celdas. También recordamos que las expresiones S en las que escribíamos nuestro código eran parte de los valores. Esto es lo que se denomina homoiconicidad.

En este post vamos a ir al núcleo del asunto: crear una celda resultado de una expresión. 

Evaluación

Las reglas de evaluación del LISP son muy sencillas y ya las vimos. Según el tipo de celda, se evalúa de una u otra manera. Eso significa que nuestra función de evaluación va a ser un switch.

Debido a que la evaluación va a crear nuevas celdas con el resultado de los cálculos, voy a incluirla en el montículo.

Además, y debido a que vamos a tener nombre cuyo valor dependerá del contexto en el que los evaluemos, vamos a requerir el paso de un argumento extra con ese contexto. El contexto estará guardado en un entorno que es otro tipo de celda.

Con todas estas cosas en mente, empezamos la implementación así:

Cell& Heap::Evaluate(Cell& c, Cell& envir)
{
if(envir.CellType()!=Cell::CT_ENVIR)
 throw std::runtime_error("Environment cell is not an environment");

switch(c.CellType())
{

Empecemos por el caso más fácil. Si la celda no es de un tipo evaluable, emitimos un error.

 default:
case Cell::CT_UNUSED:
case Cell::CT_ENVIR:
case Cell::CT_LAMBDA:
 throw std::runtime_error("Evaluating a non-evaluable cell");

El siguiente caso más fácil son los literales. El resultado del literal es él mismo aquí tenemos dos opciones. La primera es crear otra celda con el mismo valor, la segunda es reutilizar la celda de la propia expresión como valor del resultado. Generalmente se usa esta última opción ya que nos ahorramos una reserva de celda.

case Cell::CT_EMPTY:
case Cell::CT_INTEGER:
case Cell::CT_REAL:
case Cell::CT_STRING:
case Cell::CT_BOOLEAN:
 return c;

Destacamos aquí que la lista vacía se evalúa también como un literal. Es decir, el resultado de una lista vacía es la propia lista vacía.

El siguiente caso más fácil es el de los nombres. Los nombres se evalúan a lo que diga el entorno en el que estamos. Como ese entorno ya se nos ha pasado en un argumento, delegamos esa búsqueda al entorno. Habrá que programarla más adelante.

 case Cell::CT_NAME:
 return envir.GetEnvironment().FindBond(c.GetName());

Finalmente, queda la evaluación de una lista compuesta por una cadena de pares. Es algo más complejo así que le dedicaremos un apartado especial.

Aplicación de argumentos

Hay una distinción que es clave. Una función no es lo mismo que el nombre de la función. De hecho, una misma función puede tener varios nombres. Eso dependerá del entorno.

Así pues, no es lo mismo evaluar el nombre de una función a evaluar la función. En el primer caso usamos el entorno, en el segundo caso necesitamos unos argumentos que pasarle a la función para que ésta calcule su resultado. A esta última operación se la llama aplicación.

Debido a que a las funciones se les pasa los argumentos en una lista (ya que las expresiones S son listas) hemos de requerir que realmente sea una lista. Es decir, una cadena de pares (celdas CT_PAIR) acabada en CT_EMPTY. Algo como (f a b c d) que realmente es [f [a [b [c [d ()]]]]].

 case Cell::CT_PAIR:
 if(c.IsList())
 {

Ya veremos qué ocurre si no es una lista. En este caso, sabemos que el primer elemento de la lista es el nombre de la función y hay que evaluarlo para realmente obtener la función en sí.

  Cell& f=Evaluate(c.GetHead(), envir);

Dijimos que íbamos a tener dos tipos de funciones. Las funciones nativas (las predefinidas) y las lambda (definidas por el usuario). El primer caso es muy sencillo. Le pasamos a la nativa el montículo (para que pueda reservar sus celdas), los argumentos (para que pueda usarlos al evaluar) y el entorno (por si necesita usar o crear nombres). El resultado de la evaluación será lo que la función nativa nos diga.

  if(f.IsNative())
   return f.GetNative()(*this, c.GetTail(), envir);

Ya tendremos tiempo de implementar algunas funciones nativas más adelante. Ahora nos conformaremos con echarle toda la carga de trabajo a la nativa.

En este momento comprobamos que la celda que tenemos o es una función lambda o estamos intentando aplicar algo que no es una función.

  if(f.CellType()!=Cell::CT_LAMBDA)
   throw std::runtime_error("Applying non-lambda");

Finalmente, como lo que tengo es una CT_LAMBDA, usaré el objeto Lambda para aplicar los argumentos. Como hicimos con las funciones nativas, no vamos a definir ahora cómo se aplica una lambda. De hecho, primero hemos de saber cómo construir una función lambda y para eso vamos a necesitar una función nativa. Así que ni nos preocupamos, de nuevo le pasamos el montículo, los argumentos, el entorno y lo que retorne el método Apply del objeto Lambda será el resultado de la evaluación.

  return f.GetLambda().Apply(*this, c.GetTail(), envir);
 }

Para acabar tenemos el caso de qué hacer si estamos evaluando un CT_PAIR que no es una lista. La opción más fácil sería abortarlo emitiendo un error pero, por hacer algo distinto, vamos a evaluar cada uno de los dos componentes del par y retornamos un nuevo par (habrá que crearlo) con cada resultado en el componente correspondiente.

 else
 {
  //Create pair
  return CreatePair(Evaluate(c.GetHead(), envir), Evaluate(c.GetTail(), envir));
 }

Cerramos switch y la función de evaluación.

}
}

Resumiendo

No se ha hecho mucho en la evaluación realmente. Hemos comprobado el tipo de celda. Según ese tipo o emitíamos un error o devolvíamos la propia celda o buscábamos el nombre en el entorno o aplicábamos argumentos si era nativa o lambda.

Ahora todo el meollo está en la aplicación. Como tenemos los enteros como tipos básicos, introduciremos una pequeña función nativa que los sume... pero en el siguiente post.

Coinducción

Estudiando teoría de tipos me he cruzado con el concepto de coinducción. Es un concepto fácil y con interesantes consecuencias.

Inducción

Tanto en la inducción como en la coinducción queremos saber qué elementos de un conjunto universo U cumplen una propiedad P. Llamemos precisamente P al conjunto de elementos que cumplen P. Obviamente

[$$ P\subseteq U $$]

En el caso de la inducción partimos con unos casos base B que son elementos de los que tenemos constancia directa de su propiedad P. De nuevo y obviamente

[$$ B\subseteq P\subseteq U $$]

Ahora necesitamos el paso de inducción. El paso de inducción nos dice que si conocemos que ciertos elementos cumplen la propiedad, entonces otros también la cumplen. El paso clásico es

[$$ P(n)\rightarrow P(n+1) $$]

Sin embargo, generalizamos pensando que si he comprobado que los elementos de X cumplen la propiedad, entonces los elementos de F(X) también la cumplen. F(X) representa a los elementos del siguiente paso. Es decir,

[$$ X\subseteq F(X) $$]

El resultado es que cada vez X se hará más y más grande... hasta encontrar un punto fijo (por el teorema de Kleene es el mínimo punto fijo)

[$$ X=F(X)=\mu F $$]

En ese momento P=X.

Nota adicional: Si hacemos que

[$$ F(\emptyset )=B $$]

Se captura también la idea de caso base en el formalismo de F (llamada función generadora). Una restricción para esta F es que debe ser monótona.

[$$ U\subseteq V \rightarrow F(U)\subseteq F(V) $$]

Esto es lógico porque si hemos probado que un elemento x cumple la propiedad P(x) está claro que debe seguir cumpliéndola conforme avancemos en la demostración.

Coinducción

Algunas propiedades no se pueden demostrar por inducción. Sólo podremos demostrar por inducción aquellas en las que exista una función generadora F cuyo mínimo punto fijo sea P. Como ya hemos escrito,

[$$ \mu F=P $$]

Sin embargo, tenemos otro punto fijo que es el máximo punto fijo. En este punto fijo, empezamos por asumir que todos los elementos de U cumplen la propiedad y luego, con la F, vamos quitándolos. Eso es la coinducción.

Partimos de unos casos bases de los que estamos seguros que fuera de ellos no se cumple P. Luego vamos refinando esos casos quitando poco a poco, usando F otra vez, hasta llegar al máximo punto fijo.

[$$ \nu F=F(X)=X=P $$]

Todo esto está muy bien, ¿pero para qué sirve?

Principalmente para nada si ambos puntos fijos son el mismo, pero si no son el mismo obtenemos propiedades distintas ya usemos la inducción o la coinducción.

Aplicación a los subtipos recursivos

Supongamos que tenemos una lista definida de la manera usual en tipos algebráicos paramétricos.

Lista(X) = vacía | par X Lista(X)

Es decir, una lista es o bien la lista vacía o bien un par de un elemento del contenido de la lista (tipo X) con el resto de la lista.

Ahora tendremos dos tipos, los enteros y los reales. Está claro que un entero es un subtipo de un real de sólo lectura ( Entero <: Real ), pero ¿es una lista de enteros una lista de reales? ( Lista(Entero) <: Lista(Real) ).

Vayamos por partes.

Una lista vacía es una lista vacía así que no vamos a tener problemas ahí.

Si un par X Y es subtipo de otro par S T entonces X ha de ser subtipo de S e Y de T. Es decir

[$$ par\ X\ Y\ <:\ par\ S\ T\ \ \leftrightarrow\ \ X<:S\ \ \wedge\ \ Y<:T $$]

Cuando comparamos las listas de enteros y reales los primeros términos del par son precisamente Entero y Real por lo que todo va bien. Sin embargo, en el segundo término volvemos a tener Lista(Entero) y Lista(Real) que es justo lo que queríamos comprobar.

Estamos usando tipos recursivos y es normal que esto pase.

Si usáramos inducción deberíamos decir "Como no he comprobado que Lista(Entero)<:Lista(Real) entonces lo asumo falso y concluyo que una lista de enteros no es una lista de reales".

Si usáramos coinducción deberíamos decir "Como no he comprobado que Lista(Entero)<:Lista(Real) entonces lo asumo cierto y concluyo que una lista de enteros es una lista de reales".

En los lenguajes de programación que usan tipos recursivos, el uso de la coinducción es necesario ya que de otra forma estos tipos recursivos no cumplirían ninguna propiedad.

Haciendo un intérprete de LISP (IV)

Hasta ahora hemos hablado de las celdas, pero no de cómo se manejan esas celdas. En este post nos centraremos más en el montículo (heap).

Operaciones sobre celdas

Dado que las celdas no se pueden modificar, tenemos tres operaciones sobre las celdas: crearlas, leerlas y destruirlas. Para simplificar más la cosa, en esta implementación no vamos a destruir las celdas. Las vamos a dejar ahí en memoria hasta que el programa finalice. Esto es muy derrochador. Las implementaciones reales de LISP tienen un sistema denominado recolección de basura que se dedica a descubrir cuáles son las celdas sin usar y las destruye.

Por otra parte, el interfaz de lectura de celdas ya lo hicimos dentro de la propia celda. Esto significa que lo único que va a hacer nuestro montículo, por ahora, va a ser crear celdas. El montículo tendrá entonces una interfaz similar a esta.

class Heap
{
public:
Cell& CreateEmpty(void);
Cell& CreatePair(Cell& head, Cell& tail);
Cell& CreateInteger(INTEGER integer);
Cell& CreateReal(REAL real);
Cell& CreateString(std::wstring const& string);
Cell& CreateBoolean(BOOLEAN boolean);
Cell& CreateName(std::wstring const& string);
Cell& CreateEnvironment(Cell* parent_envir);
Cell& CreateLambda(Lambda& ol);
Cell& CreateNative(NATIVE native);
};

También añadiremos una función de impresión para ver lo que tenemos en el montículo.

 void Print(std::wostream& o)const;

Y más adelante añadiremos un par de funciones de evaluación. Ahora lo interesante es saber cómo vamos a gestionar el almacenamiento de celdas.

Almacenando celdas

Como vamos a reservar espacio para las celdas pero luego no lo vamos a liberar, una forma sencilla de reservar memoria es usando un deque. Un deque es una cola formada por bloques. En cada bloque habrá varios elementos (celdas en nuestro caso). Desde cierto punto de vista, un deque está a medio camino entre un arreglo y una lista. En un arreglo todos los elementos están juntos y en una lista cada elemento está separado de los demás. En la lista es necesario enlazar las posiciones de los elementos unos con otros mediante referencias.

El deque guarda los elementos consecutivos dentro de cada bloque, pero los bloques entre sí están enlazados con referencias. De esta manera la búsqueda de elementos es relativamente rápida y cuando hay que almacenar más elementos no hemos de volver reservar memoria para todo el arreglo. Sólo para un nuevo bloque. Esto significa que los elementos en un deque no se copian de aquí para allá y tener un puntero a ellos es relativamente seguro.

La implementación será así:

protected:
Cell& AllocCell(void);

protected:
std::deque<Cell> m_Cells;

Luego, la implementación de la reserva de celdas es simple y directa:

Cell& Heap::AllocCell(void)
{
m_Cells.push_back(Cell());
return m_Cells.back();
}

Creando celdas

Ya que podemos reservar espacio para las celdas, vamos a crearlas. Cada creación constará de dos pasos. El primero, reservar el espacio para celdas. El segundo, cambiar el tipo de celda de CT_UNUSED al tipo adecuado y con los datos adecuados. Esto ya lo hacíamos con los métodos de Cell así que realmente todo es bastante simple.

Cell& Heap::CreateEmpty(void)
{
return AllocCell().SetEmpty();
}

Cell& Heap::CreatePair(Cell& head, Cell& tail)
{
return AllocCell().SetPair(head, tail);
}

Cell& Heap::CreateInteger(INTEGER integer)
{
return AllocCell().SetInteger(integer);
}

Cell& Heap::CreateReal(REAL real)
{
return AllocCell().SetReal(real);
}

Cell& Heap::CreateString(std::wstring const& string)
{
return AllocCell().SetString(GetStringFromPool(string));
}

Cell& Heap::CreateBoolean(BOOLEAN boolean)
{
return AllocCell().SetBoolean(boolean);
}

Cell& Heap::CreateName(std::wstring const& string)
{
return AllocCell().SetName(GetStringFromPool(string));
}

Cell& Heap::CreateEnvironment(Cell* parent_envir)
{
return AllocCell().SetEnvironment(parent_envir);
}

Cell& Heap::CreateLambda(Lambda& ol)
{
return AllocCell().SetLambda(ol);
}

Cell& Heap::CreateNative(NATIVE native)
{
return AllocCell().SetNative(native);
}

Con esto tenemos lo fundamental para empezar a evaluar. La evaluación no es más que la creación de la celda que almacene el resultado. Lo veremos en el siguiente post.

Haciendo un intérprete de LISP (III)

En esta tercera entrada voy a explicar las operaciones sobre las celdas.

Selectores de una celda

Como ya dijimos, aunque la celda sea una clase C++, no vamos a usar polimorfismo. Usaremos la aproximación del C con switches. Eso significa que el primer selector que necesitamos es

CELL_TYPE CellType(void)const { return cell_type; }

Y también sería interesante alguna forma de ver los contenidos de la celda.

void Print(std::wostream& o, std::wstring const& indent=L"", int depth=10)const;

El primer argumento es el stream de salida que vamos a usar para imprimir. Luego la indentación que queremos y finalmente, debido a que podemos hacer ciclos referenciando celdas, la máxima profundidad de representación. Nada de esto es muy importante por ahora.

Otros selectores más interesantes son los que preguntan por un tipo concreto.

 bool IsEmpty(void)const
 {
  return cell_type==CT_EMPTY;
 }

 bool IsPair(void)const
 {
  return cell_type==CT_PAIR;
 }

 bool IsName(void)const
 {
  return  cell_type==CT_NAME;
 }

 bool IsNative(void)const
 {
  return  cell_type==CT_NATIVE;
 }

Luego, los que obtienen los campos relevantes de cada tipo de celda:

 Cell& GetHead(void)const
 {
  if(cell_type!=CT_PAIR)
   throw std::logic_error("Only pairs have head");

  return *value.head;
 }

 Cell& GetTail(void)const
 {
  if(cell_type!=CT_PAIR)
   throw std::logic_error("Only pairs have tail");

  return *value.tail;
 }

 INTEGER GetInteger(void)const
 {
  if(cell_type!=CT_INTEGER)
   throw std::logic_error("Only integers have an integer value");

  return value.integer;
 }

 REAL GetReal(void)const
 {
  if(cell_type!=CT_REAL)
   throw std::logic_error("Only reals have a real value");

  return value.real;
 }

 BOOLEAN GetBoolean(void)const
 {
  if(cell_type!=CT_BOOLEAN)
   throw std::logic_error("Only booleans have a boolean value");

  return value.boolean;
 }

 STRING GetString(void)const
 {
  if(cell_type!=CT_STRING)
   throw std::logic_error("Only strings have a string value");

  return value.string_idx;
 }

 STRING GetName(void)const
 {
  if(cell_type!=CT_NAME)
   throw std::logic_error("Only names have a name value");

  return value.string_idx;
 }

 Environment& GetEnvironment(void)const
 {
  if(cell_type!=CT_ENVIR)
   throw std::logic_error("Only environments have an environment value");

  return *value.environment;
 }

 Lambda& GetLambda(void)const
 {
  if(cell_type!=CT_LAMBDA)
   throw std::logic_error("Only lambdas have an lambda value");

  return *value.lambda;
 }

 NATIVE GetNative(void)const
 {
  if(cell_type!=CT_NATIVE)
   throw std::logic_error("Only natives have a native value");

  return value.native;
 }

Finalmente, añadimos un predicado que nos dice si una cadena de pares es una lista (termina en CT_EMPTY) o no.

 bool IsList(void)const
 {
  Cell const* c=this;
  while(c->IsPair())
   c=c->value.tail;
  return c->IsEmpty();
 }

De esta manera, cualquier cosa que queramos de la celda no requiere el conocimiento del interior de la celda. Separamos implementación de interfaz.

El siguiente paso es la modificación de las celdas.

Operaciones sobre celdas

La operación principal va a ser cambiar la celda a un tipo y con unos miembros específicos. Las celdas van a ser inmutables. Eso significa que si una celda no era CT_UNUSED, cambiarla es un error.

 Cell& SetPair(Cell& head, Cell& tail)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_PAIR;
  value.head=&head;
  value.tail=&tail;
  return *this;
 }

 Cell& SetInteger(INTEGER integer)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_INTEGER;
  value.integer=integer;
  return *this;
 }

 Cell& SetReal(REAL real)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_REAL;
  value.real=real;
  return *this;
 }

 Cell& SetBoolean(BOOLEAN boolean)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_BOOLEAN;
  value.boolean=boolean;
  return *this;
 }

 Cell& SetString(STRING string)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_STRING;
  value.string_idx=string;
  return *this;
 }

 Cell& SetName(STRING name)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_NAME;
  value.string_idx=name;
  return *this;
 }

 Cell& SetEnvironment(Cell* parent);

 Cell& SetLambda(Lambda& ol)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_LAMBDA;
  value.lambda=&ol;
  return *this;
 }

 Cell& SetNative(NATIVE native)
 {
  if(cell_type!=CT_UNUSED)
   throw std::logic_error("Cells are immutable");

  cell_type=CT_NATIVE;
  value.native=native;
  return *this;
 }

Excepto SetEnvironment() el resto de operaciones son simples. El caso de SetEnvironment() es distinto porque esa celda debe guardar un entorno. El entorno es la relación entre nombres (cadenas) y un valor. Necesitamos un mapa para eso. Meteremos el mapa en una clase Environment y crearemos la celda así.

Cell& Cell::SetEnvironment(Cell* parent)
{
 if(cell_type!=CT_UNUSED)
  throw std::logic_error("Cells are immutable");

 cell_type=CT_ENVIR;
 value.environment=new Environment(parent);
 return *this;
}

Constructores y destructores

El que una celda de entorno contenga un objeto de la clase Environment significa que en algún lado habrá que destruir ese objeto creado. De hecho, también hay que destruir los objetos Lambda (que ya veremos cómo y dónde se crean). De este modo, nuestro constructor y destructor queda así.

 Cell(void) : cell_type(CT_UNUSED) {}
 ~Cell(void);

Luego, el cuerpo del destructor será

Cell::~Cell(void)
{
 switch(cell_type)
 {
 case CT_ENVIR:
  delete value.environment;
  break;

 case CT_LAMBDA:
  delete value.lambda;
  break;
 }
}

En resumen:

• Tenemos dos formas de identificar las celdas. Con el CellType() y con predicados del tipo IsName(). Estos últimos sólo son una abreviatura de cosas como CellType()==Cell::CT_NAME.
• Tenemos varios selectores para obtener los miembros de las celdas: GetTail(), GetName(), etc.
• Tenemos varias operaciones para hacer la celda de un tipo: SetPair(), SetLambda(), etc. Sólo se pueden usar si la celda es de tipo CT_UNUSED.
• Finalmente, tenemos un constructor que inicializa la celda a CT_UNUSED y un destructor que elimina los objetos Environment o Lambda que podamos haber asignado a una de estas celdas.

Probando el SyntaxHighlighter

Voy a ver si estos scripts de Alex Gorbatchev van bien. Si es así, voy a actualizar los mensajes del LISP para que queden más bonitos.

class prueba
{
void sintactica(int a, int b, int c)
{
for(int x=a; x<b; x+=c)
  std::cout << x << std::endl;
}
};

Desafortunadamente no consigo que escape solo. Habrá que usar el escape manual.

Haciendo un intérprete de LISP (II)

Continuamos con el intérprete LISP. Esta vez vamos a hablar más tranquilamente de las formas aplicativas y la evaluación.

Representando expresiones S con celdas

De las celdas vistas, no todas se usan para las expresiones S.

• Se usan: CT_INTEGER, CT_REAL, CT_STRING, CT_BOOLEAN que son los tipos básicos que vamos a usar (no todos estos tipos son usuales en LISP). A estos valores se les llama literales (y a las celdas que los contienen celdas literales, aunque esto ya lo sabemos).
• También se usan: CT_EMPTY y CT_PAIR para crear las listas. Recordemos cómo se encadenaban los pares para guardar una lista en las celdas. Se pasaba de (1 2 3) a [1 [2 [3 ()]]] donde () es la lista vacía representada por CT_EMPTY.
• También se usa: CT_NAME es un nombre. Veremos que los nombres no tienen un valor propio sino que hay que buscarlo en el entorno en el que estemos trabajando. Más sobre esto en evaluación. La idea es que si escribo "hola" tengo una cadena, pero si escribo hola tengo un nombre. A los literales y a los nombres se les llama átomos.
• No se usan: CT_ENVIR que es para guardar qué significa cada nombre, CT_LAMBDA que sólo vale para ser aplicada a unos argumentos y CT_NATIVE que es una forma predefinida también para aplicar a unos argumentos.

En general, si queremos calcular algo tenemos que escribirlo. Y, de lo que tengo escrito, tendré que calcular lo que desconozco. En esos cálculos usaré herramientas accesorias que no se pueden calcular de por sí (entornos y formas aplicativas).

La evaluación en LISP

Hay cuatro tipos de celdas en LISP según cómo se evalúan. Generalmente, lo que se puede evaluar es lo que puedes escribir como una expresión S y quieres saber su valor (de ahí lo de evaluar). Si no lo puedes escribir como una expresión S, no se puede evaluar.

• No evaluables: Son sencillos de evaluar puesto que generan un error. Un ejemplo de no evaluable es un entorno. Una celda CT_ENVIR está pensada para guardar información de entorno, no para ser evaluada. La celda CT_LAMBDA tampoco se puede evaluar. Está pensada para ser aplicada, no se puede escribir como expresión S y por tanto no se puede evaluar. Igual con la celda CT_NATIVE.
• Literales: También son sencillos de evaluar porque representan a los valores que ya conozco. Si tengo un 3 es un 3 su valor. Así que el resultado de evaluar un literal es el propio literal. El valor CT_EMPTY es extraño porque también se considera literal, es decir, el resultado de calcular el valor de una lista vacía es una lista vacía.
• Nombres: Muy sencillo también. Un nombre no es un valor directamente. x puede ser 3 o puede ser 5. Dependerá de en el entorno en el que trabajemos. Así pues, un nombre se evalúa a lo que diga el entorno. Esta es la única función de un entorno.
• Listas: Es la interesante, ¿Qué representa (+ 1 1)? Representa la suma de uno y uno. El resultado de la evaluación debe ser la suma de uno y uno. ¿Qué representa 1? Es un literal y vale él mismo. ¿Qué representa +? La suma. Pero la suma no tiene valor hasta que le damos los argumentos 1 y 1. Es decir, que el valor del nombre + es una forma aplicativa a la que podemos aplicarle los argumentos 1 y 1.

Un poco de código

No vamos a profundizar más por ahora. Tendremos tiempo para hablar de qué se evalúa a qué. Ahora vamos a relajarnos un poco con unas pocas definiciones de código. A ver cómo hacemos una celda del montículo.

Vamos a usar un diseño a lo C. Es decir, una unión y muchos switch. Eso sí, lo meteremos todo en una clase de C++.

class Cell
{
public:
enum CELL_TYPE
{
 CT_UNUSED, CT_EMPTY, CT_PAIR, CT_INTEGER, CT_REAL
 , CT_STRING, CT_BOOLEAN, CT_NAME
 , CT_ENVIR, CT_LAMBDA, CT_NATIVE
};
protected:
CELL_TYPE cell_type;

union
{
 ///CT_PAIR data
 struct
 {
  Cell* head;
  Cell* tail;
 };

 ///CT_INTEGER data
 INTEGER integer;

 ///CT_REAL data
 REAL real;

 ///CT_BOOLEAN data
 BOOLEAN boolean;

 ///CT_NAME data
 ///CT_STRING data
 STRING string_idx;

 ///CT_ENVIR
 Environment* environment;

 ///CT_LAMBDA
 Lambda* lambda;

 ///CT_NATIVE
 NATIVE native;


} value;
};

Como se vé, aún quedan por definir muchos tipos, pero la idea está clara: según la celda que tengamos en cell_type, podremos usar unos u otros valores de la unión value. Por ejemplo, un CT_INTEGER puede usar value.integer.

Haciendo un intérprete de LISP (I)

Voy a empezar una serie de entradas en el blog sobre cómo hacer un intérprete de LISP. Va a ser un intérprete minimal. Ni mucho menos compatible con ningún dialecto LISP. Sin embargo, va a permitirnos comprender cómo funciona por dentro el LISP.

Homoiconicidad y celdas

La homoiconicidad significa que el programa va a ser un valor en el propio lenguaje. El LISP es homoicónico. Vamos a definir los valores con los que trabaja el LISP y cómo se representan los programas con ellos.

Un valor en LISP es una celda. Las celdas son inmutables. Es decir, una vez que tienen un valor no lo pueden cambiar. Por otra parte las celdas pueden hacer referencia a otra celdas de esta manera podemos construir listas.

Los tipos de celda con los que vamos a trabajar son:

• Celdas literales. Los enteros, reales, cadenas y booleano. Sería igual con cualquier otro tipo de dato básico que queramos representar. Las llamaremos CT_INTEGER, CT_REAL, CT_STRING y CT_BOOLEAN. Generalmente no se definen todos estos tipos en los LISP normales. Cada una de estas celdas guarda el valor concreto del tipo básico.
• Celdas de nombres. Un nombre es una cadena que identifica un valor. Cada una de estas celdas guarda la cadena con el nombre. Las llamaremos CT_NAME.
• Celda de lista vacía. Es una lista sin elementos. No guarda nada porque una lista vacía es siempre una lista vacía. Las llamaremos CT_EMPTY.
• Celda de par. Esta celda guarda dos referencia a sendo par de celdas. La primera se suele denomina CAR y la segunda CDR. Sin embargo yo prefiero llamarlas cabeza (head) y cola (tail) porque los pares se usan para generar listas. Las llamaremos CT_PAIR.
• Celda de entorno. Referencia a un objeto externo que es un entorno. El entorno es una función de cadenas (nombres) a valores. Los entornos se usan precisamente para averiguar qué valor tiene asignado un nombre. Estas celdas guardan una referencia a este objeto externo. Las llamaremos CT_ENVIR.
• Celdas de forma. Referencia a un objeto externo que es una forma aplicativa. Una forma puede ejecutarse si tenemos argumentos (lo que se denomina aplicar la forma a unos argumentos). Hay diversos tipos de formas que veremos más adelante. Estas celdas guardan una referencia a este objeto externo. Las llamaremos CT_LAMBDA y CT_NATIVE.

Edit: Distingo CT_LAMBDA y CT_NATIVE para hacer las cósas más fáciles luego en el código fuente.

El montículo (heap) y la recolección de basura

El montículo no es más que el conjunto de celdas con el que estamos trabajando. Cualquier celda referenciada estará en el montículo.

El montículo también tiene dos importantes misiones: crear celdas cuando hacen falta y destruirlas cuando no.

Un ejemplo de montículo podría ser.

1. CT_PAIR 2, 3
2. CT_INTEGER 30
3. CT_PAIR 4, 5
4. CT_STRING "hola"
5. CT_EMPTY

La celda 1 representa la lista (30 "hola"). La celda 3 representa la lista ("hola"). La celda 2 representa el valor entero 30. Y así.

Las expresiones

Finalmente cerramos el círculo de la homoiconicidad. Ya hemos visto algunas expresiones que representan listas y enteros. Estas expresiones se denominan expresiones S (S-expressions). Una expresión S es...

• O bien un entero como 30 o 50
• O bien un real como 30.0 o 50.5
• O bien una cadena como "hola" o "adiós"
• O bien un booleano como true o false
• O bien un nombre como hola o adiós
• O bien una lista. Las listas son precisamente una lista entre paréntesis con sus miembros separados por espacios. Ejemplos de listas son: (1 2 3) (a b c) (1 a "hola") (1 (a "hola") false) y la muy importante lista vacía (). Algunas variantes de LISP tienen el nombre nil para esa lista.

Como ya adelantamos las expresiones son valores. De hecho, cada regla de construcción de una expresión se corresponde a una celda. La excepción es la lista que es una cadena de pares. La forma de generar la lista con los pares es mediante binarización.

En algunas variantes de LISP se expresan los pares entre corchetes []. Usaremos esta notación para facilitar ver cómo se convierte una lista a una cascada de pares. Una lista (1 2 3) se representra mediante [1 [2 [3 ()]]]. Ahora sí, cada par se corresponde a una celda.

La celda 1 del montículo de arriba era la lista (30 "hola") que si escribimos como pares sería [30 ["hola" ()] ].

El lenguaje Go

Leo en varios sitios que Google ha publicado un nuevo lenguaje de programación al que ha llamado Go.

Visión preliminar

Las principales características son:

Es de la familia del C, aunque las declaraciones de variables van al revés y los tipos merecen mención aparte. Además, simplifica algo la sintaxis del C quitando cosas que sobraban (como los paréntesis del if).

El diseño del lenguaje se orienta a la compilación rápida. Es lo que más resaltan los autores. A cambio, el lenguaje es muy simple y carece de muchas cosas como excepciones o tipos paramétricos (programación genérica). Tampoco tiene sobrecarga de funciones u operadores. Aunque es un lenguaje orientado a objetos, no tiene herencia.

Usa recolección de basura aunque no es un lenguaje que funciones sobre máquina virtual.

Tiene instrucciones específicas para el paralelismo: canales y forks. Sin embargo, no tiene más soporte. No hay forma de verificar o comprobar que el programa concurrente que escribes va a funcionar.

Algunos de sus tipos de datos predefinidos son complejos: arreglos, cadenas y mapas.

Se usa la capitalización de los identificadores para introducir información semántica (exportado de símbolos).

El sistema de tipos

Merece mención especial el sistema de tipos. Es orientado a objetos, pero no tiene herencia. ¿Cómo puede ser?

Bien, es sorprendente, pero funciona y muy bien. El truco está en usar en vez de un orden parcial de herencia, usa el retículo de subconjuntos. Me explico. Cuando en un lenguaje orientado a objetos como el C++ o el Java decimos

class D : B { }

Estamos dándole dos piezas de información al compilador. La primera es que todos los miembros que tenga B los va a tener D. La segunda es que donde pueda usar B puedo usar D.

Sin embargo, la segunda se puede extraer de la primera. Puedo usar D en B porque D tiene todos los miembros de B. Así pues, si otra clase X tiene todos los miembros de B ¡también podré usarla! Esto es lo que se denomina duck typing.

Otro aspecto interesante del sistema de tipos es que los métodos se definen fuera de los tipos. De esta manera se pueden añadir métodos a tipos ya definidos, de forma similar a los extension methods de C#. Según los autores, esta forma de trabajar es ortogonal (métodos por un lados, composición de la clase por otro) y aumenta tanto el rendimiento como los tiempos de compilación.

Finalmente, y debido a que no hay herencia, han introducido un pequeño truco. Cuando una estructura (o clase sin métodos) usa otro tipo como componente, puede usarse anónimamente de forma que se importan todos sus métodos a la estructura.

type X struct {

Y; //<----

a float;

}

Como X tiene un componente anónimo de tipo Y, todos los miembros de Y pasan a X. Esto se usa en los punteros de forma que todos los miembros del tipo apuntado pasan al puntero. No hace falta entonces usar * ni ->. Me queda por descubrir cómo distingue entre copiar un puntero y copiar el objeto referenciado por el puntero.

De objetos y TADs

Leo desde LtU un ensayo de W.R.Cook que explica por qué un objeto no es un tipo abstracto de datos (TAD o ADT en inglés).

Resumiendo las diferencias sería:

1. Un objeto no necesita tipado estático. De hecho, hay muchos lenguajes orientados a objetos con tipado dinámico. Lo que necesitan los objetos es alguna forma de funciones de orden superior para la vinculación dinámica.
2. Los objetos no soportan operaciones "complejas" que tengan que inspeccionar otros objetos. De hecho, los objetos sólo pueden inspeccionarse a ellos mismos (o, según el lenguaje, a otros de su misma clase). Esto es una desventaja al principio, pero luego permite una mayor escalabilidad.
3. Los TAD permiten extender el comportamiento añadiendo nuevas funcionalidades y operaciones, mientras que los objetos extienden el comportamiento añadiendo nuevas representaciones.

En general, si mi comprensión no ha fallado, los TAD  ocultan la representación y muestran las operaciones. Los objetos muestran la representación y ocultan las operaciones (que pasan a ser parte de la representación via vinculación dinámica).

Buscando el siguiente orden de magnitud

Viendo esta entrevista con John Hughes (creador de QuickCheck) me he quedado pensando sobre el último párrafo.

If you compare Haskell programs to C code or even C++ often, they are about an order of magnitude smaller and simpler. The same is for Erlang, those results are being validated in the industry. Where is the next order of magnitude coming from? I wish I had an answer to that question because it's hard to see almost. When you look at a beautiful Haskell program, how could this be 10 times shorter? But I think we need to be asking ourselves that kind of question. If I had a good idea there, I would spend the rest of my career working on it.

Realmente parece difícil reducir más un programa Haskell, como por ejemplo su versión de quick sort.

qsort [] = []
qsort (x:xs) = qsort (filter (<>= x) xs)

Comparada con la de C...

void qsort(int a[], int lo, int hi) {
{
int h, l, p, t;

if (lo < hi) {
l = lo;
h = hi;
p = a[hi];

do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);

a[hi] = a[l];
a[l] = p;

qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}

¿De dónde va a salir el siguiente orden de magnitud?

Templates y Generics

Programación genérica

La programación genérica se basa en el uso de tipos paramétricos. Esto se consigue diciendo cosas como "una lista de enteros" o "una lista de cadenas". De forma usual esto se escribe

list<int>

list<string>

Generics

Ahora bien, el significado de estos tipos puede ser distinto. En Java (y en parte en C#) lo que se hace es borrar el tipo y usar el tipo objeto.

list<int> ----> list<object>

list<string> -----> list<object>

A cambio, el compilador comprueba los tipos e introduce las conversiones convenientes en cada caso. De esta forma hay seguridad en el uso de los tipos aunque realmente estemos trabajando sobre objetos genéricos. De ahí el nombre de estos tipos: tipos genéricos (generics).

Templates

En C++ los tipos no se borran, lo que se hace es generar un tipo nuevo a partir de un patrón. Así una lista de algo no es un tipo completo en C++ es un patrón. De ahí el nombre: patrones (templates).

list<X> ----> class { void insert(X x) {..} ..}

list<int> ----> class { void insert(int x) {..} ..}

list<string> ----> class { void insert(string x) {..} ..}

Obviamente esto es mucho más pesado para el compilador que requiere crear estos tipos. Por esta razón las compilaciones de C++ son mucho más largas que las de C# o las de Java. Realmente son macros que expanden el código a compilar.

Comparativa

Esta diferencia hace que existan casos no intuitivos. Por ejemplo, en Fabulous Adventures In Coding Eric Lippert nos muestra el siguiente ejemplo en C#.

public class C

{

public static void DoIt<T>(T t) {ReallyDoIt(t);}

private static void ReallyDoIt(string s)

  {System.Console.WriteLine("string");}

private static void ReallyDoIt<T>(T t)

  {System.Console.WriteLine("everything else");}

}

Si llamamos a C.DoIt<string> el compilador de C# borra el tipo (generics, no templates) y cuando llama a ReallyDoIt(t) es un object por lo que el resultado es "everything else".

La parábola de los dos programadores

Es un texto antiguo, pero no tiene desperdicio. Lo he dejado tal y como estaba (tiene algunas faltas de ortografía pero se lo perdono al traductor. Entre otras cosas, no sé quién es):

LA PARABOLA DE LOS DOS PROGRAMADORES


Erase una vez las empresas "AAAA-AUTOMATED ACCOUNTING APPLICATIONS
ASSOCIATION" y la "CCCC-CONSOLIDATED COMPUTERIZED CAPITAL
CORPORATION", desconocidas entre si. Ambas decidieron que necesitaban
el mismo programa para prestar un determinado servicio.

AAAA contrato a un analista-programador, Alan, para que resolviera
el problema.

Por su parte, CCCC decidio encargar el trabajo a un programador
junior,recien contratado para comprobar si era tan bueno como decia.

Alan, que poseia experiencia en la realizacion de proyectos de
programacion dificiles, decidio emplear el metodo PQR de disenyo
estructurado.

En funcion de ello, solicito a su jefe de departamento que nombrase a
otros tres programadores para formar un equipo de programacion. A
continuacion el equipo puso manos a la obra, elaborando cantidad de
informes previos de analisis del problema.

En CCCC, Charles dedico un tiempo a considerar el problema. Sus
companyeros de trabajo observaban que a menudo se sentaba con los pies
sobre su escritorio, mientras bebia cafe. A veces se le veia sentado
frente al terminal,pero su compayero de oficina podia adivinar que en
realidad estaba jugando a marcianitos, por su forma ritmica de
teclear.

A esta alturas, el equipo de AAAA estaba empezando a codificar.
Los programadores dedicaban la mitad de su tiempo a escribir y
recopilar codigos y pasaban el resto del dia reunidos, hablando de las
interfaces entre los diversos modulos.

El companero de oficina de Charles advirtio que este finalmente
habia dejado de jugar a marcianitos. En lugar de ello, su tiempo
transcurria bebiendo cafe con sus pies sobre la mesa y haciedo
garabatos en trozos de papel. Por sus garabatos no se podia decir que
estuviese jugando a "tres en raya" pero tampoco parecian tener mucho
sentido.

Han pasado dos meses. El equipo de AAAA ya ha elaborado el
calendario de implantacion del programa. Dentro de dos meses tendran
la primera version del mismo. Tras un periodo de dos meses mas, para
verificarlo y mejorarlo deberia quedar concluida la version completa
del mismo.

En este momento, el jefe de Charles ya se ha cansado de verle
holgazanear. Decide enfrentarse a el. Pero cuando se dirige a su
oficina se queda sorprendido de verle muy enfrascado, introduciendo
codigos en el terminal. Asi que decide prorrogar el encuentro, hablan
un poco y se marcha. No obstante, empieza a vigilar de cerca a
Charles, para enfrentarse a el en cuanto se le presente la ocasion.
Como en realidad no deseaba tener una conversacion desagradable le
alegra comprobar que Charles parece estar ocupado la mayor parte del
tiempo.

Incluso se le ha visto ir tarde a comer y quedarse a trabajar fuera
de horas de oficina dos o tres dias a la semana.

Transcurridos tres meses, Charles anuncia que ha finalizado el
proyecto, presenta un programa de 500 lineas. El programa esta
escrito con claridad, y una vez verificado, ejecuta todo lo que se le
exigia.

De hecho, posee incluso unos rasgos adicionales que podrian mejorar
en gran medida la rentabilidad del programa. Este se somete a prueba
y, con excepcion de un descuido que se corrige rapidamente, funciona
de manera satisfactoria.

El equipo de AAAA ya ha conlcuido dos de los 4 modulos principales
que configuran su programa. Mientras se elaboran los dos restantes,
aquellos se someten a prueba.

Tres semanas despues, Alan anuncia que ya esta lista la version
preliminar del programa una semana antes de lo previsto. El programa
se somete a prueba.

Los usuarios detectan una serie de fallos y deficiencias, a parte de
los previstos. Como Alan aclara, no hay de que extranyarse. Despues
de todo, se trata de una version preliminar en donde los fallos son
normales.

Transcurridos unos dos meses mas, el equipo ha concluido su version
definitiva del programa. Esta constituida por 2500 lineas de codigo.

(Si esto parece exagerado, pregunte a cualquiera que normalmente da
cursos de informatica en los que se exigen proyectos de programacion.

Es bastante tipico un ratio de 5 a 1 entre el programa mas largo y
el mas corto, y normalmente estos ultimos son los mejores.) Una vez
verificada, parece satisfacer la mayor parte de lo que se pedia.
Contiene un par de omisiones, y el formato de su input de datos es muy
confuso. Sin embargo, la compania decide instalar el programa;
siempre puede instruir al personal de entrada de datos para que lo
hagan en el formato requerido. Se remite el programa a algunos
programadores de matenimiento para que subsanen las omisiones.

Desenlace:

En un principio, el supervisor de Charles se quedo impresionado,
pero a medida que iba leyendo el codigo fuente, se dio cuenta de que
el proyecto era en realidad mucho mas sencillo de lo que habian
pensado.

Ahora parecia claro que no representaba un reto ni siquiera para un
programador principiante. Charles habia hecho cinco lineas de codigo
por dia. Representaba un promedio superior al normal. Pero, teniendo
en cuenta la sencillez del programa no tenia nada de excepcional.

Ademas, su supervisor no olvidaba los meses que habia estado
haciendo el vago.

En la revision salarial siguiente, Charles recibio un aumento igual
a la mitad correspondiente a la mitad de la inflacion correspondiente
a dicho periodo. No se le ascendio de puesto. Al cabo de un anyo
aproximadamente, abandono CCCC desanimado.

En AAAA, Alan recibio felicitaciones por haber concluido el proyecto
en el tiempo previsto. Su jefe echo un vistado al programa. Despues
de hojearlo durante unos minutos, vio que en el se respetaban las
normas de la companyia sobre la programacion estructurada. No
obstante rapidamente desecho la idea de leerse todo el programa;
parecia bastante incomprensible. En este momento se daba cuenta de
que el proyecto era en realidad mucho mas complejo de lo que habia
pensado en un princicpio y felicito a Alan por su trabajo.

Cada programador del equipo habia producido 3 lineas de codigo por
dia. Era un promedio normal, pero, teniendo en cuenta la complejidad
del programa, podia considerarse como excepcional. Se concedio a Alan
un elevado aumento de sueldo y se le ascendio a Analista de Sistemas
en recompensa a su trabajo.

Epilogo:

Se invita al lector a extraer sus propias conclusiones.

Nail W. Rickert.
Departamento de Matematicas,
Estadistica e Informatica.
Universidad de Illinois, Chicago.
(NOVATICA V. XII-67 Programofilia)

Macros vs Funciones

Recapitulando

En el último post dedicado a las macros dije que:

En general queremos proteger los símbolos. Una macro debe ser higiénica y transparente por defecto.

Si queremos definir un símbolo en el entorno de llamada, querremos que un símbolo sea no-higiénico. Usualmente este símbolo deberá ser pasado por argumento para controlar qué se ensucia en el entorno de llamada.

Si queremos usar un símbolo del entorno de llamada, querremos que un símbolo sea opaco. Usualmente este símbolo no deberá ser pasado por argumento porque es posible que ni siquiera exista (caso Windows/Linux).

Esto es exactamente lo mismo que hacemos con funciones. La salvedad es que en las funciones trabajamos con valores (en tiempo de ejecución) mientras que en macros trabajamos con símbolos (en tiempo de compilación). Obviamente, no existe esta distinción en lenguajes homoicónicos como LISP donde la compilación y la ejecución van a la par.

Traducción

Esto significa que existen los mismos conceptos de higiene y transparencia referencial en las funciones y, además, existen unos motivos muy parecidos para tener excepciones a la regla.

Por ejemplo:

En general queremos proteger los símbolos. Una macro debe ser higiénica y transparente por defecto.

En general queremos proteger los valores. Una función debe ser higiénica y transparente por defecto.

Realmente esto es cierto, aunque es muy fácil perder la transparencia en lenguajes como el C/C++. Lo veremos más abajo.

Si queremos definir un símbolo en el entorno de llamada, querremos que un símbolo sea no-higiénico. Usualmente este símbolo deberá ser pasado por argumento para controlar qué se ensucia en el entorno de llamada.

Si queremos modificar un valor en el entorno de llamada, querremos que un valor sea no-higiénico. Usualmente este valor deberá ser pasado por referencia para controlar qué se modifica en el entorno de llamada.

Así pues, opino que existe una analogía entre la higiene y el paso por valor. La no-higiene y el paso por referencia.

Si queremos usar un símbolo del entorno de llamada, querremos que un símbolo sea opaco. Usualmente este símbolo no deberá ser pasado por argumento porque es posible que ni siquiera exista (caso Windows/Linux).

Si queremos usar un valor del entorno de llamada, querremos que ese valor sea accesible. Usualmente este valor no deberá ser pasado por argumento porque es posible que ya podamos acceder a él.

El ejemplo claro es una variable global. Al ser global está en el entorno de llamada. Además, ya podemos acceder a ella por lo que no necesitamos pasarla por argumento. De hecho, es esto lo que hace que la función no sea transparente. Depende de algo que no pasamos por argumentos. Esto es muy común en C/C++ donde hay variables globales, estáticas y argumentos implícitos.

Transparencia en tu macro

Flashback

Vamos a volver atrás en el tiempo a la entrada de Higiene en tu macro. En un punto del texto decía...

Como ejemplo, una macro m definida así:

macro m :=
{
y=3; //Defino la y dentro del código.
f(z);
}

Y usada en un código así:

z=7;
m;
print(y); //Debería dar error, no he definido ninguna y en este código.

Da este resultado:

z=7;
y=3; //Contamino el entorno de fuera desde la macro.
f(z); //Uso la z de fuera en la macro ¿es esto deseable?.
print(y); //Captura la y de la macro en vez de estar sin definir.

Es completamente antihigiénico porque introducimos el símbolo y en el entorno de uso.

En aquella entrada nos dedicamos a la higiene. Es decir, que los símbolos de dentro de la macro no se escapasen fuera. Ahora vamos a pensar en la transparencia referencial: que los símbolos de fuera no me afecten dentro.

Transparencia referencial

Realmente la transparencia referencial es más que los símbolos de fuera no afecten dentro. Significa que nada de lo de afuera va a afectar la macro (igual con funciónes). Por tanto, la macro (o función) sólo podrá depender de los argumentos que se le pasen. Exactamente como una función matemática.

Para saber si una macro (o función) f() es transparente o no, hacemos el siguiente experimento mental:

• Llamo a f() con un valor concreto. Por ejemplo, f(3). Obtengo un resultado R1.
• Supongo que se ejecuta código arbitrario entre medias.
• Llamo a f() con el mismo valor concreto. Por ejemplo, f(3). Obtengo ahora un resultado R2.
• ¿Existe la posibilidad de que el resultado R1 sea distinto al resultado R2?

Si la respuesta es "sí", no es transparente.

En general, queremos transparencia porque nos permite razonar con mayor facilidad sobre lo que hace una macro (o función) El sistema de entornos expuesto en el post de la higiene es automáticamente transparente (gracias al entorno padre=entorno de definición). Ahora bien, ¿es esto deseable?

Deseable opacidad

Si no tenemos transparencia de ningún tipo, cualquier operación que hagamos dentro de una macro (o función) tendrá un significado desconocido. Supongamos

macro m := { y=x*x }

Parece que es hacer y el cuadrado de x. Ahora bien, podría darse el caso de que el uso de m apareciera en el siguiente entorno.

defino * como +

m //Uso la macro

¡Ahora y no es el cuadrado es el doble! Así pues, la opacidad referencial implica usar símbolos cuyo valor o definición puede realizarse luego. Esto es muy peligroso, pero puede ser muy útil.

Imaginemos el siguiente ejemplo donde defino la macro m con dos parámetros.

macro delay(os, ms) :=

{

 static_if(os==windows) Sleep(ms)

 else static_if(os==linux) usleep(ms*1000)

 else error;

}

Para empezar es una macro higiénica (ni el os ni el ms que defino en el entorno local podrán usarse fuera de la macro). Como es macro, se ejecuta en tiempo de compilación. Esto se resalta con el uso de static_if en vez de if a secas. El static_if no genera código, simplemente es como si no se escribiera el código en la rama que no se toma. En ese sentido es como el #if del preprocesador de C/C++.

Para continuar, supongamos transparencia referencial para la macro. Eso quiere decir que todos los símbolos han de tomarse del entorno de definición ¡y eso es un problema! Porque si estamos en Windows, usleep no estará definido y será un error y, si estamos en Linux, Sleep no se encontrará y será un error.

Es decir, que esta macro necesita ser opaca. Pero sólo con con los símbolos Sleep y usleep. No con el símbolo static_if ni con el * que queremos que estén vinculados con los valores del entorno de definición.

Resumiendo

En general queremos proteger los símbolos. Una macro debe ser higiénica y transparente por defecto.

Si queremos definir un símbolo en el entorno de llamada, querremos que un símbolo sea no-higiénico. Usualmente este símbolo deberá ser pasado por argumento para controlar qué se ensucia en el entorno de llamada.

Si queremos usar un símbolo del entorno de llamada, querremos que un símbolo sea opaco. Usualmente este símbolo no deberá ser pasado por argumento porque es posible que ni siquiera exista (caso Windows/Linux).

Lo que nunca me enseñaron: las PEGs

Introducción

Una de las asignaturas que más me gustó de la carrera de informática fue la de procesado de lenguajes. Se dividía más o menos en dos partes. La primera se centraba en los distintos algoritmos que hay de reconocimiento de lenguajes y la segunda en la semántica de ese lenguaje.

La primera parte era muy formal. Muchas matemáticas. La clasificación de los lenguajes de Chomsky. Los algoritmos para reconocer los lenguajes de contexto libre deterministas: expresiones regulares, LL(1), LL(k), LR(1), SLR, LALR, etc. La mayoría de estos algoritmos son complejos. Hay que calcular conjuntos, hacer grafos, transformarlos y aplicar métodos más o menos arduos.

Sin embargo, con el tiempo, he descubierto que no me enseñaron nada sobre las PEGs. Quizás únicamente una breve mención a los analizadores descendentes recursivos. Las PEGs son "gramáticas de expresiones reconocedoras" (Parsing Expression Grammars). La idea es muy simple: Probamos una cosa y, si no podemos, probamos con la siguiente.

La gran diferencia

Para reconocer una cadena como "a" en una entrada como "ac" se compara carácter a carácter. El resultado será que hay una parte reconocida "a" y sobra la "c". Una forma de asegurarnos que no sobran caracteres es añadiendo un indicador de fin de entrada. En este caso la cadena a reconocer sería "a#" y la entrada sería "ac#". Obviamente, no reconocería nada. Este truco permite centrarnos en reconocer sólo lo que se pueda reconocer y dejar sobrantes si fuera necesario.

Generalmente queremos reconocer varias cadenas. Aquí es donde las PEGs son distintas. En una gramática de contexto libre (GCL) las opciones no se ordenan. Las distintas opciones se separan con | en las GCL y se lee más o menos como "o". Es decir, "a" | "ab" sería reconoce "a" o reconoce "ab". Si introducimos la cadena "abc" reconocerá "ab" y sobra "c".

Con las PEGs no es así. Hay que reconocer ordenadamente. Las distintas opciones se separan con / en las PEG y se lee más o menos como "y si no, prueba con". Es decir "a" / "ab" sería prueba "a" y si no, prueba con "ab". Si introducimos la cadena "abc" probará primero con "a" y la reconocerá, descartando probar con "ab". Es decir que reconoce "a" y sobra "bc".

Las consecuencias de este cambio son dobles:

• Dependiendo del orden obtenemos gramáticas distintas. Es decir, "a"/"ab" no es lo mismo que "ab"/"a".
• Nunca hay ambigüegades. Esto es debido a que, si hay dos posibilidades, una estará delante de la otra.

Operadores

La restricción del orden puede parecer muy inconveniente, pero realmente no perdemos mucha expresividad respecto a una CFG. Por ejemplo, todos los operadores unarios de las expresiones regulares pueden expresarse con PEGs mediante estas transformaciones.

R = A*  ===> R = A R / ε

R = A+  ===> R = A R / A

R = A?  ===> R = A / ε

Donde ε es la cadena vacía.

Además, tenemos dos operadores más que surgen de la forma en las que las PEGs se implementan.

Cuando tenemos dos opciones la implementación de la PEG tiene que probar la primera. Si se reconoce, no hay problema. Se consume e ignoramos las otras opciones. Así que para reconocer "a" / "b" en "ac" sería:

"a" / "b"  en "ac"

Opción 1:

"a" en "ac". Coinciden las "a". Avanzo.

"" en "c". Nada más que comprobar. Éxito.

Si no se reconoce, hay que volver atrás (backtracking).

"ab" / "ac" en "acd"

Opción 1:

"ab" en "acd". Coinciden las "a". Avanzo.

"b" en "cd". No coinciden. Fallo.

Vuelvo atrás a "acd" y pruebo opción 2:

"ac" en "acd". Coinciden las "a". Avanzo.

"c" en "cd". Coinciden las "c". Avanzo.

"" en "d". Nada más que comprobar. Éxito.

Esta vuelta atrás tiene que usarse si utilizamos las opciones ordenadas /. Ya que la tenemos, podemos utilizarla en otros casos. Por ejemplo. Supongamos que queremos reconocer todas las palabras (no vacías) formadas por "a" y "b" excepto las que empiecen por "baba". Las palabras formadas por "a" y "b" son ("a" / "b")+. ¿Cómo le quitamos ahora "baba"?

La idea es simple. Intentemos reconocer "baba" y, si la encontramos, fallamos. Si no la encontramos, volvemos atrás y seguimos como si nada. Esta operación la notaremos con el operador prefijo ! La gramática sería:

!"baba" ("a" / "b")+

Si introducimos "babab" reconoceremos "baba" y por tanto, fallamos. No reconocemos la gramática. Si introducimos "babb" no reconocemos "baba" aunque habremos consumido "bab". No pasa nada, volvemos atrás a "babb" y seguimos como si nada.

La misma operación se podría realizar fallando si no reconocemos. En este caso se notaría "&". Por ejemplo, reconocer &"bxx" "b" en "bxxba" tiene éxito, pero sobra "xxba". Es una manera de requerir cierto contexto (las "xx" que siguen a la "b") antes de aceptar (sólo la "b").

Implementación

Existe una última característica de las PEG que las hace infinitamente mejores que las CFG: se pueden programar a mano. Nada de Lex/Yacc. Esto se debe a que las PEG son, ni más ni menos, que los reconocedores descendente recursivos.

Por ejemplo. En C++ una regla R = A B sería algo como:

bool R(POSICION& p)

{

return A(p) && B(p);

}

La regla R = A / B es:

bool R(POSICION& p)

{

POSICION q=p; //Prepara el backtracking

return A(p) || B(p=q);

}

Una regla R=A* es

bool R(POSICION& p)

{

POSICION q=p; //Prepara el backtracking

while(A(q)) p=q;

return true;

}

La regla R = &A B es

bool R(POSICION& p)

{

POSICION q=p; //Prepara el backtracking

return A(q) && B(p);

}

Como se ve, las reglas se programan más o menos directamente con un par de variables bien escogidas. En la realidad es algo más complejo porque queremos informar de errores, construir el AST, etc. Pero también es verdad que en la realidad podemos definir clases y abstraernos de más operaciones. El resultado es que la implementación suele ser directa.

El ataque de las ratas

Al leer la palabra "backtracking" deben haberse encendido todas las luces rojas de la complejidad. El backtracking (o vuelta atrás) es de complejidad exponencial. Esto quiere decir que si introduzco una cadena con un carácter más de longitud el resultado puede tardar el doble en calcularse. Esto es inmanejable en la práctica y el efecto es "se ha quedado colgado".

No hay que asustarse. En la realidad las PEGs se pueden calcular en tiempo lineal. Sí, sí. Lineal, O(n) para los amigos de la notación O de Landau. ¿Y cómo es posible esto? Mediante una técnica que se denomina memoización.

La memoización no es más que guardar en una tabla los resultados que ya conocemos de manera que, antes de calcularlos, busco en la tabla. ¿Que ya están? Pues tengo ya lo que buscaba. ¿Que no están? Pues los calculo y los guardo en la tabla para la próxima. El resultado es que sólo tengo que calcular cada regla en cada posición una única vez. Esto es lo que en diseño de algoritmos se denomina programación dinámica.

Como el número de reglas es fijo y las tablas hash son de complejidad amortizada constante el resultado es que la complejidad sólo depende linealmente de la longitud de la entrada. Es decir, O(n). Bien es verdad que también el consumo de espacio va a ser O(n), pero hoy en día la memoria disponible en los PCs normales permite usar las PEGs sobre ficheros de millones de caracteres.

¿Y lo de las ratas? Bueno, a este tipo de reconocedores descendentes recursivos con memoización se los denomina "packrat" que, aunque mis conocimientos de inglés me dicen lo contrario, me suena a "paquete de ratas".

Edit: Ya lo he descubierto. Podemos traducir "packrat" como "atesorador" ya que coincide la idea de memoizar con la definición de "packrat" que he encontrado en Babylon.

Argumentos y parámetros

Generalmente se usan las palabras "argumento" y "parámetro" de forma intercambiable cuando definimos o llamamos a una función. Para distinguir si es en definición o en llamada usamos los adjetivos "formal" o "actual" (mal traducido del inglés "actual"). Entonces:

int f(int a, int b) //Parámetros o argumentos formales

f(3, 4) //Parámetros o argumentos actuales

Bien. En C++ tienen una notación distinta. Para ellos los "parámetros" son los de la definición y los "argumentos" son los de la llamada. La verdad es que es una tontería usar dos palabras cuando se puede usar una, pero ya es un poco enfermizo llegar a tal grado de eficiencia para un programador.

Covariancia y contravariancia (V)

Funciones virtuales

En el último post de esta serie dije que la siguiente operación no se podía realizar.

pes.crea_mueble(150) // Mal, no sabemos las patas que tiene la silla

Esto puede soslayarse si el programador asume la responsabilidad de actualizar correctamente el estado de la silla entera cuando se modifica únicamente la parte mueble de la misma. Por ejemplo, en el caso anterior el programador puede usar una versión especial de crea_mueble() para las sillas. En esta versión especial puede optar por, por ejemplo, usar cuatro patas por defecto.

Ahora bien, ¿cómo sabe que, aunque sea un puntero a mueble, realmente es una silla? Se usa lo que se llaman funciones virtuales. Una función virtual es aquella cuyo despacho se realiza en función del tipo de objeto apuntado y no en función del tipo de puntero. De esta forma, aunque tengamos un puntero a mueble, si actuamos sobre una silla, se usará la función especial de la silla.

Con esta técnica, y bajo responsabilidad del programador, los punteros de lectura/escritura terminan siendo como los punteros de lectura: covariantes.

Paso por valor

En otro post dije que la herencia no era lo mismo que el subtipado y di un motivo en concreto: el tamaño que ocupan los objetos en memoria. Si usamos punteros (o referencias) a objetos podemos usar la técnica de arriba, pero si nuestro lenguaje es de paso por valor, tenemos un problema.

Supongamos que una función tiene el tipo f: Unit -> A. Esta función no toma ningún argumento (el tipo unit es algo así como el tipo void en C/C++ en este caso) y devuelve un objeto de tipo A. Claro está que podría devolver un subtipo B de A.

Por lo mencionado antes, los lenguajes orientados a objetos no usan realmente la relación de subtipo. Usan la relación de herencia. Eso significa que B puede ser de mayor tamaño que A y aquí surge el problema: ¿cómo sabe la función llamante si f va a devolver un A o algún otro tipo heredado como B? Porque si va a devolver un B va a tener que reservar más memoria que para un A. En caso contrario tendríamos un desbordamiento de buffer (buffer overflow).

Una solución sería pensar que la función tiene que devolver exactamente un A. Esto la haría invariante y que no podríamos cambiar cualquier aparición de f: Unit -> A por otra función g: Unit -> B.

Por otra parte, sabemos que con los punteros (y gracias a las funciones virtuales) no tenemos ese problema. Es decir, que sí podemos cambiar cualquier aparición de f2: Unit -> PA por otra función g2: Unit -> PB.

¡Pero es que es lógico! Pasamos los punteros por valor y el objeto apuntado por referencia. Los punteros son todos del mismo tamaño por lo que no hay problemas de desbordamiento de buffer. Esto es justo lo que hace el C++: permitir la covariancia de funciones sólo para los punteros (y referencias).

Marcando la variancia en los constructores de tipo

La solución de C++ está bastante encorsetada. Sólo permite covariancia para unos tipos predefindos. ¿No podríamos mejorar esto?

Si el programador supiese que, cuando usa un constructor de tipos, el resultado es otro tipo que

1. Va a tener estados consistentes y no va a tener slicing (funciones virtuales)
2. No va a provocar desbordamiento de buffer (mismo tamaño si es paso por valor)
3. No va a tener problemas semánticos (el programador es responsable y sabe lo que se hace).

Entonces podría asegurar que sus constructores de tipos van a ser covariantes o contravariantes y podría anotarlo en el código. Por ejemplo, un contenedor de sólo lectura es covariante.

Esto es lo que hace el lenguaje de programación Scala y las nuevas versiones del C#. Un ejemplo obtenido de aquí es:

//+A significa que es covariante en A

class Stack[+A] { 

//B >: A significa que A es subtipo de B (A<:B)

def push[B >: A](elem: B): Stack[B] = new Stack[B] {
override def top: B = elem
override def pop: Stack[B] = Stack.this
override def toString() = elem.toString() + " " +
Stack.this.toString()
}

def top: A = error("no element on stack")

def pop: Stack[A] = error("no element on stack")

override def toString() = ""
}

object VariancesTest extends Application {

var s: Stack[Any] = new Stack().push("hello");
s = s.push(new Object())
s = s.push(7)
Console.println(s)

}

Comentarios finales

Con esto doy por acabada la serie de variancias. Seguramente surgirá algún tema más que comentar en el futuro, por lo que no tendré ninguna pereza en reabrirla para nuevos posts. 

Las cópulas japonesas

Hoy voy a hacer otro pequeño (o gran) cambio de tema para hablar un poco sobre el idioma japonés. Lo estoy estudiando en mis ratos libres y la verdad es que, por ahora, me está gustando.

Unos de mis mayores calentamientos de cabeza ha sido la cópula. La cópula es similar al verbo "ser" cuando se usa en frases atributivas del tipo "yo soy grande" o "el disco es amarillo".

La cópula japonesa tiene una conjugación (o mejor dicho, declinación porque no se considera verbo) bastante irregular. Se puede ver en las páginas de Tae Kim, en Matsu Kaze o en esta magnífica página de Collin McCulley.

En el siguiente diagrama resumo todo lo que (creo) haber descubierto.

Ahora queda explicarlo: Analizando cómo se obtienen las distintas declinaciones llego a las siguientes conclusiones (que pueden ser incorrectas pero tienen toda la pinta de ser buenas).

1. La cópula es realmente la partícula で (de) seguida del verbo ある (aru=ser). Es decir, que realmente es el verbo ser aunque no lo parezca debido a los metaplasmos que han ocurrido hasta el japonés moderno. Veamos esas transformaciones.
2. Se realizan contracciones y abreviaturas de modo que である (de aru) termina siendo だ (da), じゃ(ja) o incluso や(ya). Hay un interesante mapa donde vemos en qué zonas se usa una u otra abreviatura en la Wikipedia. He puesto en verde discontinuo las transformaciones que señalan estas abreviaturas y contracciones. Nota: Se puede usar である (de aru) pero suena muy académico, frío y oficial. Estas variantes menos usadas están en gris en el diagrama. 
3. La educación (en el sentido de ser respetuoso) es muy importante en el japonés y hay varias maneras de conseguirla. En la cópula tenemos dos: usar la forma ます(masu, es una forma del verbo que lo hace más educado) o usar un verbo más educado como ござる (gozaru=ser, en versión mucho más educada). En el primer caso tenemos であります(de arimasu) o bien でございます(de gozaimasu) según el verbo que usemos. No se usa el verbo ござる (gozaru) sin la terminación ます(masu). En el diagrama, he puesto el fondo en verde cada vez más oscuro según aumenta el grado de educación. He puesto en azul las transformaciones que aumentan el grado de educación.
4. Las contracciones y abreviaturas hacen de であります(de arimasu) la cópula educada usual です(desu).

Siguiendo con el análisis nos encontramos con la explicación a la extraña tabla de la negación donde aparecen siempre, al menos, dos variantes. Las razones que imagino son las siguientes.

1. En vez de la partícula で(de) se usa では(dewa) en la negación (ver esta página para saber el porqué). En el diagrama he puesto en rojo las transformaciones que introducen negación y he enmarcado en rojo las formas negadas de la cópula. Esta partícula se abrevia coloquialmente a じゃ(ja) y coincide con una de las abreviaturas que teníamos (para liar algo la cosa). Así, para negar である (de aru), con la negación del verbo ある(aru) que es ない(nai) y usando la partícula では(dewa) obtengo ではない(dewa nai) o じゃない(janai) coloquialmente. Justo lo que esperábamos viendo las páginas web de arriba. Nota: Se puede usar ではない(dewa nai) pero de nuevo suena oficial, frío y académico.
2. En las formas educadas tenemos una dualidad extra. Al tener el verbo (aru o gozaru) y la terminación ます(masu) podemos o bien negar uno o bien negar el otro. Si dejamos el verbo tal cual y usamos la negación de ます(masu) que es ません(masen) obtenemos ではありません(dewa arimasen) o su versión con ja じゃありません(ja arimasen). Con el verbo supereducado ござる (gozaru) obtenemos ではございません(dewa gozaimasen) y じゃございません(ja gozaimasen).
3. Si negamos primero el verbo obtenemos (ver el punto 1) ではない(dewa nai) o じゃない(janai) pero terminan en い(i) por lo que no son verbos. Sin embargo, el verbo negado  ない (nai) puede volverse a declinar dado que al acabar en い(i) es como si fuera un adjetivo. Una forma de declinar los adjetivos es ¡añadiendo una cópula para hacerlos más educados! Así que usamos la recursividad y añadimos la cópula educada です(desu) a la negación no educada じゃない(ja nai) para obtener el último caso que nos muestra la página:  じゃないです(ja nai desu).

Esto de la recursividad en las cópulas japonesas es curioso porque hay múltiples combinaciones posibles para decir y conjugar lo mismo. De hecho, lo único que hace que se usen ciertas combinaciones y no otras es la frecuencia de uso. Por esa razón Collin McCulley añade unos números que parecen ser los resultados encontrados en Google hace algunos años. Buscando y rebuscando he encontrado un foro en la página de Tae Kim donde han puesto muchas de las combinaciones posibles (se usen realmente o no).