October 2006 - Generics

Sample code
by oleg＠pobox.com 03 Nov '06

03 Nov '06

Hello! I wonder if we should collect some example code and make it presentable. By that I mean there should be the classification of the example, brief description, and, mainly, sample test data and the expected results. And, of course, implementations for these examples in various generic programming approaches. Incidentally, the `expressibility' section in the library description can simply enumerate which examples the library can implement. _Some_ of the examples may become the part of the benchmarking suite (at this point I'm simply interested in what is possible). Here's what I have gleaned so far, from a couple of SYB papers and the code already in DARCS: generic show: essential type is t -> String [I say essential because there may be additional arguments, say, for type representation] Description: display the term; special processing for Strings, as opposed to general arrays. Category: closed Cartesian [sorry, couldn't resist] I mean, `consumer', reduce a generic term to a value of the fixed type, String. LIGD has the implementation; no test data though. generic size: essential type t -> Int Give the size of a term (in terms of data constructors). The user should be able to assign size matrix to specific data types (like strings). Category: consumer, reduce a generic term to a value of the fixed type, Int. SYB3 example, also used in Smash. I have test data and expected results (part of syb4.hs) This example is quite similar to gshow above; I personally prefer this over gshow, because the Show class already provides the latter, so it's hard to get excited over gshow. Salary Raise: essential type t -> t Transform a term (representing an `organization' or an XML document) into the term of the same type, but with different values of some primitive fields. Ralf's dream example, from SYB1. category: type-preserving transformer Variation: uniform transformation (raise everybody's salary by 10%); or the transformation should affect only specific parts of the term. Transformation can be context-independent (increment each float field by 10%) or context- (that is, traversal history) dependent (increment each float until the money runs out). Test data can be extracted from Ralf's web site. generic minimum: essential type t Provides the 'minimal' value of any term in the universe of discourse. category: pure producer Variation: functional term may or may not be handled. LIGD example. test data can be easily extracted from it. Replace all Ints with Floats in a term: essential type t -> t' where t' = f(t). category: transformer, to a term of a different type. The output type is the function of the input type. variation: replace all Ints with Floats and negate all booleans, in a single traversal (that is, `compose' multiple compatible processing steps) Smash example; test data are available in the syb4.hs generic equality: essential type t -> t -> Bool category: binary function over two generic arguments of the same type. Variation: try essential type t -> t' -> Bool Variation: permit the user supply their own comparison procedure for some data types Variation: local extensibility [as explained in Stefan Holdermans] LIGD example (including specific comparison of integers mod 2). Need test data though. something of the type t1 -> t2 -> t3 where t3 = f(t1, t2). Generalization of zip/zipWith. I have never seen that example. Obviously a lot is missing in the above -- in particular, good names for the examples, and the test data. And the idea how to organize the files with examples and test data within our DARCS repository. Stephanie Weirich wrote: > 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 I'd inline this dimension into each of the above example. But we need test data... Cheers, Oleg

8 10

HCAR
by Johan Jeuring 30 Oct '06

30 Oct '06

Dear generics-reader, I have produced a report on generic programming in Haskell for the HCAR in the first 10 versions of the HCAR. A new report is due next Monday. I'm on holidays until then, so I wonder if someone is willing to take over this (rather small) task from me? (Actually, having done it ten times, it is maybe a good time to hand it over to someone else anyway.) Thanks, Johan

1 0

Request for support letters
by Stephanie Weirich 27 Oct '06

27 Oct '06

Hi all, In a few weeks, I plan to send off a proposal for funding to help with the Generic library development. I intend to apply to a "research infrastructure" program designed to support projects that, though not specifically research themselves, will aid a community of researchers. As part of that proposal, I need to demonstrate that there is a community of researchers that is interested in the outcome: the best way to do that is to include a set of letters of support from community members. Can I get each of you to send me a short letter that describes your interest in this Generic library? (Why it is important, how you might use it in your own work, etc.) The letters don't have to be long, just a paragraph or two. Many short letters are much better than a few long ones. Please send the letters straight to me (via email) and I'll forward them with my proposal. Many thanks in advance, Stephanie

1 1

Scrap your boilerplate and Variants
by Bruno Oliveira 25 Oct '06

25 Oct '06

Hello, According to Johan timeline, we should have started discussing SyB last week. I was to busy last week, so I could not do much work on it, but this week I have some more available time so I have started summarizing SyB in: http://www.haskell.org/haskellwiki/Libraries_and_tools/Generic_programming/… The summary is not complete, please feel free to edit it and add your own comments. I found it slightly awkard to fit SyB into the template because there are many papers and variants. I wonder if there is a better way to summarize SyB (perhaps splitting into the different variants?). Since SyB does actually have users and I guess some of them may have subscribed to this list, I guess this is the approach where they can comment the most and say what they like/don't like about SyB. For example they can comment about Error Messages, Usability and Performance. Other issues that they may be interested to comment on are on what do they use SyB for (what is the typical generic function that they write) and if they ever had a situation where they though of a function that should be generic, but it turned out that they could not encode it with SyB. More generally, I think it would be very good to collect opinions of users and not just people that do generic programming research. Cheers, Bruno Oliveira

3 5

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 24 Oct '06

24 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 11 Oct '06

11 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 09 Oct '06

09 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 09 Oct '06

09 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 09 Oct '06

09 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