Type safe Eiffel

[Helmut]

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

<eiffel>
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
</eiffel>

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

<eiffel>
deferred class COMPARABLE feature
is_less alias "<" (other: like Current): BOOLEAN deferred end
...
end
</eiffel>
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:

<eiffel>
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
</eiffel>

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:

# 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 the
discussion.



= Analysis of the constraints=


== Universal conformance (UC)==


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

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

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

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

What is the advantage and disadvantage of having universal
conformance?

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

Discussion of UC:

UC gives us the possibility of having just an object. You can design
classes 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 out
what type of object it is. With an object test you have to "downcast"
the
object to do something meaningful with it.

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

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

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

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

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


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





== Feature rich ANY (FRA) ==


All classes in Eiffel inherit the features of ANY. These are a buch of
features: 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
real
life classes they usually don't need all features of ANY or just one
or two
of 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. The
designers of C made the language core minimal, so that even for
printing a
simple string to standard output you have to request some library.
Without
"#include <stdio.h> you cannot print anything. Fullstop. The basic
philosophy behind: You only pay for what you ask. If you don't ask for
stdio, you won't pay for it.

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

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

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

Without FRA you would encounter something like

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

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
example
with printing "Hello world." has nothing to do with type safety. It
served
to smell the taste about FRA and the opposite (feature poor ANY).

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

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

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

<eiffel>
is_equal (other: ANY): BOOLEAN
</eiffel>

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

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

and the code snippet

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

I would say that it is a possibility to change all arguments of type
"like
Current" in features of ANY to "ANY" and not redefining them
covariantly in
descendants. 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
oscillated
about 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
that
is_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
features
is_equal, copy etc. are in ANY?

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

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

Objects of many types need not necessarily the feature is_equal. But
some
surely need. All numbers need to be checkable for equality. E.g. the
class
INTEGER would read

<eiffel>
expanded class
INTEGER
inherit {NONE}
EQUALITY_FEATURES
...
end
</eiffel>

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

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

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

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


==Covariance (COV)==


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

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

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

They say implicitely that modelling the world usually involves
covariance. A
more 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 a
catcall 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.

<eiffel>
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
</eiffel>

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


Or look into the class NUMERIC.

<eiffel>
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
</eiffel>


NUMERIC does not provide a partial implementation like COMPARABLE. But
it
specifies contracts which the descendant has to obey to. It specifies
e.g. that the operations "+" and "-" have to satisfy some consistency
relation. 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 implicit
covariance. Does it make sense to specify

<eiffel>
plus alias "+" (other: ANY): like Current ?
</eiffel>

What is the sum of an INTEGER with a MATRIX?

No! We definitely want

<eiffel>
plus alias "+" (other: like Current): like Current
</eiffel>


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

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

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

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

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

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

As a consequence classes like COMPARABLE, NUMERIC can only be
inherited
non-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 very
conservative and prudent manner. A compiler shall be able to support
an old
and a new version of the language at the same time. Changes in the
language
shall not break existing code.

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

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

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

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

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

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

Even this requirement might be to strong. The compiler has to analyze
the code
statically. It cannot do all reasoning which humans can do. If we can
prove
that a specific code cannot produce catcalls it might be impossible
for the
compiler 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 compatibiliy
completely (at least to open up the solution space). A satisfactory
solution
has not been found for more than 15 years now. If we pose onto
ourselves too
many constraints, we might not be able to come up with a good
solution. Once
having a solution which is satisfactory without the backward
compatibility
constraint we can try to polish and improve it to make it as backward
compatible as possible.




==Promiscuous generic conformance (PGC)==


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

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

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

In simple terms ARRAY[STRING] conforms to ARRAY[ANY]. I.e. for generic
types
there is not only the conformant ancestry of the base class which
determines
conformance 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 a
string. Since STRING conforms to ANY I can attach an ARRAY[STRING] to
ARRAY[ANY] and the returned value is fine.

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

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

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

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

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

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

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

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]
we
don't want a.put(...) to be called, i.e. we want a type which has the
features
of 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
that
type. ARRAY[variant ANY] has all features of ARRAY[ANY] except those
which
have arguments of formal generic type. With that it is not any problem
to
attach an object of type ARRAY[STRING] to an entity a:ARRAY[variant
ANY],
because you cannot call the offending feature a.put(...). Attaching an
object
of 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 more
complicated fine grained solution still allowing some generic
conformance?

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




==Generic constraints based on conformance (GCC)==

Eiffel has the nice feature of constraint genericity.

The class ARRAY[G] does not have any constraint. You can use any valid
type T
to declare an ARRAY[T]. There is no need for ARRAY to know anything
about the
type of the elements it contains. It just stores and retrieves the
elements
but does not call any features of the elements.

If you design a kind of a sorted sequence the requirement is
different. You
want to store the elements in order. You must be able to compare them,
i.e. to
call a < b. Therefore you cannot accept any type as an actual generic
for the
sorted sequence. Instead you will specify

<eiffel>
class SORTED_SEQUENCE[G->COMPARABLE] ... end
</eiffel>

With that declaration Eiffel allows the type SORTED_SEQUENCE[T] only
if T
conforms to COMPARABLE. SORTED_SEQUENCE[INTEGER],
SORTED_SEQUENCE[REAL],
SORTED_SEQUENCE[STRING] are valid ones, SORTED_SEQUENCE[COMPLEX] would
be
invalid.

Since the actual generic T has to conform to COMPARABLE it is
guaranteed
that SORTED_SEQUENCE can call all features of COMPARABLE on entities
of its
formal generic type G.

This is consistent with the conformance rules: A formal generic type
conforms to itself and its constraint. No type except itself conforms
to a
formal generic.

But what happens if we write

<eiffel>
class T inherit {NONE] COMPARABLE ... end
</eiffel>

The class T still has all features of COMPARABLE so it could be used
in the
type SORTED_SEQUENCE[T]. But it cannot!

SORTED_SEQUENCE[T] is not a valid type, because T does not conform to
COMPARABLE.

Remember that COMPARABLE contains features which might produce
catcalls. Therefore a prudent user inherits from COMPARABLE only
non-conformant. But as a consequence he cannot use his type to put it
into
a sorted sequence. How frustrating!

For that reason we have to discuss the basis to define constraints. Is
conformance the right way? Why do we use conformance to define
constraints?

a) It is convenient. We have this notion of conformance and it does
the
job. So why not use it?

b) We might want to be able to use conformance in its basic form to
make assignments. E.g.

<eiffel>
class SORTED_SEQUENCE[G->COMPARABLE] feature
some_feature (e: G)
local
c: COMPARABLE
do
c := e -- This is possible, only if G conforms to
COMPARABLE
...
end
end
</eiffel>


Ad a) This is not convincing. We could use a weaker notion than
conformance
to specify constraints. It might not be difficult to find a way to
allow
the non-conforming inheritance as well to satisfy the constraint.

Ad b) This is convincing if such a construct is really needed. I have
not
yet encountered a case, where I want the above assignment c:=e to be
allowed. But if there are such useful patterns, we have to find a
solution
for that.

Anyhow: Usually defining a constraint with conformance is an
overspecification. If we define a constraint of a formal generic we
want to
have the features of the constraint and not necessarily conformance to
the
constraint.

A weaker notion than conformance that does the job is non conformant
inheritance. If D inherits non conformant B, then D has all the
features of
B. But wait: aren't there some subtle nasty details?

Yes there are.

a) Using non-conforming inheritance you can convert public features
into
private ones.

b) With repeated inheritance you can inherit more versions of the same
feature. So if the generic class calls that feature, it is ambiguous
which
one will be called on the actual generic.

Now you can say: "There you see. Conformance is the better choice."

But I do not give up so fast. I admit that pure non conformanant
inheritance
is not sufficient. But why not define a weaker type conformance? Let
us call
this form the moment "behavioural conformance".

We say that D behaves like B if all requirements of conformance are
fulfilled except that the inheritance path between D and B can contain
non-conforming parts. I.e. under behavioural conformance you can win
only
clients and not remove them and you have to resolve all ambiguities
with
repeated inheritance with proper select statements.


With that definition "G behaves like COMPARABLE" is sufficient to
describe
the constraint. A class CG[G: CONSTRAINT] can use all features of
CONSTRAINT on its formal generic G without any problems.

If you in some cases still want to be able to assign type G to
CONSTRAINT,
we have to distinguish the weaker and the stronger specification of
the
constraint, e.g.

<eiffel>
class CG[G: CONSTRAINT] -- the weaker form without
conformance

class CG[G -> CONSTRAINT] -- the stronger form with
conformance
</eiffel>


I personally think that the default case should be the weaker form,
because in
the majority of (if not in all) cases, the weaker form is sufficient.
If the
stronger form is still needed, it shall be tagged with something
extra.

So why not use always the weaker form to specify a constraint and get
rid
of the possibility to assign a formal generic to its constraint?

Reason: I cannot imagine a generic class CG[G] without having features
like

<eiffel>
some_feature (e: G; ... )
</eiffel>

How can you import an object of the formal generic type into the
object
without such features? Without such features can import nothing into
the class
except the default values with self initializing types. But a generic
class
CG[G] just using default values of G is not very interesting.

So if you have features like "some_feature" and use conformance to
specify
the constraint, you can produce catcalls.

You don't believe me. Here is the proof.

<eiffel>
class SORTED_SEQUENCE[G->COMPARABLE] ... feature
put(e:G) ...
end


local
seq: SORTED_SEQUENCE[COMPARABLE]
do
create seq.with_capacity(100)

seq.put ("Hello world.")
seq.put ( 1 ) -- seq has to compare "Hello world." <= 1 ->
catcall!
end
</eiffel>

Summary: Using conformance as the base to specify constraint generic
parameters is a bad choice. A weaker notion like the above defined
"behavioural conformance" is needed.





==Validation with local analysis (VLA)==


Validation is usually (not just in Eiffel; in nearly all typed
languages)
based on local analysis. I.e. the compiler can check the validity of a
routine
by just looking at the routine, the types it uses and the parent types
(and
parents of parents etc.). This is a very useful principle for modular
SW. A
module (a class, cluster, library) can be checked for validity and if
its
valid it remains valid in any context.

As opposed to local analysis, global analysis looks at the whole
system.

As long as Eiffel has the possibility of catcalls, local analysis is
not
sufficient to analyize validity. Look at the feature call

<eiffel>
t.f(a)
</eiffel>


The expression t has a certain type T. This type must have a feature f
which
accepts an argument of type A. As long as the actual argument a
conforms to
the type A of the corresponding formal argument of f the call is
locally
correct.

This is the static view. But at runtime the expression t can return an
object
of type DT which conforms to T. The feature f within DT might have
redefined
the formal argument to DA, a descendant of A which conforms to A. I.e.
the
actually called dynamic feature {DT}.f might expect a more specific
type DA
than indicated by the static feature {T}.f. The compiler has no
possibilities
to find that out by doing only local analysis. I.e. the constraint of
basing
validity on local analysis only is a severe one.

We can do global analysis to detect potential catcalls at compile
time. Looking at the whole system it is possible to calculate all
possible
dynamic types of objects which can be returned by the expression t. If
the
actual argument a does not conform to corresponding formal argument
for all
possible dynamic types then there is a potential catcall which the
compiler
can reject at compile time.

This algorithm (dynamic typeset calculation) is conservative in the
sense that
it can detect all possible catcalls at compile time, but not every
detected
potential catcall results in an actual catcall at runtime. Being
conservative
is a disadvantage, but not a severe one, since catcalls do not happen
very
often in real SW.

The second disadvantage is that global analysis requires much more
computation
for the compiler to decide if a system is typesafe. This might be a
problem
for very large systems where only a small fraction of the code is
added or
redesigned. Even changing one line of code requires a full system
analysis to
check the validity of the change. With modern high speed computers and
a good
search strategy of the compiler doing global analysis the response
time might
be kept within acceptable limits.

However there is a third disadvantage. The compiler can detect a
potential
catcall, but it cannot say which module causes the problem. The actual
potential catcall is detected in a well working library, the actual
polymorphic attachment might be done in another well working library
and the
connection of the two libraries is done in some user code. All this
three
parts of the code a locally valid. Where do you fix the problem? Don't
be
misled by the already given very simple examples of possible catcalls.
These
are just examples to demonstrate the possibility of catcalls in very
simple
contexts. But in real SW the problem can be much more distributed
around
different modules which do not interwork directly.

The third cited disadvantage of global analysis is a severe one. For
that
reason nearly no modern typed programming language bases validity on
global
analysis. This breaks modularity and abstraction in an unacceptable
manner. Especially for Eiffel which has been designed to support the
construction of large systems validity must be based on local
analysis.

Global analysis is a fine technique for a compiler to do optimization.
But it
shall not be used to check validity!

I.e. we are looking for a solution which guarantees type safety by
doing local
analysis.


A possible solution will be presented in another post.