How do you create a rewrite pass based on whether two expressions refers to the same bound name?

Question

How do you find and rewrite expressions that refer to the same bound name? For example, in the expression

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

both the expression map f xs and the expression map g xs refer to the same bound name, namely xs. Are there any standard compiler analyses that would let us identify this situation and rewrite the two map expressions to e.g.

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

I've been thinking about the problem in terms of a tree traversal. For example given the AST:

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

we could try to write a tree traversal to detect this case, but that seems difficult since two Map nodes that refer to the same Var might appear at widely different places in the tree. This analysis seems easier to do if you inverted all the references in the AST, making it a graph, but I wanted to see if there are any alternatives to that approach.

Answer 1

I think what you are looking for is a set of program transformations usually referred to as Tupling, Fusion, and Supercompilation, which fall under the more general theory of Unfold/Fold transformation. You can achieve what you want as follows.

First perform speculative evaluations (Unfolding) by "driving" the definition of map over the arguments, which gives rise to two new pseudo programs, depending on whether xs is of the form y:ys or []. In pseudo code:

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

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

Then perform abstractions for shared structure (Tupling) and generalisations (Folding) with respect to the original program to stop otherwise perpetual unfolding:

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

I hope this gives you an idea, but program tranformation is a research field in its own right, and it is hard to explain well without drawing acyclic directed graphs.