teaching machines

CS 330 Lecture 11 – Polymorphism: Coercion and Ad Hoc

Dear students,

All my favorite talks try to classify some phenomenon in a 2×2 matrix, so let’s do the same. Let’s categorize human endeavors into four buckets based on how much effort is involved and what effect they have:

Large Effect polymorphism John Henry
learning Vim
Small Effect sleeping voting
teaching
Little Effort Lots of Effort

As soon as we start giving our data types, we introduce a problem. If the functions we write only operate on a single type, we’ll have to write a new definition for each type we will need to support. Ugh. That’s a lot of effort to achieve a large effect.

Is there a way we can get a single piece of code to work with multiple types? Yes, that’s right. Polymorphism will help us get a big return out of just a little investment.

We have a word for such flexibility: polymorphism. We usually think of polymorphism as a feature of object-oriented programming, but polymorphism comes in many forms:

  • 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 methods. Several versions of a single function are written, each catering to a different type. We don’t reall save on effort with ad hoc polymorphism, but we at least save on names. Each version of that method has the same name.
  • Parametric polymorphism is when we let a single function be parameterized by a type. We will see this in Haskell, and we see it in generics.
  • 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.

Let’s discuss the first two of these today.

We rely on coercion a fair bit. Consider this definition of the hypot method:

double hypot(double x, double y) {
  return sqrt(x * x + y * y);
}

int main(int argc, char **argv) {
  std::cout << hypot((char) 3, (char) 4) << std::endl;
  std::cout << hypot(3, 4) << std::endl;
  std::cout << hypot(3.0f, 4.0f) << std::endl;
  std::cout << hypot(3.0, 4.0) << std::endl;
}

Function hypot accepts doubles for sure, but also ints, float, chars, and any type that the compiler can coerce into a double. That’s great for builtin types, but what about custom types? Suppose we’re building our own string class named Zing, one that isn’t O(n) for every operation like C strings are. We’d love to be able to say something like this:

Zing z = "foo";

What’s the type on the left-hand side? The right-hand side? Will this work? If you provide a pathway, it will:

class Zing {
  public:
    Zing(const char *s) {
      n = strlen(s);
      text = new char[n];
      memcpy(text, s, n);
    }

    ~Zing() {
      delete[] text;
    }

  private:
    char *text;
    int n; 
};

The compiler will sense that it can convert the right-hand side’s const char * type into the Zing type through this converting constructor. Sometimes such implicit conversions can cover up mistakes, and C++ provides an explicit modifier to prohibit such automatic conversion:

explicit Zing(const char *s) {
  n = strlen(s);
  text = new char[n];
}

Coercion can be seen as a polymorphic funnel. Many types converge to an encompassing type, and a single function is written to the encompassing type. In ad hoc polymorphism, we have several definitions of the function available for various types. What are some famous ad hoc polymorphic methods you know from Java? The first one that comes to my mind is PrintStream.println. How many different versions of this method exist? The answer can be reasoned out.

For Zing, it’d be really nice to be able to access individual characters of the string. How shall we provide that functionality? It’d be really nice to overload the [] operator. Let’s do it:

char operator[](int i) {
  return text[i];
}

Now our string feels a lot like an array. Or does it? What happens here?

Zing z = "goliath";
z[0] = 'G';

To make the character writable, we can return a reference instead of a temporary:

char &operator[](int i) {
  return text[i];
}

Now suppose we want to print the whole string just like we can print other things in C++:

std::cout << z << std::endl;

What do we want to overload here? A method of cout? The rules of C++ state that the compiler will look first for something like this:

ostream &ostream::operator<<(const Zing &z);

But there’s no way we can sneak into the ostream class and an overloaded definition for our new class. However, if this method can’t be found, the compiler than looks for a method like this:

ostream &operator<<(ostream &stream, const Zing &z);

The difference here is that operator<< is not owned by any class. It’s a top-level definition. We can write it like so:

std::ostream &operator<<(std::ostream &stream, const Zing &z) {
  for (int i = 0; i < z.Length(); ++i) {
    stream << z[i];
  }
  return stream;
}

For this to work, we need another version of operator[] that works with const strings:

const char &operator[](int i) const {
  return text[i];
}

There we have it. Two different means of making our handle several different types. And neither has to do with inheritance!

Here’s your TODO list for next time:

  • Browse the C FAQ and C++ FAQ. Write down four behaviors or features (two per language) that surprise, confound, or interest you.

See you then!

Sincerely,

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *