Comment créer une passe de réécriture selon que deux expressions se rapportent au même nom lié?

Question

Comment trouvez-vous et réécrivez-vous des expressions qui font référence au même nom lié? Par exemple, dans l'expression

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

à la fois l'expression et l'expression map f xsmap g xs se référer au même nom lié, à savoir xs. Existe-t-il des analyses de compilateur standard qui nous permettraient d'identifier cette situation et de réécrire les deux expressions map par exemple.

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

Je pensais au problème en termes de traversée d'arbre. Par exemple donné l'AST:

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

nous pourrions essayer d'écrire un traversal d'arbre pour détecter ce cas, mais cela semble difficile, car deux Map noeuds qui se réfèrent à la même Var peuvent apparaître à des endroits très différents dans l'arborescence. Cette analyse semble plus facile à faire si vous avez inversé toutes les références dans l'AST, ce qui en fait un graphique, mais je voulais voir s'il y avait des alternatives à cette approche.

Answer 1

Je pense que ce que vous cherchez est un ensemble de transformations de programme habituellement appelées Tuftage, Fusion et Supercompilation, qui relèvent de la théorie plus générale de la transformation Déplier/Plier. Vous pouvez réaliser ce que vous voulez comme suit. Effectuer d'abord des évaluations spéculatives (Dépliage) en "pilotant" la définition de la carte sur les arguments, ce qui donne lieu à deux nouveaux pseudo-programmes, selon que xs a la forme y: ys ou []. Dans le code pseudo:

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

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

Effectuez ensuite des abstractions pour la structure partagée (Tupling) et généralisations (pliage) par rapport au programme initial d'arrêter autrement perpétuel déroulement:

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)) 

J'espère que cela vous donne une idée, mais la transformation du programme est un domaine de recherche en soi, et il est difficile de bien l'expliquer sans dessiner des graphes acycliques orientés.