1
Supercombinadores y lambda-lifting
2
Cómo sustituir eficientemente
La función instantiate definida previamente implementa una sustitución interpretada. Esta función es bastante ineficiente, a saber:
i) en cada nodo del cuerpo de la abstracción se debe efectuar un análisis de casos.
ii) en cada nodo variable se debe testear si es el parámetro formal
iii) nuevas instancias de subexpresiones que no contengan ocurrencias del parámetro formal serán construída cuando puedan ser segura y beneficiosamente compartidas (full lazyness)
Solución: Dejemos que un compilador efectúe estos tests y compile cada abstracción a una secuencia de instrucciones que implemente body[var := value]
3
Complicaciones
Lo anterior funciona perfectamente para expresiones como \ x -> (sub (mul x x) 3),
pero consideremos la siguiente abstracción
f = \ x -> \ y -> - y x y la aplicación (f 3) = \ y -> - y 3
i) obtenemos una nueva abstracción, lo que correspondería a una secuencia de instrucciones par al expresión \ y -> - y 3
ii) por cada aplicación de f obtenemos una abstracción diferente dependiendo del argumento
No parece razonable pensar en que seremos capaces de compilar f a una secuencia fija de instrucciones.
4
Complicaciones (2)
Cuál es el problema? La ocurrencia libre de x en \ y -> - y x.
Posibles soluciones:
i) permitir que en el código compilado se pueda hacer referencia, y por lo tanto acceder, a los valores asignados en un environment a las variables libres que ocurran en el código (SECD, CAM, TIM).
ii) transformar las abstracciones de tal forma que no haya necesidad de hacer uso de un environment, es decir, transformar toda abstracción en un supercombinador
Esta transformación se llama lambda-lifting.
5
Sustitución simultánea
Por qué reducir la expresión (\ x -> \ y-> - y x) 3 4 efectuando una aplicación a la vez y no calcular (- y x) [x:=3, y:=4] ?
Con sustitución simultánea uno gana en:
• menos estructura intermedia es generada (la expresión \ y -> - y 3 no tiene que ser creada)
• no se generan problemas con variables libres
Entonces, la aplicación de una abstracción de aridad n podría retardarse hasta que n argumentos sean provistos.
6
Una estrategia de compilación basada en supercombinadores
Supercombinadores serán nuestra unidad de compilación. La estrategia a aplicar será la siguiente:
i) Transformar abstracciones que ocurren en el programa a supercombinadores
ii) Darle un nombre a estos supercombinadores
iii) Transformar el programa a la forma
Definiciones de supercombinadores
Expresión a ser evaluada
7
Una estrategia de compilación basada en supercombinadores (2)
iv) Compilar cada supercombinador a un código que efectúe una reducción gráfica de un supercombinador.
Ejemplo: (\ x -> \ y -> - y x) 3 4
$XY x y = - x y
$XY 3 4
8
Transformando abstracciones en supercombinadores
Ejemplo: (\ x -> ( \ y -> + y x) x) 4 ( x está libre en \ y ->)
i) abstraemos variable(s) libre(s)
\ y -> + y x => (\ x -> \ y -> + y x) x (supercombinador)
(\ x -> ((\ x -> \ y -> + y x) x ) x) ) 4
|-------- $Y -------|
|------------------$X -----------------|=>
$Y x y = + x y$X x = $Y x x
$X 4
9
Un algoritmo de lifteo
i) Elija cualquier abstracción que no contenga abstracciones
ii) Ligue todas sus variables libres y tómelos como parámetros extras (paso de -abstracción)
iii) Asígnele un nombre a la abstracción
iv) Reemplace la abstracción con el nombre elegido
v) Repita estos pasos hasta que no haya más abstracciones en la expresión
10
Eliminación de parámetros redundantes
Ejemplo: (\ x -> \ y -> - y x) 3 4 (ya es un SC pero...)
$Y x y = - x y$X x = $Y x
$X 3 4
$Y x y = - x y
(\ x -> $Y x) 3 4
por tenemos que $X = $Y
$Y x y = - x y
$Y 3 4
11
Ordenamiento de parámetrosCuando extraemos varias variables libres de una abstracción el orden
parecería no importar, sin embargo
\ y -> ... (\ x -> \ z -> + y (* x z))
$S x y z = + y (x z) $T y x = $S x y
(\ y -> ...($T y)
$S x y z = + y (x z)
(\ y -> ...(\ x -> $S x y)
$S y x z = + y (x z) $T y x = $S y x
(\ y -> ...($T y)
$S y x z = + y (x z)
(\ y -> ...(\ x -> $S y x)
$S y x z = + y (x z)
(\ y -> ...($S y)
xy yx
12
Ordenamiento de parámetros (2)
El ejemplo sugiere que tendríamos que ordenar las variables libres, de tal forma que aquellas que son ligadas más internamente en el término ocurran despúes en la lista de parámetros del supercombinador. Definiremos entonces un número léxico de nivel asociado a cada abstracción y variable
Def.
i) El número de nivel de una abstracción es uno más que el número de abstracciones que la encierran.
ii) El número de nivel de una variable es aquel de la abstracción que la liga.
Para maximizar las chances de aplicación de podemos entonces ordenar los parámetros en orden creciente
13
Supercombinadores recursivos
Supercombinadores pueden naturalmente ser recursivos, ya que ellos tienen un nombre que puede ser referenciado en el cuerpo.
Permitiremos que let y letrec ocurran en el cuerpo de un supercombinador. En particular, letrec será interpretado como una descripción textual de un grafo cíclico. Un combinador que contenga un letrec en su cuerpo se llama un combinador gráfico.
Cualquier grafo puede ser expresado por un letrec
@ a
c @ @ b
f 3
letrec a = c b b = c 3 c = f bin a
14
Lifting en presencia de letrecs
El algoritmo de lifting no tiene porqué ser modificado. Este proceso aún se sigue efectuando para abstracciones y no para letrecs. En el caso de que alguna abstracción contenga un letrec en su cuerpo la transformación dará lugar a un supercombinador con cuerpo gráfico.
Ahora, que número léxico debería ser asignado a las variables ligadas por un letrec?
Las variables ligadas en un letrec serán instanciadas cuando la abstracción que inmediatamente encierra al letrec es aplicada, ahí es cuando se construye la instancia del mismo. Por lo tanto el número a asignar debe ser el mismo que el de la abstracción.
Si el letrec no ocurre dentro de una abstracción entonces 0.
15
Lifting en presencia de letrecs (2)
Si se da el último caso entonces no ocurren variables libres en el letrec y por lo tanto las definiciones no pueden contener variables libres, por lo tanto son combinadores. Todo lo que es necesario hacer para transfornmarlas en supercombinadores es hacer el lifting de las abstracciones internas.
Ejemplo: let Inf = \ v -> (letrec vs = Cons v vs in vs)
in Inf 4
$Inf v = letrec vs = Cons v vs in vs
$Inf 4
16
Un método alternativo de lifting
El algoritmo de lifting descripto hasta ahora traduce recursion en forma un poco extraña.
\ m -> ... letrec count = \ n -> ... count...m...
$count count m n = ... count ......... = letrec count = $count count n
Un método alternativo, propuesto por T. Johnsson y usado por primera vez en el compilador de LML es el siguiente:Si la definición es de la forma f = \ x -> ... f...v..., entonces• abstraer las variables libres pero no la función• sustituir en la definición f por ($f v)
17
Un método alternativo de lifting (2)
Ventajas
No SC gráficos, recursión es representada por autoreferencia. Puede, por lo tanto ser compilado a código más eficiente y da lugar a otras optimizaciones.
Desventaja
Se complica con definiciones recursivas mutuas
(... (... ($f v) ... ($f v) ...)
$f v x = ... ($f v) ... v
(...letrec f = \ x -> (... f ...v...) in (... f ... f ...) ...)
Top Related