15

同じバインドされた名前を参照する式をどのように見つけて書き換えますか? たとえば、式では

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

map f xs式と 式 の両方がmap g xs同じバインドされた名前、つまり を参照していますxs。mapこの状況を特定し、2 つの式を次のように書き換えることができる標準的なコンパイラ分析はありますか。

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

私はツリートラバーサルの観点から問題について考えてきました。たとえば、AST が与えられた場合:

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

このケースを検出するためにツリー トラバーサルを記述しようとすることもできますがMap、同じものを参照する 2 つのノードがVarツリー内の大きく異なる場所に現れる可能性があるため、それは難しいようです。この分析は、AST 内のすべての参照を逆にしてグラフにした方が簡単に思えますが、その方法に代わる方法がないかどうかを確認したかったのです。

4

1 に答える 1

2

あなたが探しているのは、通常、Tupling、Fusion、および Supercompilation と呼ばれる一連のプログラム変換であり、Unfold/Fold 変換のより一般的な理論に該当すると思います。次のようにして、あなたが望むものを達成することができます。

xs が y:ys または [] のどちらの形式であるかに応じて、2 つの新しい疑似プログラムが生成されます。擬似コード:

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 に答える