- Haskell-Cafe - Haskell.org

Fwd: [Haskell-cafe] Parsing in Practice
by Tomasz Zielonka 26 Oct '05

26 Oct '05

[Sending it again to haskell-cafe] On 10/18/05, Tom Hawkins <tom(a)confluent.org> wrote: > I am writing a parser for a big, ugly, standard language and I need to > decide between using either Happy or Parsec. I wrote a parser for a big, ugly, non-standard language - Transact-SQL from MSSQL. > I currently have a priliminary LALR(1) grammar, so a port to Happy would > be relatively easy. In such situation I would try Happy first, but with some cautiousness. I also started with LALR(1) parsing in ocamlyacc, but I didn't manage to cover the whole language with this approach. The more productions I added the more conflicts I had. Of course I tried to remove the conflicts, but often when I added new productions I had to repeat the work. It is possible that my understanding of LALR parsing was insufficient, but the problem is that the set of LALR grammars is not closed under composition (as I've read in some paper on GLR parsing). Do you know that Happy supports GLR parsing? > But, I'm wondering if life would be easier if I chose Parsec's combinator > parsing instead. >From my experience it was indeed quite nice. However, there were some parts of the grammer that I didn't know how to handle without using "try", which could result in worse efficiency and error reporting. > It's error reporting seems to be top notch So long as you can avoid using "try" for non-terminals. > and it's "optional", "many", and "sepBy1" combinators are very elegant. Indeed they are, as they correspond nicely to E in EBNF ;-) > However, I have a few concerns with Parsec. First is performance; what > factor of slow-down should I expect? I only have a Parsec parser, so I can't compare. I dimly remember that my parser had an average efficiency, ie. it could parse about 100kB per second on P3 850. There is a parser-combinator version of a parser for Haskell which you could compare to the one from GHC. > Second is bug prevention. I don't have much experience writing LL(n) > grammars, so how easy is it to introduce bugs in a Parsec grammar? I always feared that this would be a problem, but it wasn't. I used a sample of about 1MB of application code to test, and I didn't get to using QuickCheck. > Even though I hate debugging LALR(1) parsing ambiguities, > it prevents problems. Yes, when you fight the conflicts, you get static guarantees in return. I wonder how it is with GLR? Best regards Tomasz

2 1

Re: [Haskell-cafe] Nice way to calculate character frequency in a string
by Charles SDudu 26 Oct '05

26 Oct '05

It seems like the fastest way to build a list of frequency from a string is this : import Data.Array (assocs, accumArray, Array) frequency :: String -> [(Char,Int)] frequency = filter (\f -> snd f>0) . assocs . accumArray (+) 0 ('\0', '\255') . map (\x->(x,1)) -- (~1.3 sec on a string of 700ko) But if we want to make this polymorphic we have to do this : import Data.Ix (Ix) frequency :: (Ix a, Bounded a) => [a] -> [(a,Int)] frequency = filter (\f -> snd f>0) . assocs . accumArray (+) 0 (minBound, maxBound) . map (\x->(x,1)) -- (>5 sec on a string of 700ko) but it's really much slower, it seems like min/maxBound are check each time or I dont know, and it's restrictive on the type of the elements of the list. The best polymorphic version seems to be : import Data.Map as Map (lookup, assocs, empty, insertWith) frequency :: (Ord a) => [a] -> [(a,Int)] frequency xs = Map.assocs $ foldl f Map.empty xs where f m x = let m' = Map.insertWith (+) x 1 m Just v = Map.lookup x m' in seq v m' -- (~2.1 sec on a string of 700ko) Which is not as fast as the specialized version on string, but really faster and less restrictive than the second. Thanks everyone for all your answers ! Charles

3 2

REMINDER: Contributions to the HC&A Report (November 2005 edition)
by Andres Loeh 26 Oct '05

26 Oct '05

Dear Haskellers, the deadline for the November 2006 edition of the Haskell Communities and Activities Report is only a few days away -- but this is still enough time to make sure that the report contains a section on *your* project, on the interesting stuff that you've been doing; using or affecting Haskell in some way. Many projects that have been included in former reports have not yet updated their entries. Please have a look at http://haskell.org/communities/topics.html and at the May 2005 edition for reference. * Has your project been listed in previous Reports, but is not yet updated? Please write a short update! * Are you no longer working on a project that was included in the Report? Write up what you are working on instead, and tell me if someone else has picked up the project. * Is some project you have heard about not included in any previous Report? Please let me know ... There is still time to write a completely new entry, on a new compiler, tool, library, company, user group, idea, ... -- as long as there is a connection to the Haskell language, there is a place for it in the Report! Submissions are due by next Tuesday, that is Tuesday, 01 November 2005. Please mail your entries to <hcar at haskell dot org>, in plain text or pseudo-(La)TeX format. More information can be found in the original Call for Contributions at http://www.haskell.org/pipermail/haskell/2005-October/016575.html I look forward to receiving your contributions. Thanks a lot, Andres (current editor) -- Haskell Communities and Activities Report (http://haskell.org/communities) 11/2005 edition submission deadline: 01 November 2005 <hcar(a)haskell.org>

1 0

lockFile: fd out of range
by Joel Reymont 26 Oct '05

26 Oct '05

Folks, Is there a set limit on the number of file descriptors that a Haskell program can open? I'm using hs-plugins on FreeBSD to transparently compile, load and launch scripts that establish a connection to a server. I'm getting this error: internal error: lockFile: fd out of range Please report this as a bug to glasgow-haskell-bugs(a)haskell.org, or http://www.sourceforge.net/projects/ghc/ Thanks, Joel -- http://wagerlabs.com/

1 0

Re: Nice way to calculate character frequency in a string
by Scherrer, Chad 25 Oct '05

25 Oct '05

> Hello, I need to calculate the frequency of each character in a > String. And if I can do this really well in C, I don't find a nice (and > fast) answer in haskell. I tried several functions, listed below, and > even the fastest do a lot of unnecessary things : A while back, I was trying to build a "table" function similar to what you describe, and Dean Herrington helped me speed it up and stop the stack overflows I had been getting. Here it is, in case this is useful to you... table :: (Ord a) => [a] -> [(a,Int)] table xs = Map.assocs $! foldl' f Map.empty xs where f m x = let m' = Map.insertWith (+) x 1 m Just v = Map.lookup x m' in v `seq` m' I would be interested in whether this is much slower than the other approaches you've tried. If a faster approach could be made polymorphic, I'd have a faster way to build tables! Chad Scherrer Computational Mathematics Group Pacific Northwest National Laboratory "Time flies like an arrow; fruit flies like a banana." -- Groucho Marx

1 0

RE: [Haskell-cafe] Nice way to calculate character frequency inastring
by Simon Peyton-Jones 25 Oct '05

25 Oct '05

| > Better still, help us make it faster! | > | > Simon | | What can your average Haskell user do to help other than | point out things they don't like? Well-characterised test cases are always motivating: small programs that should go fast, and don't. Why does the brain-twisting version work fast, and the obvious code go slow. Ian Lynagh's recent message was a good example [although I'm afraid we have still not done anything about it] http://urchin.earth.li/~ian/bench/bench-0.2/ghc-6.4.1.html. The next step is to look at the intermediate code that GHC produces, and try to see what's different about the good and bad version. Sometimes, as Simon M's recent message mentioned, there are things that aren't easy to change, like auto-unboxing of arrays. Other times there are just missing SPECIALISE pragmas and the like. The more the problem is characterised, the more likely we are to do something about it. Simon

1 0

Re: [Haskell-cafe] Nice way to calculate character frequency in a string
by Jon Fairbairn 25 Oct '05

25 Oct '05

On 2005-10-25 at 13:42+0200 "Charles SDudu" wrote: > > okay, it took me some time to make your solution work, but it's as fast as > the precedent solution, and really more elegant. Thank you, but I dont know > how to structure the function, see yourself : > > calc str = filter (\p -> snd p > 0) $ assocs $ ((accumArray (+) 0 (toEnum 0, > toEnum 255) (map (\x->(x,1)) str)) :: UArray Char Int) > > It's not so nice but it works, isn't there a solution to put the type > elsewhere, and another type than UArray ? Well, you can do this: import Array calc::String->[(Char, Int)] calc = filter (\p-> snd p > 0) . assocs . accumArray (+) 0 (minBound, maxBound) . (map (\x->(x,1))) You can import whatever sort of array you want, so long as it has assocs and accumArray. You don't want to change minBound and maxBound to toEnum x, since they are the bounds of Char, which might or might not be 0 and 255. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk

2 1

RE: [Haskell-cafe] Nice way to calculate character frequency in astring
by Simon Marlow 25 Oct '05

25 Oct '05

On 25 October 2005 11:59, Jon Fairbairn wrote: > On 2005-10-25 at 12:20+0200 Lemmih wrote: >> On 10/25/05, Charles SDudu <iwin_1(a)hotmail.com> wrote: >>> Hello, I need to calculate the frequency of each >>> character in a String. And if I can do this really well >>> in C, I dont find a nice (and fast) answer in haskell. I >>> tried several functions, listed below, and even the >>> fastest do a lot of unnecessary things : >>> >>> calc :: String -> [ (Char, Int) ] >>> calc = filter (\p -> snd p > 0) . assocs . >>> foldl (\k c -> unsafeReplace k [(fromEnum c, >>> (unsafeAt k (fromEnum c))+1)] ) k where k = array >>> (toEnum 0, toEnum 255) [(toEnum i, 0) | i <- [0 .. 255]] >>>>> UArray Char Int > > [snip even more disagreable code] > > Ugh! These are all horrid. If something on the lines of > >> calc = accumArray (+) 0 (minBound, maxBound) . (map (\x->(x,1))) > > isn't fast enough, complain to the implementors! What's the > point of functional programming if one has to twist into a > shape that allows inspection of one's own fundament to get > stuff to run in decent time? To make that go fast, you'd want to use a UArray. Could the compiler figure this out for itself? Not really, it might be able to figure out certain special cases where changing an Array to a UArray doesn't affect the semantics, but not in general (and GHC certainly makes no attempt to do it). Sometimes, you just need to give the compiler a bit of help. And you really want to read the file as a packed string, not a String. Or hope that GHC manages to deforest calc with whatever is generating the String. It's possible that calc deforests, but highly unlikely that hGetContents does, so I'm afraid you'll have to do the packed string conversion yourself. To make it go even faster, you need to inline & specialise accumArray. I'm not sure how much of this GHC currently does. Cheers, Simon

1 0

RE: [Haskell-cafe] Nice way to calculate character frequency in astring
by Simon Peyton-Jones 25 Oct '05

25 Oct '05

| Ugh! These are all horrid. If something on the lines of | | > calc = accumArray (+) 0 (minBound, maxBound) . (map (\x->(x,1))) | | isn't fast enough, complain to the implementors! What's the | point of functional programming if one has to twist into a | shape that allows inspection of one's own fundament to get | stuff to run in decent time? I agree. Better still, help us make it faster! Simon

2 1

RE: [Haskell-cafe] Safe FFI calls, -threaded and killThread
by Simon Marlow 25 Oct '05

25 Oct '05

On 25 October 2005 09:07, Einar Karttunen wrote: > I noticed that killThread in GHC behaves in a problematic fashion with > -threaded when the killed thread is in a midle of performing a safe > FFI call. If the behaviour (blocking until the call is done) is > intended adding documentation might be nice. > > The example below demonstrates the problem. Tthe program gets stuck > in the killThread call which is not very intuitive. Wrapping every > killThread in forkIO does not sound very nice either. > > - Einar Karttunen > > import Control.Concurrent > import Foreign.C > > foreign import ccall threadsafe "sleep" sleep :: CInt -> IO CInt > > main = do mv <- newEmptyMVar > tid <- forkIO $ sleep 100 >> putMVar mv () > threadDelay 10000 > e <- isEmptyMVar mv > if e then do putStrLn "killing sleeper" > killThread tid > putStrLn "done" > else do putStrLn "sleeper already done" This is correct, I'll document the behaviour. killThread/throwTo is currently synchronous - that is, it blocks until the exception has been delivered to the target thread (unlike the version in our PLDI paper which was non-blocking, IIRC). A non-blocking version can easily be constructed by using forkIO, as you noted. We can't kill a thread that is involved in a safe foreign call, because we have no control over the thread involved in the call. This is the really the only sensible behaviour. In the case of an unbound Haskell thread it would be possible to kill the Haskell thread while leaving the foreign call running, but this can't be done if the Haskell thread is bound (because the OS thread it is bound to is currently running foreign code). Cheers, Simon

1 0