RE: [Haskell-cafe] readEitherChan
On 19 June 2004 03:06, Thomas Hallgren wrote:
Tomasz Zielonka wrote:
On Tue, Jun 15, 2004 at 06:29:59PM -0400, S. Alexander Jacobson wrote:
readEitherChan::Chan a -> Chan b -> Either a b
eitherChan a b left right = readEitherChan a b >>= either left right
... I think it would be safer to create once new Chan (Either a b), and then read from it.
createEitherChan :: Chan a -> Chan b -> IO (Chan (Either a b))
Although createEitherChan might be the best solution for some application, it would be interesting to know what the recommended way to implement the function eitherChan above is, if that is what you really need?
The eitherChan function corresponds to guarded nondeterministic choice, usually written (a?P)+(b?Q) process calculi, i.e., a rather fundamental concurrency operator.
Section 5 of [1] enumerates some reasons why guarded nondeterministic choice is not available as a primitive in Concurrent Haskell. Section 5.2 describes a function select for nondeterministic choice, but I don't see how to use that to implement readEitherChan (or takeEitherMVar)...
It's a hard problem. Trying to code up takeEitherMVar by hand always seems to lead to solutions with race conditions - I can't see a way to do it. Perhaps takeEitherMVar should be provided as a primitive, but I'm concerned that the same problems will crop up if we tried to implement takeEitherMVar in a multi-threaded runtime (GHC doesn't currently have a true multi-threaded runtime, but we'd like to do it someday). So I think in order to do this you have to build another abstraction around MVars. I've attached some code I just hacked up to do just that; it's untested (but compiles), and has a couple of known deficiencies, but it might be along the right lines. Cheers, Simon
Simon Marlow wrote:
It's a hard problem. Trying to code up takeEitherMVar by hand always seems to lead to solutions with race conditions - I can't see a way to do it.
The following solution should be free from race conditions, takeEitherMVar :: MVar a -> MVar b -> IO (Either a b) takeEitherMVar mva mvb = do ma <- tryTakeMVar mva case ma of Just a -> return (Left a) Nothing -> do mb <- tryTakeMVar mvb case mb of Just b -> return (Right b) Nothing -> takeEitherMVar mva mvb but it has an efficiency problem, though...
Perhaps takeEitherMVar should be provided as a primitive, but I'm concerned that the same problems will crop up if we tried to implement takeEitherMVar in a multi-threaded runtime
Also, what if you wanted to choose between three variables?
So I think in order to do this you have to build another abstraction around MVars. I've attached some code I just hacked up to do just that; it's untested (but compiles), and has a couple of known deficiencies, but it might be along the right lines.
Thanks, I'll see if I can understand that... -- Thomas H
Cool! Why does it have an efficiency problem? And I would also observe that this solution doesn't work for readEitherChan because there is no tryReadChan. The naive tryReadChan tryReadChan chan = if isEmptyChan chan then return Nothing else return $ readChan chan leaves you vulnerable to race conditions. It looks like we have now have two very similar functions that, because they need the concrete representation, need to be added in the library: tryReadChan and tryReadSampleVar. Is there a systemic reason why these two very similar functions are absent? There is no point in my trying to add them if there is some *in principle* difficulty. The concurrent paper seems to indicate that there is something fundamentally suspect about a choice operator as a primitive. Is that issue related? Also, you wouldn't need these functions if Haskell's concurency model was defined to be non-preemptive. How come forkIO was not specifically defined to be non-preemptive (with forkOS dependent on the local OS native threading model)? Or alternatively, how come we have forkIO and forkOS as opposed to forkCooperative and forkPreemptive? -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com On Wed, 23 Jun 2004, Thomas Hallgren wrote:
Simon Marlow wrote:
It's a hard problem. Trying to code up takeEitherMVar by hand always seems to lead to solutions with race conditions - I can't see a way to do it.
The following solution should be free from race conditions,
takeEitherMVar :: MVar a -> MVar b -> IO (Either a b) takeEitherMVar mva mvb = do ma <- tryTakeMVar mva case ma of Just a -> return (Left a) Nothing -> do mb <- tryTakeMVar mvb case mb of Just b -> return (Right b) Nothing -> takeEitherMVar mva mvb
but it has an efficiency problem, though...
Perhaps takeEitherMVar should be provided as a primitive, but I'm concerned that the same problems will crop up if we tried to implement takeEitherMVar in a multi-threaded runtime
Also, what if you wanted to choose between three variables?
So I think in order to do this you have to build another abstraction around MVars. I've attached some code I just hacked up to do just that; it's untested (but compiles), and has a couple of known deficiencies, but it might be along the right lines.
Thanks, I'll see if I can understand that...
-- Thomas H
participants (3)
-
S. Alexander Jacobson -
Simon Marlow -
Thomas Hallgren