- Glasgow-haskell-users

Re: Proposal: priority queues in containers
by Louis Wasserman 19 Mar '10

19 Mar '10

Oh, god, so much to respond to...heh. Submit this package for canonicalization as part of the Haskell Platform. I > would for one would support its inclusion. This is an option I seriously hadn't considered. To be fair, that's because I've never used the Platform myself, preferring rather to have the most up-to-date version of GHC at all times, heh. That said, while I'd be okay with this option, I'd prefer putting it into containers, because I feel like a canonical, reliable priority queue implementation is the sort of thing a self-respecting language ought to have built in. As does Python. In Python, though, the PQ implementation is not a built-in > class in the default namespace (as are dict and set). Rather, it is one of > the "batteries included" libraries that come with Python. I think that's the > right place for it in Haskell, too. I don't know Python, but according to Wikipedia, dict and set are built into the language. I don't think it's a fair comparison: set and dict in Python seem to have a role almost as ubiquitous as [] in Haskell, much more ubiquitous than e.g. Data.Set or Data.Map. I'm also not entirely sure that "batteries included" doesn't describe containers, given all the other packages that come with GHC. > * There is no distinction between keys and priority values. A utility > type > Prio p a with the instance Ord p => Ord (Prio p a) is exported to > allow > usage of distinct keys and priority values. I disagree with this one. It requires an Ord instance that isn't really an > ordering, and makes a Functor instance impossible. I would prefer an > interface separating keys and values like that of Data.Map (which would also > increase consistency within the package). I'd be okay with separating out a priority/value version. However, I'm still clueless as to what you're talking about with respect to Functor -- what's wrong with the following? data Prio p a = Prio p a instance Ord p => Ord (Prio p a) where ... instance Functor (Prio p) where fmap f (Prio p a) = Prio p (f a) I can understand if you're uncomfortable with (==) and (\ x y -> compare x y == EQ) being inequivalent, but neither the H98 Report nor the Prelude make any such claim, as far as I can tell. The Foldable instance breaks the abstraction. I think it should > process elements in order. I think that wanting to iterate over the priority queue in the middle of the computation, without caring about order, is a perfectly legitimate desire for a programmer! Moreover, the only way to make a Foldable instance process elements in order would be something like data Ord a => PQueue a = .... which I think is an awfully dirty approach. I'm not at all a fan of adding restrictions like that, not least because it adds lots of awkward overhead. Would you be okay with not exporting a Foldable instance at all, but still exporting a toList method which doesn't guarantee any ordering on the return list? My advice would be not to stress over whether priority queues go into > containers. It's not some pristine thing of beauty that deserves treatment > with velvet gloves. I'm...not sure how to respond to this claim. At least part of me wants to say, I genuinely do think the containers package is a piece of art...and then another part pipes up, "except for the inconsistencies between the various minView/maxView versions, and the little differences between IntMap and Map, and..." That said, I wouldn't be a fan of scrapping the style which the containers package has at least tried to create. I could be convinced that rewriting the rest of containers would be a good thing to do, though...and I might just want to do that myself. Hah. How does this implementation compare with using Map/Set as a > priority queue? Continuing the discussion of the benchmarks: first, Jim, it appears that I'm the one who made a n00b benchmarking error. TT_____TT That said, as you found, my implementation is still slightly faster when the benchmark is corrected. Some comments: - QuickBinom needs to have O(1) findMin for a reasonable comparison. I added that in the benchmark below, and here. - I can't think of any more optimizations for the sparse binomial heap -- I genuinely think it's not going to get better. - There is a way to optimize my implementation still further, but it makes my code much less readable. (Specifically, I start the BinomForest at Succ Zero, and unpack the first child of every node still in the forest. Modifying the whole implementation that way, though, makes it unreadably ugly...and I think QuickBinom is possibly already at that point. I started implementing it, and realized just how ugly it was, and I stopped, but I can finish it if I have to.) Sorting 500,000 elements, compiled with -O2, run with +RTS -H128m -K64m, with another few implementations thrown in for good measure: Times (ms) min mean +/-sd median max Pairing: 1440.090 1482.893 31.501 1482.093 1532.095 Binomial: 1356.084 1389.687 26.881 1388.087 1436.090 SBinomial: 1376.086 1422.489 48.453 1400.088 1520.095 Data.Set: 1712.107 1800.912 74.880 1782.111 1976.123 Skew: 1584.099 1644.503 85.702 1602.101 1848.116 Some other benchmarks<http://hackage.haskell.org/trac/ghc/attachment/ticket/3909/plot_2.png>were done by Milan Straka earlier, when we hadn't decided what heap implementation to use at all. His comments: > I think the pairing heaps are out of the question now. I would choose > between Binomial and Leftist. The Binomial have O(1) amortized inserts, but > beware, that this does not work in persistent setting -- the insert is O(log > N) when the heaps are used persistently (there are Skew Binomial Heaps with > O(1) insert in the persistent setting too). I vote for current (v5) Binomial implementation, even if the O(1) > amortized inserts works only non-persistently (ie. under heavy persistent > usage, leftist heaps might be a _little_ better). Conclusions: There aren't any differences in asymptotics, and as it stands, the existing implementation is just as fast. It's also a) done, and b) full of Haskellish type goodness. After about five hours' work (!!!) I *finally* managed to install Criterion yesterday, so I'll send out those tests ASAP. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

5 7

"static_wrapper" imports in the FFI
by Iavor Diatchki 18 Mar '10

18 Mar '10

Hello, I have implemented a small extension to the FFI which allows for "static_wrapper" imports. These are a variation on "wrapper" imports that do not use run-time code generation. This is important in security sensitive contexts because it avoids executable data. While "static_wrapper" imports are less general then "wrapper" imports, they can be used to install Haskell handlers in many C libraries where callbacks have an extra "user-data" parameter (e.g., GTK signal handlers). I have a darcs patch implementing the feature but I could not send it to the list because for some reason the patch is 150K long (!!! my changes are only ~50 lines) and the list has a 40K limit. What is the correct way to submit the patch, should I just commit it to the GHC tree? Here is an example, illustrating how "static_wrapper" imports work: foreign import ccall "static_wrapper" runHandler :: Int -> IO Bool This declaration will generate a C function that can call Haskell functions of the specified type. More concretely, the generated function has the following signature: HsBool runHandler(HsInt argument, HsStablePointer haskell_function); (i.e., given an integer and a pointer to a haskell closure of the correct type, we return a boolean computed by executing the closure). A common use case would be to install "runHandler" as the call-back in the C library, and pass the Haskell closure as the user-specified argument. By default, the closure argument is the last argument in the C function but, if necessary, this can be changed by using a type variable to indicate the position of the closure argument. For example, another way to write the previous example is: foreign import ccall "static_wrapper" runHandler :: Int -> closure -> IO Bool If in some C library the user-specified data is the second argument, then this is how we'd write the declaration: foreign import ccall "static_wrapper" runAnotherHandler :: Char -> closure -> Int -> IO Bool In addition to generating the C function, a "static_wrapper" declaration also imports the C function's address into Haskell, as if the programmer had written an import like this: -- First example foreign import ccall "&runHandler" runHandler :: FunPtr (Int -> StablePtr (Int -> IO Bool) -> IO Bool) -- Second example foreign import ccall "&runAnotherHandler" runAnotherHandler :: FunPtr (Int -> StablePtr (Int -> Char -> IO Bool) -> Char -> IO Bool) This address can be passed to the C library when installing the handler. I hope that you find this features useful! As usual, comments and feedback are most welcome. -Iavor

7 15

Feedback request: priority queues in containers
by Louis Wasserman 17 Mar '10

17 Mar '10

Hey, I'd like to request some more feedback on the proposed<http://hackage.haskell.org/trac/ghc/ticket/3909>implementation for priority queues in containers. Mostly, I feel like adding a new module to containers should be contentious, and there hasn't been as much griping or contention as I expected. The silence is feeling kind of eerie! I'm inclined to set a deadline of next Wednesday, Mar 24, because the ticket was started two weeks ago and the current implementation has been essentially unchanged for a week. After that point, I'll consider the patch final. The proposed implementation benchmarked competitively with every alternative implementation that we tested, and offers good asymptotics in nearly every operation. Specifically, we use a binomial heap, which offers - O(log n) worst-case union - O(log n) worst-case extract (this in particular was a key objective of ours) - amortized O(1), worst-case O(log n) insertion. (In a persistent context, the amortized performance bound does not necessarily hold.) This implementation seems to offer the best balance between practical performance and asymptotic behavior. Moreover, this implementation is extremely memory-efficient, resulting in better performance on large data sets. (See the ticket for benchmarks. The most accurate benchmarks are towards the end.) A couple potentially contentious design decisions: - There is no distinction between keys and priority values. A utility type Prio p a with the instance Ord p => Ord (Prio p a) is exported to allow usage of distinct keys and priority values. - Min-queues and max queues are separated the following way: - Data.PQueue.Min exports the type MinQueue. - Data.PQueue.Max exports the type MaxQueue. (This is implemented as a wrapper around MinQueue.) The method names are the same, but I think this is acceptable, because I can't think of any algorithms that use a min-queue and a max-queue separately. - Data.PQueue adds the alias type PQueue = MinQueue, so that the "default" behavior is a min-queue. These design decisions seem to be sufficient to handle most traditional uses for priority queues. In particular, this approach offers a superset of the functionality offered by Java's built-in priority queue implementation<http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html>, which makes the same design decisions, but of course, is all imperative and yucky! (Also, it offers inferior asymptotics, heh.) I made a particular effort to offer the sort of utility functions that are found in the other modules of containers. In particular, it offers: - take, takeWhile, span, and that whole family of functions. take k q returns the *list* of the top k elements, and drop k q returns the *queue* with the first k elements deleted. The rest of these methods have analogous signatures. - q !! k is equivalent to toAscList q !! k. - filter and partition are offered in O(n) time. (It's actually not obvious that my implementation actually runs in O(n) time, but I managed to prove it.) - We offer Functor, Foldable, and Traversable instances that do not respect key ordering. All are linear time, but Functor and Traversable in particular assume the function is monotonic. The Foldable instance is a good way to access the elements of the priority queue in an unordered fashion. (We also export mapMonotonic and traverseMonotonic, and encourage the use of those functions instead of the Functor or Traversable instances.) - We offer foldrAsc, foldrDesc, foldlAsc, and foldlDesc. (Descending-order operations are just implemented as duals of the ascending-order operations, for MinQueue. For MaxQueue, it's the other way around.) - Correspondingly, we export toList, toAscList, toDescList, fromList, fromAscList, fromDescList. (toList returns an *unordered* traversal, and is *not* equivalent to toAscList.) I'm really satisfied with the patch as-is, modulo maybe tinkering with the code style a little. I'm also working on an article for TMR on priority queues in Haskell, some of the different structures we considered, and particularly the new type-safety implementation I came up with for binomial heaps in the writing of this implementation. In conclusion, I want to be sure people actually like this approach! So check it out. Complaints are appreciated, but even "I think your implementation is absolutely perfect" would reassure me. =) Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

7 9

Re: Feedback request: priority queues in containers
by Louis Wasserman 17 Mar '10

17 Mar '10

Why not use Okasaki & Brodal's "Optimal Purely Functional Priority Queues"? They offer worst case: * O(1) union, findMin, and insert * O(lg n) deleteMin The primary reason that we don't use this implementation is, quoting from the paper you yourself linked to, > Our data structure is reasonably efficient in practice; > however, there are several competing data structures that, although > not asymptotically optimal, are somewhat faster than ours in practice. Hence, our work is primarily of theoretical interest. > The current implementation is considerably faster than Okasaki's implementation in practice, based on our benchmarks. Furthermore, the asymptotics are really pretty good, and the constant factors appear to be relatively low. I wrote a pretty efficient skew binomial heap implementation -- the first step of Okasaki's approach -- and found it was already slower than the optimized binomial heap. I'm not sure whether or not I uploaded that benchmark, though. I'll do that at some point today, just to keep everyone happy. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

3 4

Haskell Platform can't use OpenGL on OpenBSD.
by Thanos Tsouanas 17 Mar '10

17 Mar '10

Hello. I have successfully compiled ghc-6.10.4 on OpenBSD on i386. I have downloaded the Haskell Platform tarball, but ./configure fails: [ ... ] checking GL/gl.h usability... yes checking GL/gl.h presence... yes checking for GL/gl.h... yes checking for library containing glEnd... no configure: error: The OpenGL C library is required Looking into GL/gl.h, I see that the function glEnd is there: GLAPI void GLAPIENTRY glEnd( void ); My system's GL/gl.h seems to be v7.4: * Mesa 3-D graphics library * Version: 7.4 My config.log states the following, regarding OpenGL: [ ...lots of passed tests... ] configure:4247: checking GL/gl.h usability configure:4264: gcc -c -g -O2 -I/usr/X11R6/include -I/usr/local/include conftest.c >&5 configure:4271: $? = 0 configure:4285: result: yes configure:4289: checking GL/gl.h presence configure:4304: gcc -E -I/usr/X11R6/include -I/usr/local/include conftest.c configure:4311: $? = 0 configure:4325: result: yes configure:4353: checking for GL/gl.h configure:4360: result: yes configure:4373: checking for library containing glEnd configure:4414: gcc -o conftest -g -O2 -I/usr/X11R6/include -I/usr/local/include conftest.c -lz > &5 /tmp//ccanY01U.o(.text+0x12): In function `main': /home/thanos/third/haskell/platform-6.10.4/haskell-platform-2009.2.0.2/conftest.c:30: undefined ref erence to `glEnd' collect2: ld returned 1 exit status configure:4421: $? = 1 configure: failed program was: | /* confdefs.h. */ | #define PACKAGE_NAME "haskell-platform" | #define PACKAGE_TARNAME "haskell-platform" | #define PACKAGE_VERSION "2009.2.0.2" | #define PACKAGE_STRING "haskell-platform 2009.2.0.2" | #define PACKAGE_BUGREPORT "" | #define STDC_HEADERS 1 | #define HAVE_SYS_TYPES_H 1 | #define HAVE_SYS_STAT_H 1 | #define HAVE_STDLIB_H 1 | #define HAVE_STRING_H 1 | #define HAVE_MEMORY_H 1 | #define HAVE_STRINGS_H 1 | #define HAVE_INTTYPES_H 1 | #define HAVE_STDINT_H 1 | #define HAVE_UNISTD_H 1 | #define HAVE_LIBZ 1 | /* end confdefs.h. */ | | /* Override any GCC internal prototype to avoid an error. | Use char because int might match the return type of a GCC | builtin and then its argument prototype would still apply. */ | #ifdef __cplusplus | extern "C" | #endif | char glEnd (); | int | main () | { | return glEnd (); | ; | return 0; | } Now, I may not be a C programmer, but is this even supposed to work? Testing this program is weird: conftest.c:5: error: conflicting types for `glEnd' /usr/X11R6/include/GL/gl.h:957: error: previous declaration of `glEnd' Which was expected, since glEnd is defined to return void in GL/gl.h, so I tried to delete that function declaration from this .c file, and I got: conftest.c: In function `main': conftest.c:8: error: void value not ignored as it ought to be Ok, this was expected, so I tried to delete the "return" and I got this final error: /tmp//ccq1Rmj0.o(.text+0x19): In function `main': : undefined reference to `glEnd' collect2: ld returned 1 exit status Please let me know if you have any ideas on how to procede with the installation of Haskell Platform. Thanks in advance. -- Thanos Tsouanas http://mpla.math.uoa.gr/~thanos/

1 1

Strange GHC/STM behaviour
by Michael Lesniak 16 Mar '10

16 Mar '10

Hello, In one of my example programs I have a strange behaviour: it is a very simple taskpool using STM; in pseudocode it's 1. generate data structures 2. initialize data structures 3. fork threads 4. wait (using STM) until the pool is empty and all threads are finished 5. print a final message In very few cases, which depend on the number of threads spawned, the program hangs *after* the final message of step 5 has been printed. "Few cases" means, for example, 50.000 good, terminating runs before it hangs. If you increment the number of spawned threads (to a few hundred or thousands), it hangs much faster. Since forked threads terminate after the main thread terminates (which it should after printing the message), this behaviour is quite unexpected. Since I've experienced strange behaviour in the past which was the fault of my system configuration[1], I am a bit cautious before reporting a bug on GHC's bugtracker, especially since its reproduction is so difficult and random. So my question is how much circumspection is expected/needed before one should enter a bug in the bug tracker? I've tested the attached code on three different systems (with different linux systems, but always GHC 6.12.1 (since it's a bit costly to install the older versions)) and observed the mentioned behaviour. Is this enough to justify a bug report? Or, on the other hand, could someone spot the error in the attached code. Given my history with strange parallel behaviour, I am much more sure that it's the fault of my code, but I can't spot the error and the described behaviour (halting *after* the final message) is really strange. Addendum: Daniel Fischer could reproduce the problem and pointed out[2], that making the evaluation of the TVAR's value strict does not reproduce the behaviour. This is even stranger in this context; I don't see, how lazy evaluation can change the behaviour of my code. Cheers, Michael [1] http://www.haskell.org/pipermail/haskell-cafe/2010-March/073938.html [2] http://www.haskell.org/pipermail/haskell-cafe/2010-March/074520.html -- Dipl.-Inf. Michael C. Lesniak University of Kassel Programming Languages / Methodologies Research Group Department of Computer Science and Electrical Engineering Wilhelmshöher Allee 73 34121 Kassel Phone: +49-(0)561-804-6269

2 8

Documenting GHC
by Yitzchak Gale 16 Mar '10

16 Mar '10

In the thread "strictness of unused arguments", Max Bolingbroke wrote: > There is nothing *published* (Simon has a half-written one lying > around though)... > Unfortunately the weird behaviour you are seeing is due to... > one of the unpublished bits... There are various critical parts of the inner workings of GHC that are poorly understood outside of the GHC team. Strictness analysis and other optimizations, and the syntax and semantics of GHC Core, immediately come to my mind. There is much more. As a user of GHC, I would vote for a full two-month delay in the next release of GHC to allow the GHC team to devote two months of their time exclusively to writing documentation. Thanks, Yitz

3 2

Re: Proposed ghc-pkg and cabal feature - right list?
by Axel Simon 16 Mar '10

16 Mar '10

I'm replying to Simon M. and myself, as should have sent my first reply to the ghc users list, I guess. On 14.03.2010, at 10:54, Axel Simon wrote: > Hi Dan, > > I reply to libraries, I think that's the right list for Cabal. > > On 13.03.2010, at 21:39, Dan Knapp wrote: > >> There doesn't seem to be a mailing list for Cabal itself, so I'm >> posting here. I came up with an idea for a small feature that I >> believe would make a useful addition to ghc-pkg and Cabal. I'm >> willing to implement it myself, but I have had some previous >> experiences with other projects where I did some work and then the >> maintainers said "sorry, not interested", so I want to gauge interest >> before I start. Who should I talk to? >> >> The feature itself is this: Arbitrary key-value pairs in Cabal >> package files and the installed-package database. The use-case is >> for >> an application supporting plugins to discover installed plugins >> compatible with it, interrogating these fields through the GHC API. > > For Gtk2Hs I would like to have a similar feature. Gtk2Hs is a > wrapper for Gtk+. It evolves on its own (for which the package has a > version number) but it may wrap different versions of Gtk+. > I think people using Gtk2Hs need to be able to conditionally compile > certain code fragments, depending on which Gtk+ version Gtk2Hs > wraps. However, I had something simpler in mind than providing any > kind of key,value pairs: I would like to "export" certain Cabal > flags into the package, which could be as easy as specifying: > > Flag gtk_2_2 > Description: Build objects for Gtk+ version 2.2. > Exported: True > > Flag gtk_2_4 > Description: Build objects for Gtk+ version 2.4. > Exported: True > > Flag gtk_2_6 > Description: Build objects for Gtk+ version 2.6. > Exported: True > > where the 'Exported' would mean that this flag should be added to > the package data base. A package would then be > > gtk-0.10.4{gtk_2_2,gtk_2_4} > > if the first two flags would be set by Cabal. A package could then > depend on gtk-0.10.4 in which certain flags are set. Moreover, I > would then want cabal to compile a users package with -Dgtk_2_2 - > Dgtk_2_4 so the user can use CPP to conditionally compile code. > > You suggestion of using arbitrary key,value pairs is more general > and needs more thought. You would have to extend Cabal quite a bit > whereas my proposal is more lightweight in that it can build on top > of Cabal's Boolean flags. May I ask: > > - could you express your package properties using Boolean flags > (which are set by Cabal automatically)? > - if not, could you not express your plug-in concept using several > packages? > > Cheers, > Axel. > > >> For example, my content-management system FruitTart could enumerate >> the list of installed packages looking for packages which export a >> field "fruit-tart-plugin-interface-version" with a numeric value >> matching the interface version it's expecting. I'm not quite sure I understand the use case here. Are you saying you want to writing something within Cabal? Or do you want to use the Cabal API to find out if a certain package is available? If you're talking about dynamic plug-ins then I assume it must be the latter. Besides the technical difficulty of loading a GHC package dynamically (that I don't know anything about), what prevents you from looking for a package that contains just the plug in? On 15.03.2010, at 16:38, Simon Marlow wrote: >> > > My first thought was "hmm, there must be another way to do that", > but I can't think of one, or at least a good one. > > Perhaps having arbitrary key-value pairs in the package database > would be a good thing. It would help us to avoid breaking things > when we need to change the format, for one thing. We could start > using key-values for new fields rather than adding them to > InstalledPackageInfo. However, then we have a strange situation > where some fields get distinguished status in InstalledPackageInfo. > Of course, for some of those fields we have richer types (e.g. > License), so it makes sense. > > So for me, I can't see any serious objections to doing this, but I'd > also ask on the cabal-devel(a)haskell.org list (in particular we > should hear what Duncan Coutts thinks). Before implementing anything like general key,value pairs, I would like to see the exact usage of these fields? So Dan wants to query these dynamically using an API. I'm much more interested in having CPP macros defined so I can compile code conditionally. For this purpose, the key,value pairs are not necessarily suitable since Dan might want to define a pair that does not create a valid -Dkey=value instruction for CPP. Cheers, Axel.

1 0

Proposed ghc-pkg and cabal feature - right list?
by Dan Knapp 16 Mar '10

16 Mar '10

There doesn't seem to be a mailing list for Cabal itself, so I'm posting here. I came up with an idea for a small feature that I believe would make a useful addition to ghc-pkg and Cabal. I'm willing to implement it myself, but I have had some previous experiences with other projects where I did some work and then the maintainers said "sorry, not interested", so I want to gauge interest before I start. Who should I talk to? The feature itself is this: Arbitrary key-value pairs in Cabal package files and the installed-package database. The use-case is for an application supporting plugins to discover installed plugins compatible with it, interrogating these fields through the GHC API. For example, my content-management system FruitTart could enumerate the list of installed packages looking for packages which export a field "fruit-tart-plugin-interface-version" with a numeric value matching the interface version it's expecting. Once again, I'm not asking anyone to do this work for me - I'm eager to get my hands dirty and do it myself. I just want to find out what the process would be to get it accepted, once it works. Thanks in advance, -- Dan Knapp "An infallible method of conciliating a tiger is to allow oneself to be devoured." (Konrad Adenauer)

2 2

native threads vs. -threaded
by Donn Cave 15 Mar '10

15 Mar '10

I have been working on a Haskell interface to the platform API for Haiku (was BeOS.) It's C++, but the interesting thing at the moment is the use of threads - a UI window gets its own thread, and whatever Haskell code will be executed by callbacks from that thread. So it was surprising when this turned out to be incompatible with the -threaded link option. With that option, I get one callback from a non-main thread, and then that native thread will die, shortly after return from the callback. Results without -threaded are not really so good either (the application may run and work for a while, but inevitably fail with various errors that I suppose might be expected), so ... what do my threads need, to make -threaded work? The callbacks are `foreign "wrapper"' functions, which means rts_lock() is already getting called. It looks to me like that should work the same as if my thread had been invoked via forkOS, true? Is there anything else that I missed, that needs to be done to set the thread up for GHC? (I had been thinking this would not be a unique situation, rather there would be several other GUI toolkits out there that use threads in this obvious way, but after a brief review of the ones I usually hear about, not so sure. If there's another library that uses OS threads this way, with Haskell bindings already, that might be something I could steal a clue from.) thanks! Donn Cave, donn(a)avvanta.com

2 4