The Artima Developer Community
Articles | News | Weblogs | Books | Forums
Artima Forums | Articles | Weblogs | Java Answers | News
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 7: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 | » ]
Frank Sommers

Posts: 2642
Nickname: fsommers
Registered: Jan, 2002

On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 15, 2007 1:00 PM
Reply to this message Reply
Advertisement
In this article, Thomas Becker combines generic and object-oriented programming to create a type-safe, heterogeneous iterator: any_iterator:

http://www.artima.com/cppsource/type_erasure.html

What do you think of the author's any_iterator?


Liu WeiPeng

Posts: 4
Nickname: pongba
Registered: Mar, 2005

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 15, 2007 8:28 PM
Reply to this message Reply
How do you ensure binary compatibility across compile-unit boundary while using vtable as a type-erasure mechanism?
Are you assuming that the client code and the library code is using the same compiler? Because if they're not, there's no way this would work.

Besides, could the fake vtable idiom solve this problem across different compilers?

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 15, 2007 9:32 PM
Reply to this message Reply
The any_iterator is a class template that resides in a header file. You are not linking to a library when you use it. It's all plain old straightforward C++. There is no linker trickery going on here.

Liu WeiPeng

Posts: 4
Nickname: pongba
Registered: Mar, 2005

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 15, 2007 9:45 PM
Reply to this message Reply
What I meant was:

// in a lib
any_iterator<...> f() { ... }

// client code
void g()
{
any_iterator<...> iter = f();
int value = *iter;
}

assuming the lib and the client code are compiled using different compilers.

Would the above code work?

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 15, 2007 10:04 PM
Reply to this message Reply
I must admit that I have never tried to compile different parts of a program on different compilers, and I don't believe I would recommend for anybody to do that. What I can tell you is this: whatever problems you will encounter are not specific to the any_iterator class template. Take any one of the iterator adaptors in the Boost iterator library, such as boost::transform_iterator. These are class templates that are derived from boost:iterator_facade, just like the any_iterator. Whatever problems you may encounter with the any_iterator, you would encounter the same problem with boost::transform_iterator. There is nothing specific to my any_iterator class in this respect.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 5:57 AM
Reply to this message Reply
First of all, it's not type erasure, it's structural subtyping: the original type is wrapped into another type which presents a common interface to the world through a base class which is used by users of that code. No types are erased.

Secondly, it's so fundamental that I don't understand why 2 pages are needed for the presentation. You want to wrap something into something else? simple:

1) make an interface.
2) make a template implementation class which inherits from above interface.
3) make a wrapper for said interface with value semantics to use in the code.

Thirdly, I don't like iterators with indirect calls where they are not really needed. Iterating should be easy. This solution only accounts for the fact that C++ lacks anonymous functions and for_each can not be used as it was meant to be.

As for C++ concepts, yeah, they are nice (type classes for C++! yeah!), but the C++ world has more severe problems than that (lack of garbage collection, lack of anonymous functions, lack of type deduction for lvalues, lack of a good standard library etc). I guess the C++ committee folks choose to do whatever they like instead of what we need.

Sebastian Redl

Posts: 1
Nickname: cornedbee
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 11:00 AM
Reply to this message Reply
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.

Edd Dawson

Posts: 1
Nickname: edd
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 11:50 AM
Reply to this message Reply
Great article, Thomas. It was an easy read, despite the relatively advanced nature of the material.

You might recall that I emailed you a while back about a similar implementation I had come up with. In fact I just this moment discovered that my second follow-up is *still* sitting in my outbox for some reason, after many months of lying dormant! I sincerely apologise for this; it wasn't my intention to be rude.

For anyone that is interested, my opaque_iterator<> can be found here: http://www.mr-edd.co.uk/?page_id=43

It's much the same idea, but I designed it coming from a different direction, that of reducing the compile time dependencies associated with stuff like the boost iterator adaptors. Type-erasure was achieved almost as an unconscious by-product.

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 12:15 PM
Reply to this message Reply
>>
I got quite creative trying to implement is_iterator.
<<

I'm glad to hear that I am not the only one who banged his head against that one... :-]

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 12:19 PM
Reply to this message Reply
I really should have mentioned your work in the references to my article, Edd. Sorry I forgot! It is true that we're coming from somewhat different directions, but the connection is clearly there.

Roland Pibinger

Posts: 93
Nickname: rp123
Registered: Jan, 2006

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 4:10 PM
Reply to this message Reply
Goodness gracious, type erasure re-interpreted as object-oriented programming! Now I'm waiting for an article that proclaims void* as the new way to do polymorphism.

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 4:50 PM
Reply to this message Reply
My approach to type erasure in general and the any_iterator in particular was motivated mostly by problems that arose in practical, commercial software engineering. You can find a more stringent scientific explanation of the relationship between generic programming, object oriented programming, and type erasure in the article by Mat Marcus, Jaakko Jarvi, and Sean Parent on their poly library:

http://homepages.fh-regensburg.de/~mpool/mpool07/proceedings/5.pdf

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.

Shunsuke Sogame

Posts: 1
Nickname: shunsuke
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 8:46 PM
Reply to this message Reply
Hi,

Based on your early implementation, I've implemented my own any_iterator for a few years.
If interested, see any_range @ http://p-stade.sourceforge.net/oven/doc/html/index.html
any_iterator/range introduces recursive ranges.


Regards,

--
Shunsuke Sogame

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 9:22 PM
Reply to this message Reply
Thanks for the link. That seems like a good idea, to have an any_range based on the any_iterator. I was not aware of your work (it didn't occur to me to google for any_range), or else I would have mentioned it in my article.

Thomas Becker

Posts: 14
Nickname: tmbecker
Registered: Oct, 2007

Re: On the Tension Between Object-Oriented and Generic Programming in C++ Posted: Oct 16, 2007 11:09 PM
Reply to this message Reply
Ok, reply to myself:

>They have chosen not to use the term "type erasure" at
> all,

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." Perhaps the person who posted the root message to this thread was a victim of this misunderstanding when he likened type erasure to using void*. (See, no matter what someone says, there is always some value in it.) Hm, what would be a better term? How about NIRP, for "non-intrusive runtime polymorphism" :o)

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-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use