Type safe Eiffel (1)

by Helmut Brandl (modified: 2011 Jul 04)

From the beginning of Eiffel the language has been characterized as strongly typed. But since its beginning there has been a hole in the type system which has not yet been fixed up to now (the so called catcall problem).

What is the hole?

The existence of the hole can be demonstrated with very simple examples. There is a class COMPARABLE defining the basic comparison operators "<", "<=", ">", ">=". The class COMPARABLE is an ancestor of types like INTEGER, REAL, STRING, ..., i.e. all types which would be characterized by a mathematician as having an order-relation.

The code snippet

local i: COMPARABLE s: COMPARABLE do i := 1 -- an INTEGER is COMPARABLE s := "Hello world." -- a STRING is COMPARABLE if i < s -- catcall !! then ... end end

is legal Eiffel, but produces a catcall with the expression "i < s", because it tries to compare an object of type INTEGER with an object of type STRING. Unfortunately the question "Is 1 less than "Hello world."" has no answer and the runtime has to react with an exception.

What happened here? The class COMPARABLE is defined like

deferred class COMPARABLE feature is_less alias "<" (other: like Current): BOOLEAN deferred end ... end
The class INTEGER implements (i.e. effects) the routine "is_less" and expects an INTEGER argument. In the code snippet above it didn't get an INTEGER, but it got a STRING which is not conformant to INTEGER.

Another example:

local a: ARRAY[STRING] aa: ARRAY[ANY] do create a.make (1,2) a[1] := "Hello world." aa := a -- an ARRAY[STRING] conforms to ARRAY[ANY] aa[2] := 1 -- catcall !! end

The array attached to "aa" is still an ARRAY[STRING]. But since the static type of "aa" is ARRAY[ANY], the assignment "aa[2]:=1" is legal Eiffel. Putting an INTEGER into a place, where a STRING is expected can only result in a runtime exception.

ECMA Eiffel (like all its predecessors) says an ARRAY[STRING] "is a" ARRAY[ANY]. But it is **not**. Into an ARRAY[STRING] you can put only strings or something conformant to strings, into an ARRAY[ANY] you can put anything.

Why has it not yet been solved?

To the inventor of Eiffel the problem has been known for a long time. In the book "Object Oriented SW Construction" (OOSC2, 1992) Bertrand Meyer analyzed and explained the problem. Since then, some solutions have already been proposed, but none of them has been satisfying.

Surely some bright people have tried to solve the problem. If bright people have not resolved the problem for more than 15 years, does that mean that the problem has no solution?

But the problem has solutions. In OOSC2 Bertrand Meyer explained, that catcalls only happen when polymorphic attach (attach a descendant to an ancestor, i.e. the "is_a" relation) and covariant redefinition (e.g. arguments of type "like Current) come together.

So if you forbid polymorphic attachs or covariant redefinitions you have a solution which makes catcalls impossible.

Unfortunately this is not a satisfactory solution. The former would rob Eiffel of one of the most powerful mechanisms in object orientation (dynamic bind), the latter one would make classes like COMPARABLE (i.e. partial implementations) impossible.

Therefore a satisfactory solution has to retain polymorphy and covariance.

But neither polymorhy nor covariance are all-or-nothing constraints. The boil down to a lot of explicit or implicit constraints. These constraints define the space, where a solution has been searched for. Since no satisfactory solution (a solution which does not violate the constraints) has been found up to now, it seems that the solution space which the constraints define might be empty.

It might be like a student of mathematics who tries to solve a problem with 4 equations and 3 unknowns where each equation stands for a constraint. Using 3 of the constraints he comes up with a solution. Unfortunately the solution does not satisfy the 4th constraint.

Hypothesis: There are too many or too strong constraints (explicit or implicit). Finding a solution implies modifying (i.e. weakening) or getting rid of some constraints.

What can we do? I propose to make all the constraints explicit and discuss them. Let us formulate the constraints as fine grained as possible in order to find an acceptable modification to the constraints, i.e. let us scrutinze the potential solution space with the goal to find a non empty solution space.

The definition of the solution space will require some decisions. Once having a non empty solution space at least one or possibly more solutions will show up (hopefully).

From my analysis up to now the following constraints are used to find the problem. They will be discussed in the following sections in order to find out in which manner we can modify them.

Constraints:

  1. Universal conformance (UC)
  2. Feature rich ANY (FRA)
  3. Covariance (COV)
  4. Backward compatibility (BC)
  5. Promiscuous generic conformance (PGC)
  6. Generic constraints based on conformance (GCC)
  7. Validation with local analysis (VLA)
  8. ...

Maybe the list will become longer and/or more fine grained during thediscussion.

Analysis of the constraints

Universal conformance (UC)

Universal conformance means that all types conform to ANY. The type graphhas a unique top. Any object in your system can be attached to an entity oftype ANY.

This can lead to some holes in the type system together with features ofANY which have implicit covariant signatures like is_equal and copy with anargument of type "like Current". We can demonstrate the problem with aslight modification of one of the above examples

local i: ANY s: ANY do i := 1 s := "Hello world." if i.is_equal (s) -- catcall !! then ... end end

One of the arising questions is: Is it really necessary that all thingsconform to ANY?

What is the advantage and disadvantage of having universal conformance?

Java has universal conformance (class Object) and C++ has no universalconformance. Smarteiffel has chosen liberal way. You can have conformanceto ANY or not. It is up to the designer.

Discussion of UC:

UC gives us the possibility of having just an object. You can designclasses which store any type of object. You can store it and move it around(i.e. its reference).

As soon as you retrieve it, you cannot do a lot with it unless you find outwhat type of object it is. With an object test you have to "downcast" theobject to do something meaningful with it.

Having UC is some kind of convenience. If you don't have UC you can alwaysgive a group of types a common conformant ancestor type to store them andmove them around. This has the advantage of being able to call some commonfeatures of this group of types and assuring that only conformantdescendants of the base type can be stored in a container class.

The opponents of UC sometimes argue that using ANY is just lack ofdesign. If want to treat a group of types in a common way, design someconformant base type for them.

Then there is the argument of beauty. Since its beginning Eiffel had aunique top and bottom of the type system: ANY and NONE. This is verypleasing for anybody which looks at Eiffel with a mathematical eye.

Another cause for UC is the possibility to implement system routines likeprint(a:ANY) which prints a representation of any object. Without UC aroutine like print is not possible which would be some loss of convenience.

To summarize, neither the case for nor the case against universalconformance has very strong arguments. UC does not seem to be a principleat the heart of the Eiffel language. If it helps (which might be the moreinteresting question), UC can be thrown over board.

By the way: The ECMA committee has already given up universalconformance. The type detachable T does not conform to ANY, just to detachable ANY. Only attached types conform to ANY.

Feature rich ANY (FRA)

This and the next chapters will be published on a weekly basis.

Covariance (COV)

Backward compatibility (BC)

Promiscuous generic conformance (PGC)

Generic constraints based on conformance (GCC)

Validation with local analysis (VLA)

The solution

Comments
  • David Le Bansais (6 years ago 5/7/2011)

    Recovery

    Since you want to consider all sides of the problem, you might want to add a catcall recovery discussion, i.e. can it be solved with a recovery mechanism? I'm not advocating it, and I don't have any suggestion (yet). It's just one of the sides of the problem, and should be listed.

    The constraint here is that catcalls throw exceptions.

    • Helmut Brandl (6 years ago 5/7/2011)

      catcall recovery

      Well, what you propose is not a solution to the problem, but a workaround. Whenever a catcall is encountered the runtime must throw an exeption. I have implemented this workaround in my Eiffel compiler and it works well in the sense that it does not allow catcalls to escape and make more damage. Bertrand has once proposed some recast mechanism which seems to be similar. All these proposals work during runtime and not compile time.

      But what I am looking for is a more rigorous solution which works at compile time, i.e. modify the validity rules (and the language, if necessary) that catcalls cannot happen at runtime. I.e. I am looking for a real type safe Eiffel. This is necessary for Eiffel to compete with other modern languages like scala and C# which do not have this design flaw (for scala I am sure, my knowlegde if C# is not very deep, so I might be wrong here).

      • Peter Gummer (6 years ago 6/7/2011)

        C# has catcalls too

        Here is the C# equivalent of one of your examples, Helmut:

        object[] aa = new string[] { "Hello world" }; aa[0] = 1;

        This compiles without any errors or warnings, but when run, the second line throws this exception:

        System.ArrayTypeMismatchException : Attempted to access an element as a type incompatible with the array.

        But I had to write a test to be sure of this, because in nearly 10 years of C# programming I don't recall ever encountering one of these.

        That's similar to my experience in Eiffel. I remember that some of the first code that I ever wrote in Eiffel had a catcall, but I was inexperienced in the language and I was using a lot of generics and multiple inheritance: a beginner jumping into the deep end of the pool. Since then, I don't recall ever encountering another catcall in Eiffel. Catcalls seem to be extremely rare in the real world, at least in the hands of cautious and experienced developers. (Which is not to say that fixing catcalls is of merely academic interest. Experienced developers learn to live with all sorts of defects in programming languages, but we would be much more productive and write much better code if those defects were fixed. Eiffel without catcalls would be a great advance.)

        • Helmut Brandl (6 years ago 6/7/2011)

          Thanks for the C# example. Promiscuous generic conformance is the guilty here (i.e. an array of strings conforms to an array of objects). Scala avoids such problems with variance annotations.

  • Manu (6 years ago 4/8/2011)

    Universal Conformance

    When you say:

    • By the way: The ECMA committee has already given up universal conformance. The type detachable T does not conform to ANY, just to detachable ANY. Only attached types conform to ANY.

    that is simply not true, there is universal conformance to the type "detachable ANY". Which explains why rules have been changed so that A [G] is equivalent to A [G -> detachable ANY].