Abstract Classes and Subtyping: Inheritance Part B

  Sather separates the concept of inheritance into subtyping and code inclusion. Code inclusion is achieved as we have seen in the previous section. It may be regarded as a purely syntactic operation that introduces no run-time relationship between the includor and includee classes. In order to specify typing relationships, Sather uses abstract classes. We will first define an example abstract class and then go on to show how concrete classes such as MANAGER and EMPLOYEE can be related to these abstract classes.

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;
This abstract type definition merely states that any employee must have a name and an id. The body of abstract type definitions consists of a semi-colon separated list of abstract signatures. Each specifies the signature of a routine or iter without providing an implementation. The argument names are for documentation purposes only and do not affect the semantics. The abstract_signatures of all types listed in the subtyping clause are included in the interface of the type being defined. Explicitly specified signatures override any conflicting signatures from the subtyping clause. If two types in the subtyping clause have conflicting signatures that are not equal, then the type definition must explictly specify a signature that overrides them. The interface of an abstract type consists of any explictly specified signatures along with those introduced by the subtyping clause. We will now see how these abstract classes, which have no implementation, can be used to specify relationships between classes.

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
See EMPLOYEE definition
class MANAGER < $EMPLOYEE is ...
   -- Manager as defined in the chapter on concrete types
See MANAGER definition

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;
The main program shows that we can create an array that holds either regular employees or managers. We can then perform any action on this array that is applicable to both types of employees. The "wage" routine is said to be "dispatched". At compile time, we don't know which wage routine will be called. At run time, the actual class of the object held by the "emp" variable is determined and the "wage" routine in that class is called.

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";
Within each branch of the typecase, the variable has the type of that branch.

     

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;
The question now is, what are the legal signatures for "rout" in any subtype of $SUPER, say $SUB. The Sather rule says that the arguments to rout in $SUB must either be the same as, or supertypes of the arguments in $SUPER (contra-variant). The return value must either be the same as or a subtype of the return value in $SUPER (co-variant). Hence, the following signatures are all legal choices.
        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;
The following types are ILLEGAL
    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;
and we have a variable "abstract_super"
        abstract_super: $SUPER := #SUB;
Since "abstract_super" can hold any subtype of $SUPER, it can actually be instantiated to some SUB object. Now suppose we call the routine "rout" on the variable "abstract_super".
        actual_high: $HIGH;   -- the actual object held is of type $HIGH
        res: $HIGH := abstract_super.rout(actual_high)
From looking at the signature of the decared type of "abstract_super",
        type $SUPER is .... rout(arg: $HIGH): $HIGH
this looks perfectly ok, since $SUPER::rout can take arguments of type $HIGH. But the call actually goes to the routine in SUB
        SUB::foo(arg: $LOW): $HIGH;
And it is illegal to call this routine with a $HIGH as argument (it is not a subtype of $LOW)! There is no way to detect this problem at compile-time. However, a run-time check may be used.

       

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;
The need for supertyping clauses arises from our definitition of type-bounds in parametrized types. Any instantiation of the parameters of a parametrized type must be a subtype of those typebounds. You may, however, wish to create a parametrized type which is instantiated with existing library code which is not already under the typebound you want. For instance, suppose you want to create a class FOO, whose parameters must support both is_eq and is_lt. One way to do this is as follows:

 
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;
Thus, supertyping provides a convenient method of parametrizing containers, so that they can be instantiated using existing classes. An alternative approach is the structural conformance rule that Sather-K uses.



Benedict A. Gomes
Mon Apr 29 10:12:43 PDT 1996