Lambda the Ultimate

A practical approach to generic programming
started 8/3/2002; 4:30:51 AM - last post 8/9/2002; 8:11:52 AM

Ehud Lamm - A practical approach to generic programming

8/3/2002; 4:30:51 AM (reads: 2548, responses: 3)

A practical approach to generic programming

Scrap your boilerplate: a practical approach to generic programming. Ralf Laemmel and Simon Peyton Jones. 12 pages, July 2002. Submitted to POPL 2003.

We describe a design pattern that for writing programs that traverse data structures built from rich mutually-recursive data types. Such programs often have a great deal of "boilerplate" code that simply walks the structure, hiding a small amount of "real" code that constitutes the reason for the traversal...

Our approach is simple to understand, reasonably efficient, and it handles all the data types found in conventional functional programming languages. It makes essential use of rank-2 polymorphism, an extension found in some implementations of Haskell.

For example, applying a function incS to all nodes of algebraic datatype Company, would look something like

increase :: Float -> Company -> Company
increase k = everywhere (mkT (incS k))

Section 9.3 compares the work presented with other techniques including polytypic programing, generalized folds and visitors.

Posted to functional by Ehud Lamm on 8/3/02; 4:31:25 AM

jon fernquest - Re: A practical approach to generic programming

8/5/2002; 8:47:18 AM (reads: 853, responses: 1)

> It makes essential use of rank-2 polymorphism,
>an extension found in some implementations of Haskell.

HUGS98 has it. Any others?

There's also a posting first-class polymorphism beats rank-2 polymorphism which implies they are substitutes.

Anyone know of any good explanations of this?

Ehud Lamm - Re: A practical approach to generic programming

8/5/2002; 9:51:04 AM (reads: 906, responses: 0)

Of what? Rank-2 polymorphism?

Ehud Lamm - Re: A practical approach to generic programming

8/9/2002; 8:11:52 AM (reads: 813, responses: 0)

The "design pattern" the paper advocates is basically a safe form of dynamic typing (or rather, dynamic casting). The idea is to apply the operation (e.g., incS) to all nodes, in such a way that nodes that are irrelevant are simply no-ops.

It is quite trivial to implement the same basic technique using OOP tools.

Of course, it's not obvious how to implement the pattern as a combinator, and adding a method to each class (which is the easiest OOP way to achieve what's needed here) results in the same issues Visitors have.