» CS 330: Lecture 17 – Subtype Polymorphism

CS 330: Lecture 17 – Subtype Polymorphism

March 12, 2018 by Chris Johnson. Filed under cs330, lectures, spring 2018.

Dear students,

As we discussed last time, polymorphism is the pursuit of code that works with many types. It manifests itself in several forms that we’ve been discussing:

Coercion, in which we have a value of type X and an operation that expects type Y, but there’s a known path for converting Xs into Ys. The function is polymorphic in the sense that it can operate on Ys and any values of types that can be converted to Y.
Ad hoc polymorphism is the name we give to the overloading of functions. Several versions of a single function are written, each catering to a different type. We don’t really save on effort with ad hoc polymorphism, but we at least save on names. Each version of that function has the same name.

Now let’s add a third form:

Subtype polymorphism is when a piece of code is targeted to handle an umbrella type, a supertype, but somehow it calls the overridden methods in the subtype.

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.

Subtype polymorphism is different from coercion, which involves converting data from one type to some universal type. With subtype polymorphism, we do not convert types. Instead, we leverage the fact that that subtypes can fit inside a supertype container. Someone asking for a rectangle can be given a square without first needing to turn the square into a rectangle.

Like ad hoc polymorphism, with subtype polymorphism, we will have multiple different implementations of a subroutine. The multiple implementations will have almost the same signature. They differ in the type of the implicit this parameter.

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 Quitter {
  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);
  } 
}

Here JButton is the conductor, and Quitter was just recently hired by the orchestra. We bridge the two by creating an intermediary that fits into ActionListener, which JButton does know about.

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—like finding roots or intersections. 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:

WDTD #1

QuadraticFunction x_squared(1, 0, 0);
std::cout << x_squared.toString() << std::endl;

WDTD #2

LinearFunction &x_plus_5(1, 5);
std::cout << x_plus_5.toString() << std::endl;

WDTD #3

LinearFunction x_plus_5(1, 5);
QuadraticFunction &ref = x_plus_5;
std::cout << ref.toString() << std::endl;

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): 16
sizeof(B): 4

B is a 4-byte int, while A is a 4-byte int plus an 8-byte pointer to something called a vtable plus some padding. That vtable is the mechanism by which polymorphism happens, and we will discuss it in more detail in a bit.

To experiment with subtype polymorphism in C++, we’re going to create a terminal-based graphing calculator. Plotting in the terminal sounds a little awkward, and it is. But it’ll be fun. We’ll use the Ncurses library to position the cursor at arbitrary locations on the screen. Here’s a first step, which plots just the x- and y-axes.

#include <ncurses.h>

class Calculator {
  public:
    Calculator() {
      initscr();
      clear();
      getmaxyx(stdscr, height, width);
    }

    void plot() {
      int mid_x = width / 2;
      int mid_y = height / 2;

      for (int x = 0; x < width; ++x) {
        mvprintw(mid_y, x, ".");
      }

      for (int y = 0; y < height; ++y) {
        mvprintw(y, mid_x, ".");
      }

      getch();
      endwin();
    }

  private:
    int width;
    int height;
};

Here’s a main method to get it up and running. Eventually we’ll feed it some functions, but not today.

int main(int argc, char **argv) {
  Calculator calc;
  calc.plot();
  return 0;
}

Let’s have it plot some functions. First, we need an abstract base class for all functions. The C++ for this pure virtual, and the syntax is not very intuitive:

class Function {
  public:
    virtual double operator()(double x) const = 0;
};

We force Quadratic and Linear into this hierarchy:

class QuadraticFunction : public Function {
  // ...
};

class LinearFunction : public Function {
  // ...
};

Next we give the calculator a vector of supertypes:

class Calculator {
  // ...

  private:
    vector<Function *> functions;
};

To get subtype polymorphism we have to use pointers or references. A vector<Function> would hold instances of Function, but since the Function class is abstract, no instances are possible. Vectors can’t hold references, so pointers it is. (C++11 introduced std::reference_wrapper, which effectively allows this.)

Now let’s add an add method:

void add(Function *f) {
  functions.push_back(f);
}

And augment our plot method:

for (int x = -mid_x; x <= mid_x; ++x) {
  for (auto fp : functions) {
    const Function &f = *fp;
    int y = f(x);
    mvprintw(mid_y - y, x + mid_x, "o");
  }
}

In our main, let’s start plotting:

QuadraticFunction f(0.1, 0, -15);
Calculator calc;
calc.add(&f);
calc.plot();

If we’re really being polymorphic we should be able to add new types to this system without modifying the conductor code. Let’s make a sine wave:

class SineFunction : public Function {
  public:
    SineFunction(double amplitude, double frequency) :
      amplitude(amplitude),
      frequency(frequency) {
    }

    double operator()(double x) const {
      return amplitude * sin(frequency * x);
    }

  private:
    double amplitude;
    double frequency;
};

Here’s your TODO list for next time:

Complete the take-home midterm. Do not work with others. You may search notes, books, and the internet. Apart from searching the web and asking questions on Piazza, you should not write to the internet. Slide your exam under my office door before 3 PM on Friday. Or turn it in during lecture. Late exams will not be accepted.

See you then!

Sincerely,

P.S. It’s time for a haiku!

Eyes of his mother
And a cape from his father
Inheritance won

P.P.S. Here’s the code we wrote together:

alignment.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  char c1 = 'c';
  char c2 = 'z';
  int i = 17;
  printf("&c: %d\n", &c1);
  printf("&c: %d\n", &c2);
  printf("&i: %d\n", &i);
  return 0;
}

Quitter.java

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

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

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

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

    button.addActionListener(new QuitListener());

    frame.setSize(1024, 512);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setVisible(true);
  }
}

dennis.cpp

#include <iostream>
#include <cmath>
#include <ncurses.h>
#include <vector>

using std::vector;

class Function {
  public:
    virtual double evaluate(double x) const = 0;
};

class LinearFunction : public Function {
  public:
    LinearFunction(double slope,
                   double intercept) :
      slope(slope),
      intercept(intercept) {
    }

    double evaluate(double x) const {
      return slope * x + intercept;
    }

  private:
    double slope;
    double intercept;
};

class SineFunction : public Function {
  public:
    SineFunction(double amplitude,
                 double frequency) :
      amplitude(amplitude),
      frequency(frequency) {
    }

    double evaluate(double x) const {
      return amplitude * sin(frequency * x);
    }

  private:
    double amplitude;
    double frequency;
};

class Calc {
  public:
    Calc() {
      initscr();
      clear();
      getmaxyx(stdscr, height, width);
    }

    void plot() {

      for (int x = 0; x < width; ++x) {
        mvprintw(height / 2, x, "-");
      }

      for (int y = 0; y < height; ++y) {
        mvprintw(y, width / 2, "|");
      }

      mvprintw(height / 2, width / 2, "+");

      for (auto f : fs) {
        for (int x = -width / 2; x < width / 2; ++x) {
          double y = f->evaluate(x);
          mvprintw((int) (-y + height / 2), (int) (x + width / 2), "*");
        }
      }

      getch();
      endwin();
    }

    void add(Function *f) {
      fs.push_back(f);
    }

  private:
    vector<Function *> fs;

    int width;
    int height;
};

int main(int argc, char **argv) {
  LinearFunction f(1, 4);
  SineFunction g(5, 0.1);

  Calc c; 
  c.add(&f);
  c.add(&g);
  c.plot();

  return 0;
}