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.