[Haskell-cafe] Explicit garbage collection
Miguel Mitrofanov
miguelimo38 at yandex.ru
Thu Jan 7 12:39:10 EST 2010
Damn. Seems like I really need (True, False, True) as a result of
"test".
On 7 Jan 2010, at 08:52, Miguel Mitrofanov wrote:
> Seems very nice. Thanks.
>
> On 7 Jan 2010, at 08:01, Edward Kmett wrote:
>
>> Here is a slightly nicer version using the Codensity monad of STM.
>>
>> Thanks go to Andrea Vezzosi for figuring out an annoying hanging
>> bug I was having.
>>
>> -Edward Kmett
>>
>> {-# LANGUAGE Rank2Types, GeneralizedNewtypeDeriving, DeriveFunctor
>> #-}
>> module STMOracle
>> ( Oracle, Ref
>> , newRef, readRef, writeRef, modifyRef, needRef
>> ) where
>>
>> import Control.Applicative
>> import Control.Monad
>> import Control.Concurrent.STM
>>
>> instance Applicative STM where
>> pure = return
>> (<*>) = ap
>>
>> newtype Ref s a = Ref (TVar (Maybe a))
>> newtype Oracle s a = Oracle { unOracle :: forall r. (a -> STM r) ->
>> STM r } deriving (Functor)
>>
>> instance Monad (Oracle s) where
>> return x = Oracle (\k -> k x)
>> Oracle m >>= f = Oracle (\k -> m (\a -> unOracle (f a) k))
>>
>> mkOracle m = Oracle (m >>=)
>>
>> runOracle :: (forall s. Oracle s a) -> IO a
>> runOracle t = atomically (unOracle t return)
>>
>> newRef :: a -> Oracle s (Ref s a)
>> newRef a = mkOracle $ Ref <$> newTVar (Just a)
>>
>> readRef :: Ref s a -> Oracle s a
>> readRef (Ref r) = mkOracle $ do
>> m <- readTVar r
>> maybe retry return m
>>
>> writeRef :: a -> Ref s a -> Oracle s a
>> writeRef a (Ref r) = mkOracle $ do
>> writeTVar r (Just a)
>> return a
>>
>> modifyRef :: (a -> a) -> Ref s a -> Oracle s a
>> modifyRef f r = do
>> a <- readRef r
>> writeRef (f a) r
>>
>> needRef :: Ref s a -> Oracle s Bool
>> needRef (Ref slot) = Oracle $ \k ->
>> (writeTVar slot Nothing >> k False)
>> `orElse` k True
>>
>> -- test
>> case
>> : refMaybe
>> b dflt ref = if b then readRef ref else return dflt
>> refIgnore ref = return "blablabla"
>> refFst ref = fst `fmap` readRef ref
>> test = do
>> a <- newRef "x"
>> b <- newRef 1
>> c <- newRef ('z', Just 0)
>> -- no performLocalGC required
>> x <- needRef a
>> y <- needRef b
>> z <- needRef c
>> u <- refMaybe y "t" a -- note that it wouldn't actually read "a",
>> -- but it won't be known until runtime.
>> w <- refIgnore b
>> v <- refFst c
>> return (x, y, z)
>>
>>
>>
>> On Wed, Jan 6, 2010 at 10:28 PM, Edward Kmett <ekmett at gmail.com>
>> wrote:
>> I don't believe you can get quite the semantics you want. However,
>> you can get reasonably close, by building a manual store and
>> backtracking.
>>
>> {-# LANGUAGE Rank2Types #-}
>> -- lets define an Oracle that tracks whether or not you might need
>> the reference, by backtracking.
>> module Oracle
>> ( Oracle, Ref
>> , newRef, readRef, writeRef, modifyRef, needRef
>> ) where
>>
>> import Control.Applicative
>> import Control.Arrow (first)
>> import Control.Monad
>> import Data.IntMap (IntMap)
>> import qualified Data.IntMap as M
>> import Unsafe.Coerce (unsafeCoerce)
>> import GHC.Prim (Any)
>>
>> -- we need to track our own worlds, otherwise we'd have to build
>> over ST, change optimistically, and track how to backtrack the
>> state of the Store. Much uglier.
>> -- values are stored as 'Any's for safety, see GHC.Prim for a
>> discussion on the hazards of risking the storage of function types
>> using unsafeCoerce as anything else.
>> data World s = World { store :: !(IntMap Any), hwm :: !Int }
>>
>> -- references into our store
>> newtype Ref s a = Ref Int deriving (Eq)
>>
>> -- our monad that can 'see the future' ~ StateT (World s) []newtype
>> Oracle s a = Oracle { unOracle :: World s -> [(a, World s)] }
>>
>> -- we rely on the fact that the list is always non-empty for any
>> oracle you can run. we are only allowed to backtrack if we thought
>> we wouldn't need the reference, and wound up needing it, so head
>> will always succeed.
>> runOracle :: (forall s. Oracle s a) -> a
>> runOracle f = fst $ head $ unOracle f $ World M.empty 1
>>
>>
>> instance Monad (Oracle s) where
>> return a = Oracle $ \w -> [(a,w)]
>> Oracle m >>= k = Oracle $ \s -> do
>> (a,s') <- m s
>> unOracle (k a) s'
>>
>> -- note: you cannot safely define fail here without risking a crash
>> in runOracle
>> -- Similarly, we're not a MonadPlus instance because we always want
>> to succeed eventually.
>>
>> instance Functor (Oracle s) where
>> fmap f (Oracle g) = Oracle $ \w -> first f <$> g w
>>
>> instance Applicative (Oracle s) where
>> pure = return
>> (<*>) = ap
>>
>> -- new ref allocates a fresh slot and inserts the value into the
>> store. the type level brand 's' keeps us safe, and we don't export
>> the Ref constructor.
>> newRef :: a -> Oracle s (Ref s a)
>> newRef a = Oracle $ \(World w t) ->
>> [(Ref t, World (M.insert t (unsafeCoerce a) w) (t + 1))]
>>
>> -- readRef is the only thing that ever backtracks, if we try to
>> read a reference we claimed we wouldn't need, then we backtrack to
>> when we decided we didn't need the reference, and continue with its
>> value.
>> readRef :: Ref s a -> Oracle s a
>> readRef (Ref slot) = Oracle $ \world ->
>> maybe [] (\a -> [(unsafeCoerce a, world)]) $ M.lookup slot
>> (store world)
>>
>> -- note, writeRef dfoesn't 'need' the ref's current value, so
>> needRef will report False if you writeRef before you read it after
>> this.
>> writeRef :: a -> Ref s a -> Oracle s a
>> writeRef a (Ref slot) = Oracle $ \world ->
>> [(a, world { store = M.insert slot (unsafeCoerce a) $ store
>> world })]
>>
>> {-
>> -- alternate writeRef where writing 'needs' the ref.
>> writeRef :: a -> Ref s a -> Oracle s a
>> writeRef a (Ref slot) = Oracle $ \World store v -> do
>> (Just _, store') <- return $ updateLookupWithKey replace slot
>> store
>> [(a, World store' v)]
>> where
>> replace _ _ = Just (unsafeCoerce a)
>> -}
>>
>> -- modifying a reference of course needs its current value.
>> modifyRef :: (a -> a) -> Ref s a -> Oracle s a
>> modifyRef f r = do
>> a <- readRef r
>> writeRef (f a) r
>>
>> -- needRef tries to continue executing the world without the
>> element in the store in question. if that fails, then we'll
>> backtrack to here, and try again with the original world, and
>> report that the element was in fact needed.
>> needRef :: Ref s a -> Oracle s Bool
>> needRef (Ref slot) = Oracle $ \world ->
>> [ (False, world { store = M.delete slot $ store world })
>> , (True, world)
>> ]
>>
>> -- test case:
>> refMaybe b dflt ref = if b then readRef ref else return dflt
>> refIgnore ref = return "blablabla"
>> refFst ref = fst <$> readRef ref
>> test = do
>> a <- newRef "x"
>> b <- newRef 1
>> c <- newRef ('z', Just 0)
>> -- no performLocalGC required
>> x <- needRef a
>> y <- needRef b
>> z <- needRef c
>> u <- refMaybe y "t" a -- note that it wouldn't actually read "a",
>> -- but it won't be known until runtime.
>> w <- refIgnore b
>> v <- refFst c
>> return (x, y, z)
>>
>> -- This will disagree with your desired answer, returning:
>>
>> *Oracle> runOracle test
>> Loading package syb ... linking ... done.
>> Loading package array-0.2.0.0 ... linking ... done.
>> Loading package containers-0.2.0.1 ... linking ... done.
>> (False,False,True)
>>
>> rather than (True, False, True), because the oracle is able to see
>> into the future (via backtracking) to see that refMaybe doesn't use
>> the reference after all.
>>
>> This probably won't suit your needs, but it was a fun little
>> exercise.
>>
>> -Edward Kmett
>>
>> On Wed, Jan 6, 2010 at 4:05 PM, Miguel Mitrofanov <miguelimo38 at yandex.ru
>> > wrote:
>>
>> On 6 Jan 2010, at 23:21, Edward Kmett wrote:
>>
>> You probably just want to hold onto weak references for your
>> 'isStillNeeded' checks.
>>
>> That's what I do now. But I want to minimize the network traffic,
>> so I want referenced values to be garbage collected as soon as
>> possible - and I couldn't find anything except System.Mem.performIO
>> to do the job - which is a bit too global for me.
>>
>> Otherwise the isStillNeeded check itself will keep you from garbage
>> collecting!
>>
>> Not necessary. What I'm imagining is that there is essentially only
>> one way to access the value stored in the reference - with readRef.
>> So, if there isn't any chance that readRef would be called, the
>> value can be garbage collected; "isStillNeeded" function only needs
>> the reference, not the value.
>>
>> Well, yeah, that's kinda like weak references.
>>
>>
>> http://cvs.haskell.org/Hugs/pages/libraries/base/System-Mem-Weak.html
>>
>> -Edward Kmett
>>
>> On Wed, Jan 6, 2010 at 9:39 AM, Miguel Mitrofanov <miguelimo38 at yandex.ru
>> > wrote:
>> I'll take a look at them.
>>
>> I want something like this:
>>
>> refMaybe b dflt ref = if b then readRef ref else return dflt
>> refIgnore ref = return "blablabla"
>> refFst ref =
>> do
>> (v, w) <- readRef ref
>> return v
>> test =
>> do
>> a <- newRef "x"
>> b <- newRef 1
>> c <- newRef ('z', Just 0)
>> performLocalGC -- if necessary
>> x <- isStillNeeded a
>> y <- isStillNeeded b
>> z <- isStillNeeded c
>> u <- refMaybe y "t" a -- note that it wouldn't actually read "a",
>> -- but it won't be known until runtime.
>> w <- refIgnore b
>> v <- refFst c
>> return (x, y, z)
>>
>> so that "run test" returns (True, False, True).
>>
>>
>> Dan Doel wrote:
>> On Wednesday 06 January 2010 8:52:10 am Miguel Mitrofanov wrote:
>> Is there any kind of "ST" monad that allows to know if some STRef
>> is no
>> longer needed?
>>
>> The problem is, I want to send some data to an external storage
>> over a
>> network and get it back later, but I don't want to send unnecessary
>> data.
>>
>> I've managed to do something like that with weak pointers,
>> System.Mem.performGC and unsafePerformIO, but it seems to me that
>> invoking
>> GC every time is an overkill.
>>
>> Oh, and I'm ready to trade the purity of runST for that, if
>> necessary.
>>
>> You may be able to use something like Oleg's Lightweight Monadic
>> Regions to get this effect. I suppose it depends somewhat on what
>> qualifies a reference as "no longer needed".
>>
>> http://www.cs.rutgers.edu/~ccshan/capability/region-io.pdf
>>
>> I'm not aware of anything out-of-the-box that does what you want,
>> though.
>>
>> -- Dan
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
More information about the Haskell-Cafe
mailing list