November 2001 - Haskell

Here is a tiny idea for a QT based GUI library
by Eray Ozkural (exa) 13 Nov '01

13 Nov '01

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi people, In the past months I've seen a lot of interest in designing a standard GUI library for Haskell. I've just realized that a feature of QT 3.0[!] library, which is a well versed GUI library used in KDE, can make writing a GUI library quite easy. There is a class called QWidgetFactory[*] in QT 3.0 that enables application programmers to dynamically generate a GUI from a .ui file which is an XML file that describes it. If a functional combinator library would be able to generate the XML file in question then a GUI could be created quite easily. You also need to access objects in the created widget and implement slots for it, which I think should be possible using the C bindings. There are new C bindings for KDE and there ought to be some for QT as well. Are there any interested implementors? :) Happy hacking, [!] http://doc.trolltech.com/3.0/index.html [*] http://doc.trolltech.com/3.0/qwidgetfactory.html [+] http://doc.trolltech.com/3.0/designer-manual-5.html - -- Eray Ozkural (exa) <erayo(a)cs.bilkent.edu.tr> Comp. Sci. Dept., Bilkent University, Ankara www: http://www.cs.bilkent.edu.tr/~erayo GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE76/b4fAeuFodNU5wRArWAAJ9wN7qFa23Q4p2ZNWIFoXNV4yJwnwCfZBrJ 4MwQbRhI01ZBzfsQs2E41Ig= =zY7d -----END PGP SIGNATURE-----

2 2

Re: seq / strictness and laziness
by Hal Daume 12 Nov '01

12 Nov '01

Dean Herington wrote: > > `seq` forces evaluation of only the top-level construct in its first > argument. (($!) similarly for its second argument.) I would guess your > "newcounts" are structured (probably a tuple or list), in which case you are > not forcing evaluation deeply enough. See > http://haskell.org/pipermail/haskell/2001-August/001581.html and followup > article. As someone who also had this problem a while ago, I'm curious why DeepSeq never made it into the Libraries. This would, imo, be something quite generally useful (and it would be really nice to be able to derive it). - Hal

2 1

how strict is Array.array?
by Johannes Waldmann 12 Nov '01

12 Nov '01

I was surprised to note that bounds $ array (0,1) undefined is undefined ( rather than (0,1) ) - why is this? just curious, -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe(a)informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --

1 0

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 07 Nov '01

07 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