Subtypes and Convertible Types

David L. Shang

Index

• What Are Subtypes After All?
• When Are Subtype Rules Required?
• Are Subclasses Subtypes?
• More Subclasses and Subtypes
• More Convertible Types
• Summary

What Are Subtypes After All?

Let us consider an example in pseudo Pascal:

x: pointer of integer;
y: pointer of 1..10 = 4;
x := y;
increase (x, 20);

function increase (x: pointer of integer, increase_value: integer)
begin
	x^ := x^+increase_value;
end

x: integer;
y: 1..10 = 4;
x := y;
increase (address(x), 20);

In fact, subranges are types convertible to integer, but not subtypes of integer, because subranges have a more restrictive premise than an integer.

When Are Subtype Rules Required?

In my last column, I introduced the concept of object name in the Transframe language. There are three different substitutions (I use the term name replacement):

• Value Replacement: the object contained in the destination name is replaced with the object contained in the source;
• Shared Reference Replacement: the destination name represents the same object denoted by the source name; and
• Copied Reference Replacement: the destination name creates a new copy of the source.

The kind of substitution used depends on the kinds of names involved in the substitution. For example:

x: int =0;
y: 1..10 =4;
x := y;

x: Image;
y: Image ="blue_sky";
x := y;

x: float[];	/* an array of float numbers */
y: static of (int,int,int) = (1,2,3);
x := y;

Only shared reference substitutions require subtype rules. For a shared reference substitution, it is possible to have two references, one is of the supertype, another is of the subtype, to share the same object. The object cannot be converted into a supertype object, otherwise the reference of subtype will refer to an invalid object.

The following figure shows when subtype rules are used and when convertible type rules are used.

Convertible rules are used in the white part of the above figure, which takes the majority. Subtype rules are used in the gray part. And the equivalent type rules are used in the dark gray part. The black part is a forbidden area where substitutions are not allowed.

Are Subclasses Subtypes?

Cardelli and Wegner introduced bounded universal quantification, which was later followed by many research works. Cook, Hill, and Canning suggested F-bounded polymorphism, in which inheritance is characterized as an operation on a recursive definition. With this operational definition of inheritance, subclasses, or inherited types, are not always subtypes. They are merely new types gotten by augmenting and modifying the parent type. Bruce followed this work by introducing a series of statically-typed functional languages where type checking is decidable.

Let me put it in a simple way: a subclass is not a subtype exactly when a covariance is presented in the subclass. The purpose of allowing subclasses which are not subtypes of their parent is to enable more subclasses so that we can get more code reuse benefits from inheritance.

The type system in languages such as Sather and Cecil go further to clearly separate the subtype hierarchy and the class hierarchy (implementation inheritance), which makes the language more complex.

I have examined the case of covariance in my first column. When subclasses require covariance, there is usually an untrue promise defined in their superclass: the superclass fails in the presentation of a precise interface specification, thus subclasses must correct the specification by using covariance and then make a violation that disables them being subtypes.

What lacks in traditional type systems is the ability to describe type dependencies: the type of a method input depends on the type of the object that performs the object; the type of the member object depends on the type of the owner; the type of the output depends on the type of the inputs; and the type of following input depends on the type of previous input. In many cases, this dependency is not just a simple the-same-type-as relation, which is supported by the concept of "selfclass", "MyType" or "like current".

Even the discussion is focused on the simple type dependency case, there is a still a major difference between Transframe's approach and other approaches. The major difference is that whether a subclass should be a subtype if the subclass has a method that uses "selfclass" in its input interface. By Transframe, a subclass is always a subtype even when "selfclass" is used.

Let us consider the example given in Kim Bruce's recent paper, Typing in Object-Oriented Languages: Achieving Expressibility and Safety (the example is simplified and translated into Transframe):

class Node
{
	next: selfclass = null;
	function attachRight(newNext: selfclass) {next:=newNext; };
}; 
class DoubleNode is Node
{
	prev: selfclass = null;
	function attachRight(newNext: selfclass)
		{ next:=newNext; newNext.prev:=self; };
}; 

function attach (n1, n2: Node)
{
	n1.attachRight(n2)
};
...
attach (aDoubleNode, aNode);

What is the real problem? I don't believe the problem is to let DoubleNode be a subtype of Node. The problem is the function attach. The method attachRight declares that the object on the right must be the same type of the object on the left. But the interface of attach does not say that n1 and n2 are in the same type, therefore, the statement:

	n1.attachRight(n2)

By Transframe, therefore, DoubleNode is a subtype of Node. The problem is not that attachRight uses "selfclass". The problem is the illegal usage of attachRight in the function attach. Such misusage should be prohibited by the compiler for static safety.

The function attach should declare the type dependency in its interface:

function attach < type NodeType:Node > (n1, n2: NodeType)
{
	n1.attachRight(n2)
};

If we do want a function attach that takes two nodes of two different types, we should check the two nodes to see whether they are in the same type before we call the attachRight method:

function attach (const n1, n2: Node)
{
	assume (n2 is n1#) n1.attachRight(n2)
	// assume n2 is typeof(n1)
};

x: int = GetIntegerFromUserInput();
n1, n2: Node;
if (x) n1:=Node(); else n1:=DoubleNode();
x := GetIntegerFromUserInput();
if (x) n2:=Node(); else n2:=DoubleNode();
attach(n1,n2);

n1: Node = DoubleNode;
n2: Node = DoubleNode;
attach(n1,n2);

The advantage of letting subclass be a subtype can be illustrated in the following way.

If DoubleNode is not a subtype of Node, the validity of a call to function attach(Node,Node) is very limited. The function can only accept nodes whose exact types are Node:

attach(Node(),DoubleNode());		// wrong
attach(DoubleNode(),Node());		// wrong
attach(DoubleNode(),DoubleNode());	// still wrong
attach(Node(),Node());			// okay

If DoubleNode is a subtype of Node, and the type dependency is specified in the function attach's interface (i.e. attach< NodeType > (NodeType,NodeType)), the function can accept more valid combinations:

attach(Node(),DoubleNode());		// wrong
attach(DoubleNode(),Node());		// wrong
attach(DoubleNode(),DoubleNode());	// okay
attach(Node(),Node());			// okay

If DoubleNode is not a subtype of Node, the validity of a call to function attach(Node,Node) will depend on whether the exact type of the actual parameters can be inferred by the compiler. This might be a big loss in practice for dynamic or heterogeneous programming. If type inference fails, the program fails:

n1, n2: Node;
if (some_dynamic_condition1) n1:=Node(); else n1:=DoubleNode(); 
if (some_dynamic_condition2) n2:=Node(); else n2:=DoubleNode(); 
attach(n1,n2);		// wrong, exact types if n1 and n2 are unknown

If DoubleNode is a subtype of Node, and the function attach provides a heterogeneous interface (i.e. attach(Node,Node)), the above code will be acceptable, because any subclass of Node are considered subtypes. Therefore, to enable a polymorphism in heterogeneous data structure, DoubleNode must be a subtype of Node.

Transframe supports multiple interfaces. So the function attach can be written in the following way:

class attach is function
	< type NodeType:Node > (n1, n2: NodeType),
	(const n1, n2: Node)
{
	enter < type NodeType:Node > (n1, n2: NodeType)
	{
		n1.attachRight(n2)
	}
	enter (const n1, n2: Node)
	{
		assume (n2 is n1#) n1.attachRight(n2)
	}
};

More Subclasses and Subtypes

Transframe allows more subclasses, and hence more subtypes, by introducing implicit subclasses via class parameterization. As I mentioned in my first column, Transframe's paramerterized classes are real classes; so that subclasses can derived from paramerterized classes.

Transframe's subtype rules contain a implicit subclass rule that judges whether two parallel subclasses of a (parameterized) class are a subclass of the other. For the description of the rule, click here.

Here are some examples:

// a parameterized class:
	class array #(ElementType: type of any; size: int);
// some derived subclasses, the class listed afterwards is a subclass of the previous:
	array#(ElementType: type of numerical)	// or array of numerical
	array#(ElementType=int)			// or array of int
	array#(ElementType=int, size=5)    	// or int[5]

// the function class:
	class function;
// some derived subclasses, the class listed afterwards is a subclass of the previous:
	function (int)
	function (int), (int,int)		// it has more interfaces

// the tuple class:
	class tuple is structural;
// some derived subclasses, the class listed afterwards is a subclass of the previous:
	< T: type of any > (T, T)			// or < T >(T,T)
	< T: type of numerical > (T, T)
	< T=int > (T, T)				// or (int, int);

// a parameterized classes:
	class Animal #(FoodType: type of Food);
// some derived subclasses, the class listed afterwards is a subclass of the previous:
	Animal #(FoodType: type of PlantFood)
	Animal #(FoodType=Grass)

// some derived subclasses, the class listed afterwards is a subclass of the previous:
	AnimalGroup #(AnimalType: type of Animal#(FoodType: type of PlantFood));
	AnimalGroup #(AnimalType: type of Animal#(FoodType=Grass));
	AnimalGroup #(AnimalType=Cow);  // let Cow be subclass of Animal#(FoodType=Grass)

More Convertible Types

function foo < R;S;T > ((R;S); (S;T); (T;R));
foo ( (2,2.0), (2.0,'c'),('v',5);

	((integer;float); (float;char); (char;integer))

	< R=integer;S=float;T=char > ( (R;S); (S;T); (T;R)  );

For more examples, click here.

Summary