Type safe Eiffel (1)
- What is the hole?
- Why has it not yet been solved?
- Analysis of the constraints
- The solution
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
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
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.
The array attached to "aa" is still an ARRAY[STRING]. But since the static type of "aa" is ARRAY[ANY], the assignment "aa:=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.
- Universal conformance (UC)
- Feature rich ANY (FRA)
- Covariance (COV)
- Backward compatibility (BC)
- Promiscuous generic conformance (PGC)
- Generic constraints based on conformance (GCC)
- Validation with local analysis (VLA)
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
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
Feature rich ANY (FRA)
This and the next chapters will be published on a weekly basis.