- Haskell - Haskell.org

Strictness of library implementations
by Ian Lynagh 12 Nov '01

12 Nov '01

The library report says The code found here is a specification, rather than an implementation. Implementations may choose more efficient versions of these functions. However, all properties of these specifications must be preserved, including strictness properties. Ratio then defines data (Integral a) => Ratio a = !a :% !a which GHC seems to implement as specified, but nhc and hugs seem to use data (Integral a) => Ratio a = a :% a Does this not have different strictness properties? Thanks Ian

2 1

ANNOUNCE: Haskell Communities and Activities Report (1st edition)
by C.Reinke 11 Nov '01

11 Nov '01

Dear fellow Haskellers, some six or seven weeks ago, I explained that we wanted to try and do something to help improve the communication between the various groups, projects, and individuals working on or with Haskell. A call went out to all of you to contribute brief summaries of your own area of work. I would collect then all these into a single report and feed it back to this very mailing list. True to the spirit of lazy evaluation, it took a long time to get everything done in the last two weeks, but now the project has finally taken form. The Haskell Communities and Activities Report (1st edition) is here! Or rather, not here.. Even though we didn't manage to convince every Haskell project to contribute a summary, it became clear very quickly that there was just too much going on to put it all into an unformatted ASCII email. So we put the information into a more report-like format (which doesn't mean it is formal;-). The report is available for download in PDF (with working links and index, yet printable) or, for those who have problems with the PDF, in HTML (using John's secret weapon, thanks) and Postscript, from the Haskell Communities home page: http://www.haskell.org/communities/ A big thanks here to everyone who contributed information to the report! I hope you will find it as interesting to read as we did. And when we'll try for an update in six months, you might want to add your own work, project, research area or group as well. Enjoy (and communicate;-)! Claus Reinke -- Computing Laboratory University of Kent at Canterbury http://www.cs.ukc.ac.uk/people/staff/cr3/

3 2

big picture on optimization
by Richard Uhtenwoldt 10 Nov '01

10 Nov '01

s

2 1

Haskell Communities - Inline .pdf problems
by C.Reinke＠ukc.ac.uk 09 Nov '01

09 Nov '01

Dear all, there seem to be some problems with displaying the .pdf file inline with IE and Acrobat plugin. I've got no idea why (any PDF experts here?-). The file seems to be okay, just save to disk and open (in fact, when you first save it to disk, the inline display has been seen to work properly immediately afterwards..). [I've tried optimising the PDF for web-display, but that seems to be even worse; I guess the file is just too long for inline viewing?-] Claus

1 0

RE: ANNOUNCE: Haskell Communities and Activities Report (1st edition)
by Simon Peyton-Jones 09 Nov '01

09 Nov '01

Thank you Claus! It makes pretty impressive reading, and I think it'll serve a useful role. Thank you for taking the time and effort to make it happen. Simon | The report is available for download in PDF (with working | links and index, yet printable) or, for those who have | problems with the PDF, in HTML (using John's secret weapon, | thanks) and Postscript, from the Haskell Communities home page: | http://www.haskell.org/communities/

1 0

Space faults in HaXml
by Joe English 08 Nov '01

08 Nov '01

Last week, Dmitry Astapov posted a message to haskell-cafe describing a HaXml program that was running out of memory on large inputs. I've done some investigation on this; here's what I've discovered so far: + The HaXml parser is overly eager; it doesn't produce a value until the entire input has been read. The heap profile for Dmitry's program shows heap usage climbing steadily up to a large peak as the document is being parsed, then a sharp drop as output begins, then climbs again as the output is produced. I suspect that this behaviour is typical of most HaXml programs. I replaced the parser with HXML (recently announced here); this flattens out the first peak, but the second one persists. (HXML uses an incremental parser -- instead of parsing a Document, it parses individual Events (start-tag, character data, end-tag, et cetera) and assembles them into a tree with a separate function.) + nhc98's heap profiler is fantastic. + Under nhc98 (v1.10), 'putStr' doesn't seem to like overly-long strings. This leads to trouble since the HaXml main driver uses a single call to 'hPutStrLn' to write the entire output document. Replacing this with 'mapM_ putChar' (or using GHC 5.02), fixes this problem, but the program still leaks. + The nhc98 heap profiler is amazingly useful. + HaXml uses the Hughes & Peyton Jones Pretty printer to format the output. This appears to have a slow leak. (Later tests show that the peak consists of "void" heap cells from the Pretty module, mostly suspended calls to Prelude.Int- and Prelude.Int+.) Figuring that it's overkill anyway I replaced it with a simpler serializer. + After this change there's *still* a space fault, which with the help of nhc's profiler (which, BTW, is great), I tracked down to the HaXml 'cat' combinator: cat :: [a -> [b]] -> (a -> [b]) cat fs = \e -> concat [f e | f <- fs] Earlier I had reported that rewriting Dmitry's test case to use the HXML internal representation directly instead of converting to HaXml's representation fixed the space leak. As it turns out, I didn't implement the 'cat' combinator, but instead used a binary concatenation operator: (+++) :: (a -> [b]) -> (a -> [b]) -> (a -> [b]) f +++ g = \x -> f x ++ g x and my implementation of mkElem had the signature mkElem :: String -> CFilter -> CFilter instead of HaXml's mkElem :: String -> [CFilter] -> CFilter. which uses 'cat' to process the second argument. Backporting this to HaXml: mkElem' name cf = \x -> [CElem (Elem h [] (cf x))] and modifying Dmitry's test case to use mkElem' and +++ instead of mkElem and cat finally fixes the problem. I'm still not sure *why* this does the trick -- hopefully somebody smarter can explain that -- but the modified program runs in bounded space, no matter how large the input file is. (It even works in Hugs, which I found surprising, since the HXML tree builder has a known problem when run with Hugs' garbage collector.) --Joe English jenglish(a)flightlab.com

1 1

penalty for proper tail recursion
by Jan-Willem Maessen 08 Nov '01

08 Nov '01

Richard Uhtenwoldt <greon(a)best.com> asks: > What is the penalty that compilers pay these days for allowing > "proper" tail-recursion (that does not grow the stack)? These days it's often little or none. Here's what I know from working very intensively on compiling (Eager) Haskell to GCC. 1) GCC has always done a fairly good job with self-tail-recursion. Oddly, I don't exploit this as I use a few tricks to do a tiny bit better. 2) GCC's latest version does a pretty good job with sibling call optimization (==tail-recursive calls to other C procedures). I've worked exclusively with gcc 3.0 prereleases for the past 9 months and it has simplified implementation tremendously. 3) Sibling call optimization is not infallible (yet?), a fact I discovered mainly by poring over the assembly code for portions of my run-time system. It seems to be good enough in practice, but there's a fallback mechanism in my implementation just in case. I use the same mechanism to handle various other more common conditions, though, so I didn't consider this a great burden in practice. It doesn't appear to actually kick in due to missed sibling call opportunities. 4) Writing your own GC means maintaining a "shadow stack": An explicit data structure which allows the pointers on the stack to be found. There are a number of ways of doing this, but all of them pretty much require that the *Haskell* compiler do the work of saving and restoring pointer variables around calls. This is a drawback of implementing precise garbage collection on top of C. Haskell compilers do enough allocation that conservative garbage collection isn't very attractive. I mention shadow stacks because they are the other (I would say dominant) source of overhead when compiling to C. It subverts register and frame slot allocation, two things the C compiler should do well. 5) In GCC, shadow stacks can be efficient to pull off---compile without a frame pointer, and declare a register global to hold the shadow stack pointer. Net change in number of available registers: none. But the loss in register/frame allocation is still annoying. I've stuck with an implementation that could be turned into bone-standard C99 code with a few days' work. The performance advantages of gcc (register globals, sibling call optimization, and per-procedure control over x86 calling conventions being the big ones) are such that I have no plans to put in the effort. I would get a working, but positively lousy, implementation. My understanding is that ghc -fvia-C also depends on GCC for properly tail-recursive output (otherwise they can use a trampoline as described in your message). They post-process the assembly code output in order to replace tail-recursive calls with jumps. This approach is less portable but reliably eliminates tail calls. The code is in GHC and wasn't hard to read when last I looked. Note that they *also* post-process the assembly code output to move info tables into the code segment. That code *is* a bit complicated, and messages over the years suggest that people looking for one trick often find themselves lost in the code for the other, as one program does them both. -Jan-Willem Maessen Eager Haskell project jmaessen(a)mit.edu

2 1

Re: Functional Metapost maintained?
by Olof Oberg 07 Nov '01

07 Nov '01

Ferenc Wagner wrote: > Hi, > > I got to know Haskell through Functional Metapost. Those > who use LaTeX and feel like programming some graphics in > Haskell, might have a look at this: > > http://tex.loria.fr/prod-graph/functional-metapost-latex.pdf > > Trying to use the package I had some problems with the > current Hugs and GHC, too. It seems like the version I have > is quite dated: it uses fromDouble, fromInt, fromRealFrac > etc. which GHC barks at. > > I made some modifications to have it compile, so that I can > use it know, but I still have a couple of problems that > should be washed out. But before I go for it, I'd like to > know if somebody have got a newer version, or somebody else > maintains it, or have some relevant information about that > package, or anything... On the Web I found nothing, really. I am interested in using FuncMP, so if you get it to work with a current GHC or Hugs.. Plain metapost is just too awkward to use when one wants to make more complex graphics, like 3D. I think Haskell might help there. /mill -- ############################################################# # S-mail: Olof Oberg # mill(a)pedgr571.sn.umu.se # # Pedagoggr. 7A # mill(a)ludd.luth.se # # S-907 30 Umea # tdv94oog(a)cs.umu.se # # Phone: 090-197395 # http://pedgr571.sn.umu.se/~mill # #############################################################

1 0

Non-monolithic version of 'sequence' for IO monad?
by Joe English 07 Nov '01

07 Nov '01

Is there any way, short of using unsafePerformIO, to implement a combinator f :: [IO a] -> IO [a] in a way that the the result is produced lazily? The problem with sequence :: (Monad m) => [m a] -> m [a] sequence = foldr (liftM2 (:)) (return []) where liftM2 f a b = do { a' <- a; b' <- b; return (f a' b') } is that it consumes the entire input before producing a result. Thanks for any advice, --Joe English jenglish(a)flightlab.com

5 7

subsequencing!
by Stephanie Randles 07 Nov '01

07 Nov '01

Hi, Im studying for an exam in Haskell program and for practice we have been given exercises to complete on our own. The answers have not been put up on the website either. So i was hoping for some help with this little program here. The idea is to be able to substitute the first occurrence of a given subsequence in a list with another subsequence. The problem im not sure how to compare the lists for equality. Here the is what i have so far..... substitute :: Eq a => [a] -> [a] -> [a] -> [a] substitute _ [] _ = [] substitute ys (x:xs) zs | ys == x = zs:xs | otherwise = x:substitute ys xs zs Any help would be greatly appreciated. Thanks Stephanie

2 1