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

[Johan Jeuring]

Thanks Bruno, for kicking off. I have had meetings all week, and  
worked on the
forthcoming release of Generic Haskell. I'll leave for holidays for  
two weeks
tomorrow, so I won't join the discussion until the week of October 23  
again.

> 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).

I definitely think it is a good idea to have such a template. I   
think you cover all relevant
aspects. I recently thought about such a template again, and also  
included:

- Subset of data types covered. Most proposals restrict the subset of  
data types on
which generic functions can be applied. The restrictions vary for the  
different proposals.

This is related to expressiveness, but different enough to warrant a  
special category, I think.

Furthermore, I called Boilerplate `Amount of work per data type', at  
least, that is what I think
you mean with boilerplate? The name boilerplate might be a bit  
confusing: what is the
boilerplate of SYB (nothing! of course (well, except for deriving  
Typeable), bust still, I
suppose you get my point).

Something I'd also like to look at is: what are the kind of type- 
error messages you get when
you make a mistake in your generic function? How `comprehensible' is  
the program (whatever
that means, and it probably means different things to different  
people)? At least size plays
a role here, but also other aspects. And is it easy to prove  
properties of generic programs?

Finally, I called required features portability, but there is  
something to say for both.

> 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?

Good idea. The darcs repository seems like a good idea. Manuel  
offered to creat one.

> 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).

Ralf implemented some function in LIGD for our comparing paper, I  
attach it to this message (together
with a file Xbits that is used somewhere; maybe there is a standard  
Haskell library for converting strings
into bits and vv? These should appear in the Darcs repository when it  
is there. Note that the code is better
viewed on paper then as code).
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ComparingGP.lhs
Type: application/octet-stream
Size: 20258 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/generics/attachments/20061005/d042cd2f/ComparingGP-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: XBitz.hs
Type: application/octet-stream
Size: 4761 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/generics/attachments/20061005/d042cd2f/XBitz-0001.obj
-------------- next part --------------

> ====================================================================== 
> =
> 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).

What do you mean with extensibility here? Not data types I assume.  
You mean that
LIGD functions are not extensible for new data types? This is a  
limitation of course.
Maybe a more severe limitation is that generic functions can only be  
defined on types
defined in Rep, we cannot add non-generic behaviour for particular  
data types.
Open data types will solve this, but these do not exist in any  
Haskell implementation.

> Performance considerations:
>    - Sums of products based and therefore involving considerable
>      performance penalties.

And types are passed at run-time, and interpreted.

Sums of products need not incur considerable performance penalties if
partial evaluators remove those intermediate layers. But we have to
experiment with behaviour here. Passing and interpreting types at run- 
time
is harder to avoid, I think.

> 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.
> =============================================================

I think LIGD is quite a nice library, that needs almost no Haskell  
extensions. But it
has its limitations.

-- Johan