My summer of code project: HsJudy
Hey Haskell folks! I'm Caio Marcelo and my project for this Summer of Code is "Fast Mutable Collection Types for Haskell", I'll be implementing a lot of APIs for data collections (like Map and Arrays) using Judy library as backend. If you want to know more about it, take a look at my SoC blog at http://cmarcelo.blogspot.com. The repo is http://svn.openfoundry.org/pugs/third-party/HsJudy/. Comments, suggestions or ideas are all welcome. Thank you Haskell.org people for accepting my application! -- Caio Marcelo
Hello Caio, Tuesday, May 30, 2006, 5:29:46 AM, you wrote:
I'm Caio Marcelo and my project for this Summer of Code is "Fast Mutable Collection Types for Haskell", I'll be implementing a lot of APIs for data collections (like Map and Arrays) using Judy library as backend.
my comments to your README:
Design an API based on existing Haskell libraries. This involves studying the Haskell API and seeing which ones would have Judy-based support, good candidates are Map, IntSet and IntMap.
Judy implements _mutable_ array/map/set, so closest interfaces for your lib will be MArray and HashTable. DiffArray is a general way to make IArray (interface) on the base of MArray (interface), that is usable with any datastructure implementing MArray interface afaik, in orer to store Haskell objects in external datastructures, one should use StablePtr (see the module Foreign.StablePtr). i'm not sure that GHC will be efficient when working with large number of StablePtrs. of course, it will be not required for storing simple (unboxed) values, such as Int or Double. for further info about unboxed containers and immutable vs mutable containers read http://haskell.org/haskellwiki/Arrays you should also see to the Collections package: darcs get --partial http://darcs.haskell.org/packages/collections/ although it contains only _immutable_ datastructures at this moment. may be, you can codevelop with Bernardy interface for mutable maps/sets
all Haskell software that uses common data structures like Maps and Arrays would benefit from a faster implementation
sorry, i don't think so. especially for Arrays ;)
Some work[4] has already been done in Judy1 (mapping from words to bits)
Data.HashTable contains two hash functions. you can start with it and develop hashing class: class Hash a where hash :: a-> Int32 instance Hash String where hash = hashString
It's possible that no Haskell API matches some functionalities (like 'unbounded' Arrays);
this functionality is supported in my revision of Array libraries. i will inform you as i it will be published
If you want to know more about it, take a look at my SoC blog at
the Judy library itself: http://judy.sf.net http://mesh.dl.sourceforge.net/sourceforge/judy/Judy-1.0.3.tar.gz and last but not least :) feel free to ask us in the haskell-cafe and on IRC -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Bulat Ziganshin wrote:
the Judy library itself: http://judy.sf.net http://mesh.dl.sourceforge.net/sourceforge/judy/Judy-1.0.3.tar.gz
I wonder if the authors of the library could be persuaded to make it available under an Open Source license, because currently it is under the very limiting restrictions (ie incomaptible with commercial development and the "normal" Haskell library license) imposed by LGPL... Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com
"Brian Hulley" <brianh@metamilk.com> wrote:
I wonder if the authors of the library could be persuaded to make it available under an Open Source license, because currently it is under the very limiting restrictions imposed by LGPL...
You have a very non-standard definition of "Open Source", if the GPL and LGPL do not fit in, since those are classic Free Software licences! The Google SoC rules insist that all work produced under their programme be Open Source according to the OSI definition at http://www.opensource.org/
(ie incomaptible with commercial development and the "normal" Haskell library license)
I believe you are wrong. Both the GPL and the LGPL (more so the latter) are perfectly compatible with commercial development. Specifically, the GPL and BSD3 (as used by ghc) licences are compatible, in the sense that you can freely combine BSD3 code with GPL code. Plenty of people make money from closed-source projects that include LGPL'd components. If what you really mean by "open source" is the ability to take code and into make non-open modifications to it (as BSD permits), then that is far more demanding than what most people mean by the term. Regards, Malcolm
Malcolm Wallace wrote:
"Brian Hulley" <brianh@metamilk.com> wrote:
I wonder if the authors of the library could be persuaded to make it available under an Open Source license, because currently it is under the very limiting restrictions imposed by LGPL...
You have a very non-standard definition of "Open Source", if the GPL and LGPL do not fit in, since those are classic Free Software licences! The Google SoC rules insist that all work produced under their programme be Open Source according to the OSI definition at http://www.opensource.org/
(ie incomaptible with commercial development and the "normal" Haskell library license)
I believe you are wrong. Both the GPL and the LGPL (more so the latter) are perfectly compatible with commercial development. Specifically, the GPL and BSD3 (as used by ghc) licences are compatible, in the sense that you can freely combine BSD3 code with GPL code. Plenty of people make money from closed-source projects that include LGPL'd components.
If what you really mean by "open source" is the ability to take code and into make non-open modifications to it (as BSD permits), then that is far more demanding than what most people mean by the term.
Well the problem with LGPL afaiu is that if you statically link your code to it your are required to make your own source code available. If HsJudy would have a BSD licence but only the C Judy component had the LGPL licence, a possible solution for me afaiu would be to put the C Judy code into a DLL. This depends though on HsJudy itself being BSD (or something which allows you to statically link to it without having to disclose the source for the program you're statically linking to). I don't think (I may be wrong) that different bits of Haskell code (under GHC at least) can currently coexist happily in DLLs. Anyway I hope I didn't sound negative. I think it will be *great* to have mutable collection types in Haskell - I just get worried if something so important should have a restrictive licence attached. Good luck with the project, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com
On May 30, 2006, at 3:11 PM, Brian Hulley wrote:
Well the problem with LGPL afaiu is that if you statically link your code to it your are required to make your own source code available.
You could be confusing LGPL with GPL, I think. Or am I confused? Thanks, Joel -- http://wagerlabs.com/
Brian Hulley wrote:
Malcolm Wallace wrote:
"Brian Hulley" <brianh@metamilk.com> wrote:
If what you really mean by "open source" is the ability to take code and into make non-open modifications to it (as BSD permits), then that is far more demanding than what most people mean by the term.
Well the problem with LGPL afaiu is that if you statically link your code to it your are required to make your own source code available.
That is untrue. You never have to reveal your source code when your code uses an LGPL libary. If you modify the LGPL library source then you do have to release the modified library source under the LGPL -- but this does not mean you need to release the code that uses your modified library. http://www.gnu.org/licenses/lgpl.html "When a program is linked with a library, whether statically or using a shared library, the combination of the two is legally speaking a combined work, a derivative of the original library. The ordinary General Public License therefore permits such linking only if the entire combination fits its criteria of freedom. The Lesser General Public License permits more lax criteria for linking other code with the library." If you dynamically link then there is little to do, as the users can easily switch to a modified library. If you statically link you must supply object code (not source code): "If you link other code with the library, you must provide complete object files to the recipients, so that they can relink them with the library after making changes to the library and recompiling it. And you must show them these terms so they know their rights." So there is a difference in static vs dynamic linking -- with static linking you have to make (at least) your object code available. -- Chris
On Tue, 2006-05-30 at 14:16 +0100, Brian Hulley wrote:
Bulat Ziganshin wrote:
the Judy library itself: http://judy.sf.net http://mesh.dl.sourceforge.net/sourceforge/judy/Judy-1.0.3.tar.gz
I wonder if the authors of the library could be persuaded to make it available under an Open Source license, because currently it is under the very limiting restrictions (ie incomaptible with commercial development and the "normal" Haskell library license) imposed by LGPL...
I don't really want to get into a licensing war but I don't think this is really true. The LGPL is of course an open source licence. Plenty of proprietary code is developed on top of LGPL C libraries, for example everything that uses Gtk+ (like VMWare and Adobe PDF viewer). I know some people take issue with using the LGPL for Haskell libraries because of the linking problems. While it's easy to swap over a LGPL C .so module it's rather harder for Haskell since there's no stable ABI. However this is easy to overcome by adding an explicit exception. I've seen at least one LGPL Haskell lib include such an exception. Duncan
Duncan Coutts wrote:
I know some people take issue with using the LGPL for Haskell libraries because of the linking problems. While it's easy to swap over a LGPL C .so module it's rather harder for Haskell since there's no stable ABI. However this is easy to overcome by adding an explicit exception. I've seen at least one LGPL Haskell lib include such an exception.
Could someone put a sample LGPL exception on the wiki? It would be generally useful for those wanting to use the LGPL with Haskell code. Cheers, Simon
On Tue, May 30, 2006 at 04:23:51PM +0100, Simon Marlow wrote:
Duncan Coutts wrote:
I know some people take issue with using the LGPL for Haskell libraries because of the linking problems. While it's easy to swap over a LGPL C .so module it's rather harder for Haskell since there's no stable ABI. However this is easy to overcome by adding an explicit exception. I've seen at least one LGPL Haskell lib include such an exception.
Could someone put a sample LGPL exception on the wiki? It would be generally useful for those wanting to use the LGPL with Haskell code.
If the only thing included in hslibs is a 3BSD-style interface then we have no problem, the user of the software links against the version of libjudy installed on the system. I am the original author of the HsJudy bindings which I implemented for building very fast free variable sets in jhc. I considered making a stand-alone version that included the judy source, but decided it would be much nicer to just link against the libjudy installed on the system as it is a generally very useful library. John -- John Meacham - ⑆repetae.net⑆john⑈
Hello Haskellers, I am Jun Mukai, and my project for Google Summer of Code 2006 is HaskellNet: network related libraries for haskell. my blog for SoC can be read at http://sequence.complete.org/blog/111. The repository will be set up at darcs.haskell.org soon. I prepare another repository at http://www.city5.org/haskellprog/haskellnet/ tentatively. By now, it have only SMTP and POP3 library. Any comments are welcome. Best Regards, -- Jun Mukai mukai@jmuk.org
participants (10)
-
Brian Hulley -
Bulat Ziganshin -
Caio Marcelo -
Chris Kuklewicz -
Duncan Coutts -
Joel Reymont -
John Meacham -
Jun Mukai -
Malcolm Wallace -
Simon Marlow