如何根据两个表达式是否引用相同的绑定名称来创建重写过程

Question

如何查找和重写引用相同绑定名称的表达式？例如，在表达式中

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

表达式map f xs和表达式map g xs都引用相同的绑定名称即xs。是否有任何标准的编译器分析可以让我们识别这种情况，并将两个map表达式重写为例如

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

我一直在从树遍历的角度思考这个问题。例如，给定AST:

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

我们可以尝试编写一个树遍历来检测这种情况，但这似乎很困难，因为引用同一Var的两个Map节点可能出现在树中完全不同的位置。如果您反转AST中的所有引用，使其成为一个图形，则此分析似乎更容易进行，但我想看看是否有其他方法可以替代此方法。

Answer 1

我认为您正在寻找的是一组程序转换，通常称为Tupling、Fusion和Supercompilation，它们属于更通用的展开/折叠转换理论。你可以通过以下方式实现你想要的。

首先，通过在自变量上"驱动"map的定义来执行推测性求值（展开），这会产生两个新的伪程序，这取决于xs的形式是y:ys还是[]。在伪代码中：

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

然后对原始程序执行共享结构的抽象（Tupling）和概括（Folding），以停止其他永久展开：

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

我希望这能给你一个想法，但程序转换本身就是一个研究领域，如果不画非循环有向图，很难很好地解释。