SourceForge.net LogoThe Eiffel Compiler / Interpreter (tecomp)

doc/papers/lang/catcall solution

A solution to the catcall problem

Abstract

Eiffel in its current form is not completely type safe. Type errors (called catcalls in Eiffel speak) are possible. The compiler cannot detect these type errors. They usually trigger an exception at runtime.

These type errors are possible due to covariant redefinition of arguments and polymorphy. Both principles are very powerful in OO programming. Other languagues (like java, scala, etc.) solve this problem by disallowing covariant redefinitions of arguments and keeping polymorphy.

Since both, covariant redefinition of arguments and polymorphy, add a lot of power to object oriented programming, a solution to the catcall problem shall keep both, covariance and polymorphy, and rule out the potential type errors.

This paper introduces a solution to the catcall problem by imposing stricter rules and making inheritance more fine granular by keeping the expressiveness of the language.

The proposed solution might at first reading give the impression that it restricts the language too much. Because of that even the author of this paper didn't like the solution at the beginning. But this is due to the fact that the solution will change some coding pattern.

But digging more into the solution, the reader will realize that the solution is rigid in the sense that the compiler can detect all type errors and the software is as concise and expressive as before or better.

The problem

Eiffel allows polymorphic attach and covariant redefinition of arguments. This can lead to type errors.

The type errors which can occur are demonstrated with some examples.

Example 1: COMPARABLE

    deferred class COMPARABLE feature 
       is_less alias "<" (other: like Current): BOOLEAN
          ...
       is_less_equal alias "<=" (other: like Current): BOOLEAN
          ...
    end
 
    expanded class INTEGER inherit COMPARABLE ... end
    class          STRING  inherit COMPARABLE ... end
 
    a,b: COMPARABLE
    ...
    a := 10               -- polymorphic attach
    b := "Hello world!"   -- polymorphic attach
 
    if a < b   -- type error!!!
    then
        ...
 

The expression a < b generates a type error, because the entity a points to an INTEGER and a<b tries to call {INTEGER}.is_less with a STRING argument.

The type error is due to the combination of

  1. implicit covariant redefinition (argument of type like Current) of the inherited features is_less, is_less_equal (inherited from COMPARABLE) within the classes INTEGER and STRING.
  2. polymorphic attach of objects of type INTEGER, STRING to entities of type COMPARABLE
  3. call of a feature on a polymorphic entity with covariantly redefined argument

Example 2: Containers

    class SET[G->COMPARABLE] feature
        has(e:G): BOOLEAN
        extend(e:G)
        ...
    end
 
    s: SET[COMPARABLE]
    ...
    create {SET[INTEGER]} s        -- attachs a SET[INTEGER] object to s
    s.extend("Hello world!")       -- type error!!!
 

The type error is due to the combination of

  1. implicit covariant redefinition (argument of type G) of the feature `extend' within the types SET[INTEGER] and SET[STRING]
  2. polymorphic attach of an object of type SET[INTEGER] to an entity of type SET[COMPARABLE]
  3. call of a feature on a polymorphic entity with covariantly redefined argument

Example 3: Minors and alcoholic beverages

    class BEVERAGE ... end
    class SOFT_DRINK inherit BEVERAGE ... end
    class ALCOHOL    inherit BEVERAGE ... end
 
    class CUSTOMER feature
         drink: BEVERAGE  -- drink which has been served to the CUSTOMER
         serve(b: like drink)  do drink := b end
    end
 
    class MINOR inherit 
         CUSTOMER redefine drink end  
    feature
         drink: SOFT_DRINK
    end
 
    ...
    little_willy: MINOR
    beer: ALCOHOL
    c: CUSTOMER
 
    c := little_willy     -- polymorphic attach
    c.serve(beer)         -- type error: little willy is not allowed
                          -- to drink beer!!!
 

Solution of the problem

Analysis

In all of the above examples the type error is due to

  1. covariant redefinition of arguments
  2. polymorphic attach (inheritance establishes a classical subtype releation in Eiffel)
  3. call of a feature with covariantly redefined arguments

Covariant argument redefinition in subtypes (a subtype relation allows polymorphic attach) violate the Liskov Substitution Principle (LSP). Inheritance with covariant redefinition does not allow that the subtype (descendent) can be substituted in all aspects to an entity of its supertype (parent).

A MINOR is not a CUSTOMER in all aspects, because an arbitrary CUSTOMER can be served all kinds of drinks. MINORs are allowed to be served only SOFT_DRINKs. I.e. a type precondition has been strengthened in the subtype.

An INTEGER is not a COMPARABLE in all aspects, because a COMPARABLE allows to be compared (is_less, is_less_equal) with any other COMPARABLE, but an INTEGER can be compared only with other INTEGERs (this is a direct consequence of declaring an argument with the type like Current.

A SET[INTEGER] is not a SET[COMPARABLE] in all aspects, because SET[INTEGER] allows only INTEGERs to be inserted and SET[COMPARABLE] allows insertion of arbitrary COMPARABLEs.

Solution

The problems is solved by making sure that covariant argument redefinitions and polymorphic attach cannot occur in combination. This is made sure by the following rules

  1. Normal inheritance does not establish a subtype relation, i.e. class C inherit B ... end does not imply that C conforms to B (therefore it is not possible to attach objects of type C to an entity of type B).
  2. Covariant redefintion of arguments under normal inheritance is allowed only with anchored types (like Current, like other_feature).
  3. Conforming inheritance (inherit ->) does not allow covariant redefinitions of arguments. In case of class C inherit -> B ... end all anchored arguments of features of B are deanchored within B before being inherited in C.
  4. Generic constraints can be expressed as G -> C1 (i.e. all actual generics have to conform to C1) or G like C2 (i.e. all actual generics must behave like C2 (i.e. inherit normally from C2 with possibly covariantly redefined arguments).
  5. In general a generic type C[T] does not conform to C[U] even if T conforms to U (i.e. entities of type LIST[ANY] do not make sense any more).
  6. Beside the anchored types `like Current' and `like other_feature' the anchored type `like {G}.some_feature' is possible within generic classes provided that G is a formal generic (this is in some occasions necessary to anchor the type of a local variable or attribute within a container to the result of some query of the formal generic; with that anchoring the type adapts to the corresponding type of the actual generic).

So we have 3 forms of inheritance

  class 
     C
  inherit ->          -- conforming inheritance
     B_CONF
  inherit             -- behavioural/normal inheritance
     B_NORM
  inherit{NONE}       -- secret/implementation inheritance
     B_SECRET
  ...
  end
 

and 2 forms of generic constraints

   class 
       C[
           G -> CONST1,      -- actual generics have to conform to CONST1 
           H like CONST2     -- actual generics have to inherit
                             -- normally from CONST2
        ]
       ...
   end
 

Default inheritance (i.e. if no inheritance clause is present) is `inherit ANY' and the default constraint is like detachable ANY.

With these rules we give up universal conformance. A class which should conform to ANY has to be declared

    class C inherit -> ANY
       ...
    end
 

How to use typesafe Eiffel

Example 1: COMPARABLE

    deferred class COMPARABLE feature 
       is_less alias "<" (other: like Current): BOOLEAN
          ...
       is_less_equal alias "<=" (other: like Current): BOOLEAN
          ...
    end
 
    expanded class INTEGER inherit COMPARABLE ... end
    class          STRING  inherit COMPARABLE ... end
 
    a,b: COMPARABLE
    ...
    a := 10               -- compiler error: INTEGER does not conform
                          -- to COMPARABLE, it only behaves like COMPARABLE
    b := "Hello world!"   -- compiler error: STRING does not conform
                          -- to COMPARABLE
 
    if a < b   -- type error no longer possible
    then
        ...
 

Example 2: Containers

    class 
        SET[G like COMPARABLE] -- conformance is not necessary, G has
                               -- to be like a COMPARABLE
    feature
        has(e:G): BOOLEAN
        extend(e:G)
        ...
    end
 
    s: SET[COMPARABLE]
    ...
    create {SET[INTEGER]} s        -- compiler error:  SET[INTEGER]
                                   -- does not conform to SET[COMPARABLE]
 
    s.extend("Hello world!")       -- type error no longer possible
 

Example 3: Minors and alcoholic beverages

    class BEVERAGE ... end
    class SOFT_DRINK inherit BEVERAGE ... end
    class ALCOHOL    inherit BEVERAGE ... end
 
    class CUSTOMER feature
         drink: BEVERAGE  -- drink which has been served to the CUSTOMER
         serve(b: like drink)  do drink := b end
    end
 
    class MINOR inherit 
         CUSTOMER redefine drink end  
    feature
         drink: SOFT_DRINK
    end
 
    ...
    little_willy: MINOR
    beer: ALCOHOL
    c: CUSTOMER
 
    c := little_willy     -- compiler error: MINOR does not conform to CUSTOMER
 
    c.serve(beer)         -- type error no longer possible
 

Example 4: Polymorphy I: Different implementations of SEQUENCEs

In the above examples conformant inheritance has been avoided in order to allow covariant redefinitions without type errors. Now we look into some classical OO examples using polymorphy with conformant inheritance.

    deferred class SEQUENCE[G] feature
        first: G   deferred end
        last:  G   deferred end
        extend_rear(e: G)   deferred end
        append(other: like Current)
            -- Append `other' after the end of the current sequence.
           do
              -- Implementation can be done here!
           end
        has_equal_elements(other: like Current): BOOLEAN
            -- Does `other' have elements in the same sequence which
            -- are equal to the corresponding elements in `Current'?
           do
              -- Implementation can be done here!
           end
        ...
 

We define now different implementations of SEQUENCEs and we want all implementations to conform to SEQUENCE.

    class 
        ARRAYED_SEQUENCE[G] 
    inherit
        -> SEQUENCE[G]         -- conformant inheritance
    feature
        -- provide implementation for all deferred features
        ...
    end
 

In the same pattern LINKED_SEQUENCE can be written.

With these definitions we can mix freely different implementations of SEQUENCEs without the danger of committing an undetected type error.

    s1,s2: SEQUENCE[STRING]
    s3:    LINKED_SEQUENCE[STRING]
    ...
    s1 := create {LINKED_SEQUENCE[STRING]}
    s2 := create {ARRAYED_SEQUENCE[STRING]}
    s2 := create {ARRAYED_SEQUENCE[STRING]}
 
    s1.extend_rear("Bertrand")
    s1.extend_rear("Emmanuel")
 
    s2.extend_rear("Alexander")
    s2.extend_rear("Eric")
 
    s3.extend_rear("Alexander")
    s3.extend_rear("Eric")
 
    check
       s2.has_equal_elements(s3)
       s3.has_equal_elements(s2)
    end
 
    s1.append(s2)
 
    s2.append(s3)
 

Example 4: Polymorphy II: Rectangles and other shapes

   deferred class SHAPE feature
        draw               deferred end
        move(x,y: INTEGER) deferred end
   end
 
   class RECTANGLE inherit -> SHAPE ... end
   class CIRCLE    inherit -> SHAPE ... end
 
   s: SEQUENCE[SHAPE]
   r: RECTANGLE
   c: CIRCLE
   s1,s2: SHAPE
   ...
   s.extend_rear (r)
   s.extend_rear (c)
   ...
   s[i].draw
   ...
   s[i].move(10,30)
 
   if 
      s.has(r)   -- all SHAPEs have a  `is_equal(other: SHAPE): BOOLEAN'
   then
      ...
   end
 
   s1 := r; s2 := c
   if 
       s1.is_equal(s2) -- no catcall!!
   then
 

General rules for families of polymorphic types

Polymorphic types have to be designed properly. For each family of polymorphic types a common ancestor is needed from which all descendants have to inherit comformantly (i.e. use `inherit -> ANC' instead of `inherit ANCESTOR'). This common ancestor can be ANY.

All descendants must not redefine features with covariant arguments. Arguments of type `like Current' or `like other_feature' have to be replaced by their deanchored form within the common ancestor. If the common ancestor is ANY, all descendants can redefine `is_equal'. But they have to use the signature

    is_equal (other: ANY): BOOLEAN
 

Transition strategy

A compiler implementing type safe Eiffel won't compile code which is written in current Eiffel. Therefore the proposed change to typesafe Eiffel is a breaking change.

But any solution which solves the catcall problem and implements typesafe Eiffel will break code. This is inevitable since in current Eiffel you can write code which encounters type errors at runtime and in typesafe Eiffel this code won't compile.

Even if the change seems to break a lot of code, the adaption to typesafe Eiffel is not as difficult as it looks at first glance.

An Eiffel compiler implementing typesafe Eiffel should implement the new syntactic constructs with the option to a) not check the typesafe rules, b) check them a issue warnings and c) rigidly check the rules.

The most common cases

If you compile current Eiffel code with a compiler for typesafe Eiffel you will get many many compiler errors in all locations where you do polymorphic attaches (due to the fact that normal inheritance is not conforming in type safe Eiffel).

But this compile errors can be removed in (usually) a very limited number of inheritance clauses. Just change `inherit ANC' to `inherit -> ANC' if you need conforming inheritance. Unless you use covariant argument redefinitions with conforming inheritance, your code will probably compile in typesafe Eiffel.

But sometimes it hurts ...

If you have a lot of variables/attributes of type SOME_CONTAINER[ANY] and you throw into these containers arbitrarily INTEGERs, REALs, STRINGs etc. typesafe Eiffel will force you to redesign your structures. All the most common types like INTEGER, REAL, STRING, etc. won't conform any more to ANY.

Summary

The proposed version of typesafe Eiffel solves the catcall problem in a manner that a compiler can detect all potential type errors which might lead to catcalls without any global analysis.

It separates clearly normal inheritance with the possibility to covariantly redefine arguments and conforming inheritance which disallows covariant redefinitions of arguments.

A compiler implementing typesafe Eiffel will break existing Eiffel code. Therefore a transition strategy has been proposed which allows stepwise redesign of existing Eiffel code. It is expected that most redesign have to be done in common libraries (like Eiffel Base). User code will be effected, but probably in a much milder form than the base libraries.

Discussion

Feel free to comment on that topic at http://sourceforge.net/projects/tecomp/forums/forum/1034481.

 Local Variables: 
 mode: outline
 coding: iso-latin-1
 fill-column: 70
 outline-regexp: "=\\(=\\)*"
 End:
Table of contents

- Abstract

- The problem

- Example 1: COMPARABLE

- Example 2: Containers

- Example 3: Minors and alcoholic beverages

- Solution of the problem

- Analysis

- Solution

- How to use typesafe Eiffel

- Example 1: COMPARABLE

- Example 2: Containers

- Example 3: Minors and alcoholic beverages

- Example 4: Polymorphy I: Different implementations of SEQUENCEs

- Example 4: Polymorphy II: Rectangles and other shapes

- General rules for families of polymorphic types

- Transition strategy

- The most common cases

- But sometimes it hurts ...

- Summary

- Discussion


ip-location