Malcolm Wallace wrote [snip]
I don't think MVars make any sense without concurrency, so I don't see the point of implementing the one without the other. I'm willing to be persuaded otherwise. (It would be nice to have some concurrency in nhc98, of course, but I don't foresee that happening soon.)
I apologise to Malcolm, but in any case I doubt if implementing MVars in a world with only one thread would cost him a great deal of effort.
Well it would be simple enough provided you didn't mind your computation halting with deadlock rather unpredictably. :-) [snip] OK, the point is to make programs more portable from NHC to other systems. (Perhaps you would rather lock them in? 8-) If I write, say, Alastair Reid's newObject and killObject in NHC using IORefs, then this will work fine in NHC, but may mysteriously go wrong when someone ports them to GHC and calls newObject and killObject simultaneously.
I'm not sure we should be discussing this here; really we should have a separate Haskell Mutable State standard. However let's try anyway. Clearly it would be trivial to implement MVars in NHC to fit such a goal, something like newtype MVar a = MVar (IORef (Maybe a)) takeMVar (MVar ioRef) = do aOpt <- readIORef ioRef case aOpt of Nothing -> error "Computer deadlocked. Please buy a new one." Just a -> do writeIORef ioRef Nothing return a (newMVar and putMVar I'll leave as exercises for the reader.) I admit though that Alastair is right in this: while NHC + MVars and NHC + Haskell finalizers may be doable, NHC + Haskell finalizers + MVars may not be, because then you have the problem of blocking. If the main program and the finalizer both do x <- takeMVar mVar putMVar mVar (update x) then the program will unnecessarily deadlock if the finalizer is called inbetween the take and the put. Malcolm, is it feasible to implement a workaround to this? However even if Haskell finalizers + MVars are impossible in NHC, I don't think Haskell finalizers + mutable state have to be. For example another mutable variable we could have would be a PVar which is always full and has functions newPVar :: a -> IO (PVar a) updatePVar :: PVar a -> (a -> a) -> IO a updatePVar represents an atomic update; the function is applied to the value in the PVar and the old value is returned. For GHC and Hugs you could implement PVars using MVars. NHC could implement them as follows: newtype PVar = PVar (IORef a) updatePVar (PVar ioRef) updateFn = do [stop any new finalizers running] a <- readIORef ioRef writeIORef (updateFn a) [reenable finalizers] return a Then we have mutable state (enough to implement Alastair's killObject/newObject safely) in a way that I think NHC wouldn't find it too hard to implement. Of course you need a global flag which disables removing things from the finalizer queue, and the reenable-finalizers primitive could also check to see if any finalizers had arisen in the meantime. Also we are implicitly assuming that the execution of finalizers is properly nested, but that doesn't seem to hard a condition to ensure (in the context of NHC). Malcolm, does all this make sense to you, or am I talking total rubbish? I don't claim these PVars are perfect; there are things I can do with MVars which I don't know how to do with PVars. But I do claim that they provide sufficient mutable state to be useful in finalizers, without being hard for anyone (GHC, Hugs or NHC) to implement with finalizers. A "Mutable Variables Standard" could then define IORefs and PVars. Then with Haskell98 + FFI + Mutable Variables you would be able to write portable code that does mutable things in finalizers, and we would all be happy.
George Russell <ger@tzi.de> writes:
OK, the point is to make programs more portable from NHC to other systems. (Perhaps you would rather lock them in? 8-) If I write, say, Alastair Reid's newObject and killObject in NHC using IORefs, then this will work fine in NHC, but may mysteriously go wrong when someone ports them to GHC and calls newObject and killObject simultaneously.
Yes, I agree that this is a problem. A naive programmer could try an incorrect approach to mutating shared state in a Haskell finaliser, and believe that it is correct and portable, simply because it happens to work in nhc98. It would be nice to be able to lessen the chances of this happening by providing the proper primitives for shared access.
For example another mutable variable we could have would be a PVar which is always full and has functions
newPVar :: a -> IO (PVar a) updatePVar :: PVar a -> (a -> a) -> IO a
I was musing that a single-threaded system might be able to provide just a restricted set of atomic operations on MVars, say, something like newMVar + withMVar + modifyMVar, which might be enough to guarantee correct locking whilst excluding deadlock. But your suggestion of a different synchronisation variable type with more limited capabilities is probably better than trying to define the precise restrictions on MVars. I'll need to think some more about the details of PVars, but my first reaction is that they would very easy to implement. However, I fear it may be no good persuading me of their value if you cannot also persuade the other implementations to adopt them, so I'd like to hear what Hugs and ghc people have to say, especially whether they would also solve the problems with mutable shared state raised by Alastair. Regards, Malcolm
However even if Haskell finalizers + MVars are impossible in NHC, I don't think Haskell finalizers + mutable state have to be. For example another mutable variable we could have would be a PVar which is always full and has functions [snip]
updatePVar (PVar ioRef) updateFn = do [stop any new finalizers running] a <- readIORef ioRef writeIORef (updateFn a) [reenable finalizers] return a
Just for the record, I think that if we were to pursue this approach, then the right primitive to add is: -- | -- Execute argument atomically with respect to finalizers. -- Nested calls to blockFinalizers are allowed. -- -- That is, while executing the argument, no finalizers will start -- to execute. -- (Finalizers that are already executing may continue to execute.) blockFinalizers :: IO a -> IO a [The last sentence is to take care of cases like finalizers calling blockFinalizers.] One would then write George's example like this:
updatePVar (PVar ioRef) updateFn = blockFinalizers $ modIOVar ioRef updateFn
This is what I was referring to the other day when I suggested that a mechanism in the style of interrupt disable might be easier to implement than MVars. -- Alastair
(message referred to follows) Alastair suggested implementing blockFinalizers rather than PVars. However I dislike this for two reason: (1) I'm rather attached to PVars. Not just because I suggested them (actually I think I stole them from Einar Karlsen) but because it looks to me as if they could be implemented very efficiently and would be quite useful. If we take the more general interface: newPVar :: a -> IO (PVar a) updatePVar :: PVar a -> (a -> (a,b)) -> IO b then PVar's are absolutely guaranteed not to block, and updatePVar can be implemented as an atomic operation in any of GHC, NHC and Hugs, and I suspect it should even be pretty easy to implement it directly in C (since all you are doing is moving pointers to thunks around). In particular I would like to petition Simon Marlow to include updatePVar in this way in GHC, because (unlike the corresponding solution with MVars) it could very cheaply be guaranteed to work atomically (with MVars you need complicated patterns of expensive block-exception primitives to stop asynchronous exceptions mucking things up). Furthermore although you cannot provide updatePVarIO :: PVar a -> (a -> IO (a,b)) -> IO b you can implement something fairly similar to it if you are naughty by giving updatePVar a function which returns an unsafePerformIO'd action. The action will then of course be executed at some outspecified date when the user tries to read the contents of the PVar. For UniForM at least there is an application for this which would plug an existing embarassing hole in the events code, namely that you mustn't throw asynchronous exceptions at threads which use events. (2) blockFinalizers looks fine for Hugs and NHC which only have a single-thread model, but it looks tricky in general where we do not have a conception of "during". Effectively that means an implementation on a parallel architecture which accesses state has to come up with some arbitrary order of state accesses, just so that it can rely on it to specify blockFinalizers. Of course PVars assume an ordering of state accesses, but only between accesses to the single PVar. (There is a similar problem lurking with "unsafe" external calls, which is probably why they are called "unsafe".) (3) The implementation of PVars Alastair gives using blockFinalizers also will not work in general unless you also specify that Haskell finalizers are properly nested. This is OK for NHC, maybe not for Hugs, certainly not for GHC. This is not of course a problem for PVars since the reason is that Hugs and GHC have concurrency, and on a concurrent machine you would naturally implement PVars using MVars (if not as primitives in their own right). Alastair Reid wrote:
However even if Haskell finalizers + MVars are impossible in NHC, I don't think Haskell finalizers + mutable state have to be. For example another mutable variable we could have would be a PVar which is always full and has functions [snip]
updatePVar (PVar ioRef) updateFn = do [stop any new finalizers running] a <- readIORef ioRef writeIORef (updateFn a) [reenable finalizers] return a
Just for the record, I think that if we were to pursue this approach, then the right primitive to add is:
-- | -- Execute argument atomically with respect to finalizers. -- Nested calls to blockFinalizers are allowed. -- -- That is, while executing the argument, no finalizers will start -- to execute. -- (Finalizers that are already executing may continue to execute.) blockFinalizers :: IO a -> IO a
(2) blockFinalizers looks fine for Hugs and NHC which only have a single-thread model, but it looks tricky in general where [...]
Ah, I see what you mean. I'd kinda hardwired into the definition the assumption that finalizers run at higher priority than other threads and that there's a single execution thread. I'd hoped that blockFinalizers would be useful for defining other primitives but since it won't even work for GHC, I agree that PVar will meet most of our needs. (An even simpler design might be to extend our IORef implementations with 'atomicallyModifyIORef'.) So, is this a design that we could agree on? It seems a reasonable question to ask is whether either PVars or atomicallyModifyIORef could be used instead of MVars in existing concurrent code. If yes, then it seems likely that we can make our libraries Finalizer-safe. If no, it'll probably give us some clues as to what is missing and we can think about whether we'd miss them. A
I'd hoped that blockFinalizers would be useful for defining other primitives but since it won't even work for GHC, I agree that PVar will meet most of our needs. (An even simpler design might be to extend our IORef implementations with 'atomicallyModifyIORef'.)
So, is this a design that we could agree on?
I like it. I'd vote for 'atomicModifyIORef' rather than a new PVar type, though. Cheers, Simon
Simon Marlow wrote:
I'd hoped that blockFinalizers would be useful for defining other primitives but since it won't even work for GHC, I agree that PVar will meet most of our needs. (An even simpler design might be to extend our IORef implementations with 'atomicallyModifyIORef'.)
So, is this a design that we could agree on?
I like it. I'd vote for 'atomicModifyIORef' rather than a new PVar type, though.
Yes, I think I would too. So that's the end of PVars. Just to check, is there any problem implementing atomicModifyIORef :: IORef a -> (a -> (a,b)) -> IO b? (Especially for NHC?) Because that's the type I would like it to have. I can see a number of applications for this function . .
Alastair:
So, is this a design that we could agree on?
SimonM:
I like it. I'd vote for 'atomicModifyIORef' rather than a new PVar type, though.
Ok, onto the second question: Can we use atomicModifyIORef to make our code finalizer-safe? I see potential problems wherever two IORefs need to be modified atomically. Obviously, it's easy enough to change code like this: foo :: (IORef a, IORef b) -> IO () foo (ref1,ref2) = do modifyIORef ref1 f modifyIORef ref2 g to foo :: IORef (a,b) -> IO () foo ref = do modifyIORef ref (f `cross` g) More difficult would be something composite objects where multiple IORefs need to be updated 'at once'. With MVars, you'd use a single MVar as the lock for the whole object and then use IORefs for mutable bits within the tree. You'd use a similar approach with a construct like blockFinalizers. I don't know how to achieve the same goal with atomicModifyIORef. -- Alastair ps While pondering the problems in the semantics of blockFinalizers, I came up with an alternative semantics which would make sense for GHC. @runAtomically m@ runs m atomically with respect to any finalizers or any threads also executing @runAtomically@. That is, any side effects from m must not overlap with the side effects of any other finalizer or thread (if other threads exist). On a system where finalizers behave like interrupts (i.e., finalizers can preempt normal threads and finalizers run to completion before any other finalizers or normal threads run), runAtomically has the effect of delaying execution of finalizers until m completes. In the presence of cooperative concurrency, we must also block execution of normal threads while m runs. On a system where finalizers behave like preemptive threads runAtomically must wait until all [other] currently running finalizers terminate and any other thread running rnuAtomically to terminate, then fresh finalizers must be prevented from starting while m is running, when m completes, any pending finalizers can be started. (I think this can be implemented using something like a reader-writer lock where all finalizers must take the 'reader' lock when they start and runAtomically takes the 'writer' lock when it runs. There's a small wrinkle on the standard reader-writer design that a 'reader' become a 'writer' if it calls runAtomically.) On multiprocessor systems, it might be possible to optimize things by taking the 'reader' lock only when the finalizers/threads start to have side effects. I feel more confident that runAtomically could be used to make libraries finalizer-safe than I do with atomicModifyIORef.
Alastair Reid wrote:
Alastair:
So, is this a design that we could agree on?
SimonM:
I like it. I'd vote for 'atomicModifyIORef' rather than a new PVar type, though.
Ok, onto the second question:
Can we use atomicModifyIORef to make our code finalizer-safe?
I see potential problems wherever two IORefs need to be modified atomically. Obviously, it's easy enough to change code like this:
foo :: (IORef a, IORef b) -> IO () foo (ref1,ref2) = do modifyIORef ref1 f modifyIORef ref2 g
to
foo :: IORef (a,b) -> IO () foo ref = do modifyIORef ref (f `cross` g)
More difficult would be something composite objects where multiple IORefs need to be updated 'at once'. With MVars, you'd use a single MVar as the lock for the whole object and then use IORefs for mutable bits within the tree. You'd use a similar approach with a construct like blockFinalizers. I don't know how to achieve the same goal with atomicModifyIORef.
I do. To modify ioRef1 and ioRef2 "simultaneously", write atomicModifyIORef ioRef1 (\ contents1 -> unsafePerformIO ioRef2 (\ contents2 -> blah blah)) The actual modification will take place when the result or contents of ioRef1 or ioRef2 get evaluated. It's horrible of course, but we've got unsafePerformIO in the FFI standard so why not? You cannot get deadlocks (because atomicModifyIORef won't deadlock), but instead you can get non-termination. GHC at least detects this non-termination and produces an "Exception: <<loop>>" or something of the sort. To avoid the non-termination, you need to order the ioRefs in some way or use some similar strategy, just as you'd have to for MVars. In fact for UniForM this strategy looks more reliable than our existing one of using MVars, since at least atomicModifyIORef is guaranteed to leave something in the ioRef, while with MVars you have to watch out for someone killing the thread at an inconvenient time when the MVar is empty.
Alastair:
I don't know how to achieve the same goal with atomicModifyIORef.
George:
I do. To modify ioRef1 and ioRef2 "simultaneously", write
atomicModifyIORef ioRef1 (\ contents1 -> unsafePerformIO ioRef2 (\ contents2 -> blah blah))
The actual modification will take place when the result or contents of ioRef1 or ioRef2 get evaluated.
I must be missing something because this seems to be riddled with race conditions. In particular, if ioRef1 is updated by a lazy function, then the write to ioRef1 happens but the write to ioRef2 does not. -- Alastair
Alastair Reid wrote:
Alastair:
I don't know how to achieve the same goal with atomicModifyIORef.
George:
I do. To modify ioRef1 and ioRef2 "simultaneously", write
atomicModifyIORef ioRef1 (\ contents1 -> unsafePerformIO ioRef2 (\ contents2 -> blah blah))
The actual modification will take place when the result or contents of ioRef1 or ioRef2 get evaluated.
I must be missing something because this seems to be riddled with race conditions.
In particular, if ioRef1 is updated by a lazy function, then the write to ioRef1 happens but the write to ioRef2 does not.
Yes but so what? The write to ioRef2 will happen when you try to evaluate something from the unsafePerformIO. You can do that right away (seq'ing whatever the first atomicModifyIORef returned) if it makes you feel happier. EG (to take an actual example of something I use to implement composable events in Haskell) we can implement a function simpleToggle2 :: IORef Bool -> IORef Bool -> IO (Just (Bool,Bool)) which attempts to flip the two IORefs from True to False (if they are both True); otherwise returning their actual values. Then you could code this something like this (no I'm not going to check if it passes GHC) simpleToggle2 ioRef1 ioRef2 = do res <- atomicModifyIORef ioRef1 (\ contents1 -> unsafePerformIO (atomicModifyIORef ioRef2 (\ contents2 -> if contents1 && contents2 then (False,(False,Nothing)) else (contents2,(contents1,Just (contents1,contents2))) ) ) seq res (return res) Then the first atomicModifyIORef replaces the contents of ioRef1 by a thunk, and returns another thunk. The seq then proceeds to evaluate this thunk, causing the unsafePerformIO to be run, which changes ioRef2. There IS a potential problem, because if you run simpleToggle2 on the same ioRef simpleToggle2 ioRef ioRef or if two threads run simpleToggle2 simultaneously on the same ioRefs but in opposite order simpleToggle2 ioRef1 ioRef2 || simpleToggle2 ioRef2 ioRef1 or in general you have n threads simultaneously running simpleToggle on a cycle of ioRefs, you can get non-termination, because you will find your thunks get linked in a circular chain, with each one depending on the next. This is exactly the same as what happens if you attempt writeIORef x (unsafePerformIO (readIORef x)) and then attempt to evaluate the contents of x. However you also have exactly the same problem when you try to implement simpleToggle2 on MVar Bool, except there you get deadlock instead. The solution in both cases is to put some constraint on the ordering, for example construct some well-founded linear order on ioRefs such that simpleToggle2 ioRef1 ioRef2 is never called unless ioRef2 < ioRef1 (I think it's that way round). If you all you have is a data structure containing two IORefs, and the only accesses you want to these IORefs are (a) individual access, with a guaranteed terminating update function; (b) joint access, then the solution is simply to make sure that (say) you always access the first ioRef first. Then I think you have guaranteed termination. This is exactly the same with MVars. So although some Haskell purists (mentioning no names) might object to using unsafePerformIO like this, it does not seem to make matters worse than using MVars, since it's purely a question of taste whether you prefer non-termination or a deadlock.
Alastair:
On a system where finalizers behave like preemptive threads [nonsense deleted]
My outline of consequences/ implementation for GHC-like systems was completely wrong because I was still thinking about finalizers as special cases. What needs to happen on GHC-like systems is that runAtomically takes a global lock (just a plain lock, not a reader-writer lock) when it starts and releases that lock when it ends. Finalizers don't do anything special when they start or end and they don't get blocked in any special way. Finalizers just take and release the lock the same as anyone else. -- Alastair
participants (4)
-
Alastair Reid -
George Russell -
Malcolm Wallace -
Simon Marlow