Semántica formal para clausuras léxicas

El lambda cálculo es una herramienta asombrosa. En pocas líneas puedes definir un modelo de computación. Esta simplicidad permite transmitir ideas de manera formal con relativa facilidad. Por esa razón estuve pensando cómo explicar la clausura léxica de manera matemática.

El lambda cálculo con semántica natural

Empezaré por el lambda cálculo con semántica natural (también llamada operacional de paso grande). La sintaxis del lambda cálculo es muy sencilla. [$$t::=x\mid tt\mid \lambda x.t$$] Este tipo de definiciones sintácticas se leen así:

[$t::=$]	Un término (o expresión) es
[$x$]	o bien una variable
[$tt$]	o bien una aplicación de un término sobre otro
[$\lambda x.t$]	o bien una función que toma una variable y devuelve un valor calculado por un término. Esto es a lo que se llama una abstracción lambda o función anónima.

Nota: La aplicación se asocia por la izquierda. Entonces, en vez de escribir [$(((t_1 t_2) t_3) t_4)$] escribimos [$t_1 t_2 t_3 t_4$]. 

Lo que es la semántica es también muy fácil de expresar: un término se convierte en un valor mediante una relación binaria [$t\Downarrow v$]. Los valores [$v$] sólo son un tipo especial de término que se denominan formas normales (nosotros vamos a usar WNF). [$$v::= \lambda x.t \mid x v_1 \cdots v_n$$]  Estas formas normales no se pueden reducir más con las reglas de evaluación con las que vamos a expresar la semántica. Estas reglas son las siguientes:
   

Regla E-VAR[$$x\Downarrow x$$]	Regla E-ABS[$$\lambda x.t \Downarrow \lambda x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}t_1 \Downarrow x v_1 \cdots v_k\\t_2 \Downarrow v \end{array}}{t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$]	Regla E-APABS [$$\frac{\begin{array}{c}t_1 \Downarrow \lambda x.t\\t_2 \Downarrow v \\ [x\leftarrow v]t\Downarrow  v'\end{array}}{t_1 t_2 \Downarrow v'}$$]

Como se comprobará, las reglas E-VAR y E-ABS no son complicadas ya que tanto las variables como las abstracciones son valores. El núcleo de todo está en las aplicaciones.
Tanto la regla E-APVAL como la regla E-APABS tienen una forma que recuerda a las fracciones. Esta es una notación usual en lógica para especificar reglas de inferencia e indica que si lo de arriba, que es el antecedente, se cumple, entonces lo de abajo, el consecuente, se debe cumplir.

La regla E-APVAL toma dos términos aplicados el [$t_2$] al [$t_1$]. Si resulta que [$t_1$] tras evaluar tiene un valor que no es una abstracción, lo único que podemos hacer es poner el valor de [$t_2$] detrás de la forma normal, haciéndola un poco más larga. Esto tiene algo más de sentido si, por ejemplo, usamos una variable que se llame [$lista$] y evaluemos algo como [$(lista\ 1\ 7) (2+3)$]. El resultado es la propia [$lista\ 1\ 7$] con un añadido que es el valor de [$2+3$]. Es decir, que [$  (lista\ 1\ 7) (2+3) \Downarrow lista\ 1\ 7\ 5$].

La regla E-APABS también toma dos términos aplicados. Esta vez tiene que ocurrir que [$t_1$] se evalúa a una función [$\lambda x.t$]. Entonces, hay que aplicar el resultado de [$t_2$] que es [$v$] a la función. La forma de hacerlo es sustituir todas las apariciones de [$x$] en [$t$] por [$v$] y calcular el valor que nos da esto. La sustitución la hemos escrito como [$[x\leftarrow v]$].

Entonces, si queremos calcular el doble de 1+3, sería evaluar [$(\lambda x.x+x)(1+3)$]. Usando la regla E-APABS vemos que, efectivamente, [$t_1=  \lambda x.x+x$] y que [$t_1 \Downarrow   \lambda x.x+x $] gracias a la regla E-ABS. Entonces, [$t=x+x$]. Por otra parte, [$t_2=1+3$] y [$t_2 \Downarrow 4$]. Finalmente, la sustitución a realizar es [$[x\leftarrow  4]t = 4+4$]. La evaluación es [$4+4\Downarrow 8$] por lo que [$v'=8$] y podemos decir que ocho es el doble de cuatro: [$$(\lambda x.x+x)(1+3)\Downarrow 8$$]

Nota: ¿Cómo es que estamos usando sumas y números si no los hemos definido? Realmente, sí que lo están. El lambda cálculo permite codificar los números (y muchas más cosas) como funciones. Esta es la llamada codificación de Church.



El lambda cálculo sin sustituciones

El lambda cálculo es Turing completo. Esto quiere decir que cualquier función calculable se puede calcular en él. Esto, por otra parte, no significa que sea eficiente computacionalmente. De hecho, la sustitución es una operación muy costosa: hay que recorrer todo el término en el que queremos sustituir y comparar las variables y manipular grandes trozos de expresión. Las reglas exactas son estas:

[$$[x\leftarrow t]x=t$$]	[$$\frac{x\ne x'}{[x\leftarrow t]x'=x'}$$]
[$$[x\leftarrow t](t_1 t_2)=(  [x\leftarrow t] t_1 ) (   [x\leftarrow t]  t_2 )$$]	[$$[x\leftarrow t]\lambda x.t' =  \lambda x. t' $$]

La última regla está más abajo y es la más divertida porque tiene que evitar capturar las variables. Para hacer esto debe explorar además del término donde se sustituye el término a sustituir. Más coste.
[$$\frac{\begin{array}{c}x\ne x'\\x'\notin fv(t)\end{array}}{[x\leftarrow t]\lambda x'.t' =  \lambda x'. [x\leftarrow t] t' }$$] Todos los creadores de compiladores e intérpretes buscan los métodos más curiosos para evitar la sustitución. Uno de estos métodos es la evaluación por entornos, aunque hay más como las máquinas G, los supercombinadores, etc.

Nosotros vamos a usar la evaluación por entornos que es más simple. La idea es sencilla: no sustituimos, sólo apuntamos lo que hay que sustituir. Lo apuntamos en un entorno que es una colección de vinculaciones de ese tipo. [$$ E::= \emptyset \mid E, x=v $$] Añadimos el entorno a nuestra relación de evaluación de esta manera [$$ E \vdash t \Downarrow v$$] Se podría leer "bajo el entorno [$E$] el término [$t$] se evalúa a [$v$]".

La idea es sencilla, ahora hay que establecer las reglas de evaluación. Un primer intento podría ser éste:

   

Regla E-VAR[$$\frac{x=v \in E}{E\vdash x\Downarrow v}$$]	Regla E-ABS[$$E\vdash\lambda x.t \Downarrow \lambda x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}E \vdash t_1 \Downarrow x v_1 \cdots v_k\\ E \vdash t_2 \Downarrow v \end{array}}{E \vdash t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$]	Regla E-APABS [$$\frac{\begin{array}{c} E \vdash t_1 \Downarrow \lambda x.t\\ E \vdash t_2 \Downarrow v \\   E,x=v \vdash t\Downarrow  v'\end{array}}{ E \vdash t_1 t_2 \Downarrow v'}$$]

El truco está en la nueva regla E-VAR que mira en el entorno el valor de la variable encontrada y en la regla E-APABS que introduce en el entorno la vinculación.

Desafortunadamente estas reglas no funcionan.

El problema se observa en la siguiente evaluación [$$\emptyset \vdash (\lambda y.\lambda x.y) 3 \Downarrow v'$$] La regla a aplicar sería E-APABS que me diría que [$$ y=3 \vdash \lambda x.y \Downarrow v'$$] La regla E-ABS terminaría la evaluación incorrectamente [$$ y=3 \vdash \lambda x.y \Downarrow \lambda x.y$$] en vez de la correcta [$\lambda x.3$]. Hay que evitar que se pierda el entorno en la regla E-ABS. Al perder el entorno la expresión [$\lambda x.y$] queda abierta con la variable [$y$] libre. La solución es cerrarla con una clausura. La clausura será léxica porque hemos ido descendiendo por las estructuras sintácticas arrastrando los entornos hasta aquí.

Incluyamos entonces un nuevo término a nuestra sintaxis: las clausuras léxicas. Que son la combinación de una abstracción lambda y un entorno. [$$ t::= x\mid tt \mid \lambda x.t \mid \lambda^E x.t $$] Ahora los valores son [$$ v::= \lambda^E x.t \mid x v_1 \cdots v_k$$] y las reglas de evaluación correctas serían
   

Regla E-VAR[$$\frac{x=v \in E}{E\vdash x\Downarrow v}$$]	Regla E-ABS[$$E\vdash\lambda x.t \Downarrow \lambda^E x.t $$]
Regla E-APVAL[$$\frac{\begin{array}{c}E \vdash t_1 \Downarrow x v_1 \cdots v_k\\ E \vdash t_2 \Downarrow v \end{array}}{E \vdash t_1 t_2 \Downarrow x v_1 \cdots v_k v}$$]	Regla E-APABS [$$\frac{\begin{array}{c} E \vdash t_1 \Downarrow \lambda^{E'} x.t\\ E \vdash t_2 \Downarrow v \\   E',x=v \vdash t\Downarrow  v'\end{array}}{ E \vdash t_1 t_2 \Downarrow v'}$$]

He cambiado la regla E-ABS convirtiendo la abstracción (que es código) en la clausura léxica (que es un valor) y la regla E-APABS que ahora usa el entorno de la clausura en vez del entorno de llamada.

Si evaluamos otra vez   [$$\emptyset \vdash (\lambda y.\lambda x.y) 3 \Downarrow v'$$] obtenemos que [$ v'=\lambda^{y=3}x.y$]. Lo cual me dice que hay una sustitución pendiente de [$y$] por el valor [$3$]. Esta sustitución se hará cuando se aplique la función. No se perderá.

Nota: Hay un pequeñísimo detalle a tener en cuenta en estas nuevas reglas. Si queremos hacer una lista como hicimos antes [$lista\ 1\ (1+1)$] no podremos evaluarla. Eso es así porque la variable [$lista$] no está en el entorno y no podremos aplicar la regla E-VAR. Una solución a esto es añadir un entorno inicial donde [$lista=lista$] de manera que [$ lista=lista \vdash lista\ 1\ (1+1) \Downarrow   lista\ 1\ 2$]. Esto nos debe llevar a pensar que hay dos tipos de variables las de código ([$lista$][$=lista$]) y las de valor ([$lista=$][$lista$]). Haciendo que las variables de valor tengan también entorno ([$x^E$]) abrimos la puerta a las macros higiénicas.

Modelos de memoria compartida

Orden de programa

Un programa se compone de instrucciones.

1 x=A //Lee el valor de A
2 B=2 //Escribe un valor en B
3 y=B //Lee el valor de B

Usaré las letras mayúsculas (A,B,C) para las localizaciones de memoria y las minúsculas (a,b,c) para registros o valores que no estén en memoria. Como nos interesa el modelo de memoria, ignoraremos las operaciones que no trabajen con memoria. Para mayor facilidad usaremos números para cada instrucción.

Cuando se ejecuta un programa las instrucciones que se van ejecutando conforman una secuencia que se denomina traza. Se llama orden de programa a la relación de orden estricto que encadena las instrucciones según se ejecutan en una traza. Si escribimos esta relación como [$ \rightarrow_p $] entonces, el programa de arriba tiene la siguiente traza

[$$ 1 \rightarrow_p 2 \rightarrow_p 3 $$]

Nada extraño. Esta relación es un orden estricto y, en principio, total.


Modelo secuencialmente consistente (SC)

Cuando tenemos varios procesadores, cada uno de ellos ejecutando una hebra distinta, ¿cómo se reparten las instrucciones? ¿Y qué instrucciones se ejecutan antes que otras? Un modelo de memoria compartida responde a estas preguntas.

El modelo más simple es el secuencialmente consistente (SC) de Lamport. En este modelo las instrucciones de todos los procesadores se intercalan y el orden resultante de las mismas ha de ser un orden total que llamaremos de ocurrencia [$ \rightarrow_o $].

Si no pusiéramos más condiciones, este orden podría ser cualquiera, incluso sin respetar el orden de programa.

Por ejemplo, este programa con dos hebras

INICIALMENTE: A=B=0
HEBRA 1   HEBRA 2
1 x=A     11 y=B
2 B=1     12 A=1

Tiene el siguiente orden de programa

[$$ 1 \rightarrow_p 2 $$]
[$$ 11 \rightarrow_p 12 $$]

Sin condiciones adicionales, el orden de ocurrencia podría ser, por ejemplo

[$$ 2 \rightarrow_o 12 \rightarrow_o 1 \rightarrow_o 11 $$]

Nota: Tanto el orden [$ \rightarrow_p $] como el orden [$ \rightarrow_o $] son transitivos por lo que con el ejemplo de arriba también tendríamos [$ 2 \rightarrow_o 1, 2 \rightarrow_o 11, 12 \rightarrow_o 11 $]. Es usual no listar estas relaciones que se pueden derivar fácilmente de la primera.

Este orden daría como resultado x=y=1 lo cual es bastante contraintuitivo. El modelo SC tiene la siguiente restricción: si [$N$] y [$M$] son dos instrucciones y [$ N \rightarrow_p M $] entonces debe darse que [$ N \rightarrow_o M $]. Esta condición se expresa de la siguiente manera.

[$$ \frac{N \rightarrow_p M}{N \rightarrow_o M} $$]

Esto quiere decir que si en una hebra se ejecuta una instrucción antes que otra por el orden de programa (por ejemplo, la 11 antes de la 12) entonces ese mismo orden aparece en el orden de ocurrencia. Como en el ejemplo anterior teníamos que 12 ocurría antes que 11, excluimos este posible orden del modelo SC.

[$ 2 \rightarrow_o 12 \rightarrow_o 1 \rightarrow_o 11$] no es SC porque [$2 \rightarrow_o 1$] pero [$1 \rightarrow_p 2$]
[$ 11 \rightarrow_o 1 \rightarrow_o 2 \rightarrow_o 12 $] sí es SC y el resultado es un intuitivo x=y=0
[$ 1 \rightarrow_o 2 \rightarrow_o 11 \rightarrow_o 12 $] sí es SC y el resultado es otro intuitivo x=0, y=1

El dibujo típico del modelo secuencialmente consistente es una memoria compartida asignada únicamente a un procesador en cada momento.

Optimizaciones en compiladores y procesadores

Desafortunadamente las cosas no son tan sencillas. Generalmente el orden de programa es excesivamente restrictivo para realizar optimizaciones. Una optimización típica es la siguiente.

1 A=5
2 x=A
3 B=1

En el anterior programa, la instrucción 2 ha de esperar a que la instrucción 1 escriba el valor 5 en A. Un compilador o un procesador astuto reordena el programa de la siguiente forma.

11 A=5
12 B=1
13 x=A

En este programa transformado, la instrucción 12 se ejecuta mientras la instrucción 11 se está terminando. Esto evita que tengamos que esperar en la instrucción 13 tanto como hacíamos en la instrucción 2.

El problema es que el programador ha escrito las instrucciones 1,2,3 y no las 11,12,13. ¿Qué pasa si ejecutamos esto con otra hebra?

HEBRA 1   HEBRA 2
1 A=5     21 if(B=1)
2 x=A     22   A=7
3 B=1

Pensando en SC de ninguna manera podría ocurrir que x=7 ya que para cuando B=1, x ya tiene el valor 5 y por mucho que modifiquemos A=7, x ya no va a cambiar. Esto no es así si el procesador o el compilador reordena el programa de la hebra 1 sin que lo sepamos.

HEBRA 1   HEBRA 2
11 A=5    21 if(B=1)
12 B=1    22   A=7
13 x=A

Aunque el programador ha escrito 1,2,3, el compilador o el procesador lo reordena a 11,12,13 para optimizar la espera de la instrucción 2 tras la 1. Ahora bien, ¡esto ahora permite que x=7! El orden de ocurrencia para este bug sería

[$$ 11 \rightarrow_o 12 \rightarrow_o 21 \rightarrow_o 22 \rightarrow_o 13 $$]

Si el pobre programador intenta razonar sobre el orden del programa original 1,2,3 lo que vería sería

[$$ 1 \rightarrow_o 3 \rightarrow_o 21 \rightarrow_o 22 \rightarrow_o 2 $$]

que no es SC porque la instrucción 3 se ejecuta antes que la 2.

Relajando el modelo SC

Por esta razón el modelo SC no es útil: no permite al compilador o al procesador optimizar los programas sin dejar al programador con un difícil bug a resolver. La solución es exponer al programador un modelo más débil que se denomina un modelo relajado.

¿Cómo vamos a relajar ese modelo? Hay varias formas.

La primera es permitir reordenar las instrucciones de un programa y proporcionar al programador herramientas para decirle al compilador y al procesador cuándo no se pueden reordenar. Una de estas herramientas es una instrucción llamada barrera de memoria (memory fence) y lo único que significa es que es una barrera que las instrucciones no se la pueden saltar al ser reordenadas.

Con una barrera, el programa anterior quedaría así

HEBRA 1   HEBRA 2
1 A=5     21 if(B=1)
2 x=A     22 A=7
3 FENCE
4 B=1

Y ni el compilador ni el procesador podrían reordenar la instrucción 4 sobre la 3 o la 1 o la 2 bajo la 3. De esta manera, el programador se asegura de que leemos A antes de modificar B. Por otra parte, el compilador o el procesador son libres de realizar otras optimizaciones en otros sitios.

¿Pero en qué sitios? ¿Podría reordenar la instrucción 2 sobre la 1? Realmente no, porque necesitamos conocer A en la instrucción 2 y eso depende de la instrucción 1. A esta relación se la llama una dependencia y la escribiremos [$\rightarrow_d$]. Básicamente indica que un valor no se puede usar antes de que haya sido calculado. En un modelo de memoria relajado al menos se debe conservar la dependencia. Es decir,

[$$\frac{N \rightarrow_d M}{N \rightarrow_o M}$$]

Además, las barreras de memorias ordenan lo que ocurre antes y después de ellas.

[$$\frac{N \rightarrow_p M,  N\ es\ FENCE}{N \rightarrow_o M},\ \ \frac{N \rightarrow_p M,  M\ es\ FENCE}{N \rightarrow_o M}$$]

Entonces, en el programa anterior teníamos.

[$$1\rightarrow_p 2\rightarrow_p 3\rightarrow_p 4,11\rightarrow_p 12$$]
[$$1\rightarrow_d 2,11\rightarrow_d 12$$]
[$$3\ es\ FENCE$$]

Por la dependencia debe cumplirse que

[$$1\rightarrow_o 2,11\rightarrow_o 12$$]

y por barrera debe cumplirse que

[$$1\rightarrow_o 3,2\rightarrow_o 3,3\rightarrow_o 4$$]

Entonces, está claro que

[$1\rightarrow_o 11\rightarrow_o 2\rightarrow_o 12\rightarrow_o 3\rightarrow_o 4$] sí cumple con el modelo relajado
[$1\rightarrow_o 11\rightarrow_o 2\rightarrow_o 12\rightarrow_o 4\rightarrow_o 3$] no cumple con el modelo relajado porque [$4\rightarrow_o 3$]

Nota: La instrucción 12 no se ejecuta, pero de ejecutarse lo haría en la posición arriba puesta.
Nota: Sabemos que si [$4\rightarrow_o 3$] entonces no se da [$3\rightarrow_o 4$] porque estamos tratando con órdenes.


Otras barreras, otros modelos, otras instrucciones

Algunos compiladores y procesadores se restringen a reordenar instrucciones que son de cierto tipo. Los más usuales son

• Reordena una escritura seguida de otra escritura (WW)
• Reordena una lectura seguida de una escritura (RW)
• Reordena una escritura seguida de una lectura (WR)
• Reordena una lectura seguida de otra lectura (RR) 

Eso permite además tener barreras de memoria selectivas que

• Impida reordenar escrituras anteriores a la barrera con escrituras posteriores (WW)
• Impida reordenar lecturas anteriores a la barrera con escrituras posteriores (RW)
• Impida reordenar escrituras anteriores a la barrera con lecturas posteriores (WR)
• Impida reordenar lecturas anteriores a la barrera con lecturas posteriores (RR) 

Esto lleva permitirle al compilador y al procesador más optimizaciones. Existen más métodos de restringir la reordenación como instrucciones atómicas, sincronizaciones, bloqueos, etc. Eso sí, empieza a crearnos un zoológico de modelos de memoria que, sin embargo, se dan en la vida real. Por ejemplo,

Procesador o 
Modelo de memoria  Relaja WR  Relaja WW  Relaja RW  Relaja RR
SC
IBM 360            Sí
TSO                Sí
PC                 Sí
PSO                Sí         Sí
WO                 Sí         Sí         Sí         Sí
RCsc               Sí         Sí         Sí         Sí
RCpc               Sí         Sí         Sí         Sí
Alpha              Sí         Sí         Sí         Sí
RMO                Sí         Sí         Sí         Sí
PowerPC            Sí         Sí         Sí         Sí

Para más información http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.5742&rank=1

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.

Nunca es tarde para una (buena) compilación

Compilación estática y compilación dinámica

La compilación usual es la compilación estática. En la compilación estática analizamos el código fuente y generamos un código ejecutable en la plataforma de destino que queramos. Es lo que se denomina código nativo o código máquina.

Generalmente este tipo de compilación es muy rígida porque necesitamos saberlo todo antes de producir el ejecutable nativo. Una primera solución a este problema es separar el código nativo en bloques distintos que cargamos cuando vayamos a ejecutar. A esto se le denomina biblioteca dinámica.

Pero podemos hacerlo mejor. Podríamos no generar un código nativo, sino separar el compilador en dos partes. La primera genera un código incompleto llamado código intermedio o bytecode y la segunda termina de compilar ese código incompleto al código nativo más tarde. Cuando vayamos a ejecutar.

Esto es la compilación dinámica que fue introducida por David Ungar en el lenguaje Self. Este tipo de traducciones de un código binario a otro código binario se llaman traducciones binarias. Son usuales en los emuladores y máquinas virtuales.

La compilación dinámica más simple es la adelantada en el tiempo (AOT en sus siglas en inglés). En este caso compilamos todo el código intermedio a código nativo en cuanto tenemos que ejecutar el programa. Esto hace que sea lento arrancar el programa pero, una vez funcionando, vaya rápido.

¡Justo a tiempo!

Otra opción es compilar más tarde. ¿Cómo vamos a compilar después de cargar el código? Muy sencillo: compilamos conforme vayamos ejecutando. Empezamos a ejecutar una sección del código (función o incluso un bloque de una función). Si está compilado lo ejecutamos y si no, lo compilamos y ejecutamos. De esta manera el arranque es más rápido que en AOT porque sólo compilamos lo que necesitamos para arrancar y no todo el programa.

Esta compilación es la compilación justo a tiemo (JIT en sus siglas inglesas) y es la más usada con diferencia. De hecho, se puede hasta hacer más rápida aún. La técnica es muy sencilla. Introducimos junto al compilador un intérprete. Cuando nos encontramos un trozo de código sin compilar pasamos el intérprete y recogemos estadísticas de uso de ese trozo de código.

Cuando la estadística nos indica que es un trozo de código muy usado, compilamos. Si no es muy usado lo dejamos sin compilar y lo interpretamos. De esta manera se mejoran incluso los tiempos de arranque ya que suelen ser secciones de código que usan mucho las entradas/salidas a disco y compilar no sirve para acelerarlas. Véase la Ley de Amdhal.

Finalmente podemos hacer que el propio usuario o el propio programa decida cuándo compilar y cuándo no. Incluso, compilar desde código fuente y no desde código intermedio. En este caso hay que meter todo el compilador (y no solo la parte de traducción binaria) en el sistema de ejecución. Esto es lo que se llama la compilación incremental.

Pero no todo acaba aquí: Cuando el programa ya está compilado ¡podemos recompilarlo! Esta técnica es la recompilación dinámica (dynarec o DRC en inglés). La recompilación vuelve a optimizar el código ya que una vez que tenemos el programa entero se dispone de más información que cuando se está compilando.

Máquinas virtuales e instrucciones

Una máquina virtual es un procesador que se emula por software. Si la máquina virtual está pensada para ofrecer todas las prestaciones de un sistema real, se llama máquina virtual de sistema. Si es una abstracción para que algún proceso funcione, se llama máquina virtual de proceso. (Ver la Wiki).

Una máquina virtual puede ser una implementación de una máquina ideal que no exista. Es más, podemos inventarnos la máquina virtual que necesitemos para resolver un problema específico. Inventar las instrucciones de la máquina y definir su comportamiento es una de las partes más emocionantes de la creación de máquinas virtuales propias.

Personalmente he tratado con un tipo de máquinas virtuales que se denominan máquinas de pila. Sin embargo, hoy en día estoy con otro tipo llamadas máquinas de registro. Las primeras me parecen mucho más fáciles, pero he de reconocer que la comparación hecha en la Wikipedia deja claro que las segundas son mucho más rápidas. También hay un tercer tipo por lo que la lista completa sería:

• Máquinas de pila. Instrucciones sin argumentos del tipo PUSH, POP, ADD, SUB, etc.
• Máquinas de registro. Instrucciones con argumentos de origen y destino tipo ADD x,y; SUB x,y; etc.  Algunos juegos de instrucciones tienen también tres argumentos como MUL x, y, z;
• Máquinas de acumulador. Instrucciones con argumento de origen únicamente. El destino es un registro especial que es el acumulador. Serían cosas como ADD x; SUB x; etc.

Esta clasificación también se puede extender a máquinas reales, aunque sea muy difícil encontrar un microprocesador que sea exclusivamente de un tipo. Por ejemplo, la arquitectura i386 tiene instrucciones de pila (como FSUB), instrucciones de acumulador (como STOS) e instrucciones de registro de dos (como ADD) y de tres (como IMUL) argumentos.