Typechecking

A compiler or interpreter should reject our code under the following conditions:

• A variable is assigned a value of an incompatible type, as in int x = "32".
• A function is passed an incompatible type, as in max(9, ['a', 'b']).
• An operation is not supported by a type, as in false.absoluteValue().

The act of examining code for these conditions is typechecking. Do you think these Java statements typecheck?

String a = "breath";
String b = a;

System.out.println(100 + 1);

Random g = new Random();
int c = g.nextInt(6);
int d = g.nextInt(6);
int e = Math.max(c, d);

All of these statements pass typechecking. What about these statements?

double f = 6 + 3.0;
int g = f;                       // nope

Object s = "Goodbye, Pluto!";
int h = s.length();              // nope

int k = 13;
byte m = k;                      // nope

byte n = 128;                    // nope

Each language has a unique set of typechecking rules that are used to decide if two different types are compatible. Some languages require strict nominal equivalence. Two types are nominally equivalent only if they are in fact the same named type. For example, a variable of type char is nominally compatible with a parameter of type char. Other languages require only that the two types have structural equivalence, which means that they have the same overall shape, regardless of their name.

Consider the notions of nominal and structural equivalence in the context of these C struct definitions:

struct stack_t {
  int elements[1000];
  int size;
};

struct queue_t {
  int elements[1000];
  int size;
};

These two types are structurally equivalent since they are both made of a 1000-element int array and another int. They are not nominally equivalent as they are not the same named type.

Consider this C program that passes a queue to a function expecting a stack:

void clear(struct stack_t *stack) {
  stack->size = 0;
}

int main() {
  struct queue_t q;
  clear(q);
  return 0;
}

Assemble a program using this code and the struct definitions defined earlier and compile it.

Consider this C program that attempts to pass a color to a function that expects a vehicle:

enum vehicle_t {
  BIKE, CAR, BUS, TRAIN
};

enum color_t {
  RED, GREEN, BLUE
};

int cost(enum vehicle_t vehicle) {
  return vehicle * 10;
}

int main() {
  enum color_t color = BLUE;
  int blue_cost = cost(BLUE);
  printf("%d\n", blue_cost);
  return 0;
}

Compile this program.

Nominal equivalence is strict and makes subprograms less general. Many languages relax this strict equivalence by permitting types to form hierarchies. A subtype is accepted anywhere a supertype is expected, as in this Java program:

List<File> files = ArrayList<>();
Button clicker = new ImageButton("circle.png");

Subtype compatibility makes it possible for developers to write polymorphic functions that serve an entire type hierarchy. For example, this method knows only of the Object supertype:

public String embrace(Object x) {
  return String.format("[%s]", x.toString());
}

Yet any object can be sent to this method, even one whose class didn't exist at the time this method was written.