- Generics - Haskell.org

A Lightweight Implementation of Generics and Dynamics (LIGD)
by Bruno Oliveira 25 Oct '06

25 Oct '06

Hello all, Johan mentioned in his last email that, starting from October 2nd (yesterday), we could begin to discuss the different approaches to Generic Programming (GP). Since I have not seen any email concerning this I'll open the hostilities, which will hopefully sparkle some discussion. I provide my summary for LIGD in the end of this email, but before that I would like to discuss a few things: 1) While discussing the different approaches, we should also develop a "template" for reporting our conclusions. I think that having a base template will make our life easier. At the moment I am using the following: - Approach (Just the name of the approach) - Required features (What do we need) - Usage (how to use it, what different users do we have and what knowledge do they need) - Extensibility (is it extensible, if not can we do anything about it?) - Performance considerations (what are the performance impacts, is it possible to improve?) - Expressibility (what kind of generic functions can we write? producer and consumers? different arities? local redefinition?) - Boilerplate (what is the boilerplate involved, is it possible to remove it?) - Helpful extra features (what could Haskell have that would make the approach easier to use? Are those features realistically feasible?) - Discussion (General discussion, advantages/disadvantages, comparasion with other approaches) but note that this is not, by any means, supposed to be a proposal for the final template. It is just my initial template. We probably should discuss the template as we go along and tune it (if you think it is a good idea to have it in the first place). 2) Johan also mentioned a darcs/svn repository for the resulting paper/document. I think this is a great idea. Is anyone taking care of this? It would also be a good idea to use the repository to store some code for the different approaches. This way people who would like to experiment with code, would not have to repeat the task individually. What do you think? 3) Related to 2), we could start by collecting code for the approaches from the authors of the papers. I guess most of them are in this mailing list anyway. For example, we could now ask Ralf Hinze or James Cheney (either one of you two reading this email ?) if they some code available for LIGD that they could submit. We could then add this code to darcs/svn and do some experiments with it: organize it like a library, define generic functions, etc. If no code is available, perhaps we should find a volunteer that implements the code (if that's the case for LIGD I can volunteer for it). Here is my summary of LIGD, which is not complete but I think it can be a starting point. ======================================================================= Approach: A Lightweight Implementation of Generics and Dynamics Required features: - Haskell 98 + existential types Usage: - Library Writer: Responsible for the sums-of-products machinery, the representation(s) data type(s) to be defined in the library and defining the class and standard instances for "Representable". The library writer needs to be have a deep knowledge about generic programming. - Power User: Defines the boilerplate for new data types. Needs to be fairly familiar with the implementation. - User: defines generic functions by pattern matching on the structure of "Rep". This requires that he is comfortable with sums of products and isomorphisms. For convenience, the user should also provide a definition that uses the type class "Representable", which avoids the representations to be passed explicitly. - End User: If "Representable" is used, then the end can just use generic functions in the same way as any other ad-hoc (that is, type class overloaded) functions. Extensibility: - Data types are non-extensible, however we can try to combine the approach with type classes to get some form of extensibility (RepLib proposes one solution like this). Performance considerations: - Sums of products based and therefore involving considerable performance penalties. Expressibility: - Can do both producer and consumer functions. - Multiple representations needed for generic functions of different arities; - No local redefinitions. Boilerplate: - Isomorphisms between sums of products and data types - Instances of Representable - Smart constructors for representation of data types Helpful extra features: - GADTs (already implemented in GHC) allow more direct definitions of generic functions, since there is no need to apply the type coercions explicitly; - A boilerplate generation mechanism. This would effectively mean that power users would not be necessary. - Open data types and functions in order for extensibility. - Kind polymorphism, for eliminating the need for multiple representations; Discussion: An interesting approach which is quite lightweight and that is fairly easy to use (specially if we would not need to handle any of the boilerplate). It is a bit outdated because with GADTs, the use can be slightly simplified. However, this also takes us further away from Haskell 98 or even Haskell' (since GADTs will not be there). I think that LIGD is still a reference for a generic programming library that uses a data type for type representations and sums of products as a family of data types. A drawback may be performance, since we need to convert a data type into its isomorphic sum of products representation. ============================================================= Cheers, Bruno

9 15

patch applied (generics): Alternative implementation for SYB3.
by Oleg Kiselyov 25 Oct '06

25 Oct '06

Tue Oct 24 20:01:17 PDT 2006 oleg(a)okmij.org * Alternative implementation for SYB3. A ./SYB31/ A ./SYB31/dat1.hs A ./SYB31/dat2.hs

1 0

Wiki and summary for LIGD
by Bruno Oliveira 12 Oct '06

12 Oct '06

Hello, I've added an entry for Generic Programming in the Haskell wiki here: http://www.haskell.org/haskellwiki/Libraries_and_tools For now the main page does not have much but I hope that we can add more content. The summary for LIGD can be found here: http://www.haskell.org/haskellwiki/Libraries_and_tools/Generic_programming/… And I have also created a page with the template: http://www.haskell.org/haskellwiki/Libraries_and_tools/Generic_programming/… Feel free to fix/edit the pages. Cheers, Bruno Oliveira

1 0

www.haskell.org not very responsive
by Bruno Oliveira 10 Oct '06

10 Oct '06

Hello All, I am trying to edit the Wiki, but I am having trouble with www.haskell.org. It seems not to be very responsive. After many tries, I did manage to create a link in http://haskell.org/haskellwiki/Libraries_and_tools (and I think it is created as a sub-page as Manuel pointed out to me). I also created a "no contents yet page", which was not really intended to live longer than a few minutes. Unfortunatelly, because I am having problems accessing haskell.org, this page is actualling living for a while now ... Are you also having problems accessing haskell.org? Cheers, Bruno

2 1

patch applied (generics): Added LIGD and LIGD.examples
by chak＠cse.unsw.edu.au 10 Oct '06

10 Oct '06

Mon Oct 9 11:47:12 PDT 2006 Manuel M T Chakravarty <chak(a)cse.unsw.edu.au> * Added LIGD and LIGD.examples - LIGD is the code contributed by James Cheney - LIOGD.examples has been posted to the list by Johan Jeuring A ./LIGD/ A ./LIGD.examples/ A ./LIGD.examples/ComparingGP.lhs A ./LIGD.examples/XBitz.hs A ./LIGD/Dynamic.lhs A ./LIGD/DynamicLeibniz.lhs A ./LIGD/FoldRep.hs A ./LIGD/Lambda.hs A ./LIGD/MapRep.hs A ./LIGD/Nat.hs A ./LIGD/RepFn.lhs M ./README -1 +3

1 0

darcs repo
by Manuel M T Chakravarty 10 Oct '06

10 Oct '06

Hi folks, As discussed, I set up a darcs repository on haskell.org for us to put example code in. Anybody can obtain it by executing darcs get http://darcs.haskell.org/generics or if you have an existing account for the CVS/darcs repos at haskell.org, you can alternatively use darcs get darcs.haskell.org:/home/darcs/generics I have set up push messages to go to this list. We'll see whether that works in a moment when I push the LIGD code that was posted by James and Johan. There is also a README file with some comments re the directory structure of the repository. Darcs ~~~~~ If you are new to darcs, check out <http://darcs.net/>, where you can find binaries to download for a wide variety of architectures, a manual, and a wiki with lots of additional information. (For Fedora Core users, just execute "yum install darcs" as root - darcs is in Fedora Extras.) License ~~~~~~~ When looking at the source code, I noticed that it does not have any licencing information. If we want to develop a library that we expect end users to build applications with, it is absolutely crucial to properly licence the code. In particular, we must be very careful to not use any code from libraries that do not have an explicit licence (or a license that conflicts with whatever license terms we want for our end product). In addition, anybody who contributes patches needs to do that under the agreement that his or her code may be released under the licencing terms of the library that we develop. As we want to develop a sort of standard, I strongly suggest to use the New BSD Licence <http://opensource.org/licenses/bsd-license.php>, which is what GHC uses, too. It's called BSD3 in Cabal <http://www.haskell.org/ghc/docs/latest/html/libraries/Cabal/Distribution-Li…>. James, Johan, Ralf, would you mind to put your LIGD code under this license? If you agree, please just put a file called LICENSE with the license text (copy from above URL) into the LIGD/ and LIGD.examples/ directories in the darcs repo. Manuel

1 0

HaWiki and darcs
by Bruno Oliveira 06 Oct '06

06 Oct '06

Hello, Manuel has offered himself to take care of darcs repository for us. Since nobody replied I guess everyone is happy about that. Manuel: Would you like to go ahead and set up the repository? James Cheney already send some code that can go there. Regarding the wiki (sugested by Simon P. Jones) I can post the summary I sent previously if someone tells me how to create a new WikiPage :) I was playing around HaWiki and modifying pages is quite simple, but I could not figure out how to create a new page... I was also considering adding an entry to: http://haskell.org/hawiki/CommunityIssues linking to the new page -- something like "Generics: Discussion on a generic programming library for Haskell". Would this be an adequate location? Cheers, Bruno

2 1

Meeting at Haskell Workshop
by Johan Jeuring 25 Sep '06

25 Sep '06

Dear all, We've had a meeting discussing the next steps in developing a Common Library for Generic Programming at the Haskell Workshop. This email summarizes the main points. Furthermore, I have added some observations of my own, marked with [JJ:]. The main requirements for the library are ease of use and stability. [JJ: by stability we mean: we'll use the same API for a longer period; ease of use might mean different things to different people. I suppose we'll make the meaning of ease of use more clear while we go.] Furthermore, the library should be based on Haskell 98, + maybe commonly accepted extensions that we expect will end up in Haskell'. But we should be careful with using extensions for the Common library, the `purer' the better, from a standard point of view. We might take a levelled approach here: offer a library for Haskell 98, a library for Haskell' (if we know in time what that's going to be), and a library for Haskell'+addenda (if those are going to come). We want to start with finding out the weaknesses and strengths of the various approaches. Meanwhile we want to construct a set of examples with which we can illustrate the different characteristics of the approaches (gsize and functorial map were mentioned). [JJ: Andres Loeh, Ralf Hinze and I have written a paper about Comparing approaches to generic programming in Haskell, see http://www.cs.uu.nl/ research/techreps/UU-CS-2006-022.html. It does not discuss several of the candidate libraries. But it does give a nr of examples used for comparing the approaches, namely encode/decode, eq , functorial map, show, and update. Each of the examples illustrates different characteristics of generic programming. This might be a starting point for the examples.] Furthermore, we would also like to develop a benchmark (examples + desired input/output behaviour) which can be used to (also) benchmark performance. Hopefully we can extract several generic programming characteristics from the examples. It would be good to extract a document from the email discussion, in which we describe the comparison of the different approaches, and later the proposal for a Common library. Bruno Oliveira expressed an interest in helping, Johan is also willing to invest, and maybe others will want to join in as well. [JJ: I suppose we should set up a darcs or svn project for the document/paper?] [JJ: it might be nice to try to condense the final results in a research paper, a la Siek et al who compared generics a couple of years ago.] The next step is thus a discussion of the advantages and disadvantages of the different approaches. We want to have the discussion linearly through the approaches, focussing on one approach at a time (but of course other approaches may appear in the discussion as well). [JJ: what order should we take here? Chronological? That might make it a bit easier? - Light-weight Generics and Dynamics - SYB (including the Revolutions stuff?) - Generics for the Masses - Generics as a library - Smash your Boilerplate - RepLib - Extensible superclasses (WGP'06) - Almost compositional functions Did I include all proposals here? I think two weeks per proposal might be enough, on avarage? This would imply we are ready with the discussions by the beginning of next year. I'm on holidays for a couple of weeks in October, so I'll have a bit of a false start, but I suppose we should try to not let us distract by the absence of some of the people in the discussion. Of course, it is always possible to contribute about a particular method even if its assigned time slot has passed.] I propose to start the discussion next week, October 2, with Light- weight generic and dynamics, and from then on take the next paper on the list after two weeks. I'll also announce the initiative on the Haskell, generic-haskell, and dgp mailing lists this week. All the best, Johan

1 0

Common Generic Programming Library: Portland
by Johan Jeuring 13 Sep '06

13 Sep '06

Dear all, Thanks for all reactions and ideas. As you notice Andres Loeh has set up a mailing list. I will make a short announcement about the initiative to develop a Common Generic Programming Library at the Workshop on Generic Programming. I propose to meet in the last half hour of the lunch-break, so from 13:30-14:00 of the Haskell Workshop, in the room of the Haskell Workshop. [If this room is locked for some reason, I will either ask to unlock it, or we'll find a location nearby.] Hope to see you in Portland, Johan

1 0