Type safe Eiffel

by Helmut Brandl (modified: 2010 Oct 25)

The following is a short description of a solution to the catcall problem (recently posted in comp.lang.eiffel as well):

In Eiffel it is easy to generate runtime type errors. Therefore Eiffel cannot (yet) be considered to be a typesafe language. A modern Eiffel shall be typesafe.

A runtime type error (called catcall in Eiffel speak) can happen because Eiffel has

a) Polymorphic attach

b) Covariant redefinition or routine arguments

c) Promiscuous generic conformance

Polymorphic attach (a) is at the heart of object orientation in all OO languages. The textbook example is a graphic library with an abstract base class SHAPE and some concrete descendants like RECTANGLE, CIRCLE, ELLIPSE, TRIANGLE, POLYGON, etc.

Eiffel is the only language (at least I don't know another language) which allows covariant redefinitons of arguments (b) usually in the form of anchored declarations like

  deferred class COMPARABLE feature
     is_less alias "<" (o:like Current)
     ...
  end.

which adds a lot of reuse possibitlities and expressiveness.

However with (a) and (b) lead to type errors like

  a,b: COMPARABLE
  ...
  a := "Hello" -- possible because STRING conforms to COMPARABLE
  b := 1       -- possible because INTEGER conforms to COMAPARABLE
  if
    a < b     -- runtime type error!!
  then
    ...
  end

With promiscuous generic conformance (c) another class of type errors are possible, e.g.

  s: ARRAYED_SEQUENCE[COMPARABLE]
  s_int: ARRAYED_SEQUENCE[INTEGER]
  i: INTEGER
  ...
  create s_int
  s := s_int
  ...
  s.extend_rear(1)
  s.extend_rear("Hello")
  ...
  i := s_int[1] + s_int[2]  -- runtime type error

This problem is shared by other languages like C++ and Java which allow promiscuous generic conformance as well.

A solution has been sought since the beginning of Eiffel. Bertrand already stated the catcall problem (combination of (a) and (b)) in his book object oriented software construction very clearly. Many solutions have already been proposed but none of these has been satisfactory.

But the solution is very simple. Bertrand has already given the key idea of the solution in his OOSC book. Polymorphic attach and covariant redefinitions of arguments in combination can lead to type errors. Neither polymorphic attach nor covariant redefinition alone is problematic, only the combination.

The only problem to solve: Disallow the combination of polymorphic attach and covariant redefinition in combination. Since both come with inheritance we need 2 forms of inheritance. One that allows polymorphic attach of an object to its parent class but disallows covariant redefintion of arguments and one form of inheritance which disallows polymorphic attach and allows covariant redefinitions. The former can be expressed with "inherit ->" and the latter with "inherit" (just a proposal, another syntax is possible as well). E.g.

 class                     class
   RECTANGLE                 INTEGER
 inherit ->                inherit
   SHAPE                     COMPARABLE
 ...                       ...
 end                       end

With that distinction everything is fine for (a) and (b). The solution is so simple and clear. But it has some consequences which some might not like.

1. Universal conformance is no longer possible

2. Constrained genericity has to be adapted

The definition of the class ANY leads to implicit covariant redefinition of arguments of all its descendants due to the signature

  is_equal (other: like Current): BOOLEAN

Therefore no class can "inherit ->" from ANY. But is this a problem? I mean a real problem? Is it really necessary that we have a type to which all objects can be attached and is that type necessarily ANY? Most will answer "yes" to all that questions. This is the main obstacle for a modern type safe Eiffel.

But the answer is "no". It is not a real problem. All things which can be achieved by universal conformance to ANY can be achieved by other means.

The second impact on constrained genericity can be resolved be expressing the constraints in the same two manners as inheritance, e.g.

  class CG1[G -> CONFORMANT_CONSTRAINT]  ... end
  class CG2[G: like COVARIANT_CONSTRAINT]   ... end

(or the difference expressed the by another syntactic construct).

If the user wants to express a constraint he usually means the second form. There is rarely the need that formal generic must be attached to its constraint. The main reasons for the constraint is to express which features can be called on formal generics.

The last form (c) of runtime type errors can be solved by forbidding generic conformance (or using a more disciplined one like e.g. scala has).

There is one strong argument against type safe Eiffel:

 It is not backward compatible!!!

But: A type safe Eiffel which is backward compatible does not seem to possible.

Main reason: ISE Eiffel can generate runtime type errors, type safe Eiffel makes runtime type errors impossible. Therefore a compiler of type safe Eiffel cannot compile programs written in ISE Eiffel.

For details see also the white paper at http://tecomp.sourceforge.net -> white papers -> catcall solution

Comments
  • Peter Gummer (6 years ago 26/10/2010)

    Non-conforming inheritance

    Helmut, part of your proposal is to change the semantics of the unqualified inherit keyword, to mean a "form of inheritance which disallows polymorphic attach and allows covariant redefinitions."

    Isn't this the same as non-conforming inheritance? Eiffel already has this, although the syntax differs from your proposal: inherit {NONE}.

    • Helmut Brandl (6 years ago 26/10/2010)

      In the current state of the discussion the concrete syntax I have proposed is not the important thing for me. I have used "inherit ->" and "inherit" to express semantics which are different from the usual "inherit" and "inherit {NONE}".

      It is also possible to reuse the current syntax "inherit {NONE}", but the current semantics of "inherit {NONE}" is not sufficient to achieve the same. E.g. you must enforce the proper use of select clauses in case of repeated inheritance to be able to use the parent (or ancestor) as a generic constraint.

      The "inherit ->" in my proposal is more restrictive that the usual "inherit" in ISE Eiffel. It not only disallows covariant redefinitions, it deanchores all anchored argument types.

      In order to express the different semantics I have used different syntax. I have kept the plain "inherit" from ISE Eiffel, because it is nearly the same, it just disallows polymorphic attach.

      For details see my white paper at http://tecomp.sourceforge.net.

      • Peter Gummer (6 years ago 27/10/2010)

        Non-conforming inheritance

        Helmut, I did not ask you about syntax.

        My question was, isn't your proposed new semantics for the unqualified inherit keyword the same as non-conforming inheritance?

        You've hinted that the answer to my question might be no, but I still can't see a difference.

        • Helmut Brandl (6 years ago 27/10/2010)

          Non-conforming inheritance

          Sorry, if I haven't explained it well (for details and more examples see also http://tecomp.sourceforge.net/index.php?file=doc/papers/lang/catcall_solution.txt)

          The semantics of ISEs "inherit {NONE}" and my proposals "inherit" is definitely not the same.

          My proposals "inherit" (i.e. if you have class C inherit A ... end):

          - Resolves all ambiguities with repeated inheritance, i.e. it requires proper select clauses in case of ambiguities. In ISEs "inherit {NONE}" ambiguities with repeated inheritance are not a problem.

          - The parent can be used as a constraint in formal generics, i.e. you can write "class CG[G: like A] ... end". In ISEs "class C inherit {NONE} A" you cannot write "class CG[G->A] ... end" and use CG[C] as a type, because C does not conform to A. That is the problem with ISEs generic constraint: The requirement for an actual generic to conform to its constraint is an overkill. It is usually not necessary. You just want to have the guarantee that the actual generic has the same features and same contracts as the constraint, i.e you want the actual generic to "behave like the constraint".

          - You cannot do descendant hiding. In ISEs "inherit {NONE}" you can do descendant hiding.

          To summarize:

          - "inherit {NONE}" is the weakest form of inheritance, sometimes called "implementation inheritance" or "facility inheritance".

          - my "inherit" is the mostly used form of inheritance (it is kind of "is-a" relationship, without the possibility of polymorphic attach, but all possibilities of covariant redefinition and no ambiguities in the inheritance relation).

          - my "inherit ->" is the strongest form of inheritance, it allows polymorphic attach and forbids therefore covariant redefintions to avoid runtime type errors.

          In my opinion all three forms of inheritance are reasonable. ISE does not distinguish between "inherit" and "inherit ->". You can regard my proposal as a split of ISEs "inherit" in two different forms of inheritance. If three forms are too many, the first one should be dropped.

          • Peter Gummer (6 years ago 27/10/2010)

            That's clearer, thanks

            Perhaps I would have understood the distinction you're making if I had read your white paper ;-)

            The concepts of conformance, the "is-a" relationship and polymorphism are tightly welded in my mind. I think I would find it a challenge to distinguish these concepts in everyday coding.

            I guess that we would always use "inherit" when writing classes, allowing compiler errors to alert us to the fact that a client class is attempting a disallowed polymorphic attachment. Then we would probably go back to the class and change it to "inherit ->". This would be doable, assuming that the class didn't have any covariant redefinitions, only if the class belonged to us; if the class was in someone else's library (e.g., ISE or Gobo) then we would be stuck. We'd have to redesign what we were doing to avoid polymorphic attachment. So maybe the authors of class libraries should always use "inherit ->", where possible within the library, in order to prevent such frustrations for their clients.

            • Helmut Brandl (6 years ago 27/10/2010)

              your remarks

              1. tightly welded: I am sure once you get used to it, it will become second nature to distinguish the concepts. The key question: Is the heir a real subclass, i.e. can it be substituted or does it just behave like the parent.

              2. libraries: I dont think it is a problem. Try to find examples where it is unclear whether to use "inherit" or "inherit ->". I have not yet found any

              class INTEGER inherit COMPARABLE -- no subtype relation NUMERIC -- no subtype relation ... end class RECTANGLE inherit -> SHAPE -- a subtype relation end class LINKED_LIST inherit -> LIST -- a subtype relation ... end class TWO_WAY_LIST inherit -> LIST inherit LINKED_LIST -- not a subtype relation -- covariant redeclaration of LINKABLE to BI_LINKABLE allowed -- arguments can have type `like first_cell' ... end

              Try to think it through with some examples. I am quite sure that the distinction becomes quite natural once used to it.

              • Manu (6 years ago 27/10/2010)

                INTEGER not a subtype relation from NUMERIC and COMPARABLE! I'm afraid that you are wrong, there is code out there that does exactly that.

                • Helmut Brandl (6 years ago 27/10/2010)

                  show me whats wrong

                  Hello Manu,

                  it is easy to critisize in "one sentence remarks". Give me examples of code which cannot be done in the type safe manner I have described.

                  Note: I have not said that INTEGER does not inherit in a visible way from NUMERIC and COMPARABLE. I have just said that an INTEGER cannot be attached to an entity of type NUMERIC or COMPARABLE any more. Look at my examples in the original post. Attaching INTEGER to COMPARABLE makes runtime type errors possible. I am afraid that all examples you can give me have the inherent risk of runtime type errors and are therefore not typesafe. But let's see, if you can come up with an example which cannot be coded well with my proposal and is type safe.

                  Note: I have already indicated that the change is NOT backward compatible. If this is a killing point for you, I accept that. But then the logic of your argument is "it is not backward compatible, therefore you are wrong". But with the same logic void safety is wrong as well (which we both agree that it is not).

                  • Manu (6 years ago 28/10/2010)

                    I've seen code that do: LIST [NUMERIC] := LIST [INTEGER]. My understanding is that you would disallow that and this is just bad.

                    As for breaking changes, all of them are bad and it is always a trade-off. Void-safety positive aspects currently outweigh the negative aspects. Most people realize that they can still have code that compiles with or without void-safety, providing a smooth migration to void safety.

                    Clearly changing the meaning of `inherit' is not a good thing as I cannot see how to achieve backward compatibility which is needed if Eiffel wants a chance to keep its current users. Alienating users is not a good thing and we learned that a long time ago.

                    • Helmut Brandl (6 years ago 30/10/2010)

                      Backward compatibility

                      It easy to achieve migration in the same manner as you have done with void safety. Just introduce in the compiler the new semantics and have an option not to check type safety rigidly (maybe just output a warning or whatever you choose appropriate). With that option all old code will compile out of the box. In addition you can have an option to check type safety rigidly. So smooth migration is possible.

                      The problem with LIST[NUMERIC] := LIST[INTEGER]: This construct is inherently unsafe. I dont know what is your way to make it typesafe. Even in your proposal you have made with Bertrand you proposed to forbid that unless there is some "variant" annotation!

                • Peter Gummer (6 years ago 28/10/2010)

                  We rely on INTEGER being a subtype of NUMERIC

                  See the classes here:

                  http://www.openehr.org/svn/ref_impl_eiffel/BRANCHES/adl1.5/libraries/openehr/src/rm/data_types/quantity

                  In particular, DV_QUANTIFIED.magnitude, which is NUMERIC and is redefined in various descendant classes in the same cluster as INTEGER or DOUBLE.

                  • Helmut Brandl (6 years ago 7/11/2010)

                    subtype

                    Hello Peter, sorry for responding so late. I have been away from the internet for 2 weeks.

                    Having DV_QUANTIFIED.magnitude as NUMERIC and redefine it to descendants to INTEGER or DOUBLE is not a problem for type safety. This by itself causes no need that INTEGER and DOUBLE *conform* to numeric. Having the same behaviour is enough.

                    Typesafety problems arise as soon as you do arbitrary attachments and you get one NUMERIC entity attached to an INTEGER and another to DOUBLE and start mixing the types arbitrarily. Typesafe Eiffel has to disallow this kind of undisciplined attachments.

  • Fernando Pelliccioni (5 years ago 1/2/2012)

    Promiscuous Generic Conformance

    "...This problem is shared by other languages like C++ and Java which allow promiscuous generic conformance as well...."

    It is not true, C++ doesn't allows Promiscuous Generic Conformance

    See ...

    The Design and Evolution of C++ of Bjarne Stroustrup

    15.9 Template Class Relationships (Page 360)
    "... thinking of Set<Circle> as a Set<Shape> is a fundamental conceptual error. 
    In particular, Set<Circle> guarantees that its members are Circles, so that users 
    can safely and efficiently apply Circle-specific operations, such as determining 
    the radius, on its members. If we allowed a Set<Circle> to be treated as a 
    Set<Shape>, we could no longer maintain that guarantee because it is presumably 
    acceptable to put arbitrary Shapes such as Triangles into a Set<Shape>..."

    http://www.amazon.com/Design-Evolution-C-Bjarne-Stroustrup/dp/0201543303

    • Helmut Brandl (4 years ago 4/6/2012)

      Thanks for the hint

      Fernando,

      you are absolutely right. C++ forbids promiscuous generic conformance and I think this is a very good design decision. Unfortunately Eiffel allows it. The more I think about it the more am I convinced that promiscuous generic conformance needs to be considered invalid (as stated in my blog entry).

  • Victorien Elvinger (5 years ago 29/4/2012)

    Type safe with type contol

    And why not to need a type control when the type error can appear?

    In void safety we must test the state (attached or detached) of the detachable variables to do a call.

    We can do the same way. ie impose a type control when an anchor is used.

    For example :

    a.is_equal (b) is a compilation error

    while

    if a.same_type (b) then

       a.is_equal (b)

    end

    is conform.