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

[Bruno Oliveira]

Hello,

Before any comments, just a reminder that there is an updated summary for LIGD
at the Haskell Wiki

http://www.haskell.org/haskellwiki/Libraries_and_tools/Generic_programming/Lightweight

where I merged some of Johan Jeuring and James Cheney previous comments in.

>> I'm trying to get these roles straight in my head. I think we're  
>> going to have a similar division for many of the library proposals.
>> 
>> A Generic library has several important components: the "framework"  
>> or way of representing a particular type, instances of this framework  
>> for the primitive types, helper functions for creating instances for  
>> new types, and a base set of generic operations/support code to get  
>> things started. The "Library writer" is responsible for all of these.
>> 
>> A user of the generic library may want to do two things:
>>   (a) define new type-indexed functions
>>   (b) ensure that their datatypes can be used with type-indexed  
>> functions
>> In Bruno's terminology,
>>   - Power User: does both of these
>>   - User: does (b) but not (a)
>>   - End User: does neither, just calls existing type-indexed  
>> functions on existing datatypes.

>I think that this is a good summary.

Right, I think this is useful too, I added this information to the template page:

http://www.haskell.org/haskellwiki/Libraries_and_tools/Generic_programming/Template

For now it is almost just a copy and paste from Stephanie's text in the template page. 
But I think eventually, we should create a separate page explaining this information about the users.

>> Note that we could imagine eliminating/automating (b) for some  
>> platforms with Template Haskell.

>Is this a statement specific to LIGD? Using Template Haskell would in
>my opinion be a good argument for Template Haskell itself, but not
>very practical, because I have the feeling that it is a relatively
>unstable (in the sense of interface changes) extension of the Haskell
>language. Also, it is definitely not going to be in Haskell', and it's
>use wouldn't really be optional, because TH-generated code can (as far
>as I know) so far not be exported and saved as a normal Haskell
>module.

>Using a tool like DrIFT would have the advantage that people not having
>that tool available could still make full use of generic programs.
>They'd just have more work.

Like Andres, I would also be reluctant in saying that TH is the best solution 
for b). DrIFT has the advantage that is not tied to GHC and I guess it is relatively stable.
Another alternative is that, provided that we come with some standart library to generic 
programming in Haskell, we can just propose some lightweight extension for 
eliminating/automating b). That's what happens already in SyB and Derivable Type Classes.

>> >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).
>> >
>> 
>> I think I prefer the term "Specializability" (even though it is more  
>> of a mouthful.) Generic
>> functions can be specialized at particular datatypes to specific  
>> operations.
>> (LIGD does not support this behavior, but could be extended to do so  
>> by pushing RepLib through the GADT translation.)

>The phrase "specialization" makes sense if you consider generic functions
>that in principle work on all data types, and now are trying to assign a
>new, specific behaviour to the function for one data type. But what if we
>have defined a function in the style of a generic programmign approach
>such as LIGD that does not have a catch-all case and does only work for
>a limited number of data types. That'd correspond to an ad-hoc overloaded
>functions. You might still want to extend such functions to new data types.
>And in this case, I think it's better to call the function "extensible" or
>"open".

Yes, I think I would associate "specialization" with a form of partial evaluation
that takes a generic function and produces a specialized function for a
specific type. This is not the same as adding an ad-hoc case to a generic function 
and using the same term for the two may lead to some confusion.

>> Aside: should we be developing a benchmark suite if we are actually  
>> going to be making decisions about performance? I don't want to guess  
>> here. Given that we will be collecting versions of several functions  
>> for each library, we should be able to run sort of "Library shootout".

>Yes, I think that would be a very good idea.

Right, this calls for a new Wiki page and perhaps some volunteer for 
the task. Anyone eager to collect generic functions/ develop 
performance cases and report those in the Wiki :)?

>> I also would like to know if there are some specific Haskell  
>> extensions that could dramatically improve performance. These  
>> extensions would not be portable, of course, but perhaps for specific  
>> platforms we could support optimized execution.

>Maybe RULES pragmas could help, but it would almost certainly also
>imply writing the conversion functions in a specific style.

>> >Expressibility:
>> >   - Can do both producer and consumer functions.
>> >   - Multiple representations needed for generic functions of  
>> >different
>> >     arities;
>> >   - No local redefinitions.
>> 
>> I think we should separate expressibility of the generic functions  
>> and expressibility wrt to what type information can index such  
>> functions.
>> 
>> For the former we talk about producer/consumer functions (read/show),  
>> functions of different arities (map,zip), functions defined by higher- 
>> order types (map, count, reduce), functions requiring type-indexed  
>> types (the zipper, bit-packed arrays, generalized tries).
>> 
>> For the latter, we talk about the ability to use the library with  
>> types that contain
>>   records
>>   nested datatypes
>>   higher-kinded types (what kinds?)
>>   datatypes with existential components (both of kind type and  
>> higher kinds)
>>   datatypes with first-class polymorphic components (both of kind  
>> type and higher kinds)
>>   above with class constraints
>>   GADTs (simple, and those that subsume existentials...)
>>   datatypes with higher-kinded type arguments

>Yes, that is a good idea as well. I will have another look at LIGD
>to find out how that fits in these categories.

Ok, would you like to report the results in the Wiki page? There is 
already a section for the subset of types covered. And I added Stephanie's
List to the template page.

Please feel free to edit the LIGD Wiki page and add your own comments. 

Cheers,

Bruno Oliveira