Lambda the Ultimate

Patterns in Datatype-Generic Programming
started 8/23/2003; 2:18:17 PM - last post 8/25/2003; 4:20:54 AM

Ehud Lamm - Patterns in Datatype-Generic Programming

8/23/2003; 2:18:17 PM (reads: 1475, responses: 6)

Patterns in Datatype-Generic Programming

Jeremy Gibbons. Patterns in Datatype-Generic Programming. To appear in Declarative Programming in the Context of Object-Oriented Languages. Uppsala, 25th August 2003.

Generic programming consists of increasing the expressiveness of programs by allowing a wider variety of kinds of parameter than is usual. The most popular instance of this scheme is the C++ Standard Template Library. Datatype-generic programming is another instance, in which the parameters take the form of datatypes. We argue that datatype-generic programming is sufficient to express essentially all the genericity found in the Standard Template Library, and to capture the abstractions motivating many design patterns. Moreover, datatype-generic programming is a precisely-defined notion with a rigorous mathematical foundation, in contrast to generic programming in general and the C++ template mechanism in particular, and thereby offers the prospect of better static checking and a greater ability to reason about generic programs.

This paper lays the background for the Datatype Generic Programming (DGP) project funded by the UK's Engineering and Physical Sciences Research Council (a call for PhD candidates was circulated a few months back).

This line of work is closely related to my areas of interest, specifically abstraction mechanisms in programming languages.

DGP is essentialy an outgrowth of typeful programming of the variety found in Haskell. As such, it is likely to give rise to the same concerns people have with advanced (and static) type systems. Be that as it may, I am quite sure that moving towards more generic, while still logically sound, software artefacts is the right way to go.

Posted to Software-Eng by Ehud Lamm on 8/23/03; 2:23:22 PM

Ehud Lamm - Re: Patterns in Datatype-Generic Programming

8/24/2003; 3:01:32 AM (reads: 547, responses: 0)

Quote:

Alexander,in his foreword to Gabriel’s book, hopes that the software patterns movement will yield programs which make you gasp because of their beauty. We think that’s a goal worth aiming for, however optimistically. We have yet to see a meta-programming framework that supports beautiful programming (although we confess to being impressed by the intricate possibilities of template meta-programming demonstrated by [Alexandrescu]), but we have high hopes that datatype-generic programs could be breathtakingly beautiful.

Ehud Lamm - Re: Patterns in Datatype-Generic Programming

8/24/2003; 10:38:48 AM (reads: 513, responses: 0)

I wonder if the comparison with the STL is solely for PR purposes. The more I think of it the clearer it is that the approach is much more tightly related to high order programming. The relation to STL (and things like Ada's generic units etc.) really amounts to only two things, the shared goal of achieving more "generic" componenets, and the fundamental realization that parameterization is the way to approach the problem.

Vesa Karvonen - Re: Patterns in Datatype-Generic Programming

8/25/2003; 3:56:17 AM (reads: 463, responses: 1)

I wonder if the comparison with the STL is solely for PR purposes.

After reading the paper, I think that a more accurate title for the paper would be something like "A critique of C++ templates and STL". Discussion of the actual title of the paper "Datatype Generic Programming" seems very shallow to me. I was disappointed, because I was hoping that the paper would actually discuss it (e.g. define it formally and provide examples whose semantics would also be discussed thoroughly) so that I might have learned something new. The critique of STL and C++ templates also seemed like old news. I couldn't find any critique there that a really knowledgeable C++ expert wouldn't know already.

Ehud Lamm - Re: Patterns in Datatype-Generic Programming

8/25/2003; 3:59:17 AM (reads: 483, responses: 0)

I think the major point of the paper is to explain the background for the DGP project. It doesn't claim to provide any new insights.

Vesa Karvonen - Re: Patterns in Datatype-Generic Programming

8/25/2003; 4:12:24 AM (reads: 463, responses: 1)

Perhaps my expectations were too high due the claim that "[...] datatype-generic programming is a precisely-defined notion with a rigorous mathematical foundation [...]". At any rate, I'm looking forward to reading some more in depth papers on the subject.

Ehud Lamm - Re: Patterns in Datatype-Generic Programming

8/25/2003; 4:20:54 AM (reads: 478, responses: 0)

The work on Generic Haskell (see here for example) is a good place to start.

Then read about bananas etc.