9

ステートメントのブロックを使用する手続き型 EDSL があります。

これらのステートメントは、特定の順序でブロックに追加されませんが、ステートメント間に依存関係がある場合があります。

ただし、EDSL のコンパイル中は、ステートメントが依存の順序で並べられていることを確認する必要があります。

B := A
C := B
E := D

すべてのステートメントに依存関係があるわけではないため、完全な順序はありません (たとえばE := D、上記は独立しており、どこにでも配置できます)。循環的な依存関係がないため、リストの順序付けが可能になるはずです。

ステートメントに依存関係がないことを意味するwhich を使用Data.List.sortByして定義することにより、ソリューションをハックしようとしました。これはいくつかの例では機能しましたが、一般的なケースでは機能しませんでした。たとえば、次の順序で何もしませんでした:OrderingEQ

C := B                           B := A
D := C    = should produce =>    C := B
B := A                           D := C

これは、デフォルトの並べ替え挿入並べ替えが、挿入されたアイテムが次のものより小さいか等しいことを確認するためです。

インターネットでPosetの実装を検索しましたが、該当するものは見つかりませんでした:

altfloat:Data.PosetはOrdering = LT | GT | EQ | NC( NCNon-comparable の場合) を定義しますが、提供されたものは-like非比較項目をsort想定し、単にそれらを破棄します。NaN

logfloat:Data.Number.PartialOrdは、使用法を除いて上記と似ておりMaybe Ordering、パッケージのどこにもソート機能がありませんでした。

Math.Combinatorics.Poset使用方法や適用可能かどうかはわかりません。

以下は、拘束力のあるステートメントと拘束力のないステートメントの両方を持つ最小限の例です。非バインド ステートメントの順序は重要であり、それらは元の順序を維持する必要があります (つまり、並べ替えは、依存関係を持たない wrt ステートメントに対して安定している必要があります)。

本格的な依存グラフを使用せずに、これに対する簡単な解決策があることを願っています...

module Stmts where

import Data.List ( sortBy )

data Var = A | B | C | D | E | F | G | H deriving (Eq, Show)
data Stmt = Var := Var
          | Inc Var
  deriving (Show)

-- LHS variable
binds :: Stmt -> Maybe Var
binds (v := _) = Just v
binds _        = Nothing

-- RHS variables
references :: Stmt -> [Var]
references (_ := v) = [v]
references (Inc v)  = [v]

order :: [Stmt] -> [Stmt]
order = sortBy orderStmts

orderStmts :: Stmt -> Stmt -> Ordering
orderStmts s1 s2 = ord mbv1 mbv2
 where
  ord Nothing   Nothing   = EQ  -- No dep since they don't bind vars
  ord (Just v1) Nothing   = LT  -- Binding statements have precedence
  ord Nothing   (Just v2) = GT  -- ^^^
  ord (Just v1) (Just v2)       -- Both statements are binding:
    | v1 `elem` refs2 = LT      --  * s2 depends on s1
    | v2 `elem` refs1 = GT      --  * s1 depends on s2
    | otherwise       = EQ      --  * neither

  -- *Maybe* they bind variables
  mbv1  = binds s1
  mbv2  = binds s2

  -- Variables they reference  
  refs1 = references s1
  refs2 = references s2

-- The following should return [B := A, C := B, D := C, Inc F, Inc G]
test = order [Inc F, Inc G, C := B, D := C, B := A]
4

2 に答える 2

7

あなたのアプローチの問題は、あなたorderStmtsが順序付けでも部分順序付けでもないことです。特に、それは推移的ではないため、ソートに使用しようとすると失敗します。

あなたが探しているのはトポロジーソートです。それらの間にエッジ (依存関係) がある頂点 (ステートメント) のグラフがあり、順序がエッジと一致することを確認したいと考えています。

拘束力のないステートメントは簡単なので、宣言だけに焦点を当てます (リストを 2 つに分割し、宣言を並べ替えて、再度連結するだけです)。

トポロジカル ソートはData.Graphに既に実装されているため、タスクが非常に簡単になります。

module Stmts where

import Data.Graph

data Var = A | B | C | D | E | F | G | H deriving (Eq, Ord, Show)

data Decl = Var := Var 
  deriving (Show, Eq)

data Stmt = Decl
          | Inc Var
  deriving (Show, Eq)

sortDecls :: [Decl] -> [SCC Decl]
sortDecls = stronglyConnComp . map triple
  where
    triple n@(x := y)   = (n, x, [y])

-- The following should return [B := A, C := B, D := C]
test = map flattenSCC . sortDecls $ [C := B, D := C, B := A]

インスタンスがないため、呼び出しflattenSCCはテスト専用です。おそらく、s のサイクルをチェックして (サイクルは言語のコンパイル エラーになります)、何もない場合は、並べ替えられたシーケンスを抽出します。SCCShowSCC

于 2014-10-03T12:42:11.593 に答える
2

ステートメントグループをソートする唯一の方法は、ルーツから子供まで歩くことだと思います

import Data.List

data Var = A | B | C | D | E | F | G | H deriving (Eq, Show)
data Stmt = Var := Var deriving (Show)

parent :: Stmt -> Var
parent (_ := p) = p

child :: Stmt -> Var
child (c := _) = c

steps :: [Stmt] -> [[Stmt]]
steps st = step roots st
  where step _ [] = []
        step r s = let (a, b) = partition (flip elem r . parent) s
                       (v, u) = partition (flip elem (map child b) . child ) a
                   in  if null u then error "Cycle!"
                                 else u : step (r ++ (nub $ map child u)) (v ++ b)

        roots = let cs = map child st
                    rs = nub $ filter (not . flip elem cs) (map parent st)
                in  if null rs then error "No roots!"
                               else rs

main = mapM_ print $ steps [F := H, G := H, C := B, D := C, B := A]

出力あり

[F := H,G := H,B := A]
[C := B]
[D := C]

「ソート」がグループ（ステートメントではない）を超えている場合。

partition( は、map、 、 ...を通して不変であるため、このコードでは安定性が認められ++ます)

（追加した）

何らかの安定性プロパティ (ステートメントの並べ替え) が本当に必要な場合は、他の制限を追加する必要があります (「安定性」の定義)。

2 つの「ソート」ダイレクト アルゴリズムを使用します (ステートメントを前または後ろに並べ替えるだけです)。

orderToFront :: [Stmt] -> [Stmt]
orderToFront [] = []
orderToFront (s@(_ := p):xs) = let (l, r) = splitAtFirst ((==p).child) xs
                               in  if null r then s: orderToFront xs
                                             else head r: s: orderToFront (l ++ tail r)

orderToBack' :: [Stmt] -> [Stmt]
orderToBack' [] = []
orderToBack' (s@(c := _):xs) = let (l, r) = splitAtFirst ((==c).parent) xs
                               in  if null r then s: orderToBack' xs
                                             else orderToBack' (l ++ head r: s: tail r)
orderToBack = reverse . orderToBack'

splitAtFirst :: (a -> Bool) -> [a] -> ([a], [a])
splitAtFirst f xs = let rs = dropWhile (not.f) xs
                    in  (take (length xs - length rs) xs, rs)


main = do

    let q = [F := H, C := B, D := C, G := F, B := A]

    putStrLn "-- orderToFront"
    mapM_ print $ orderToFront q

    putStrLn "-- orderToBack"
    mapM_ print $ orderToBack q

同じ入力で、orderToFront出力は出力とは異なりorderToBackますが、両方が有効です

-- orderToFront
F := H
B := A
C := B
D := C
G := F
-- orderToBack
B := A
F := H
G := F
C := B
D := C

(等式関係のみでは、アルゴリズムを O(n^2) より低くすることはできませんが、安定性の制限を定義すると、それを減らすことができます)

于 2014-10-02T10:50:30.390 に答える