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)

All classes in Eiffel inherit the features of ANY. These are a buch offeatures: type, is_equal, copy, twin, once_manager, io, is_deep_equal,deep_win, do_nothing, default_rescue, ... just to mention a some of them(in EiffelStudio 6.3 the class ANY has 29 public features).

These features are imposed on all classes and therefore on all types,independently whether they need them or not. And if you study some reallife classes they usually don't need all features of ANY or just one or twoof them. So for somebody looking for some minimal kernel of the language,this is a little bit disturbing.

All who know C are familiar with the famous "Hello world"-example. Thedesigners of C made the language core minimal, so that even for printing asimple string to standard output you have to request some library. Without"#include <stdio.h> you cannot print anything. Fullstop. The basicphilosophy behind: You only pay for what you ask. If you don't ask forstdio, you won't pay for it.

The philosophy behind Eiffels ANY seem to be just the opposite: You don'thave to ask, you just have to pay. It is already included in the basicsetup. Some might argue that unused features will be squeezed out finallyby the optimizer and in the final binary you won't pay for unusedfeatures. However in the whole development process you have them in.

Let us smell the taste of the different views a little bit. A hello-worldprogram with FRA reads like

class HELLO create make feature {NONE} make do print ("Hello world.%N") end end

Without FRA you would encounter something like

class HELLO inherit STANDARD_INPUT_OUTPUT create make feature {NONE} make do print ("Hello world.%N") end end

Too noisy? I don't know. But up to now it is a matter of taste.

You might ask, what has this to do with type safety. Admittedly the examplewith printing "Hello world." has nothing to do with type safety. It servedto smell the taste about FRA and the opposite (feature poor ANY).

The thing gets more interesting if we look at features like is_equal andcopy. Since they have an argument anchored to Current "is_equal ( other: likeCurrent): BOOLEAN", they imply covariant redefinition in descendants. I.e. anyclass, which redefines is_equal will redefine the argumentcovariantly. INTEGER, REAL, STRING, ... all have a different definition ofis_equal and are expecting an argument of the same type (or conformant).

And this together with universal conformance (UC) hurts. UC implies thepossibility of polymorphic attachment of an object of any type to an entity oftype ANY and FRA makes it possible, that is_equal can be called with anargument of any type as long as it is called on an entity of type ANY but isexpecting a specific one. And these two facts open up a possible catcall withis_equal.

The current version of the ECMA Eiffel specification has tried to resolvethe issue by giving is_equal another signature. The spec. defined

is_equal (other: ANY): BOOLEAN

This is possible, but it has some ugly consequences. Look at the classINTEGER. Would you be pleased with the class text

expanded class INTEGER feature ... is_equal(other: ANY): BOOLEAN external "built_in" end .. end

and the code snippet

local i: INTEGER do i := 5 if i.is_equal ("Hello world") then ... end end

I would say that it is a possibility to change all arguments of type "likeCurrent" in features of ANY to "ANY" and not redefining them covariantly indescendants. With that, the catcalls with is_equal can be avoided.

But what about copy? What would you say to "i.copy("Hello world")"?

Bertrand Meyer some time ago stated that the ECMA committee has oscillatedabout the signature of is_equal, but now the definition of is_equal (other:ANY) is firm. Some weeks later another member of the committee stated thatis_equal(other: like Current) is back. Maybe in the next meeting they... I don't know.

But wait a moment. We are discussing the constraint "feature rich ANY"here. Therefore the real question is: Is it necessary that the featuresis_equal, copy etc. are in ANY?

What would be the consequence of e.g. putting is_equal and copy into a classEQUALITY_FEATURES, is_deep_equal and deep_cloned into DEEP_FEATURES, io andprint into STANDARD_INPUT_OUTPUT?

The most obvious consequence is that you cannot any longer compare any twoobjects by the object comparison operator "~", because "~" relies on is_equal.

Objects of many types need not necessarily the feature is_equal. But somesurely need. All numbers need to be checkable for equality. E.g. the classINTEGER would read

expanded class INTEGER inherit {NONE} EQUALITY_FEATURES ... end

Without inheriting from EQUALITY_FEATURES no assignment of expanded typeswould be possible. Expanded types have copy semantics. Therefore the semanticeffect of assignment is based on the semantics of the copy feature. Anyexpanded class not inheriting the equality features would not be assignable(as opposed to reference type which are always assignable without havingcopy).

Removing FRA will give us "You only get what you ask for".

Besides the additional effort it gives me some new freedom of design. WithoutFRA I can design a classes which cannot be compared nor copied. Sometimes thismight be my design intention. Maybe I want to say to you: Just create objectsof this class, modify them with the features I have designed for it, but donot ask for equality nor for copy. The class has not been designed forthat. Why not?

The constraint FRA can be lifted, if it helps. The combination of UC, FRA andthe anchored signature of is_equal and copy cannot all be kept.

Covariance (COV)

Since catcalls can only happen when polymorphic attach meets covariantredefinition some might propose to get rid of covariance.

Bertrand and Emmanuel have written a little paper with the title "The worldis covariant. Is it safe?".

The title already reveals that they don't consider removing covariance anoption. They try to illustrate it with a CUSTOMER which can be served any typeof BEVERAGE (i.e. CUSTOMER has the feature "serve(b:BEVERAGE)". A BEVERAGE iseither a SOFT_DRINK or ALCOHOL. MINORs are CUSTOMERs, but they shall have themore restrictive feature "serve(b:SOFT_DRINK)".

They say implicitely that modelling the world usually involves covariance. Amore specific type might require some more specific argument in its features.

The problem arises if a MINOR is considered as a CUSTOMER (polymorphic attach)and served an alcoholic beverage. That is the realworld correspondance of acatcall which at least parents won't like.

Despite the potential catcall, the example is a strong case for covariance:Its modelling power.

Another case for covariance is its practical implications.

Let us look into the class COMPARABLE.

deferred class COMPARABLE feature is_less alias "<" (other: like Current): BOOLEAN deferred end is_less_equal alias "<=" (other: like Current): BOOLEAN do Result := Current < other or Current ~ other end is_greater alias ">" (other: like Current): BOOLEAN do Result := not (Current <= other) end ... end

Note that in the class COMPARABLE only the feature "<" is deferred. The others"<=", ">", ">=" are effective and based on "<" and "~". The class COMPARABLEis therefore also called a partial implementation. A descendant only has toeffect (i.e. to implement) the feature "<" and will get the other ones forfree and consistent with a mathematical order relation.

Or look into the class NUMERIC.

deferred class NUMERIC feature plus alias "+" (other: like Current): like Current deferred end minus alias "-" (other: like Current): like Current deferred ensure Result + other ~ Current end ... end

NUMERIC does not provide a partial implementation like COMPARABLE. But itspecifies contracts which the descendant has to obey to. It specifiese.g. that the operations "+" and "-" have to satisfy some consistencyrelation. We can say that NUMERIC models a certain behaviour which INTEGER,REAL, COMPLEX, MATRIX, etc. have to satisfy.

Now imagine the classes COMPARABLE and NUMERIC without its implicitcovariance. Does it make sense to specify

plus alias "+" (other: ANY): like Current ?

What is the sum of an INTEGER with a MATRIX?

No! We definitely want

plus alias "+" (other: like Current): like Current

So the case for covariance can be made with modelling power, partialimplementations and behaviour classes. Covariance is a very powerfulmechanism. Therefore nobody wants to get rid of covariance.

But: Is it an all-or-nothing decision? Do we want to be able to redefinecovariantly any feature in any class?

Maybe we can find a restricted form of covariance which gives us theadvantages of covariance without its dangers.

Remember: Covariance itself is not the problem, only covariance combined withpolymorphic attach and polymorphically calling the feature with covariantlyredefined arguments.

So it could be possible to allow covariant redefinitions only when they cannotdo any harm, i.e. instead of full covariance only a restricted form ofcovariance.

An attempt: Allow covariant redefinitions only on features which are notinherited conformantly.

As a consequence classes like COMPARABLE, NUMERIC can only be inheritednon-conformantly.

What other restrictions of covariance can you imagine?

Backward compatibility (BC)

The changes of the Eiffel language have been made up to now in a veryconservative and prudent manner. A compiler shall be able to support an oldand a new version of the language at the same time. Changes in the languageshall not break existing code.

This is in general a wise way to move forward. A code breaking change isinconvenient to the users.

Therefore the fix of the hole in the type system is expected not to breakexisting code. Is this possible?

A solution of the catcall issue has to disallow possible catcalls. Since inthe current version of Eiffel it is possible to code catcalls, the new versionof the language must reject some of the currently valid Eiffel code.

Therefore the requirement of complete backward compatibility is too strong. Itcannot be fulfilled.

But we don't want to give up backward compatibility in general. Well writtenEiffel code does not produce catcalls. But it might use Eiffel constructswhich are catcall prone even if in the specific case it does not produce acatcall.

Is it at least possible to make a change in the language which does not breakexisting code which does not produce catcalls?

Even this requirement might be to strong. The compiler has to analyze the codestatically. It cannot do all reasoning which humans can do. If we can provethat a specific code cannot produce catcalls it might be impossible for thecompiler to prove that. In that case, the compiler has to reject the code,i.e. break the code even if no actual catcall happen.

Therefore I propose to lift the requirement for backward compatibiliycompletely (at least to open up the solution space). A satisfactory solutionhas not been found for more than 15 years now. If we pose onto ourselves toomany constraints, we might not be able to come up with a good solution. Oncehaving a solution which is satisfactory without the backward compatibilityconstraint we can try to polish and improve it to make it as backwardcompatible as possible.

Promiscuous generic conformance (PGC)

Conformance is based on inheritance. A descendant conforms to its conformantparents, i.e. if "class D inherit B ..." is encountered, D conforms toB. Conformance is transitive. If A conforms to B and B conforms to C, then Aconforms to C.

This is not a complete description of conformance, but it captures the basicidea.

But Eiffel also has generic classes. There is a rule of conformance whichopens up another path. If we have a generic class CG[G] and a type D whichconforms to B, then CG[D] conforms to CG[B] as well.

In simple terms ARRAY[STRING] conforms to ARRAY[ANY]. I.e. for generic typesthere is not only the conformant ancestry of the base class which determinesconformance but also the ancestry of its actual generic parameters.

Does this make sense? We can answer diplomatically: Yes and no!

As long as I want to get an element of an ARRAY an ARRAY[STRING] returns me astring. Since STRING conforms to ANY I can attach an ARRAY[STRING] toARRAY[ANY] and the returned value is fine.

If I put something into ARRAY[ANY] (which is in reality ARRAY[STRING]), thecompiler won't complain. But the object attached is an ARRAY[STRING] whichdoes not like putting INTEGERs or BOOLEANs into it.

So yes, it is fine for all features not having arguments of formal generics ofthe surrounding class. And no, every use of a feature having arguments offormal generics of the surrounding class might produce a catcall.

Promiscuous generic conformance is part of the problem. We have to find a lessliberal form of generic conformance in order to make Eiffel type safe.

The most rigid solution would be to dissallow conformance based on conformanceof actual generics, i.e. an ARRAY[STRING] cannot be attached to an entity oftype ARRAY[ANY]. The question: Does this cut off useful patterns?

I personally have not yet encountered useful patterns which require attachingan ARRAY[STRING] to ARRAY[ANY]. But maybe you will protest and say "I use thispattern frequently to achieve XYZ". If you have a valid point, then we have tofind something less rigorous.

A less rigorous solution has already been proposed in the above mentionedpaper "The world is covariant. Is it safe?". It is based on the observationthat only features having arguments of formal generic type aredangerous. E.g. in the class ARRAY

class ARRAY[G] ... feature item alias "[]" (i: INTEGER): G ... put (el: G; i:INTEGER) ... end

the feature "item" will never produce catcalls, but the feature "put" can do.

If we attach an object of type ARRAY[STRING] to an entity a:ARRAY[ANY] wedon't want a.put(...) to be called, i.e. we want a type which has the featuresof ARRAY[ANY] without the dangerous ones. In other words we want ARRAY[ANY] to"forget" some of its features.

Syntactically it has been proposed to use ARRAY[variant ANY] to be thattype. ARRAY[variant ANY] has all features of ARRAY[ANY] except those whichhave arguments of formal generic type. With that it is not any problem toattach an object of type ARRAY[STRING] to an entity a:ARRAY[variant ANY],because you cannot call the offending feature a.put(...). Attaching an objectof type ARRAY[STRING] to an entity a:ARRAY[ANY] won't be allowed any longer.

What would you prefer? The simple more rigorous solution or the morecomplicated fine grained solution still allowing some generic conformance?

Is there a third (or forth, ... ) way?

Generic constraints based on conformance (GCC)

This and the next chapters will be updated soon.

Validation with local analysis (VLA)

The solution