Should the Vector type inherit from the Array type in an environment where both are first-class objects

Question

I have created a programming language that is based on java for a personal project. The language already has generic classes and functions and the generics are completely compatible with primitive types (which I decided not to turn into objects, autoboxed or otherwise).

I am currently designing the Standard Library and having never created a Standard Library I am not sure if making the Vector type inherit from Array would be a disaster or not. Currently it looks like this:

in langname.lang.Array:

class Array<T>
{
  Memory<T> memblock;

  /* Shortened versions of significant functions */

  T & operator[](int index)
  {
    return memblock[index]
  }

  int size()
  { 
    return memblock.size()
  }

  void resize(int newSize)
  {
    /* pseudo code */
    newMem = new Memory<T>(newSize)
    for ref in memblock by key
      newMem[key] = ref
    memblock = newMem
  }
}

in langname.util.Vector:

class Vector<T> extends Array<T>
{
  int count; // number of elements actually being used by the vector

  /* Shortened versions of significant functions */

  T & operator[](int index)
  {
    return super.operator[](index);
  }

  int size()
  { 
    return count;
  }

  void resize(int newSize)
  {
    /* brief pseudo code */
    if(newSize > super.size())
      super.resize(newSize);

    while(count < newSize)  // in-case the array is expanding
      push() // add new empty elements until count == newSize
      count++;

    while(count > newSize) // in-case the array is shrinking
      pop() // remove elements until count == newSize
      count--;
  }
}

The Memory class encapsulates the concept of a block of memory and contains only natively implemented methods. The language has overloadable operators and references so the arr[index] syntax will be used to access elements. I am familiar with the Liskov substitution principle and the Vector type currently behaves exactly like an Array should when used as such. The code showed above is shortened for the sake of brevity.

I figured this was a good idea because Vectors are essentially resizeable arrays and this would allow Vectors to be used whenever a function expects an array. Is this wrong practically or idiomatically and will I run into trouble further down the road?

Answer 1

Invalid Data

One other things glaring out to me in your design is that your Vector class seems to assume, as a result of that count member, that not all of the elements in the array have been meaningfully initialized. So you might have a memory block with 100 elements even though the Vector is only using 75 of them.

Yet Array offers a size method anyway which returns the total size of the memory block.

Now passing that Vector through to a function which accepts an Array reference/pointer and traverses all the elements in the Array can then easily be wasting work if not outright causing a bug, as it might assume that the entire contents of the Array contain meaningfully-initialized values for the elements.

This might not be a problem on its own if Vector overrides the size method (in which case we end up with a dynamic dispatch cost covered below), but if you combine it with the slicing issue described below, then it can become a very real, yet very obscure threat to a complex codebase.

One thing I would suggest at the very least if you use Array this way is to take out that size method. Functions which input an array should be given a size parameter separately, or Arrays should never be used as Vector uses them (they should never be bigger than the number of elements actually meaningfully stored/initialized within them).

Object Slicing

Whenever I see inheritance used like this in C++ at least from one concrete, self-sufficient class to another, it can be a potential smell.

One of the issues you can encounter here is slicing.

You might pass an instance of a Vector to a function which accepts a reference to an Array, e.g., in which the function makes a copy. The function then inadvertently slices away the Vector bits and only produces an Array when its intention was instead to produce a precise replica. Now when interacting with the invalid data issue above, this potentially becomes a very serious problem (even worse than usual slicing scenarios).

A way to protect yourself from this is to always inherit from classes which are at least partially abstract (cannot be instantiated on their own). It's often useful, in C++ at least, to make sure your base classes cannot be instantiated -- only the leaves of your inheritance hierarchy (which are kind of sealed, final subclasses, not to be inherited further) and not the branches and roots, as anything less is always susceptible to object slicing.

That's for C++ though, where things like copy construction do not involve dynamic dispatch. Since you're designing your own language, you might be able to have one where copying a Vector through a base pointer/reference can result in another Vector, thereby eliminating the object slicing problem outright. This would change the existing dynamics of inheritance in a C++-esque language quite a bit. I wouldn't know what to make of such a language, as it would be venturing into unexplored territory. Yet there would be an inherent performance cost to one that did this uniformly, and even if not (ex: having overridable copy constructors), that cost would be required for your above example in order to avoid slicing.

Dynamic Dispatch

By nature, if you allow destruction to occur on a Vector through a reference to an Array, it requires at least dynamic dispatch for destruction (some form of runtime checking through an Array which determines exactly what kind of Array it is and performs branching to execute the appropriate instructions to free the resources). Since Vector and Array have a different size (with Vector introducing a new count field), the instructions to free their memory (both from stack and heap) would have to be different.

Inheritance always implies polymorphism and dynamic dispatch at least in the context of releasing/destroying unless it's impossible to destroy objects through a base pointer.

Of course if you disallow the case of releasing resources through a base pointer/reference, then the dynamic dispatch overhead would go away (unless you avoid the object slicing issues mentioned above, in which case they would come back again for copying). But you probably don't want to do that, since it would make it impossible to create a polymorphic base container, like a list storing references to Array which actually refer to a Vector, let alone a list of references to a Mammal which actually contains a list of Dog and Cat instances.

Efficiency in Context

In the context of a library as general-purpose as a standard library accompanying a language, efficiency takes on a different nature.

It's no longer sufficient to just make it "fast enough" against some real-world user operation. Speed here no longer becomes about making specific operations "fast enough". Speed starts to become a form of generality. The faster your uber-general-purpose library becomes, the more applicable it becomes and fulfills that goal of being generally applicable.

When standard libraries lack speed, it then causes developers to avoid using them in performance-critical scenarios. And that defeats a lot of the purpose of a general library if alternative approaches can easily outperform them.

The reason something like std::vector in C++ is so successful is because when comparing it to alternative methods of creating a growable, dynamically-sized array, people find they can't beat its performance. For apples to apples to comparisons, std::vector gets pretty close to optimal. Now if vector started paying the overhead of dynamic dispatch in functions like operator[], let alone in constructing or destroying it, a lot of that optimal efficiency would be lost.

So a lot of the key to the success of C++'s standard library comes from avoiding dynamic dispatch cost and vtable/vptr costs (vtable costs are usually trivial, but can actually start to get explosive when combined with code generation techniques like templates). A lot of what you are doing above indicates paying such cost somewhere, somehow.

Dynamic Dispatch Part Two

Since there was an expressed interest in this efficiency aspect, the most performance-critical function of something like Vector tends to be operator[] and possibly iterators (if it provides them).

If you allow a Vector to actually be considered an Array rather than containing one, then a function that inputs an Array by reference that receives a Vector then has to pay a dynamic (aka virtual) dispatch overhead like this:

When f in the above diagram calls Array::operator[], it then requires inspecting the type of Array in some form in order to resolve that what it's actually calling here is Vector::operator[]. That's dynamic dispatch, and the biggest overhead there isn't even necessarily branching but because it introduces an unknown to the compiler which can only be resolved at runtime. That then defeats a lot of the optimizer's ability to optimize the hell out of this function call (inlining it, e.g.), as it can't know what function is going to actually be called until the program is executed and the appropriate inputs are provided (that is, unless it's an exceptionally smart optimizer that will generate a different set of instructions when you pass a Vector down the call stack and effectively perform code generation even outside a generic context).

This dynamic dispatch overhead doesn't have to be present if Vector doesn't inherit from Array and the array is marked as final/sealed. In that case, a decent optimizer will make calls to operator[] as cheap as indexing a native array, as with the case with std::vector::operator[] in C++.

Downcasting

Another problem that can occur when inheriting like this is that it might lead to the temptation to occasionally downcast. That temptation can be ever-present in the context of inheritance, but here we don't have to use inheritance (I'll get to that point finally).

The fact that this code suggests merely allowing going from a reference to a Vector to Array and back to Vector again might encourage poor behavior in ways that we can avoid with an iron fist.

When in Doubt, Prefer Composition

Whenever there's a doubt as to whether to use inheritance or composition, favor the latter. It has far fewer ways of being misused. So I suggest something more like this:

class Vector<T>
{
    Array<T> array; // array used for the vector
    int count;      // number of elements actually being used

    T& operator[](int index)
    {
        return array[index];
    }

    int size()
    { 
        return count;
    }

    void resize(int newSize)
    {
        /* brief pseudo code */
        if(newSize > array.size())
            array.resize(newSize);

        while(count < newSize)  // in-case the array is expanding
            push() // add new empty elements until count == newSize
            count++;

        while(count > newSize) // in-case the array is shrinking
            pop() // remove elements until count == newSize
            count--;
    }
};

... this doesn't have as much syntactical sugar since you might have to explicitly call an accessor function, e.g., to get access to the array contents of a vector in order to pass the contents through to a function which inputs an Array by const reference or by value, e.g. Yet this solution can mitigate if not avoid all the issues described above (invalid data, implicit slicing, dynamic dispatch cost, and the temptation to downcast).

It also avoids the potential for the fragile base class syndrome outright. You're free if you use composition as suggested here, to change the implementation details of Array all you like. As long as you don't invalidate the interface requirements which Vector depends on to work, Vector is guaranteed to continue to work in spite of such changes. We don't get this kind of hard guarantee if Vector inherits from Array and potentially has access to some of its details.

So whenever in doubt, I strongly recommend composition. Inheritance is most naturally used when your classes model a subset of a concept (ex: a Cat is a subset of the concept of Mammal). It's almost always awkward and unnatural when used to model something that seems more like a superset. While the superset/subset distinction might not be so distinctly clear in this context, the fact that it might be a bit fuzzy is another reason to reach for composition.

Alternative Strategy

I don't understand the dynamics of your language very well, but an alternative strategy you could potentially explore is to have something like an "array handle", constructed on the fly. Example using overly simplistic code:

// Doesn't own memory, just provides a temporary handle to 
// existing memory in another data structure.
template <class T>
struct ArrayHandle
{
    // Returns the nth element.
    T& operator[](int n)
    {
        assert(n >= 0 && n < size && "n is out of bounds!");
        return ptr[n];
    }

    // Ideally private members, just using struct here for simplicity.
    T* ptr;
    int size;
};

This then gives you a uniform target to decay your data structures to which constructs a handle to contiguous memory on the fly. Both Vector and Array can then provide a method to obtain this handle and pass it along to functions that want to work with a contiguous block of elements.

There's no optimization barrier here, no dynamic dispatch, and it gives you a uniform, homogeneous target type used for parameter passing that lets you uniformly work with contiguous data structures, whether it's coming from Arrays or Vectors or something else.

Against any decent optimizer, invoking operator[] for ArrayHandle there will become as cheap as indexing a native array.

Answer 2

While Ike's answer is very good, I think it's missing one simple and crucial point:

Public inheritance is an "is a" relationship. E.g. "Audi A8 is a Car"

Vector inheriting from Array means "Vector is an Array". To me it's intuitive that that's not the case. Instead, both are clearly different sequential indexed containers, like a linked list, a deque, a ring buffer, and a few others.

.NET represents this with shared interfaces such as IEnumerable, while C++ uses iterators and template mechanics for the same concept.