1

Las máquinas TIM y Spineless-Tagless G

2

TIM: La máquina de tres instrucciones

En principio TIM parece ser una máquina de reducción de grafos muy diferente a las que hemos visto. Sin embargo una máquina G puede relativamente fácil ser traducida a TIM.

TIM fue inventada por Fairbairn and Wray [FW87].

Aquí haremos una presentación muy superficial del funcionamiento de la máquina, basándonos básicamente en un ejemplo.

3

Cómo trabaja TIM

Considere la siguiente definición: f x y = g E1 E2

donde E1 y E2 son dos expresiones arbitrarias y g es algún otro SC.

La máquina G efectuará la siguiente reducción al encontrar una aplicación de f:

@ @ @ y => @ E2

f x g E1

E1 y E2 son los grafos de las respectivas expresiones, los que tienen que ser construídos en el heap (por código generado por C). Si g no utiliza el primer argumento, por ejemplo, la construcción del grafo es trabajo perdido.

4

Flattening

El paso 1 de la transformación es el siguiente.

Supongamos que reemplazamos la definición de f por la siguiente:f x y = g (c1 x y) (c2 x y)

c1 x y = E1

c2 x y = E2

Inventamos dos funciones auxiliares. Esta definición de f es equivalente a la anterior, pero independientemente de cuán complicada sea E1, el único trabajo efectuado durante la reducción de f es construír el grafo de (c1 x y).

Pero para una máquina G hay aún algo más para ganar. Con la primer definición E1 será compilada usando el esquema C, no pudiendo sacar ventajas de las optimizaciones introducidas con E.

5

Flattening (2)

Pero con la segunda definición la expresión E1 es ahora la parte derecha de la definición de un SC, por lo tanto las optimizaciones pueden ser aplicadas (pensar, por ejemplo, en que E1 sea la expresión (x + y) * (x - y)).

Por supuesto que E1 y E2 podrían a su vez contener expresiones

grandes que a su vez serán compiladas con C (por ejemplo,

suponer que E2 es (h E3 E4)). Por lo tanto la optimización

deberá ser aplicada nuevamente a las partes derechas de c1 y

c2.

El resultado final es un programa plano, así llamado por que

ninguna expresión tiene una estructura anidada.

6

TuplingLa siguiente observación a hacer es que c1 y c2 son los dos aplicados

a x e y. Por lo tanto tenemos que construír los grafos de (c1 x y) y (c2 x y) antes de llamar a g. Si c1 y c2 tuvieran muchos argumentos el grafo podría hacerse realmente grande. Los dos grafos son tan similares que uno podría imaginarse una forma de evitar duplicación al construír los mismos y por lo tanto reducir la cantidad de nodos alojados en el heap.

Esta idea puede expresarse con la siguiente transformación:f x y = let tup = (x,y)

in g (c1 tup) (c2 tup)

c1 (x,y) = E1

c2 (x,y) = E2

7

Tupling (2)

La idea es que f primero empaqueta sus argumentos en una tupla, y luego pasa esta tupla a c1 y c2.

Con esta definición de f la reducción ahora se puede ilustrar de la siguiente forma:

@ @ @ @ y => @ c2

f x g @ c1 x

y

8

No espina

En la figura anterior se puede notar que los argumentos que son apuntados desde la espina son de la forma (c tup), para algun SC c y tupla tup. Durante la reducción lo que se hace es construír un stack de punteros a esos argumentos. Pero como ahora estos argumentos son todos de la misma forma lo que podríamos hacer en vez es pushear en el stack la raíz misma de los argumentos.

Entonces luego de la reducción el stack luciría como sigue:

c2

c1 x

y

9

No espina (2)Cada item de la espina es ahora un par formado por un

puntero a código y un puntero a una tupla. Este par puede ser entendido como un nodo de aplicación.

Cuando la función f se ejecuta los argumentos x e y ya están en el stack, por lo tanto la tupla x e y es en realidad una tupla de pares puntero a código y puntero a tupla.

Un par (puntero a código, puntero a tupla) se llama una clausura.

Una tupla de estas clausuras es llamada un frame.

Un puntero a un frame es llamado puntero de frame.

Notar que ya no hay más espina en el heap, el stack es la espina de la expresión que se está evaluando.

10

Un ejemploConsideremos la función compose2 con la siguiente definición:compose2 f g x = f (g x x)

La forma aplanada de compose2 seríacompose2 f g x = f (c1 g x)

c1 g x = g x x

Cuando compose2 se comience a ejecutar sus tres argumentos se hallarán en el tope del stack:

código-f | frame-f

código-g | frame-g

código-x | frame-xx

g

f

11

Un ejemplo (2)Lo primero a hacer es formar el frame de estos 3 argumentos en el

heap, y a su vez removerlos del stack. Guardaremos un puntero a este nuevo frame en un registro especial, el puntero de frame. Esto es efectuado por la instrucción Take 3 .

El estado de la máquina ahora es de la siguiente forma:

código-x | frame-x

código-g | frame-g

código-f | frame-ff

g

x

|

ptro. de frame

12

Un ejemplo (3)Ahora prepararemos los argumentos para f. De hecho hay sólo

uno, (g x x), y lo que haremos será pushear una clausura para esta expresión en el tope del stack. El puntero de frame para la clausura es el puntero corriente, por lo tanto la instrucción sólo necesita proveer una etiqueta de código:

Push (Label “c1”)

Finalmente lo que queremos hacer es “saltar” a f. Como f es un argumento de compose2, ésta será representada por una clausura en el frame corriente. Lo que debemos hacer entonces es tomar esta clausura, cargar su puntero de frame en el registro de puntero de frame y su código de puntero en el “program counter”. Todo esto es efectuado por la instrucción:

Enter (Arg 1)

13

Un ejemplo (4)

Luego de esta instrucción el estado de la máquina será el siguiente:

código-x | frame-x

código-g | frame-g

código-f | frame-ff

g

x

|

ptro. de frame: frame-fprogram ctr.: código-f

c1 |

Entonces, el cuerpo de compose2 consiste de sólo estas 3 instrucciones: compose2: Take 3 -- (3 argumentos) Push (Label “c1”) -- clausura para (g x x) Enter (Arg 1) -- f es el argumento 1

14

Un ejemplo (5)Todavía nos falta resolver como procesar la etiqueta c1.

Cuando la clausura para (g x x) sea necesaria, ésta será entrada con la instrucción Enter, de tal forma que el program counter apuntará a c1, y el puntero de frame original, el que contiene a f, g y x. Lo único que resta es preparar los argumentos para g, o sea x, y luego entrar g:

c1: Push (Arg 3) -- x es el argumento 3

Push (Arg 3) -- x de nuevo

Enter (Arg 2) -- g es el argumento 2

Es claro porqué se llama TIM la máquina, hay 3 instrucciones predominantes (aunque Push y Enter tienen distintos modos de direccionamiento).

15

ResumenEs TIM mejor máquina que G?

Comparar costo de instrucción Take con G Mkap?

La única medida clara es el consumo de heap.

Ahora exploraremos otro modelo de evaluación el que sugiere un diseño de evaluador que combina spectos de G y TIM.

La máquina Spineless Tagless G adopta la característica

“no-espina” y el mecanismo de actualización de TIM, pero su stack consiste de punteros a nodos de heap como en G (y no a pares código-frame como en TIM).

16

STG: un modelo alternativo de máquina

Presentaremos brevemente otra máquina abstracta para lenguajes funcionales perezosos. El diseño de la misma contiene un conjunto considerable de características poco usuales:

• El lenguaje de la máquina abstracta es un conciso lenguaje funcional. A cada construcción del mismo se le puede dar una interpretación operacional directa, la que se puede formalizar usando un sistema de transición de estados.

• Los objetos del heap, tanto WHNF como computaciones suspendidas se representarán en forma uniforme, con un puntero de código en el primer campo de los mismos. Con esta representación no hará falta examinar tags para determinar el flujo de ejecución. Se efectúan directamente saltos al código apuntado por el puntero. De ahí el nombre de tagless.

17

STG: un modelo alternativo de máquina (2)

• En esta máquina se presenta con gran precisión el tratamiento de objetos estructurados en forma eficiente.

• La máquina manipula valores unboxed, lo que como ya hemos visto es esencial para implementar eficientemente operaciones aritméticas.

• No es necesario efectuar el proceso de lambda lifting. En vez se identifican las variables libres que ocurren en abstracciones, dejendo a estas últimas en su lugar.

• La máquina se adapta fácilmente a la implementación de reducciones paralelas.

18

Representación de clausuras

El heap de la máquina está constituído por objetos de dos clases: WHNFs (values) y suspensiones (thunks). WHNFs pueden ser clasificadas además en dos clases: funciones y objetos estructurados. Un valor, naturalmente, puede contener suspensiones (celdas Cons, por ejemplo).

En lo que sigue se usará el término clausura para referirse tanto a valores como a suspensiones. Se considerarán a continuación distintas formas en las que clausuras pueden ser representadas, contrastando además la máquina STG con otros diseños.

19

Representación de funcionesLa forma más compacta de representar una función es como un

bloque estático de código junto con los valores de sus variables libres. (Clausura)

La representación física directa de una clausura es un puntero a un bloque contiguo de memoria de heap, la que consiste en un puntero de código, que apunta al código, seguido de (punteros a) valores de las variables libres.

Para efectuar la computación, a un registro distinguido, el puntero de environment, se lo hace apuntar a la clausura y entonces el código es ejecutado. Esta operación se llama entrar una clusura. El código puede acceder a las variables libres usando offsets del puntero de environment.

20

Representación de thunks

En un lenguaje perezoso valores son pasados a funciones y cargados en objetos estructurados sin ser evaluados. Al igual que valores funcionales, estos valores representan una ejecución suspendida y pueden ser también representados como clausuras. Para evaluarlas se las fuerza.

STG usa el modelo self-updating. En este modelo la actualización de código es responsabilidad del código mismo (no como G que actualiza luego de cada reducción). El código para forzar una clausura simplemente pushea una continuación en el stack y luego entra la clausura. Si la clausura es una suspensión entonces luego de la evaluación se actualiza la misma, si no simplemente se devuelve el valor computado

21

Compilación de aplicación de funciones

Al igual que en G y en TIM, STG trata la aplicación de funciones de la siguiente forma: pushea el argumento en el stack de evaluación y hace un tail-call (o entra) la función.

No existe un return asociado a la finalización de la evaluación. Este modelo es llamado push-enter.

El costo principal de este modelo es que el link entre el cuerpo de función y un frame de activación se pierde. En lenguajes estrictos cuando se encuentra la aplicación de una función, el compilador puede alojar un frame y desactivarlo luego de la ejecución. En el modelo push-enter simplemente se pushean los argumentos. No se puede identificar precisamente cuando un frame debe ser alojado o desactivado.

22

Estructuras de datosObjetos estructurados son construídos usando constructores y

desempaquetados usando case. El mecanismo general usado para objetos definidos por el usuario es exactamente el mismo que el usado para los tipos estructurados primitivos.

Como se ha dicho, objetos estructurados son representados como clausuras.

El modelo self-updating usado por STG hace uso del hecho de que un objeto estructurado es solamente forzado por una expresión case. Una celda Cons, si usamos registros para almacenar la head y tail, nunca debe ser alojada en el heap.

Esta es una optimización muy ventajosa (muchas funciones retornan objetos estructurados).

23

El lenguaje de STGLas características particulares del código STG son las

siguientes:

• Todos los argumentos de funciones y constructores son variables simples o constantes. Esto se corresponde con el, hecho de que los argumentos son preparados (ya sea construyendo una clausura o evaluándolos) previamente al llamado. (lets para argumentos no triviales).

• Todos los constructores y operaciones primitivas son saturados. Esto simplifica la semántica operacional del lenguaje. (expansión )

• Pattern matching es efectuado sólo por expresiones case, y los patterns son simples (al igual que en G).

24

El lenguaje de STG (2)• Existe una forma especial de ligadura. El lenguaje incluye una

forma de ligadura con la siguiente forma general:

f = {v1, ... , vn} \ {x1, ... , xm} -> e

Con la siguiente lectura: f es ligado a una clausura alojada en el heap, la que contiene un puntero de código y (punteros a las) variables libres v1, ... , vn . Esta clausura representa la función (\

x1, ... , xm -> e), cuando su código es ejecutado un registro especial apuntará a la clausura permitiendo así el acceso a los valores de sus variables libres.

La bandera de actualización () de una forma lambda indica si la clausura debe ser actualizada o no ({u,n}).

25

Traducción a lenguaje STG

En general, traducción a lenguaje STG comprende las siguientes transformaciones:

• Reemplazar aplicación binaria por múltiple aplicación:

(... (( f e1) e2) ...) => f {e1, ... , en}

STG aplica una función a todos los argumentos disponibles

• Saturar todos los constructores y operadores primitivos:

c {e1, ... , en} => \ y1 ... ym . c {e1, ... , en , y1, ..., ym }

donde c es un constructor u operador primitivo de aridad n + m.

• Dar un nombre a todo argumento de función no-atómico y a toda abstracción introduciendo una expresión let.

• Convertir la parte derecha de una declaración let a una forma lambda, agregando variables libres y la información de actualización (bandera).

26

Un ejemploLa función (Samba) map definida a continuación: map f [] = []

map f (x:xs) = (f x) : map f xs

se traduce al siguiente código STG:map = {} \n {f , xs} ->

case xs of

Nil {} -> Nil {}

Cons {y, ys} -> let fy = {f, y} \u {} -> f y

mfy = {f, ys} \u {} -> map {f, ys}

in Cons {fy, mfy}