Hello, I have some code that manipulates STRefs within the ST monad. All good and fine, until I come across some computation that uses lets say IO and everything skids to a halt. At this point I have 3 choices: 1. Define a ST State Transformer monad and do all my previous ST computations in that 2. convert all subsequent ST computations into IO computations using stToIO 3. stop using the ST monad and do everything in the IO monad I was wondering what advice folks had. In particular, what are the disadvantages to doing everything in the IO monad - ie why even bother with the ST monad? Any help appreciated cheers
Well, what to do with your computation depends on what that computation is actually doing. Is the IO really critical to your algorithm, or can it be done separately? Remember that pure computation is lazy and so you can save yourself from interleaving a lot of IO in with generating the data, if you are, for example, printing it as it is computed. Basically, the distinction between ST and IO you should worry about is the same as the one between pure values and IO. You don't want lots of computations in the IO monad, because IO computations are harder to reason about; it's harder to make guarantees about what they do. ST computations should be thought of as computing pure functions, similar to how ordinary Haskell functions would, except that they may have multiple named state variables which are carried along during the computation, and permit an imperative style of programming, for when that is more natural. (Various graph algorithms, for instance.) As far as I can tell, stToIO shouldn't be needed in ordinary programming. runST will serve quite well to extract a value from an ST computation. If what you are doing is fundamentally IO, and not just computing some function, then you should write your computation in the IO monad. Note that from the IO monad, you can hook up some pure computations (plain functions, ST, etc.) to do whatever kind of processing is needed to get from input to output. For this reason, when writing code in the IO monad, one should only really have to worry about the input and output to be performed. I hope this is useful, - Cale On 02/08/05, Srinivas Nedunuri <nedunuri@cs.utexas.edu> wrote:
Hello, I have some code that manipulates STRefs within the ST monad. All good and fine, until I come across some computation that uses lets say IO and everything skids to a halt. At this point I have 3 choices:
1. Define a ST State Transformer monad and do all my previous ST computations in that 2. convert all subsequent ST computations into IO computations using stToIO 3. stop using the ST monad and do everything in the IO monad
I was wondering what advice folks had. In particular, what are the disadvantages to doing everything in the IO monad - ie why even bother with the ST monad?
Any help appreciated
cheers
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
"Cale Gibbard" <cgibbard@gmail.com> wrote in message news:89ca3d1f05080300353ecd7fd5@mail.gmail.com... Well, what to do with your computation depends on what that computation is actually doing. Is the IO really critical to your algorithm, or can it be done separately? Remember that pure computation is lazy and so you can save yourself from interleaving a lot of IO in with generating the data, if you are, for example, printing it as it is computed. <<Alas, I wish I could seperate the IO from the ST. Unf the IO in question here is related to files and directories and the program I am writing (a simple version control program) manipulates a mutable object graph (hence the use of ST) and then interleaved with that needs to access File IO. runST isn't much use to me since I don't want to run anything "locally" (I believe that's what runST does - it manufactures an initial empty state and threads that through). Rather everything operates on this global object model. >> Basically, the distinction between ST and IO you should worry about is the same as the one between pure values and IO. You don't want lots of computations in the IO monad, because IO computations are harder to reason about; it's harder to make guarantees about what they do. ST computations should be thought of as computing pure functions, similar to how ordinary Haskell functions would, except that they may have multiple named state variables which are carried along during the computation, and permit an imperative style of programming, for when that is more natural. (Various graph algorithms, for instance.) << Can you elaborate on this a bit more? AFAIK, IO t is just ST RealWorld t. Since you never get to look at the state in an ST monad anyway, why does it matter (for the purposes of reasoning about your prgram) whether its RealWorld or some manufactured state? e.g. I have a function "f data = do x <- g data; y <- h x, etc." the only information I have is that the given computations will happen in that order given a suitable "state" value so referential transparency only extends as far as being able to say that f data can be replaced by its right hand side.
As far as I can tell, stToIO shouldn't be needed in ordinary programming. runST will serve quite well to extract a value from an ST computation. If what you are doing is fundamentally IO, and not just computing some function, then you should write your computation in the IO monad. Note that from the IO monad, you can hook up some pure computations (plain functions, ST, etc.) to do whatever kind of processing is needed to get from input to output. For this reason, when writing code in the IO monad, one should only really have to worry about the input and output to be performed. I hope this is useful, - Cale On 02/08/05, Srinivas Nedunuri <nedunuri@cs.utexas.edu> wrote:
Hello, I have some code that manipulates STRefs within the ST monad. All good and fine, until I come across some computation that uses lets say IO and everything skids to a halt. At this point I have 3 choices:
1. Define a ST State Transformer monad and do all my previous ST computations in that 2. convert all subsequent ST computations into IO computations using
stToIO
3. stop using the ST monad and do everything in the IO monad
I was wondering what advice folks had. In particular, what are the disadvantages to doing everything in the IO monad - ie why even bother with the ST monad?
Any help appreciated
cheers
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Srinivas Nedunuri wrote:
Hello, I have some code that manipulates STRefs within the ST monad. All good and fine, until I come across some computation that uses lets say IO and everything skids to a halt. At this point I have 3 choices:
1. Define a ST State Transformer monad and do all my previous ST computations in that 2. convert all subsequent ST computations into IO computations using stToIO 3. stop using the ST monad and do everything in the IO monad
I was wondering what advice folks had. In particular, what are the disadvantages to doing everything in the IO monad - ie why even bother with the ST monad?
The most obvious disadvantage is that the IO monad has no equivalent of runST. Also, there is no ioToST (only unsafeIOToST), so if you use the IO monad, the code can only be used within the IO monad. The IO monad is like a "trap"; once your inside, you can't get out. -- Glynn Clements <glynn@gclements.plus.com>
"Glynn Clements" <glynn@gclements.plus.com> wrote in message news:17136.35401.310280.912763@cerise.gclements.plus.com...
Srinivas Nedunuri wrote:
Hello, I have some code that manipulates STRefs within the ST monad. All good and fine, until I come across some computation that uses lets say IO and everything skids to a halt. At this point I have 3 choices:
1. Define a ST State Transformer monad and do all my previous ST computations in that 2. convert all subsequent ST computations into IO computations using stToIO 3. stop using the ST monad and do everything in the IO monad
I was wondering what advice folks had. In particular, what are the disadvantages to doing everything in the IO monad - ie why even bother with the ST monad?
The most obvious disadvantage is that the IO monad has no equivalent of runST.
OK, I'm missing something here. What is the big deal about runST? Can I not get the IO equivalent by simply running the program at the top level (assuming I don't have multiple threads going). Do you have a practical example of needing runST in several places in your program?
Also, there is no ioToST (only unsafeIOToST), so if you use the IO monad, the code can only be used within the IO monad. The IO monad is like a "trap"; once your inside, you can't get out. True but I'm effectively trappend now anyway. I have a bunch of ST code, and then somewhere in there I had the misfortune of needing to insert a file copy and bam I'm now stuck with the dang IO monad which goes and "infects" the entire program.
-- Glynn Clements <glynn@gclements.plus.com>
Hello, On 8/3/05, Srinivas Nedunuri <nedunuri@cs.utexas.edu> wrote:
The most obvious disadvantage is that the IO monad has no equivalent of runST. OK, I'm missing something here. What is the big deal about runST? Can I not get the IO equivalent by simply running the program at the top level (assuming I don't have multiple threads going). Do you have a practical example of needing runST in several places in your program?
Here is an example (not that I am suggesting that this is how we should write the function 'fib'). Notice the type of 'fib' --- there are no monads, even though the implementation internally uses state. import Control.Monad.ST import Data.STRef fib :: Int -> Int fib n = runST (do x <- newSTRef 1 y <- newSTRef 1 let loop n | n < 1 = return () loop n = do x' <- readSTRef x y' <- readSTRef y writeSTRef x y' writeSTRef y (x' + y') loop (n-1) loop n readSTRef x) -Iavor
OK thanks for the example. That makes sense. The state is being used locally and not exported, which if you were using the IO monad you would be forced to do cheers -s "Iavor Diatchki" <iavor.diatchki@gmail.com> wrote in message news:5ab17e79050803144943dacff6@mail.gmail.com... Hello, On 8/3/05, Srinivas Nedunuri <nedunuri@cs.utexas.edu> wrote:
The most obvious disadvantage is that the IO monad has no equivalent of runST. OK, I'm missing something here. What is the big deal about runST? Can I not get the IO equivalent by simply running the program at the top level (assuming I don't have multiple threads going). Do you have a practical example of needing runST in several places in your program?
Here is an example (not that I am suggesting that this is how we should write the function 'fib'). Notice the type of 'fib' --- there are no monads, even though the implementation internally uses state. import Control.Monad.ST import Data.STRef fib :: Int -> Int fib n = runST (do x <- newSTRef 1 y <- newSTRef 1 let loop n | n < 1 = return () loop n = do x' <- readSTRef x y' <- readSTRef y writeSTRef x y' writeSTRef y (x' + y') loop (n-1) loop n readSTRef x) -Iavor
On Wed, 2005-08-03 at 12:07 -0500, Srinivas Nedunuri wrote:
I was wondering what advice folks had. In particular, what are the disadvantages to doing everything in the IO monad - ie why even bother with the ST monad?
The most obvious disadvantage is that the IO monad has no equivalent of runST. OK, I'm missing something here. What is the big deal about runST? Can I not get the IO equivalent by simply running the program at the top level (assuming I don't have multiple threads going). Do you have a practical example of needing runST in several places in your program?
Having recently used the MonadReader and MonadState classes, I got the impression that ST should actually be deprecated. It seems to me that they are a relic from the time when there were no threads, i.e. when everything was in a single IO monad and you couldn't run another IO computation in independently. Nowadays, you can use one of the MonadState monad if you want lazy computation (on top of which you can implement state read and write accesses similar to IORefs) or IO-enabled computation (if you use MonadState.StateT and embed an IO monad at the core). Is this view correct? If not, could there be a comment as to what ST is useful (rather than a reference to a full blown paper that pre- dates the MonadState,... libraries). Axel.
Am Donnerstag, 4. August 2005 10:21 schrieb Axel Simon:
[...]
Nowadays, you can use one of the MonadState monad
State transformer monads like State and StateT can be implemented without using special language features. So there was always the opportunity to implement something like State or StateT. So, in a way, we always could use the MonadState monads. If ST could be replaced by MonadState monads, ST had never been included in the libraries, I suppose.
if you want lazy computation (on top of which you can implement state read and write accesses similar to IORefs) or IO-enabled computation (if you use MonadState.StateT and embed an IO monad at the core).
The point is that the MonadState monads don't give you update-in-place. Update-in-place is exactly the reason why ST is there.
Is this view correct? If not, could there be a comment as to what ST is useful (rather than a reference to a full blown paper that pre-dates the MonadState,... libraries).
ST is useful if you have to update small parts of an array since you don't have to construct a whole new array with ST. With ST you are able to update a single array element in O(1) time. In comparison, updating a single key's value in a finite map via State or StateT takes O(log n) time.
Axel.
Best regards, Wolfgang
On Thu, 2005-08-04 at 10:58 +0200, Wolfgang Jeltsch wrote:
Am Donnerstag, 4. August 2005 10:21 schrieb Axel Simon:
[...]
Nowadays, you can use one of the MonadState monad
State transformer monads like State and StateT can be implemented without using special language features. So there was always the opportunity to implement something like State or StateT. So, in a way, we always could use the MonadState monads. If ST could be replaced by MonadState monads, ST had never been included in the libraries, I suppose.
Well, MonadState needs multi-parameter type classes, and hence, require much more than ST.
if you want lazy computation (on top of which you can implement state read and write accesses similar to IORefs) or IO-enabled computation (if you use MonadState.StateT and embed an IO monad at the core).
The point is that the MonadState monads don't give you update-in-place. Update-in-place is exactly the reason why ST is there.
Ok, granted. In particular I take your point about array accesses. However, I am not quite convinced that using ST has any advantages over using IO directly. Of course, one could claim that programmers wants to protect themselves from themselves by disallowing arbitrary IO. But if that is the only "advantage" then I'd rather go for the flexibility to use arbitrary IO later on without having to rewrite my whole program. Thanks for you comment, Axel.
On Thu, 04 Aug 2005 10:09:06 +0100 Axel Simon <A.Simon@kent.ac.uk> wrote:
Ok, granted. In particular I take your point about array accesses. However, I am not quite convinced that using ST has any advantages over using IO directly. Of course, one could claim that programmers wants to protect themselves from themselves by disallowing arbitrary IO. But if that is the only "advantage" then I'd rather go for the flexibility to use arbitrary IO later on without having to rewrite my whole program.
This has been mentioned before, but the point of ST vs. IO is that you can encapsulate the update-in-place operations using runST and provide a purely functional interface to the outside world. If the external api doesn't need to expose the internal state and the library doesn't require IO internally, then ST gives the best of both worlds: a pure interface and efficiency. I think the Data.Graph algorithms in GHC's libraries are coded in this way. Regards, Pedro -- Pedro Vasconcelos, School of Computer Science, University of St Andrews ----------------------------------------------------------------------- "In theory there is no difference between theory and practice but in practice there is." -- Tony Davie
Am Donnerstag, 4. August 2005 11:09 schrieben Sie:
On Thu, 2005-08-04 at 10:58 +0200, Wolfgang Jeltsch wrote:
Am Donnerstag, 4. August 2005 10:21 schrieb Axel Simon:
[...]
Nowadays, you can use one of the MonadState monad
State transformer monads like State and StateT can be implemented without using special language features. So there was always the opportunity to implement something like State or StateT. So, in a way, we always could use the MonadState monads. If ST could be replaced by MonadState monads, ST had never been included in the libraries, I suppose.
Well, MonadState needs multi-parameter type classes, and hence, require much more than ST.
The class MonadState needs multi-parameter type classes but the monads State and StateT don't. If you switch the state and monad argument of StateT, you can also create a class which is a bit less flexible than MonadState but which nevertheless allows State and StateT to be instances of it: class StateMonad sm where put :: s -> sm s () get :: sm s s instance StateMonad State where ... instance Monad m => StateMonad (StateT m) where ... Note that sm in the class declaration has kind * -> *. So, multi-parameter classes have nothing to do with the ability to implement monads like State and StateT. These are just implemented as equivalent to ordinary functions via newtype.
[...]
However, I am not quite convinced that using ST has any advantages over using IO directly.
Of course, it has. As someone already pointed out, you can hide the imperativeness of a ST-implemented algorithm behind a purely functional interface by using runST.
[...]
Thanks for you comment, Axel.
Your welcome. Best regards, Wolfgang
On Thu, Aug 04, 2005 at 10:09:06AM +0100, Axel Simon wrote:
On Thu, 2005-08-04 at 10:58 +0200, Wolfgang Jeltsch wrote:
Am Donnerstag, 4. August 2005 10:21 schrieb Axel Simon:
[...]
Nowadays, you can use one of the MonadState monad
State transformer monads like State and StateT can be implemented without using special language features. So there was always the opportunity to implement something like State or StateT. So, in a way, we always could use the MonadState monads. If ST could be replaced by MonadState monads, ST had never been included in the libraries, I suppose.
Well, MonadState needs multi-parameter type classes, and hence, require much more than ST.
MonadState needs multi-parameter type classes, State and StateT don't. And ST needs rank-2 types (or at least one rank-2 constant) and, to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives).
if you want lazy computation (on top of which you can implement state read and write accesses similar to IORefs) or IO-enabled computation (if you use MonadState.StateT and embed an IO monad at the core).
The point is that the MonadState monads don't give you update-in-place. Update-in-place is exactly the reason why ST is there.
Ok, granted. In particular I take your point about array accesses. However, I am not quite convinced that using ST has any advantages over using IO directly. Of course, one could claim that programmers wants to protect themselves from themselves by disallowing arbitrary IO. But if that is the only "advantage" then I'd rather go for the flexibility to use arbitrary IO later on without having to rewrite my whole program.
Some algorithms are more naturally written imperatively and some programs are more efficient when written imperatively. The ST monad makes it possible to write programs which look imperative and actually _are_ imperative too but still could have been purely functional (given rank-2 types). I think one could call the ST monad a safe yet still efficient variant of unsafePerformIO + IORef's + IOArray's. Groeten, Remi -- Nobody can be exactly like me. Even I have trouble doing it.
Remi Turk wrote:
MonadState needs multi-parameter type classes, State and StateT don't. And ST needs rank-2 types (or at least one rank-2 constant) and, to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives).
I think one could call the ST monad a safe yet still efficient variant of unsafePerformIO + IORef's + IOArray's.
No, the point of ST is that it is safe (as opposed to unsafePerformIO), but still has the advantages of being both efficient and allowing purely functional encapsulation via runST (as oppesed to IORefs and IOArrays). The only price is that you need rank-2 polymorphism and new language primitives for creating, reading and writing references. But using these primitives is much better than using unsafePerformIO - the latter entails a lot of harmful things. -- Till Mossakowski Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen till@tzi.de P.O.Box 330440, D-28334 Bremen http://www.tzi.de/~till
On 8/4/05, Till Mossakowski <till@informatik.uni-bremen.de> wrote:
Remi Turk wrote:
MonadState needs multi-parameter type classes, State and StateT don't. And ST needs rank-2 types (or at least one rank-2 constant) and, to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives).
I think one could call the ST monad a safe yet still efficient variant of unsafePerformIO + IORef's + IOArray's.
No, the point of ST is that it is safe (as opposed to unsafePerformIO), but still has the advantages of being both efficient and allowing purely functional encapsulation via runST (as oppesed to IORefs and IOArrays). The only price is that you need rank-2 polymorphism and new language primitives for creating, reading and writing references. But using these primitives is much better than using unsafePerformIO - the latter entails a lot of harmful things.
Hmmm... Wasn't that what he said? /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
Sebastian Sylvan wrote:
On 8/4/05, Till Mossakowski <till@informatik.uni-bremen.de> wrote:
Remi Turk wrote:
MonadState needs multi-parameter type classes, State and StateT don't. And ST needs rank-2 types (or at least one rank-2 constant) and, to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives). I think one could call the ST monad a safe yet still efficient variant of unsafePerformIO + IORef's + IOArray's. No, the point of ST is that it is safe (as opposed to unsafePerformIO), but still has the advantages of being both efficient and allowing purely functional encapsulation via runST (as oppesed to IORefs and IOArrays). The only price is that you need rank-2 polymorphism and new language primitives for creating, reading and writing references. But using these primitives is much better than using unsafePerformIO - the latter entails a lot of harmful things.
Hmmm... Wasn't that what he said?
I disagree with the equation "primitives = unsafe" that is implicit in sentence to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives). The point is that ST uses *safe* primitives, and not "something like unsafePerformIO". To clarify things, here a little table about different possibilities of using arrays in Haskell: MonadState IOArray IOArray ST with with with FiniteMap unsafePerformIO MutArr safe yes yes no yes efficient no yes yes yes allows yes no yes yes functional encapsulation avoids yes no no no in-place- update primitives avoids yes yes yes no rank 2 -- Till Mossakowski Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen till@tzi.de P.O.Box 330440, D-28334 Bremen http://www.tzi.de/~till
Hello Till, Friday, August 05, 2005, 10:04:53 AM, you wrote: TM> MonadState IOArray IOArray ST TM> with with with TM> FiniteMap unsafePerformIO MutArr TM> safe yes yes no yes TM> efficient no yes yes yes afaik, ST efficient only with small enough arrays. one time i tried STArray of about 100 000 elements and seen that things goes much worse than in IO monad with IOArray. on small arrays STArray performs good enough (i was trying to create sorting routine. afair, it was an insert sort) -- Best regards, Bulat mailto:bulatz@HotPOP.com
Bulat Ziganshin wrote:
Hello Till,
Friday, August 05, 2005, 10:04:53 AM, you wrote:
TM> MonadState IOArray IOArray ST TM> with with with TM> FiniteMap unsafePerformIO MutArr
TM> safe yes yes no yes
TM> efficient no yes yes yes
afaik, ST efficient only with small enough arrays. one time i tried STArray of about 100 000 elements and seen that things goes much worse than in IO monad with IOArray. on small arrays STArray performs good enough
(i was trying to create sorting routine. afair, it was an insert sort)
That is weird, because in base/GHC/IOBase.lhs, IOArray is constructed on top of STArray: newtype IOArray i e = IOArray (STArray RealWorld i e) But maybe ghc has some special treatment of IOArray. Till -- Till Mossakowski Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen till@tzi.de P.O.Box 330440, D-28334 Bremen http://www.tzi.de/~till
On Fri, Aug 05, 2005 at 01:13:06PM +0400, Bulat Ziganshin wrote:
Hello Till,
Friday, August 05, 2005, 10:04:53 AM, you wrote:
TM> MonadState IOArray IOArray ST TM> with with with TM> FiniteMap unsafePerformIO MutArr
TM> safe yes yes no yes
TM> efficient no yes yes yes
afaik, ST efficient only with small enough arrays. one time i tried STArray of about 100 000 elements and seen that things goes much worse than in IO monad with IOArray. on small arrays STArray performs good enough
(i was trying to create sorting routine. afair, it was an insert sort)
It might have been caused by a recently fixed (in CVS) unfeature/bug, described on http://sourceforge.net/tracker/index.php?func=detail&aid=1019758&group_id=80... IIRC, if the same code could be used both for "ST s a" and for "IO a", GHC could fail to specialize the "ST s a" version because it had a typevariable too much. Groeten, Remi -- Nobody can be exactly like me. Even I have trouble doing it.
On Fri, Aug 05, 2005 at 08:04:53AM +0200, Till Mossakowski wrote:
Sebastian Sylvan wrote:
Hmmm... Wasn't that what he said?
I disagree with the equation "primitives = unsafe" that is implicit in sentence
to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives).
The point is that ST uses *safe* primitives, and not "something like unsafePerformIO".
Ah, I think I understand what we're disagreeing about exactly now. We're understanding "primitive" to mean different things :) You're seeing runST, newSTRef, writeSTRef etc as primitives, is that correct? I see them as the public interface to something which is implemented in something else. That is, just like the "memo" function (deprecated, from the package util) is a safe interface (memo is nicely referentially transparant) to a piece of functionality implemented using unsafe primitives (unsafePerformIO), the ST monad a perfectly safe abstraction built on top of not-so-safe primitives. And with primitives I mean unsafePerformIO in my previously attached implementation. In GHC's implementation, this is even more clear: writeSTRef :: STRef s a -> a -> ST s () writeSTRef (STRef var#) val = ST $ \s1# -> case writeMutVar# var# val s1# of { s2# -> (# s2#, () #) } (fptools/libraries/base/GHC/STRef.lhs) {-# INLINE runST #-} runST :: (forall s. ST s a) -> a runST st = runSTRep (case st of { ST st_rep -> st_rep }) {-# NOINLINE runSTRep #-} runSTRep :: (forall s. STRep s a) -> a runSTRep st_rep = case st_rep realWorld# of (# _, r #) -> r (fptools/libraries/base/GHC/ST.lhs) There is a lot of messing around with state here. Actually, runST(Rep) is remarkably similiar to unsafePerformIO: {-# NOINLINE unsafePerformIO #-} unsafePerformIO :: IO a -> a unsafePerformIO (IO m) = case m realWorld# of (# _, r #) -> r (fptools/libraries/base/GHC/IOBase.lhs) On Fri, Aug 05, 2005 at 08:12:36AM +0200, Till Mossakowski wrote:
Remi Turk wrote:
In a final attempt to convince someone of I'm not exactly sure what, I attached a simple implementation of the ST monad in terms of unsafePerformIO + IORef + IOArray.
OK, but you have to reason about this implementation to show that it is safe (which may be difficult because unsafePerformIO makes reasoning extremely difficult), while the primitives of ST are more easily proved to be safe.
Though it's certainly not a formal proof, it seems to be ok by both the "can you imagine an alternative, possibly horribly slow, but pure implementation" and by the "does it perform no observable side-effects and does it always yield the same value" criteria. However, this is almost what I meant: Assume you'd really like to have (1) the efficient histogram function from my previous message and (2) an efficient implementation of ixmap. You could implement both using unsafePerformIO + IOArray's and still be perfectly safe. However, you'd have to prove it's safe _twice_, both for (1) and for (2). The superior alternative is to first implement the ST monad using unsafePerformIO + IOArray's, proof that to be safe, and then implement (1) and (2) using ST without having to think about safety anymore. Happy hacking, Remi "We're probably agreeing 99.9% anyway" Turk -- Nobody can be exactly like me. Even I have trouble doing it.
Remi Turk wrote:
Ah, I think I understand what we're disagreeing about exactly now. We're understanding "primitive" to mean different things :)
You're seeing runST, newSTRef, writeSTRef etc as primitives, is that correct? I see them as the public interface to something which is implemented in something else.
The advantage of seeing runST, newSTRef, writeSTRef etc as primitives is that there is a denotational semantics for them (see Laucnbury/ Peyton Jones: "State in Haskell"), which coincides with the operational semantics. This is not the case for unsafePerformIO. unsafePerformIO is a purely operational primitive, although some uses of unsafePerformIO can a posteriori (and usually with a lot of handwaving) shown to behave in a good (denotational) way. The ghc file you cite should be regarded as operational detail, not as a language definition of runST, newSTRef, and writeSTRef.
Remi "We're probably agreeing 99.9% anyway" Turk
Yes, of course. Till -- Till Mossakowski Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen till@tzi.de P.O.Box 330440, D-28334 Bremen http://www.tzi.de/~till
Am Freitag, 5. August 2005 08:04 schrieb Till Mossakowski:
[...]
I disagree with the equation "primitives = unsafe" that is implicit in sentence
to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives).
The point is that ST uses *safe* primitives, and not "something like unsafePerformIO".
I think that the one which you cited refered to implementing the ST monad (which needs unsafe primitives, AFAIK) while you refer to implementing algorithms using the ST monad (which normally avoids unsafe primitives).
[...]
Best regards, Wolfgang
On Thu, Aug 04, 2005 at 10:40:01PM +0200, Till Mossakowski wrote:
Remi Turk wrote:
MonadState needs multi-parameter type classes, State and StateT don't. And ST needs rank-2 types (or at least one rank-2 constant) and, to be implemented _efficiently_, also needs something like unsafePerformIO (or even lower-level unsafe mutable state primitives).
I think one could call the ST monad a safe yet still efficient variant of unsafePerformIO + IORef's + IOArray's.
No, the point of ST is that it is safe (as opposed to unsafePerformIO), but still has the advantages of being both efficient and allowing purely functional encapsulation via runST (as oppesed to IORefs and IOArrays). The only price is that you need rank-2 polymorphism and new language primitives for creating, reading and writing references. But using these primitives is much better than using unsafePerformIO - the latter entails a lot of harmful things.
As I agree with everything after the "No" I guess there is a new misunderstanding in the world :) I'll try to clarify what I meant: Occasionally, one would like to write a piece of code which performs updates in place. As an example I'll use a function hist :: [Char] -> [(Char, Int)] which returns a histogram of (lowercase) letters. The most efficient (and to many also most obvious) way to implement this function is using an mutable array of letters to occurrence counts. One way to implement "hist" is then something like: hist str = unsafePerformIO (do arr <- newArray ... mapM_ (\x -> ...) str getAssocs arr ) which is safe, as it does not have observable side-effects and always yields the same value for a given argument. Still, the proof obligation that it actually is safe lies with the programmer, each time he implements something like "hist". In general, if some IO-action "foo" is pure except for its use of IORef's and IOArray's, and it only uses ones it created itself, and doesn't return any of them, it _cannot_ have observable side-effects and will always yield the same value and hence "unsafePerformIO foo" _will always be safe_. This can be abstracted into a "design pattern" ;), called "the ST monad", thus only requiring the programmer to give a "this use of unsafePerformIO is safe"-proof once for runST, instead of each time he implements a "hist"-like function. (See attached modules.) Hm, I'm not sure whether this can meaningfully be called a "clarification". Oh well :) In a final attempt to convince someone of I'm not exactly sure what, I attached a simple implementation of the ST monad in terms of unsafePerformIO + IORef + IOArray. And as a really-I-mean-it final remark,
I think one could call the ST monad a safe yet still efficient variant of unsafePerformIO + IORef's + IOArray's. , could probably be phrased better as the "ST monad can be seen as a safe subset of the functionality of unsafePerformIO + IORef + IOArray."
Cheers, Remi -- Nobody can be exactly like me. Even I have trouble doing it.
Remi Turk wrote:
In a final attempt to convince someone of I'm not exactly sure what, I attached a simple implementation of the ST monad in terms of unsafePerformIO + IORef + IOArray.
OK, but you have to reason about this implementation to show that it is safe (which may be difficult because unsafePerformIO makes reasoning extremely difficult), while the primitives of ST are more easily proved to be safe. -- Till Mossakowski Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen till@tzi.de P.O.Box 330440, D-28334 Bremen http://www.tzi.de/~till
Am Mittwoch, 3. August 2005 19:07 schrieb Srinivas Nedunuri:
[...]
I have a bunch of ST code, and then somewhere in there I had the misfortune of needing to insert a file copy and bam I'm now stuck with the dang IO monad which goes and "infects" the entire program.
You can use something like myPureComputation :: String -> ST s Int where the parameter denotes the file content. Then you do something like this: do fileContent <- readFile "myFile" print $ runST $ myPureComputation fileContent So you don't need to infect your ST computation with I/O the same way you often don't need to infect an ordinary pure calculation with I/O. Or did you mean something different?
[...]
Regards, Wolfgang
participants (11)
-
Axel Simon -
Bulat Ziganshin -
Cale Gibbard -
Glynn Clements -
Iavor Diatchki -
Pedro Vasconcelos -
Remi Turk -
Sebastian Sylvan -
Srinivas Nedunuri -
Till Mossakowski -
Wolfgang Jeltsch