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