miniSL parte 4 - Sintaxis

El gran problema que tiene el LISP, desde el punto de vista humano, es su sintaxis uniforme. Por otra parte, esa es su gran ventaja a la hora de implementarlo o extenderlo. Conforme vayamos complicando la sintaxis, y esta sea adecuada, se facilitará la lectura y se dificultará su procesado.

Todo lenguaje de programación se puede reducir a una serie de combinaciones de operadores con sus operandos. En LISP esa combinación la produce la lista.

( operador operando1 operando2 … operandoN )

Si queremos introducir expresiones infijas y prefijas, necesitamos separar la lista por comas. En caso de no hacerlo, tendríamos la siguiente ambigüedad:

( operador 1 + 2 )
( operador 1 [+2] )
( operador [1+2] )

Una vez separada por comas, no hay dificultades en resolver la ambigüedad anterior.

( operador, 1, +2 )
( operador, 1+2 )

Es habitual usar la combinación preponiendo el operador y esa será nuestra sintaxis básica.

operador(1, +2)

Esta sintaxis es similar a las expresiones M del LISP y, al usarla, perdemos algo de la homoiconicidad. Es decir, la representación en memoria se aleja de la representación textual del código.

Mezclando operadores infijos, prefijos y postfijos obtenemos esta gramática informal.

exp             -> infija
infija          -> prefija | infija SIMBOLO infija
prefija         -> postfija | SIMBOLO prefija
postfija        -> primaria | postfija "(" lista_operandos? ")"
primaria        -> ENTERO | CADENA | NOMBRE | "(" exp ")"
lista_operandos -> exp | exp "," lista_operandos

Los SIMBOLOs son cadenas de

 !%&*+-/<=>?^|~

Más adelante estableceremos algunas restricciones sobre los símbolos. Los nombres cadenas de letras, dígitos y subrayado que no empiecen por dígitos. Las cadenas se expresarán entre comillas.

"Escribiremos las cadenas así"

Nada de esto está especificado en la gramática de arriba donde hemos usado los token SIMBOLO, ENTERO, CADENA y NOMBRE en los casos descritos. Por ahora no profundizaré en este aspecto ya que nos interesa saber cómo va a ser el AST, no cómo va a ser el análisis léxico (escaneado).

Todas las operaciones generan una combinación. Eso quiere decir que 1+2 se transforma en +(1,2) y que -7 se transforma en -(7). De esta manera, se consigue uniformidad en la representación pero legibilidad en el código. El resultado es que, tras estas transformaciones, toda la sintaxis se puede describir con cuatro tipos de nodos.

1. Valores literales como 1 u "hola".
2. Nombres como f o x.
3. Combinaciones como f(x, x).
4. Listas para almacenar la lista de operadores de una combinación. Aprovecharemos también para representar listas así [1, "hola", x].

Entonces, cuando escribimos f(1+2), se transforma en f(+(1,2)) y se representa en un árbol sintáctico con los siguientes nodos.

1. Nodo de nombre f.
2. Node de nombre +.
3. Nodo de literal entero 1.
4. Nodo de literal entero 2.
5. Nodo de lista vacía. Esto es la lista [].
6. Nodo de construcción de lista a partir de los nodos 4 y 5. Esto es la lista [2].
7. Nodo de construcción de lista a partir de los nodos 3 y 6. Esto es la lista [1,2].
8. Nodo de combinación a partir de los nodos 2 y 7. Esto es la combinación +(1,2).
9. Nodo de combinación a partir de los nodos 1 y 8. Esto es la combinación f(+(1,2)).

En la siguiente entrada veremos cómo construir el árbol sintáctico usando celdas en un montículo de forma similar a como hicimos en el LISP.

Semántica operacional de continuaciones

He encontrado una semántica operacional para las continuaciones que es muy simple de entender.

Sintaxis

Su sintaxis es la siguiente:


[$$ t::= x \mid \lambda x.t \mid tt \mid callcc \mid \#e $$]

Esto quiere decir que un término será o bien una variable, o bien una abstracción lambda, o bien una aplicación de un término sobre otro, o bien una llamada a call/cc o bien una continuación (con el [$ \# $] delante).

Como se observa, las continuaciones hacen uso de una nueva categoría sintáctica [$ e $]. Esta es la categoría de los términos con hueco. Debido a que vamos a evaluar primero el operador y luego el operando, en la última aplicación de esta categoría requerimos un valor a la izquierda.


[$$ e::= [] \mid et \mid ve $$]

Los valores son los ya conocidos más una continuación.

[$$ v::= \lambda x.t \mid x v_1 ... v_n \mid \#e $$]

Así que, en el fondo, una continuación no es más que una expresión con un hueco. Ese hueco hay que rellenarlo cuando utilicemos la continuación. Para eso hemos de definir primero la semántica.

Semántica

Esta semántica hace uso de los propios términos con hueco. Cuando escribimos [$ e[t] $] lo que queremos decir es un término con hueco [$ e $] rellenado el hueco con el término [$ t $]. En este caso, la regla β queda así:

[$$ e[(\lambda x.t)v] \rightarrow e[ [x \mapsto v] t] $$]

Que no es más que decir: allá donde haya una aplicación de una abstracción sobre un valor, sustitúyela por el término de la aplicación cambiando la variable ligada por el valor. Esta regla es usual en el lambda cálculo, aunque dentro de un término con hueco hecho explícito, así que no comentaré nada más.

El meollo del asunto está en modificar ese término con hueco y para eso usamos call/cc y la continuación.

[$$ e[callcc\ t] \rightarrow e[t (\#e)] $$]
[$$ e[(\#e') v] \rightarrow e'[v] $$]

Lo que hace call/cc es recordar el término con hueco, guardándolo en la continuación. Lo que hace la continuación es volver a ese término con hueco.

Ejemplo

De esta manera, usando las continuaciones, se pueden implementar las sentencias de control que queramos. Por ejemplo, un bucle, si suponemos que tenemos secuencia, variables y condicionales.

[$$ n=0;\ k=callcc\ (\lambda x. x)\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} $$]

Evalúo [$ n=0 $]. Ahora [$ n $] vale [$ 0 $].

[$$ k=callcc\ (\lambda x. x)\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} $$]

Evalúo [$ callcc $]. Es un paso importante porque todo lo que hay alrededor del call/cc pasa a ser la continuación.

[$$ k\ =\ (\lambda x. x)\ (\#\ []\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} )\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} $$]

Evalúo la aplicación de la abstracción lambda con la continuación. Es muy fácil porque es la función identidad por lo que el resultado es la propia continuación.

[$$ k\ =\ (\#\ []\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \}\ )\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} $$]

Ahora [$ k $] vale la continuación  [$ \#\ []\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} $].

[$$ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} $$]

Evalúo el [$ if $] que, al ser cierto, es igual a evaluar su cuerpo.

[$$ print\ n\ ;\ n=n+1\ ;\ k\ 0 $$]

Como [$ n $] valía [$ 0 $], imprimimos un cero.


[$$ n=n+1\ ;\ k\ 0 $$]

Y [$ n $] vale [$ 1 $]

[$$ k\ 0 $$]

Ahora empieza el baile. Debido a que [$ k $] vale la continuación  [$ \#\ []\ ;\ if\ n<5\ \{\ print\ n\ ;\ n=n+1\ ;\ k\ 0\ \} $], evaluamos a:

[$$ (\#\ []\ ;\ if\ n<5\ \{\ print\ n\ ;\ k\ 0\ \})\ 0 $$]

Aplicar la continuación es sustituir toda la expresión por la continuación sustituyendo el hueco por el operando evaluado (ya lo está, es el cero).

[$$ 0\ ;\ if\ n<5\ \{\ print\ n\ ;\ k\ 0\ \} $$]

El cero se ignora en la secuencia y repetimos el bucle con [$ n $] igual a [$ 1 $]. Obviamente, cuando sea [$ 5 $], el cuerpo del [$ if $] no se ejecutará y terminaremos el programa.

Arreglado el LaTeX

Al final he usado MathJax para el LaTeX ya que el anterior sistema parece que ha muerto definitivamente. Ha sido un poco tedioso modificar todas las fórmulas, pero poco a poco creo que están todas bien.

miniSL parte 3 - Celdas

Para cada una de las partes mencionadas anteriormente, tendremos que escribir un programa que tomará una entrada y devolverá una salida.

• Escaneador: Caracteres a tokens.
• Reconocedor: Tokens a AST.
• Generador: AST a código intermedio (o máquina).
• Ejecución: Código intermedio (o máquina) a valores de resultado.

Debido a que vamos a realizar un intérprete muy simple (el paso 3 se omite y la ejecución evalúa directamente el AST) durante ejecución necesitamos trabajar con dos tipos de objetos: el AST y los valores. Usaremos una misma estructura para almacenar ambos tipos: la celda (CELL). La celda es el nombre usual de la unidad de memoria cuando ésta es uniforme. Ayudará en el futuro para la recolección de basura.

Llamaremos valor a los posibles resultados de la evaluación de cierto código (código=AST). En principio, sólo podremos evaluar el código aunque existen valores que son código y se evalúan a ellos mismos: los literales como el entero 3 o la cadena "hola". Las celdas de valor entero serán del tipo INT_VAL y las cadenas STRING_VAL.

Es probable que necesitemos alguna celda especial de gestión del propio intérprete y que no será ni código ni valor (por ejemplo, una celda sin usar UNUSED). También (y coincidiendo con el LISP) tomaremos el constructor de lista (CONS_CTOR) como código y valor, aunque no es literal ya que lo evaluaremos. Así que, por ahora lo que tendría sería la siguiente clasificación de tipos de celdas.

enum CELL_TYPE
{
UNUSED, 

//Literals
INT_VAL, STRING_VAL,

//Value constructors

//Code constructors

//Value and code constructors
CONS_CTOR,
};

Para terminar de rellenar esta lista de tipos de celda necesitamos saber cómo construir código y eso requiere conocer la sintaxis. Por eso la siguiente entrada de esta serie se dedicará a elegir una sintaxis para nuestro lenguaje script.

miniSL parte 2 - Pasos a realizar

Un intérprete de un lenguaje de programación, procede en los siguientes pasos (de forma simplificada).

1. Escaneador (lexer): Leer los caracteres del código fuente y agruparlos en tokens. Los tokens son grupos de caracteres que tienen significado sintáctico. Es usual que el espacio en blanco y los comentarios se ignoren al buscar tokens. También es usual que se realicen ciertas transformaciones como calcular el valor de un número a partir de los caracteres que lo componen.
2. Reconocedor (parser): Usando la sintaxis, reconstruir el árbol sintáctico del código fuente. Este paso es el reconocimiento y, debido a la simplicidad que queremos en nuestra implementación, en él utilizaremos una sintaxis con una gramática muy fácil de reconocer. En concreto, como veremos más adelante, será una sintaxis LL(1).
3. Generación de código: Opcionalmente, se puede transformar el árbol sintáctico abstracto en el árbol objetivo abstracto y generar código a partir de él. Este código podrá ser primero un código intermedio a ejecutar en una máquina virtual o a compilar en código máquina y ejecutar en una máquina real. En nuestro lenguaje miniSL no utilizaremos esta transformación y ejecutaremos directamente el árbol sintáctico por simplicidad.
4. Ejecución: La ejecución del resultado de los pasos anteriores. Esto podrá ser o bien la ejecución del árbol sintáctico, o bien la ejecución en una máquina virtual de un código intermedio generado por el paso 3, o bien la ejecución en una máquina real del código máquina generado por el paso 3. Existe la posibilidad de realizar el paso 3 mientras se ejecuta. Esto ya se comentó en una entrada anterior.

En la siguiente entrada de esta serie empezaremos a pensar en la sintaxis. La sintaxis ha de ser suficientemente simple para poder ser reconocida fácilmente, pero con las características descritas en la primera parte. A partir de la sintaxis decidiremos qué tokens y qué reglas sintácticas vamos a utilizar.

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.

Enlaces de interés

Muy breve esta vez:

¿Cómo ser un (buen) programador?

¿Cómo es el lenguaje de programación ese? 

¿Uso un lenguaje dinámico o estático?

¿Qué tal programador soy?