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.

0 comentarios:

Publicar un comentario en la entrada