|| 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]4. 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
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
distinguish from conses. Actually, it is convenient to give the class
nil the same interface as the class
typically used to end a chain of conses in a binary tree or a list.
class ['a, 'b] nil = object
method null = true method car : 'a = raise Null method cdr : 'b = raise Null
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
leaving the code unchanged.
The type constraint can be enforced in subclasses of
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
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.