15

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

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

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

4

1 回答 1

2

我认为您正在寻找的是一组通常称为 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))

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

于 2012-09-08T09:46:47.197 回答