C++ type erasure

[jsmith]

One of the significant advantages templates have over polymorphism
is their ability to retain type. When you write a function frobnicate()
that takes a base class instance (by reference or pointer), that function
has "lost" the real type of its parameter: from the perspective of
the compiler, while executing frobnicate(), it has a base class instance.

Example:

struct Base {};
struct Derived : Base {};

void frobnicate( Base& b ) {
   std::cout << "The compiler says this function was passed a base class object";
}

int main() {
   Derived d;
   frobnicate( d );
}

Although in reality we passed a Derived instance to frobnicate(), from the
perspective of the compiler, frobnicate() received a Base instance, not a
Derived instance.

This can be a problem at times. Perhaps the most common trouble spot is when
frobnicate() needs to make a copy of the object passed to it. It can't.
First of all, to copy an object you have to know at compile time it's
real type, because the real type name is used to invoke the copy constructor:

// Note how we must say "new type-name".
Derived* d_copy = new Derived( original_d );

(In fact, the clone pattern was invented to solve this problem. But we won't
go into that here.)

Templates solve that problem, because templates allow you to retain the
"real type" of b at compile time.

template< typename T >
void frobnicate( const T& b ) {
   T b_copy( b );
   std::cout << "I just made a copy of b" << std::endl;
}

Now that I've evangelized templates a bit, it should be understood that sometimes,
templates' ability to retain type is a hindrance. How can that be? Consider
the following declaration:

template< typename T >
class MyVector {
};

The problem with this declaration is that it exposes the contained type as part
of its type: MyVector<int> is not the same type as MyVector<unsigned>
is not the same type as MyVector<char>. If we wanted, for example, to store
MyVector instances in an STL container, we couldn't directly, because the
containers do not support polymorphism unless you make a base class and store
pointers to base class instances. But, doing so leads potentially to the
above problem with losing type information and also creates tighter coupling
in your code because now two potentially unrelated types must conform to some
virtual interface defined by the common base class.







Introducing type erasure. To use the above MyVector example (it isn't
a very good one here, but it illustrates the point), what if MyVector didn't
have to expose T as part of its type? Then, I could store a MyVector of ints
in the same container as a MyVector of std::strings without resorting to
derivation and polymorphism.

In fact, boost::any is a good example of type erasure. boost::any allows you
to store absolutely anything inside it, but boost::any itself is not a template
class -- it does not expose the type of what is contained inside it.

boost::function is another example of type erasure.

But what can it do for you? Why bother?

Let's take an RPG game as an example. The game has different kinds of items:
weapons of various types, armor of various types, helmets of various types,
scrolls, magic potions, etc. etc. I want to be able to store all of these
in my backpack. Immediately an STL container comes to mind -- perhaps a deque.
But that means that either I must make one class called Item that is a superset
of attributes of all the different kinds of items, or I must make Item a base
class of all those types. But then, once I've stored the Item in the backpack,
I've lost its real type. If I want to prevent the player from, say, wielding
a scroll as a weapon or donning a flashlight for armor, I must resort to downcasts
to check if the Item is really the right type.

But there is an alternative:

class Weapon {};
class Armor {};
class Helmet {};
class Scroll {};
class Potion {};

class Object {
   struct ObjectConcept {
       virtual ~ObjectConcept() {}
   };

   template< typename T > struct ObjectModel : ObjectConcept {
       ObjectModel( const T& t ) : object( t ) {}
       virtual ~ObjectModel() {}
     private:
       T object;
   };

   boost::shared_ptr<ObjectConcept> object;

  public:
   template< typename T > Object( const T& obj ) :
      object( new ObjectModel<T>( obj ) ) {}
};

int main() {
   std::vector< Object > backpack;

   backpack.push_back( Object( Weapon( SWORD ) ) );
   backpack.push_back( Object( Armor( CHAIN_MAIL ) ) );
   backpack.push_back( Object( Potion( HEALING ) ) );
   backpack.push_back( Object( Scroll( SLEEP ) ) );
}

And now I am able to store objects of disparate types in my backpack.
The cynic will argue that I'm not storing polymorphic types; I'm storing
Objects. Yes ... and no. As we'll see, Object is a simple "passthrough"
object that becomes transparent to the programmer later.

But, you say, you've just done the inheritance thing. How is this better?
It is better not because it affords you more functionality than the inheritance
approach, but because it does not tighly couple Weapons and Armors etc through
a common base class. It gives me the power of retaining type as templates do.

Suppose I want now to look at all items that are capable of doing damage to
an opponent in battle. Well, all Weapons will do that, and perhaps some, but
not all Scrolls and Potions. A scroll of Fire will damage an opponent, a
scroll of Enchant Armor not so much.

Here's one way:

   
struct Weapon {
   bool can_attack() const { return true; } // All weapons can do damage
};

struct Armor {
   bool can_attack() const { return false; } // Cannot attack with armor...
};

struct Helmet {
   bool can_attack() const { return false; } // Cannot attack with helmet...
};

struct Scroll {
   bool can_attack() const { return false; }
};

struct FireScroll {
   bool can_attack() const { return true; }
}

struct Potion {
   bool can_attack() const { return false; }  
};


struct PoisonPotion {
   bool can_attack() const { return true; }
};


class Object {
   struct ObjectConcept {   
       virtual ~ObjectConcept() {}
       virtual bool has_attack_concept() const = 0;
       virtual std::string name() const = 0;
   };

   template< typename T > struct ObjectModel : ObjectConcept {
       ObjectModel( const T& t ) : object( t ) {}
       virtual ~ObjectModel() {}
       virtual bool has_attack_concept() const
           { return object.can_attack(); }
       virtual std::string name() const
           { return typeid( object ).name; }
     private:
       T object;
   };

   boost::shared_ptr<ObjectConcept> object;

  public:
   template< typename T > Object( const T& obj ) :
      object( new ObjectModel<T>( obj ) ) {}

   std::string name() const
      { return object->name(); }

   bool has_attack_concept() const
      { return object->has_attack_concept(); }
};

int main() {
   typedef std::vector< Object >    Backpack;
   typedef Backpack::const_iterator BackpackIter;

   Backpack backpack;

   backpack.push_back( Object( Weapon( SWORD ) ) );
   backpack.push_back( Object( Armor( CHAIN_MAIL ) ) );
   backpack.push_back( Object( Potion( HEALING ) ) );
   backpack.push_back( Object( Scroll( SLEEP ) ) );
   backpack.push_back( Object( FireScroll() ) );
   backpack.push_back( Object( PoisonPotion() ) );

   std::cout << "Items I can attack with:" << std::endl;
   for( BackpackIter item = backpack.begin(); item != backpack.end(); ++item )
       if( item->has_attack_concept() )
           std::cout << item->name();
}

[moorecm]

Wow! That is a serious article, jsmith.

       virtual bool has_attack_concept() const
           { return object.can_attack(); }

However, wouldn't this place the requirement that has_attack() be defined for any element stored in the container? How does that differ from having a base class with a pure virtual method?

Am I missing something?

EDIT: Actually, I think I might have lost track of the real problem being solved. So even if a base class was used for 'concepts', the object's real type is still retained. Then again, the coupling would be re-introduced.

EDIT2: Alternatively, couldn't traits and a selector class be used to check for existing concepts?

[jsmith]

However, wouldn't this place the requirement that has_attack() be defined for any element stored in the container? How does that differ from having a base class with a pure virtual method?

It does. You are right ... it doesn't really differ from a pure virtual method in a base class from
a functionality standpoint. The benefit in the above example is that no derivation is needed
for the different item types. They can all be different types.

Actually, I think I might have lost track of the real problem being solved. So even if a base class was used for 'concepts', the object's real type is still retained. Then again, the coupling would be re-introduced.

Yes, again you're right. But you don't need to have a base class at this point. As long as
every class has a method with signature "bool can_attack() const" it works. It is very similar
to polymorphism, only without the need for derivation.

Alternatively, couldn't traits and a selector class be used to check for existing concepts?

Yes, as long as you have the real type of the object, because the trait mechanism works
through template specialization. Having the real type of the object might be problematic
if the objects are stored as base class pointers in the container. This, in my opinion, is
the real benefit of type erasure.

[tummychow]

Enchant armor... roguelike player?

[jsmith]

Been there, done that.

[Disch]

NOTE: my tone here might sound a little "wtf is this", but I'm just trying to understand this concept and see the applications. I'm not trying to be argumentative, it's just how I come across. Please do not take this post as anything negative. =)
----------------------


I can see how this would be useful in a situation where you're trying to use preexisting classes which are not modifyable. For instance, std::vector, std::list, etc all share common functions like push_back, begin(), end(), etc, so you could build a design around that.

Apart from that, though, I don't see why you would benefit choosing this over inheritance.

True, you don't have to derive... but so what? Is derivation really anything worth avoiding?

At least with derivation you can downcast if you need to. From the example above, I'm a little lost as to how you'd obtain the original type from your 'Object' object. In the case of an RPG with multiple items in one pack, downcasting seems like an inevitability.

In the above, you can find out that you can attack with X object. But then what... how do you actually attack with it? Do you give every class (even those that can't attack) an Attack() function?

Inheritence just seems like the better solution here, (and in any situation I can think of where you're dealing with classes that you are designing yourself).

Thoughts / counterpoints?

Like in my NOTE above, believe me when I say I'm not trying to shoot this down. I'm just wondering what the point is. As it is now I don't think I understand it fully.

[Bazzy]

Concepts are quite a powerful thing when you have different types which are somehow related but they don't have a common base class
Something like that is planned to be added to C++ in a future version.
Concepts can solve problems which templates and Inheritance don't solve

[moorecm]

The first benefit that I see, using type erasure, is memory management. I would love to let the container handle it. In order to check for a concept, independent of whether or not there are abstract base classes providing the interfaces, traits could be used.

Consider a few more members, such as name and category for the item classes. The application would then have enough information to tell what kind of item it is and how to wield it. This could all be done without casting, too. I don't see why the application would ever need to know the actual type other than to copy it--and that problem could be solved with the Prototype pattern (aka, Clone pattern).

[jsmith]

@Disch:

First let me say that I wasn't trying to pick on a previous thread; I used this example because it was fresh
in my memory and I didn't want to try to come up with something else. By using this as an example, I am
not saying that this is the best approach for the game design. In the original post I just wanted to throw
out some alternative ideas.

True, you don't have to derive... but so what? Is derivation really anything worth avoiding?

Sometimes it is. The problem with polymorphism in C++ is that in a polymorphic function (for example, one
which takes a base class reference/pointer as a parameter), you've lost the 'actual' type of the parameter.
One of the powers of templates is their ability to let you specialize functions for certain types. For example,
std::string is a specialization of std::basic_string<> for char. Once you've lost the actual type of the parameter,
the function can no longer take advantage of those customizations. The solution to that in the polymorphic world
is to write another virtual method. Which solves the problem, albeit at the cost of another virtual method call
whereas in the template case, assuming a small function, it could be inlined.

At least with derivation you can downcast if you need to. From the example above, I'm a little lost as to how you'd obtain the original type from your 'Object' object. In the case of an RPG with multiple items in one pack, downcasting seems like an inevitability.
In the above, you can find out that you can attack with X object. But then what... how do you actually attack with it? Do you give every class (even those that can't attack) an Attack() function?

It implies a different design. Rather than have an attack() method, I would say have a use() method. use() for Weapon
means to attack; use() for a Scroll means to read it; use() for a Potion means to drink it. The idea is to let the Item know
how to handle itself, rather than requiring some external code know how to handle the Item. The former way I think better
compartmentalizes the functionality; the latter requires potentially a lot of switch() statements and/or casts. The former way
allows you to avoid casting at all (which may be a good thing, because casts can fail... then what?) Also, when you add a new
Item type to the game, you wouldn't need to touch any existing code; you'd just write another item class object that would
handle itself.

[Disch]

Concepts are quite a powerful thing when you have different types which are somehow related but they don't have a common base class

Well that's kind of where I'm confused. If they're somehow related, couldn't you just give them a common base class?

Something like that is planned to be added to C++ in a future version.
Concepts can solve problems which templates and Inheritance don't solve

I don't doubt this at all. But this is kind of what I'm looking for. Could someone pose such a problem where Inheritance isn't suitable? I'm just having a really hard time visualizing it.

The first benefit that I see, using type erasure, is memory management.

The example just uses smart pointers for memory management. I don't see how type erasure contributes to that in any way.

Consider a few more members, such as name and category for the item classes. The application would then have enough information to tell what kind of item it is and how to wield it. This could all be done without casting, too

True, but again.. this can all be done more easily/cleanly with inheritance.

I don't see why the application would ever need to know the actual type other than to copy it

It depends how much you abstract. If you have your base 'Item' class have tons of virtual functions for things which aren't applicable to all items, then you don't need to downcast.

I'd argue that's not preferable though, and that you're better off keeping 'Item' restricted to things that only apply to all items, and downcasting for more specific tasks.

But to each his own.

First let me say that I wasn't trying to pick on a previous thread

Oh, I understand that. I'm very grateful for the explanation, actually. I don't mean to be causing a fuss, I'm just trying to understand this concept. I appreciate all the help and responses thus far.

The problem with polymorphism in C++ is that in a polymorphic function (for example, one which takes a base class reference/pointer as a parameter), you've lost the 'actual' type of the parameter. One of the powers of templates is their ability to let you specialize functions for certain types.

Alright, I get this. I've actually done this myself in the past. Yes this is very useful. But isn't that a point towards general templates (and not necessarily type erasure)? Or are they the same thing (am I misinterrpreting the terms?)

I guess where my confusion is... I don't see how your above 'Object' class does anything of value that can't be accomplished more easily with Inheritance.

And in fact.. your ObjectConcept class uses inheritance to accomplish its ultimate goal. So the whole thing just seems roundabout and adds an unnecessary layer of function calls.

Rather than have an attack() method, I would say have a use() method

True enough. But again... couldn't you just do that with polymorphism?

[Bazzy]

C++xy concepts ( xy != 0x ) are a bit different from jsmith's ObjectConcept
If you are interested here is a video on them: http://www.youtube.com/watch?v=Ot4WdHAGSGo
There the lecturer said at a certain point that they are like type types.
Concepts allow you to get the same function to work with different types which have some characteristics in common but they are not related by inheritance

[jsmith]

If they're somehow related, couldn't you just give them a common base class?

You could, though I would argue that if the common base class contained nothing more than pure virtual methods,
then there are only two reasons for making the base class, neither of which IMHO are stellar reasons:

1) Want/need to store the objects in a (non-polymorphic) container;
2) Want to have some external code call functions into the object.

In the case of #1, type erasure solves the problem without the need for the derivation. In the case of #2, you can,
depending upon your design, rewrite it such that the object calls functions externally (ie, flip it). This is a common
design paradigm that can typically seen in message handling systems.

Could someone pose such a problem where Inheritance isn't suitable?

There are no problems that inheritance cannot solve. But I do think that inheritance and operator overloading do
not mesh well. I'm thinking particularly of the thread on the assignment operator for a derived class. Yes, it works.
But it would be simpler in my mind if inheritance were not involved.

But isn't that a point towards general templates (and not necessarily type erasure)? Or are they the same thing (am I misinterrpreting the terms?)

Polymorphism defeats the specialization because polymorphism means dealing with base class instances. So
void do_it( BaseClass& obj ) { frobnicate( obj ); } cannot take advantage of frobnicate's specialization
on DerivedClass, because the compiler only knows it has a base class instance.

I guess where my confusion is... I don't see how your above 'Object' class does anything of value that can't be accomplished more easily with Inheritance.

And in fact.. your ObjectConcept class uses inheritance to accomplish its ultimate goal. So the whole thing just seems roundabout and adds an unnecessary layer of function calls.

It allows me to store disparate objects in a container without requiring me to use a base class.

True enough. But again... couldn't you just do that with polymorphism?

Let me turn it around. Why use polymorphism when I don't need it?

[moorecm]

The example just uses smart pointers for memory management. I don't see how type erasure contributes to that in any way.

Yes, it does use a smart pointer--my mistake. I guess what I was thinking was that the container doesn't have to contain pointers, which lead me to the assumption that the container could manage the object.

[jsmith]

The reason I declared it to be a boost::shared_ptr<> is so that the object could be
stored in an STL container.

[Disch]

I watched the video Bazzy linked to (c++0x is exciting! But I feel like a nerd for saying that) and read jsmith's post, but now I'm too tired/fried to write a response, so I'll have to wait until tomorrow.

Thanks everyone.

[jsmith]

Another reason to use type erasure, as a colleague put it: when the type shall remain
nameless. For example, when using expression templates. No mortal will ever figure
out the type of an expression to be able to store it in a variable. Look at boost::spirit's
rule<> template. Said type captures an entire parse tree and no human will ever get
the type right.