» CS 330: Lecture 15 – Ad Hoc Polymorphism

CS 330: Lecture 15 – Ad Hoc Polymorphism

March 7, 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:

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.
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 in Java and templates in C++.
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.

We started discussing coercion last time, and we write this function:

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

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"; // instead of Zing z = Zing("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. The types don’t match, but there’s a defined transition from one to the other.

Will this code work?

void print(Zing z) {
  std::cout << z.Length() << std::endl;
}

int main(char **argv, int argc) {
  print("foo");
}

Before we go further, let’s talk a bit about the various types of values we encounter in C++. We’ve got plain old types. How do those fare in a situation like this?

void swap(int a, int b) {
  int tmp = a;
  a = b;
  b = tmp;
}

int main() {
  int i = 10;
  int j = 11;
  swap(i, j);
  std::cout << "i: " << i << std::endl;
  std::cout << "j: " << j << std::endl;
}

Because functions have this semantic notion that they are insulated from one another, plain old values get cloned before being passed in. So, the a and b of swap do indeed get swapped, but this has no lasting effect. To break that insulation, we can employ pointers. Instead of sending in the values themselves, let’s just communicate their locations:

void swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int main() {
  int i = 10;
  int j = 11;
  swap(&i, &j);
  std::cout << "i: " << i << std::endl;
  std::cout << "j: " << j << std::endl;
}

This works, but the code becomes much more difficult to reason about. Enter references, available in C++ but not in C. References give us the sharing semantics of pointers but the syntax of plain old values:

void swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

int main() {
  int i = 10;
  int j = 11;
  swap(i, j);
  std::cout << "i: " << i << std::endl;
  std::cout << "j: " << j << std::endl;
}

Internally, references are implemented using pointers, but that’s an implementation detail. In C++, one should favor references over pointers for sharing data. We’ll use a lot of references in the code we write from here on out.

Moving on, in ad hoc polymorphism, we have several definitions of the function available for various types. We don’t really have one piece of code working with many types, but we do have one name working with many 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];
}

It’s common practice in C++ to provide two versions of methods, one that returns a reference and another that is const and returns a plain old value.

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 then 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;
}

That’s enough for one day. We’ll continue our discussion of ad hoc polymorphism next time.

Here’s your TODO list for next time:

What do you think about having a take-home exam instead of an in-class one?

See you then!

Sincerely,

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

f, f, f, f, f
That’s what the compiler says
On seeing your code

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

zing.cpp

#include <iostream>

#define FOO 6

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

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

    ~Zing() {
      delete[] s;
    }

  private:
    char *s;
    int length;
};

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

}

int main(int argc, char **argv) {
  Zing z = "Jordan's Sister";
  /* std::cout << "z[4]: " << z[4] << std::endl; */
  std::cout << "z: " << z << std::endl;
  /* std::cout << "z[-1]: " << z[-1] << std::endl; */
  /* std::cout << "z[1000]: " << z[1000] << std::endl; */

  /* z[4] */

  /* Zing *pz = new Zing("Jordan's Mom");  */
  return 0;
}

swap.c

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

/* void swap(int a, int b) { */
  /* int tmp = a; */
  /* a = b; */
  /* b = tmp; */
/* } */

/* void swap(int *a, int *b) { */
  /* int tmp = *a; */
  /* *a = *b; */
  /* *b = tmp; */
/* } */

void swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

int main(int argc, char **argv) {
  int i = 10;
  int j = 15;
  swap(i, j); 
  printf("i: %d\n", i);
  printf("j: %d\n", j);
  return 0;
}