¿Cómo se crea un pase de reescritura basado en si dos expresiones se refieren al mismo nombre encuadernado?

Question

¿Cómo se encuentran y reescriben las expresiones que hacen referencia al mismo nombre encuadernado? Por ejemplo, en la expresión

let xs = ... 
in ...map f xs...map g xs... 

tanto la expresión map f xs y la expresión map g xs referirse al mismo nombre unido, a saber xs. ¿Hay algún análisis de compilación estándar que nos permita identificar esta situación y reescribir las dos expresiones map a, p.

let xs = ... 
    e = unzip (map (f *** g) xs) 
in ...fst e...snd e... 

He estado pensando en el problema en términos de un cruce de árboles. Por ejemplo, dada la AST:

data Ast = Map (a -> b) -> Ast -> Ast 
     | Var String 
     | ... 

podríamos tratar de escribir un recorrido de árbol para detectar este caso, pero que parece difícil, ya que dos Map nodos que se refieren a la misma Var podrían aparecer en muy diferentes lugares en el árbol. Este análisis parece más fácil de hacer si invertiste todas las referencias en el AST, convirtiéndolo en un gráfico, pero quería ver si hay alguna alternativa a ese enfoque.

Answer 1

Creo que lo que está buscando es un conjunto de transformaciones de programa generalmente denominadas Tupling, Fusion y Supercompilación, que se incluyen en la teoría más general de la transformación Unfold/Fold. Puedes lograr lo que quieras de la siguiente manera.

Primero realice evaluaciones especulativas (Despliegue) al "dirigir" la definición de mapa sobre los argumentos, lo que da lugar a dos nuevos pseudo programas, según si xs tiene la forma y: ys o []. En pseudocódigo:

let y:ys = ... 
in ...(f y):(map f ys)...(g y):(map g ys)... 

let [] = ... 
in ...[]...[]... 

A continuación efectuar abstracciones de estructura compartida (Tupling) y generalizaciones (plegable) con respecto al programa original para parar de otra forma perpetua despliegue:

let xs = ... 
in ...(fst tuple)...(snd tuple)... 
where tuple = generalisation xs 
     generalisation [] = ([],[]) 
     generalisation (y:ys) = let tuple = generalisation ys 
           in ((f y):(fst tuple),(g y):(snd tuple)) 

espero que esto le da una idea, pero la transformación del programa es un campo de investigación en sí mismo, y es difícil de explicar bien sin dibujar gráficos acíclicos dirigidos.