Type Tricks 1 - Phantom Types

Warning: Unused type parameter

Java, as with most statically typed languages, allows types to be parameterized by other types. This is usually used to write generic data structures such as lists, maps, sets, etc. These data structures all have one thing in common: They expect to hold values of a type specified as a parameter to the data structure.

It is, however, possible to use type parameters purely as means of distinguishing between otherwise identical types at compile-time. As an example, consider a 3D simulator that contains functions for converting arbitrary points between "world space" and "screen space". The program defines a Point type and a pair of functions for world/screen space conversions:

class Point
{
  int x;
  int y;
  int z;

  void screenToWorld(Point p) { // Omitted }
  void worldToScreen(Point p) { // Omitted }
}

The problem with this approach is that the compiler cannot distinguish between points in world space and points in screen space. It's entirely possible for the programmer to mix up the two. Problems of this nature, particularly in this area of computer graphics, can be extremely hard to track down: objects onscreen may simply move incorrectly or not appear at all.

The programmer could create two separate WorldPoint and ScreenPoint types, but this would then mean duplicating code for functions that apply to points regardless of their coordinate systems. The programmer could use inheritance, but this has serious problems as will be demonstrated. The solution is to parameterize the Point type by a type that represents the coordinate system of the point. As "coordinate system" is essentially an abstract concept, the actual type needs no value-level representation at all:

class Point<C>
{
  int x;
  int y;
  int z;

  Point( /* ... */ ) { // Omitted }
}

class WorldSpace
{
  private WorldSpace() { }
}

class ScreenSpace
{
  private ScreenSpace() { }
}

class Matrices
{
  // Omitted, irrelevant.
}

class PointConversions
{
  Point<WorldSpace> screenToWorld(Point<ScreenSpace> p)
  { 
    return new Point<WorldSpace>(Matrices.multiplyByInverseMatrix(p));
  }

  Point<ScreenSpace> worldToScreen(Point<WorldSpace> p)
  {
    return new Point<ScreenSpace>(Matrices.multiplyByMatrix(p));
  }

  <C> Point<C> reflectX(Point<C> p)
  {
    return new Point<C>(-p.x, p.y);
  }
}

Note that the programmer is now statically prevented from passing a Point<WorldSpace> where a function demands a Point<ScreenSpace> and vice-versa. The programmer does not want or need actual values of types WorldSpace or ScreenSpace and so the construction of which is made impossible by making the constructors private. This is from where the term phantom arises: the types are not used at the value-level, and essentially appear out of thin air. Due to the nature of Java generics, the compiler will erase the type parameters, incurring no runtime cost whatsoever. It is also possible to write functions that apply to points in any coordinate system, removing the need to use inheritance, simply by leaving the coordinate system unspecified in the type parameter to Point type. The type system is also able to express concepts such as "a function that takes a point in any coordinate system and returns a point in the same coordinate system" as in reflectX(): the values of the type parameters in the function parameter and return type must match. Lastly, using types in this manner leads to code that helps to document itself: the programmer could remove the worldToScreen and screenToWorld function names and it would still be reasonably obvious what the functions did based on the types alone.

Phantom types see heavy use in languages such as OCaml, where they are used to, for example, provide read-only views of mutable references.

How not to do it

The average Java programmer would likely immediately attempt to use inheritance to solve the above problem. Unfortunately, it doesn't solve the problem at all. Given the following definitions:

abstract class Point
{
  int x;
  int y;
  int z;

  protected Point(
    int x,
    int y,
    int z)
  {
    this.x = x;
    this.y = y;
    this.z = z;
  }
}

class PointWorld extends Point
{
  PointWorld(
    int x,
    int y,
    int z)
  {
    super(x, y, z);
  }
}

class PointScreen extends Point
{
  PointScreen(
    int x,
    int y,
    int z)
  {
    super(x, y, z);
  }
}

class PointConversions
{
  PointScreen worldToScreen(PointWorld p)
  {
    // Omitted.
  }

  PointWorld screenToWorld(PointScreen p)
  {
    // Omitted.
  }

  Point reflectX(Point p)
  {
    // ?!
  }
}

Unfortunately, due to Java's subtyping rules, there's now no way to express that the input to and the result of reflectX() must be the same type. Using the functions implies a lot of unsafe casting. The same problem applies to all methods that could be defined in the base Point class: all methods must work with values of type Point, essentially throwing away type information. The choice is either between losing type information, or writing functions once for each class that extends the Point type. Finally, using subclassing has a small cost at runtime, which may matter for performance critical code. It comes as no great shock that most modern well-written Java code avoids subclassing, preferring to rely on generics and interfaces for polymorphism.