[Hs-Generics] A Lightweight Implementation of Generics and Dynamics (LIGD)

[Bruno Oliveira]

Dear James, Ralf

As you might know, Johan proposed people related to the generic programming
community to gather and try to come up with a library for generic programming in Haskell.
The discussions are supposed to start this week with LIGD, which you two proposed.

Yesterday I sent an email to generics at haskell.org (our discussion mailing list) and 
gave a quick summary of your approach. I also proposed that we should collect code 
from the authors for the various approaches. You can see the original email at the end of 
the message. 

So, since we are now discussing LIGD, I was wondering if you have some code that 
you wouldn't mind to share with us. It won't be terribly hard for us to encode your 
paper (you even have a listing), but perhaps you have some extra code that didn't make 
it into the paper that would be interesting to discuss. For example, you mention at the end of 
LIGD that using a different representation type we could encode a generic map.

Also, perhaps you could comment about the use of LIGD as a basis for a generic 
programming library.

Regards,

Bruno Oliveira

On Tue, 03 Oct 2006 12:47:04 +0100, Bruno Oliveira wrote:

>Hello all,

>Johan mentioned in his last email that, starting from October 2nd (yesterday), we could
>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


>_______________________________________________
>Generics mailing list
>Generics at haskell.org
>http://www.haskell.org/mailman/listinfo/generics


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/generics/attachments/20061004/02ee8197/attachment-0001.htm