The Artima Developer Community
Sponsored Link

Articles Forum
On the Tension Between Object-Oriented and Generic Programming in C++

32 replies on 3 pages. Most recent reply: Nov 27, 2007 10:35 AM by Eivind Eklund

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 32 replies on 3 pages [ « | 1 2 3 | » ]
Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 17, 2007 10:07 AM
Reply to this message Reply
Advertisement
> Type erasure is the C++ way of achieving structural
> subtyping. Given that C++ is a strongly typed language,
> having structural subtyping is anything but fundamental -
> in fact it is quite amazing that it works.
>
> As for the rest, blah, blah, blah.
>
>
>
>
>
> Anyway, I ran into the is_iterator trap a short time ago.
> Consider this overload set:
>
> template <typename T>
> data_holding_object<T> make_dho();
>
> template <typename Iterator>
> data_holding_object<
> typename std::iterator_traits<Iterator>::value_type
> >
> make_dho(Iterator first, Iterator last);
>
>
> Harmless, right? I want an empty dho, I create one using
> make_dho<int>() (the actual situation in my library is
> more complex; directly using the data_holding_object type
> is impractical). I want a pre-filled one, I create one
> using make_dho(v.begin(), v.end()).
>
> Well ... except that creating the overload set fails in
> GCC 4. (Haven't tested other compilers yet.)
> make_dho<int>() fails to compile.
> I got quite creative trying to implement is_iterator. I
> thought I had a solution that works using lazy_enable_if -
> only to realize that the enable_if simply failed always,
> not just for non-iterators.
>
>
>
> On the other hand, my type erasure in the same library
> works beautifully. Being able to write source<int> instead
> of a type that would fill 5 lines and have only a single
> virtual call per operation as overhead is really nice.

You mean something like this?


#include <iostream>
#include <list>
using namespace std;

template <class T> class dho {
public:
T m_data;

dho(const T &t = T()) : m_data(t) {
}

};

template <typename T> dho<T> make_dho() {
return dho<T>(T());
}

template <typename Iterator> dho<typename std::iterator_traits<Iterator>::value_type> make_dho(Iterator first, Iterator last) {
return dho<typename std::iterator_traits<Iterator>::value_type>();
}

int main() {
list<int> list1;
list1.push_back(1);
make_dho(list1.begin(), list1.end());
getchar();
return 0;
}


It compiles fine under msvc++ 8.0.

Raul Huertas

Posts: 1
Nickname: raulh39
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 17, 2007 3:46 PM
Reply to this message Reply
> I'm beginning to understand why some people are not happy
> with the term "type erasure." It does sound a bit like
> "making things typeless."

I have to agree with that.

> Hm, what would be a better term? How
> about NIRP, for "non-intrusive runtime polymorphism" :o)

How about External Polymorphism? (http://tinyurl.com/33lf7w (PDF))

I think that the pattern you describe is similar to that used in boost::shared_ptr. And Scott Meyers uses this term to refer to that pattern in "My Most Important C++ Aha! Moments...Ever" (http://tinyurl.com/fr9yj).

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 17, 2007 4:47 PM
Reply to this message Reply
> How about External Polymorphism?
> (http://tinyurl.com/33lf7w (PDF))

Thanks a lot for the link! It seems to me that these guys really deserve the credit for having pioneered the idea: the paper is dated 1996. What's interesting is that the motivation that they give for their work is very much practical. Confirms my belief that good patterns always come from solving practical engineering problems. The abstract point of view, as in "OO vs. generic programming," is important, but it comes later. And it is useful only if it remains grounded in applied engineering.

As for the terminology, I do like their "External Polymorphism." There is one little catch, though: back then, in 1996, the default meaning of the word "polymorphism" was "runtime polymorphism." It seems to me that that has changed. Nowadays, I believe we would have to add the qualification "runtime." That would make it

"External Runtime Polymorphism"

So now the choices are NIRP and ERP :-]

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 17, 2007 5:02 PM
Reply to this message Reply
Ok, another reply to myself:

One difference between the external polymorphism pattern of http://tinyurl.com/33lf7w and the more recent type erasure implementations along the lines of boost::any is this: the original external polymorphism pattern did not have the handle class on the outside. It was pretty much understood that you would work with pointers or references to the external base class. It seems to me that the idea of the handle class is a substantial addition to the pattern. Who deserves credit? Most likely Kevlin Henney, but I'm not sure.

Roland Pibinger

Posts: 93
Nickname: rp123
Registered: Jan, 2006

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 17, 2007 5:32 PM
Reply to this message Reply
> They have chosen not to use the term "type erasure" at
> all, but that's not something that we should argue about.
> Consensus on terminology is something that takes time to
> evolve.

I don't mean that type erasure is the same as 'void*'. In fact, templates and object-oriented programming are orthogonal in C++. Templates work with objects as smoothly as with values. There is no "Trouble with Object-Oriented and Generic Programming" (maybe Boost has troubles, but that's their problem). Just in the tradition of STL most template aficionados ignore object-oriented programming in favor of value oriented programming.

John Zabroski

Posts: 272
Nickname: zbo
Registered: Jan, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 20, 2007 2:28 AM
Reply to this message Reply
Just some punditry:

Type erasure can occur at any stage of the executable's life span. Compile-time type erasure results in unnecessary casts and a performance hit because the executable doesn't know that there is a more specific structural subtype that can be guaranteed through static type-checking.

Run-time type erasure is actually quite different. It examines how an object reference is used in a particular context: a particular Operating Scope guarantees an operational level responsibility.

void* is what is known as an opaque data type, which itself is a loaded term that could mean many things. However, the intuitive definition of opaque data type in this context is "delayed type declaration". A delayed type declaration can result in Impostor Types.

Also, any rub-against involving object-orientedness and generic programming is strictly the result of unsafe type features. Eric Allen touches upon this very lightly in Chapter 7, "The Rogue Tile", of Bug Patterns in Java. A version of this chapter is in the IBM developerWorks archive.

John Zabroski

Posts: 272
Nickname: zbo
Registered: Jan, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 20, 2007 5:52 AM
Reply to this message Reply
@Thomas Becker
@As for the terminology, I do like their "External Polymorphism." There is one little catch, though: back then, in 1996, the default meaning of the word "polymorphism" was "runtime polymorphism." It seems to me that that has changed. Nowadays, I believe we would have to add the qualification "runtime." That would make it "External Runtime Polymorphism"

Correct. Compile-time polymorphism is perfectly plausible and used to select at compile-time which function or data structure should be used, usually to reduce the overhead imposed by a vtable and calling a function by accessing it through the vtable.

I get the notion of "external" and "non-intrusive run-time", but these terms don't have suitable antonyms. What is internal polymorphism? What is intrusive run-time polymorphism? "External" and "non-intrusive run-time" both seem like frantic ontologies to describe something thoroughly analytical and inherent to object-oriented analysis.

Martin Fowler talks about a "Knowledge / Operational split" in his book Analysis Patterns, a concept which I have found to be very useful when figuring out what I want to say before figuring out how to say it. I googled "Knowledge / Operational split" (K/O split) a week ago but never got any results, so I am assuming it's not popular. In K/O Split, he breaks down responsibilities into knowledge-level and operational-level qualifications. I don't believe Martin Fowler ever intended for someone to use K/O split in a discussion on run-time polymorphism strategies, but it's an idea I'm passing along here.

Johan Nilsson

Posts: 3
Nickname: jnilsson
Registered: Mar, 2004

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 21, 2007 8:43 AM
Reply to this message Reply
How much work would it take to extend any_iterator to be able to iterate through e.g. a map's mapped_values?

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 26, 2007 5:08 PM
Reply to this message Reply
>>
How much work would it take to extend any_iterator to be able to iterate through e.g. a map's mapped_values?
<<

One could answer that with "none at all" or with "that's not the point." If you need an iterator that does something specific, you need to create that iterator. (In this case, you'd use some suitable combination of an STL iterator with Boost iterator adaptors). Once you have a "concrete" iterator, you can assign it to suitable instantiations of the any_iterator class template. The point of the any_iterator is to allow uniform runtime treatment of different types of concrete iterators. Creating those concrete iterators in the first place is completely independent of the existence of the any_iterator.

Johan Nilsson

Posts: 3
Nickname: jnilsson
Registered: Mar, 2004

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 29, 2007 4:49 AM
Reply to this message Reply
> >>
> How much work would it take to extend any_iterator to be
> able to iterate through e.g. a map's mapped_values?
> <<
>
> One could answer that with "none at all" or with "that's
> not the point."

Which could imply a studid question ... I probably browsed through the article too quick.

[snip]

> Creating those concrete iterators in the first place is
> completely independent of the existence of the
> any_iterator.

So any_iterator could perhaps then be a valuable higher-level addition to the Boost.Iterator library instead?

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 30, 2007 2:02 PM
Reply to this message Reply
> So any_iterator could perhaps then be a valuable
> higher-level addition to the Boost.Iterator library

In principle, yes. At this point, however, it is not clear to me if there is enough interest in iterator type erasure. I personally believe very strongly in the usefulness of type erasure in modern C++ programming, especially as a way to reconcile generic and OO programming. I know that I'm not the only one, but I don't see widespread consensus on the issue.

Johan Nilsson

Posts: 3
Nickname: jnilsson
Registered: Mar, 2004

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 31, 2007 3:29 AM
Reply to this message Reply
> > So any_iterator could perhaps then be a valuable
> > higher-level addition to the Boost.Iterator library
>
> In principle, yes. At this point, however, it is not clear
> to me if there is enough interest in iterator type
> erasure. I personally believe very strongly in the
> usefulness of type erasure in modern C++ programming,
> especially as a way to reconcile generic and OO
> programming.

Right. I'm using a similar technique to be able to declare iterator support as part of e.g. abstract base class interfaces.

Antonio Vazquez Araujo

Posts: 1
Nickname: avaraujo
Registered: Nov, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Nov 15, 2007 7:36 AM
Reply to this message Reply
Sorry. I dont understand this.
Maybe is a typo.

class any
{
public:
any() : content(0) {}

template
any(ValueType const & value) : content(new holder(value)) {}
...

I think must be:
template < typename ValueType>
class any{
private:
placeholder* content;
public:
any()
:content(0){
}
any(ValueType const & value)
:content(new holder<ValueType>(value)){
...

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Nov 15, 2007 4:34 PM
Reply to this message Reply
Thanks for pointing this out! It's that old glitch again that happens when showing C++ code in HTML: Despite the fact that the code is enclosed in <pre> </pre>, the angle brackets are not treated as literals. If you look at the page source, you'll see

template<typename ValueType>

That is displayed as just

typename

To get the correct display, one must use < and > for the angle brackets.

The error is mine, I submitted it wrong. I'll email Frank Sommers and ask him to fix it.

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Nov 15, 2007 4:41 PM
Reply to this message Reply
> To get the correct display, one must use < and > for the
> angle brackets.

Ok, ha, ha, my post was displayed with HTML substitutions. What I meant was:

"To get the correct display, one must use & l t ; and & g t ; for the angle brackets, with the spaces removed."

Flat View: This topic has 32 replies on 3 pages [ « | 1  2  3 | » ]
Topic: Flex and JavaFX Previous Topic   Next Topic Topic: Java EE 6


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us