RE: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
(Dropping [EMAIL PROTECTED])
Hi,
We've not yet looked at I/O in detail in Haskell, but there's a paper from a
few years back where I experimented with ways of integrating I/O with an
earlier implementation of atomic blocks in Java.
http://research.microsoft.com/~tharris/papers/2005-scp.pdf
The basic idea is to provide a way for a transaction to call into
transaction-aware libraries. The libraries can register callbacks for if the
transaction commits (to actually do any "O") and for if the transaction aborts
(to re-buffer any "I" that the transaction has consumed). In addition, a
library providing access to another transactional abstraction (e.g. a database
supporting transactions) can perform a 2-phase commit that means that the
memory transaction and database transaction either both commit or both abort.
Of course, these solutions don't deal with the question of atomic blocks that
want to perform output (e.g. to the console) and receive input in response to
that. My view at the moment is _that does not make sense in an atomic block_
-- the output and input can't be performed atomically because the intervening
state must be visible for the user to respond to.
We also briefly experimented with extending the SXM system Maurice Herlihy
worked on at MSR Cambridge to support transactions that include accesses to the
file system and registry --
http://msdn2.microsoft.com/en-us/library/aa366295.aspx describes the TxF and
TxR systems it was built over.
Some other interesting work in this area is Elliot Moss' papers on "open
nested" transactions -- these provide another building block at the same level
as the Java system I mentioned: library writers can use them with care to
extend the range of things that can be done inside an atomic block.
Cheers,
Tim
-Original Message-
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Benjamin Franksen
Sent: 24 November 2006 03:16
To: haskell@haskell.org
Cc: haskell-cafe@haskell.org
Subject: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
[sorry for quoting so much, kinda hard to decide here where to snip]
Cale Gibbard wrote:
> On 23/11/06, Jason Dagit <[EMAIL PROTECTED]> wrote:
>> A comment on that video said:
>>
>> - BEGIN QUOTE
>> It seems to me that STM creates new problems with composability.
>> You create two classes of code: atomic methods and non atomic methods.
>>
>> Nonatomic methods can easily call atomic ones ? the compiler could
>> even automatically inject the atomic block if the programmer forgot.
>>
>> Atomic methods and blocks cannot be allowed to call nonatomic code.
>> The nonatomic code could do I/O or other irrevocable things that would
>> be duplicated when the block had to retry.
>> END QUOTE
>>
>> I imagine an example like this (some pseudo code for a side effect
>> happy OO language):
>>
>> class Foo {
>> protected int counter; // assume this gets initialized to 0
>> public doSomething() {
>> atomic{
>> counter++;
>> Console.Write("called doSomething execution# " + counter);
>> // something which could cause the transaction to restart
>> }
>> }
>> public doOtherThing() {
>> atomic{
>> doSomething();
>> // something which could cause the transaction to restart
>> }
>> }
>> }
>>
>> Now imagine doSomething gets restarted, then we see the console output
>> once each time and counter gets incremented. So one solution would be
>> to move the side effects (counter++ and the console write) to happen
>> before the atomic block. This works for doSomething, but now what if
>> we called doOtherThing instead? We're back to having the extra
>> side-effects from the failed attempts at doSomething, right? We just
>> lost composability of doSomething? I'm assuming counter is only meant
>> to be incremented once per successful run of doSomething and we only
>> want to see the output to the log file once per successful run, but it
>> needs to come before the log output inside doSomething so that the log
>> makes sense.
>>
>> I realize STM is not a silver bullet, but it does seem like
>> side-effects do not play nicely with STM. What is the proposed
>> solution to this? Am I just missing something simple? Is the
>> solution to make it so that Console.Write can be rolled back too?
>
> The solution is to simply not allow side effecting computations in
> transactions. They talk a little about it in the video, but perhaps
> that's not clear. The only side effects an atomic STM transaction may
> have are
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
Hi, On 23/11/06, Benjamin Franksen <[EMAIL PROTECTED]> wrote: One answer is in fact "to make it so that Console.Write can be rolled back too". To achieve this one can factor the actual output to another task and inside the transaction merely send the message to a transactional channel (TChan): So, you could simply return the console output as (part of) the result of the atomic action. Wrap it in a WriterT monad transformer, even. (one, console) <- atomic $ runWriterT $ do tell "hello world\n" return 1 putStr console (Not terribly efficient, but you get the idea.) You're just calculating what output to make inside the transaction; the actual outputting happens outside, once the transaction commits. Another task regularly takes messages from the channel With STM, the outputter task won't see any messages from the channel until your main atomic block completes, after which you're living in IO-land, so you might as well do the output yourself. Pugs/Perl 6 takes the approach that any IO inside an atomic block raises an exception. Unfortunately I can't see how to generalize this to input as well... The dual of how you described the output situation: read a block of input before the transaction starts, and consume this during the transaction. I guess you're not seeing how this generalises because potentially you won't know how much of the input you will need to read beforehand... (so read all available input?(!) You have the dual situation in the output case, in that you can't be sure how much output it may generate / you will need to buffer.) input <- hGetContent file atomic $ flip runReaderT input $ do input <- ask -- do something with input return 42 (This is actually a bad example, since hGetContents reads the file lazily with interleaved IO...) later, /Liyang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
| The basic idea is to provide a way for a transaction to call into
transaction-aware libraries. The libraries
| can register callbacks for if the transaction commits (to actually do any
"O") and for if the transaction
| aborts (to re-buffer any "I" that the transaction has consumed). In
addition, a library providing access
| to another transactional abstraction (e.g. a database supporting
transactions) can perform a 2-phase
| commit that means that the memory transaction and database transaction either
both commit or both
| abort.
Yes, I have toyed with extending GHC's implementation of STM to support
onCommit :: IO a -> STM ()
The idea is that onCommit would queue up an IO action to be performed when the
transaction commits, but without any atomicity guarantee. If the transaction
retries, the action is discarded. Now you could say
atomic (do {
xv <- readTVar x
yv <- readTVar y
if xv>yv then
onCommit launchMissiles
else return () })
and the missiles would only get launched when the transaction successfully
commits.
This is pure programming convenience. It's always possible to make an existing
Haskell STM transaction that *returns* an IO action, which is performed by the
caller, thus:
dO { action <- atomic (do {
xv <- readTVar x;
yv <- readTVar y;
if xv>yv then
retur launchMissiles
else return (return ()) }) ;
action }
All onCommit does is make it more convenient. Perhaps a *lot* more convenient.
I have also toyed with adding
retryWith :: IO a -> STM ()
The idea here is that the transction is undone (i.e. just like the 'retry'
combinator), then the specified action is performed, and then the transaction
is retried. Again no atomicity guarantee. If there's an orElse involved, both
actions would get done.
Unlike onCommit, onRetry adds new power. Suppose you have a memory buffer,
with an STM interface:
getLine :: Buffer -> STM STring
This is the way to do transactional input: if there is not enough input, the
transaction retries; and the effects of getLine aren't visible until the
transaction commits. The problem is that if there is not enough data in the
buffer, getLine will retry; but alas there is no way at present to "tell"
someone to fill the buffer with more data.
onRetry would fix that. getLine could say
if then retryWith
It would also make it possible to count how many retries happened:
atomic ( `orElse` retryWith )
I have not implemented either of these, but I think they'd be cool.
Simon
PS: I agree wholeheartedly with this:
| Of course, these solutions don't deal with the question of atomic blocks that
want to perform output
| (e.g. to the console) and receive input in response to that. My view at the
moment is _that does not
| make sense in an atomic block_ -- the output and input can't be performed
atomically because the
| intervening state must be visible for the user to respond to.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
On Fri, Nov 24, 2006 at 08:22:36AM +, Simon Peyton-Jones wrote: > I have also toyed with adding > > retryWith :: IO a -> STM () > > The idea here is that the transction is undone (i.e. just like the 'retry' > combinator), then the specified action is performed, and then the transaction > is retried. Again no atomicity guarantee. If there's an orElse involved, > both actions would get done. > > Unlike onCommit, onRetry adds new power. Suppose you have a memory > buffer, with an STM interface: > getLine :: Buffer -> STM STring [Sorry for a long email, I had no time to make it short ;-)] Another example would be my experiments with supporting time in STM, ie. functions: retryIfBefore :: UTCTime -> STM () retryIfAfter :: UTCTime -> STM () (Current code can be obtained with "darcs get" from http://www.uncurry.com/haskell/stm-time/. BTW, shout if you want such a library - it will motivate me to finally release it officially). The naive implementation could hold UTCTime in a single TVar and update this variable in a loop, say, 100 times a second. Of course, with many threads using retryIfBefore/retryIfAfter this would cause too many retries. In my implementation I split the time TVar into a list of TVars, each holding a bit of time representation. The retryIf* functions are written in such a way, that they retry as soon as they can tell that it's too early or too late. This way the number of retries for (retryIfBefore then) is at most the length of suffix of bits that differ in representation of "now" and "then". But there is still a problem with accuracy. Ideally, we would like to be as accurate as possible. One solution goes like this: if retryIfBefore retries because the time value stored in variables is too low, let's allow it to notify the manager thread what UTCTime it is waiting for, so it can schedule to update the variables exactly at this moment. That's where retryWith would help. Right now I am using something named autonomous transactions: autonomously :: Bool -> STM a -> STM () This basically forks a new thread to perform the given transaction outside of the current transaction. To be fair, I am not sure it is sound - as you can imagine, the implementation uses some dirty tricks like unsafeIOToSTM. I haven't checked what would happen if I used some variables created in the surrounding transaction. BTW, implementing STM.Time was very instructive for me. It made me realize that I didn't understand STM as well as I thought. Perhaps it could be made in a nice tutorial, if it wasn't so riddled with unsafish stuff: unsafeIOToSTM mentioned above, and unsafePerformIO used to initialize a top-level variable *and* spawn a manager thread. Here retryWith could also help - I fork the manager thread with it. > I have not implemented either of these, but I think they'd be cool. I agree especially about retryWith. But I think it's name should include a "danger! sign", because when used wrong, it can "break" the nice properties of STM and cause very surprising bugs. For me one good "danger" indicator is "IO", so perhaps "retryWithIO" ? Best regards Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
On Fri, Nov 24, 2006 at 10:02:59AM +0100, Tomasz Zielonka wrote: > That's where retryWith would help. Right now I am using something named > autonomous transactions: > > autonomously :: Bool -> STM a -> STM () > > This basically forks a new thread to perform the given transaction > outside of the current transaction. Forgot to explain this Bool parameter: it controls whether the enclosing transaction is waiting for the autonomous transaction to finish. I don't really like this idea, but it allowed to gain some small efficiency advantage, decreasing the number of retries. Best regards Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM- video
this thread reminds me about something that I wanted to ask you. if I recall correctly, most of the literature references in STM papers are recent, so I wondered whether you are aware of this one: NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM SourceTechnical Report: TR-205 Year of Publication: 1978 Author D. P. Reed I'm not entirely sure where I got my version from (it was mentioned as a cornerstone in Alan Kay et al s latest project, Croquet, on which Reed is a collaborator: http://www.opencroquet.org/ ), but here is the abstract: http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=889815 (note that it mentions both grouping of updates, and synchronized composition of modules with local synchronization constraints) and this might be the official site for the scanned copy (?): http://www.lcs.mit.edu/publications/specpub.php?id=773 just wondering, claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM- video
Interesting reference. I had never heard of it. From reading section 1.2 it sounds like an early description of the optimistic approach to implementing atomic transactions (which is itself a well-studied field). Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Claus | Reinke | Sent: 24 November 2006 12:22 | To: Simon Peyton-Jones; Tim Harris (RESEARCH) | Cc: haskell-cafe@haskell.org | Subject: Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM- video | | this thread reminds me about something that I wanted to ask you. | if I recall correctly, most of the literature references in STM papers | are recent, so I wondered whether you are aware of this one: | | NAMING AND SYNCHRONIZATION IN A | DECENTRALIZED COMPUTER SYSTEM | | SourceTechnical Report: TR-205 | Year of Publication: 1978 | Author D. P. Reed | | I'm not entirely sure where I got my version from (it was mentioned | as a cornerstone in Alan Kay et al s latest project, Croquet, on which | Reed is a collaborator: http://www.opencroquet.org/ ), but here is | the abstract: | | http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=889815 | | (note that it mentions both grouping of updates, and synchronized | composition of modules with local synchronization constraints) | | and this might be the official site for the scanned copy (?): | | http://www.lcs.mit.edu/publications/specpub.php?id=773 | | just wondering, | claus | | ___ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
I was inspired by Simon's post to kludge up a working prototype that does what
is discussed:
Simon Peyton-Jones wrote:
> | The basic idea is to provide a way for a transaction to call into
> transaction-aware libraries. The libraries
> | can register callbacks for if the transaction commits (to actually do any
> "O") and for if the transaction
> | aborts (to re-buffer any "I" that the transaction has consumed). In
> addition, a library providing access
> | to another transactional abstraction (e.g. a database supporting
> transactions) can perform a 2-phase
> | commit that means that the memory transaction and database transaction
> either both commit or both
> | abort.
>
> Yes, I have toyed with extending GHC's implementation of STM to support
>
> onCommit :: IO a -> STM ()
>
> The idea is that onCommit would queue up an IO action to be performed when
> the transaction commits, but without any atomicity guarantee. If the
> transaction retries, the action is discarded. Now you could say
>
> I have also toyed with adding
>
> retryWith :: IO a -> STM ()
>
> The idea here is that the transction is undone (i.e. just like the 'retry'
> combinator), then the specified action is performed, and then the transaction
> is retried. Again no atomicity guarantee. If there's an orElse involved,
> both actions would get done.
>
> It would also make it possible to count how many retries happened: atomic
> ( `orElse` retryWith )
>
> I have not implemented either of these, but I think they'd be cool.
>
> Simon
The prototype is:
{- November 24th, 2006
Demonstration Code by Chris Kuklewicz <[EMAIL PROTECTED]>
Usual 3 clause BSD Licence
Copyright 2006
This is inspired by a post by Simon Peyton-Jones on the haskell-cafe
mailing list, in which the type and semantics of onCommit and
withRetry were put forth.
The semantics of printing the contents of the TVar "v" created in
test via retryWith may or may not be well defined. With GHC 6.6 I get
*AdvSTM> main
"hello world"
"retryWith Start"
("retryWith v",7)
"Flipped choice to True to avoid infinite loop"
"onCommit Start"
("onCommit v",42)
("result","foo")
"bye world"
Aside from that I think the unsafeIOToSTM is not really unsafe here
since it writes to privately created and maintained variables.
Since the implementation is hidden it could be changed from ReaderT
to some other scheme.
Once could also use MonadBase from
http://haskell.org/haskellwiki/New_monads/MonadBase to help with the
lifting, but this has been commented out below.
TODO: figure out semantics of catchAdv. At least it compiles...
-}
module AdvSTM(MonadAdvSTM(..),AdvSTM,retryWith) where
-- import MonadBase
import Control.Exception(Exception)
import Control.Monad(MonadPlus(..),liftM)
import Control.Monad.Reader(MonadReader(..),ReaderT,runReaderT,lift,asks)
import Control.Concurrent.STM(STM,orElse,retry,catchSTM,atomically)
import Control.Concurrent.STM.TVar(TVar,newTVarIO,newTVar,readTVar,writeTVar)
import GHC.Conc(unsafeIOToSTM)
import Data.IORef(IORef,newIORef,readIORef,writeIORef,modifyIORef)
import Data.Typeable(Typeable)
import Data.Generics(Data)
class MonadAdvSTM m where
onCommit :: IO a -> m ()
onRetry :: IO a -> m ()
orElseAdv :: m a -> m a -> m a
retryAdv :: m a
atomicAdv :: m a -> IO a
catchAdv :: m a -> (Exception -> m a) -> m a
liftAdv :: STM a -> m a
-- Export type but not constructor!
newtype AdvSTM a = AdvSTM (ReaderT (CommitVar,RetryVar) STM a) deriving
(Functor,Monad,MonadPlus,Typeable)
type CommitVar = TVar ([IO ()]->[IO ()])
type RetryVar = IORef ([IO ()]->[IO ()])
{- Since lifting retry and `orElse` gives the semantics Simon wants, use
deriving MonadPlus instead
instance MonadPlus AdvSTM where
mzero = retryAdv
mplus = orElseAdv
-}
-- instance MonadBase STM AdvSTM where liftBase = AdvSTM . lift
retryWith :: IO a -> AdvSTM b
retryWith io = onRetry io >> retryAdv
instance MonadAdvSTM AdvSTM where
onCommit io = do
cv <- AdvSTM $ asks fst
old <- liftAdv $ readTVar cv
liftAdv $ writeTVar cv (old . ((io >> return ()):))
onRetry io = do
rv <- AdvSTM $ asks snd
liftAdv $ unsafeIOToSTM $ modifyIORef rv (\ old -> old . ((io >> return
()):) )
{-
orElseAdv (AdvSTM a) (AdvSTM b) =
{- If a retries then its onRetry commands are kept on the list of
actions to do if the whole command fails. It would be possible
to save the "rv" and use unsafeIOToSTM to implement a different
policy here -}
AdvSTM $ do env <- ask
lift $ (runReaderT a env) `orElse` (runReaderT b env)
-}
orElseAdv = mplus
retryAdv = liftAdv retry -- the same as retryAdv = mzero
atomicAdv = runAdvSTM
catchAdv (AdvSTM action) handler =
let h env error = let (AdvSTM cleanup) = handler error
in runReaderT cleanup env
in AdvSTM $ do env <- ask
lift $ catchSTM (runReaderT action env) (h env)
liftAdv = AdvSTM . lift
-- This replaces "atomica
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
Hi, I got this working on Mac OS X. I had to download media player 9: http://www.microsoft.com/windows/windowsmedia/software/Macintosh/osx/default.aspx This contains the WMV3 codec. Cheers, Chris. On Fri, 24 Nov 2006, James William Pye wrote: > On Fri, Nov 24, 2006 at 10:26:38AM +0100, Tomasz Zielonka wrote: > > Does anybody know how to watch this on Linux? I would prefer to simply > > download the movie file and use MPlayer on that, but I failed. > > > > . or on Mac OS X (haven't tried yet) > > The latest mplayer works for me on FreeBSD/amd64 (1.0rc1, iirc). > ___ > Haskell mailing list > Haskell@haskell.org > http://www.haskell.org/mailman/listinfo/haskell > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
I posted an improved version of the new monad to the wiki at
http://haskell.org/haskellwiki/New_monads/MonadAdvSTM
Observations:
** This idiom made it easy for the retrying case to queue an action which
ensures success in the next attempt.
** More than one operation can be queued for both the commit and the retry
possibilities.
** Reading the TVar in the onRetry/retryWith branch sees the "rolled back"
value, which luckily is the initialization value instead of undefined in the
case where the TVar was created in the aborted block.
** The new code includes unlift* operations which makes the STM code in
testUnlift much easier to write.
The relevant example its output are now:
-- Example code using the above, lifting into MonadAdvSTM:
test ::(Monad m, MonadAdvSTM m) => TVar Bool -> m [Char]
test todo = do
onCommit (print "onCommit Start")
onRetry (print "onRetry Start")
v <- liftAdv $ newTVar 7
liftAdv $ writeTVar v 42
onCommit (atomically (readTVar v) >>= \x->print ("onCommit v",x))
onRetry (atomically (readTVar v) >>= \x->print ("onRetry v",x))
choice <- liftAdv $ readTVar todo
case choice of
True -> return "foo"
False -> retryWith $ do
atomically (writeTVar todo True)
print "Flipped choice to True to avoid infinite loop"
-- Same example as test, but unlifting from AdvSTM
testUnlift :: TVar Bool -> AdvSTM [Char]
testUnlift todo = do
onCommit <- unlift1 onCommit
onRetry <- unlift1 onRetry
retryWith <- unlift1 retryWith
liftAdv $ do
onCommit (print "onCommit Start")
onRetry (print "onRetry Start")
v <- newTVar 7
writeTVar v 42
onCommit (atomically (readTVar v) >>= \x->print ("onCommit v",x))
onRetry (atomically (readTVar v) >>= \x->print ("onRetry v",x))
choice <- readTVar todo
case choice of
True -> return "foo"
False -> retryWith $ do
atomically (writeTVar todo True)
print "Flipped choice to True to avoid infinite loop"
-- Example similar to Simon's suggested example:
countRetries :: (MonadAdvSTM m, Monad m, Enum a) => IORef a -> m a1 -> m a1
countRetries ioref action =
let incr = do old <- readIORef ioref
writeIORef ioref $! (succ old)
in action `orElseAdv` (retryWith incr)
-- Load this file in GHCI and execute main to run the test:
main = do
counter <- newIORef 0
todo <- newTVarIO False
print "test"
result <- runAdvSTM (countRetries counter $ test todo)
retries <- readIORef counter
print ("result",result,"retries",retries)
atomically (writeTVar todo False)
print "testUnlift"
result <- runAdvSTM (countRetries counter $ testUnlift todo)
retries <- readIORef counter
print ("result",result,"retries",retries)
print "bye world"
The output in GHCI is
*AdvSTM> main
"test"
"onRetry Start"
("onRetry v",7)
"Flipped choice to True to avoid infinite loop"
"onCommit Start"
("onCommit v",42)
("result","foo","retries",1)
"testUnlift"
"onRetry Start"
("onRetry v",7)
"Flipped choice to True to avoid infinite loop"
"onCommit Start"
("onCommit v",42)
("result","foo","retries",2)
"bye world"
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
Simon Peyton-Jones wrote: > I have also toyed with adding > > retryWith :: IO a -> STM () > > The idea here is that the transction is undone (i.e. just like the 'retry' combinator), then the specified action is performed, and then the transaction is retried. Again no atomicity guarantee. If there's an orElse involved, both actions would get done. > > Unlike onCommit, onRetry adds new power. Suppose you have a memory buffer, > with an STM interface: > getLine :: Buffer -> STM STring > > This is the way to do transactional input: if there is not enough input, the transaction retries; and the effects of getLine aren't visible until the transaction commits. The problem is that if there is not enough data in the buffer, getLine will retry; but alas there is no way at present to "tell" someone to fill the buffer with more data. > > onRetry would fix that. getLine could say > if then retryWith > > It would also make it possible to count how many retries happened: >atomic ( `orElse` retryWith ) > > I have not implemented either of these, but I think they'd be cool. > > Simon After seeing how close I could come to creating onRetry/retryWith I have a question about the semantics of your idea for retryWith. Normally after a retry the STM block is rolled back and put to sleep and will only be awakened and re-executed if one of the STM variables it had read from is committed to by a different STM block. What about retryWith ? Will the STM block be put to sleep under the same conditions? Can the IO action given to retryWith include commits to STM variables? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
| Normally after a retry the STM block is rolled back and put to sleep and will | only be awakened and re-executed if one of the STM variables it had read from is | committed to by a different STM block. The *semantics* are that it is retried anytime in the future. The *pragmatics* are as you describe. | What about retryWith ? Will the STM block be put to sleep under the same | conditions? Can the IO action given to retryWith include commits to STM variables? The semantics are the same as before: the action passed to retryWith is run, and the block is retried anytime in the future. The pragmatics are the same: the action passed to retryWith is run, and the block is put to sleep only to be awakened if one of the STM variables it has read from has been written to -- which could have happened already if the IO action did so. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
Hi,
> After seeing how close I could come to creating onRetry/retryWith I have a
> question about the semantics of your idea for retryWith.
>
> Normally after a retry the STM block is rolled back and put to sleep and
> will
> only be awakened and re-executed if one of the STM variables it had read
> from is
> committed to by a different STM block.
>
> What about retryWith ? Will the STM block be put to sleep under the same
> conditions? Can the IO action given to retryWith include commits to STM
> variables?
Starting with this last question -- yes, the example of an STM GetLine using
retryWith to pull more input into a buffer relies on an atomic block in the IO
action to update the buffer.
There are some interesting questions to think about the semantics of
"retryWith". The semantics of "retry" in the PPoPP paper say nothing about
putting threads to sleep -- it would be correct for an implementation to spin
repeatedly executing an "atomic" block until it completes without calling
"retry". What should happen with "retryWith" -- should we introduce blocking &
wake-up into the semantics, or say that the "retryWith" actions are collected
together, executed in place of the transaction (if it does ultimately retry)
and then the transaction re-attempted? For simplicity (and to leave
flexibility to the implementation) I'd prefer to keep blocking & wake-up out of
the semantics.
Taking that option, suppose we have "atomic { X }" and X retries with IO action
Y. I think I'm saying that that would be equivalent to "Y ; atomic { X }".
What are the consequences of this? In the GetLine example it means that an
implementation that does put threads to sleep must detect conflicts between the
first execution of X and any transactions performed in Y.
Are there any interesting problems that come up if "Y" performs transactions
that use "retry" or "retryWith"?
Tim
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
Here I restate what you obviously know several times, then take a shot at
answering your final question.
Tim Harris (RESEARCH) wrote:
> Hi,
>
>> After seeing how close I could come to creating onRetry/retryWith I have a
>> question about the semantics of your idea for retryWith.
>>
>> Normally after a retry the STM block is rolled back and put to sleep and
>> will
>> only be awakened and re-executed if one of the STM variables it had read
>> from is
>> committed to by a different STM block.
>>
>> What about retryWith ? Will the STM block be put to sleep under the same
>> conditions? Can the IO action given to retryWith include commits to STM
>> variables?
>
> Starting with this last question -- yes, the example of an STM GetLine using
retryWith to pull more input into a buffer relies on an atomic block in the IO
action to update the buffer.
That makes such (atomic X) actions which call (retryWith Y) useful, but will
require changing the runtime to do efficiently if the (Y) action does not allow
the (atomic X) to succeed/commit on the next attempt. Imaging that getLine does
not block and returns no input, so (Y) does not feed (X). Then the next attempt
to do (X) will (retryWith Y) and (Y) still fails to get input, so you have a
"busy wait" where (Y) and (X) alternately execute. It will require a runtime
change to prevent (X) from being retried until more input appears.
In pseudocode this would be:
X = if tchan is empty then retryWith Y else do work and commit
Y = if input is available then feed tchan else return ()
>
> There are some interesting questions to think about the semantics of
"retryWith". The semantics of "retry" in the PPoPP paper say nothing about
putting threads to sleep -- it would be correct for an implementation to spin
repeatedly executing an "atomic" block until it completes without calling
"retry".
It would indeed be semantically correct, but if you have many spinning threads
then the program will grind to a halt and few people would be able to employ
STM. So the spec need not mention the blocking, but it should be possible to
implement it that way. And GHC does. And onCommit can be implemented without
changing from blocking to spinning, while retryWith does change from blocking to
spinning (without a runtime change)
> What should happen with "retryWith" -- should we introduce blocking &
wake-up into the semantics, or say that the "retryWith" actions are collected
together, executed in place of the transaction (if it does ultimately retry) and
then the transaction re-attempted?
Since (retryWith y1) `orElse` (retryWith y2) must execute y1 and y2, I used
onRetry to collect such actions: "retryWith io = onRetry io >> retry". After
running all the onRetry actions it immediately re-attempts the whole atomic
transation without regard for whether any STM variables have been updated, so
this causes spinning.
[ Aside: I probably will modify it so that a lack of onRetry actions will
prevent spinning. ]
> For simplicity (and to leave flexibility to
the implementation) I'd prefer to keep blocking & wake-up out of the semantics.
> Taking that option, suppose we have "atomic { X }" and X retries with IO
action Y. I think I'm saying that that would be equivalent to "Y ; atomic { X
}". What are the consequences of this?
Bad consequences. In particular, Y must finish before X is re-attempted. My
implementation does this at the moment, which is bad, but the right solution
requires a runtime change.
> In the GetLine example it means that an
implementation that does put threads to sleep must detect conflicts between the
first execution of X and any transactions performed in Y.
There may also be a distinction for whether
[Existing/retry] If atomic { X } fails with a normal retry then rollback and put
X to sleep until an appropriate STM update
[Existing/fail] If atomic { X } fails with from a conflicting update then
rollback and immediately re-attempt X
[New case/retry] If atomic { X } fails with (retryWith Y) then rollback and put
X to sleep until an appropriate STM update and then schedule (Y) (e.g. with
forkIO).
[New case/fail a] If atomic { X } fails with a conflicting update and has a
pending (onRetry Y) then rollback and schedule both Y and a re-attempt of X.
This last case comes from imagining using orElse:
(code calls retryWith Y) `orElse` (code that causes conflicting update)
in which case running Y seems like the obvious thing to do.
>
> Are there any interesting problems that come up if "Y" performs transactions
that use "retry" or "retryWith"?
>
> Tim
>
In many useful cases, such as the getLine example, the Y action will have its
own atomic {} block. In which case the semantics of when it is allowed to
re-attempt X are what is important. If you require (Y) to complete before
re-attempting (X) then you get an infinite regression where every (atomic block)
fails with (retryWith (next atomic block)), and nothing is ever re-attempted.
This is why "retryWith Y"
RE: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
| In many useful cases, such as the getLine example, the Y action will have its
| own atomic {} block. In which case the semantics of when it is allowed to
| re-attempt X are what is important. If you require (Y) to complete before
| re-attempting (X) then you get an infinite regression where every (atomic
block)
| fails with (retryWith (next atomic block)), and nothing is ever re-attempted.
| This is why "retryWith Y" meaning rollback X and do "Y >> atomic X" is the
wrong
| implementation.
I don't agree. I think it's quite reasonable. Not many atomic blocks will
finish with retryWith. Of course there is a possibility of an infinite loop,
but we already have that: f x = f x. Of course, Y can always choose to do a
forkIO, but it shouldn't hav to.
For me the only difficulty is the implementation. We'd like to block X on the
TVars it read (as usual), *unless* executing Y wrote to any of them. That
requires a bit more cleverness in the commit code, but not a great deal I think.
Simon
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Re: [Haskell-cafe] SimonPJ and Tim Harris explain STM - video
Eureka,
I claim to have written an implementation which agrees with all the semantics
that Simon Peyton-Jones wants for onCommit/onRetry/retryWith. See below:
Simon Peyton-Jones wrote:
> | In many useful cases, such as the getLine example, the Y action will have
> its
> | own atomic {} block. In which case the semantics of when it is allowed to
> | re-attempt X are what is important. If you require (Y) to complete before
> | re-attempting (X) then you get an infinite regression where every (atomic
> block)
> | fails with (retryWith (next atomic block)), and nothing is ever
> re-attempted.
> | This is why "retryWith Y" meaning rollback X and do "Y >> atomic X" is the
> wrong
> | implementation.
>
> I don't agree. I think it's quite reasonable. Not many atomic blocks will
> finish with retryWith. Of course there is a possibility of an infinite loop,
> but
> we already have that: f x = f x. Of course, Y can always choose to do a
> forkIO,
> but it shouldn't hav to.
>
> For me the only difficulty is the implementation. We'd like to block X on the
> TVars it read (as usual), *unless* executing Y wrote to any of them. That
> requires a bit more cleverness in the commit code, but not a great deal I
> think.
>
> Simon
It is the Helper Thread code version on the wiki at
http://haskell.org/haskellwiki/New_monads/MonadAdvSTM#Helper_Thread_Code
Quick explanation of the code for runAdvSTM (usually called with atomicAdv):
When the action X in (atomicAdv X) ends with (retryWith Y) the job Y is put into
an MVar. Then a retry causes the orElse in wrappedAction to perform
check'retry. This sees the job Y and then
*) if this is the first retry job: creates and cache a channel and spawn the
helper thread
*) push the retry job Y into the channel
*) call retry to cause action X to cause the current GHC runtime to block on
whatever STM-variables it used
The wrappedAction commits if and only if the action X commits. In which case
the commit action stored in the TVar is read and performed. Then a check is
performed to see if the helper thread was spawned, and if so tell the helper
thread to quit and block until the helper thread is done.
Note that the action X can be re-attempted by the runtime before the retry job Y
is run or before it has finished running. But this will only happen in the
usual cases where there was an STM update, instead of the possible busy wait in
the Single Thread code example on the wiki page.
Does this meet your specifications, Simon?
--
Chris
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
