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.