Semántica natural de LISP - parte 2 - LISP imperativo

En la primera parte de esta serie homenaje a John McCarthy vimos una semántica de LISP sin permitir la modificación ni de los valores ni de las vinculaciones. Era un LISP funcional. En esta parte vamos a introducir esa posibilidad. Es por tanto un LISP imperativo.

La memoria y los contextos

En el momento que introducimos cambios, hemos de manejar estados. El estado con el que trabajaremos será la memoria [$M$]. Esta memoria será el conjunto libremente generado por [$$M::= \emptyset \mid M,m\Leftarrow c$$] Los identificadores [$m$] son las direcciones de memoria y los objetos sintácticos [$c$] son las celdas con el contenido de esa dirección. Veremos la sintaxis de las celdas más abajo.

Usaremos también los identificadores [$E$] como sinónimos a [$m$]. No son una nueva categoría, son la misma categoría sintáctica. Simplemente, vamos a usar [$E$] cuando hablemos de posiciones de memoria que guardan entornos. Esto nos hará mucho más legibles las ecuaciones y reglas a continuación.

Si bien recuerda el lector de la primera parte, esta definición de [$M$] es muy similar a la definición de contexto [$C$] que teníamos. Esta vez, nuestro contexto no podrá tener valores porque todo hemos de guardarlo en la memoria para que pueda ser modificado. Así pues, nuestro contexto ahora será [$$C::=\emptyset \mid C,x\leftarrow m$$] Donde [$x$] son los identificadores de variable.

Operaciones sobre memoria y contextos

Debido a la similitud entre la sintaxis de memoria y contexto, vamos a dar sus operaciones a la vez. La primera operación es el dominio que nos indica qué posiciones de memoria o qué identificadores de variable están en uso.

En primer lugar, la memoria vacía o el contexto vacío tienen un dominio vacío.

[$$dom(\emptyset)=\emptyset$$]

[$$dom(\emptyset)=\emptyset$$]

Para continuar, el dominio de la memoria o el contexto más una asignación de memoria o vinculación de variable se calcula recursivamente.

[$$dom(M,m\Leftarrow c)=dom(M)\cup\{m\}$$]

[$$dom(C,x\leftarrow m)=dom(C)\cup\{x\}$$]

La siguiente operación que vamos a especificar es la pertenencia a memoria o a contexto. El caso base es cuando la propia asignación o vinculación está en la parte más externa de la memoria o contexto.

[$$(m\Leftarrow c)\in(M,m\Leftarrow c)$$]

[$$  (x\leftarrow m)\in(M,x\leftarrow m)  $$]

El caso recursivo ocurre cuando no se encuentra en esa posición externa.

[$$\frac{m\ne m'\;\;\;\;\;\;  (m\Leftarrow c)\in M}{(m\Leftarrow c)\in(M,m'\Leftarrow c')}$$]

[$$\frac{x\ne x'\;\;\;\;\;\;(x\leftarrow c)\in C}{(x\leftarrow m)\in(C,x'\leftarrow m')}$$]

Finalmente, y dado que estamos hablando de mutaciones de memoria, tendremos que introducir las operaciones de cambio de memoria y de contexto. Es similar a la pertenencia, pero con una comprobación extra por si la dirección de memoria o variable que queremos modificar no está usada y, por tanto, hay que añadirla. Empecemos por esta regla extra.

[$$\frac{m\notin dom(M)}{M\langle m\Leftarrow c\rangle=M,m\Leftarrow c}$$]

[$$  \frac{x\notin dom(C)}{C\langle x\leftarrow m\rangle=C,x\leftarrow m}$$]

 Cuando lo que queremos cambiar sí está en el dominio, hemos de buscarlo y cambiarlo.

[$$(M,m\Leftarrow c)  \langle m\Leftarrow c'\rangle= (M,m\Leftarrow c') $$]	[$$  (M,x\leftarrow m)   \langle x\leftarrow m'\rangle =   (M,x\leftarrow m')    $$]
[$$\frac{m\ne m'\;\;\;\;\;\;  m' \in dom(M)}{  (M,m\Leftarrow c)\langle m'\Leftarrow c' \rangle =   (M \langle m'\Leftarrow c' \rangle ,m\Leftarrow c)  }$$]	[$$\frac{x\ne x'\;\;\;\;\;\; x'\in dom(C)}{(C,x\leftarrow m)\langle x'\leftarrow m'\rangle =   (C \langle x'\leftarrow m'\rangle ,x\leftarrow m)   }$$]

Celdas y entornos

Las celdas van a contener los valores del LISP funcional. Además, dado que las vinculaciones de variables van a poder ser modificadas, también vamos a introducir en ellas a los contextos. Su sintaxis es la que sigue [$$c::= l \mid x \mid (m.m) \mid \lambda^Emm \mid |p| \mid C $$] Es decir, que una celda podrá ser o bien un literal [$l$], o bien una variable [$x$], o bien un par [$(m.m)$], o bien una clausura [$\lambda^Emm$], o bien un valor predefinido [$|p|$], o bien un contexto [$C$]. Recordemos que la [$E$] no es más que una dirección de memoria como las [$m$].

Dentro de los literales incluimos la lista vacía que escribiremos [$()$]. Una lista de contextos es un entorno. La operación más importante en los entornos es la búsqueda de la vinculación de una variable. Lo haremos buscando en el contexto en posición de cabeza de la lista y luego, si no se encuentra, usando la recursión en el resto de la lista. Bastan dos reglas para realizar este procedimiento. 

[$$\frac{E\Leftarrow(m'.E')\in M\;\;\;\;\;\;m'\Leftarrow C\in M\;\;\;\;\;\;x\leftarrow m\in C}{x\leftarrow m\in_M E}$$]

[$$\frac{  E\Leftarrow(m'.E')\in M\;\;\;\;\;\;m'\Leftarrow C\in M\;\;\;\;\;\;x\leftarrow m\notin C \;\;\;\;\;\;  x \leftarrow m \in_M E' }{ x\leftarrow m\in_M E }$$]

Las dos reglas de arriba son muy similares. Primero, en ambas reglas, se comprueba que la dirección de memoria [$E$] sea un par y que su primer campo [$m'$] apunte a un contexto [$C$]. Luego, si encontramos la variable en [$C$], ahí está (primera regla) y, si no la encontramos, buscamos en el resto de la lista [$E'$] que es el llamado entorno padre (segunda regla).

Otra operación muy simple, y que más que nada es una abreviatura, es la introducción de un nuevo contexto en un entorno.[$$\frac{m' \notin dom(M)\cup\{m\}}{M\triangleright E\Leftarrow C\mid E' \triangleright M,m'\Leftarrow C, E\Leftarrow (m',E')}$$] Para empezar, usaremos [$M\triangleright$] a la izquierda y [$\triangleright M'$] a la derecha de un juicio cuando quiera indicar que la memoria [$M$] se cambia y como resultado obtenemos la memoria [$M'$]. En este caso, leemos el consecuente como "dada la memoria [$M$], obtengo el entorno [$E$] al introducir un nuevo contexto [$C$] en el entorno padre [$E'$] y la memoria con estos cambios es todo lo que hay a la derecha del [$\triangleright$]".

Relaciones auxiliares de evaluación

En la primera parte introdujimos un par de relaciones auxiliares de evaluación: la desestructuración o ajuste de patrones y el envoltorio. Hemos de adaptar ambas a la introducción de la memoria. Ahora hemos de explorar la memoria en vez de explorar valores. Todo esto hace las reglas un poco más largas, pero en el fondo son exactamente las mismas.

El ajuste de patrones sigue teniendo tres reglas: para literales (la llamaremos P-LIT), para variables (P-VAR) y para pares (P-PAIR).
   

[$$\frac{m\Leftarrow l\in M\;\;\;\;\;\;m'\Leftarrow l\in M}{C\{m\mid m'\}_M=C}$$]

[$$\frac{m\Leftarrow x\in M\;\;\;\;\;\; x\notin dom(C)}{C\{m\mid m'\}_M=(C,x\leftarrow m')}$$]

[$$\frac{m\Leftarrow (m_1.m_2)\in M\;\;\;\;\;\;m'\Leftarrow (m'_1.m'_2)\in M}{C\{m\mid m'\}_M=  C\{m_1\mid m'_1\}_M   \{m_2\mid m'_2\}_M   }$$]

El envoltorio sigue teniendo sus dos reglas: para la lista vacía (la llamaremos W-EMPTY) y para el par (W-PAIR). Esta vez se complica un poco más porque hemos de acarrear las memorias de una evaluación a la siguiente. De esta forma los cambios en la primera evaluación afectan a la segunda evaluación. 

[$$\frac{m\Leftarrow ()\in M}{M\triangleright E \vdash m \Downarrow m \triangleright M}$$]

[$$\frac{m\Leftarrow (m_1.m_2)\in M\;\;\;\;\;\; M\triangleright E \vdash m_1 \downarrow m_1' \triangleright M_1 \;\;\;\;\;\;    M_1\triangleright E \vdash m_2 \Downarrow m_2' \triangleright M_2 \;\;\;\;\;\;\; m' \notin dom(M_2)  }{  M\triangleright E \vdash m \Downarrow m' \triangleright M_2,m'\Leftarrow(m'_1.m'_2) } $$]

 En definitiva, lo que hace el envoltorio es evaluar los operandos para obtener los argumentos. En el proceso crea una lista de argumentos.


La evaluación

Ya tenemos todo lo necesario para la evaluación. Es exactamente igual que la evaluación en la versión funcional sólo que acarreando memorias de una evaluación a la siguiente y usando entornos en vez de contextos.

 

[$$\frac{m\Leftarrow l\in M}{M\triangleright E\vdash m\downarrow m \triangleright M}$$]

La primera regla, que sigue siendo E-LIT, mira lo que hay en la dirección de memoria [$m$] y, si es un literal [$l$], devuelve la propia dirección de memoria como su resultado. Eso significa que el resultado de evaluar un literal es él mismo.

[$$  \frac{m\Leftarrow x\in M\;\;\;\;\;\; x\leftarrow m'\in_M E}{M\triangleright E \vdash m \downarrow m' \triangleright M}  $$]

Esta segunda regla, E-VAR, mira lo que hay en la dirección de memoria y, si es una variable [$x$], busca su vinculación [$m'$] en el entorno [$E$] y devuelve esa vinculación. En ninguna de estas dos reglas se modifica la memoria.
 

[$$  \frac{\begin{array}{c}m\Leftarrow(m_1.m_2)\in M\;\;\;\;\;\;M\triangleright E\vdash m_1 \downarrow m'_1 \triangleright M_1 \;\;\;\;\;\; m'_1 \Leftarrow |p|\in M_1 \\  M_1 \triangleright E \vdash |p|m_2 \rightarrow_\delta m'_2 \triangleright M' \end{array}}{  M\triangleright E \vdash m \downarrow m' \triangleright M'  }  $$]

La regla E-PRE, que trata con los valores predefinidos, es algo más compleja. Primero, la regla observa que [$m$] apunta a un par [$(m_1.m_2)$] en la memoria. Eso significa que hay una combinación y hemos de evaluarla. Evalúa el operador [$m_1$] y observa que su resultado [$m'_1$] apunta a un valor predefinido [$|p|$]. Además, hemos modificado la memoria al evaluar el operador y hemos de buscar en [$M_1$]. Una vez que sabemos que es un valor predefinido, delegamos toda evaluación a la relación delta [$\rightarrow_\delta$] que se encarga de los valores predefinidos. La especificaremos más adelante.

[$$ \frac{  \begin{array}{c}m\Leftarrow(m_1.m_2)\in M\;\;\;\;\;\;M\triangleright E\vdash m_1 \downarrow m'_1 \triangleright M_1 \;\;\;\;\;\; m'_1 \Leftarrow \lambda^{E_c}m_f m_b\in M_1 \\ M_1 \triangleright E \vdash m_2 \Downarrow m'_2 \triangleright M_2 \;\;\;\;\;\;  M_2 \triangleright E' \Leftarrow \emptyset\{m_f \mid m'_2 \}_{M_2} \mid E_c \triangleright M_3 \;\;\;\;\;\;  M_3 \triangleright E' \vdash m_b \downarrow m' \triangleright M' \end{array}}{ M\triangleright E \vdash m \downarrow m' \triangleright M' } $$]

 La última regla, E-APP, es la más compleja y usa prácticamente todas las relaciones auxiliares vistas hasta ahora. Explicaremos lo que hace paso a paso:

1. Los tres primeros antecedentes son exactamente iguales que los de la regla E-PRE. Es decir, comprobamos que es un par, evaluamos el primer componente y descubrimos que es, en este caso, una clausura con entorno de clausura en la dirección de memoria [$E_c$] con parámetros formales en la dirección de memoria [$m_f$] y el código a ejecutar en la dirección de memoria [$m_b$].
2. A continuación, evaluamos los operandos para obtener los argumentos. Esto es justamente lo que hace la relación de envoltorio. Es el primer antecedente de la segunda fila.
3. Una vez que tenemos los argumentos, usamos ajuste de patrones para generar un contexto en el cual estén vinculadas las variables de los parámetros formales [$m_f$] a los argumentos [$m'_2$]. Esta parte es [$\emptyset\{m_f\mid m'_2\}_{M_2}$].
4. Luego, ese contexto se introduce en un nuevo entorno [$E'$] usando como entorno padre el [$E_c$] para obtener la memoria [$M_3$]. Es lo que hace [$ M_2 \triangleright E' \Leftarrow \emptyset\{m_f \mid m'_2 \}_{M_2} \mid E_c \triangleright M_3 $]
5. Entonces, tenemos en la dirección de memoria [$E'$] el entorno donde evaluar el cuerpo de la clausura y obtener el resultado [$m'$] junto con la memoria final [$M'$]. Es lo que hace el último antecedente.

Para ver cómo funciona todo esto, haremos un ejemplo de evaluación.

Ejemplo de evaluación

Aunque va a ser un ejemplo muy simple, la memoria va a estar bastante llena. Para no liarnos voy a usar como identificadores de memoria los valores de la semántica funcional entre corchetes. De esta forma entendemos mejor qué hay en la dirección de memoria [$m_4$] si en vez de escribir [$m_4$] escribo [$[\lambda^{C_0}((x.y))x]$].

Entonces, nuestra memoria [$M_0$] va a ser la siguiente.

[$[C_0]$]	[$\Leftarrow$]	[$list\leftarrow [\lambda^{(C_0)}xx], car\leftarrow [\lambda^{(C_0)}((x.y))x] $]
[$ [\lambda^{(C_0)}xx] $]	[$\Leftarrow$]	[$ \lambda^{[(C_0)]}[x][x]$]
[$ [x] $]	[$\Leftarrow$]	[$x$]
[$ [\lambda^{(C_0)}((x.y))x] $]	[$\Leftarrow$]	[$\lambda^{[(C_0)]}[((x.y))][x]$]
[$ [((x.y))] $]	[$\Leftarrow$]	[$([(x.y)].[()])$]
[$ [(x.y)] $]	[$\Leftarrow$]	[$([x].[y])$]
[$ [y] $]	[$\Leftarrow$]	[$y$]
[$ [(car\ (list\ 1\ 2))] $]	[$\Leftarrow$]	[$([car].[((list\ 1\ 2))])$]
[$ [car] $]	[$\Leftarrow$]	[$car$]
[$ [((list\ 1\ 2))] $]	[$\Leftarrow$]	[$([(list\ 1\ 2)].[()])$]
[$ [(list\ 1\ 2)] $]	[$\Leftarrow$]	[$([list].[(1\ 2)])$]
[$ [()] $]	[$\Leftarrow$]	[$()$]
[$ [list] $]	[$\Leftarrow$]	[$list$]
[$ [(1\ 2)] $]	[$\Leftarrow$]	[$([1].[(2)])$]
[$ [1] $]	[$\Leftarrow$]	[$1$]
[$ [(2)] $]	[$\Leftarrow$]	[$([2].[()])$]
[$ [2] $]	[$\Leftarrow$]	[$2$]
[$ [(C_0)] $]	[$\Leftarrow$]	[$([C_0].[()])$]

Ahora vamos a querer evaluar la dirección de memoria [$m=[(car\ (list\ 1\ 2))]$] en el entorno [$E_0=[(C_0)]$] y usando la memoria [$M_0$]. Necesitaremos hallar los interrogantes de [$$ M_0\triangleright E_0 \vdash m \downarrow\ ????\ \triangleright\ ????$$] Deberemos proceder con la regla E-APP en la cual encontramos que [$[(car\ (list\ 1\ 2))]\Leftarrow ([car].[((list\ 1\ 2))])\in M_0$] Entonces, [$m_1=[car]$] y hemos de evaluar [$$ M_0 \triangleright E_0 \vdash m_1 \downarrow\ ????\ \triangleright\ ????$$] Hay que aplicar la regla E-VAR en la cual obtenemos como resultado la dirección de memoria [$[\lambda^{(C_0)}((x.y))(x)]$].

A continuación hemos de realizar el envoltorio. Aparcamos E-APP(car). Ahora, como [$[((list\ 1\ 2))]\Leftarrow ([(list\ 1\ 2).[()]) \in M_0$] es un par, hay que entrar en W-PAIR. Nos dice que evaluemos el primer componente del par que es[$[(list\ 1\ 2)]$]. Tendremos que usar E-APP otra vez.

Aparcamos W-PAIR(car) y E-APP(car) para entrar en E-APP(list). Como [$[(list\ 1\ 2)]\Leftarrow ([list].[(1\ 2)]) \in M_0$], la regla E-APP me dice que evalúe el primer componente del par. En este caso [$[list]$]. Aplicando E-VAR obtenemos que el resultado es la celda [$\lambda^{[(C_0)]}[x][x]$] y tengo que entrar en envoltorio otra vez.

Tenemos en suspenso E-APP(list), W-PAIR(car) y E-APP(car). Y estamos trabajando con W-PAIR para envolver [$[(1\ 2)]\Leftarrow ([1].[(2)])\in M_0$]. Esta regla me dice que evalúe el primer componente que por E-LIT es él mismo [$[1]$] y que vuelva a aplicar el envoltorio sobre el segundo componente [$[(2)]$]. Aparco este W-PAIR(1) y voy con W-PAIR otra vez.

En este punto están en suspenso W-PAIR(1), E-APP(list), W-PAIR(car) y E-APP(car). Seguimos trabajando con la memoria [$M_0$] y hemos de aplicar W-PAIR a [$[(2)]\Leftarrow ([2].[()])\in M_0$]. El resultado es que [$[2]$] se evalúa por E-LIT a él mismo y W-EMPTY me devuelve el propio [$[()]$].

Ahora ocurre una cosa muy importante. La regla W-PAIR modifica la memoria. Añade un par en una nueva dirección. El primer componente del par es el resultado de la evaluación del primer componente, que era [$[2]$] y el segundo, el del envoltorio, que era [$[()]$]. Entonces, mi nueva memoria será [$$M_1=M_0,m_0\Leftarrow ([2].[()])$$] y el resultado de W-PAIR es [$$ M_0 \triangleright E_0 \vdash [(2)] \Downarrow m_0 \triangleright M_1$$] Este cambio de memoria es importante porque ahora recuperamos W-PAIR(1) y usa [$M_1$] en vez de [$M_0$].

Nota: Escribo [$m_0$] en vez de [$[(2)]$] porque [$[(2)]$] ya está usado en [$M_0$] y se confundiría. Tenemos dos celdas con el mismo contenido en memoria.

Retomamos W_PAIR(1) y sigue en suspenso E-APP(list), W-PAIR(car) y E-APP(car). La regla W_PAIR vuelve a modificar la memoria. En este caso [$$M_2=M_1,m_1\Leftarrow ([1].m_0)$$] y lo que hemos demostrado es [$$ M_0 \triangleright E_0 \vdash [(1\ 2)] \Downarrow m_1 \triangleright M_2$$].

Retomamos E-APP(list) y sigue en suspenso W-PAIR(car) y E-APP(car). El siguiente antecedente de la regla E-APP es el que realiza el ajuste de patrones. En este caso hemos de ajustar [$\emptyset\{[x]\mid m_2\}_{M_2}$]. Es sencillo usando la regla P-VAR. El ajuste devuelve el contexto [$C_1=x\leftarrow m_2$].

A continuación, la regla E-APP introduce el nuevo contexto [$C_1$] en la memoria. La nueva memoria es [$$M_3=M_2, [C_1]\Leftarrow C_1, [(C_1 C_0)]\Leftarrow ([C_1].[(C_0)]$$] y el nuevo entorno está en [$[(C_1 C_0)]$]. En este nuevo entorno y con esta nueva memoria evaluamos el cuerpo de la clausura que era [$[x]$]. Usamos para ello la regla E-VAR y encontramos que [$x\leftarrow m_2 \in_{M_3} [(C_1 C_2)]$] por lo que el resultado es [$m_2$] con la propia memoria [$M_3$]. Entonces lo que hemos demostrado hasta ahora es que [$$ M_0 \triangleright E_0 \vdash [(list\ 1\ 2)] \downarrow m_2 \triangleright M_3 $$]

Retomemos W-PAIR(car) y mantengamos en suspenso E-APP(car). La regla W-PAIR, tras evaluar el primer componente del par, envuelve el segundo. Usando la regla W-EMPTY obtenemos [$[()]$] como resultado de este envoltorio. A continuación, modifica la memoria incluyendo un nuevo par en [$m_3$] con ambos resultados. Es decir que [$M_4=M_2,m_3\Leftarrow (m_2.[()])$] y hemos demostrado que [$$ M_0 \triangleright E_0 \vdash [((list\ 1\ 2))] \Downarrow m_3 \triangleright M_4$$]

Retomamos, por fin, E-APP(car). Hemos de realizar primero el ajuste de patrones en el cual obtenemos el contexto [$C_2=x\leftarrow [1],y\leftarrow m_1$]. Luego, incluimos un nuevo entorno en la memoria con ese contexto y con entorno padre el de la clausura. [$$M_5=M_4, [C_2]\Leftarrow C_2, [(C_2 C_0)]\Leftarrow ([C_2].[(C_0)])$$] Y, finalmente, evaluamos el cuerpo de la clausura. Es sencillo porque consta únicamente de una variable y aplicamos E-VAR. Demostramos, por fin, que [$$M_0 \triangleright E_0 \vdash [(car\ (list\ 1\ 2))] \downarrow [1] \triangleright M_5$$]

Valores predefinidos y formas especiales

Especificaremos muy pocas formas predefinidas. La más usual en un lenguaje imperativo es la evaluación en secuencia. Usaremos el valor predefinido [$|begin|$] para esta evaluación. Necesitamos tres reglas. La primera dice que la evaluación en secuencia de la lista vacía es la propia lista vacía.[$$\frac{m\Leftarrow ()\in M}{M\triangleright E \vdash |begin|m \rightarrow_\delta m \triangleright M}$$] La segunda regla indica que si la lista a evaluar en secuencia sólo tiene un elemento, el resultado es la evaluación de ese elemento. [$$\frac{m\Leftarrow (m_1.m_2)\in M \;\;\;\;\;\; m_2\Leftarrow () \in M \;\;\;\;\;\; M \triangleright E \vdash m_1 \downarrow m' \triangleright M'}{M\triangleright E \vdash m \rightarrow_\delta m' \triangleright M'}$$]Finalmente, si hay más de un elemento, evaluamos el primero y evaluamos en secuencia el resto.[$$\frac{m\Leftarrow (m_1.m_2)\in M \;\;\;\;\;\; m_2\Leftarrow () \notin M \;\;\;\;\;\; M \triangleright E \vdash m_1 \downarrow m'_1 \triangleright M_1 \;\;\;\;\;\; M_1 \triangleright E \vdash |begin|m_2 \rightarrow_\delta m' \triangleright M'}{M\triangleright E \vdash m \rightarrow_\delta m' \triangleright M'}$$]

Para definir una vinculación usamos el valor predefinido [$|def!|$].[$$\frac{m\Leftarrow (m_1.m_2) \in M \;\;\;\;\;\; m_1 \Leftarrow x \in M \;\;\;\;\;\; M \triangleright E \vdash |begin|m_2 \rightarrow_\delta m' \triangleright M'}{ M\triangleright E \vdash |def!|m \rightarrow_\delta m' \triangleright M' \langle E \Leftarrow x \leftarrow m'\rangle}$$] La relación auxiliar [$M \langle E \Leftarrow x \leftarrow m\rangle$] es la que realmente modifica la memoria con la nueva definición.[$$\frac{E\Leftarrow (m_1.E_2)\in M \;\;\;\;\;\; m_1 \Leftarrow C \in M}{M \langle E \Leftarrow x \leftarrow m\rangle = M\langle M_1 \Leftarrow C \langle x \leftarrow m \rangle \rangle}$$]

Es posible definir el valor predefinido [$|set!|$] que modifica una vinculación preexistente. La dificultad de esta definición estriba en hacerla recursiva (hacia el entorno padre) si no se halla la variable a modificar en el contexto actual.

Semántica natural de LISP - parte 1 - LISP funcional

Como homenaje a McCarthy, voy a dedicar una serie de posts a descubrir la semántica natural del LISP. Empezaremos por un LISP reducido que llamaré LISP funcional en el cual no hay mutaciones de las vinculaciones de variables. Cualquiera que haya leído el SICP reconocerá que ésto se corresponde a la primera parte del libro.

La semántica natural o semántica de paso grande no es más que una relación que a cada programa [$t$] en un contexto [$C$] le proporciona un valor [$v$]. Escribiremos esta relación así [$$C \vdash t \downarrow v$$] y se lee "[$t$] se evalúa a [$v$] bajo el contexto [$C$]". Aunque antes debemos especificar claramente cuáles son las estructuras sintácticas que forman [$t$], [$C$] y [$v$].

Sintaxis

La sintaxis de los programas son términos [$t$] que son a su vez, o bien una variable [$x$], o bien un literal [$l$], o bien un par de términos [$(t.t)$]. Esto se escribe así: [$$t ::= x \mid l \mid ( t . t )$$] Dentro de los literales incluimos la lista vacía [$()$] que permite, junto con el par, formar listas. Una lista [$(1 2 3)$] es realmente [$(1.(2.(3.())))$]. Es decir, el primer componente del par es el término que está en la cabeza de la lista y el segundo componente es otra lista que representa al resto de los términos. Es común llamar a estos componentes "head" y "tail"  (cabeza y cola en inglés) o "car" y "cdr". Estos dos últimos nombres tienen una historia más larga.

Los literales son símbolos como [$1, 53, "hola",$] etc. que tienen un valor en sí mismos. Las variables son símbolos como [$x, y, z,$] etc. que requieren un contexto para saber el valor que representan.

La sintaxis de los valores [$v$] es o bien un término [$t$], o bien una clausura [$\lambda ^C t t$], o bien una forma predefinida [$|p|$]. [$$v::=t\mid \lambda^C tt \mid |p|$$] Escribiremos las formas predefinidas entre barras para distinguirlas de las variables y literales, aunque el símbolo que sea [$p$] puede coincidir con ellos.

Los contextos no son más que una colección de vinculaciones de valores a variables.[$$ C::= \emptyset \mid C,x\leftarrow v$$] Construímos los contextos con el contexto vacío [$\emptyset$] al que le vamos agregando vinculaciones de la forma [$x\leftarrow v$]. Aunque la forma correcta de escribir un contexto sea [$\emptyset, x \leftarrow 5, y \leftarrow 8$], omitiremos el [$\emptyset$].

Operaciones sobre contextos

Vamos a necesitar un par de operaciones para trabajar con los contextos. Son muy simples. La primera es el dominio del contexto [$dom\ C$] que nos dice qué variables se han usado en un contexto. [$$ dom\ \emptyset = \emptyset $$][$$ dom(C,x\leftarrow v)=dom(C)\cup\{x\}$$]

La segunda operación busca una variable en un contexto. Lo escribiremos como una relación de pertenencia [$x\leftarrow v \in C$] para simplificar la lectura. [$$x\leftarrow v\in C,x\leftarrow v$$][$$\frac{x\ne x'\;\;\;\;\;\;x\leftarrow v\in C}{x\leftarrow v\in C,x'\leftarrow v'}$$]La primera línea es una regla tan obvia que lo mismo es difícil de entender: [$x\leftarrow v$] pertenece a [$C,x\leftarrow v$]. La segunda regla dice que [$x\leftarrow v$] pertenece a [$C,x'\leftarrow v'$] si [$x$] es distinta a [$x'$] y [$x\leftarrow v$] pertenece a [$C$]. Si llega un momento que [$C=\emptyset$], no podremos usar ninguna de las dos reglas (y por tanto [$x\leftarrow v$] no pertenecerá).

Ajuste de patrones

Llegará un momento en la evaluación en el cual tendremos que relacionar argumentos con parámetros. La forma más inteligente de hacerlo es usando el ajuste de patrones, también llamado asignación desestructurante. El ajuste de patrones que vamos a ver aquí es muy simple: toma un término y un valor, devolviendo las vinculaciones que deberían tener las variables del término para que se ajuste al valor proporcionado. Por ejemplo. Si quiero ajustar [$x$] y [$3$], lo escribiré así [$\{x\mid 3\}$] y el resultado será que la variable [$x$] ha de vincularse al valor [$3$]. Esta vinculación es la que hemos escrito [$x\leftarrow 3$] en los contextos. Como no tenemos contexto al que añadir la vinculación, lo incluiremos en nuestro ajsute de patrones. El resultado es que el ajuste de patrones es una relación [$C\{t\mid v\}=C$]. El ejemplo de arriba se podría completar entonces con [$$z\leftarrow 8\;\{x\mid 3\}=z\leftarrow 8,x\leftarrow 3$$]Más ejemplos serían [$$z\leftarrow 8\;\{(x\; y)\mid (3\;7)\}=  z\leftarrow 8,x\leftarrow 3,y\leftarrow 7$$][$$\emptyset\{(x y. z)\mid(1 \; (2 \; 3) \; 4 \; 5 \; 6)\}=x\leftarrow 1,y\leftarrow(2\;3), z\leftarrow(4  \;5  \; 6)$$][$$x\leftarrow 5\{x\mid 5\}=???$$] En el último ejemplo no es posible calcular el ajuste de patrones porque [$x$] ya está definida. ¡Incluso si le vamos a dar el mismo valor! De esta manera cada contexto sólo tendrá una única aparición de cada variable.

Las reglas del ajuste de patrones son muy sencillas. En primer lugar, la regla D-LIT dice que los literales han de coincidir.[$$C\{l\mid l\}=C$$] La regla D-VAR modifica el contexto vinculando la variable, que no está definida previamente, al valor.[$$\frac{x\notin C}{C\{x\mid v\}=C,x\leftarrow v}$$] Finalmente, la regla D-PAIR es meramente estructural.[$$C\{(t_1.t_2)\mid(v_1.v_2)\}=C\{t_1\mid v_1\}\{t_2\mid v_2\}$$]

La evaluación

Llega la hora de dar la relación de evaluación [$C \vdash t \downarrow v$] que antes mencionábamos. Son cuatro reglas. La primera, que llamaremos E-LIT, es para saber el valor de un literal. Es muy sencillo porque es él mismo. [$$C \vdash l \downarrow l$$] La segunda (E-VAR) es para saber el valor de una variable. Necesitamos consultar el contexto.[$$\frac{x\leftarrow v \in C}{C \vdash x\downarrow v}$$] La tercera la usaremos para pares cuya cabeza se evalúe a un valor por predefinido. La llamaremos E-PRE. [$$\frac{C\vdash t_0 \downarrow |p|  \;\;\;\;\;\; C\vdash (|p| t_1 \cdots t_n) \rightarrow_\delta v}{C\vdash (t_0 t_1 \cdots t_n)\downarrow v}$$] Aquí hemos usado una relación auxiliar [$C\vdash v\rightarrow_\delta v$] en la que introduciremos la semántica de los valores predefinidos (ver más abajo). Finalmente, la regla E-APP, formaliza el uso de una clausura.[$$\frac{C\vdash t_0 \downarrow \lambda^{C'}t't''  \;\;\;\;\;\; C\vdash (t_1 \cdots t_n) \Downarrow (v_1 \cdots v_n)   \;\;\;\;\;\;  C' \{ t' \mid (v_1 \cdots v_n) \}\vdash t''\downarrow v}{C\vdash (t_0 t_1 \cdots t_n) \downarrow v}$$] Hemos usado el ajuste de patrones en el último antecedente (a la derecha del todo.) También hemos usado una relación auxiliar [$ C\vdash (t_1 \cdots t_n) \Downarrow (v_1 \cdots v_n) $] que llamaremos de "envoltorio" que lo único que hace es evaluar una lista de términos, término a término, para obtener una lista de valores.

Las reglas de esta relación auxiliar de envoltorio son muy simples. Primero, la lista vacía se envuelve a sí misma. [$$C\vdash () \Downarrow ()$$] Y segundo, un par evalúa su cabeza y envuelve el resto. [$$\frac{C\vdash t_1 \downarrow v_1  \;\;\;\;\;\; C\vdash t_2 \Downarrow v_2}{C \vdash (t_1.t_2) \Downarrow (v_1.v_2)}$$] En general podemos ver la relación de envoltorio como una abreviatura de
[$$C\vdash t_1 \downarrow v_1   \;\;\;\;\;\;     C\vdash t_2 \downarrow v_2     \;\;\;\;\;\;  \cdots   \;\;\;\;\;\;   C\vdash t_n \downarrow v_n  $$]  que escribimos [$$ C\vdash (t_1t_2\cdots t_n) \Downarrow (v_1v_2\cdots v_n)$$]

Formas predefinidas

Las formas predefinidas nos pueden servir para trabajar con los literales. Por ejemplo, la suma se puede formalizar así (llamaremos a esta regla P-ADD): [$$\frac{C\vdash (t_1 \cdots t_n)\Downarrow (N_1 \cdots N_n) }{  C\vdash (|+| t_1 \cdots t_n)\rightarrow_\delta \sum_{k=1}^n{N_k}  }$$] Donde los [$N$] mayúsculas han de ser literales de número como el [$3$] o el [$75.82$].

Entre todas las formas es especialmente importante la que genera clausuras. Llamaremos a este valor predefinido[$|\lambda|$] y se define con la regla P-LAMBDA [$$C\vdash (|\lambda| t_1 t_2) \rightarrow_\delta \lambda^Ct_1 t_2 $$] Con esta forma especial podemos definir funciones.

Ejemplos de evaluación

Si usamos un contexto inicial [$$C_0 = lambda \leftarrow |\lambda|, +\leftarrow |+|$$] tenemos suficiente potencia expresiva para calcular el doble de [$3$] (realmente, con lambda y usando la codificación de Church, tenemos la potencia expresiva de un modelo computacional Turing completo). Me he tomado algunas libertades para simplificar la derivación (no he usado la abreviatura del envoltorio y le he dado nombres a los contextos). El resultado es el que sigue (clic para ampliar):

En el contexto inicial podemos incluir más definiciones. Algunas funciones típicas son:[$$car\leftarrow \lambda^{C_0}((x.y))x$$][$$cdr\leftarrow\lambda^{C_0}((x.y))y$$][$$list\leftarrow\lambda^{C_0}xx$$][$$cons\leftarrow\lambda^{C_0}(x y)(x.y)$$] Con este nuevo contexto inicial podemos calcular el segundo elemento de la lista [$(1 2 3)$]. La derivación (omitiendo ya nombres de reglas) es la que sigue:

Hasta aquí por hoy. En la siguiente parte de esta serie permitiremos mutaciones en la vinculación de las variables.

Expresiones dependientes en templates de C++

El código

Existe un aspecto poco conocido a la hora de usar los templates de C++ que son las expresiones dependientes. Éstas dan un susto de vez en cuando a quienes las usan ya que son una mala implementación de las clausuras estáticas. El código ofensivo es el siguiente.

void f() { std::cout<<"A"; }

template<typename T>
struct B {
 void f() { std::cout<<"B"; }
};

template<typename T>
struct D : public B<T> {
 void g()
 {
  f();  //¿Imprime "A" o "B"?
 }
};

int main()
{
 D<char>::g();
}

Si llamamos a D<t>::g(), ¿se imprime "A" o se imprime "B"? Si se imprimiera "A" significa que se está usando el entorno global y si se imprime "B" significa que se está usando el entorno de la estructura D (que hereda de B). Esto está relacionado con la pregunta, ¿cuándo se compila/comprueba D? D se compila/comprueba parte cuando se declara (en el código de arriba donde pone template<typename T> struct D hasta la llave de cierre }; ) y parte cuando se instancia (cuando se hace T=char en D<char>::g() ).

Las clausuras 

Teniendo en cuenta que main() está en el entorno global y la estructura D es el entorno local de la definición de g(), el problema aquí es distinguir entre la clausura dinámica o la clausura estática. La clausura dinámica significa que si no encontramos la definición de un nombre en una declaración, buscamos en el contexto donde se está usando esa declaración (en D<char>::g()) . La clausura estática busca en el contexto donde se está declarando la declaración (en template...).

En los lenguajes basados en entorno, como el LISP o el Scheme, se usa la clausura estática, también llamada clausura léxica. Esto impide comprobar con facilidad si nuestra declaración es correcta porque no tenemos aún los tipos a los que vamos a instanciar (el char). Claro que esto no es problema ni en LISP ni en Scheme porque son lenguajes dinámicos.

La decisión 

La "solución" de los creadores de C++ fue separar la declaración del template en dos partes: la parte dependiente de los parámetros de tipos (los T) y la parte independiente de los mismos. La parte independiente puede comprobarse estáticamente, mientras que la parte dependiente se deja para cuando se conozca el argumento de tipo para la instanciación (el char).

El gran problema es que comprobar significa también buscar las declaraciones de los nombres y, en el caso de arriba, según f() sea del contexto estático o dinámico será la que imprime "A" o imprime "B".

Es fácil ver que la herencia de la clase D es B<T> y, efectivamente, depende de T por lo que no se va a buscar ningún nombre hasta el momento de instanciación ( D<char>::g() ). Antes de la instanciación está la declaración ( desde template<typename T> struct D hasta la llave de cierre }; ) y resulta que el f() que hay dentro de la declaración de g() no depende de T. Eso significa que se busca el nombre ahí, en declaración y el que encuentra es el que imprime "A" ya que el que imprime "B" depende de T a través de la herencia y no lo va a ver hasta la instanciación.

El resultado, contraintuitivo, es que imprime "A". Si tu compilador imprime "B", no se ajusta al estándar. Puedes ver más de esto en el FAQ del C++.

La historia se repite

Todo el lío fue la decisión, desde mi punto de vista errónea, de intentar comprobar el template en declaración, antes de tener los argumentos de tipos para instanciar. En el 90% de los casos al final no puedes comprobarlo en declaración porque casi todo va a depender de T, ¡que para algo se ha puesto! Así que la ganancia de separar las expresiones en dependientes e independientes es mínima y la pena es que se ha introducido la clausura dinámica por la puerta de atrás. La clausura dinámica es recordada amargamente por los programadores de LISP ya que hizo perder veinte años de investigación probando cosas como las FEXPR que al final tuvieron que ser descartadas.

In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained (John McCarthy, History of Lisp)

Si se hubiera usado la clausura léxica, estos problemas no habrían surgido ya que se habría seguido la idea de sustitución (de hecho, esa fue la razón por la que se inventó la clausura léxica) y los costes habrían sido prácticamente los mismos que los que pagamos ahora.



El problema es que ahora estamos atados. De eso hablaré en otra entrada.

Asincronía en C# 5.0

En octubre Eric Lippert empezó una serie en su blog dedicada a la nueva característica de C#: la posibilidad de escribir programas asíncronos. Es un paso lógico tras los cambios producidos en las versiones anteriores de C#.

¿Qué tienen en común las siguientes características de C#? (Todas convenientemente explicadas por Eric)

1. Los iteradores
2. Métodos anónimos
3. LINQ
4. Asincronía

Muy sencillo. Todas estas características se obtienen mediante una transformación sintáctica del código. Es decir. No hay una nueva semántica, sólo transformaciones sintácticas. ¿Y por qué es esto relevante? Porque se habrían evitado todo el follón si hubieran introducido un mecanismo de macros en el lenguaje. No algo tan crudo como el preprocesador de C. Quizás algo como los patrones de C++. O, mucho mejor, algo como las macros del LISP o Scheme.

Si es que al final volvemos al principio.

miniSL parte 1

Hace algún tiempo escribí una serie de entradas sobre cómo hacer un intérprete LISP. El LISP es un lenguaje perfecto para iniciarse en la escritura de lenguajes de script propios, pero no es excesivamente amistoso a la hora de programar. De hecho, jocosamente se le llama "Lots of Insipid, Stupid Parentheses" que traducido es "montones de insípidos y estúpidos paréntesis" y muchas cosas más. La verdad es que, salvo para los fanáticos, el que sólo haya un tipo de parentización en LISP no ayuda visualmente a comprender la estructura del programa.

• En LISP se escribe:  (+ (* 5 2) x)
• Lo que usualmente se escribe como: 5*2+x

El uso de operadores infijos y precedencias despeja la expresión y facilita su lectura. Esto no es gratis. El reconocedor sintáctico (parser) de un lenguaje con operadores infijos y precedencias es algo más complejo. Por eso creo que es muy interesante ver de la manera más simplificada posible cómo funciona un lenguaje script con estas características.

De estas ideas surge miniSL ("mini scripting language" o  "mini lenguaje de script") que, en poco más de mil líneas de código C++, implementa un lenguaje con las siguientes características destacables:

• Sintaxis no trivial con operadores prefijos, infijos y postfijos.
• Sentencias de control de selección (if) y bucle (while).
• Recolección de basura.
• Manejo explícito de entornos (let).
• Funciones anónimas (funciones lambda).
• Bucle REPL.
• Varios tipos de datos básicos: booleano, entero y cadena.
• Distinción entre declaración y modificación de variables.
• Posibilidad de definición de funciones nativas adicionales. 

En la siguiente entrada del blog dedicada a este lenguaje empezaremos con las estructuras de datos que vamos a utilizar.

La cadena dinámica y la cadena estática

La cadena dinámica

Supongamos el siguiente código

f(x) { return g(x) }
g(y) { return h(y) }
h(z) { return z }

Cuando ejecutamos f(3), creamos un entorno con x=3 y evaluamos "return g(x)". Esto es una llamada a g(y) por lo que creamos otro entorno con y=3 y evaluamos "return h(y)". ¡Pero esto no es todo! De alguna manera debemos saber que cuando obtengamos el resultado de "h(y)" hemos de volver al entorno que llamó a "g(y)". Es decir, el entorno inicial con "x=3".

Esto produce una cadena de entornos que se va construyendo conforme el programa se va evaluando. En el caso de antes, cuando estamos en "return z" la cadena sería:

f(3), g(3), h(3)

Esto no es más que la pila de llamadas. Nada nuevo.

La cadena estática

Modifiquemos el código anterior de la siguiente manera.

f(x) { g(y) { h(z) { return z } ; return h(y) } ; return g(x) }

Muchos lenguajes no permiten esta construcción de funciones anidadas. Esto es debido a que en este caso hay que guardar el entorno de clausura de las funciones. Para entender la clausura lo más sencillo es introducir una variable que no esté declarada. Por ejemplo, cambiando la definición de "h" por

h(z) { return z+v }

El resultado es que como no conocemos el valor de "v", no podemos calcular "z+v" y, por ende, "h(z)". Cuando esto ocurre se dice que la expresión está abierta.

La forma de poder calcular lo anterior es cerrando la expresión dándole un valor a "v". Lo más natural es que ese valor esté en un entorno exterior.

{
v=3
...
h(z) { return z+v }
}

De alguna manera hay que disponer del entorno exterior en "h(z)". Si ahora volvemos al ejemplo del inicio de esta sección, podríamos usar en vez de "v", "x".

f(x) { g(y) { h(z) { return z+x } ; return h(y) } ; return g(x) }

¿Cómo sabe ahora "h(z)" el valor de "x" cuando sea llamada? Necesita un enlace, llamado el enlace estático, al entorno de "f(x)".  Sin embargo, las cosas no son tan simples por dos razones.

La primera es que el entorno de "f(x)" va a ser distinto según se cree en una llamada o en otra. Por ejemplo, en "f(3)" vamos a tener el entorno "x=3" y en "f(7)" pues "x=7".

La segunda es que podemos devolver una referencia a la propiar función. Supóngase:

f(x) { g(y) { return y+x } ; return g }

En este caso hemos de agrupar tanto la definición de la función "g" como el entorno en el que se definió en un único objeto. Como este objeto lo que hace es darle un valor a las variables no definidas de la función (en este caso la "x") lo que hace es la clausura de tal función. Por lo tanto a este tipo de objeto se le llama una clausura o una clausura léxica.

Pues bien, la cadena formada por todos los enlaces estáticos que atraviesa las clausuras léxicas de la función actual es la cadena estática.

Ni que decir tiene que la cadena estática es bastante más difícil de implementar que la dinámica. Para esta última basta una pila, pero para la anterior hace falta usar recolección de basura si se quiere usar en toda su capacidad. Es por esta razón que el LISP (el primer lenguaje con recolección de basura) fuera también el primero en implementar la cadena estática (el llamado "lexical scoping" del Scheme).

Haciendo un intérprete de LISP (XX)

Esta es la última entrada sobre cómo hacer un intérprete LISP. Son las conclusiones.

Conclusiones

Empezamos describiendo los valores con los que íbamos a trabajar y dijimos que los guardaríamos en celdas. La idea de los valores elegidos era la homoiconicidad de forma que las propias expresiones del lenguaje fueran valores.

A continuación vimos cómo representar expresiones con celdas. También dijimos que la idea de la evaluación era convertir esas expresiones en otros valores.

Debido a que necesitábamos manipular las celdas empezamos a introducir operaciones sobre celdas.

Como también hacía falta inicializar y crear nuevas celdas, nos dedicamos a definir las operaciones correspondientes en el montículo.

Finalmente, en la quinta parte, nos dedicamos a definir la evaluación. La evaluación se apoyaba en la aplicación de las que teníamos dos variantes.

La primera era la predefinida. Estos eran los valores que llamábamos nativos y de los que dábamos la suma como ejemplo. También introdujimos el REPL como medio de comprobar que realmente la suma funcionaba.

La segunda forma de aplicación era usando una llamada compuesta. Es decir, definida por el usuario. Para eso teníamos las funciones lambda que guardábamos en objetos Lambda.

Para aplicar el objeto lambda realizábamos varios pasos: Creábamos un nuevo entorno local, vinculábamos los argumentos, comprobábamos la aridad y, finalmente, evaluábamos el cuerpo de la función lambda.

Hasta este punto habíamos hablado de entornos, pero no los habíamos definido. En la novena parte los definíamos.

Una vez que teníamos claro cómo usar los objetos lambda, lo único que nos faltaba era crearlos. Para eso introducíamos una nueva nativa.

Aunque mencionamos el REPL anteriormente, no lo habíamos especificado. En la undécima parte lo hacíamos.

En nuestra definición de celdas y entornos habíamos hablado repetidamente de los nombres. En la duodécima parte explicamos cómo usarlos y modificar su contenido. Además, introducimos la nativa que nos saca del REPL y otra que detiene la evaluación.

Cuando todo parecía terminado con las funciones lambda, nos damos cuenta que hace falta un pequeño detalle en nuestra implementación de los entornos. Debemos tener la capacidad de modificar nuestros entornos padre para poder realizar la clausura léxica correctamente.

La décimo cuarta parte es una colección de funciones nativas que posiblemente sean interesantes tener: operaciones con listas, formas especiales, formas especiales con booleanos y operaciones de inspección del estado del intérprete.

En la décimo quinta parte damos por concluida la realización del intérprete añadiendo las rutinas de lectura de expresiones y escritura de valores.

Las últimas cuatro partes (descontando ésta) las dedicamos a pensar en extensiones posibles.

Primero hablamos de mejoras básicas y casi siempre realizadas por un intérprete real: la recolección de basura y cache de celdas.

Luego, de otras extensiones menos básicas como las macros o carga de ficheros en tiempo de ejecución.

También exploramos la posibilidad de modificar la estructura del lenguaje. Vemos cómo podríamos llegar a Lua, Self o Smalltalk.

Finalmente, en vez de modificar el lenguaje, podríamos estandarizarlo. Hablábamos de los dos dialectos principales del lisp: Common Lisp y Scheme.

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í.

Haciendo un intérprete de LISP (XV)

En esta entrega del intérprete LISP vamos a tratar la entrada/salida someramente. Nos dedicaremos a ver únicamente la rutina de lectura de expresiones y la de escritura de valores.

La rutina de lectura

Tampoco vamos a adentrarnos mucho en la rutina de lectura. De hecho, se puede usar una PEG fácilmente para las expresiones S. Tomado, y simplificado, de aquí.

Atom = {Char}+ 
<s-expression> ::= <quote>? Atom / <quote>? '('  <s-expression>* ')' 
<quote>  ::= [']

Realmente lo interesante aquí es que los literales y los identificadores se pueden agrupar como átomos en la gramática y, luego, distinguirlos en la parte semántica.

La rutina de escritura

A diferencia de la rutina de lectura, la escritura debe servir para cualquier valor. Por ejemplo, una función lambda. Además, hemos de intentar formatear algo la salida para que la lectura sea agradable. Es lo que se denomina el prettyprinting.

No vamos a calentarnos mucho la cabeza. Usaremos una indentación para destacar el grado de anidamiento que tengan los valores. Todo eso se puede incluir en una misma rutina de la siguiente forma:

void Cell::Print(std::wostream& o, std::wstring const& indent, int depth)const
{
 if(this==NULL)
  throw std::logic_error("Null cell");

 switch(cell_type)
 {
 case CT_UNUSED:
  o << L"[unused]";
  break;

 case CT_EMPTY:
  o << L"()";
  break;

 case CT_PAIR:
  if(IsList())
  {
   if(depth>0)
   {
    o << L"(";
    Cell const* c=this;
    c->value.head->Print(o, indent+L" ", depth-1);
    c=c->value.tail;
    while(c->IsPair())
    {
     o << L"\n " << indent;
     c->value.head->Print(o, indent+L" ", depth-1);
     c=c->value.tail;
    }
    o << L")";
   }
   else
    o << L"[list]";
  }
  else
  {
   if(depth>0)
   {
    o << L"[\n";
    value.head->Print(o, indent+L" ");
    o << L"\n";
    value.tail->Print(o, indent+L" ");
    o << L"]";
   }
   else
    o << L"[pair]";
  }
  break;

 case CT_INTEGER:
  o << value.integer;
  break;

 case CT_REAL:
  o << value.real;
  break;

 case CT_STRING:
  o << L"\"" << *value.string_idx << L"\"";
  break;

 case CT_BOOLEAN:
  o << (value.boolean? L"[true]" : L"[false]");
  break;

 case CT_NAME:
  o << *value.string_idx;
  break;

 case CT_ENVIR:
  o << L"[envir " << (void*)this;
  if(depth>0)
  {
   o << L"\n";
   value.environment->Print(o, indent+L" ", depth-1);
  }
  o << L"]";
  break;

 case CT_LAMBDA:
  if(depth>0)
  {
   o << L"[lambda " << (void*)this << L" ";
   value.lambda->Print(o, indent+L" ", depth-1);
   o << L"]";
  }
  else
   o << L"[lambda " << (void*)this << L"]";
  break;

 case CT_NATIVE:
  o << L"[native " << (void*)this << L"]";
  break;
 }
}

En las celdas lambda y entorno delegamos al propio objeto, pero las rutinas de impresión son muy similares.

Con esto hemos acabado la parte inexcusable del LISP. A partir de aquí dedicaremos las siguientes entradas a extensiones y modificaciones. Empezaremos por la más necesaria: la recolección de basura, ya que hasta ahora creábamos celdas pero no las destruíamos.

Haciendo un intérprete de LISP (XIV)

En esta parte de la serie sobre el intérprete LISP vamos a poner el código de algunas funciones nativas que pueden ser útiles.

Operaciones de lista

Tendríamos por ejemplo

Cell& FOL_Cons(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty() || !args.GetTail().GetTail().IsEmpty())
  throw std::runtime_error("Cons needs two arguments");

 Cell& head=heap.Evaluate(args.GetHead(), envir);
 Cell& tail=heap.Evaluate(args.GetTail().GetHead(), envir);

 if(!tail.IsList())
  throw std::runtime_error("Cons needs a list as second argument");

 return heap.CreatePair(head, tail);
}

Cell& FOL_Car(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Car requires one arguments");

 Cell& head=heap.Evaluate(args.GetHead(), envir);
 return head.GetHead();
}

Cell& FOL_Cdr(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Cdr requires one arguments");

 Cell& head=heap.Evaluate(args.GetHead(), envir);
 return head.GetTail();
}

Cell& FOL_Second(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Second requires one arguments");

 Cell& head=heap.Evaluate(args.GetHead(), envir);
 return head.GetTail().GetHead();
}

Cell& FOL_Third(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Third requires one arguments");

 Cell& head=heap.Evaluate(args.GetHead(), envir);
 return head.GetTail().GetTail().GetHead();
}

Cell& FOL_Nth(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty() || !args.GetTail().GetTail().IsEmpty())
  throw std::runtime_error("Nth requires two arguments");

 INTEGER at=heap.Evaluate(args.GetHead(), envir).GetInteger();
 Cell& list=heap.Evaluate(args.GetTail().GetHead(), envir);
 return list.ListIdx(at);
}

Cell& FOL_Length(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Length requires one arguments");

 Cell& list=heap.Evaluate(args.GetHead(), envir);
 return heap.CreateInteger(list.ListLength());
}

Cell& FOL_List(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty())
  return heap.CreateEmpty();

 return heap.CreatePair(  heap.Evaluate(args.GetHead(), envir)
  , FOL_List(heap, args.GetTail(), envir)  );
}

Cell& R_Append(Heap& heap, Cell& list1, Cell& list2)
{
 if(list1.IsEmpty())
  return list2;

 return heap.CreatePair( list1.GetHead(), R_Append(heap, list1.GetTail(), list2) );
}

Cell& FOL_Append(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty() || !args.GetTail().GetTail().IsEmpty())
  throw std::runtime_error("Append requires two arguments");

 Cell& list1=heap.Evaluate(args.GetHead(), envir);
 Cell& list2=heap.Evaluate(args.GetTail().GetHead(), envir);

 return R_Append(heap, list1, list2);
}

Cell& FOL_Reverse(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Reverse requires one arguments");

 Cell* r=&heap.CreateEmpty();
 for(Cell* p=&heap.Evaluate(args.GetHead(), envir); p->IsPair(); p=&p->GetTail())
  r=&heap.CreatePair( p->GetHead(), *r );

 return *r;
}

Formas especiales

Algunas posibles son

Cell& FOL_Lambda(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty())
  throw std::runtime_error("Lambda needs two arguments at least");

 Cell* params=&args.GetHead();
 Cell* p;
 for(p=params; p->IsPair(); p=&p->GetTail())
  if(!p->GetHead().IsName())
   throw std::runtime_error("Binding a non-name");

 if(!p->IsEmpty())
  throw std::runtime_error("Lambda needs a list as first argument");

 return heap.CreateLambda(*new Lambda(*params, args.GetTail(), envir));
}


Cell& FOL_Defun(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty())
  throw std::runtime_error("Defun needs three arguments at least");

 Cell& lambda=FOL_Lambda(heap, args.GetTail(), envir);
 envir.GetEnvironment().Bind(heap, *args.GetHead().GetName(), lambda);
 return lambda;
}

Cell& FOL_Quote(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Quote needs one single argument");

 return args.GetHead();
}


Cell& FOL_SetQ(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty())
  throw std::runtime_error("SetQ needs two arguments at least");

 if(!args.GetHead().IsName())
  throw std::runtime_error("SetQ requires a name as fist argument");

 Cell& r=heap.EvaluateInSequence(args.GetTail(), envir);
 envir.GetEnvironment().ChangeBond(heap, heap.GetStringFromPool(*args.GetHead().GetName()), r);
 return r;
}

Cell& FOL_Define(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty())
  throw std::runtime_error("Define needs two arguments at least");

 if(!args.GetHead().IsName())
  throw std::runtime_error("Define requires a name as fist argument");

 Cell& r=heap.EvaluateInSequence(args.GetTail(), envir);
 envir.GetEnvironment().Bind(heap, *args.GetHead().GetName(), r);
 return r;
}

Cell& FOL_Let(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty())
  throw std::runtime_error("Let needs two arguments at least");

 Cell& envcell=heap.CreateEnvironment(&envir);
 Environment& newenv=envcell.GetEnvironment();

 //Bind to environment
 for(Cell* qb=&args.GetHead(); qb->IsPair(); qb=&qb->GetTail())
 {
  Cell& binding=qb->GetHead();
  if(binding.IsEmpty() || binding.GetTail().IsEmpty())
   throw std::runtime_error("Bindings must have two elements at least");
  
  newenv.Bind(heap, *binding.GetHead().GetName(), heap.EvaluateInSequence(binding.GetTail()
   , envir)); // HERE!
 }

 //Evaluate in new environment
 return heap.EvaluateInSequence(args.GetTail(), envcell);
}

Cell& FOL_LetInSeq(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty())
  throw std::runtime_error("Let* needs two arguments at least");

 Cell& envcell=heap.CreateEnvironment(&envir);
 Environment& newenv=envcell.GetEnvironment();

 //Bind to environment
 for(Cell* qb=&args.GetHead(); qb->IsPair(); qb=&qb->GetTail())
 {
  Cell& binding=qb->GetHead();
  if(binding.IsEmpty() || binding.GetTail().IsEmpty())
   throw std::runtime_error("Bindings must have two elements at least");
  
  newenv.Bind(heap, *binding.GetHead().GetName(), heap.EvaluateInSequence(binding.GetTail()
   , envcell)); // HERE!
 }

 //Evaluate in new environment
 return heap.EvaluateInSequence(args.GetTail(), envcell);
}

Cell& FOL_Do(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty() || args.GetTail().GetTail().IsEmpty())
  throw std::runtime_error("Do needs three arguments at least");

 Cell& envcell=heap.CreateEnvironment(&envir);
 Environment& newenv=envcell.GetEnvironment();

 //Initial bind to environment
 for(Cell* qb=&args.GetHead(); qb->IsPair(); qb=&qb->GetTail())
 {
  Cell& binding=qb->GetHead();
  if(binding.IsEmpty() || binding.GetTail().IsEmpty())
   throw std::runtime_error("Bindings must have two elements at least");
  
  newenv.Bind(heap, *binding.GetHead().GetName(), heap.Evaluate(binding.GetTail().GetHead()
   , envir)); // HERE!
 }

 //Loop
 Cell* r=NULL;
 while(heap.Evaluate(args.GetTail().GetHead(), envcell).GetBoolean())
 {
  r=&heap.EvaluateInSequence(args.GetTail().GetTail(), envcell);

  //Update
  for(Cell* qb=&args.GetHead(); qb->IsPair(); qb=&qb->GetTail())
  {
   Cell& binding=qb->GetHead();
   heap.EvaluateInSequence(binding.GetTail().GetTail(), envcell);
  }
 }

 return r==NULL ? heap.CreateEmpty() : *r;
}

Cell& FOL_DoInSeq(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty() || args.GetTail().GetTail().IsEmpty())
  throw std::runtime_error("Do* needs three arguments at least");

 Cell& envcell=heap.CreateEnvironment(&envir);
 Environment& newenv=envcell.GetEnvironment();

 //Initial bind to environment
 for(Cell* qb=&args.GetHead(); qb->IsPair(); qb=&qb->GetTail())
 {
  Cell& binding=qb->GetHead();
  if(binding.IsEmpty() || binding.GetTail().IsEmpty())
   throw std::runtime_error("Bindings must have two elements at least");
  
  newenv.Bind(heap, *binding.GetHead().GetName(), heap.Evaluate(binding.GetTail().GetHead()
   , envcell)); // HERE!
 }

 //Loop
 Cell* r=NULL;
 while(heap.Evaluate(args.GetTail().GetHead(), envcell).GetBoolean())
 {
  r=&heap.EvaluateInSequence(args.GetTail().GetTail(), envcell);

  //Update
  for(Cell* qb=&args.GetHead(); qb->IsPair(); qb=&qb->GetTail())
  {
   Cell& binding=qb->GetHead();
   heap.EvaluateInSequence(binding.GetTail().GetTail(), envcell);
  }
 }

 return r==NULL ? heap.CreateEmpty() : *r;
}

Cell& FOL_DoList(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty())
  throw std::runtime_error("DoList needs one arguments at least");

 Cell& envcell=heap.CreateEnvironment(&envir);
 Environment& newenv=envcell.GetEnvironment();

 //Check the binding
 Cell& binding=args.GetHead();
 if(binding.IsEmpty() || binding.GetTail().IsEmpty())
  throw std::runtime_error("Bindings must have two elements at least");

 //Loop
 Cell* r=NULL;
 for(Cell* list= &heap.EvaluateInSequence(binding.GetTail(), envir); list->IsPair(); list=&list->GetTail())
 {
  newenv.Bind(heap, binding.GetHead().GetName(), list->GetHead());
  r=&heap.EvaluateInSequence(args.GetTail(), envcell);
 }

 return r==NULL ? heap.CreateEmpty() : *r;
}

Operaciones y formas especiales con booleanos

Cell& FOL_Boolean_And(Heap& heap, Cell& args, Cell& envir)
{
 for(Cell* qa=&args; qa->IsPair(); qa=&qa->GetTail())
  if(!heap.Evaluate(qa->GetHead(), envir).GetBoolean())
   return heap.CreateBoolean(false);

 return heap.CreateBoolean(true);
}

Cell& FOL_Boolean_Or(Heap& heap, Cell& args, Cell& envir)
{
 for(Cell* qa=&args; qa->IsPair(); qa=&qa->GetTail())
  if(heap.Evaluate(qa->GetHead(), envir).GetBoolean())
   return heap.CreateBoolean(true);

 return heap.CreateBoolean(false);
}

Cell& FOL_Boolean_Not(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || !args.GetTail().IsEmpty())
  throw std::runtime_error("Boolean not needs one single argument");

 return heap.CreateBoolean(!heap.Evaluate(args.GetHead(), envir).GetBoolean());
}

Cell& FOL_Boolean_If(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty() || args.GetTail().IsEmpty() || args.ListLength()>3)
  throw std::runtime_error("Lambda needs two or three arguments");

 if(heap.Evaluate(args.GetHead(), envir).GetBoolean())
  return heap.Evaluate(args.GetTail().GetHead(), envir);

 return args.GetTail().GetTail().IsEmpty() ? heap.CreateEmpty()
  : heap.Evaluate(args.GetTail().GetTail().GetHead(), envir);
}

Otras funciones

Cell& FOL_ProgN(Heap& heap, Cell& args, Cell& envir)
{
 Cell* r=&args;
 for(Cell* qa=&args; qa->IsPair(); qa=&qa->GetTail())
  r=&heap.Evaluate(qa->GetHead(), envir);
 return *r;
}

Cell& FOL_Prog1(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty())
  return args;

 Cell& r=heap.Evaluate(args.GetHead(), envir);
 for(Cell* qa=&args.GetTail(); qa->IsPair(); qa=&qa->GetTail())
  heap.Evaluate(qa->GetHead(), envir);

 return r;
}

Cell& FOL_Eval(Heap& heap, Cell& args, Cell& envir)
{
 if(args.IsEmpty())
  throw std::runtime_error("The evaluator needs one argument at least");

 return heap.Evaluate(heap.Evaluate(args.GetHead(), envir), envir);
}

Cell& FOL_Print(Heap& heap, Cell& args, Cell& envir)
{
 if(heap.GetPrintOutput()!=NULL)
  for(Cell* qa=&args; qa->IsPair(); qa=&qa->GetTail())
   heap.Evaluate(qa->GetHead(), envir).Print(*heap.GetPrintOutput());

 return heap.CreateEmpty();
}

Realmente podríamos seguir así creando bibliotecas y bibliotecas de funciones.

Haciendo un intérprete de LISP (XIII)

En la última entrada introducimos SetQ. Este SetQ es distinto a los del LISP usual en dos aspectos. El primero está relacionado con la capacidad que tiene el SetQ usual del LISP para modificar varios símbolos a la vez. El segundo, sin embargo, sí que es importante ya que está relacionado con la clausura léxica.

Inspeccionando el estado del intérprete

Vamos a introducir unas funciones nativas para inspeccionar el montículo y los entornos. Usualmente esto se hace en LISP con órdenes (commands). De hecho, la salida del intérprete con Quit también suele ser una orden pero, para mantenerlo simple todo, usaremos funciones nativas.

Para inspeccionar el montículo usaremos esta función nativa:

Cell& FOL_Heap(Heap& heap, Cell& args, Cell& envir)
{
 if(!args.IsEmpty())
  throw std::runtime_error("Heap needs no arguments");

 heap.Print(std::wcout);

 return args;
}

Para inspeccionar los entornos usaremos esta función nativa:

Cell& FOL_Envir(Heap& heap, Cell& args, Cell& envir)
{
 INTEGER depth=args.IsEmpty() ? 0 : heap.Evaluate(args.GetHead(), envir).GetInteger();
 Cell* e=&envir;
 while(depth>0)
 {
  --depth;
  Cell* parent=e->GetEnvironment().GetParent();
  if(parent!=NULL)
   e=parent;
 }

 return *e;
}

Esta última función toma un argumento opcional que indica qué nivel de entorno padre queremos inspeccionar.

Inspeccionando entornos padre

Lo veremos con un ejemplo. Definimos esta función:

> (setq f (lambda (x) (envir x)))

<lambda 003A9AD0 <envir 003A6828> (x)
  ((envir
    x))>

Luego, la usamos:

> (f 0)

<envir 003A9438>= <envir
 (x
  0)
>

El entorno donde se evaluó (envir 0) era el que tenía definido únicamente la x. El resto de símbolos está definido en el entorno padre.

> (f 1)

<envir 003A6828>= <envir
 (add
  <native 003A6930>)
 (envir
  <native 003A6A48>)
  ...

Omito el resto de símbolos. Como ya hemos visto, cuando un símbolo no se encuentra en un entorno, se recurre al entorno padre.

El problema de setq

El problema de setq radica en que, tal como está, sólo modifica el entorno local. Incluso cuando el símbolo a modificar esté en un entorno padre. En el caso de las funciones este entorno padre es la clausura léxica.

> (setq f (lambda (x) (setq y 3) (envir x)))

<lambda 003A74A0 <envir 003A6828> (x)
  ((setq
    y
    3)
   (envir
    x))>

> (f 0)

<envir 003AA810>= <envir
 (x
  0)
 (y
  3)
>

Sin embargo, si predefino el símbolo "y", no obtengo el resultado deseado.

> (setq y 5)

5

> (f 0)

<envir 003AA810>= <envir
 (x
  0)
 (y
  3)
>

> y

5

Hay que modificar el comportamiento de setq para que actúe no sólo en el entorno local. También debe modificar los entornos padre si el símbolo a modificar está allí.

Cambiando el vínculo

Introducimos un nuevo método en los entornos. Buscaremos en los entornos padre y modificaremos el símbolo en el entorno donde lo encontremos. Si no lo encontramos, lo definimos localmente.

Cell& Environment::ChangeBond(Heap& heap, STRING name, Cell& cell)
{
 //Modifiy if already defined.
 Environment* current=this;
 while(current!=NULL)
 {
  BONDMAP::iterator i=current->m_Bonds.find(name);
  if(i!=current->m_Bonds.end() && i->second!=NULL)
  {
   i->second=&cell;
   return cell;
  }

  //Go to parent's (if it exists)
  if(current->m_Parent==NULL)
   break;

  current=&current->m_Parent->GetEnvironment();
 }

 //Define if not defined.
 m_Bonds[name]=&cell;
 return cell;
}

El resultado es que ahora podemos hacer lo que queríamos hacer: modificar símbolos del entorno de definición.

> (setq f (lambda (x) (setq y 3) (envir x)))

<lambda> (x)
((setq
 y
 3)
(envir
 x))>

> (setq y 5)

5

> (f 0)

<envir 003AA810>= <envir
 (x
  0)
>

> y

3

>