domingo, 29 de noviembre de 2009

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.

miércoles, 25 de noviembre de 2009

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.


lunes, 23 de noviembre de 2009

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.

domingo, 22 de noviembre de 2009

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.

miércoles, 18 de noviembre de 2009

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" ()] ].


domingo, 15 de noviembre de 2009

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.



miércoles, 11 de noviembre de 2009

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).

domingo, 8 de noviembre de 2009

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?

miércoles, 4 de noviembre de 2009

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".


domingo, 1 de noviembre de 2009

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)