Dynamic Dispatch

In which I explain how to solve puzzle questions involving dynamic dispatch.

Goto is considered harmful. For example, it is tedious to specify which statement to execute next with absolute precision. Hence, modern languages like INTERCAL do not have goto. Instead they have the much better comefrom.

10 comefrom 20
20 print "forever"

The statement comefrom is so much better than goto. The exercise of building the flowgraph of a program stops being boring. Instead, reconstructing the flowgraph feels like solving an entertaining puzzle. The statements of the program are the pieces of the puzzle. Initially, you can't tell much by looking around them. You have to spread your net wide until you find two pieces that click. You join them, and then repeat, trying to find another fit.

Popular languages like Java are worse in this respect. For the most part, the flow of control is rather clear, boring. There is one exception, though: dynamic dispatch. I have seen several puzzles who, at their core, were about figuring out what dynamic dispatch does.

Alas, if you understand how dynamic dispatch is implemented, all these puzzles become rather boring. It's not so bad as it sounds, though, because most people don't know or don't want to know how dynamic dispatch is implemented. Even better, there are different ways of implementing it. Adepts of one implementation find it difficult to communicate with adepts of the other.

Let's look at an example.

class A {}
class B extends A {}
class X { void f(A a) { } }
class Y extends X { void f(A a) {} void f(B b) {} }
public class Main {
  public static void main(String[] args) {
    A a; B b; X x; Y y;
    a = b = new B();
    x = y = new Y();
    x.f(a); x.f(b);
    y.f(a); y.f(b);
  }
}

Let's pretend to be a compiler. First, we get rid of classes.

void f_X_A(X this, A a) { }
void f_Y_A(Y this, A a) { }
void f_Y_B(Y this, B b) { }
void Main_main_StringA(String[] args) {
  a = b = new_B();
  x = y = new_Y();
  f_X_A(x,a); f_X_B(x,b);
  f_Y_A(y,a); f_Y_B(y,b);
}

The argument this used to be implicit, but is now explicit. The function names are decorated with the types of the arguments: otherwise we'd confuse them. At the call sites, we plugged in function names based on the static types; that is, we don't track the flow of any execution. Oh … oops … the function f_X_B is called but not defined. The closest one is f_X_A. Perhaps we should call that one? Sure. Why not? (says the compiler to itself)

void f_X_A(X this, A a) { }
void f_Y_A(Y this, A a) { }
void f_Y_B(Y this, B b) { }
void Main_main_StringA(String[] args) {
  a = b = new_B();
  x = y = new_Y();
  f_X_A(x,a); f_X_A(x,b);
  f_Y_A(y,a); f_Y_B(y,b);
}

This doesn't feel right. I was to dispatch something at runtime, but the code from above does no work at runtime. Oh, right, let's see which function overrides which. In this case, f_Y_A overrides f_X_A: the first argument is subtyped ($Y \lt: X$), the others are exactly the same. So, I'll introduce some code that does that dispatch.

void f_X_A(X this, A a) {
  if (this instanceof Y) { f_Y_A(this, a); }
  else { /* old body */ }
}
void f_Y_A(Y this, A a) { }
void f_Y_B(Y this, B b) { }
void Main_main_StringA(String[] args) {
  a = b = new_B();
  x = y = new_Y();
  f_X_A(x,a); f_X_A(x,b);
  f_Y_A(y,a); f_Y_B(y,b);
}

Notes. The implementation from above is what I'd call C++-like. The alternative is the Java-like implementation, which I won't describe here. Even the C++-like one I described is a caricature. The trouble is that once all details are put in, the description becomes pretty horrendous. Still, the details that do appear above are usually enough to figure out what happens in $99\%$ of puzzles.

Finally, what we really care about is not the implementation. We only care about having some simple rules that let us figure out the control flow of any program. The particular set of rules exemplified above is easy to remember as a set of actions that a compiler does. (The Java compiler certainly does not do this.) Pretending that a compiler does this and then that is just a useful mnemonic.