- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Relaxing atomicity of STM transactions
by Arie Middelkoop 29 Sep '10

29 Sep '10

Hi Tom, You wrote that you are interested in the programming experience with relaxed atomicity. What you are asking for are the ideas behind Twilight STM, written in these papers: > http://proglang.informatik.uni-freiburg.de/projects/syncstm/techreport2010t… (brief summary of the underlying ideas + rationale. Newer version available upon request) > http://www.cs.uu.nl/research/techreps/repo/CS-2010/2010-020.pdf (about a nicer API for Twilight using Haskell + formalization. Search in the document for "twilight") For experimental purposes, we have implementations in C, Java and Haskell. Annette already replied to this thread with a link to our Haskell implementation. The main idea is to change (only) the commit protocol of a transaction. The transaction (speculatively/lockless) executes as always: depending on its semantics, it may restart when it reads a value that has been modified since the start of a transaction, or if you use a multi-versioning STM, perhaps read data from older memory snapshots. What semantics you choose here is of no real concern as long as the transaction reaches its commit-point while having read data from a consistent memory snapshot. At the commit-point, however, we do something special: the programmer can provide code to manually validate the transaction using a special API. At the commit point, we first put the transaction in an irrevocable state. This ensures that at any point the programmer's validation code gives an OK, we can publish the outcome of the transaction. We then validate the transaction (without restarting) to discover inconsistencies. Finally, the validation code is executed to inspect these inconsistencies. To easily inspect these inconsistencies, you can tag all reads in the transactional body with region identifiers. In the validation code, you can then query if this region has become inconsistent, and what the new values are. These new values are again taken from a consistent memory snapshot - important! In the example that you provided, this would mean that the reference that you want to loosely read from, you tag with a special region. In the validation code, you can then easily ignore its inconsistency. Or, more likely: inspect the new value to see if the difference with the actual read value is not too big. Additionally, in the validation code, since the transaction is irrevocable, it is possible to safely do I/O, and you can change the outcome of the transaction slightly based on the new values inspected, i.e. repair the inconsistencies. These ideas provide a more fundamental way to deal with relaxed atomicity, whereas just reading "loosely" from a variable is not. In the latter case, you have no clue how out-dated the values are that you read, for example. Hope this is useful to you, Arie > Thanks for the responses, but I think I should explain a bit more. > I'm not interested in being able to read the live value of a TVar at > any arbitrary time (via. unsafeIOToSTM). But rather I would like > looslyReadTVar to have exactly the same semantics as readTVar, except > that the STM runtime would not reject the transaction if the TVar is > modified by another transaction before the atomic commit takes place. > > Also, as I would be implementing something similar in Atom, I'm not > necessarily interested in a Haskell implementation, but rather if the > programming experience is elevated by these alternative semantics. > > For example: > > incr :: TVar -> STM () > incr a = looslyReadTVar a >>= writeTVar a . (+ 1) > > decr a :: TVar -> STM () > decr a = readTVar a >>= writeTVar a . (- 1) > > If incr and decr where atomically started at the same time with the > same TVar, decr would be rejected if incr completed first, but not the > other way around. The initial reaction may be that this seriously > breaks the atomicity of STM, but there may be cases where this could > be useful. For instance, it allow a computationally expensive > transactions to complete, even if their inputs are constantly being > modified. In the embedded domain, this could be a fault monitor that > reads a bunch of constantly changing sensors.

1 0

Relaxing atomicity of STM transactions
by Tom Hawkins 29 Sep '10

29 Sep '10

Has anyone in the STM community considered the ability to read a TVar, such that it would allow the transaction to complete even if the TVar was modified by another transaction? (I am assuming this is not how STM works by default.) For example: looselyReadTVar :: TVar a -> STM a Atom [1] has similar semantics to STM. If Atom were to relax it's rule atomicity in this fashion, it could open the door to improved task scheduling and higher levels of program description. Has STM research already gone down this path? -Tom [1] http://hackage.haskell.org/package/atom

7 10

A model theory question
by Patrick Browne 29 Sep '10

29 Sep '10

Hi, Below is an assumption (which could be wrong) and two questions. ASSUMPTION 1 Only smaller models can be specified using the sub-class mechanism. For example if we directly make a subclass A => B then every instance of B must also be an instance of A (B implies A or B is a subset of A). Hence, type classes cannot be combined using sub-classing to provide specifications of bigger models. QUESTIONS 1) If assumption 1 is correct, is there a mechanism whereby the module system can be used to construct bigger models? 2) If there is such a mechanism does it involve type classes or is it a module only solution? Regards, Pat This message has been scanned for content and viruses by the DIT Information Services E-Mail Scanning Service, and is believed to be clean. http://www.dit.ie

2 5

Re: [Haskell-cafe] Relaxing atomicity of STM transactions
by Brandon Moore 29 Sep '10

29 Sep '10

On Sep 28, 2010, at 6:36 PM, Tom Hawkins <tomahawkins(a)gmail.com> wrote: Thanks for the responses, but I think I should explain a bit more. I'm not interested in being able to read the live value of a TVar at any arbitrary time (via. unsafeIOToSTM). But rather I would like looslyReadTVar to have exactly the same semantics as readTVar, except that the STM runtime would not reject the transaction if the TVar is modified by another transaction before the atomic commit takes place. Given the current implementation, I think the easiest way to get those semantics is to lift the untracked readTVarIO into STM with unsafeIOToSTM.

2 1

Non-strict evaluation and concurrency (STM) : conflict?
by Romain Demeyer 28 Sep '10

28 Sep '10

Hi, I'm working on Concurrent Haskell, especially with the monad STM. I don't fully understand the way my program is executed. I think the lazy evaluation leads to a loss of performance, if we don't pay attention to this problem. A short example will be more explicit : Imagine this scenario : we have a set of threads (the workers) that have (each) a result to compute (purely). When finished, they try to save the result in an shared inbox, using STM. If the inbox is full, the thread waits until the inbox is empty. A specific thread is looking at the inbox: when it finds a value in the inbox, it prints the value on the screen (for example, it could be any processing based on the value) and then empty the inbox and wait that a remaining thread add a new value). Let's a function "do_job", the function to execute by the threads (the workers) : do_job :: (b -> a) -> b -> Inbox a -> IO () do_job f input inbox = do { value <- return (f input) ; atomically ( writeMsg inbox value ) } The idea is : (f input) is the function to compute. Once compute, we want to save the result atomically. The problem is, because of the lazy evaluation, the "value" is computed in the atomic section, and not before, resulting in a loss of efficiency. Indeed, to be fast, a concurrent program has to keep the atomic sections as "small" as possible, because it limits the parallelism. To illustrate this, let's see this source code : module Main where import Control.Concurrent import Control.Concurrent.STM import Data.Maybe import System.Random import System.IO {-- Inbox --} type Inbox a = TVar (Maybe a) createInbox :: STM (Inbox a) createInbox = newTVar Nothing readMsg :: Inbox a -> STM a readMsg inbox = do { inboxContent <- readTVar inbox ; if (isNothing inboxContent) then retry else do { writeTVar inbox Nothing ; return (fromJust inboxContent) } } writeMsg :: Inbox a -> a -> STM () writeMsg inbox value = do { inboxContent <- readTVar inbox ; if (isNothing inboxContent) then writeTVar inbox (Just value) else retry } {-- Workers --} * do_job :: (b -> a) -> b -> Inbox a -> IO ()* *do_job f input inbox = do { value <- return (f input) * * ; atomically ( writeMsg inbox value ) }* do_jobs_in_threads :: [((b->a),b)] -> Inbox a -> TVar Int -> IO () do_jobs_in_threads [] _ _ = return () do_jobs_in_threads ((f,input):xs) inbox flag = do { forkIO_and_notify flag (do_job f input inbox) ; do_jobs_in_threads xs inbox flag } {-- Caller --} * * *caller :: Inbox a -> (a -> IO ()) -> Int -> IO ()* *caller _ _ 0 = return ()* *caller inbox process n = do { msg <- atomically (readMsg inbox)* * ; process msg * * ; caller inbox process (n-1) }* caller_in_thread flag inbox process n = forkIO_and_notify flag (caller inbox process n) {-- forkIO with notification --} create_flag = atomically ( newTVar 0 ) forkIO_and_notify :: TVar Int -> IO () -> IO () forkIO_and_notify tvar action = do { atomically ( do { oldValue <- readTVar tvar ; writeTVar tvar (oldValue + 1) } ) ; forkIO (do { action ; atomically ( do { oldValue <- readTVar tvar ; writeTVar tvar (oldValue - 1) } ) } ) --; putStrLn "Tread lancé" } ; return () } waitFlag flag = atomically ( do { valueflag <- readTVar flag ; if valueflag > 0 then retry else return () } ) {-- main --} main :: IO () main = do { flag <- create_flag ; inbox <- atomically (createInbox) ; *caller_in_thread flag inbox (\x -> putStrLn ("Caller : "++ (show (x)))) 3* * ; do_jobs_in_threads [(perm,[1..11]),(perm,[1..8]),(perm,[1..3])] inbox flag* ; waitFlag flag ; return () } where perm (l:ls) = injectett l (perm ls) injectett x (l:ls) = injecte x l ++ injectett x ls injecte x (l:ls) = [x:l:ls]++map (l:) (injecte x ls) inputs = zip (replicate 3 f) [[1..11],[1..8],[1..3]] As you can see, we ask for 3 threads to compute permutations for [1..11], [1..8] and [1..3]. The "Caller" write a message when a thread finished. What we expect is that the second and third thread finish their work before the first one. But the output of this program is : *Caller : 39916800* *Caller : 40320* *Caller : 6* ... which means that threads 2 and 3 have to wait the first thread before being able to save (and probably compute) their own result. If I force to evaluate "value" before the atomic section, by defining : do_job :: (b -> a) -> b -> Inbox a -> IO () do_job f input inbox = do { value <- return (f input) ; value `seq` atomically ( writeMsg inbox value ) } Then I obtain a more efficient program, as the output confirms : *Caller : 6* *Caller : 40320* *Caller : 39916800* That's what we want, but what is the explanation of this behavior? STM is designed to be optimistic, not blocking. So, does it means that the "value" is evaluated at "commit-time"? Do you know some problems that are related or do you know some works that can be useful at this subject? Thanks for your help, rde

4 5

HackageDB: Haddock parse failure
by Jonas Almström Duregård 28 Sep '10

28 Sep '10

HackageDB reports a build failure for happy-meta-0.1.1 (http://hackage.haskell.org/package/happy-meta-0.1.1) but from the log it seems that the failure occurs when building the documentation. The error is src/LALR.lhs:230:2: parse error on input `numberSets' I'm guessing there is no syntax error in this file (it is taken from Happy), but rather an error in Haddock? Also, perhaps HackageDB should ignore errors in building the documentation? Currently the reported build failure propagates to the dependencies of the library... /J

3 2

Question on monad transformers stack
by Arnaud Bailly 28 Sep '10

28 Sep '10

Hello Cafe, I have the following type which represents some action using Git > newtype (Monad m) => Git m a = Git { runGit :: ErrorT String (StateT Environment m) a } > deriving (Monad, MonadState Environment, MonadError String) and the following typeclass whose purpose is to abstract away the details of executing commands in the OS, with an obvious IO instance, and to ease testing of commands effects: > -- | A monad for simple execution of a process within the > class (MonadError e m) => MonadExec e m where > debug :: String -> m () > exec :: String -> [String] -> m String > -- ^Do not really execute commande but output the command string and arguments passed > exec' :: String -> [String] -> m String > exec' proc args = return $ program proc args The type environment is : > data Environment = Env { debugMode :: Bool, > baseDirectory :: FilePath, > maven :: FilePath, > git :: FilePath, > p4 :: FilePath, > javaHome :: FilePath} > deriving (Eq, Show, Read) This follows the monad stack pattern presented in RWH and in Don Stewart's presentation on scripting with haskell. Actually, what I am trying to achieve is to be able to write my own scripts in Haskell. What I would like to do is to be able to wrap each Git action occuring in a MonadExec instance into a call to debug according to the status of the debugMode flag in environment, in order to prevent the need of explicit calls to debug. Something like the -v flag in bash... I can imagine being able to do this using 2 different ways: - add a constraint on Git monad and write explicitly return and >>= to use debug - push the environment or part of it inside the MonadExec, for example as a Reader. What is the "best" (i.e. most economical) way of doing this? Thanks for your advices. Arnaud Bailly

2 2

Can't make a derived instance of `Typeable (A B)': `A' has arguments of kind other than `*'
by Christopher Done 28 Sep '10

28 Sep '10

Suppose I have a data type: data A f = A { a :: f Integer } why can't I derive a Typeable instance like so? deriving instance Typeable (A Maybe) I get: Can't make a derived instance of `Typeable (A Maybe)': `A' has arguments of kind other than `*' In the stand-alone deriving instance for `Typeable (A Maybe)' I would have expected that the arguments are instantiated by the Maybe type constructor and thus the type of A would be: Maybe Integer -> A What am I missing?

3 5

Why can't libraries/frameworks like wxHaskell/gtk2hs/... be used with newer versions of ghc/wxWidgets/GTK+/... ?
by caseyh＠istar.ca 27 Sep '10

27 Sep '10

Why can't libraries/frameworks like wxHaskell/gtk2hs/... be used with newer versions of ghc/wxWidgets/GTK+/... ?

3 2

parsec manyTill documentation question
by Peter Schmitz 27 Sep '10

27 Sep '10

I am new to parsec and having difficulty understanding the explanation of manyTill in http://legacy.cs.uu.nl/daan/download/parsec/parsec.html. (I really appreciate having this doc by the way; great reference.) I.e.: > manyTill :: GenParser tok st a -> GenParser tok st end -> GenParser tok st [a] > > (manyTill p end) applies parser p zero or more times until parser > end succeeds. Returns the list of values returned by p . This parser > can be used to scan comments: > > simpleComment = do{ string "")) > } > > Note the overlapping parsers anyChar and string "", ... since anyChar begins reading input beginning with the char *after* string ""). Second, manyTill, by definition, keeps applying p (anyChar) until end (string "-->") is satisfied, so I would expect one could just write: manyTill anyChar (string "-->") Assuming the documentation is correct on both counts, I would really appreciate any explanation someone could offer. Thanks very much, (really like Haskell & parsec) -- Peter (If anyone knows of a collection of parsec demos or good examples, I would appreciate a link; thanks)

3 3