Chapter 5. Abstract Classes and Subtyping

Table of Contents
5.1. Abstracting over Implementations
5.2. Abstract Class Definitions
5.3. Subtyping
5.4. Supertyping
5.5. Type Conformance
5.6. The typecase statement
5.7. The Overloading Rule
5.8. When Covariance Ails You

Abstract class definitions specify interfaces without implementations. Abstract class names must be entirely uppercase and must begin with a dollar sign '$' ; this makes it easy to distinguish abstract type specifications from other types, and may be thought of as a reminder that operations on objects of these types might be more expensive since they may involve dynamic dispatch. In order to motivate the notion of abstract classes, we will start by considering different implementations of a data structure.

5.1. Abstracting over Implementations

We will illustrate the need for abstraction by considering the implementation of a classic data structure, the stack. Objects are removed from a stack such that the last object to be inserted is the first to be removed (Last In First Out). For the sake of simplcity, we will define our stack to hold integers.

5.1.1. Implementing a Stack using an Array

The obvious implementation of a stack is using an array and a pointer to the top of the stack. When the stack outgrows the original array we allocate, we double the size of the array and copy the old elements over. This technique is known as amortized doubling and is an efficient way to allocate space for a datastructure whose size is not known when it is created.
class ARR_STACK is
   private attr elems:ARRAY{INT};
   private attr index:INT; -- Points to the next location to insert

   create:SAME is
      res ::= new;
      res.elems := #ARRAY{INT}(5);
      res.index := 0;
      return res;
   end;

   push(e:INT) is
      if index > elems.size then
         new_elems:ARRAY{INT} := #ARRAY{INT}(index * 2);
         -- copy over the old elements
         loop
            new_elems.set!(elems.elt!);
         end;
         elems := new_elems;
      end;
      elems[index] := e;
      index := index + 1;
   end;

   pop:INT is
      index := index - 1;
      return elems[index];
   end;

   is_empty:INT is
      return index = 0;
   end;
end;

It would be appropriate to also shrink the array when elements are popped from the stack, but we ignore this complexity for now.

5.1.2. A Stack Calculator

The stack class we defined can now be used in various applications. For instance, suppose we wish to create an calculator using the stack
class RPN_CALCULATOR is
   private attr stack:ARR_STACK;

   create:SAME is
      res ::=new;
      res.stack := #ARR_STACK;
      return res;
   end;

   push(e:INT) is
      stack.push(e);
   end;

   add:INT is
      -- Add the two top two eleemnts
      if stack.is_empty then
         empty_err;
         return 0;
      end;
      arg1:INT := stack.pop;
      if stack.is_empty then
         empty_err;
         return 0;
      end;
      arg2:INT := stack.pop
      return arg1 + arg2;
   end;

   private empty_err is
      #ERR + "No operands available!"
   end;
end;

This corresponds to a H-P style reverse polish notation calculator (RPN) where you first enter operands and then an operator.

5.1.3. A Linked List Representation of a Stack

An alternative implementation of a stack might make use of a chain of elements i.e. a linked list representation. Each link in the chain has a pointer to the next element
class STACK_ELEM_HOLDER is
   readonly attr data:INT;
   attr next:INT_STACK_ELEM;

   create(data:INT):SAME is
      res ::= new;
      res.data := data;
      res.next := void;
      return res;
   end;
end;

The whole stack is then constructed using a chain of element holders.
class LINK_STACK is
   private attr head:STACK_ELEM_HOLDER;
   create:SAME is  res ::= new; return res; end;

   push(e:INT) is
      elem_holder ::= #STACK_ELEM_HOLDER(e);
      elem_holder.ext := head;
      head := elem_holder;
   end;

   pop:INT is
      res:INT := head.data;
      head := head.next;
   end;

   is_empty:BOOL is
      return void(head);
   end;
end;

5.1.4. Switching Representations:Polymorphism

Each of these stack implementations has advantages and disadvantages (the trade-offs are not very significant in our example, but can be quite considerable in other cases). Either of these stacks could be used in our calculator. To use the linked list stack we would need to replace ARR_STACK by by LINK_STACK. wherever it is used.

It would be nice to be able to write code such that we could transparently replace one kind of stack by the other. If we are to do this, we would need to be able to refer to them indirectly, through some interface which hides which particular implementation we are using. Interfaces of this sort are described by abstract classes in Sather. An abstract class that describes the stack abstraction is
abstract class $STACK is
   create:SAME;
   push(e:INT);
   pop:INT;
   is_empty:BOOL;
end;

Note that the interface just specifies the operations on the stack, and says nothing about how they are implemented. We have to then specify how our two implementations conform to this abstraction. This is indicated in the definition of our implementations. More details on this will follow in the sections below.
class ARR_STACK < $STACK is ... same definition as before ...

class LINK_STACK < $STACK is ... same definition as before ...

The calculator class can then be written as follows
class RPN_CALCULATOR is
   private attr stack:$STACK;
   create(s:$STACK):SAME is
      res ::= new;
      res.stack := s;
      return res;
   end;

   ... 'add' and 'push' behave the same
end;

In this modified calculator, we provide a stack of our choice when creating the calculator. Any implementation that conforms to our stack abstraction my be used in place of the array based stackt
s:LINK_STACK := #LINK_STACK;
calc:RPN_CALCULATOR := #RPN_CAlCULATOR(s);
calc.push(3);
calc.push(5);
#OUT + calc.add;          -- Prints out 8