CSE 505 -- Types in Object-Oriented Languages

Type in an object-oriented language:

A collection of operation signatures, where each signature consists of the operation name, the types of the arguments, and the type of the result(s)

Design Decision: should types be declared statically?

Java includes static type declarations. Smalltalk does not. They are optional in Cecil.

Design Decision: should abstract type and concrete implementation inheritance be separate or combined?

Reasons for separating them:

• they are different concepts
• allows additional flexibility (for example, multiple implementations of the same abstract type)

• it makes the language more complicated
• they often go together

   abstract type Stack
   implementation classes ListStack, ArrayStack
      both would conform to the abstract type Stack

   Stack inherits from Deque (just masks off extra operations like front)

In Java, types can be specified using classes, abstract classes, or interfaces. You can't mask off extra operations. This seems like a good tradeoff among the alternatives.

Another definition sometimes used in type inference systems: a type is a set of classes (see e.g. Palsberg and Schwartzbach)

Covariant vs. Contravariant vs. Invariant Rule

The contravariant rule for subtyping is used in Emerald, Cecil, Trellis/Owl, etc. (It is also the rule used in Cardelli's paper "A Semantics of Multiple Inheritance".)

The covariant rule is used in Eiffel, and in Java for arrays (as a special case).

The invariant rule is used in Java for everything but arrays.

Contravariant rule:

1. S provides all the operations that T does (and maybe some more)
2. For each operation in T, the corresponding operation in S has the same number of arguments and results
3. The types of the results of S's operations are subtypes of the types of the corresponding results of T's operations
4. The types of the arguments of T's operations are subtypes of the types of the corresponding arguments of S's operations (note the reversal of T and S here)

Covariant rule:

1. The types of the arguments of S's operations are subtypes of the types of the corresponding arguments of T's operations

Invariant rule:

1. S provides all the operations that T does (and maybe some more)
2. For each operation in T, the corresponding operation in S has the same number of arguments and results
3. The types of the results of S's operations are the same as the types of the corresponding results of T's operations
4. The types of the arguments of T's operations are the same as the types of the corresponding arguments of S's operations

Examples

Type Color

Type GrayScaleColor (a subtype of Color)

Type Number
  subtypes Float, Integer
 // in this example I'm assuming numbers are full-fledged objects

Type Point
  x(): Number
  y(): Number

Type ColoredPoint
  x(): Number
  y(): Number
  mycolor() : Color

Type GrayScalePoint
  x(): Number
  y(): Number
  mycolor() : GrayScaleColor

Under the contravariant and covariant rules, GrayScalePoint is a subtype of ColoredPoint Point -- anywhere a ColoredPoint is needed, we can use a GrayScalePoint. However, the invariant rule says that GrayScalePoint is not a subtype of ColoredPoint, because mycolor has a different signature in the two types.

Example code:

  p : ColoredPoint;
  c : Color
  p := new GrayScalePoint();

  c := p.mycolor;

  q , r : Point;
  a : Number;
  q := new ColoredPoint();
  r := new GrayScalePoint();
  a := q.x + r.x;  

Type Point
  x(): Number
  y(): Number
  setDotSize(c : Integer);

Type ColoredPoint
  x(): Number
  y(): Number
  setDotSize(c : Number);

    p1, p2 : Point;
    c : ColoredPoint;
    p1 := new Point();
    c := new ColoredPoint();
    p2 := c;   // legal because ColoredPoint is a kind of Point
    p1.setDotSize(3);
    p2.setDotSize(4);
    c.setDotSize(4.5);  // legal because a float is a kind of number

    p1.setDotSize(3.5);
    p2.setDotSize(3.5);  // ok in dynamically typed language

Now consider:

Type ColoredPoint
  x(): Number
  y(): Number
  mycolor() : Color
  setcolor(c : Color);

Type GrayScalePoint
  x(): Number
  y(): Number
  mycolor() : GrayScaleColor
  setcolor(c : GrayScaleColor);

    c : ColoredPoint;
    c := new GrayScalePoint();  /* compile time error */
    c.setcolor(yellow);  /* an error would occur if we tried this */

However, under the covariant rule GrayScalePoint would still be a subtype of ColoredPoint, and the above program would type check correctly, and in the absence of a runtime type check, would lead to errors. (This is analogous to the Java array typing example previously.)

Java Examples

    class Point {
      public int x;
      public int y;
    }

    class ColoredPoint extends Point {
      public Color mycolor;
    }


    interface PointMaker {
      Point makePoint();
    }

    interface PointEater {
      void eat(Point p);
    }

    interface ColoredPointMaker {
      ColoredPoint makePoint();
    }

    interface ColoredPointEater {
      void eat(ColoredPoint p);
    }

    interface ColoredPointMaker extends PointMaker {
      ColoredPoint makePoint();
    }

    interface ColoredPointEater extends PointEater {
      void eat(ColoredPoint p);
    }

    class PtMaker1 implements PointMaker {
      Point makePoint() {
	 return new Point();
      }
    }
    class PtMaker2 implements PointMaker {
      Point makePoint() {
	 return new ColoredPoint();
      }
    }

    class PtMaker3 implements PointMaker {
      ColoredPoint makePoint() {
	 return new ColoredPoint();
      }
    }

    class Eater1 implements ColoredPointEater {
      void eat (Point p) {
      }
    }

    class Eater2 implements PointEater {
      void eat (ColoredPoint p) {
      }
    }