Dynamic types and virtual inner types

The concept based polymorphism I tried to explain in my previous post can be more conveniently expressed with another syntax which avoids concepts at all.

The key observation is that runtime polymorphism and F-bounded polymorphism are very similar in nature, and, to some extent, the latter can be implemented using the former. If I have understood correctly, that is exactly how the Java virtual machine implements generics.

For example, suppose you have an abstract class Shape with a virtual function draw, and several concrete classes like Square, Circle, Triangle, which override draw.
Client code using runtime polymorphism would look like:

void render(Shape* shape)
{
  shape->draw();
}

while using generic programming one could write:

template <typename S>
where Inherits<S, Shape>
void render(S* s)
{
  s->draw();
}

assuming that the concept Inherits<T, U> is verified when T inherits from U (possibly indirectly). An approximation for Inherits is

auto concept Inherits<typename T, typename U>
{
  // T can be implicitly converted to U
  T::operator U();
}

Using the generic code in such situations should probably be considered a mistake, because if one wants to use template based polymorphism, defining the abstract class Shape is pointless. It would be better to directly define a ShapeConcept having a member function draw.

However, the example suggests that a syntax resembling templates could be used to express runtime polymorphism:

template <Shape! S>
void render(S* s)
{
  s->draw();
}

the idea being that S is the runtime type of s. The compiler could instantiate the template immediately and implement the body just like a Shape pointer were used instead of S. Here S is not really a type, since for example expressions like

new S

should be rejected; let’s call things like S dynamic types. They behave much like incomplete types (cannot be instantiated directy, sizeof cannot be called on them), but are a different beast: for the purpose of typechecking they are just subtypes of their parent concept (Shape, in this example), but for code generation they are considered equivalent to it.

Why could all of this syntax be possibly useful? Well, when using ordinary abstract classes, it does not really add anything to the language, but it shows its power when another (more than syntactical) extension is introduced: virtual inner types.

Just like the name suggests, virtual inner types are inner types which behave polymorphically. The typical (and motivating) example here is still that of the abstract factory. So suppose you have the following abstract factory:

class AbstractAnimal;
class AbstractFood;

class AbstractFactory
{
public:
  virtual AbstractAnimal* createAnimal() = 0;
  virtual AbstractFood* createFood() = 0;
};

and the following abstract products:

class AbstractAnimal
{
public:
  virtual void eat(Food*) = 0;
};

class AbstractFood
{
public:
  virtual int quality() const = 0;
};

As explained in my previous posts [1] [2], there’s no way to explain to the compiler that the Food that an animal is able to eat is only that created by the same factory which created that very animal.
Virtual inner types could be used to solve the problem:

class AbstractAnimal;
class AbstractFood;

class AbstractFactory
{
public:
  virtual typedef AbstractAnimal Animal;
  virtual typedef AbstractFood Food;
  virtual Animal* createAnimal() = 0;
  virtual Food* createFood() = 0;
};

class AbstractAnimal
{
public:
  virtual typedef AbstractFactory Factory;
  virtual void eat(Factory::Food* food) = 0;
};

class AbstractFood
{
public:
  virtual typedef AbstractFactory Factory; // unused, only here for completeness
  virtual int quality() const = 0;
};

The idea is that virtual typedef Base X forces inherited class to define an inner type X inheriting from Base. Furthermore, this type behaves polymorphically (the type itself, not only instances!). That means that if A is a dynamic type with parent AbstractAnimal, then A::Factory is the correct dynamic type with parent AbstractFactory.

To explain this fact in more detail, let’s continue the example:

class Cow;
class Grass;

class CowFactory : public AbstractFactory
{
public:
  typedef Cow Animal;
  typedef Grass Food;
  Cow* createAnimal();
  Grass* createFood();
};

class Cow : public Animal
{
public:
  typedef CowFactory Factory;
  void eat(Grass* grass);
};

class Grass : public Food
{
public:
  typedef CowFactory Factory;
  int quality() const;
};

notice that we have defined inner types corresponding to the virtual typedefs of parent classes. Besides, the argument to eat is Grass and not AbstractFood.
Client code, in fact, cannot simply pass an AbstractFood object to the eat member function. The following function should not compile:

void feed(AbstractAnimal* animal, AbstractFood* food)
{
  animal->eat(food);
}

but can be fixed with the use of dynamic types

template <AbstractFactory! Factory>
void feed(Factory::Animal* animal, Factory::Food* food)
{
  animal->eat(food);
}

expressing the fact that both animal and food come from the same factory of dynamic type Factory. The food parameter (actually stored in an AbstractFood variable), is statically downcasted to Grass before being passed to the eat member function. The static typechecking via dynamic types ensures that such a downcast is always safe, so there is no need to perform a dynamic cast.

These ideas for a language extension are essentially equivalent to the ones expressed in the previous post, but seem to require less drastic changes in compiler implementations. Furthermore, they don’t use concepts, so it could be even implemented on top of the existing gcc.

Advertisements

One Response to “Dynamic types and virtual inner types”

  1. Internet Banking Says:

    Just wasting some time on Digg and I found your entry. Not normally what I like to learn about, but it was absolutely worth my time. Thanks.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: