Before looking into the actual source code of the ST monad, I thought that ST must be something like newtype ST s a = ST (IO a) where the strict ST monad is based on normal IO bind function and lazy ST monad also uses unsafeInterleaveIO. Then runST would be just an unsafePerformIO. However when looking into http://darcs.haskell.org/packages/st it is in Control.Monad.ST.Lazy newtype ST s a = ST (State s -> (a, State s)) data State s = S# (State# s) and in Hugs.ST: newtype ST s a = ST (forall r. (a -> r) -> r) Both GHC and Hugs seem to use primitives, that are not available in JHC. Would my IO definition above be correct, at all? It seems that much of the code in the 'st' package could not be re-used in JHC.
On Sun, Nov 15, 2009 at 12:38:33AM +0100, Henning Thielemann wrote:
Before looking into the actual source code of the ST monad, I thought that ST must be something like
newtype ST s a = ST (IO a)
where the strict ST monad is based on normal IO bind function and lazy ST monad also uses unsafeInterleaveIO. Then runST would be just an unsafePerformIO.
However when looking into http://darcs.haskell.org/packages/st
it is in Control.Monad.ST.Lazy newtype ST s a = ST (State s -> (a, State s)) data State s = S# (State# s)
and in Hugs.ST: newtype ST s a = ST (forall r. (a -> r) -> r)
Both GHC and Hugs seem to use primitives, that are not available in JHC. Would my IO definition above be correct, at all? It seems that much of the code in the 'st' package could not be re-used in JHC.
In jhc, we would use something similar to what ghc does. the current IO definition is: newtype IO a = IO (World__ -> (# World__, a #)) So, the only difference would be ST takes any state, not just the world, or newtype ST s a = ST (s -> (# s, a #)) However, your definition might be better in practice, as it allows easy transformations between IO and ST as you noted, and there is no way to specify to jhc that the 's' parameter can be elided always so there is a chance it may make it into the runtime. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/
On Sat, Nov 14, 2009 at 04:15:40PM -0800, John Meacham wrote:
In jhc, we would use something similar to what ghc does. the current IO definition is:
newtype IO a = IO (World__ -> (# World__, a #))
So, the only difference would be ST takes any state, not just the world, or
newtype ST s a = ST (s -> (# s, a #))
It occurs to me that something like this would be closer to the ghc way..
data State s :: # newtype ST s a = ST (State s -> (# State s, a #))
then making IO
newtype IO a = ST World__ a
but just the newtype around IO is probably a better first pass as it won't require mucking with the IO implementation. Plus it will be portable to other compilers that have unsafePerformIO... John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/
John Meacham wrote:
On Sat, Nov 14, 2009 at 04:15:40PM -0800, John Meacham wrote:
In jhc, we would use something similar to what ghc does. the current IO definition is:
newtype IO a = IO (World__ -> (# World__, a #))
So, the only difference would be ST takes any state, not just the world, or
newtype ST s a = ST (s -> (# s, a #))
It occurs to me that something like this would be closer to the ghc way..
data State s :: # newtype ST s a = ST (State s -> (# State s, a #))
then making IO
newtype IO a = ST World__ a
but just the newtype around IO is probably a better first pass as it won't require mucking with the IO implementation. Plus it will be portable to other compilers that have unsafePerformIO...
well, it would be nice for such a "portable" implementation to exist... However, unsafePerformIO is often slower than an ST implementation has the potential to be (e.g. in GHC unsafePerformIO contains lots of safe-guards, each of which has been added after painful experience but which are not needed for ST itself). -Isaac
On Sun, 15 Nov 2009, Isaac Dupree wrote:
well, it would be nice for such a "portable" implementation to exist...
Voila http://darcs.haskell.org/packages/statethread/ It compiles, but I have not tested any program that uses it. Even with simplest examples using storablevector it depends largely on fortune whether they run or crash. So no chance to make reliable statements about something more complex.
However, unsafePerformIO is often slower than an ST implementation has the potential to be (e.g. in GHC unsafePerformIO contains lots of safe-guards, each of which has been added after painful experience but which are not needed for ST itself).
unsafePerformIO is needed only once per ST block, namely for runST. That should not be too often.
Henning Thielemann wrote:
On Sun, 15 Nov 2009, Isaac Dupree wrote:
well, it would be nice for such a "portable" implementation to exist...
Voila http://darcs.haskell.org/packages/statethread/
It compiles, but I have not tested any program that uses it. Even with simplest examples using storablevector it depends largely on fortune whether they run or crash. So no chance to make reliable statements about something more complex.
hmm, I looked at the code. I don't quite understand lazy ST, but I don't think that version you made is correct. The writes (and reads) really may not be re-ordered based on which data is demanded when. I think the distinctive thing about lazy ST is that the whole computation doesn't have to be executed before returning a result (so you can return an infinite list/computation, like, do{ a <- something; as <- recur; return (a:as) } ). But I can't figure out how to implement the correct behavior... (or if I'm just confused)...
However, unsafePerformIO is often slower than an ST implementation has the potential to be (e.g. in GHC unsafePerformIO contains lots of safe-guards, each of which has been added after painful experience but which are not needed for ST itself).
unsafePerformIO is needed only once per ST block, namely for runST. That should not be too often.
ah, right. (unsafeInterleaveIO isn't perfect either, but, first to consider correctness, as above)
On Sun, 15 Nov 2009, Isaac Dupree wrote:
hmm, I looked at the code. I don't quite understand lazy ST, but I don't think that version you made is correct. The writes (and reads) really may not be re-ordered based on which data is demanded when. I think the distinctive thing about lazy ST is that the whole computation doesn't have to be executed before returning a result (so you can return an infinite list/computation, like, do{ a <- something; as <- recur; return (a:as) } ). But I can't figure out how to implement the correct behavior... (or if I'm just confused)...
Thank you for spotting the problem so quickly. I have pushed a patch that hopefully solves the problem.
Henning Thielemann wrote:
On Sun, 15 Nov 2009, Isaac Dupree wrote:
hmm, I looked at the code. I don't quite understand lazy ST, but I don't think that version you made is correct. The writes (and reads) really may not be re-ordered based on which data is demanded when. I think the distinctive thing about lazy ST is that the whole computation doesn't have to be executed before returning a result (so you can return an infinite list/computation, like, do{ a <- something; as <- recur; return (a:as) } ). But I can't figure out how to implement the correct behavior... (or if I'm just confused)...
Thank you for spotting the problem so quickly. I have pushed a patch that hopefully solves the problem.
Hopefully. I'm afraid that might still be too much interleaving; consider for example the definition of (>>) and (writeSTRef r a >> writeSTRef r b); probably neither write will even happen, because the result () won't be demanded! or (writeSTRef r a >> readSTRef r) (Also don't forget interleaving in instance Applicative Lazy.ST, if the instances ultimately end up being involved)
That is, maximum laziness would be achieved, if there would be a state-thread for every reference.
indeed. Do you know if even GHC achieves this maximum laziness? I am undecided whether it is possible and/or practical. -Isaac
On Sun, 15 Nov 2009, Isaac Dupree wrote:
Hopefully. I'm afraid that might still be too much interleaving; consider for example the definition of (>>) and (writeSTRef r a >> writeSTRef r b); probably neither write will even happen, because the result () won't be demanded!
If we evaluate runST (newSTRef x >>= \r -> writeSTRef r a >> writeSTRef r b) none of the writeSTRefs would be executed. But this would be correct, wouldn't it?
or (writeSTRef r a >> readSTRef r)
If we evaluate runST (newSTRef x >>= \r -> writeSTRef r a >> readSTRef r) then readSTRef is triggered, because its result is requested and then because of the implementation of unsafeIOToST the previous actions are triggered. However, I see that I must implement strictToLazyST in terms of unsafeIOToST.
(Also don't forget interleaving in instance Applicative Lazy.ST, if the instances ultimately end up being involved)
indeed, I forgot that see new patch
Ah, I see you've put your machinations into StateT, in a way I admit I don't entirely understand but sounds plausible to me... other than how it looks to me that you end up wrapping all IO actions (like writeIORef) inside an unsafeInterleaveIO, and there is no lossless way to reverse that (no `seq`: might not be executed; `seq`: crashes on `return undefined`) But I think I figured out my own question: StateT makes all IO actions return a tuple type that's under its control. :-) other question is whether it works when you test it with things :-) -Isaac
participants (3)
-
Henning Thielemann -
Isaac Dupree -
John Meacham