Jak utworzyć przejście przepisać na podstawie tego, czy dwa wyrażenia odwołują się do tej samej nazwy powiązanej?

Question

Jak znaleźć i ponownie napisać wyrażenia odnoszące się do tej samej nazwy powiązanej? Na przykład, w wyrażeniu

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

zarówno wyrażenie map f xs i wyrażenie map g xs odnoszą się do tej samej nazwy związane, mianowicie xs. Czy istnieją jakieś standardowe analizy kompilatorów, które pozwolą nam zidentyfikować tę sytuację i przepisać oba wyrażenia o wartości map na przykład?

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

Myślałem o problemie w kategoriach przemiany drzewa. Na przykład biorąc pod uwagę AST:

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

moglibyśmy spróbować napisać przechodzenie drzewa w celu wykrycia tej sprawy, ale to wydaje się trudne, ponieważ dwa Map węzły, które odnoszą się do tego samego Var może pojawić się w bardzo różnych miejscach na drzewie. Ta analiza wydaje się łatwiejsza, jeśli odwrócisz wszystkie odniesienia w AST, tworząc wykres, ale chciałem sprawdzić, czy istnieją jakieś alternatywy dla tego podejścia.

Answer 1

Myślę, że to, czego szukasz, to zestaw przekształceń programowych, zwykle określanych jako Tupling, Fusion i Superkompilacja, które wchodzą w zakres bardziej ogólnej teorii transformacji Rozwiń/Zwiń. Możesz osiągnąć to, co chcesz, w następujący sposób.

Najpierw wykonuj oceny spekulacyjne (Rozkładanie) przez "sterowanie" definicją mapy przez argumenty, co powoduje powstanie dwóch nowych pseudo programów, w zależności od tego, czy xs ma postać y: ys lub []. W pseudo kod:

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

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

Następnie wykonaj abstrakcje na wspólną strukturę (Tupling) i uogólnień (Folding) w stosunku do oryginalnego programu, aby zatrzymać inaczej wieczystego rozkładania:

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

Mam nadzieję, że to daje pomysł, ale programowa transformacja jest dziedziną badawczą samą w sobie i trudno ją dobrze wytłumaczyć bez rysowania acyklicznych kierowanych grafów.