data-fix-cse 0.0.2 → 0.0.3

raw patch · 2 files changed

+43/−27 lines, 2 filesdep ~data-fixPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: data-fix

API changes (from Hackage documentation)

Files

• data-fix-cse.cabal +9/−8
• src/Data/Fix/Cse.hs +34/−19

@@ -1,15 +1,15 @@ Name:            data-fix-cse-Version:         0.0.2-Cabal-Version:   >= 1.6+Version:         0.0.3+Cabal-Version:   >= 1.10 License:         BSD3 License-file:    LICENSE Author:          Anton Kholomiov, Oleg Kiselyov Maintainer:      <anton.kholomiov@gmail.com> Category:        Data-Synopsis:        Common subexpression elimination for the fixploint types.   +Synopsis:        Common subexpression elimination for the fixploint types. Build-Type:      Simple-Description:     -  Common subexpression elimination for the fixploint types.   +Description:+  Common subexpression elimination for the fixploint types.  Stability:       Experimental @@ -26,13 +26,14 @@     Location: https://github.com/anton-k/data-fix-cse  Library-  Build-depends: base >= 4, base < 5, data-fix, transformers, containers+  Build-depends: base >= 4, base < 5, data-fix >= 0.3.0, transformers, containers+  default-language: Haskell2010   Hs-source-dirs: src/    ghc-options: -Wall -  Exposed-Modules: +  Exposed-Modules:       Data.Fix.Cse-  Other-Modules:  +  Other-Modules:       Data.Fix.BiMap       Data.Fix.BiMapFramed

@@ -1,5 +1,5 @@ -- | Implements common subexpression elimination (CSE) with hashconsig algorithm as described in--- the paper 'Implementing Explicit and Finding Implicit Sharing in EDSLs' by Oleg Kiselyov. +-- the paper 'Implementing Explicit and Finding Implicit Sharing in EDSLs' by Oleg Kiselyov. -- You can define your datatype as a fixpoint type. Then the only thing you need to perform CSE -- is to define an instance of the class 'Traversable' for your datatype. module Data.Fix.Cse (@@ -9,7 +9,7 @@      -- * Explicit sharing     letCse, Let(..),-    letCata, letCataM,+    letFoldFix, letFoldFixM,     letWrapper,      -- * Framed sharing@@ -18,8 +18,10 @@     -- frames per each if- or else block. So that variables     -- from different if-the-else branches don't get messed up.     -- We need to allocate a new frame for each branch.-    -- We can do it with special structure @FrameInfo@.    -    FrameInfo(..), cseFramed+    -- We can do it with special structure @FrameInfo@.+    FrameInfo(..), cseFramed,+    -- * Deprecated functions+    letCata, letCataM ) where  import Control.Applicative hiding (empty)@@ -38,18 +40,18 @@ -- | Directed acyclic graphs. type Dag f = IM.IntMap (f VarName) --- | If plain lists are enough for your case. +-- | If plain lists are enough for your case. fromDag :: Dag f -> [(VarName, f VarName)] fromDag = IM.toList --- | Performs common subexpression elimination with implicit sharing.  +-- | Performs common subexpression elimination with implicit sharing. cse :: (Eq (f Int), Ord (f Int), Traversable f) => Fix f -> Dag f-cse x = getDag $ execState (cataM hashcons x) empty+cse x = getDag $ execState (foldFixM hashcons x) empty   -- | With explicit sharing you provide user with the special function that -- encodes let-bindings for your EDSL ('LetBind'). You should not use 'LetLift' case.--- It's reserverd for the CSE algorithm. +-- It's reserverd for the CSE algorithm. data Let f a     = LetExp (f a)     | LetBind a (a -> a)@@ -59,22 +61,22 @@ -- For exampe: -- -- > newtype T = T { unT :: Fix (Let f) }--- > +-- > -- > let_ :: T -> (T -> T) -> T -- > let_ = letWrapper T unT letWrapper :: (Fix (Let f) -> a) -> (a -> Fix (Let f)) -> a -> (a -> a) -> a letWrapper to from a e = to $ Fix $ LetBind (from a) (from . e . to) --- | Performs common subexpression elimination with explicit sharing.  +-- | Performs common subexpression elimination with explicit sharing. -- To make sharing explicit you can use the datatype 'Let'. letCse :: (Eq (f Int), Ord (f Int), Traversable f)    => Fix (Let f) -> Dag f-letCse x = getDag $ execState (letCataM hashcons x) empty+letCse x = getDag $ execState (letFoldFixM hashcons x) empty  -- | Monadic catamorphism for fixpoint types wrapped in the type 'Let'.-letCataM :: (Applicative m, Monad m, Traversable f) =>+letFoldFixM :: (Applicative m, Monad m, Traversable f) =>    (f a -> m a) -> Fix (Let f) -> m a-letCataM m expr = evalStateT (go expr) IM.empty+letFoldFixM m expr = evalStateT (go expr) IM.empty    where go    = phi . unFix          phi x = case x of                    LetLift var -> do@@ -90,9 +92,9 @@                                   go . e . Fix . LetLift $ var  -- | Catamorphism for fixpoint types wrapped in the type 'Let'.-letCata :: (Functor f, Traversable f) =>+letFoldFix :: (Functor f, Traversable f) =>    (f a -> a) -> Fix (Let f) -> a-letCata f expr = evalState (go expr) IM.empty+letFoldFix f expr = evalState (go expr) IM.empty    where go    = phi . unFix          phi x = case x of                    LetLift var -> do@@ -107,6 +109,19 @@                                   put s'                                   go . e . Fix . LetLift $ var ++-- | Catamorphism for fixpoint types wrapped in the type 'Let'.+letCata :: (Functor f, Traversable f) =>+   (f a -> a) -> Fix (Let f) -> a+letCata = letFoldFix+{-# DEPRECATED letCata "Use letFoldFix" #-}++letCataM :: (Applicative m, Monad m, Traversable f) =>+   (f a -> m a) -> Fix (Let f) -> m a+letCataM = letFoldFixM+{-# DEPRECATED letCataM "Use letFoldFixM" #-}++ hashcons :: (Ord a) => a -> State (BiMap a) Int hashcons e = do   m <- get@@ -119,15 +134,15 @@ -- | Marker type for creation frames of variables. -- Start new frame when if-block starts, create next frame -- when you go into the next branch of the same block (with else ir elif),--- stop frame when leaving the if-then-else block. Use no frame for all +-- stop frame when leaving the if-then-else block. Use no frame for all -- other expressions. data FrameInfo = NoFrame | StartFrame | StopFrame | NextFrame   deriving (Show, Eq, Ord) --- | Performs common subexpression elimination with implicit sharing using information of frames.  +-- | Performs common subexpression elimination with implicit sharing using information of frames. -- It doesn't share the variables in different branches of imperative if-then-else block. cseFramed :: (Eq (f Int), Ord (f Int), Traversable f) => (f Int -> FrameInfo) -> Fix f -> Dag f-cseFramed getFrameInfo x = F.getDag $ execState (cataM (hashconsFramed getFrameInfo) x) F.empty+cseFramed getFrameInfo x = F.getDag $ execState (foldFixM (hashconsFramed getFrameInfo) x) F.empty  hashconsFramed :: (Ord a) => (a -> FrameInfo) -> a -> State (F.BiMap a) Int hashconsFramed getFrameInfo e = do@@ -136,7 +151,7 @@         NoFrame    -> m'         StartFrame -> F.startFrame m'         StopFrame  -> F.stopFrame m'-        NextFrame  -> F.nextFrame m'      +        NextFrame  -> F.nextFrame m'    case F.lookup_key e m of     Nothing -> let (k,m') = F.insert e m