Lambda the Ultimate

I'm new to Ltu, and according to the suggested protocol, am introducing myself.

Who am I? A married man, who is about to have his first child, a software engineer who writes primarily Java and C++ frameworks and applications for a living, and a human being who can't get enough of computing.

To kick off my new membership, I'd like to ask about peoples' thoughts on generic programming. Specifically, I've been thinking about the proposal for Java Generics and how it leaves me totally unsatisfied - which lead me to thinking about generic programming in the ummm... general sense.

I don't believe I had every thought deeply about what it is that constitues "generic programming", but I've come to the conclusion that it's the capability to invoke a single set of operations against multiple types - with the result that differing operations for differing types are carried out. Given this definition, I readily came to the conclusion that subtype polymorphism really is just a form of generic programming (that is, the commonly referred to "one interface - multiple implementations"). Subtype polymorphism is quite limited though - specifically by the fact that the generic code is only applicable to named types within a family tree. Which leads us to the more commonly referred to generic programming technique - parametric polymorphism. With the form of parametric polymorphism that I am most acquainted with, the generic code is capable of executing against types which are not part of the same type family tree. However, Java Generics implements bounded parametric polymorphism - a form of parametric polymorphism where the type constraint is bounded by the type family tree. I really don't see the point of implementing such a form of genericity as it seems to be essentially equivalent to subtype polymorphism - other than the fact that it eliminates a small amount of casting in user code. What do people who have experience with both bounded and unbounded parametric polymorphism think?

While considering all this, I began to wonder, is subtype polymorphism even necessary or desired, if parametric polymorphism is capable of achieving all of the same results and more? I wonder if perhaps there is a more elegant form of polymorphism that can replace both parametric and subtype polymorphism - maybe something that is the combination of both... What do others think? (Please let's keep the conversation limited to staticly typed languages, as I would like to avoid the inevitable flame posts about how Java sucks because Smalltalk's nonexistent static typing and non-subtyping conformance in dynamic typing allow you to write generic code).

I'll try to answer your real question tomorrow when I have more time. As LtU regulars now I am a GP fanatic.

Mean while let me welcome you, and assure you that we don't have flame wars on LtU. Indeed, our subject is prone to religious wars, but LtU discussions have always been professional and civilized.

Maybe it's because we all know generic programming rules

Note that GJ is only one approach to generic programming in a statically typed OOP language. Indeed, it is quite different than what you'd find in C++ or Ada:

One may contrast two styles of implementing generics, homogeneous and heterogeneous. The homogeneous style, exemplified by the generic idiom, replaces occurrences of the type parameter by the type Object. The heterogeneous style, exemplified by C++ and Ada, makes one copy of the class for each instantia- tion of the the type parameter. The GJ and Pizza com- pilers implement the homogeneous translation, while Agesen, Freund, and Mitchell [AFM97] propose having the class loader implement the heterogeneous translation. Other proposals utilize a mixture of homogeneous and heterogeneous techniques [CS98]. [Bracha et al OOPSLA 98]

Right - the homogeneous style of generics being effectively equivalent to subtype polymorphism, because it is incapable of generating anything but virtual calls - the generated code must effectively be the exact same for every type by the very definition of homogeneous. This gets deeper into my point about generics. Genericity is about different behavior for different types - this means generating different code for different types. The typical virtual dispatch mechanism implemented for subtype polymorphism allows the generated target code to remain homogeneous at the call site - at the expense of limiting the genericity of the user code. It's nice that that optimization can be made, but it shouldn't limit the expressiveness of our higher level languages.

> Other proposals utilize a mixture of homogeneous and heterogeneous techniques

After going back and re-reviewing some papers, I realized that this statement is referring to the systems which propose support for primitives through heterogeneous translation (primitive support being another sore point of Java Generics). Without some form of common syntax between primitives and Objects, (for example, operator overloading ala C++, primitive pseudo-methods ala PolyJ, or primitives as full-blown types ala IBM - http://makeashorterlink.com/?A52212203) this seems like a mixed bag.

But this point about mixed homogeneous and heterogeneous translation brings me back to my point about code generation. Perhaps the largest complaint about heterogeneous translations is that they can lead to code bloat. If a compiler/vm implementation were to use homogeneous translation where the instantiated types against a generic function/class are in the same family tree, and heterogeneous translation where the instantiated types are not, then it seems you would have the best of both worlds.

That depends upon what you mean. The casts are still present in the bytecode, so they are, in reality, being evaluated at run time.

On another topic, were my previous questions too mundane or naive? I was hoping to here some interesting discussion.

I think these issues are important, and not that naive. It's just that LtU is awfully quiet these days.

On another topic, were my previous questions too mundane or naive? I was hoping to here some interesting discussion.

The title of this discussion, "Self Introduction", made me think it was a link to a Self (the OO language) discussion and so I've only just got around to reading it! Sorry, I don't have anything to deep to say on this topic.

I've thought of a few things on genericity that might be interesting. The functional programming folk like to talk about parameteric and ad-hoc polymorphism. Haskell addresses ad-hoc polymorphism with type classes. I don't know much about them I've afraid. There is also the generic function approach. SICP has an excellent discussion in chapter 2.

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-17.html#%_sec_2.4