- Glasgow-haskell-users

strong type derivation in ghc 6.12 compared to 6.12
by Seyed Hosein Attarzadeh Niaki 07 May '10

07 May '10

I have problems with upgrading some already working code for GHC 6.12. The following code: ----------------------------------------------------------- {-# LANGUAGE DeriveDataTypeable, GeneralizedNewtypeDeriving, TemplateHaskell #-} import Data.Data import Language.Haskell.TH.Syntax class Nat a class (Data a, Lift a) => ProcType a instance (Lift a, Nat s) => Lift (FSVec s a) where lift (FSVec xs) = undefined newtype Nat s => FSVec s a = FSVec {unFSVec :: [a]} deriving (Eq, Typeable, Data) -- The following line does not cause a problem in GHC 6.10 -- instance (Typeable s, Nat s, ProcType a) => ProcType (FSVec s a) ----------------------------------------------------------- works fine in ghc 6.10.4 and I get (extra stuff removed): // *Main> :i FSVec newtype (Nat s) => ... instance (Data a, Typeable s, Nat s) => Data (FSVec s a) -- Defined at ghctest.hs:16:26-29 ... // but in 6.12.2 what I get is: // *Main> :i FSVec newtype (Nat s) => ... instance (Data s, Data a, Nat s) => Data (FSVec s a) ... // So, although the last line in the above code compiles correctly in ghc 6.10.4, in 6.12.2 GHC complains with: // ghctest.hs:19:10: Could not deduce (Data s) from the context (Typeable s, Nat s, ProcType a) arising from the superclasses of an instance declaration at ghctest.hs:19:10-64 Possible fix: add (Data s) to the context of the instance declaration In the instance declaration for `ProcType (FSVec s a)' Failed, modules loaded: none. // Why are they different? Why 6.12 derives a stronger constraint? Is it a bug or it was not working correctly before? -- Hosein Attarzadeh

3 2

segmentation fault in Gtk2Hs callbacks
by Axel Simon 07 May '10

07 May '10

Good morning, I'm looking at ticket http://hackage.haskell.org/trac/ghc/ticket/4038 and wonder who is to blame: - this segmentation fault occurs in Gtk2Hs' callbacks (i.e. a Haskell function pointer is being passed to C land) and in a signal (where a general machinery is used to invoke a Haskell function), thus, it doesn't seem to be the way callbacks are used - the segfault only occurs in ghc 6.12.2 not in ghc 6.12.1 However, in the release notes of 6.12.2 there are no changes indicated that look like the RTS has changed. So I would like to simply ask: Are any of the GHC developers aware of any change in the concurrency or GC behaviour in GHC's RTS? Have any other parameters changed (perhaps something with multithreading?). Neither Gtk2Hs nor GHC seem to have changed, yet, there are these intermittend segfaults. It would be good to know which part is the culprit. Thanks, Axel

2 1

standalone binary deriving
by Ben 05 May '10

05 May '10

compiling the following fragment in ghci {-# LANGUAGE StandaloneDeriving #-} import Data.Binary (Binary) newtype Pair a b = Pair (a,b) deriving instance (Binary a, Binary b) => Binary (Pair a b) results in the following message: Prelude> :load "/Users/catbee/Documents/dev/haskell/savestream/foo.hs" [1 of 1] Compiling Main ( /Users/catbee/Documents/dev/haskell/savestream/foo.hs, interpreted ) ghc: panic! (the 'impossible' happened) (GHC version 6.12.1 for i386-apple-darwin): genDerivBinds: bad derived class binary-0.5.0.2:Data.Binary.Binary{tc rkt} Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug should i file a bug report? b

2 1

Re: Parallel Haskell: 2-year project to push real world use
by John Lato 05 May '10

05 May '10

> From: Roman Leshchinskiy <rl(a)cse.unsw.edu.au> Following on this discussion, I have an algorithm that currently uses BLAS to do the heavy work. I'd like to try to get it working with DPH or Repa, although my prior attempts have been less than successful. I have a vector of vectors where each element depends upon the previous two; I can use zipWithP to generate each successive element, but I don't see how to create the entire structure. I could use "unfold" if one were provided. The best approach I can think of is to create a sequential list of element-vectors. Also, where is scanP? I don't see it in Data.Array.Parallel.Prelude (GHC-6.12.1). Cheers, John

1 0

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

* Roman Leshchinskiy <rl(a)cse.unsw.edu.au> [04.05.2010 10:02]: > On 04/05/2010, at 11:10, Christian Höner zu Siederdissen wrote: > > > * Ben Lippmeier <benl(a)ouroborus.net> [04.05.2010 02:21]: > >> > >> You can certainly create an array with these values, but in the provided code it looks like each successive array element has a serial dependency on the previous two elements. How were you expecting it to parallelise? > > > > actually, in reality it is rather more complex, in a 2d-array, each cell > > (i,j) requires a linear number of accesses to previously calculated > > cells that all have indices bounded by the current (i,j). > > > > One of the simplest codes is like this: > > > > forall i in [1..n] > > forall j in [i..n] > > set (i,j) to: minimum of (i,k)+(k,j) (forall k in [i+1..j-1]) > > Is this related to wavefront algorithms? Although those only access immediate neighbours IIRC. There is some similarity, but this problem extends to a lot of dynamic program algorithms that work on matrices. > > In any case, vector could well provide an operation like this: > > cant_think_of_a_name :: Vector v a => Int -> (v a -> a) -> v a > > The function would take the initialised prefix of the vector (starting with empty) and produce the next element. This would require a bit of hackery underneath but the interface would be safe and pure. Would something like this be useful? This would be very useful in general, as a number of algorithms that now require lazy arrays or ST/IO could be written with pure code. With the correct index transformation, it should be possible to have everything laid out nicely. > > > Here http://www.tbi.univie.ac.at/newpapers/Abstracts/98-06-009.ps.gz is > > a description of a parallel version of RNAfold. > > IIUC, this parallelises processing of each diagonal but computes the diagonals one after another. Could you perhaps store each diagonal as a separate (parallel) array? That would make things much simpler. That is no problem at all. > > > I can make my libraries available under GPLv3, they just need a bit of > > love. This gives you a moderately complex algorithm for which there is, > > too, a highly optimized C version (RNAfold -d2, in the vienna rna > > package). > > That would be fantastic! > > Roman > > Gruss, Christian

2 1

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

* Ben Lippmeier <benl(a)ouroborus.net> [04.05.2010 02:21]: > > You can certainly create an array with these values, but in the provided code it looks like each successive array element has a serial dependency on the previous two elements. How were you expecting it to parallelise? actually, in reality it is rather more complex, in a 2d-array, each cell (i,j) requires a linear number of accesses to previously calculated cells that all have indices bounded by the current (i,j). One of the simplest codes is like this: forall i in [1..n] forall j in [i..n] set (i,j) to: minimum of (i,k)+(k,j) (forall k in [i+1..j-1]) So, either I use destructive updates or need a tricky way to extend the already computed part of the array with the new part (i,j). The above code shows only why I need destructive updates. RNA folding is one of those where it is needed. I will try to distill the code down to an example that shows a possibility for parallelization. I would want to use this for future algorithms where it makes much more sense (O(n^4) or more), but that still first update an array element, and then access it later. Here http://www.tbi.univie.ac.at/newpapers/Abstracts/98-06-009.ps.gz is a description of a parallel version of RNAfold. > > Repa arrays don't support visible destructive update. For many algorithms you should't need it, and it causes problems for parallelisation. > > I'm actively writing more Repa examples now. Can you sent me some links explaining the algorithm that you're using, and some example data + output? > > Thanks, > Ben. > > > > On 04/05/2010, at 9:21 AM, Christian Höner zu Siederdissen wrote: > > > a = array (1,10) [ (i,f i) | i <-[1..10]] where > > f 1 = 1 > > f 2 = 1 > > f i = a!(i-1) + a!(i-2) > > > > (aah, school ;) > > > > Right now, I am abusing vector in ST by doing this: > > > > a <- new > > a' <- freeze a > > forM_ [3..10] $ \i -> do > > write a (a'!(i-1) + a!(i-2)) > > > > Let's say I wanted to do something like this in dph (or repa), does that > > work? We are actually using this for RNA folding algorithms that are at > > least O(n^3) time. For some of the more advanced stuff, it would be > > really nice if we could "just" parallelize. > > > > To summarise: I need arrays that allow in-place updates. > > > > Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are > > using vector right now. On a single core, it performs really great -- > > even compared to C-code that has been optimized a lot. > > > > Thanks and "Viele Gruesse", > > Christian >

2 1

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

* Roman Leshchinskiy <rl(a)cse.unsw.edu.au> [04.05.2010 02:32]: > On 04/05/2010, at 09:21, Christian Höner zu Siederdissen wrote: > > > Hi, > > > > on that topic, consider this (rather trivial) array: > > > > a = array (1,10) [ (i,f i) | i <-[1..10]] where > > f 1 = 1 > > f 2 = 1 > > f i = a!(i-1) + a!(i-2) > > > > (aah, school ;) > > > > Right now, I am abusing vector in ST by doing this: > > > > a <- new > > a' <- freeze a > > forM_ [3..10] $ \i -> do > > write a (a'!(i-1) + a!(i-2)) > > > > Let's say I wanted to do something like this in dph (or repa), does that > > work? We are actually using this for RNA folding algorithms that are at > > least O(n^3) time. For some of the more advanced stuff, it would be > > really nice if we could "just" parallelize. > > Do you really just need a prefix sum? These are easily parallelisable if the operator is associative. For instance, you could implement the Fibonacci sequence as: > > mapP fst $ scanP (\(a,b) _ -> (a+b,a)) (1,0) $ replicateP n (0,0) > > and DPH would parallelise it. That's how I would write the above with vector as well. That is, kind of, the fun part: you have (1) a number of vectors whose values depend on each other (bad!) (2) in-place update (bad!) (3) rather trivial calculations for each element (mostly: sum, minimum, fold, map, backpermute) (good!), we have simple semiring calculations here > > > To summarise: I need arrays that allow in-place updates. > > In-place updates + parallelism = bad! That's oversimplifying, of course. But the transformations underlying DPH, for instance, simply don't work in the presence of side effects. The thing is, you can write the algorithm in a way such that each operation on index "k" (whatever dimension k has) only requires access to values <=k and those values will never change again. The problem is that more than one vector is involved making it less fun to write code like your fibonacci example. > > > Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are > > using vector right now. On a single core, it performs really great -- > > even compared to C-code that has been optimized a lot. > > That's great to know! Do you (or anyone else) by any chance have any benchmarks you could share? At the moment, I'm only benchmarking vector with a couple of rather simplistic algorithms which is a bit of a problem. I can make my libraries available under GPLv3, they just need a bit of love. This gives you a moderately complex algorithm for which there is, too, a highly optimized C version (RNAfold -d2, in the vienna rna package). I am giving a talk wednesday, after that I'll prepare the libraries for hackage. Gruss, Christian

1 0

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 04 May '10

04 May '10

Hi, on that topic, consider this (rather trivial) array: a = array (1,10) [ (i,f i) | i <-[1..10]] where f 1 = 1 f 2 = 1 f i = a!(i-1) + a!(i-2) (aah, school ;) Right now, I am abusing vector in ST by doing this: a <- new a' <- freeze a forM_ [3..10] $ \i -> do write a (a'!(i-1) + a!(i-2)) Let's say I wanted to do something like this in dph (or repa), does that work? We are actually using this for RNA folding algorithms that are at least O(n^3) time. For some of the more advanced stuff, it would be really nice if we could "just" parallelize. To summarise: I need arrays that allow in-place updates. Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are using vector right now. On a single core, it performs really great -- even compared to C-code that has been optimized a lot. Thanks and "Viele Gruesse", Christian * Duncan Coutts <duncan.coutts(a)googlemail.com> [30.04.2010 17:11]: > On Fri, 2010-04-30 at 10:25 -0400, Tyson Whitehead wrote: > > On April 30, 2010 06:32:55 Duncan Coutts wrote: > > > In the last few years GHC has gained impressive support for parallel > > > programming on commodity multi-core systems. In addition to traditional > > > threads and shared variables, it supports pure parallelism, software > > > transactional memory (STM), and data parallelism. With much of this > > > research and development complete, and more on the way, the next stage > > > is to get the technology into more widespread use. > > > > Does this mean DPH is ready for abuse? > > This project is about pushing the practical use of the parallel > techniques that are already mature, rather than about pushing research > projects along further. > > So this project is not really about DPH. On the other hand it's possible > someone might be able to make more immediate use of the dense, regular > parallel arrays which has been a recent spinoff of the DPH project. They > have the advantage of being considerably easier to implement, but much > less expressive than the full sparse, nested parallel arrays. > > Duncan > > _______________________________________________ > Glasgow-haskell-users mailing list > Glasgow-haskell-users(a)haskell.org > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

4 3

Re: Parallel Haskell: 2-year project to push real world use
by Christian Höner zu Siederdissen 03 May '10

03 May '10

Sorry, to make it more clear: in the line: > write a (a'!(i-1) + a!(i-2)) only > (a'!(i-1) + a!(i-2)) would need to be parallel, as there we typically have a sum/minimum or whatever. The forM_ over each index does not need to be, since we have to fill the array anyway... * Christian Höner zu Siederdissen <choener(a)tbi.univie.ac.at> [04.05.2010 01:22]: > Hi, > > on that topic, consider this (rather trivial) array: > > a = array (1,10) [ (i,f i) | i <-[1..10]] where > f 1 = 1 > f 2 = 1 > f i = a!(i-1) + a!(i-2) > > (aah, school ;) > > Right now, I am abusing vector in ST by doing this: > > a <- new > a' <- freeze a > forM_ [3..10] $ \i -> do > write a (a'!(i-1) + a!(i-2)) > > Let's say I wanted to do something like this in dph (or repa), does that > work? We are actually using this for RNA folding algorithms that are at > least O(n^3) time. For some of the more advanced stuff, it would be > really nice if we could "just" parallelize. > > To summarise: I need arrays that allow in-place updates. > > Otherwise, most libraries that do heavy stuff (O(n^3) or worse) are > using vector right now. On a single core, it performs really great -- > even compared to C-code that has been optimized a lot. > > Thanks and "Viele Gruesse", > Christian

1 0

blackholes and exception handling
by Sebastian Fischer 03 May '10

03 May '10

Hello, GHC can spot (some) non-terminating computations and terminate with blackhole: <<loop>> instead of running indefinitely. With exception handling one can handle such situations. The following program 'launches missiles': import Control.Exception main = do handle go_ahead don't_launch_first launch_missiles don't_launch_first = don't_launch_first go_ahead :: SomeException -> IO () go_ahead _ = putStr "go ahead, " launch_missiles = putStr "fire!" The output of this program is go ahead, fire! although, don't_launch_first is a non-terminating computation. Without black-hole detection this code would never 'launch missiles'. Is the above output intended? The idea behind black-hole detection is that one bottom is as good as another [1]. Consequently, exception handling may not distinguish between non-termination and other errors. Is the equation _|_ `catch` const a = a supposed to hold in general (for every kind of bottom)? Or is it a bug in GHC that programmers can handle black-hole errors? Sebastian [1] A semantics for imprecise exceptions http://portal.acm.org/citation.cfm?id=301637 -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

4 4