Transformación CPS

Hace algún tiempo hablamos de las continuaciones. Además, dimos una semántica operacional para ellas. Ahora vamos a describir cómo se transforma un programa para que use continuaciones en todas sus llamadas a función. Esto es el estilo de paso de continuaciones (CPS) que permite eliminar la necesidad de usar una pila de llamadas. Es decir, la cadena dinámica.

El estilo de paso de continuaciones (CPS)

Para empezar, veamos cómo es eso del CPS. Supongamos la siguiente expresión.
[$$ f(g(a)) $$]
Lo primero que calculamos es el valor de [$a$]. Luego, el valor de [$g(a)$] y, finalmente, el valor de [$f(g(a))$]. El estilo CPS añade un argumento adicional a cada función que es la continuación, a la que le pasaremos el resultado cuando la función termine.

¿A dónde pasábamos el resultado de [$g(a)$]? A [$f$]. Así que, al hacer [$g$] CPS, la expresión de arriba queda
[$$ g(f, a) $$]
y se leería algo así como "calcula [$g(a)$] y pásale el resultado a [$f$]. El problema es que también tenemos que hacer CPS a [$f$] por lo que ahora [$f$] no toma un argumento, toma dos: la continuación y su argumento propiamente dicho. La solución es añadir una función anónima. La expresión de arriba con tanto [$g$] como [$f$] puestas en CPS sería así:
[$$g(\lambda x.f(k,x), a)$$]
El detalle es que [$k$] es la continuación de la expresión, que no sabemos cuál es porque no he dicho qué vamos a hacer después de calcular [$f(g(a))$]. Para destacar claramente que [$k$] es la continuación, que [$f(g(a))$] es la expresión original y que [$g(\lambda x.f(k,x), a)$] es la expresión transformada a CPS, vamos a usar la siguiente notación:
[$$ T\ [\ f(g(a))\mid k\ ]\ = g(\lambda x.f(k,x), a) $$]

La transformación de Plotkin

Bastará conocer las reglas de la transformación [$ T\ [\ ]$] para poder realizarla. Esto es a lo que se dedicó Plotkin en 1975 en el artículo "Call-by-name, call-by-value and the [$\lambda$]-calculus", aunque ha llovido mucho y la versión que presento aquí es bastante distinta a la original.

Lo primero que necesitamos es definir el lenguaje que vamos a transformar. Vamos a usar una variante del lambda cálculo sin currificar. Es muy sencilla: un valor es o bien una variable o bien una función anónima.
[$$ v::= x \mid \lambda (x_1,...,x_n).e $$]
Una expresión es o bien un valor o bien una aplicación (llamo [$s$] a las aplicaciones).
[$$ e::= v \mid s $$]
También llamaremos, [$k$] a una expresión. Una aplicación no es más que una llamada a función.
[$$ s::= e_0 (e_1,...,e_n) $$]
Para transformar un programa escrito con esta sintaxis hemos de dar la transformación para cada una de estas construcciones sintácticas. Si lo que tengo un valor, ya está calculado, sólo he de pasarlo a la continuación. ¡Pero ojo! Si es una función he de transformarla antes en CPS. De esto se va a encargar la transformación auxiliar [$ M[\ ]$].

• Regla P-TV: [$ T\ [\ v\mid k\ ]= k(M[\ v\ ])$]

La transformación auxiliar es bien sencilla: si no es una función no hace nada, si es una función le añade el argumento de la continuación y transforma su cuerpo.

• Regla P-MX:  [$ M\ [\ x\ ]=x $]
• Regla P-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid x\ ] $]

Finalmente, si lo que tenemos es una aplicación, vamos calculando su operador y argumentos hasta que, al final, podamos llamar a la función.

• Regla P-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]=T[\ e_0 \mid \lambda x_0.T[\ e_1 \mid \lambda x_1.\ ...T[\ e_n \mid \lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]

Va a ser muy habitual encontrarnos con transformaciones anidadas del tipo [$...T[\ e\mid\lambda x.T[...$] ya que representan una secuencia de operaciones. El resultado de [$e$] se pasa a la continuación que empieza por [$\lambda x...$] lo que hace guardar el resultado de [$e$] en [$x$] y proseguir con la ejecución de la secuencia. Para facilitar la comprensión de una expresión en CPS vamos a poner como subíndice de una variable la expresión cuyo valor guarda.

Bien, ahora que tenemos las cuatro reglas de Plotkin vamos a probar a ver cómo transforma a [$f(g(a))$]. Vamos a hacerlo paso a paso.

1. Inicial: [$T[\ f(g(a)) \mid k\ ]$]
2. Regla P-TS: [$ T[\ f \mid \lambda x_f.T[\ g(a) \mid \lambda x_{g(a)}. x_f(k, x_{g(a)})\ ]\ ] $]
3. Regla P-TV: [$ (\lambda x_f.T[\ g(a) \mid \lambda x_{g(a)}. x_f(k, x_{g(a)})\ ]\ )(M[\ f\ ]) $]
4. Regla P-MV: [$ (\lambda x_f.T[\ g(a) \mid \lambda x_{g(a)}  . x_f(k, x_{g(a)})\ ]\ )(f) $]  
5. Regla P-TS: [$ (\lambda x_f.T[g \mid \lambda x_g.T[\ a \mid \lambda x_a. x_g( \lambda x_1. x_f(k, x_{g(a)}) , x_a)\ ]\ ]\ )(f) $]  
6. Regla P-TV: [$ (\lambda x_f. (\lambda x_g.T[\ a \mid \lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a)\ ]\ )(M[\ g\ ]) )(f) $]
7. Regla P-MV: [$ (\lambda x_f. (\lambda x_g.T[\ a \mid \lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a)\ ]\ )(g) )(f) $]
8. Regla P-TV: [$ (\lambda x_f. (\lambda x_g.  (\lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a) )(M[\ a\ ]\ ) )(g) )(f) $]
9. Regla P-MV: [$ (\lambda x_f. (\lambda x_g.  (\lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a) )(a) )(g) )(f) $]

 El resultado de esta expresión es sorprendentemente complejo. Además, parece que podríamos usar varias veces la regla beta para reducir un poco más la expresión.

1. Del anterior: [$ (\lambda x_f. (\lambda x_g.  (\lambda x_a. x_g( \lambda x_{g(a)}. x_f(k, x_{g(a)}) , x_a) )(a) )(g) )(f) $]
2. Regla beta: [$ (\lambda x_g.  (\lambda x_a. x_g( \lambda x_{g(a)}. f(k, x_{g(a)}) , x_a) )(a) )(g) $]
3. Regla beta: [$ (\lambda x_a. g( \lambda x_{g(a)}. f(k, x_{g(a)}) , x_a) )(a) $]
4. Regla beta: [$ g( \lambda x_{g(a)}. f(k, x_{g(a)}) , a) $]

Esto sí se parece a lo que teníamos inicialmente, el problema es que no podemos realizar reglas beta ya que estamos transformando código y ¿cómo sabemos qué lambdas son del código y qué lambdas son las introducidas por la transformación?

¡Ah!... Se me ocurre una idea. Podríamos etiquetarlas...

Nota: ¿Por qué no podemos realizar reglas beta en el código? Imaginemos la siguiente expresión [$(\lambda x.3)(f(x))$]. Si [$f(x)$] tiene efectos secundarios, al realizar la regla beta obtendríamos [$3$] y habríamos perdido los efectos secundarios.

 La tranformación de alto nivel de Appel

Esta fue la idea que se le ocurrió a Appel en 1992 para su libro "Compiling with Continuations", pero no es tan sencilla. En primer lugar estaríamos tentados a etiquetar (con una rayita encima) las lambda que fueran introducidas por la transformación a CPS. Empecemos por la regla que las introduce: la P-TS que renombraremos a A-TS.

• Regla A-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]=$][$T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar\lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]

El problema es que las [$\bar\lambda$] no son código, son funciones sobre el código (de ahí lo de alto nivel). Si dejáramos las cosas así obtendríamos
[$$ T[\ f(a)(b)\ ]=f(\bar\lambda x_{f(a)}.x_{f(a)}(k,b), a) $$]
Y eso no es código. No es código porque contiene un [$\bar\lambda$] que es una función sobre el código. No está en la sintaxis que pusimos al inicio.

La solución se obtiene forzando que las continuaciones se especifiquen siempre de forma indirecta, como una función sobre el código. En ese aspecto, cambiamos la regla P-ML de la siguiente forma (la nueva regla es la A-ML):

• Regla P-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid x\ ] $]  
• Regla A-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid \bar\lambda x_0.x x_0\ ] $]  

El truco está en que [$\bar\lambda x_0.x x_0$] convierte el código [$x$] en una función que toma código [$x_0$] y devuelve código [$x x_0$]. Como [$x$] va a ser la continuación, el efecto es pasarle [$x_0$] a la continuación. Justo lo que teníamos antes pero, esta vez, el [$\bar\lambda$] significa que estoy trabajando con funciones sobre código y no sobre código. Podré usar la regla beta para simplificarlas. Lo que buscábamos a la hora de etiquetar.

También hay que trastear la regla A-TS porque [$k$] no es código.

• Regla P-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]= $][$ T[\ e_0 \mid \lambda x_0.T[\ e_1 \mid \lambda x_1.\ ...T[\ e_n \mid \lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $] 
•  Regla A-TS antigua (etiqueto lambdas): [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]= $][$ T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar \lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $] 
• Regla A-TS nueva (arreglo [$k$]): [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]= $][$ T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar \lambda x_n. x_0(\lambda x.k x, x_1,...,x_n)\ ]\ ...\ ]\ ] $]

El truco de [$\lambda x.kx$] es que [$k$] es una función de código que tomará el código [$x$] y generará otro código que permanece dentro del cuerpo de [$\lambda x$]. El resultado es, por tanto, código. Para dejar claro qué variables son de código y qué variables son funciones sobre el código, también etiquetaremos estas últimas que incluirán ahora todas las continuaciones también.

Entonces, las reglas de transformación de alto nivel definitivas son las siguientes:

• Regla A-MX:  [$ M\ [\ x\ ]=x $]
• Regla A-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid   \bar\lambda x_0.x x_0  \ ] $]
• Regla A-TV: [$ T\ [\ v\mid \bar k\ ]= k(M[\ v\ ])$]
• Regla A-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid \bar k\ ]=$][$T[\ e_0 \mid \bar\lambda x_0.T[\ e_1 \mid \bar\lambda x_1.\ ...T[\ e_n \mid \bar\lambda x_n. x_0(\lambda x.\bar k x, x_1,...,x_n)\ ]\ ...\ ]\ ] $]
•  Regla beta: [$ (\bar\lambda (x_1,...x_n). e) (v_1,...,v_n) = [x_1 \rightarrow v_1,...,  x_n \rightarrow v_n  ]e $]

Mejoran mucho el resultado de la transformación a CPS. El único inconveniente es que debemos trabajar con funciones sobre código (de alto nivel). Así que, si [$k$] sin etiquetar es código, no puedo escribir
[$$ T[\ f(a)\mid k\ ]$$]
Tengo que escribir
[$$ T[\ f(a)\mid \bar\lambda x.k x\ ]$$]
y el resultado de esto no es todo lo perfecto que quisiéramos:
[$$ f( \lambda x.k x, a) $$]
Se me ocurre otra idea... ¿Y no podemos mezclar las reglas de Plotkin y de Appel para usar código o funciones sobre código cuando queramos?

La tranformación CPS híbrida

Separemos entonces [$T\ [\ ]$] en dos: una sin etiqueta y otra con etiqueta [$\bar T\ [\ ]$]. La versión sin etiqueta requiere que la continuación sea código [$T\ [\ e\mid k\ ]$] y la etiquetada requiere que sea una función sobre código [$\bar T\ [\ e\mid \bar k\ ]$]. La mezcla es sencilla. 

• Regla H-MX:  [$ M\ [\ x\ ]=x $]
• Regla H-ML: [$ M\ [\ \lambda(x_1,...,x_n).e\ ]=\lambda(x,x_1,...,x_n).T[\ e\mid x \ ] $]
• Regla H-TV: [$ T\ [\ v\mid k\ ]= k(M[\ v\ ])$]
• Regla H-TS: [$ T\ [\ e_0(e_1,...,e_n) \mid k\ ]=$][$\bar T[\ e_0 \mid \bar\lambda x_0. \bar T[\ e_1 \mid \bar\lambda x_1.\ ... \bar T[\ e_n \mid \bar\lambda x_n. x_0(k, x_1,...,x_n)\ ]\ ...\ ]\ ] $]  
• Regla H-FV: [$ \bar T\ [\ v\mid \bar k\ ]= \bar k(M[\ v\ ])$]
• Regla H-FS: [$ \bar T\ [\ e_0(e_1,...,e_n) \mid \bar k\ ]=$] [$\bar T[\ e_0 \mid \bar\lambda x_0. \bar T[\ e_1 \mid \bar\lambda x_1.\ ... \bar T[\ e_n \mid \bar\lambda x_n. x_0(\lambda x.\bar k x, x_1,...,x_n)\ ]\ ...\ ]\ ] $]
• Regla beta: [$ (\bar\lambda (x_1,...x_n). e) (v_1,...,v_n) = [x_1 \rightarrow v_1,...,  x_n \rightarrow v_n  ]e $]

Con estas reglas sí que conseguimos el objetivo deseado.
[$$ T\ [\ f(a)\mid k\ ]\ = f(k,a)$$]
[$$ T\ [\ f(g(a))\mid k\ ]\ = g(\lambda x.f(k,x), a) $$]
El único problemilla que tenemos es que trabajamos como en dos fases. En la primera fase quitamos las [$T$] (y [$\bar T$]) de en medio y en la segunda fase quitamos las [$\bar \lambda$] con la regla beta. Es posible hacerlo todo a la vez, pero aumenta lo suficiente la complejidad como para no explicarlo aquí (se basa en separar las [$e$] en [$v$] y en [$s$] y tratar cada caso con una regla distinta, específica).

Transformación CPS para lenguajes reales

Para finalizar vamos a apuntar brevemente cómo son las reglas de transformación CPS para un lenguaje de programación real, con asignación, selección, secuencia y demás primitivas.

• AsignaciónT: [$ T\ [\ \mathrm{set}\ x\ e \mid k\ ]=\bar T[ e \mid \bar\lambda x_0. k (  \mathrm{set}\   x\ e)\ ] $]
• AsignaciónF: [$ \bar T\ [\ \mathrm{set}\  x\ e \mid \bar k\ ]=\bar T[ e \mid \bar\lambda x_0. \bar k (  \mathrm{set}\   x\ e)\ ] $]
• SelecciónT: [$ T\ [\ \mathrm{if}\ e_1\ e_2\ e_3 \mid k\ ]=\bar T[\ e_1 \mid \bar\lambda x_1. (  \mathrm{if}\ x_1\ T[\ e_2 \mid k\ ]\ T[\ e_3 \mid k\ ]\ ] $]
• SelecciónF: [$ \bar T\ [\   \mathrm{if}\ e_1\ e_2\ e_3 \mid \bar k\ ]=\bar T[\ e_1 \mid \bar\lambda x_1. (  \mathrm{if}\ x_1\ \bar T[\ e_2 \mid \bar k\ ]\ \bar T[\ e_3 \mid \bar k\ ]\ ] $]
• SecuenciaT: [$ T\ [\ e_1 ; e_2 \mid k \ ]= \bar T[\ e_1 \mid \bar\lambda x.T[\ e_2 \mid k\ ]\ ] $]
• SecuenciaF: [$ \bar T\ [\ e_1 ; e_2 \mid \bar k \ ]= \bar T[\ e_1 \mid \bar\lambda x. \bar T[\ e_2 \mid \bar k\ ]\ ] $]

La selección duplica el código que hay en la continuación porque lo usa en dos sitios. Esto puede dar lugar a un código final más grande de lo deseable. La solución es postergar a tiempo de ejecución el paso de la continuación de la siguiente forma:

• SelecciónT2: [$ T\ [\ \mathrm{if}\ e_1\ e_2\ e_3 \mid k\ ]=(\lambda x. \bar T[\ e_1 \mid \bar\lambda x_1. (  \mathrm{if}\ x_1\ T[\ e_2 \mid k\ ]\ T[\ e_3 \mid x\ ]\ ])(k) $]   
• SelecciónF2: [$ \bar T\ [\   \mathrm{if}\ e_1\ e_2\ e_3 \mid \bar k\ ]=(\lambda x. \bar T[\ e_1 \mid \bar\lambda x_1. (  \mathrm{if}\ x_1\ \bar T[\ e_2 \mid \bar x\ ]\ \bar T[\ e_3 \mid \bar k\ ]\ ])(\lambda x_0.\bar k x_0) $]  

La clásica función call/cc se implementa así.

• CallCCT: [$ T\ [\ \mathrm{calcc}\ | k\ ] = k (\lambda(x_0,x_1).x_1(x_0,\lambda(x_2,x_3).x_0(x_3))) $]
• CallCCF: [$ \bar T\ [\ \mathrm{calcc} \ | \bar k\ ] =  \bar k (\lambda(x_0,x_1).x_1(x_0,\lambda(x_2,x_3).x_0(x_3))) $]

Los let se pueden implementar como lambdas aplicados inmediatamente, pero los letrec, no. Asumimos que los letrec sólo pueden vincular valores. Entonces:

• LetRecT: [$ T\ [\ \mathrm{letrec}\ x_1=v_1,...,x_n=v_n\ \mathrm{in}\ e \mid k\ ]=$][$\mathrm{letrec}\ x_1=M[\ v_1\ ],...,x_n=M[\ v_n\ ]\ \mathrm{in}\ T[\ e \mid k\ ] $]
• LetRecF: [$ \bar T\ [\ \mathrm{letrec}\ x_1=v_1,...,x_n=v_n\ \mathrm{in}\ e \mid \bar k\ ]=$][$\mathrm{letrec}\ x_1=M[\ v_1\ ],...,x_n=M[\ v_n\ ]\ \mathrm{in}\ \bar T[\ e \mid \bar k\ ] $]

Referencias

Matt Might - How to compile with continuations
Mark Feeley - The 90 minute Scheme to C compiler 

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

Divisiones y módulos enteros

Supongamos que queremos saber si un número es impar. ¿Bastaría este código?

bool impar(int n)
{
 return (n%2) == 1;
}

Veamos. Introducimos el valor 5, hacemos la división por 2 y obtenemos el resto 1. Efectivamente, es impar. Ahora introduzcamos el valor -3, hacemos la división por 2 y obtenemos ¿qué resto? En mi implementación obtengo -1. Eso es un problema, pero ¿por qué sale -1? ¿No debería salir 1?

El operador de módulo % está muy relacionado con la división entera. La división entera se define de la siguiente manera. Sean cuatro números enteros [$n, d, c$] y [$r$] que llamaremos dividendo, divisor, cociente y resto. Esos cuatro números cumplen la siguiente ecuación.

[$$ n = dc + r $$]

Si, además, imponemos la siguiente inecuación, el cociente y el resto son únicos para cada par de dividendo y divisor.

[$$ 0\le r \lt \left| d \right| $$]

Esto es, básicamente, la llamada división euclídea. Matemáticamente este procedimiento de división es muy interesante y tiene muchas propiedades, pero carece de otras. En concreto, con esta división entera multiplicar divisor y dividendo por menos uno altera el resultado.

[$$ \frac{a}{b} \ne \frac{-a}{-b} $$]

Se puede probar con, por ejemplo, [$ \frac{7}{3} $] el cociente será [$2$] y el resto [$1$] mientras que [$ \frac{-7}{-3} $] tiene cociente [$3$] y resto [$2$]. No puedo obtener cociente [$2$] porque el resto tiene que ser positivo.

Entonces, usemos una división más intuitiva. Por ejemplo, hacemos la división en los reales y luego redondeamos. Ahora bien, hay varios tipos de redondeo. Los más usuales son el redondeo por truncamiento, por defecto, por exceso y al entero más cercano (con varias estrategias de desempate).

Según usemos un tipo de división u otra, obtendremos el resto (es decir, el resultado del operador %) de una forma u otra, pero todas mediante la ecuación anterior para mantener consistencia. Despejamos de ella el resto y esa es nuestra definición del operador %.

[$$ n\%d = r = n - dc = n - d \left[ \frac{n}{d} \right] $$]

La división entre corchetes representa el cociente que cambiará según elijamos uno u otro redondeo. El resumen está en esta tabla.

	Redondeo por truncamiento	Redondeo por defecto	Redondeo por exceso	Redondeo al más cercano	División euclídea
[$$\frac{3}{5}$$]	c=0 r=3	c=0 r=3	c=1 r=-2	c=1 r=-2	c=0 r=3
[$$\frac{-3}{5}$$]	c=0 r=-3	c=-1 r=2	c=0 r=-3	c=-1 r=2	c=-1 r=2
[$$\frac{3}{-5}$$]	c=0 r=3	c=-1 r=-2	c=0 r=3	c=-1 r=-2	c=0 r=3
[$$\frac{-3}{-5}$$]	c=0 r=-3	c=0 r=-3	c=1 r=2	c=1 r=2	c=1 r=2

Hay tres hechos importantes en esta tabla:

1. En el redondeo por truncamiento el signo del resto coincide con el signo del dividendo.
2. En el redondeo por defecto el signo del resto coincide con el signo del divisor (y en el redondeo por exceso con su opuesto).
3. En el redondeo al entero más cercano el resto es el más cercano a cero posible.

Nota: La división que utilizamos cuando usamos el AND binario (&) para calcular rápidamente un módulo [$ a\% 2^n = a \& (2^n -1) $] es o bien la por defecto o la euclídea (tanto el divisor como el resto son positivos en este caso).

Ahora sólo queda ver qué lenguaje de programación usa qué tipo de división y módulo. La siguiente tabla extraída de la Wikipedia lo lista.

Lenguaje	Operador	El resultado tiene el mismo signo que
ActionScript	%	Dividendo
Ada	mod	Divisor
	rem	Dividendo
ASP	Mod	No definido
ALGOL-68	%×	Euclídea
AMPL	mod	Dividendo
AppleScript	mod	Dividendo
BASIC	Mod	No definido
bc	%	Dividendo
bash	%	Dividendo
C (ISO 1990)	%	Depende de implementación
C (ISO 1999)	%	Dividendo
C++	%	Depende de implementación
C#	%	Dividendo
CLARION	%	Dividendo
Clojure	mod	Divisor
ColdFusion	%	Dividendo
Common Lisp	mod	Divisor
	rem	Dividendo
D	%	Dividendo
Eiffel	\\	Dividendo
Erlang	rem	Dividendo
Euphoria	mod	Divisor
	remainder	Dividendo
FileMaker	Mod	Divisor
Fortran	mod	Dividendo
	modulo	Divisor
GML (Game Maker)	mod	Dividendo
Go	%	Dividendo
Haskell	mod	Divisor
	rem	Dividendo
J	|~	Divisor
Java	%	Dividendo
JavaScript	%	Dividendo
Just Basic	MOD	Dividendo
Lua 5	%	Divisor
Lua 4	mod(x,y)	Divisor
Liberty Basic	MOD	Dividendo
MathCad	mod(x,y)	Divisor
Maple (software)	e mod m	Divisor
Mathematica	Mod	Divisor
Microsoft Excel	=MOD()	Divisor
MATLAB	mod	Divisor
	rem	Dividendo
Oberon	MOD	Divisor
Objective Caml	mod	Dividendo
Occam	\	Dividendo
Pascal (Delphi)	mod	Dividendo
Pascal (ISO-7185 and ISO-10206)	mod	Euclídea
Perl	%	Divisor
PHP	%	Dividendo
PL/I	mod	Divisor (ANSI PL/I)
PowerBuilder	mod(x,y)	?
PowerShell	%	Dividendo
Prolog (ISO 1995)	mod	Divisor
	rem	Dividendo
Python	%	Divisor
RealBasic	MOD	Dividendo
R	%%	Divisor
RPG	%REM	Dividendo
Ruby	%, modulus()	Divisor
	remainder()	Dividendo
Scheme	modulo	Divisor
	remainder	Dividendo
Scheme R6RS	mod	Euclídea
	mod0	Más cercano a cero
SenseTalk	modulo	Divisor
	rem	Dividendo
Smalltalk	\\	Divisor
SQL (SQL:1999)	mod(x,y)	Dividendo
Standard ML	mod	Divisor
	Int.rem	Dividendo
Stata	mod(x,y)	Euclídea
Tcl	%	Divisor
Torque Game Engine	%	Dividendo
Turing (programming language)	mod	Divisor
Verilog (2001)	%	Dividendo
VHDL	mod	Divisor
	rem	Dividendo
Visual Basic	Mod	Dividendo
x86 Assembly	IDIV	Dividendo
ADEP_AUTO language	MODULO(x,y)	Divisor

También existe el mismo problema relacionado con la operación equivalente en los reales (flotantes). Esta es la tabla en este caso.

Lenguaje	Operador	El resultado tiene el mismo signo que
C (ISO 1990)	fmod	?
C (ISO 1999)	fmod	Dividendo
	remainder	Más cercano a cero
C++	std::fmod	?
C#	%	Dividendo
D	%	?
Common Lisp	mod	Divisor
	rem	Dividendo
Go	math.Fmod	Dividendo
Haskell (GHC)	Data.Fixed.mod'	Divisor
Java	%	Dividendo
JavaScript	%	Dividendo
Objective Caml	mod_float	Dividendo
Perl	POSIX::fmod	Dividendo
PHP	fmod	Dividendo
Python	%	Divisor
	math.fmod	Dividendo
Ruby	%, modulus()	Divisor
	remainder()	Dividendo
Scheme R6RS	flmod	Euclídea
	flmod0	Más cercano a cero
Standard ML	Real.rem	Dividendo

Bueno. Entonces. Al final. ¿Cómo sé si un número es impar o no? Lo mejor es aprovechar que el resto cero es igual en todas las implementaciones y hacer algo así.

bool impar(int n)
{
 return (n%2) != 0;
 }

miniSL parte 12 - Limitaciones y uso del recolector de basura

Hasta ahora hemos hablado del montículo, las celdas y  cómo crearlas. Sin embargo, no hemos visto cómo se usa la recolección de basura implementada y, tampoco, sus limitaciones.

La recolección de basura sirve para detectar celdas no usadas y marcarlas como tales. La forma de hacerlo es muy sencilla. Tenemos un conjunto raíz que son celdas que sabemos a ciencia cierta que son usadas de forma. A partir de ese conjunto exploramos qué otras celdas usan. El resto son celdas sin usar. Este algoritmo se denomina mark and sweep (marca y barre). El código para esto se adelantó en la parte 8, pero queda por saber cómo se usa exactamente.

Lo importante son las limitaciones del algoritmo de recolección de basura implementado en miniSL. Son las siguientes.

• El algoritmo de mark and sweep usado detiene la ejecución. Aunque este es el menor de nuestros problemas como veremos más adelante.
• El algoritmo usado sólo usa el entorno global (lo veremos con más detalle en la siguiente parte) como el conjunto raíz. Esto quiere decir que no podemos llamar el algoritmo en medio de la ejecución del código porque la celda que contiene el entorno local de la función no forma parte del conjunto raíz.
• En concreto, no podríamos lanzar el recolector de basura cuando notemos que nos hemos quedado sin memoria. Por ejemplo, en el caso de entrar en la línea 6 de la función Script::CreateCell(). Por esa razón, hemos de reservar una nueva celda y no reutilizar una antigua.
• La estructura del recolector de basura no es incremental. El algoritmo mark and sweep usa dos conjuntos de celdas: las marcadas (usadas) y las no marcadas (no usadas). Para poder hacer un recolector de basura incremental hacen falta tres conjuntos llamados de celdas blancas, grises y negras.
• Debido a todo esto, el propio miniSL no puede llamar al recolector de basura. Lo tiene que hacer la aplicación que use el script.

Ni que decir tiene que estas limitaciones hacen el lenguaje miniSL inútil en la vida real, pero simplifican muchísimo el código. Nosotros lo que haremos será llamar al recolector de basura en cada ciclo del bucle de lectura-evaluación-impresión o (REPL).
Este bucle será ahora:

• Lectura de una expresión.
• Evaluación de la expresión.
• Impresión del resultado.
• Recolección de basura.

Veremos el REPL en la parte 32, ya que antes hemos de definir cómo evaluamos y cómo leemos una expresión. Hasta ahora sólo sabemos imprimir las celdas.

En la siguiente entrada nos centraremos en el conjunto raíz de nuestro recolector de basura. Es decir, en el entorno global que contiene los símbolos definidos más generales.

Grados de confianza gatunos

Como bien saben los que me siguen, de vez en cuando hago una excursión por temas no informáticos. Esta vez en el mundo de los gatos. Responderé a la pregunta ¿cómo sé si mi gato tiene confianza en mí o no?

El gato amistoso de Shu es de grado 4.

Cierta persona me dijo una vez que los grados son los siguientes.

1. Desconfiado. El gato se aleja si te acercas a él. No tendrá menos de dos o tres metros de distancia entre tú y él.
2. Próximo. Te puedes acercar a él, pero no se dejará tocar. O sólo se dejará tocar muy poco tiempo. 
3. Mimoso. El gato se deja tocar, acariciar y rascar, pero sin hacer cosas raras. Cualquier movimiento, mirada, ruido, etc. hará que salga pitando. En general no es buena idea mirar a los ojos a los gatos. Es mejor parpadear lentamente para decir "no te estoy cazando".
4. Escalador. Una vez que está cómodo cerca de ti, el gato puede querer subirse encima. Generalmente no lo intentará cuando estés de pie. Podrá ser sobre las rodillas o sobre la barriga si estás tumbado.
5. Observador. El gato se deja coger y deja que te pongas en pie con él. Si al gato no le gusta, se echará al suelo. Algunos gatos incluso te piden que los cojas poniendo sus patitas en tus rodillas. Realmente, una vez que se acostumbran, les encanta observar las cosas desde arriba.
6. Confiado. El gato se deja coger y deja que andes con él. Algunos gatos pueden llegar incluso a abrazarse a ti. Este es el grado máximo, pero cualquier tontería hará que el gato pierda confianza y luego es difícil volverla a ganar. Así que mucho mimo.

Nota final: El ronroneo no es muy fiable. No siempre significa que el gato está contento. También puede ser que quiera algo, o que se haya olvidado que está ronroneando y siga ahí runrun.

Infija, prefija, postfija y circunfija

Expresión infija. Es la usual. El operando (+) aparece entre los operadores (1 y 2).

[$$ 1 + 2 $$]

Expresión prefija. El operador aparece antes de los operadores.

[$$ + 1 2 $$]

Es la forma natural en el lenguaje de programación Haskell. Variante de esta es también [$ +(1,2) $] donde es más natural usar un operador alfabético como [$ f(1,2) $].

Expresión postfija. El operador aparece detrás de los operadores.

[$$ 1 2 + $$]

Expresión circunfija. El operador rodea a los operadores. Esto es típico en los paréntesis.

[$$ (1 2) $$]

Es la forma usual del LISP. Otra variante es con los operadores separados por coma o similar.

Frecuencia fraccional

El problema

Supongamos que tenemos un evento que se dispara a una frecuencia dada [$f_0$] (por ejemplo, una frecuencia de muestreo). Llamaremos eventos básicos a estos eventos. Es fácil comprobar que puedo generar otros eventos derivados a partir de estos eventos básicos. Bastará tomar una frecuencia divisora [$f=f_0/k$] y lanzar un evento derivado cada [$k$] eventos básicos. Por ejemplo, si [$k=3$] tengo un evento derivado cada tres eventos básicos.

Si trazamos el número de evento básico en el eje de abscisas y el número de evento derivado en el eje de ordenadas, obtenemos una línea. En este caso, de pendiente [$1/3=f/f_0$].

¿Pero qué ocurriría si la frecuencia es una fracción cualquiera de [$f_0$] y no exactamente un divisor?

El algoritmo

En este caso a veces tendremos que contar [$k$] eventos básicos y otras veces [$k+1$]. No obtenemos una frecuencia exacta, pero en promedio sí será la [$f$] deseada. Pagamos un jitter por tener una frecuencia que no es divisora de la frecuencia básica.

Lo interesante aquí es que seguimos obteniendo una recta, aunque ya no está centrada en el origen y tampoco tiene una pendiente [$1/k$]. Si llamo [$0\le r<1$] a la altura de intersección con el eje de ordenadas y [$t$] al número de evento básico (en definitiva, es el tiempo transcurrido) mi recta es

[$$y=r+\frac{f}{f_0}t$$]

El primer evento derivado se tendrá que lanzar cuando la recta corte a la línea [$y=1$]. Es decir

[$$1=r+\frac{f}{f_0}t$$]

Debido a que el resultado puede no ser un número entero, hemos de redondear al siguiente evento básico que llamaremos [$t_1$].

[$$t_1=\left \lceil \frac{1-r}{f/f_0} \right \rceil$$]

Ya sabemos cuándo lanzar el siguiente evento derivado: será en el evento básico [$t_1$]. Lo interesante aquí es que puedo trasladar de nuevo todo al origen de coordenadas y calcular el valor [$r$] para el siguiente evento derivado empezando desde cero. Usando exactamente las mismas ecuaciones.

Este nuevo valor de [$r$], que llamaré [$r_1$], será el valor de [$r$] en [$t_1$] pero restando [$1$] para volver al origen de coordenadas.

[$$r_1=r+\frac{f}{f_0}t_1-1$$]

Con lo que el algoritmo sería

1. Iniciamos con [$r=0$] y el valor [$f=f_0$] de frecuencia que deseemos.
2. Calculamos [$t_1$] y [$r_1$] a partir del valor de [$r, f$] y [$f_0$].
3. Esperamos [$t_1$] eventos básicos antes de lanzar un evento derivado.
4. Hacemos [$r \leftarrow r_1$] y vamos al paso 2

La implementación

Este algoritmo está muy bien, pero hay un detalle de implementación. Tanto el valor [$f/f_0$] como el valor [$r$] están en el intervalo [$[0,1)$]. No es descabellado usar una notación de coma fija para representarlo en [$n$] bits. Entonces, usando el subíndice [$p$] para la coma fija,

[$$f_p=2^n \frac{f}{f_0} $$]
[$$r_p=2^n r$$]

Y las ecuaciones quedan

[$$t_1=\left \lceil \frac{2^n-r_p}{f_p} \right \rceil $$]
[$$r_1=r_p+f_p t_1-2^n$$]

La ecuación de [$t_1$] tiene un problema: el redondeo por exceso. Generalmente las divisiones enteras tienen redondeo por defecto. Es fácil hacer la conversión sumando el denominador menos uno.

[$$t_1=\left \lceil \frac{2^n-r_p}{f_p} \right \rceil=\left \lfloor \frac{2^n-r_p+f_p-1}{f_p} \right \rfloor $$]

Y un paso más es darnos cuenta que [$2^n-1-r_p$] no es más que el complemento a uno de [$r_p$] que notaremos [$ \sim r_p $].

[$$t_1=\left \lfloor \frac{\sim r_p+f_p}{f_p} \right \rfloor $$]

La ecuación de [$r_1$] puede simplificarse también ya que sumar o restar [$2^n$] no tiene efecto en aritmética módulo [$2^n$] por lo que llegamos a

[$$r_1=r_p+f_p t_1$$]

El algoritmo sigue siendo el mismo.