**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.

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.

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.

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.

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; |

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 |