Lecture 16

2023-05-24 | Week 8 | edited by Ashwin Ranade

(originally written 2022-11-16 by Carey Nachenberg)

Ashwin here! This lecture covers OOP Palooza’s multiple inheritance to dynamic dispatch - slides 67 to 110.

Table of Contents

Multiple Inheritance and Its Issues

Multiple inheritance is when a derived class inherits implementations from two or more superclasses, e.g.:

class Person { ... };
class Robot { ... };

class Cyborg: public Person, public Robot
{ ... }

Multiple inheritance is considered an anti-pattern, and forbidden in most languages! In cases where you want to use multiple inheritance, have your class implement multiple interfaces instead.

Here’s an example where there’s a problem:

class CollegePerson {
public:
  CollegePerson(int income) { income_ = income; }
  int income() const { return income_; }
private:
    int income_;
};

class Student: public CollegePerson {
public:
  Student(int part_time_income) :
    CollegePerson(part_time_income)
  {/* Student-specific logic */ }
};

class Teacher: public CollegePerson {
public:
  Teacher(int teaching_income) : 
    CollegePerson(teaching_income)
  { /* Teacher-specific logic */ }
};

class TA: public Student, public Teacher  {
public:
    TA(int part_time_income, int ta_income) : 
      Student(part_time_income),
      Teacher(ta_income) 
    { /* TA-specific logic */ }
};

int main() {
 TA amy(1000, 8000);
 cout << "Amy's pay is $"
      << amy.income();
}

Notice that in this example, both Student and Teacher inherit from the same base class, CollegePerson. Also notice that CollegePerson has an income() method that returns the CollegePerson’s income_ field. But here’s the problem, since a TA class inherits from both Student and Teacher, and each of these has a CollegePerson base part (each with their own copy if the income_ field), the TA class inherits TWO copies of the income_ field, and two copies of the income() method! So when you ask for a TA’s income(), does this call Student’s version of income() or Teacher’s version of income()? Given the example above, if we called Student’s version, we’d get a result of $1000, but if we called Teacher’s version we’d get a result of $8000. This is called the “diamond pattern” - it occurs when a derived class D inherits from a base class B twice by inheriting from two distinct classes X, Y that both on their own are derived from B. It actually inherits the base class B twice, and thus has two copies of every member field, etc.

Needless to say, this is very confusing for the programmer. Some languages, like C++ will generate an error for this: “error: non-static member income’ found in multiple base-class subobjects of type ‘CollegePerson’”. Other languages have a mechanism to pick one of the two functions to always call, or perhaps let the programmer specify which base version to call (e.g., TA.income()). Regardless, you want to avoid the diamond pattern, and multiple inheritance more generally.

We can even have issues with multiple inheritance without a diamond pattern. Consider what would happen if two base classes define a method with the same prototype, and then a third class inherits from both base classes. When calling that method, which version should be used? It gets complicated.

TL;DR - don’t use multiple subclass inheritance; inherit from multiple interfaces instead

Abstract Methods and Classes

Abstract methods are methods that define an interface, but don’t have an implementation. For instance, area() and perimeter() are abstract methods in the example below:

class Shape { 
public:
  double area() const = 0;
  double perimeter() const = 0;
};

An abstract method defines “what” a method is supposed to do along with its inputs and outputs – but not “how.” An abstract class is a class with at least one abstract method - it defines the public interface and partial implementation for subclasses.

When defining a base class, most languages allow the programmer to specify one or more “abstract methods”, which are just function prototypes without implementations.

class Shape { // C++ class
public:
  // area and rotate are "abstract" methods
  virtual double area() const = 0;
  virtual void rotate(double angle) = 0;
  virtual string myName() 
    { return "abstract shape"; }
};

abstract class Shape {  // Java class
 // area and rotate are "abstract" methods
 public abstract double area();
 public abstract void rotate(double angle);
 public String myName()
   { return "abstract shape"; }
};

Question: Can we instantiate an object of an A.B.C. like Shape?

int main() {
  Shape s;  // ?????
  cout << s.area(); // ????
}

Answer: You can’t instantiate an object of an ABC because it has an incomplete implementation. What if the user tried to call s.area()? There’s no method implementation to call!

So why define abstract methods at all? Why not just provide dummy implementations in the base class?

class Shape { // C++ class
public:
  // area is an "abstract" method
  virtual double area() const { return 0; }   // dummy version returns 0
  virtual void rotate(double angle) { }        // dummy version does nothing
  virtual string myName() 
    { return "abstract shape"; }
};

Answer: An abstract method forces the programmer to redefine the method in a derived class, ensuring they don’t accidentally use a dummy base implementation in a derived class!

OK what about abstract classes and types? Just as with concrete classes, when you define a new abstract class, it automatically creates a new type of the same name! More specifically, it defines a reference type, which can ONLY be used to define pointers, references, and object references… not concrete objects.

When should you use abstract methods/classes

Use abstract methods/classes under the following circumstances.

  • Prefer an abstract method when there’s no valid default implementation for the method in your base class.
  • Prefer an abstract class over an interface when all subclasses share a common implementation (one or more concrete methods or fields), and you want the derived classes to inherit this implementation

In contrast, you would inherit/implement an interface when you have a “can-do” relationship, e.g., a Car can do Driving, so a car might implement a Drivable interface.

Inheritance and Typing

When we use inheritance to define classes, we automatically create new supertypes and subtypes! The base class (e.g., Person) defines a supertype. The derived class (e.g., Student) defines a subtype. And given the rules of typing, we can then use a subtype object anywhere a supertype is expected.

As we learned earlier, any time you define a class or an interface, it implicitly defines a new type.

The type associated with a concrete class is specifically called a value type. Value types can be used to define references, object references, pointers, and instantiate objects.

The type associated with an interface OR abstract class is called a reference type. Reference types can ONLY be used to define references, object references, and pointers.

Ok, so how does typing work with inheritance? Consider these two classes:

class Person {
public:
  virtual void talk()
    { cout << "I'm a person"; }
  virtual void listen()
    { cout << "What'd you say again?"; }
};

class Student: public Person {
public:
 virtual void talk() 
   { cout << "I hate finals."; }
 virtual void study() 
   { cout << "Learn, learn, learn"; }
};

Well… the Person base class definition implicitly defines a new type called Person. And the Student subclass definition implicitly defines a new type called Student. And since Student is a subclass of Person the Student type is a subtype of the Person type!

Ok, and how does typing work with interface inheritance? Consider this example:

// Java interface inheritance
public interface Washable {
  public void wash();
  public void dry();
}

public class Car implements Washable {
  Car(String model) { ... }
  void accelerate(double acc) { ... }
  void brake(double decel) { ... }

  public void wash() {
   System.out.println("Soap & bucket");
  }
  public void dry() {
    System.out.println("Dry with rags");
  }
}

Well… the Washable interface definition implicitly defines a new type called Washable. And the Car class definition implicitly defines a new type called Car. And since Car is an implementer of Washable the Car type is a subtype of the Washable type!

Inheritance and Typing Challenges

Question: When would a derived class not be a subtype of its base class? Answer: When we privately inherit from a base class, the derived class is NOT a subtype of the superclass’s type, nor does it share the interface of the base class!

Question: When could a class have a supertype, but not a superclass? Answer: A class could have a supertype of an interface type, without having a superclass, since an interface is not a class (at least in some languages).

Subtype Polymorphism

Subtype Polymorphism is the ability to substitute an object of a subtype (e.g., Circle) anywhere a supertype (e.g., Shape) is expected. More technically, S.P. is where code designed to operate on an object of type T operates on an object that is a subtype of T.

class Shape { ... };
class Circle: public Shape { ... };

void display(Shape& s) {    // display accepts a Shape (supertype) object
  ...
}

int main() {
  Circle circ(0,0,5);
  display(circ);            // but we're passing in an object that's asubtype of Shape
}

As we learned in datapalooza, typing rules state that if a function can operate on a supertype, it can also operate on a subtype! The same holds true for supertypes and subtypes associated with inherited classes! And for classes that implement interfaces!

This also works because the class associated with the subtype supports the same public interface as the class associated with the supertype:

class Washable { // Interface
  virtual void wash() = 0;
  virtual void dry() = 0;
};
class Car: public Washable { ... }

void washAThing(Washable& w) {  // this function  accepts a supertype
  w.wash();
}

void cleaningCrew() {
  Car Subaru;
  washAThing(subaru);  // we're passing a subtype object to the function above
}

So we’ve seen that we can substitute a subtype object anywhere a supertype is expected. This works because the subclass inherits/implements the same interface as its superclass. But that’s not enough! We also expect the methods of the subclass to have the same semantics as those in superclass.

Consider these base and derived classes:

class Shape {
public:
  virtual double getRotationAngle() const {
      // returns angle in radians
  } 
  ...
};

class Square: public Shape {
public:
  virtual double getRotationAngle() const {
    // returns angle in degrees
  }
  ...
};

Notice that our derived class returns the result in degrees, but the base class returns the result in radians? This would change the semantics of the interface defined by the base class, and is a bad idea. Imagine if you passed a Square object to a function that operated on Shapes? Any time it operated on a Square and called getRotationAngle() it would get a result in degrees, when it expected results in radians. This would cause tons of bugs. To ensure this doesn’t happen, a derived class should always implement the same semantics as the base class. If a subclass adheres to the interface and semantics of the base class, we can truly substitute any subtype object for a supertype, and our code will still work. This is called the Liskov Substitution Principle, named after computer scientist Barbara Liskov.

Subtype Polymorphism in Dynamically-typed Languages?

So far, all of our examples have been with statically-typed languages!

Question: Can we have subtype polymorphism in dynamically-typed languages like Python? Consider this example:

class Car:
  def speedUp(self, accel):
    ...
  def slowDown(self, decel):
    ...
  def steer(self, angle):
    ...

class HybridCar(Car):
  def speedUp(self, accel):
    ...
  def slowDown(self, decel):
    ...

def drive_car(c):
  c.speedUp(5)

def main():
  prius = HybridCar()
  drive_car(prius)  # is this using subtype polymorphism?

Answer: Nope. Subtype polymorphism occurs when we process a subtype object as if it were an object of the supertype. But in dynamically-typed languages, variables have NO type at all! For instance, the parameter c in the drive_car(c) class above has no type. So how can we be treating the prius (a subtype) as if it’s a supertype (a Car)? We can’t, and we’re not. So we’re NOT using subtype polymorphism! This code will work, however (using duck typing)! It’s just not subtype polymorphism!

Classify That Language: Subtype Polymorphism

Consider the following code. In this language, a “trait” is the name for an interface. Does this program use subtype polymorphism? Why or why not?

trait Shape {
  def getArea(): Double
  def getPerim(): Double  
}

class Square(side: Double) extends Shape {
  override def getArea(): Double = side * side
  override def getPerim(): Double = 4 * side
}
class Circle(r: Double) extends Shape {
  override def getArea(): Double = Math.PI * r * r
  override def getPerim(): Double = 2 * Math.PI * r
}

def printStats[T <: Shape](s: T): Unit = { 
  println("The area is: " + s.getArea()) 
  println("The perimeter is: " + s.getPerim()) 
}

val square = Square(10.0)
val circle = Circle(1.0)
printStats(square)
printStats(circle)

Answer: This program does use subtype polymorphism. We pass a subtype object like square/circle, and treat it like a supertype, using type T, which is designated to be some subtype of a Shape.

Dynamic Dispatch

Imagine we have a variable var that refers to some object:

void foo(Shape& var) { // c++
  cout << var.area();
}

or:

def foo(var):
  print(var.area())

With Dynamic Dispatch, when you call a method on var, e.g.: var.area(), the actual method that gets called is determined at run-time based on the target object that var refers to. The determination is made in one of two ways:

  • Based on the target object’s class, or
  • By seeing if the target object has a matching method (regardless of the object’s type or class), and calling it if one was found - in languages without classes and just objects

So dynamic dispatch is the process of figuring out which method to call when a call is made to a virtual method at runtime. Do we call Circle’s area() method, Square’s area() method, or what?

Dynamic Dispatch in Statically-typed Languages

In statically typed languages, the language examines the class of an object at the time of a method call and uses this to “dynamically dispatch” to the class’s proper method. Typically this is implemented by adding a hidden pointer into each object which points at a vtable for the class. A vtable is an array of function pointers which points to the proper method implementation to use for the current class. Every class has its own vtable. Only virtual methods are included in the vtable. So a Circle object would have a pointer to a vtable pointing to Circle’s area() and perimter() methods. And a Square object would have a pointer to a vtable pointing to Square’s area() and perimeter() methods. When the call happens, e.g. var.area(), the vtable associated with the object is consulted and the pointer to the area() function is used to call the proper function.

Dynamic dispatch is NOT used to call regular instance or class methods. Instead a standard function call is used in these cases. For regular instance functions (that are non-virtual) or class/static functions, a function call to them is called “static dispatch,” since the proper function to call can be determined at compile time (statically), not at runtime (dynamically).

Dynamic Dispatch in Dynamically-typed Languages

In dynamically typed languages, things get more interesting! While a class may define a default set of methods for its objects the programmer can add/remove methods at runtime to classes or sometimes even individual objects! So when a method is called, the language can’t necessarily rely upon an object’s class or type to figure out what method to use! Here’s an example from javascript:

// Javascript dynamic dispatch example
function makeThemTalk(p) {
  console.log(p.name + " says: " + p.talk());
}

var person = {
  name: "Alan Kay",
  talk: function() { return "Java is meh"; },
  change: function()
    { this["talk"] = function() { return "I <3 Smalltalk"; } }

};

var bird = {
  name: "bluebird",
  talk: function() { return "Chirp chirp"; }
};

makeThemTalk(person)
person.change()
makeThemTalk(person)
makeThemTalk(bird)

So how might a language that allows you to customize methods for individual objects determine which method to call? Answer: The language stores a unique vtable in every object!

Dynamic Dispatch Challenge Questions

Question: What is the difference between subtype polymorphism and dynamic dispatch?

Answer: Subtype polymorphism is a statically-typed language concept that allows you to substitute/use a subtype object (e.g., HighPitchedGeek) anywhere code expects a supertype object (e.g., a Geek). Since the subtype class shares the same public interfaces as the supertype, the compiler knows that the types are compatible and substitution is allowed.

In contrast, dynamic dispatch is all about determining where to find the right method to call at run-time for virtual/overridable methods. Dynamic dispatch occurs whether or not we have subtype polymorphism, as we’ve seen in dynamically-typed languages like Ruby and Python.

Question: Is dynamic dispatch slower, faster, or the same speed as static dispatch? Why?

Dynamic dispatch is slower than static dispatch, since we need to look up function pointers in the vtable at runtime before performing the call. Static dispatch calls are hard-wired at compile time into the generated machine code, and thus much faster (a direct machine language call).

Classify That Language: Dynamic Dispatch

Consider the following classes…

class Geek {
public:
  void tickleMe() { 
    laugh(); 
  }
  virtual void laugh()
    { cout << “ha ha!”; }
};

class HighPitchGeek: public Geek {
public:
  virtual void laugh()
    { cout << “tee hee hee”; }
};

int main() {
  Geek *p = new HighPitchGeek;
  
  p->tickleMe(); // ?

  delete p;
}

Question: Will dynamic dispatch be used in this program? Also, what will print, and why? Answer: Yes, it’s using dynamic dispatch. This will print “tee hee hee”. Why? Because dynamic dispatch always selects the most derived-version of a function to call. So even though the laugh() method is called by the tickleMe() method which is defined in Geek, the laugh() method has been redefined in HighPitchedGeek, and our object is of type HighPitchedGeek, and so this version is called..