Lambda the Ultimate

Interactions of Abstractions in Programming
started 9/13/2002; 3:46:06 AM - last post 9/15/2002; 2:54:28 AM

Noel Welsh - Interactions of Abstractions in Programming

9/13/2002; 3:46:06 AM (reads: 1299, responses: 2)

Interactions of Abstractions in Programming

This paper describes an approach called generic programming (see also http://www.cs.utexas.edu/users/novak/autop.html) to reusable code components. The basic idea is to create generic algorithms, like iterate-accumulate that iterates over a collection accumulating a parameter (very similar to fold), and parameterise data by views, which are light-weight wrappers around data to provide the interfaces expected by the generic algorithms. One assembles a program by combining generic algorithms and views into appropriate combinations. The implementation then compiles the code to a target language (Lisp, C, etc.) using inlining and partial evaluation to remove the abstractions introduced at the generic level.

At first I thought this paper introduced nothing new. Generic programming is something anyone could do in a language that supports some notion of interfaces. Upon later reflection I've decided the generic programming system is useful in two ways: Firstly, it is useful to have a way to explicitly program in different levels (similar to DSLs). Secondly, having guaranteed compiler optimisations gives the freedom to program in a much more abstract style than one might normally.

The Future Work, particularly the idea of encoding constraints beyond those offered by current type systems, is quite interesting.
Posted to Software-Eng by Noel Welsh on 9/13/02; 3:47:56 AM

Anton van Straaten - Re: Interactions of Abstractions in Programming

9/13/2002; 1:29:27 PM (reads: 487, responses: 0)

Assuming we're talking about the same thing, the classic, and very successful, example of generic programming in the real world is the STL framework in C++, which was built on the C++ template mechanism. More recently, the Boost library extends this approach (see this survey of Generic Programming Techniques in Boost).

"The importance of the C++ Standard Template Library, STL, lies more in its concepts than in the actual code or the details of its interfaces" - David Musser. He's right, but in addition to that, the approach has proven itself in a lot of real-world code - it enables the use of high-level abstractions which retain a high degree of efficiency. (See the SGI page on STL for more info.)

My personal experience of generic programming in C++ is that it makes the language feel like a much more dynamic language than it "is", although I think a large part of this is simply due to the consistent use and application of interfaces, as Noel suggested. Most libraries and frameworks are not decomposed to the level which generic programming libraries tend to be. Good generic libraries are typically excellent examples of reusability and good component design, that can put the type systems of many languages to shame (in a practical sense at least - I don't know about the formal perspective).

One example shown on the Boost page linked above, is a generalized copy function that can copy elements in both arrays and linked lists, for example. Traditional naively-typed languages (new term :) don't let you do this kind of thing at a low level - although some really should, IMO. There's such a big focus on abstraction in the better computer languages, so why the heck can't we abstract the same concept (e.g. copying elements) over multiple data types, without having to jump through hoops?

One language to watch in this space is Goo. I don't know enough about it myself, and it doesn't help that it has a rather cryptic set of two-letter function names which makes it look a bit like a Lispy version of APL, without the greek characters...

Ehud Lamm - Re: Interactions of Abstractions in Programming

9/15/2002; 2:54:28 AM (reads: 440, responses: 0)

This seems similar to ideas I have been exploring.