February 2007 - Haskell-Cafe

Debugging concurrent program - no threads apparently running, but RTS still doing something.
by Alistair Bayley 22 Feb '07

22 Feb '07

Below is a test case for a threading problem I can't figure out. It models a socket server (here I've replaced the socket with an MVar, to keep it simple). The idea is to have a listener which accepts incoming requests on the socket. When one arrives, it forks a handler thread to deal with the request, and returns to listening on the socket. The handler thread is run in parallel with a timeout thread. In the test case below, the handler takes too long, so the timeout thread completes and kills the handler. The problem is that when the main thread ends, the RTS doesn't stop for another 6 or so seconds. The only thread that runs this long is the handler (waitFor (secs 8.0)) but it has already been killed. So I'm scratching my head a bit. Also, any pointers to better techniques for designing and debugging concurrent code are appreciated (is there a better way than putStrLn?) Platform: ghc-6.6, Windows XP. Thanks, Alistair --------------------------------------------------------------------- module Main where import Prelude hiding (catch) import Control.Concurrent import Control.Exception import System.IO secs :: Float -> Int secs n = round (n * 1000000) -- e.g. waitFor (secs 25) waitFor n = debug ("waitFor start " ++ show ((fromIntegral n) / 1000000.0)) >> threadDelay n >> debug ("waitFor end " ++ show ((fromIntegral n) / 1000000.0)) debug msg = myThreadId >>= ( \t -> putStrLn $ (show t) ++ ": " ++ msg ) -- Thread 1 - start server then send message main = do hSetBuffering stdout LineBuffering blockingInput <- newEmptyMVar -- like a socket; accept on a socket blocks listnr <- forkIO (listener blockingInput) putMVar blockingInput "hello" waitFor (secs 2.0) debug "main: done" -- Thread 2 - listener. -- Blocks on input; when input arrives, starts handler thread. listener blockingInput = do msg <- takeMVar blockingInput serveRequest msg -- in a real server we'd loop: --listener blockingInput debug "listener: done" -- Start threads 3 and 4 - handler and timeout. serveRequest msg = do let acquire = return () let release _ = debug "handler release action" forkIO (runTimeout 0.1 acquire release (handler msg)) return () handler msg _ = do debug ("handler start: " ++ msg) catch (waitFor (secs 8.0) >> debug "handler end") (\e -> debug ("Exception: " ++ (show e)) >> throwIO e) runTimeout timeout acquire release action = do handlerTid <- myThreadId -- Use this to ensure the timeout thread doesn't start before the handler -- i.e. give the handler a chance to start. startTimeout <- newEmptyMVar timeoutTid <- forkIO (runTimeoutThread startTimeout timeout handlerTid) bracket acquire ( \a -> release a >> killThread timeoutTid ) ( \a -> do debug "runTimeout: start handler action" putMVar startTimeout True action a debug "runTimeout: end handler action" ) runTimeoutThread startTimeout timeout handlerTid = do takeMVar startTimeout debug "runTimeoutThread: start" waitFor (secs timeout) killThread handlerTid debug "runTimeoutThread: end"

2 2

Re: Leaves of a Tree
by Chad Scherrer 22 Feb '07

22 Feb '07

Neil, I think this idea is better than what I had suggested, but as it stands it doesn't typecheck. Did you mean something like this? leaves :: Tree -> [Int] leaves = f [] where f rest (Leaf n) = n : rest f rest (Branch l r) = f (f rest r) l -Chad ------------------------------- (from Neil Mitchell) Hi Tom > data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) > leaves :: Tree -> Set Int > leaves (Leaf n) = singleton n > leaves (Branch left right) = union (leaves left) (leaves right) The standard method for a traversal over leaves with accumulation is: leaves :: Tree -> Set Int leaves x = f [] where f (Leaf n) rest = n : rest f (Branch l r) rest = f l (f r rest) This makes the construction of the list quite cheap. Then you can do the fromList trick, and that might give you a speed up. Thanks Neil

2 1

Leaves of a Tree
by Tom Hawkins 22 Feb '07

22 Feb '07

Hello, Any recommendations for speeding up extracting the set of leaves from a tree? data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) My slow, naive function: leaves :: Tree -> Set Int leaves (Leaf n) = singleton n leaves (Branch left right) = union (leaves left) (leaves right) In my case, many of the branches in the tree are the same. I suspect the fixed point operation mentioned in the thread "speeding up fibonacci with memoizing" is applicable, but I'm having a tough time making the connection. -Tom

6 5

Selecting overlapping instances
by Emil Axelsson 22 Feb '07

22 Feb '07

Hello! I have a problem with overlapping instances for which I already know a workaround. However, I'm still curious to know if there isn't a simpler solution available. I have a feeling that -fallow-incoherent-instances might be the answer, but I can't get it to work. In the code at the end of the message, (Block w n s e) is a representation of a geometrical block whose west-/north-/south-/eastern edge has type w/n/s/e respectively. (*||*) composes two blocks horizontally and (*=*) composes vertically. In this simplified example, there is only one primitive block -- unitBlock. Now, I want to be able to make grids of unitBlock:s where the edges can have any type that can be obtained using (,) and (). This is what the Grid class attempts. The program compiles fine until I add the test program > test :: Block ((),()) ((),()) ((),()) ((),()) > test = grid which raises an "Overlapping instances" error. What I would like is for the compiler to pick *either* of the two matching instances first, and then the other one, because in this particular case, it doesn't matter which one it picks first. The workaround is to explicitly pick an order by giving the additional instance (requires -fallow-overlapping-instances): > instance ( Grid x1 y1 > , Grid x1 y2 > , Grid x2 y1 > , Grid x2 y2 > ) => Grid (x1,x2) (y1,y2) > where > grid = grid *||* grid Is there any way to make this work without adding this last instance? Thanks! / Emil -------------------------------------------------------- > data Block w n s e = Block > > (*||*) :: Block w1 n1 s1 x -> Block x n2 s2 e2 -> Block w1 (n1,n2) (s1,s2) e2 > (*||*) = undefined > > (*=*) :: Block w1 x s1 e1 -> Block w2 n2 x e2 -> Block (w1,w2) n2 s1 (e1,e2) > (*=*) = undefined > > unitBlock :: Block () () () () > unitBlock = undefined > > class Grid x y > where > grid :: Block x y y x > > instance Grid () () > where > grid = unitBlock > > instance (Grid x1 y, Grid x2 y) => Grid (x1,x2) y > where > grid = grid *=* grid > > instance (Grid x y1, Grid x y2) => Grid x (y1,y2) > where > grid = grid *||* grid

1 0

Re: Leaves of a Tree
by Chad Scherrer 22 Feb '07

22 Feb '07

Hi Tom, Tom Hawkins wrote: > Folding was my first approach: > > leaves :: Tree -> Set Int > leaves tree = accumLeaves Set.empty tree > > accumLeaves :: Set Int -> Tree -> Set Int > accumLeaves set (Leaf n) = insert n set > accumLeaves set (Branch l r) = foldl accumLeaves set [l,r] > > However, with this approach I quickly ran out of stack space. I found > this odd, since I thought this program was tail recursive and > shouldn't be using the stack. This is a problem of tail recursion and lazy evaluation not playing nicely. See this page: http://www.haskell.org/haskellwiki/Stack_overflow > My next attempt was to use some form of memorization. Since many of > the branches in my trees are equal, memorization should prevent > following branches that have already been calculated. My question is, > what is the best way to transform the original function to incorporate > memorization? I think something like this could be done, if there's some invariants maintained by the data structure. Is there any additional structure you're imposing beyond that required for the "data" line? -Chad

1 0

Type-level lambdas in Haskell? ( was Multiparameter class error)
by oleg＠pobox.com 21 Feb '07

21 Feb '07

Alfonso Acosta wrote: > class Synchronous s f1 f2 | s -> f1, s -> f2 where > mapSY :: f1 a b -> s a -> s b > delaySY :: a -> s a -> s a > zipWithSY :: f2 a b c-> s a -> s b -> s c > > The goal of this class is to extend the name of the following > functions (which BTW are already present in a working library and for > that reason _it is a must_ that their types remain untouched) ... > > mapSY :: (a->b) -> Signal a -> Signal b > delaySY :: a -> Signal a -> Signal b -> Signal c > zipWithSY :: (a->b->c) -> Signal a -> Signal b -> Signal c > > .. accepting these definitions as well > > mapSY :: (HDPrimType a, HDPrimType b) => > HDFun (a->b) -> HDSignal a -> HDSignal b > delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a > zipWithSY :: (HDPrimType a, HDPrimType b, HDPrimType c) => HDFun > (a->b->c) -> HDSignal a -> HDSignal b -> HDSignal c First of all, the design already exhibits the problem: delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a cannot be made _at all_ the member of an instantiated Synchronous class. The reason is that in the class definition > class Synchronous s f1 f2 | s -> f1, s -> f2 where > delaySY :: a -> s a -> s a the function delaySY is declared *fully* polymorphic over 'a' -- there are no constraints on a and no restrictions. However, > delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a shows that 'a' is constrained to satisfy the HDPrimType a. That's the problem: the latter function is not generic enough. The problem is described (and solved) in a message `Restricted Datatypes Now' http://www.haskell.org/pipermail/haskell-prime/2006-February/000498.html I'm not certain if there is a compelling reason to place mapSY, delaySY and zipWithSY in the same class. If not, the following is the solution to the problem. Both sets of mapSY, delaySY and zipWithSY are unified in overloaded functions: {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} module SY where class SynchronousM arg1 s a b | s a b -> arg1 where mapSY :: arg1 -> s a -> s b class SynchronousD s a where delaySY :: a -> s a -> s a class SynchronousZ arg1 s a b c | s a b c -> arg1 where zipWithSY :: arg1 -> s a -> s b -> s c -- stubs newtype Signal a = Signal a newtype HDSignal a = HDSignal a newtype HDFun a = HDFun a class HDPrimType a where cnv :: a -> a; cnv = id instance HDPrimType Int instance HDPrimType Bool -- (not so) Grand Unification instance SynchronousM (a->b) Signal a b where mapSY f (Signal x) = Signal (f x) instance (HDPrimType a, HDPrimType b) => SynchronousM (HDFun (a->b)) HDSignal a b where mapSY (HDFun f) (HDSignal x) = HDSignal (cnv . f . cnv $ x) instance SynchronousD Signal a where delaySY _ = id instance HDPrimType a => SynchronousD HDSignal a where delaySY _ (HDSignal x) = HDSignal (cnv x) instance SynchronousZ (a->b->c) Signal a b c where zipWithSY f (Signal x) (Signal y) = Signal (f x y) instance (HDPrimType a, HDPrimType b, HDPrimType c) => SynchronousZ (HDFun (a->b->c)) HDSignal a b c where zipWithSY (HDFun f) (HDSignal x) (HDSignal y) = HDSignal (cnv (f (cnv x) (cnv y)))

2 1

Is anyone using CUDA with haskell yet?
by Jefferson Heard 21 Feb '07

21 Feb '07

I don't want to duplicate anyone's work, and I'm not sure that NDA would allow me to release the code in any case (have to check on it carefully), but is anyone currently using the CUDA framework from nVidia inside of Haskell for highly parallel programming? -- Jeff

1 0

Re: Leaves of a Tree
by Chad Scherrer 21 Feb '07

21 Feb '07

Tom, I think inserting elements would be a lot faster than multiple unions. I would try: leafList :: Tree -> [Int] leafList (Leaf n) = [n] leafList (Branch left right) = leafList left ++ leafList right leaves = fromList . leafList If you're writing many functions on Trees (or maybe even if you're not), you might consider writing a fold function and putting leafList in terms of this. Do you have experience with folds? -Chad > Hello, > > Any recommendations for speeding up extracting the set of leaves from a tree? > > data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) > > My slow, naive function: > > leaves :: Tree -> Set Int > leaves (Leaf n) = singleton n > leaves (Branch left right) = union (leaves left) (leaves right) > > In my case, many of the branches in the tree are the same. I suspect > the fixed point operation mentioned in the thread "speeding up > fibonacci with memoizing" is applicable, but I'm having a tough time > making the connection. > > -Tom

2 1

Type-level lambdas in Haskell?
by oleg＠pobox.com 21 Feb '07

21 Feb '07

On 2/21/07, Alfonso Acosta <alfonso.acosta at gmail.com> wrote: > In my opinion adding Type-level lambdas would be the way to go, but > they unfortunately are not part of Haskell. Type-level lambdas are already present in Haskell. Please see the messages On computable types. I. Typed lambda and type closures http://www.haskell.org/pipermail/haskell/2006-September/018486.html On computable types. II. Flipping the arrow http://www.haskell.org/pipermail/haskell/2006-September/018487.html

1 0

Type-level lambdas in Haskell? ( was Multiparameter class error)
by Alfonso Acosta 21 Feb '07

21 Feb '07

Now I'm facing another problem, sorry if it takes too long to reach the Type level lambdas issue ... The full definition of my class is class Synchronous s f1 f2 | s -> f1, s -> f2 where mapSY :: f1 a b -> s a -> s b delaySY :: a -> s a -> s a zipWithSY :: f2 a b c-> s a -> s b -> s c The goal of this class is to extend the name of the following functions (which BTW are already present in a working library and for that reason _it is a must_ that their types remain untouched) ... mapSY :: (a->b) -> Signal a -> Signal b delaySY :: a -> Signal a -> Signal b -> Signal c zipWithSY :: (a->b->c) -> Signal a -> Signal b -> Signal c .. accepting these definitions as well mapSY :: (HDPrimType a, HDPrimType b) => HDFun (a->b) -> HDSignal a -> Signal b delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a zipWithSY :: (HDPrimType a, HDPrimType b, HDPrimType c) => HDFun (a->b->c) -> HDSignal a -> HDSignal b -> HDSignal c The problem is: How to choose the f1 and f2 parameters when defining the instances? instance Synchronous Signal (->) ?? where instance Synchronous HDSignal ?? ?? where I'm facing one of the problems discussed at Type Classes with Functional Dependencies (http://web.cecs.pdx.edu/~mpj/pubs/fundeps-esop2000.pdf )section 3.1: "Some of the remaining instances can be reworked to ﬁt the constructor class framework by introducing dummy type and value constructors" The following is a solution following the one proposed by MJones in his paper, but is not acceptable as it requires changing the types of the original functions. newtype F2 a b c = F2 (a->b->c) newtype HDF1 a b = HDF1 (HDFun (a->b)) newtype HDF2 a b c = HDF2 (HDFun (a->b->c)) instance Synchronous Signal (->) F2 where .... instance Synchronous HDSignal HDF1 HDF2 where ... Following MJones advice, redefining the class to something such us ... class Synchronous2 a sa sb sc f1ab f2abc | {- dependencies ommited -} where mapSY :: f1ab -> sa -> sb delaySY :: a -> sa -> sa zipWithSY :: f2abc-> sa -> sb -> sc ... is feasible but not elegant at all because the number of class parameters and dependencies are dramatically increased. In my opinion adding Type-level lambdas would be the way to go, but they unfortunately are not part of Haskell. Something like this would be much more expressive and useful. Using the first definition of the class we could do something as instance Synchronous Signal (->) (\a b c -> (a->b->c)) where .... instance Synchronous HDSignal (\a b -> HDFun (a->b)) (\a b c -> HDFun (a->b->c)) where ... Is there any extension to the language covering type-level lambdas or even a plan to include them in next revision? Thanks, Fons On 2/21/07, Alfonso Acosta <alfonso.acosta(a)gmail.com> wrote: > Thanks, the functional dependency solved the problem > > On 2/21/07, Yitzchak Gale <gale(a)sefer.org> wrote: > > Hi Alfonso, > > > > You wrote: > > > Could not deduce (Synchronous s f11) > > > from the context (Synchronous s f1) > > > \begin{code} > > > class Synchronous s f1 where > > > mapSY :: f1 a b -> s a -> s b > > > delaySY :: a -> s a -> s a > > > sourceSY :: f1 a a -> a -> s a > > > sourceSY f s0 = o > > > where > > > o = delaySY s0 s > > > s = mapSY f o > > > \end{code} > > > > > > Can anyone explain a bit further than GHC what am I doing wrong? > > > > Every method of a multiparameter class must refer > > to every parameter in its signature. Otherwise, there > > is no way for the compiler to know which instance > > of the class you want when you use the method. > > > > There are two ways to get around this restriction. > > One is to use a functional dependency: > > > > class Synchronous s f1 | s -> f1 where > > > > That promises that for each type s, you will > > only define an instance Synchronous s f1 > > for at most a single type f1. Now, whenever > > you mention s in a type signature, it is as if > > you also mentioned f1. > > > > If you can't keep that promise, then you will > > have to use a phantom parameter. Change > > the type of delaySY to > > > > delaySY :: f1 -> a -> s a -> s a > > > > and ignore the f1 parameter when you implement > > delaySY: > > > > delaySY _ x y = ... > > > > Then, when you use delaySY, you specify the > > type f1 by writing: > > > > delaySY (undefined :: T) ... > > > > Regards, > > Yitz > > >

2 1