Lambda the Ultimate

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

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

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

Andrew

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

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

Thanks!

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

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

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.

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.

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.

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

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

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

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