Abstract Classes and Subtyping: Inheritance Part B

Abstract Type Definitions

$EMPLOYEE illustrates an abstract type. EMPLOYEE and MANAGER are subtypes. Abstract type definitions specify interfaces without implementations. Abstract type names must be entirely uppercase and must begin with a dollar sign $. Below, we will illustrate how the abstract type may be used.

type $EMPLOYEE is
   -- Definition of an abstract type.  Any concrete class that subtypes
   -- from this abstract class must provide these routines.
    name: STR;
    id: INT;
end;

Abstract types can never be created! Unlike concrete classes, they are *not* object definitions. All you can do with an abstract type is to declare a variable to be of that type. Such a variable can point to any actual object which is a subtype of that abstract class. How we determine what objects such an abstract variable can point to is the subject of the next section.

Subtyping: Inheritance Part B

As promised, here is the other half of inheritance. Subtyping between an abstract and a concrete class or between two abstract classes, introduces a subtyping relationship between the parent and the child classes. We can then define a variable to be of the type of the abstract parent - the variable can hold an actual object which is of the type of any of the children.

class EMPLOYEE < $EMPLOYEE is ...
   -- Employee, as defined in the chapter on concrete types

class MANAGER < $EMPLOYEE is ...
   -- Manager as defined in the chapter on concrete types

class TESTEMPLOYEE is

     main is
        employees: ARRAY{$EMPLOYEE} := #ARRAY{EMPLOYEE}(3); -- 3 element array
        i:INT := 0; wage: INT := 0;
        loop until!(i = employees.size);
             emp: $EMPLOYEE := employees[i];
             emp_wage: INT := emp.wage;    -- Dispatched call to "wage"
             wage := wage+emp_wage;
        end;                                                                
        #OUT+wage+"\n";
     end;
end;

Typecase

In some cases, we want to know the actual concrete type an abstract variable holds, which can be done by using the "typecase" statement. For instance, suppose we want to know the total number of subordinates in an array of general employees.

    peter ::= #EMPLOYEE("Peter",1);  -- id = 1
    paul ::= #MANAGER("Paul",12,10); -- id = 12,10 subordinates
    mary ::= #MANAGER("Mary",15,11); -- id = 15,11 subordinates                
    employees: ARRAY{$EMPLOYEE} := |peter,paul,mary|;
    totalsubordinates: INT := 0;
    loop employee: $EMPLOYEE := employees.elt! 
                -- An iterator that yields sucessive employees
        typecase employee 
        when MANAGER then 
           totalsubordinates := totalsubordinates + employee.numsubordinates;
         else  end; -- Do nothing.
    end;
    #OUT+"Number of subordinates:"+totalsubordinates+"\n";

Type Conformance

Sather's subtyping rule is called contravariance. It is sometimes referred to as conformance or generalization. The nature of the subtyping rule gives rise to periodic newgroup religious battles, usually phrased as covariance vs. contravariance. The contravariant rule is quite simple, and a bit counter-intuitive at first.

        type $HIGHER is ... some definition end;     
        type $HIGH < $HIGHER is ... some definition ... end;
        type $LOW < $HIGH is ... some definition ... end;
        type $SUPER is
            rout(a: $HIGH): $HIGH;
        end;

        type $SUB < $SUPER is    rout(a: $HIGH): $HIGH;     end;
        type $SUB < $SUPER is   rout(a: $HIGH): $LOW;      end;
        type $SUB < $SUPER is   rout(a: $HIGHER): $HIGH;      end;
        type $SUB < $SUPER is   rout(a: $HIGHER): $LOW;      end;

    type $SUB < $SUPER is    rout(a: $LOW): <any return value>;     end;

In practice, the argument types are almost always the same type (invariant, which is the C++ rule). There are certain unusual situations in which contravariance of arguments is useful. The return types are quite often subtypes.

The reason for this rule is that it is THE ONLY STATICALLY TYPESAFE RULE (invariance, as in C++, is a special case of this rule). Pure covariance is NOT statically typesafe. This is a bit hard to understand. Consider a variable foo of type $SUPER and suppose we had defined a class SUB in the ILLEGAL covariant manner.

        class SUB < $SUPER is 
                rout(arg: $LOW): $HIGH;

        abstract_super: $SUPER := #SUB;

        actual_high: $HIGH;   -- the actual object held is of type $HIGH
        res: $HIGH := abstract_super.rout(actual_high)

        type $SUPER is .... rout(arg: $HIGH): $HIGH

        SUB::foo(arg: $LOW): $HIGH;

Covariance vs. Contravariance.

Periodically a co vs. contra-variance argument flares up on the net. The arguments are usually very involved and (imho) not worth following. They often revolve around whether cows are truly herbivores or some such detail of the animal kingdom. Below, I will attempt to briefly describe the technical aspect of the argument - the relative typesafety of both systems.

First some terms. This argument is purely about argument types (there is no disagreement about return types). Hence, the term contravariance is often used instead of conformance. The basic argument arises because Eiffel follows the covariant rule for arguments while Sather is contravariant (and other languages like C++ are invariant). At issue is whether both rules are statically typesafe.

You will frequently hear claims by the Eiffel people that their system uses the more natural covariance rule and is still statically typesafe due to a "closed-system" checking algorithm, which is not yet implemented in the Eiffel compilers (someone correct me if I'm wrong). And the conformance sceptics will say - not possible - that's undecidable (I can give you a somewhat handwavy, but basically correct argument to this effect). The two sides mean slightly different things by "type-safe", and I believe that the contravariant side is clearer. The truth is that the closed system type checker promised by Eiffel is conservative. This means that perfectly legal function calls may be rejected by the algorithm because it cannot prove that the call is typesafe. The undecidablity argument shows that however good the algorithm, since the problem is inherently undecidable, it will always be possible (quite easy, actually) to show that statically legal function calls will be rejected. What this can lead to is groups of people just turning off the type safety check, since they believe that their program is ok, even though the system cannot prove it. If this happens, all static typesafety is lost.

With contravariance, on the other hand, any legal function call (based just on the signatures, and not on some arbitrary property of the computation involved) will be accepted by the compiler and will be typesafe. If covariant behaviour is required, it must be obtained by a typecase within the routine body. This clearly indicates the only points at which a type violation may occur within a program.

Supertyping

What is the rationale behind supertyping clauses, and how are they used ?

You define supertypes of already existing types. The supertype can only contain routines that are found in the subtype i.e. it cannot extend the interface of the subtype.

        type $IS_EMPTY{T} > FLIST{T}, FSET{T} is
           is_empty: BOOL;
        end;

 
class BAR{T}  is
        -- Library class that you can't modify
   is_eq(o: T): BOOL;
   is_lt(o: T): BOOL;
end;
type $MY_BOUND{T} > BAR{T} is
    is_eq(o: T): BOOL;
    is_lt(o: T): BOOL;
end;
class FOO{T < $MY_BOUND{T}} is
   some_routine is
        -- uses the is_eq and is_lt routines on objects of type T
        a,b,c: T;
        if (a < b or b = c) then
                ..
        end;
  end;
end;