Lambda the Ultimate

inactiveTopic Generic Programming
started 1/1/2001; 5:19:15 AM - last post 1/11/2001; 1:41:47 PM
Ehud Lamm - Generic Programming  blueArrow
1/1/2001; 5:19:15 AM (reads: 3195, responses: 17)
Generic Programming
This is a very good intro to the theory of generic programming. It is pretty dense (esp. after last night), coverring algebras, homomorphisms, isomporphisms, catamorphisms, functors, relations and other wonderfully sounding concepts. The explanations are quite good.

The paper discusses adding gnericity to Haskell in the context of the language PolyP.

Even if you are not theoretically inclined, the paper has some interesting examples.
Posted to theory by Ehud Lamm on 1/1/01; 5:19:52 AM

Ehud Lamm - Re: Generic Programming  blueArrow
1/3/2001; 8:38:58 AM (reads: 2536, responses: 0)
I find this subject very sexy, so I am a bit perplexed at the lack of responses. Is it because the link is to a long paper, beacuase the subject is theoretical, or because nobody around here is amzed at the power of generic programming?

While we are at it: Who's for more theory on the log?

Chris Rathman - Re: Generic Programming  blueArrow
1/3/2001; 2:29:17 PM (reads: 2527, responses: 0)
The longer papers (and theoretical ones) are fine but they do take a bit more time to digest. I'm printing the paper now as I still find it harder to work with digital than analog for the longer papers.

I'm all for a mixture of both theory and practice. :-)

andrew cooke - Re: Generic Programming  blueArrow
1/4/2001; 2:45:52 AM (reads: 2543, responses: 0)
Just got to this discussion via a route that might shed some light on theoretical posts...

Last night I was bored and too tired to do anything constructive, so I started reading the Demeter book (available in pdf from the Demeter site). I'd skimmed it before, but never grasped what adaptive programming was about (part of the problem, apart from my laziness, is that it's difficult to skim pdf files in the same way as compressed CO2 books). Anyway, I put in a bit more effort last night, found the appropriate chapters, and it all started to make a bit more sense.

So, this morning as I was working I started wondering how similar approaches could work with functional languages and, since I've recently been using ML, I Googled the web for a while and ended up searching for Functional ML and Polytypic references. That got me to the same page that this article referred to, reminded me of this post, and here I am.

Now that I have some motivation I'll sit down and read the paper.

Anyway, getting back to your question (I must hurry up - supposed to be working!):

- Theoretical papers are good when you are motivated to read them

- There's a lot of papers out there; finding one recommended here implies it is more likely to be useful (so keep up the good work)

- Posts with theoretical papers are "longer term" than fun discussions about syntax

- This site would be *much* improved by a search engine

- This site would be improved by a list of "recently updated discussions" so that comments on "old" posts aren't lost.

So theoretical posts are good. However, the site structure isn't one that supports long-term archiving or discussions.

Also, I suspect that the more frivolous articles attract more readers. Maybe it's worth putting up a poll? I'd suggest thinking carefully about the questions first, though.


andrew cooke - Re: Generic Programming  blueArrow
1/4/2001; 2:45:59 AM (reads: 2518, responses: 0)
Something odd seems to be happening - I just tried to edit my message and, apparently, posted a second time. Not sure if this will post a thrird time or simply alter my second message...


Ehud Lamm - Re: Generic Programming  blueArrow
1/4/2001; 3:36:13 AM (reads: 2504, responses: 0)
Re search engine:

Notice the search box on the left (btw: see the related logs at the bootom). The search isn't perfect but is pretty good. One thing to keep in mind: the results appear as the names of the top story of the day. So it may seem like the title is not appropriate for your request, but if you click and view the page you'll find the match.

I also noticed that google traversed the site, and many older postings can be found from there.

(One thing we can do, is have a page of links to 'interesting archived discussions', but then someone would have to admin that page..)

andrew cooke - Re: Generic Programming  blueArrow
1/4/2001; 4:29:45 AM (reads: 2522, responses: 0)
Notice the search box on the left

OK, I'm stupid stupid stupid. Or blind.


Ehud Lamm - Re: Generic Programming  blueArrow
1/4/2001; 6:51:24 AM (reads: 2503, responses: 0)
Welcome! I added the search box per your requests, so enjoy.

pixel - Re: Generic Programming  blueArrow
1/4/2001; 10:12:02 AM (reads: 2506, responses: 0)
# I'm all for a mixture of both theory and practice. :-)

Totally agreed. I've started reading the paper, but didn't find the time to go through it all yet...

Ehud Lamm - Re: Generic Programming  blueArrow
1/4/2001; 10:55:22 AM (reads: 2505, responses: 0)
The paper is indeed quite deep and technical, not to mention that it is pretty long...

I really liked the graph algorithms examples in the beginning. To me this kind of examples is really motivating.

Chris Rathman - Re: Generic Programming  blueArrow
1/4/2001; 12:42:50 PM (reads: 2523, responses: 0)
Having gone through the paper, I'm still not sure of the limitation of Haskell. I also breezed thru some of the info on Cayenne and PolyP hoping to get a handle.

From what I gather, Haskell gets it genericity via the use of classes. One of the examples given is the ability to create a map function that operates on both lists and trees. To me, the solution would be to create a class "mappable" that defines the interface for the functions and operations which must be defined for the specific instance. Hence, any data structure that wishes to be considered mappable must have an instance defining the mappable functions that apply to that data structure.

As far as I can tell, PolyP is aimed at providing a method to bypass a common Type (class) and use inference to draw the appropriate functions for the different kinds of classes. It appears that the approach is to relieve the definition of a common class and allow the genericity to apply across different classes of datatypes. It's almost as if the onus of constructing the common class is pushed off to the compiler instead of the programmer.

Then again, I could be completely wrong!!! :-)

One other note while were on the subject of generic programming. There are several different kinds of polymorphism. The type being discussed wrt Haskell is Parametric (Universal) Polymorphism (though the authors use the term PolyTypic programming). In the OO world there's also the type of polymorphism afforded through the use of subclassing (subtyping).

Parametric polymorphism seems to emphasize static type checking at compile time, whereas subclass polymorphism emphasizes dynamic type checking at run time. There is a facility in Hugs of existential types that can mimic runtime polymorphism, but I haven't had time to get my head around it.

andrew cooke - Re: Generic Programming  blueArrow
1/5/2001; 12:29:08 AM (reads: 2522, responses: 0)
I've only read a small part, but I think your understanding is correct (but with a strange emphasis on classes! ;-), but that things go a bit deeper.

First they are trying to exploit common features amongst types (which as you say is like implementing the types from the same base class, in an OO way of looking at things (I know nothing about Haskell - maybe it has some kind of OO ideas - but the polytypic argument seems to be a general one about types rather than classes)).

Second, they are hoping that this leads to a writing programs as follows:

- first, describe a generic process that operates on a generic data structure

- second, specialise that process to the case (process and data details) in question

The idea being that the high level process is separate from low-level details - the latter can be modified to allow the software to change over time without affecting the high-level functionality (and much of the maths is about proving that, as far as I can see).

For an OO-related look at the same thing you might like the Demeter book which helped me a lot (chapter 4 was good for me).

On the other hand, if the Demeter book is about something completely different then I have got things very mixed up and this post is completely incorrect! :-)

Oh, and finally, on the comment about different types of polymorphism - maybe this is equivalent to moving from early binding (static types) to mid-binding (at program generation time) (cf late-binding at run time). But perhaps that's pushing my luck too far.

Chris Rathman - Re: Generic Programming  blueArrow
1/5/2001; 6:27:45 PM (reads: 2518, responses: 0)
I've only read a small part, but I think your understanding is correct (but with a strange emphasis on classes! ;-), but that things go a bit deeper.
Given that when I spent some time with Haskell, I was trying to write the OO Shape polymorphism it's probably more than coincidence that I view it through that lense. :-)

In my defense, I should say that classes in Haskell are a different sort of beast than they are in the OO languages. In OO languages, classes define methods and state - being more an Abstract Data Type. In Haskell, classes define the kinds of operations that are applicable to a given type. A type in Haskell being an instance of a class.

A function can be called polymorphically if the data type supports a common set of operations. Any data type that is an instance of a class can be treated generically. In essence, the class of operations provides the mechanism for genericity as it currently exists in Haskell.

I haven't looked closely at PolyP or Cayenne but both of them compile into standard Haskell code. My assumption is that the two compilers make an inference about how to generate the necessary code to produce the glue for a common class definition for the functions.

Haskell was the first functional programming language that I studied. Unfortunately, I've looked at a lot of other languages in the interim, so my memory on Haskell is a bit fuzzy. What I'd like to see though is a clear cut example of where Haskell fails in it's genericity and a PolyP or Cayenne example that solves the problem. The paper alludes to some examples but they were not quite clear to me.

Given that both compile to Haskell, it would be interesting to see the results solved in both Haskell with multiple classes required and in the Polytypic languages.

While I'm on Haskell, I would like to say that the online material for the language is not nearly as good for introductory material as say for ML (could just be that ML is older and more mature). I thought that A Gentle Introduction to Haskell was neither gentle nor an introduction (though it really depends if you are familiar with another functional language - which I wasn't).

The most accessible online material I found was Two Dozen Short Lessons in Haskell though it is not so much a good read as it is a workbook to get acquanted with the language and concepts. I finally had to purchase Haskell: The Craft of Functional Programming which was about the right speed for me (slow and methodical).

Oh, and finally, on the comment about different types of polymorphism - maybe this is equivalent to moving from early binding (static types) to mid-binding (at program generation time) (cf late-binding at run time).
Haskell, Clean and ML seem to emphasize early binding. O'Caml though allows you to go either way, as it is a mixed model language.

Ehud Lamm - Re: Generic Programming  blueArrow
1/7/2001; 8:01:56 AM (reads: 2481, responses: 0)
Haskell type classes are also compiled by removing the type class information (and using an explicit dictionary). See Wadler's paper.

Type classes are akin to interfaces in some OO languages, but are merged nicely with type inference.

andrew cooke - Re: Generic Programming  blueArrow
1/7/2001; 12:34:39 PM (reads: 2478, responses: 0)
In Haskell, classes define the kinds of operations that are applicable to a given type.

Ah... Now that sounds so like what I thought the paper was saying that I suspect I've misunderstood it! If Haskell classes are first class then how is PolyP different from Haskell? (OK, I should read past the first couple of chapters - I stopped at the subscripts of subscripts (which, in their defense, they said weren't vital to understand)).

Ehud Lamm - Re: Generic Programming  blueArrow
1/8/2001; 12:26:03 PM (reads: 2471, responses: 0)
Type clases allow you to quantify over a set of types, as ooposed to quantify over all types. In this sense they are quite close to interfaces (not objects: they do not have state, nor do they need VTables).

However I don't think they are first class. Care to enlighten me?

Ehud Lamm - Re: Generic Programming  blueArrow
1/11/2001; 12:15:41 PM (reads: 2452, responses: 0)
More insight on category theory.

Chris Rathman - Re: Generic Programming  blueArrow
1/11/2001; 1:41:47 PM (reads: 2448, responses: 0)
Speaking of categorical programming, I've been meaning to take a look at the Charity programming language one of these days when I have the time (and my head is clear). Looks like an interesting language along these lines, though it is definitely not ready for prime time.