1

Compilación, pereza y expresiones let(rec)

2

Compilando un programa

Describiremos un compilador para la máquina minimal usando un conjunto de esquemas de compilación.

Cada supercombinador será compilado con el esquema SC, el que a su vez está definido en función de un esquema R, que es el que efectivamente genera código-G. Este esquema genera una secuencia de instrucciones que respeta el esquema visto en la clase pasada: primero la secuencia de instrucciones para instanciar el cuerpo del supercombinador, y luego las instrucciones Slide y Unwind.

El grafo del cuerpo será generado por la función C.

3

Compilando un programa (2)

SC [d] es el código-G generado para la definición d de un supercombinador:

SC [f x1 ... xn = e ] = R [ e ] [ x1 xn nn

R [ e ] genera código que instancia la expresión e en environment , para un supercombinador de aridad n, y luego procede a desplegar el stack:

R [ e ] n = C [ e ] ++ [Slide n + 1, Unwind]

4

Compilando un programa (3)

Finalmente, C [e ] r genera código que construye el grafo de la expresión e en environment , dejando un puntero al resultado en el tope del stack:

C [ f ] = [Pushglobal f] f supercombinador

C [ x ] = [Push ( x) ] x variable local

C [ i ] = [Pushint i] i es un número

C [ f e ] = C [ e ] ++ C [ f ] +1 ++ [Mkap]

donde+n x = ( x) + n

5

Un ejemplo de compilación

Veamos ahora como ejemplo el código que se genera para el combinador K.

Comenzaremos evaluando la expresión:

SC [ “K” , [“x”, “y”] , Evar “x”]

Un paso de reducción nos da:

R [Evar “x”] [ x |-> 0 ... y |-> 1 ] 2

y uno más

C [Evar “x”] [ x |-> 0 ... y |-> 1 ] ++ [Slide 3, Unwind]

6

Un ejemplo de compilación

Para compilar el cuerpo del supercombinador efectuamos un lookup de x, que está en el tope del stack. Entonces generamos código para hacer una copia del tope del stack usando la instrucción Push 0.

[Push 0, Slide 3, Unwind]

7

Una máquina lazy

Introducimos ahora un pequeño cambio a la máquina para poder hacerla perezosa, ya que hasta ahora la máquina no sobreescribe la raíz del redex antes de efectuar el unwinding. Si éste estuviera compartido evaluaciones podrían ser repetidas.

En la nueva máquina lo que haremos será sobreescribr la raíz de la expresión original con un nodo de indirección, el que apuntará a la nueva instancia construída.

El efecto es que la máquina “recuerda” el valor calculado.

Para eso introduciremos las instrucciones Update y Pop.

8

Una máquina lazy

Hasta ahora el código para cada supercombinador termina con la secuencia [Slide n + 1, Unwind], donde n es la aridad del SC. Para capturar la noción de actualización reemplazaremos esta secuencia con

[Update n, Pop n, Unwind]

La instrucción Update se encarga de sobreescribir la raíz del redex.

La instrucción Pop se usa para remover los argumentos del stack que ya no son necesarios.

9

Una máquina lazy (2)

@

@ enen-1

@f e1

e

e

Antes de ejecutar Slide (n+1) Después

10

Una máquina lazy (3)

@

@ enen-1

@f e1

e

#

@

f

ei) Antes de Update n ii) Después de Update n

#

e

iii) Después de Pop n

11

Update, Pop y Unwind

Update n : i a : a0 : ... : an : s h m => i a0 : ... : an : s h[an:NInd a] m

Pop n : i a0 : ... : an-1 : s h m => i s h m

El efecto de Update n es sobreescribir el n+1-ésimo item del stack con un nodo de indirección al item en el tope.

Pop n simplemente remueve n items del stack.

[Unwind] a0 : s h[a0:NInd a] m => [Unwind] a : s h m

12

Modificación al esquema R

Para que el compilador se comporte como hemos especificado, ahora debemos introducir una primer modificación al esquema de compilación R:

R [ e ] genera código que instancia la expresión e en environment , para un supercombinador de aridad n, y luego procede a desplegar el stack:

R [ e ] n = C [ e ] ++ [Update n, Pop n, Unwind]

13

Expresiones let(rec)

Ahora extenderemos al compilador y la máquina que hemos construído para que aceptan expresiones let(rec) en el cuerpo de un supercombinador.

Estas expresiones son definidas en el tipo Expr a por el constructor ELet, que toma como argumentos un boolean que indica si las definiciones son recursivas o no, las definiciones y la expresión en que las definiciones serán usadas.

Antes de efectuar la extensión, definiremos una forma más eficiente de acceder a las variables del stack.

14

Acceso a argumentos

Supongamos que el proceso de unwinding ha encontrado un nodo f de SC y que éste toma n argumentos. En la máquina que estamos considerando, el stack luciría de la siguiente forma:

@

@ enen-1

@f e1

@

15

Acceso a argumentos (2)En la nueva versión de la máquina el stack se verá

modificado como sigue:

@

en

@f e1

@

@e2

Los n elementos al tope delstack ahora apuntan directa-mente a las expresiones e1...en.

El punto importante es que aho-ra tenemos acceso rápido a las variables. Esto mejora la eficien-cia de acceso a las expresiones que sustituirán a los paráme-tros formales.

Notar puntero a raíz.

16

Modificación de instruccionesUna vez que elegimos modificar el stack también tendremos

que modificar algunas de las instrucciones.

Las afectadas son las instrucciones Push y Unwind.

La instrucción Push no necesitará más mirar “a través de los nodos de aplicación”.

Push n : i a0 : ... : an : s h m => i an : a0 : ... : an : s h m

17

Modificación de instrucciones (2)

La otra modificación requerida es que Unwind debe reacomodar el stack. Este reacomodamiento es requerido siempre que un SC con suficientes argumentos es localizado al tope del stack.

La nueva regla de transición para Unwind es:

[Unwind] a0 : ... : an : s h[a0:NGlobal n c, m a1: NAp a0 a´1

... an: NAp an-1 a´n ]

=> c a´1 : ... : a´n : an : s h m

18

Variables localmente ligadas

Retornamos a la implementación de expresiones let(rec), considerando primero el caso no recursivo.

Las variables x1 ... xn en la expresión let x1= e1 ... xn = en in e

pueden ser tratadas de la misma forma que lo son los argumentos a combinadores, una vez que las expresiones e1

... en han sido creadas.

Es decir accedemos a las variables x1 ... xn por medio de offsets en el stack, usando el environment para registrar su posición.

Supongamos que el código para construír las definiciones locales es Code. La siguiente secuencia de acciones será entonces necesaria:

19

Variables localmente ligadas (2)

e1

en

e1

en

e

e

Inicialmente

Después deCode Después de

construír e

Al final

20

Variables localmente ligadas (3)Como hemos agregado n nuevas variables en el stack, esto

debe ser considerado en el esquema de compilación. El código para construír las ligaduras locales (Code) simplemente construirá el código de cada ei dejando las direcciones de esas piezas de grafo en el stack.

Luego de construír el cuerpo de la expresión e, el que puede usar cualquiera de las xi, los punteros a las expresiones ei deben ser removidos del stack. Esto se logrará haciendo uso de una instrucción Slide.

La situación con definiciones locales recursivas es más complicado, ya que cada una de las ei debe ser compilada de tal forma que todas las variables xi estén en alcance.

21

Variables localmente ligadas (4)Para lograr esto último se crearán nodos vacíos en el grafo

dejando además punteros a ellos en el stack.

Luego cada expresión ei es compilada usando el mismo mapeo de variables que el usado en el caso no recursivo.

Al final de cada código compilado para las expresiones pondremos un Update, cuya función será sobreescribir el nodo vacío con la pieza correspondiente de grafo. Esto último lo lograremos usando una nueva instrucción, Alloc

n, la que creará n nodos vacíos (que serán representados con el símbolo ?).

El proceso que se ilustra a continuación deberá ser repetido hasta que cada una de las ei sea procesada.

El código para e es compilado en forma similar al caso no recursivo.

22

Variables localmente ligadas (5)

?

?

?

?

e1Alloc n

Después deconstruír e1

#

?

e1

Después deactualizar e1

Inicialmente

23

Alloc

Para esta versión de la máquina entonces necesitaremos agregar la instrucción Alloc, que crea n lugares en el heap. Usaremos estos lugares para marcar donde guardaremos las expresiones ligadas en las definiciones.

Estos nodos son inicialmente creados como nodos de indirección que apuntan a una dirección ilegal de heap: hNull (esto no importa ya que esos nodos serán sobreescritos).

Alloc n : i s h m => i a1 : ... : an : s h [a1 : Nind hNull m ... an : Nind hNull]

24

Modificación del esquema C

C [ let x1 = e1; ... ; xn = en in e ]

= C [ e1 ] ++ ... ++

C [ en ] n ++

C [ e ] ’ ++ [Slide n] ’ =n [ x1 |-> n-1, ... , xn |-> 0]

C [ let rec x1 = e1; ... ; xn = en in e ]

= [Alloc n] ++

C [ e1 ] ’ ++ [Update n-1] ++ ... ++

C [ en ] ’ ++ [Update 0]

C [ e ] ’ ++ [Slide n] ’ =n [ x1 |-> n-1, ... , xn |-> 0]

25

Compilando Y

Y f = letrec x = f x in x

SC [ “Y”, [“f “] , ELet True [( “x”, EAp (Evar “f”) (Evar “x”))] (Evar “x”) ]

R [ELet True [( “x”, EAp (Evar “f”) (Evar “x”))] (Evar “x”) ] [(“f “, 0)] 1

C [ELet True [( “x”, EAp (Evar “f”) (Evar “x”))] (Evar “x”) ] [(“f “, 0)] ++

[Update 1, Pop 1, Unwind]

[Alloc 1] ++

C [EAp (Evar “f”) (Evar “x”)] p ++ [Update 0] ++

C [Evar “x”] p ++ [Slide 1] ++

[Update 1, Pop 1, Unwind]

where p = [(“x”, 0) , (“f “, 1)]

26

Compilando Y (2)

[Alloc 1] ++

[Push 0, Push 2, Mkap] ++ [Update 0] ++

[Push 0] ++ [Slide 1] ++

[Update 1, Pop 1, Unwind]