teaching machines

CS 330 Lecture 12 – Subtype Polymorphism

February 20, 2017 by . Filed under cs330, lectures, spring 2017.

Dear students,

We introduced four type of polymorphism last time and saw examples of the first two—coercion and ad hoc polymorphism—through the lens of C++. On to a third form:

Subtype polymorphism is different from coercion, which involves converting data from one type to some universal type. Like ad hoc polymorphism, we will have multiple different implementations of a subroutine, but all the implementations will have (mostly) the same signature. They differ in the type of the implicit this parameter. Subtype polymorphism is usually the polymorphism that you most think of as polymorphism, even though you probably saw its other forms first, because it’s a feature of object-oriented programming.

I like to think of subtype polymorphism in terms of an orchestra. The conductor up front with the baton knows about music in general, but isn’t necessarily versed in every instrument. Rather, the conductor uses a language that’s not specific to any particular instrument to make parts of the orchestra do something. Like get louder or softer. Faster or slower. To get in tune, perhaps. The individual instruments are responsible for obeying the general command in their own unique way.

In our code, we use subtype polymorphism to let one chunk of conductor code, probably written years ago, continue to work with new code. The conductor code appeals to some interface, and any new code we write conforms to that interface.

One of the simplest examples of subtype polymorphism is seen in adding a callback to a JButton:

import javax.swing.JFrame;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;

public class Button {
  public static void main(String[] args) {
    JFrame frame = new JFrame("Quit");

    final JButton button = new JButton("Quit");
    frame.add(button);

    class QuitListener implements ActionListener {
      public void actionPerformed(ActionEvent e) {
        frame.dispose();
      }
    }
    button.addActionListener(new QuitListener());

    frame.pack();
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setVisible(true);
  } 
}

Let’s look at polymorphism in C++. Suppose we’re writing a graphing calculator, and we want to model various function families. We create a QuadraticFunction class:

class QuadraticFunction {
  public:
    QuadraticFunction(double a,
                      double b,
                      double c) :
      a(a),
      b(b),
      c(c) {
    }

    double operator()(double x) const {
      return a * x * x + b * x + c;
    }

    string toString() const {
      stringstream ss;
      ss << a << " * x^2 + " << b << " * x + " << c;
      return ss.str();
    }

  protected:
    double a, b, c; 
};

Later on, we discover we need a LinearFunction class too, and we decide to make it a subtype of QuadraticFunction. Why make a special subtype? Perhaps LinearFunction can do something faster by overriding its supertype methods. Anyway, here it is:

class LinearFunction : public QuadraticFunction {
  public:
    LinearFunction(double a,
                   double b) :
      QuadraticFunction(0, a, b) {
    }

    double operator()(double x) const {
      return b * x + c;
    }

    string toString() const {
      stringstream ss;
      ss << b << " * x + " << c;
      return ss.str();
    }
};

Now, let’s have a round of What Does This Do:

In the last of these, we have a supertype reference to an instance of a subtype. What will happen? In Java, we’ll invoke the subtype’s method. In C++, by default, we will get the invoking type’s method. To make C++ behave like Java, we must explicitly mark overrideable methods as virtual.

Why on earth should we have to do this? Why shouldn’t virtualness be the default behavior? Well, C++ is a language concerned with performance. When the compiler sees a call to a non-virtual method, it can figure out at compile time what the program counter should jump to. But in a polymorphic hierarchy with virtual functions, we’re not exactly certain what kind of object we have.

Consider method conduct:

void conduct(const Instrument &instrument) {
  instance.emlouden();
}

Where will this jump to? Tuba‘s emlouden? Viola‘s? Kazoo‘s? We just don’t know at compile time. This decision has to be made at runtime, and is therefore more expensive. The C++ designers believe that you shouldn’t have to pay for what you don’t need, so virtual is not the default. You have to sign up to get punched in the face.

We also need one extra pointer per instance of any class with a virtual method. Look at the memory footprint of these two classes, which are identical in all respects except for the virtualness of f:

#include <iostream>

class A {
  public:
    virtual void f() {}
    int a;
};

class B {
  public:
    void f() {}
    int b;
};

int main(int argc, char **argv) {
  std::cout << "sizeof(A): " << sizeof(A) << std::endl;
  std::cout << "sizeof(B): " << sizeof(B) << std::endl;
  return 0;
}

On my laptop, I get this for output:

sizeof(A): 4
sizeof(B): 12

A is just a 4-byte int, while B is a 4-byte int plus an 8-byte pointer plus some padding. If you are trying to interoperate with C or write objects out to disk or the network, you probably do not want to write out the vtable pointer.

Here’s your TODO list for next time:

See you then!

Sincerely,