December 2006 - Haskell-Cafe

interval arithmetic for integers?
by Nicolas Frisby 08 Dec '06

08 Dec '06

I'm looking to not reinvent the wheel. Is there an existing package that supports interval arithmetic on integers (or more)? A possible complication is that I'm hoping to include open intervals such as (GreaterEqThan 3). If there's not a package to go with, any pointers on the appopriate rules for this stuff? I started coding up multiplication and decided it was harder than I first thought... Thanks for your time, Nick

3 5

throwTo & block statements considered harmful
by Chris Kuklewicz 08 Dec '06

08 Dec '06

Title: "throwTo & block statements considered harmful" This is a short essay to prove that the current GHC concurrency implementation has a critical flaw. And this is on the wiki at: http://haskell.org/haskellwiki/GHC/Concurrency#throwTo_.26_block_statements… The key problem is, at least in the presence of block/unblock, that Exceptions are never reliably delivered. And this is not a theoretical case, but can cause a hang in something as innocuous as "program A" given below. Simon Marlow wrote: >> I think people are misunderstanding the nature of a safepoint. The >> safepoint is a point at which you are prepared to have exceptions >> delivered. This does not mean that they *will* be delivered, just that they >> can. If you need to *wait* for an asynchronous exception, then you >> shouldn't be using them at all. > > Right. If a thread mostly runs inside 'block' with the occasional safe > point, then your exceptions are not really asynchronous, they're synchronous. > > > In this case, I'd say a better solution is to have an explicit event queue, > and instead of the safe point take an event from the queue. The action on > receiving an event can be to raise an exception, if necessary. > > Cheers, Simon The implementation of asynchronous signals, as described by the paper "Asynchronous exceptions in Haskell Simon Marlow, Simon Peyton Jones, Andy Moran and John Reppy, PLDI'01." is fatally inconsistent with the implementation in GHC 6.4 and GHC 6.6 today. The implemented semantics have strictly weaker guarantees and render programs using asynchronous expressions impossible to write correctly. The semantics in the paper were carefully designed to solve the problem laid out in the first sentence of the abstract: "Asynchronous exceptions, such as timeouts, are important for robust, modular programs, but are extremely difficult to program with -- so much so that most programming languages either heavily restrict them or ban them altogether." And I believe the paper succeeded. The paper shows how to replace other languages pervasive and intrusive error catching and handling code with much cleaner, clearer, and often more correct code. The implementation in GHC has changed the behavior of throwTo from asynchronous (not-interruptible) to synchronous (interruptible?) as discussed in section 8 of the paper. This change, in and of itself, is not the fatal problem; as described in the paper a (forkIO (throwTo ...)) recovers the asynchronous behavior. The fatal change between the paper and GHC comes from not following section 7.2 as published. Section "7.2 Implementation of throwTo" has two bullet point, and the second bullet point is (retyped, so typos are my own fault): "As soon as a thread exits the scope of a 'block', and at regular intervals during execution inside 'unblock', it should check its queue of pending exceptions. If the queue is non-empty, the first exception from the queue should be raised." A test of GHC 6.6 shows that this is not the case. Test program A: > loop = block (print "alive") >> loop main = do tid <- forkIO loop threadDelay > 1 killThread tid Program A, compiled with (-threaded) on a single CPU machine never halts. It will print "alive" forever while the the main thread is blocked on "killThread". This is wh As an aside, removing the threadDelay causes killThread to destroy the child before it can enter the block, thus showing the need to add "forkBlockedIO" or "forkInheritIO" to the library. This can be worked around using an MVar. Changing the definition of loop produces Test program B: > loop = block (print "alive") >> yield >> loop main = do tid <- forkIO loop > threadDelay 1 killThread tid This prints "alive" twice before the killThread succeeds. The paper demands that when the loop in Program A exits the scope of "block (print a)" that it check a queue of pending exceptions, see that it is non-empty, and raise the exception thrown by killThread. This can also be seen in "Figure 5. Transition Rules for Asynchronous Exceptions", where killThread should use throwTo to create an in-flight exception and exiting the scope of block in the presence of this in-flight exception should raise the exception. The implementation in GHC sleeps the main thread at the killThread command, and it is awoken when the block is exited and to succeed in delivering the exception it must execute while the child is still in the unblocked state. But the child re-enters a blocked state too quickly in Program A, so killThread never succeeds. The change in Program B has the child "yield" when unblocked and this gives the main thread a change to succeed. This trick using yield to make a safepopint was suggested by Simon Marlow: > The window in 'unblock (return ())' is tiny, I'm not really surprised if > nothing ever gets through it. You might have more luck with 'unblock yield'. It has been said on this mailing list thread that needing "yield" to program concurrently is a bug in the user's code and should be replaced by other mechanisms. In a complex program with many threads even the yield trick may not be enough to program reliably. Using blockY io = do x <- block io yield return x unblockY io = unblock (yield >> io) instead of 'block' and 'unblock' is at least a simple but unreliable workaround. This would not be a fatal flaw if there were a simple reliable workaround. The best workaround is the following, which is anything but simple, and amount to re-implementing the mechanisms in the paper: * When forking a thread: ** Create an (Chan Exception) (or (TChan Exception)) and pass it to the child thread. Call this the queue. ** Create a ((T)MVar queue) to indicate whether the thread is still alive or not and wrap the whole child action in a 'finally' to ensure this is set to the dead state when the child exits. (Alive iff the queue is in the MVar) ** To be sure the child thread is in the handler, use another MVar or re-use the "alive/dead" MVar to ensure the child is running before returning the ThreadId from the fork operation. * Replace all uses throwTo/killThread by ** Test the alive/dead state of the thread, proceeding only on living threads ** Putting the Exception in the queue ** Call throwTo/killThread with the Exception * The child thread must: ** implement safepoints by checking the queue ** At each 'block' to 'unblock' transition the child ought to add a safepoint This machinery closely recovers the queue of exceptions and the semantics described in the paper. When a thread has died the queue is removed from the alive/dead MVar and can be garbage collected, along with any pending exceptions for the dead thread. To ensure the above semantics are not violated by the caller, the now fork operation should not return an exposed ThreadId, but should return some proxy type or operation to ensure only the proper throwto/killThread are peformed. Next I will demonstrate how the paper's achievement of simple and clear error handling code is lost. The child thread is where the workaround becomes a nightmare. It is impossible to test the current 'block' versus 'unblock' state. So the only time the child is certain that a 'block' to 'unblock' transition has occurred is when it is explicit: > unblock ( .... block ( ... ) <*> .... ) The <*> is obviously such a transition and ought to have a safepoint added. But is only because the block had the explicit unblock around it. If there were a function such as > atomicUpdateFoo = block (...) <?> then there is no way to know if the <?> should be a safepoint. Therefore atomicUpdateFoo needs documentation so that the caller knows to add a safepoint in the case it is called from the unblocked case. In a more complex example: > atomicUpdateFooBar = block (...) <1?> block (...) <2?> the caller cannot add <1?> itself, and must therefore pass in code 'safe :: IO ()' to all such functions: > atomicUpdateFooBar safe = block (...) >> trans >> block (...) >> trans where 'trans' is "return ()" or "checkChan queue" depending on whether the the caller knows it is in a 'block' or 'unblock' state. If the parent never needed to use 'throwTo'/'killThread' then the child never needs 'block'/'unblock' and the nightmare is avoided. But if the child uses any operation which can block such as 'accept' or 'getChar' or 'takeMVar' then the parent cannot deliver the signal without waking up the child with a 'throwTo' which quickly leads to either an overwhelming use of 'catch' in the child (like other languages) or use of 'block' and the fragile workaround I just described. As an aside, if there was a "isBlockedThreadState" operation, then it would be possible to create a better client workaround: checkChan queue x = do isBlocked <- isBlockedThreadState -- perhaps needing =<< myThreadId case isBlocked of True -> return x False -> raiseQueue queue x raiseQueue queue x = do hasException <- isEmptyChan queue case hasException of False -> return x True -> readChan >>= raise checkedBlock queue io = do x <- block io checkChan queue x checkedUnblock queue io = checkChan queue >> io If that existed then the client should use checkedBlock and checkedUnblock instead of block and unblock. The net effect of this workaround is to implement the queue described in the original paper and wrap the forkIO/throwTo/block/unblock operations with new ones that implement the semantics described in the section 7.2 of the paper. We can try to implement isBlockedThread state by maintaining a stack of block/unblock operations: checkedBlock stack queue io = do x <- bracket_ (modifyIORef stack (True:)) (modifyIORef stack tail) (io) checkChan queue x checkedUnblock stack queue io = do checkChan queue () x <- bracket_ (modifyIORef stack (False:)) (modifyIORef stack tail) (io) isBlockedThread stack = liftM head (readIORef stack) Where "stack :: IORef [Bool]" is created and passed to the child by the modified fork operation. The 'stack' above grows without bound during recursion and is not tail recursive, so the stack management should be changed to the algorithm in the paper... in which case one really has recreated the paper's implementation inside Haskell. The only alternatives are to * write code that may hang forever at a throwTo/killThread * never use throwTo or killThread making block/unblock irrelevant * never use 'block' (and 'unblock') * only write children with explicit "(unblock ... block (... block () ...) >>= raiseQueue queue >>= ...." where the different between checked and unchecked block is obvious and explicit. * Track and propagate the blocked state as in atomicUpdateFooBar. This problem with throwTo/block was not obvious until I stated writing small programs to test the implementation in GHC and thus discovered that the paper's description had mislead me. The key problem is, at least in the presence of block/unblock, that Exceptions are never reliably delivered. And this is not a theoretical case, but can cause a hang in something as innocuous as "program A" given above. -- Chris Kuklewicz

1 1

modelling problem
by Kurt Schelfthout 08 Dec '06

08 Dec '06

Hi Haskell'ers, I'm trying, more as a first excercise in Haskell than anything else, to code a simulation framework in Haskell. A simulation is a bunch of simulation state consisting of constituents (e.g. physical entities like a ball or properties like temperature), on which agents (e.g. simulated humans) in the system can do activities. Activities have a certain duration, and define how the simulation progresses. The simulator framework should just define the basics to maintain a normal representation of time and of cause and effect, i.e. make sure that the state evolves through the application of the activities in the right order. In a later step I will add "laws", which transform activities when they overlap or conflict (e.g. two drive activities leading to collision). I've run into the following problem. I defined a class that allows to define activities on constituents: class Activity a c where start :: c -> a -> Time --start of the activity (this isn't actually dependent on c, I guess) end :: c -> a -> Time --end of the activity delta :: a -> Time -> c -> c --how the constituent is changed at the given time Two parameter type class because some activities are only applicable to certain constituents: instance Activity Paint Ball where instance Activity Move Ball where instance Activity Paint Wall where but you can't move a wall for example, so no instance for Move Wall. My question is: How can I now represent the state of the simulation (i.e. all activites on all constituents). E.g. a list of activities won't do since the list is heterogeneous (i.e. [Paint Ball White, Move Ball (2,0)]) I know about existentials, but I'm at a loss at how to implement the "wrapper" datatype that is exemplified on http://www.haskell.org/hawiki/ExistentialTypes since my class has two parameters, in fact I'm at a loss at how to use existentials here completely. Then, how could I go back from the "general" lists (or whatever datatype) of [a]'s and [c]'s, to a list of [([a],c)] of all activities a that are applicable to a certain constituent c? I can't seem to be able to use the Typeable class for example, since this can not "cast" to typeclasses, only to concrete types (I think...). What I initially liked about this idea is that it can be encoded in the typesystem which activities apply to which consituents, but now it seems like I will have to encode it in the simulation framework more directly (i.e. giving each consituent a String name to encode its "type"). More straightforward ways of modelling this problem (avoiding multiple type class parameters and existentials :) )are also welcome. thanks for any pointers, Kurt

4 3

known, I know: class contexts and mutual recursion
by Conor McBride 08 Dec '06

08 Dec '06

Hi folks I just tripped over the "Contexts differ in length" error message. I know it's not a new problem, but I thought I'd enquire as to its status. For those of you who haven't seen it, here's an example, contrived but compact. > data Thing > = Val Int > | Grok Thing (Maybe Int -> Int) > eval :: Monad m => Thing -> m Int > eval (Val i) = return i > eval (Grok t f) = return (f (eval t)) My eval function compiles ok. See? The recursive call to eval targets the Maybe monad, so I get *Mmm> eval (Grok (Val 5) (maybe 0 (1 +))) :: Maybe Int Just 6 However, when I try to decompose eval as a pair of mutually recursive functions, namely > foo :: Monad m => Thing -> m Int > foo (Val i) = return i > foo (Grok t f) = return (goo t f) > goo :: Thing -> (Maybe Int -> Int) -> Int > goo t f = f (foo t) I get Mmm.lhs:15:1: Contexts differ in length When matching the contexts of the signatures for foo :: forall (m :: * -> *). (Monad m) => Thing -> m Int goo :: Thing -> (Maybe Int -> Int) -> Int The signature contexts in a mutually recursive group should all be identical Poking about on the web, I got the impression that this was a known infelicity in ghc 6.4 (which I'm using), due to be ironed out. However, an early-adopting colleague with 6.6 alleges that foo-goo is still poisonous. I'm wondering what the story is. I mean, is there some nasty problem lurking here which prevents the lifting of this peculiar restriction? I'm not in a panic about this. I have a workaround for the problem as I encountered it in practice. Mind you, it's the sort of thing that's likely to happen more often, the more you localise the effects you tend to use. In the above, goo doesn't throw exceptions; rather, because goo has a handler, it can offer a /local/ exception-throwing capability to foo. Curious Conor

5 5

Re: [Haskell] ANNOUNCE: Visual Haskell 0.2 final
by Bulat Ziganshin 08 Dec '06

08 Dec '06

Hello Krasimir, Friday, December 8, 2006, 11:12:26 AM, you wrote: > The final version of Visual Haskell 0.2 is ready: > - distributed with a stable GHC version (6.6) how about bundlng it with up-to-date GHC 6.6 build (which've fixes a lot of problems) or, better, allow to use it with user-installed ghc 6.6.* installation? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 4

MissingH status and thanks
by John Goerzen 08 Dec '06

08 Dec '06

Since the MissingH discussion took place on this list, I thought I should update you all on the status. First off, MissingH now has a new Trac-based homepage, complete with wiki, Darcs repository information, source browser, bug tracker, etc. It's at http://software.complete.org/missingh Secondly, the MissingH modules have been renamed as we discussed here. And finally, various pieces of MissingH have been split off already into separate packages. (See the announcements on haskell(a)h.o) The full list of changes -- planned and executed -- is at http://software.complete.org/missingh/wiki/TransitionPlanning Thanks to all for your valuable feedback. I hope that these changes will make this set of code more useful to everyone. -- John

1 0

"computational time" always 0.0 in this example...
by Lennart 08 Dec '06

08 Dec '06

Hi, with the following code, I want to measure the time being needed to execute the algorithm. But the result is always 0.0. import Char (toLower) import Maybe import List ( delete, sort, intersect ) import System.CPUTime import Control.Exception import Debug.Trace fromInt = fromIntegral wordList2 :: [String] wordList2 = ["Sam J Chapman", "Samuel Chapman", "S Chapman", "Samuel John Chapman", "John Smith", "Richard Smith", "aaaa mnop zzzz", "bbbb mnop yyyy", "aa mnop zzzzzz", "a ", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaa bcdefgh mmmmmmmm stuvwx zzzzzz", "jjjj bcdefgh qqqqqqqq stuvx yyyyyy", "aaaaa bcdefgh stuvwx zzzzzz", "aaaaa aaaaa aaaaa zzzzzz", "aaaaa aaaaa"] time :: IO t -> IO t time a = do start <- getCPUTime v <- a end <- getCPUTime let diff = (fromIntegral (end - start)) / (10^12) -- let diff = (fromIntegral (end - start)) putStrLn "Computation time:" print (diff :: Double) return v main = do putStrLn "Starting..." time $ doTest wordList2 wordList2 `seq` return () putStrLn "Done." test3 = let loop = getCPUTime >>= print >> loop in loop doTest :: [String] -> [String] -> [ Double ] doTest [] _ = [] doTest (x:xs) [] = doTest xs xs doTest (x:xs) (y:ys) = result : (doTest (x:xs) (ys)) where result = qGramMetrics2 x y qGramMetrics2:: String -> String -> Double qGramMetrics2 t1 t2 = let i = intersect (qGramList (map toLower t1) 3) (qGramList (map toLower t2) 3) il = fromInt (length i) ml = fromInt ((max (length t1) (length t2)) - 1 ) in (il / ml ) -- list of chars within list of qgrams qGramList :: String -> Int -> [[Char]] qGramList [] _ = [] qGramList (x:[]) _ = [] qGramList (x:xs) i1 = (x: take (i1 - 1) xs):(qGramList xs i1) -- list of chars within list of qgrams numberedQgramListWithStart :: String -> Int -> [(Int, [Char])] numberedQgramListWithStart x i1 = let prefix = replicate (i1-1) '#' suffix = replicate (i1-1) '$' in numberedQgramList (prefix++(x++suffix)) i1 0 numberedQgramList :: String -> Int -> Int -> [(Int, [Char])] numberedQgramList [] _ _ = [] numberedQgramList (x:xs) i1 i2 -- add the dollar-sign | (length xs) < i1 && x=='$'= [] | otherwise = (i2,(x: take (i1 - 1) xs)):(numberedQgramList xs i1 (i2+1)) Am using ghci 6.6 under a Kubuntu 6.10 Linux. time $ product [1..1000] `seq` return () instead of time $ doTest wordList2 wordList2 `seq` return () works fine. things like time $ print (doTest wordList2 wordList2) `seq` return () or time $ length (doTest wordList2 wordList2) `seq` return () or time $ trace (doTest wordList2 wordList2) `seq` return () didn't work. Am desperated... Lennart

4 5

STUArray's newArray_ breaks referential transparency
by Stefan O'Rear 07 Dec '06

07 Dec '06

newArray_ allocates an array full of garbage. > import Control.Monad.ST > import Data.Array.ST > import Data.Array > > tickle :: Int > tickle = runST (do { > x <- newArray_ (0,100) ; > (readArray :: STUArray s Int Int -> Int -> ST s Int) x 3 > })

1 0

Hac 2007 : Haskell Hackathon - extended registration
by dons＠cse.unsw.edu.au 07 Dec '06

07 Dec '06

------------------------------------------------------------------------ Hac 2007 The 2007 Haskell Hackathon January 10-12, 2007 Oxford University Computing Laboratory http://haskell.org/haskellwiki/Hac_2007 ------------------------------------------------------------------------ The deadline for registration for Hac 2007, the Haskell Hackathon, has passed, and some places are still available, on a first-come first-served basis. The current attendee list is up at: http://haskell.org/haskellwiki/Hac_2007/Attendees If you want to attend the hackathon, and hack on Haskell infrastructure, tools, libraries and compilers, please register, and get ready to hack those lambdas! Follow the instructions on the registration page: http://haskell.org/haskellwiki/Hac_2007/Registration Numbers for the hackathon are limited to 20. The organisers, Duncan Coutts Ian Lynagh Don Stewart Attached is the initial announcement: ------------------------------------------------------------------------ Hac 2007 The 2007 Haskell Hackathon January 10-12, 2007 Oxford University Computing Laboratory http://haskell.org/haskellwiki/Hac_2007 ------------------------------------------------------------------------ Following the success of the GHC Hackathon at ICFP, we are pleased to announce the inaugural Haskell Hackathon, Hac 2007! The event will be held over 3 days, January 10-12 2007, at the Oxford University Computing Laboratory, in the UK. The plan is to hack on Haskell infrastructure, tools, libraries and compilers. To attend please register, and get ready to hack those lambdas! Code to hack on: * Hackage * Cabal * Porting foreign libraries * Porting compilers * Bug squashing * Performance improvements to compilers * You decide! Registration: We ask that you register you interest. Follow the instructions on the registration page: http://haskell.org/haskellwiki/Hac_2007/Registration Numbers for the hackathon are limited to 20, due to room size constraints. Should space be available after the registration period ends, additional attendees may register on a first-come first-served basis. Important dates: Registration deadline: December 6th, 2006 Confirmation: December 10th, 2006 Hackathon: January 10-12, 2007 Organisers: Duncan Coutts Ian Lynagh Don Stewart

1 0

How to get subset of a list?
by Huazhi (Hank) Gong 07 Dec '06

07 Dec '06

Like given a string list s="This is the string I want to test", I want to get the substring. In ruby or other language, it's simple like s[2..10], but how to do it in Haskell? -- View this message in context: http://www.nabble.com/How-to-get-subset-of-a-list--tf2735647.html#a7631994 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

7 8