Article Discussion
On the Tension Between Object-Oriented and Generic Programming in C++
Summary: The author discusses how the use of generic programming in C++ can lead to conflicts with object-oriented design principles. He demonstrates how a technique known as type erasure can often be used to resolve these conflicts. An in-depth example is presented: any_iterator, a type-safe, heterogeneous C++ iterator.
32 posts.
The ability to add new comments in this discussion is temporarily disabled.
Most recent reply: November 27, 2007 7:35 AM by Eivind
    Frank
     
    Posts: 135 / Nickname: fsommers / Registered: January 19, 2002 7:24 AM
    On the Tension Between Object-Oriented and Generic Programming in C++
    October 15, 2007 0:00 PM      
    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
       
      Posts: 4 / Nickname: pongba / Registered: March 6, 2005 11:46 PM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      October 15, 2007 7:28 PM      
      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
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        October 15, 2007 8:32 PM      
        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
           
          Posts: 4 / Nickname: pongba / Registered: March 6, 2005 11:46 PM
          Re: On the Tension Between Object-Oriented and Generic Programming in C++
          October 15, 2007 8:45 PM      
          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
             
            Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
            Re: On the Tension Between Object-Oriented and Generic Programming in C++
            October 15, 2007 9:04 PM      
            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
       
      Posts: 98 / Nickname: achilleas / Registered: February 3, 2005 2:57 AM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      October 16, 2007 4:57 AM      
      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.
    • Edd
       
      Posts: 1 / Nickname: edd / Registered: October 16, 2007 5:39 AM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      October 16, 2007 10:50 AM      
      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
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        October 16, 2007 11:19 AM      
        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.
    • Shunsuke
       
      Posts: 1 / Nickname: shunsuke / Registered: October 16, 2007 2:37 PM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      October 16, 2007 7:46 PM      
      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
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        October 16, 2007 8:22 PM      
        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.
    • Sebastian
       
      Posts: 1 / Nickname: cornedbee / Registered: October 16, 2007 4:48 AM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      October 16, 2007 10:00 AM      
      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.
      • Thomas
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        October 16, 2007 11:15 AM      
        >>
        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... :-]
      • Achilleas
         
        Posts: 98 / Nickname: achilleas / Registered: February 3, 2005 2:57 AM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        October 17, 2007 6:07 AM      
        > 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.
    • Johan
       
      Posts: 3 / Nickname: jnilsson / Registered: March 22, 2004 11:44 PM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      October 21, 2007 4:43 AM      
      How much work would it take to extend any_iterator to be able to iterate through e.g. a map's mapped_values?
      • Thomas
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        October 26, 2007 1:08 PM      
        >>
        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
           
          Posts: 3 / Nickname: jnilsson / Registered: March 22, 2004 11:44 PM
          Re: On the Tension Between Object-Oriented and Generic Programming in C++
          October 29, 2007 0:49 AM      
          > >>
          > 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
             
            Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
            Re: On the Tension Between Object-Oriented and Generic Programming in C++
            October 30, 2007 10:02 AM      
            > 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
               
              Posts: 3 / Nickname: jnilsson / Registered: March 22, 2004 11:44 PM
              Re: On the Tension Between Object-Oriented and Generic Programming in C++
              October 30, 2007 11:29 PM      
              > > 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
       
      Posts: 1 / Nickname: avaraujo / Registered: November 14, 2007 10:08 PM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      November 15, 2007 4:36 AM      
      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
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        November 15, 2007 1:34 PM      
        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
           
          Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
          Re: On the Tension Between Object-Oriented and Generic Programming in C++
          November 15, 2007 1:41 PM      
          > 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."
    • zade
       
      Posts: 2 / Nickname: zadechina / Registered: September 28, 2005 2:50 PM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      November 19, 2007 4:30 AM      
      any_iterator use type-erase tech to erase the actal type such as vector::iterator or list::iterator; in that case, it is only a iterator to access the elements in the container.

      but yet any_iterator expose the iterator more details such as the iterator_tag. For my option, I want to only access elements with the type user defined. If you want to tell the iterator tag type to the user, you can use the runtime tech such as through tag_type() function.

      so for template class any_iterator, the CategoryOrTraversal template argument should not needed; and to the extreme, all the argument except the Value are not needed. code like below:
      template< class Value> class any_iterator;

      in this case, type-erase tech is used in its extreme.
      • Thomas
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        November 25, 2007 4:06 PM      
        > so for template class any_iterator, the
        > CategoryOrTraversal template argument should not needed;
        > and to the extreme, all the argument except the Value are
        > not needed.

        The point of these template arguments is to ensure that the any_iterator is a Standard-conforming iterator. Among other things, this ensures that the any_iterator works properly with generic algorithms of the kind found in the STL. If you really need to work with iterators that do not have these capabilities, my recommendation would be to avoid the term "iterator." I believe it's best to reserve the term "iterator" for Standard-conforming iterators.
    • Roland
       
      Posts: 25 / Nickname: rp123 / Registered: January 7, 2006 9:42 PM
      Re: On the Tension Between Object-Oriented and Generic Programming in C++
      October 16, 2007 3:10 PM      
      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
         
        Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
        Re: On the Tension Between Object-Oriented and Generic Programming in C++
        October 16, 2007 3:50 PM      
        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.
        • Roland
           
          Posts: 25 / Nickname: rp123 / Registered: January 7, 2006 9:42 PM
          Re: On the Tension Between Object-Oriented and Generic Programming in C++
          October 17, 2007 1:32 PM      
          > 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
             
            Posts: 62 / Nickname: zbo / Registered: January 20, 2007 9:22 AM
            Re: On the Tension Between Object-Oriented and Generic Programming in C++
            October 19, 2007 10:28 PM      
            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.
        • Thomas
           
          Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
          Re: On the Tension Between Object-Oriented and Generic Programming in C++
          October 16, 2007 10:09 PM      
          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)
          • Raul
             
            Posts: 1 / Nickname: raulh39 / Registered: October 17, 2007 6:33 AM
            Re: On the Tension Between Object-Oriented and Generic Programming in C++
            October 17, 2007 11:46 AM      
            > 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
               
              Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
              Re: On the Tension Between Object-Oriented and Generic Programming in C++
              October 17, 2007 0:47 PM      
              > 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
                 
                Posts: 14 / Nickname: tmbecker / Registered: October 15, 2007 3:27 PM
                Re: On the Tension Between Object-Oriented and Generic Programming in C++
                October 17, 2007 1:02 PM      
                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.
              • John
                 
                Posts: 62 / Nickname: zbo / Registered: January 20, 2007 9:22 AM
                Re: On the Tension Between Object-Oriented and Generic Programming in C++
                October 20, 2007 1:52 AM      
                @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.
          • Eivind
             
            Posts: 3 / Nickname: eeklund2 / Registered: January 4, 2006 8:59 PM
            Re: On the Tension Between Object-Oriented and Generic Programming in C++
            November 27, 2007 7:35 AM      
            > 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)

            "Type normalization" or "Type canonicalization". The latter is probably better, though it is a mouthful. Using a common abbreviation for canonicalization, it would be "Type c14n", though that's only slightly better.

            Eivind.