At the limit of virtual types

5	At the limit of virtual types

Alternating lists have been used in [BOW98] as the basic example to illustrate the strength of virtual types. In this section, we reuse alternating lists, but as a counter-example to virtual types.

In fact, alternating lists have been chosen as a simple example of recursively define classes, and in particular, as a simplification of recursively defined parse trees [PS94]⁴. We argue that alternating lists are much better implemented by parametric types than by virtual types. Using parametric polymorphism, we show that there is a continuous sequence of refinements starting with very simple classes and leading to alternating lists. Conversely, virtual types can only address a particular point in this sequence.

In Lisp the most important data structure is the memory cell called a cons. In an object oriented setting, it can be defined as follows:

class ['a, 'b] cons h t = object
  val head : 'a = h val tail : 'b = t
  method null = false method car = head method cdr = tail
end;;

A cons can be used as a pair, that is, a cell filled with two values of different types. In Lisp, one uses a special pointer, usually called nil, to distinguish from conses. Actually, it is convenient to give the class nil the same interface as the class cons since nil is typically used to end a chain of conses in a binary tree or a list.

exception Null;;
class ['a, 'b] nil = object
  method null = true method car : 'a = raise Null method cdr : 'b = raise Null
end;;

With parametric classes, one can define heterogeneous lists, whose elements can be of different types. In many situations one need only consider homogeneous lists; hence we can define the more precise type:

type 'a homo_list = ('a, 'a home_list) cons;;

Alternating lists are just another particular instance of conses that could be defined as follows:

type ('a, 'b) alt_list = ('a, ('b, ('a, 'b) alt_list) cons) cons;;

Indeed, alternating lists have nothing to do with virtual types. Here, we have only specialized the types of classes cons and nil leaving the code unchanged.

The type constraint can be enforced in subclasses of cons and nil rather than in objects of those classes by restricting the types of the class parameters (we only show the subclass for cons):

class ['a, 'alt_self] alt_cons h t =
  object (_ : 'self)
    constraint 'alt_self = ('b, 'self) #cons
    inherit ['a, 'alt_self] cons h t
  end;;

Alternating lists are not final classes, and can be specialized using inheritance. For instance, it is straightforward to add a method returning the length of the list. Of course, many more variations ---including side effects and binary methods--- can be devised, as for any class, just playing with parameterization and inheritance.

In summary, alternating lists appear as one particular point in a sequence of successive refinements of parametric classes. All examples can be programmed naturally and uniformly with parametric classes. On the opposite, virtual types would show up abruptly in the middle of the sequence. We do not see any problem in extending our treatment of alternating lists to other more complicated but similar patterns, such as parse trees, even though we are not convinced that parse trees are a good use of objects.