- Haskell-Cafe - Haskell.org

Design of a DSL in Haskell
by Joerg Fritsch 05 Dec '12

05 Dec '12

This is probably a very basic question. I am working on a DSL that eventuyally would allow me to say: import language.cwmwl main = runCWMWL $ do eval ("isFib::", 1000, ?BOOL) I have just started to work on the interpreter-function runCWMWL and I wonder whether it is possible to escape to real Haskell somehow (and how?) either inside ot outside the do-block. I thought of providing a defautl-wrapper for some required prelude functions (such as print) inside my interpreter but I wonder if there are more elegant ways to co-loacate a DSL and Haskell without falling back to being a normal library only. --Joerg

5 12

RFC: Changes to Travis CI's Haskell support
by Simon Hengel 05 Dec '12

05 Dec '12

Hi, currently the default to test Haskell projects on Travis CI [1] is: install: - cabal install --enable-tests script: - cabal test The issue with this is that it runs the test-suite twice, which is a waste of resources and delays build reports. This was an oversight on my part, when I adapted Travis's Haskell support for cabal-install-0.14.0. I think the right thing to do is: install: - cabal install --only-dependencies --enable-tests script: - cabal configure --enable-tests && cabal build && cabal test Please let me know if you think there are better ways to do it, or if you see any issues. Cheers, Simon [1] https://travis-ci.org/

2 2

confirming order of kinds and rank of types
by dude 05 Dec '12

05 Dec '12

I hope you can help me confirm my understanding of the order of kinds and rank of types as reported in [1,2]. I have been validating the mapping functions in Section 2 against the GHC 7.4.2 type checker by explicitly annotating the universal quantifiers as described in [1]. 1. Just to baseline my understanding, given the following data type data U a = UC (forall a. a) -- :k U, U :: * -> * -- order of kind = 1 -- :t UC, UC :: (forall a1. a1) -> U a -- rank of type = 2 am I correct that the order of the kind is 1 and the rank of the type constructor is 2? See page 3 of [1] for counting the order and also page 3 of [2] for counting rank. 2. Assuming the answer to #1 above is yes, am I also correct that the order of Fix is 2 and the rank of In is also 2 and the annotation to In does not affect its rank? newtype Fix f = In (forall f. f (Fix f)) -- :k Fix, Fix :: (* -> *) -> * -- order of kind = 2 -- :t In, In :: (forall (f1 :: * -> *). f1 (Fix f1)) -> Fix f -- rank of type still = 2 3. Are the explicit annotations I added to the following fixpoint operator correct? Hinze indicates this is a third order kind and it seems that although the annotation on HIn has a higher order, the rank of the type hasn't changed, correct? newtype HFix h a = HIn (forall h. (forall a. h (HFix h) a)) -- :k HFix, HFix :: ((* -> *) -> * -> *) -> * -> * -- per hinze order of kind = 3 -- :t HIn, HIn :: (forall (h1 :: (* -> *) -> * -> *) a1. h1 (HFix h1) a1) -> HFix h a -- still rank of type = 2 because there's one quantifier to the left of the function arrow. If all that all checks out, I have a few follow up questions: 4. Hinze reports that mapHFix is Rank3, but the following type checks with the Rank2Type pragma and if I remove the explicit universal quantifiers in HIn. Put the quantifiers back in an it does not type check. mapHFix maph mapa (HIn v) = HIn (maph (mapHFix maph) mapa v) 5. Also, the inferred signature for mapHFix differs from the one stated by Hinze. It's this ... mapHFix :: ((t2 -> HFix t t1 -> HFix h a) -> t2 -> t (HFix t) t1 -> h (HFix h) a) -> t2 -> HFix t t1 -> HFix h a What is the rank of this type signature? The type variables are not in the same order as Hinze's and I was able to just wrap a (forall t2 t t1 h a.) around the whole thing and it type checked. Why are they different? 6. What is the correct type signature for mapHFix? The correct type signature should support changing the pragma from Rank2Types to RankNTypes, then today's 7.4.2 type checker will succeed where it could not in 1999 when the paper was written, correct? Thanks so much for helping me confirm my understanding of these issues! -- dude 1. Polytypic Values Posess Polykinded Types. (Hinze, 1999) 2. A Direct Algorithm for Type Inference in the Rank 2 Fragment of the Second Order Lambda Calculus. (Kfoury, 1993)

1 0

Naive matrix multiplication with Accelerate
by Clark Gaebel 05 Dec '12

05 Dec '12

Hello cafe, I've recently started learning about cuda and hetrogenous programming, and have been using accelerate [1] to help me out. Right now, I'm running into trouble in that I can't call parallel code from sequential code. Turns out GPUs aren't exactly like Repa =P. Here's what I have so far: import qualified Data.Array.Accelerate as A import Data.Array.Accelerate ( (:.)(..) , Acc , Vector , Scalar , Elt , fold , slice , constant , Array , Z(..), DIM1, DIM2 , fromList , All(..) , generate , lift, unlift , shape ) import Data.Array.Accelerate.Interpreter ( run ) dotP :: (Num a, Elt a) => Acc (Vector a) -> Acc (Vector a) -> Acc (Scalar a) dotP xs ys = fold (+) 0 $ A.zipWith (*) xs ys type Matrix a = Array DIM2 a getRow :: Elt a => Int -> Acc (Matrix a) -> Acc (Vector a) getRow n mat = slice mat . constant $ Z :. n :. All -- Naive matrix multiplication: -- -- index (i, j) is equal to the ith row of 'a' `dot` the jth row of 'b' matMul :: A.Acc (Matrix Double) -> A.Acc (Matrix Double) -> A.Acc (Matrix Double) matMul a b' = A.generate (constant $ Z :. nrows :. ncols) $ \ix -> let (Z :. i :. j) = unlift ix in getRow i a `dotP` getRow j b where b = A.transpose b' -- I assume row indexing is faster than column indexing... (Z :. nrows :. _ ) = unlift $ shape a (Z :. _ :. ncols) = unlift $ shape b This, of course, gives me errors right now because I'm calling getRow and dotP from within the generation function, which expects Exp[ression]s, not Acc[elerated computation]s. So maybe I need to replace that line with an inner for loop? Is there an easy way to do that with Accelerate? Thanks for your help, - Clark [1] http://hackage.haskell.org/package/accelerate

3 9

Is hackage.haskell.org down?
by Ivan Perez 04 Dec '12

04 Dec '12

Hi haskellers, I've been having problems to access hackage.haskell.org for the past 2-4 hours. Is everything ok? Cheers, Ivan

3 2

PLMW: Mentoring at POPL. Second Call for Participation
by Gareth Smith 04 Dec '12

04 Dec '12

Students! You have until Sunday to apply for funding to come to both POPL and PLMW! CALL FOR PARTICIPATION SIGPLAN Programming Languages Mentoring Workshop, Rome Tuesday January 22, 2013 Co-located with POPL 2013 PLMW web page: http://www.doc.ic.ac.uk/~gds/PLMW/index.html After the resounding success of the first Programming Languages Mentoring Workshop at POPL 2012, we proudly announce the 2nd SIGPLAN Programming Languages Mentoring Workshop (PLMW), co-located with POPL 2013 and organised by Nate Foster, Philippa Gardner, Alan Schmitt, Gareth Smith, Peter Thieman and Tobias Wrigstad. The purpose of this mentoring workshop is to encourage graduate students and senior undergraduate students to pursue careers in programming language research. This workshop will provide technical sessions on cutting-edge research in programming languages, and mentoring sessions on how to prepare for a research career. We will bring together leaders in programming language research from academia and industry to give talks on their research areas. The workshop will engage students in a process of imagining how they might contribute to our research community. We especially encourage women and underrepresented minority students to attend PLMW. Since PLMW will be in Rome this year, we particularly look forward to seeing Eastern European students at the workshop. This workshop is part of the activities surrounding POPL, the Symposium on Principles of Programming Languages, and takes place the day before the main conference. One goal of the workshop is to make the POPL conference more accessible to newcomers. We hope that participants will stay through the entire conference, and will also attend the POPL tutorials on Monday 21st January which are free to PLMW registered attendees. Through the generous donation of our sponsors, we are able to provide scholarships to fund student participation. These scholarships will cover reasonable expenses (airfare, hotel and registration fees) for attendance at both the workshop and the POPL conference. Students attending this year will get one year free student membership of SIGPLAN The workshop registration is open to all. Students with alternative sources of funding are welcome. APPLICATION for PLMW scholarship: The scholarship application can be accessed from the workshop web site (http://www.doc.ic.ac.uk/~gds/PLMW/index.html) The deadline for full consideration of funding is 9th December, 2012. Selected participants will be notified from Friday 14th December, and will need to register for the workshop by December 24th. SPONSORS: Google Imperial College London Jane Street Monoidics NSF Resource Reasoning SIGPLAN vmware

1 0

Is it possible to have constant-space JSON decoding?
by Iustin Pop 04 Dec '12

04 Dec '12

Hi, I'm trying to parse a rather simple but big JSON message, but it turns out that memory consumption is a problem, and I'm not sure what the actual cause is. Let's say we have a simple JSON message: an array of 5 million numbers. I would like to parse this in constant space, such that if I only need the last element, overall memory usage is low (yes, unrealistic use, but please bear with me for a moment). Using aeson, I thought the following program will be nicely-behaved: > import Data.Aeson > import qualified Data.Attoparsec.ByteString.Lazy as AL > import qualified Data.ByteString.Lazy as L > > main = do > r <- L.readFile "numbers" > case AL.parse json r :: AL.Result Value of > AL.Fail _ context errs -> do > print context > print errs > AL.Done _ d -> case fromJSON d::Result [Value] of > Error x -> putStrLn x > Success d -> print $ last d However, this uses (according to +RTS -s) ~1150 GB of memory. I've tried switching from json to json', but while that uses slightly less memory (~1020 MB) it clearly can't be fully lazy, since it forces conversion to actual types. Looking at the implementation of "FromJSON [a]", it seems we could optimise the code by not forcing to a list. New (partial) version does: > AL.Done _ d -> case d of > Array v -> print $ V.last v And this indeed reduces the memory, when using json', to about ~700MB. Better, but still a lot. It seems that the Array constructor holds a vector, and this results in too much strictness? Looking at the memory profiles (with "json" and "Array"), things are quite interesting - lots of VOID, very small USE, all generated from Data.Aeson.Parser.Internal:array. Using -hd, we have a reasonable equal split between various attoparsec combinators, Data.Aeson.Parser.Internal epressions, etc. So, am I doing something wrong, or is it simply not feasible to get constant-space JSON decoding? Using the 'json' library instead of 'aeson' is no better, since that wants the input as a String which consumes even more memory (and dies, when compiled with -O2, with out of stack even for 64MB stack). thanks, iustin

4 7

Re: [Haskell-cafe] Design of a DSL in Haskell
by Brent Yorgey 03 Dec '12

03 Dec '12

(Sorry, forgot to reply to the list initially; see conversation below.) On Mon, Dec 03, 2012 at 03:49:00PM +0100, Joerg Fritsch wrote: > Brent, > > I believe that inside the do-block (that basically calls my > interpreter) I cannot call any other Haskell function that are not > recognized by my parser and interpreter. This seems to just require some sort of "escape mechanism" for embedding arbitrary Haskell code into your language. For example a primitive embed :: a -> CWMWL a (assuming CWMWL is the name of your monad). Whether this makes sense, how to implement embed, etc. depends entirely on your language and interpreter. However, as you imply below, this may or may not be possible depending on the type a. In that case I suggest making embed a type class method. Something like class Embeddable a where embed :: a -> CWMWL a I still get the feeling, though, that I have not really understood your question. > I am also trying to learn how I could preserve state from one line > of code of my DSL to the next. I understand that inside the > interpreter one would use a combination of the state monad and the > reader monad, but could not find any non trivial example. Yes, you can use the state monad to preserve state from one line to the next. I am not sure what you mean by using a combination of state and reader monads. There is nothing magical about the combination. You would use state + reader simply if you had some mutable state as well as some read-only configuration to thread through your interpreter. xmonad is certainly a nontrivial example but perhaps it is a bit *too* nontrivial. If I think of any other good examples I'll let you know. -Brent > > > On Dec 3, 2012, at 1:23 PM, Brent Yorgey wrote: > > > On Sun, Dec 02, 2012 at 03:01:46PM +0100, Joerg Fritsch wrote: > >> This is probably a very basic question. > >> > >> I am working on a DSL that eventuyally would allow me to say: > >> > >> import language.cwmwl > >> main = runCWMWL $ do > >> eval ("isFib::", 1000, ?BOOL) > >> > >> I have just started to work on the interpreter-function runCWMWL and I wonder whether it is possible to escape to real Haskell somehow (and how?) either inside ot outside the do-block. > > > > I don't think I understand the question. The above already *is* real > > Haskell. What is there to escape? > > > >> I thought of providing a defautl-wrapper for some required prelude > >> functions (such as print) inside my interpreter but I wonder if > >> there are more elegant ways to co-loacate a DSL and Haskell without > >> falling back to being a normal library only. > > > > I don't understand this sentence either. Can you explain what you are > > trying to do in more detail? > > > > -Brent > >

2 2

Can not use ST monad with polymorphic function
by Dmitry Kulagin 03 Dec '12

03 Dec '12

Hi Cafe, I try to implement some sort of monadic fold, where traversing is polymorphic over monad type. The problem is that the code below does not compile. It works with any monad except for ST. I suspect that monomorphism is at work here, but it is unclear for me how to change the code to make it work with ST. fold :: Monad m => (Int -> m ()) -> m () fold f = mapM_ f [0..20] selectFold :: Monad m => String -> IO ((Int -> m ()) -> m ()) selectFold method = do -- in real program I'd like to choose between -- different fold methods, based on some IO context return fold useFold :: Monad m => ((Int -> m ()) -> m ()) -> m () useFold fold' = fold' f where f _ = return () -- some trivial iterator main = do fold'' <- selectFold "some-method-id" print $ runST $ useFold fold'' Thank you! Dmitry

4 5

To my boss: The code is cool, but it is about 100 times slower than the old one...
by Fixie Fixie 03 Dec '12

03 Dec '12

Hi all haskellers I every now and then get the feeling that doing my job code in Haskell would be a good idea. I have tried a couple of times, but each time I seem to run into performance problems - I do lots of heavy computing. The problem seems to be connected to lazy loading, which makes my programs so slow that I really can not show them to anyone. I have tried all tricks in the books, like !, seq, non-lazy datatypes... I was poking around to see if this had changed, then I ran into this forum post: http://stackoverflow.com/questions/9409634/is-indexing-of-data-vector-unbox… The last solution was a haskell program which was in the 3x range to C, which I think is ok. This was in the days of ghc 7.0 I then tried compile the programs myself (ghc 7.4.1), but found that now the C program now was more that 100x faster. The ghc code was compiled with both O2 and O3, giving only small differences on my 64-bit Linux box. So it seems something has changed - and even small examples are still not safe when it comes to the lazy-monster. It reminds me of some code I read a couple of years ago where one of the Simons actually fired off a new thread, to make sure a variable was realized. A sad thing, since I am More that willing to go for Haskell if proves to be usable. If anyone can see what is wrong with the code (there are two haskell versions on the page, I have tried the last and fastest one) it would also be interesting. What is your experience, dear haskellers? To me it seems this beautiful language is useless without a better lazy/eager-analyzer. Cheers, Felix

8 21