Haciendo un intérprete de LISP (XIX)

En esta penúltima entrada sobre el intérprete LISP voy a hablar sobre los distintos caminos que siguen a partir de nuestro intérprete.

El primer camino (y más usual) es usar el LISP como un lenguaje dedicado. Al ser tan simple hacer un intérprete LISP, se usa en muchísimos programas. Por ejemplo, en AutoCad (el llamado AutoLISP), en Emacs o en Audacity (el Nyquist en honor a Nyquist).

El segundo camino, mucho menos usado, es convertir nuestro intérprete en un LISP estándar. Existen muchos dialectos estandarizados de LISP, pero hay dos que predominan. El Common Lisp y el Scheme.

El Common Lisp

El Common Lisp es el abuelo de los LISP. Recopila añadidos y añadidos desde 1984 cuando se creó. No es un dialecto que busque innovar la estructura del LISP. Simplemente va introduciendo nuevas y nuevas características.

Cada característica, cada nuevo uso que se le quería dar hacía que se introdujeran nuevos tipos de datos, nuevas construcciones y nuevas semánticas. El resultado es que el estándar de Common Lisp es bastante voluminoso (1153 páginas).

Una de estas características es el CLOS que permite usar la programación orientada a objetos en el LISP, además de los paradigmas usuales de programación procedural y funcional usuales del LISP.

El Scheme

Si Common Lisp es la navaja suiza de los LISP, con una característica apropiada para cada momento, Scheme intenta ser un cuchillo muy afilado que sirva para todo. Esta filosofía llevó a los desarrolladores de Scheme a modificar la estructura del LISP.

Esta estructura se cambió en varios sentidos.

1. Una gran simplificación. Por ejemplo, se usa el mismo nombre de espacios para funciones y variables. Tiene menos tipos de datos, etc.
2. La introducción de continuaciones para el control de flujo y el requerimiento de la optimización de llamadas de cola.
3. La introducción de un nuevo sistema de macros sintácticas.
4. La introducción de clausuras y vinculado léxico, en vez de dinámico.

Muchas de estas decisiones han resultado ser muy interesantes. Tanto que se "filtraron" al Common Lisp. Por ejemplo, las clausuras léxicas.

El resultado de esto es que el Scheme es un lenguaje muy fácilmente implementable. Además, como el intérprete es muy pequeño, se puede usar incluso en entornos incrustados.

Como era de esperar, el estándar de Scheme son unas pocas páginas. 

Haciendo un intérprete de LISP (XVIII)

En esta parte de la realización de un intérprete LISP vamos a ver cómo convertirlo en un intérprete de otros lenguajes. Si no de forma completa, sí de manera básica, dando unas pinceladas.

A Lua

El lenguaje Lua es realmente diferente al LISP. La página principal del lenguaje está aquí y existe una interesante entrada en la Wikipedia. A poco que investiguemos el lenguaje nos encontramos con que el tipo de dato fundamental en Lua no es la lista, si no la tabla.

Realmente en LISP ya hemos usado tablas para los entornos. ¿Podremos quitar las listas? La respuesta es sí y muy fácilmente. Basta con realizar las siguientes operaciones:

1. Permitir que los entornos usen como clave cualquier valor y no únicamente cadenas. A partir de ahora son tablas.
2. Representar las expresiones mediante tablas. Para esto se puede ver el MetaLua.
3. Modificar las reglas de evaluación para usar tablas. Ver por ejemplo las metatablas del Lua.

Una lista será ahora una tabla con claves 0, 1, 2, 3... Con este truco, las celdas de tipo CT_PAIR desaparecen de nuestro intérprete. A cambio, abundarán las celdas de tipo CT_TABLE (antiguas celdas de entornos).

Nota: Hay una pequeña diferencia entre un entorno y una tabla. Un entorno puede tener un entorno padre donde se busque una clave no encontrada en él mismo. Generalmente una tabla no tiene estas tablas padre. Nuestras tablas sí las tendrán, ya que las tenemos que usar como entornos también.

Las celdas de tabla mantienen la información en un objeto aparte. Generalmente este objeto será una tabla hash. Las tablas hash son una estructura de datos que no es trivial. Cambian de tamaño, el acceso no es inmediato, hay que mantener la cuenta del factor de carga, etc. Por esta razón habría que implementar una serie de trucos para hacer todo más eficiente. Por ejemplo, el Lua tiene una tabla separada para cuando las claves son números naturales y otra para el resto de accesos.

A Self

Una vez que empezamos a usar tablas surge de forma natural la técnica de guardar en ellas las operaciones que se pueden realizar sobre ellas mismas. De hecho, Lua tiene dos operadores para acceder a tablas. El primero es el punto "." que obtiene el valor bajo una de las claves de la tabla. Por ejemplo, "a.b(c)" busca el valor "b" dentro de la tabla "a" y le aplica los argumentos "(c)".

El otro operador se escribe con dos puntos ":" y es azúcar sintáctico ya que se puede traducir "a:b(c)" por "a.b(a, c)". Es decir, que reutiliza la tabla como primer argumento. Puede verse aquí. Esto significa que usamos la tabla "a" no sólo para buscar la operación "b", sino que también vamos a usar esta tabla como argumento de la operación.

Si siempre nos decantamos por esta segunda opción, pasando la tabla como un argumento implícito (generalmente llamado "self"), lo que tenemos es un lenguaje orientado a objetos puro. En este tipo de lenguajes escribir "a.b(c)" significa "enviar al objeto "a" el mensaje "b" con argumentos (c)". Realmente es igual a lo que escribíamos en Lua "a:b(c)". Esta es la esencia del lenguaje Self.

Para distinguir las tablas a secas de los objetos, en Self se denominan "slots" a las claves de las tablas. Además, existen diversos tipos de slots, aunque no entraremos a discutirlos aquí.

Lo realmente interesante es que Self permite herencia por prototipos. Esto significa que si buscamos una clave en una tabla/objeto y no lo encontramos, hemos de buscar en el objeto prototipo. ¡Pero esto es exactamente lo mismo que buscar en el entorno padre en el caso de los entornos! La única pequeña diferencia de mención es que Self puede tener varios objetos/tablas/entornos padre, ya que permite herencia múltiple.

Otro lenguaje que sigue este esquema de objetos y prototipos es JavaScript.

A Smalltalk

Una vez que empezamos a cambiar lo que ocurre cuando no encontramos una clave/"slot" en un objeto nos lleva a pensar en la siguiente simplificación: ¿para qué buscar en un objeto y, si no está, vamos a otro? ¡Directamente buscamos en el otro! Esta es la idea del uso de clases.

Una clase es un objeto que nos dice qué "slots" tiene otro objeto. Se consideran entonces a las clases como "patrones" de los objetos relacionados con ella. Este sistema tiene una gran ventaja: no se repite información. Sin embargo, esta mejora se consigue a cambio de aumentar la complejidad.

Smalltalk es un lenguaje que hace esta distinción entre objeto y clase. Además, es un lenguaje con muchas sorpresas tanto sintácticas como semánticas. Pero este artículo se está haciendo demasiado largo y le dejo al lector el gozo de investigarlas.

Continuaciones

Definición
La forma usual de escribir una composición de funciones es algo como:

f(g(3))

Para evaluarla, calculamos g(3) y continuamos pasándole el resultado a f(x). Por esa razón podríamos escribirlo como

(λx.f(x))g(3)

A la función λx.f(x) se la denomina la continuación de g(3) en f(g(3)).

Esto tan tonto no es fácil de explicar. Véase por ejemplo, la Wikipedia.

Las continuaciones se suelen usar explícitamente. Es decir, que cuando calculo g(3) le voy a decir cuál es su continuación. Eso significa que g debe aceptar otro argumento que es la continuación.

g(3, λx.f(x) )

Esto es lo que se denomina el estilo de paso de continuaciones (CPS). Aunque, realmente, la f también debería tener su continuación. La llamaremos k.

g(3, λx.f(x, k) )

Obviamente, la k debemos haberla sacado de algún sitio. En princpio es el contexto en el que se usa todo f(g(3)).

Usos

El efecto más interesante del uso del CPS es que las funciones no retornan jamás. No necesitan devolver el resultado ya que lo que hacen es pasárselo como argumento a la continuación. La continuación será otra función que llamará a la siguiente continuación y así hasta que se acabe el programa.

Esta es la razón por la que existe una continuación especial, primitiva, que significa "no hacer nada más" o bien "cálculo acabado". En el caso de la k de arriba, podríamos pensar que es esta continuación inicial. El significado sería entonces: calcula g(3), continúa pasando el resultado a λx.f(x) y continúa acabando el cálculo.

Dicho esto, hay que mencinar que ya hemos usado continuaciones sin saberlo en los lenguajes imperativos como C o Java. Por ejemplo, el "return" de una función es equivalente a ejecutar su continuación inmediatamente. Es decir, salir de la función.

El "break" en los bucles es equivalente a ejecutar la continuación del bucle. De esta forma, se sale del bucle.

Las excepciones que salen de varias funciones y bloques "try" en C++ o Java, son similares a ejecutar, en vez de la continuación normal, la continuación que nos lleva al bloque "catch".

Los lenguajes que cuentan con las continuaciones como valores de primera clase (como Scheme o Ruby) tienen una llamada especial que se denomina "call with current continuation". Esta llamada pasa la continuación de la propia llamada, la continuación actual, a una función pasada como argumento. ¿Qué es la continuación actual? Pues pensemos en algo así como la dirección de retorno de una subrutina o llamada. La única diferencia es que ahora podemos retornar de llamadas, bucles o cualquier otro bloque de código. Esto incluye varios bloques y funciones tal y como hacen las excepciones.

Los usos anteriores son los llamados "hacia delante" ya que salimos de una llamada, bloque, etc. Existe otros usos que son "hacia atrás" y permiten realizar bucles y recursiones.

Pero no seguiremos más por mor de brevedad.

Haciendo un intérprete de LISP (XVII)

El LISP es un lenguaje homoicónico. Es decir, las expresiones son valores en sí. Esto permite trabajar con el código como si fuera dato. Por esa razón he puesto el tag "programación genérica" en todos las entradas del intérprete lisp. En esta entrada vamos a ver qué podemos hacer gracias a esta propiedad.

Carga de ficheros

La carga de ficheros es bien simple. Lo cargamos como dato y, dado que los datos son también código, lo ejecutamos. Existen un gran inconveniente a esta forma de trabajar: Si queremos usar el código varias veces tendríamos que cargarlo y ejecutarlo varias veces. Esto es debido a que podríamos usar diferentes entornos de ejecución cada vez que carguemos el fichero. Al tener los símbolos distintos significados, cada ejecución tendría lugar a diferentes resultados.

Hay varias soluciones a esto.

1. Admitirlo. Esto es lo que se ha llamado siempre incluir ficheros.
2. Usar siempre el entorno global cuando se cargan ficheros.
3. No permitir expresiones que usen nombres del entorno en el fichero a cargar.

En concreto, la tercera solución es muy atractiva. Encerrar el código en algún tipo de construcción de forma que los nombres se extraigan del entorno de uso, no del entorno de carga, nos lleva de forma natural al concepto de macro.

De las funciones a las macros

El gran problema del uso de datos como si fuera código es que perdemos el entorno. Si uso un nombre "x", dependiendo de donde lo use, significará una cosa u otra. Si sé que lo voy a usar inmediatamente está claro que se refiere al entorno actual, pero si voy a atrapar esa "x" en un trozo de dato que voy a usar luego... ¿qué valdrá esa "x" cuando se use? No lo sabemos.

Esta es una de las razones por las que Scheme usa las clausuras sintácticas a la hora de utilizar macros. De esta manera cuando convertimos código en dato también nos llevamos el entorno en los datos. Pero no seguiremos por ese camino. Miremos antes algo más simple. ¿Por qué no ocurren estos problemas con las funciones?

El código que se ejecuta en las funciones lo hace en tres posibles entornos. Esto ya está explicado aquí. Lo interesante de este modelo es que, use donde use cualquier nombre, éste ha de estar definido en el mismo trozo de código un poco más arriba. Tanto en la evaluación de sus argumentos como en la evaluación de la función.

Esto se observa en el siguiente diagrama.

En las funciones los entornos se evalúan donde se escriben, en el sitio de llamada (el entorno de uso). El cuerpo se evalúa donde se escribe también (en el entorno local). El resultado se usa tal cual.

En una macro lo que queremos es evaluar código en el entorno de uso. Tal como hacíamos en la inclusión. Es la parte de la derecha de la figura anterior. Como se observa, se evalúa el código generado en el entorno local fuera, en el entorno de uso. Además, se usan los argumentos sin evaluar. Esto lleva a todos los problemas conocidos de las macros (ver por ejemplo el libro de Paul Graham, On Lisp).

Realmente la evaluación de la macro se hace en un paso especial que se denomina macro expansión. Este paso es especial porque se tiene que ejecutar en tiempo de compilación mientras que la simple evaluación se compila. En nuestro caso, en el que tenemos un intérprete, esta diferencia es únicamente nominal.

Más allá de las macros

Viendo el diagrama, existen otras posibilidades de llamadas compuestas; aparte de las macros y las funciones. Además de las que evalúen algunos argumentos sí y otros no.

La mezcla de macro y función no es usual, pero las FEXPR sí que se ven de vez en cuando.

Haciendo un intérprete de LISP (XVI)

A partir de este punto consideramos el intérprete de LISP como completo en el sentido de que con él es posible evaluar interactivamente. Esto no significa que no podamos seguir añadiendo mejoras. A estas mejoras le dedicaremos los últimos cinco posts, aunque no añadiré ya código para implementarlas.

Cache de celdas y cadenas

Hasta ahora siempre que usábamos una celda de tipo CT_EMPTY, por ejemplo, siempre reservábamos memoria (via CreateEmpty() ). Es una tontería reservar varias veces la celda CT_EMPTY ya que no tiene estado y dos celdas de este tipo son idénticas.

La solución es bien sencilla. CreateEmpty() va a devolver siempre la misma celda. De esta forma ahorramos muchas celdas ya que todas las listas tienen un CT_EMPTY al final. La misma idea se puede usar para CT_BOOL cuando es true y cuando es false. Incluso, se podría usar para los números enteros más usados: el cero, el uno, el dos, etc.

Existe un impedimento para este tipo de técnica. Si queremos añadir a cada celda un localizador que nos diga en qué fichero fuente, en qué línea y en qué columna aparece esa celda; no tendremos más remedio que usar una celda distinta para cada aparición en el código.

En el caso de las cadenas es muy conveniente tener una única tabla de cadenas. De esta forma todas las celdas CT_STRING y CT_NAME no contienen la cadena en sí, sino una referencia a la tabla de cadenas. De esta manera aunque haya cien celdas CT_STRING con la misma cadena, sólo habrá una única copia de la cadena en nuestra tabla de cadenas.

Estas tablas asociativas se denominan comunmente cache.

Recolección de basura

Aún así tenemos el grandísimo problema de que celda que creemos es celda que perdemos. No podemos liberarla una vez no se use. Este problema ya surgió en los años 1960 cuando se creó el LISP. La solución consiste en usar una técnica llamada recolección de basura (garbage collection).

En su forma más simple es tal como se describe en el siguiente diagrama.

En primer lugar seleccionamos unas celdas las cuales sabemos que están siendo usadas. A estas celdas las llamamos el conjunto raíz. Un ejemplo de celda siempre usada es el entorno global. Estas celdas son las marcadas en (a).

En segundo lugar seguimos las referencias a otras celdas. Si una celda que sabemos usada referencia a otra celda, es posible llegar a usar esa celda referenciada y, por tanto, la consideramos usada también. Es lo que hacemos en (b). A este paso se le llama el marcado.

La idea es que las celdas no marcadas no van a poder ser usadas en el futuro porque no existe una referencia a ellas. Estas son las celdas blancas en (c). En este momento es cuando se liberan esas celdas no marcadas. A este paso se le denomina el barrido.

No es difícil averiguar por qué se denomina a este método de recolección de basura "marcado y barrido" (mark and sweep).

Existen muchísimos otros algoritmos de recolección de basura (conteo de referencias, marcado y barrido incremental, por generaciones, paralelo, etc.) No los veremos aquí.