teaching machines

CS 330 Lecture 14 – Graphing Calculator

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

Dear students,

Let’s put subtype polymorphism to work in a Curses-based graphic calculator. Let’s start with an abstract base class for all manner of functions:

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

Now let’s recast our linear and quadratic functions as independent subtypes of Function:

class QuadraticFunction : public Function {
  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;
    }

  private:
    double a, b, c; 
};

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

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

  private:
    double a, b; 
};

And now we create a graphic calculator class. It will be our conductor code, knowing only about Functions but not any particular subtype:

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

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

    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, ".");
      }

      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");
        }
      }

      getch();
      endwin();
    }

  private:
    int width;
    int height;
    vector<Function *> functions;
};

And finally, a main method to put it all together:

int main(int argc, char **argv) {
  QuadraticFunction f(0.1, 0, -15);

  Calculator calc;
  calc.add(&f);
  calc.plot();

  return 0;
}

One thing that’s a little weird here is that we are keeping a vector of pointers to Function. We can’t do vector<Function>, because that would suggest that we are keeping a list of vanilla Function values. But we can’t have a values that are Functions—it’s pure virtual. But wait. Suppose it wasn’t pure virtual. Would that work? Let’s investigate on a smaller example:

class A {
  public:
    A(int a) : a(a) {
    }

  private:
    int a;
};

class B : public A {
  public:
    B(int a, int b) : A(a), b(b) {
    }

  private:
    int b;
};

int main(int argc, char **argv) {
  B b(4, 5);
  A a = b;
  std::cout << sizeof(a) << std::endl;
  return 0;
}

Here’s we’re trying to squeeze an instance of B into an A value. Does this compile? Yes. But As aren’t big enough to hold Bs. What we get is a slice of B.

So, no, we can’t squeeze a QuadraticFunction object into a Function object, pure virtual or not. However, we can squeeze a QuadraticFunction * into a Function *. We can also squeeze a QuadraticFunction & into a Function &, but vector can’t hold references. So, we are channeled into using pointers.

Is this safe? Probably not. Pointers are safe only if we know the memory they point to will stick around. Here’s a case where it doesn’t:

void rot(Calculator &calc) {
  QuadraticFunction f(1, 0, 0);
  calc.add(&f);
}

After method rot finishes, f goes away, but the calculator still has a pointer to it—a dangling reference. Okay, so we have to use pointers. But we are scared about the persistence of memory. The quickest fix and one you’ll commonly see in libraries is to assume that the pointer points to dynamically allocated memory, and that the calculator will assume ownership over the memory it points to. But let’s see what happens when we run our main under valgrind:

valgrind --leak-check=yes --show-reachable=yes ./calc

Memory leaks! We need a deconstructor to free this memory. It will get called when calc goes out of scope.

Calculator::~Calculator() {
  for (auto f : functions) {
    delete f;
  }
}

What happens if we accidentally give a pointer to a stack variable to the calculator? Let’s try with a smaller example:

void foo(int *x) {
  delete x;
}

int main(int argc, char **argv) {
  int a = 1;
  int b = 2;
  int c = 3;

  foo(&b);

  std::cout << "a: " << a << std::endl;
  std::cout << "b: " << b << std::endl;
  std::cout << "c: " << c << std::endl;

  return 0;
}

Terrible things. On both my Macintosh and Linux machines, this crashes the program. I bet you $5 that you can find a machine on which this doesn’t crash. That’s scary. But so is drinking sugar water. On a machine where this doesn’t crash, that delete will be modifying memory that it doesn’t own. malloc and free keep some bookkeeping metadata in the vicinity of the pointer. In this case, there is no metadata because it’s not dynamically allocated memory. But something is there: garbage.

I think sometimes it would be nice to have heap pointers and stack pointers be different, incompatible types. If you invent a language like this, please let me know.

You might be thinking the headache of dynamic allocation is yuck. You should check out unique_ptr, which was designed to manage situations like these.

Subtype polymorphism lets us add new types to this system without modifying the conductor code. Let’s make a derivative class:

class FunctionDerivative : public Function {
  public:
    FunctionDerivative(const Function *f) :
      f(f) {
    }

    double operator()(double x) const {
      const double DELTA = 0.001;
      return ((*f)(x + DELTA) - (*f)(x - DELTA)) / (2 * DELTA);
    }

  private:
    const Function *f;
};

A real derivative would examine the change in x as y gets infinitesimally small. Let’s pretend we’re happy with finite differencing. The FunctionDerivative class becomes a second conductor. It doesn’t know what sort of Function its computing the derivative for.

In our main, we can get the derivative plotted without modifying the calculator in any way (or shape or form!):

FunctionDerivative *fprime = new FunctionDerivative(&f);
...
calc.add(fprime);

Hopefully we can agree that we all benefit from subtype polymorphism. Our conductor code can process a whole hierarchy of types, which is code reuse at its finest.

Here’s your TODO list:

See you next time!

Sincerely,

P.S. It’s Haiku Monday!

I could eat a horse
It’s not that I’m so hungry
It’s that I eat meat