Difference between revisions of "Comparison of catcall solutions"

Revision as of 09:42, 24 June 2007

Motivation

By allowing covariant feature redefinition and hiding of features, the Eiffel language introduces the problem of catcalls (Changed Availability or Type). Currently the ECMA Eiffel standard does not specify how the occurrence of catcalls should be statically rejected.

The purpose of this document is to show a comparison between different proposals on how to handle the issue of preventing catcalls.

Criteria for a solution

To be able to judge a solution we use the following criteria which we consider as important:

Syntax overhead 

How much syntax will be added to the language in order to express safe covariance and generics?

Covariance on non-generic types 

Are covariant argument redefinitions addressed in the solution? How does the programmer express it?

Export status restrictions 

Is restriction of export status addressed in the solution? How does the programmer express it?

Use of generic types 

How is conformance of generics? Are catcalls for generics addressed in the solution? How does the programmer express it? Can generics be used as now or are there restrictions?

Agents 

Can agents be modeled with the solution while being type safe and expressive?

Comparator 

Can comparator types be modeled with the solution while being type safe and expressive?

Complexity of the compiler check 

Is it just a matter of doing one check or several?

Complexity of the runtime 

Does the runtime need more information to do assignment attempts or object tests?

Whole-system analysis 

Is a whole-system analysis necessary?

Dynamic class and type loading 

Is it safe to dynamically load new classes at runtime and instantiate new types?

Backward compatibility 

Is the solution backward compatible to existing source code?

Applicable per cluster 

Can the solution be applied on a per cluster basis?

Support of compiler/IDE 

Can the compiler/IDE help in updating existing source code? How?

General remarks

Checking feature calls

As the Single-level Call rule (8.25.3, VUSC) describes, a feature call is only valid if it is valid for every type in the dynamic type set. A simple solution would be that every feature call has to be checked for all possible descendants of the static target type. If this check is performed on a system, it will catch all catcalls - but also report false positives.

Some of the proposed solutions try to address this problem by finding a better approximation to the dynamic type set so that the false positives can be ruled out.

In general this is problematic as it requires a whole-system analysis, thus preventing the dynamic loading of new classes at run-time. The reason for this is that it is not known at compile time which features will be covariantly redefined by dynamically loaded classes.

This is only the case with non-generic types. For generics, it is known at compile time that all features containing a formal in the parameter list can be treated as covariantly redefined and corresponding precautions can be implemented via the type system and conformance rules which allow to load even generic types at run-time.

By the way, Eiffel Software has started to implement the basis of the single-level call rule in it's Eiffel compiler. It is work in progress which revealed some implementation problems.

Generic vs. non-generic covariance

We can distinguish two different kinds of covariant argument redefinition:

• When a generic type is derived, the formal generic parameters will be replaced by the actual generic parameters. Given the current conformance rules for generics, this can be seen as a covariant redefinition for all features which contain a formal generic as an argument. A simple example is the change from LIST [ANY] to LIST [INTEGER] where the feature put changes signature from ANY to INTEGER.
• In the non-generic case, covariance happens for certain anchored type declarations and in the case of explicitly changing an argument type to a descendant. This happens in general only on a small subset of the features.

The main difference is that in the generic case, all features which have a formal generic parameter automatically change the signature in different derivations whereas the non-generic case only specific features are covariantly redefined (if any at all). Also, in the generic case it is known for all possible descendants which features are redefined covariantly.

This observation helps to understand the various proposals and to see their strengths and weaknesses:

• A proposal which operates on the feature level can be good for non-generic classes as you generally have a small number of features covariantly redefined and you only have to specify these features. In the case of generics this can become cumbersome as all features with formal generic parameters are always considered as covariantly redefined and thus for generics they always have to be considered.
• A proposal which operates on the type level is better suited for generics as you don't have to specify every single feature which has a formal generic parameter as argument. But they run into problems in the non-generic case if you look at anchored types - for example like Current. Due to the fact that you have a covariant redeclaration in every descendant with such a feature, operating on the type level means that you have to handle every descendant specifically whereas if you operated on the feature level you could just handle this single feature.
• You see that there are two families of features: Features with formal arguments and ordinary features which are covariantly redefined. The fundamental difference between these two families is that they can change their signature independently. From LIST [ANY] to LIST [INTEGER] only the features based on the formal change their signature while they don't change from LIST [ANY] to LINKED_LIST [ANY] where the ordinary ones do. If you don't want to restrict the programmers expressiveness these feature families have to be addressed separately and a one fits all solution does not exist.

Contravariant generics

The modeling of certain problems involving generics requires contravariance. The two examples which will be used are comparator objects and agents:

• If you want to compare objects using a comparator, it either needs to be able to compare objects of the exact type, or an ancestor. Thus if you want to compare strings, either a comparator for STRING or one for ANY is suitable.
• If you want to pass an argument of type STRING to an agent, the agent either has to accept a STRING or ANY argument (or no argument at all).

These problems can only be modeled if there is a way to express contravariant conformance for generics. This means that all proposed solutions which don't offer this possibility can't be used to model agents or comparator correctly and safely.

Catcall benchmark

Catcall checkpoints

Overview of general solutions

The following proposals handle the case of covariance on non-generic and generic types.

Novariance

In the novariance proposal, covariant redefinition for arguments is prohibited. If covariance is needed for modeling purposes it can be simulated by renaming.

The conformance between generics with different formal parameters is removed.

Forget / keep

With the forget and keep mechanisms you specify per type on the feature level which features need not to be called - these features can safely be redefined covariantly - or which features have to be available - these features have to be typesafe for all possible values of a caller object.

Reference: Article on dev.eiffel.com

Dynamic typeset algorithm

The dynamic typeset algorithm does not change any semantics of the types or the conformance as it is in Eiffel already, it only does an abstract execution of the system to limit the possibilities per feature call which have to be checked if they are safe.

Overview of solutions for non-generics

These proposal only address the case for non-generics. For generic catcalls another solution (e.g. wildcard generics) can be used.

Restrict types

With restrict types you specify per type on the type level which descendant types that are allowed. Only these types can be assigned to such a variable, and all feature calls on these variables have to be valid for all possible types in this list.

Reference: IssueFLEX_CATCALL on ECMA wiki
Reference: Discussion in ECMA mailinglist named Catcall removal: another proposal, available in parts

DOG proposal

With the DOG proposal, features which can be covariantly redefined have to be marked as such. These features can only be called on specially marked entities which have a restricted conformance, thus preventing assignments from descendants with potential covariantly redefined arguments.

Reference: IssueDOG on ECMA wiki

Overview of solutions for generics

These proposal only address the case for generics. For non-generic catcalls another solution (e.g. novariance) can be used.

Usage-site variance

This solution lets the programmer decide on the instantiation of a generic if the generic parameter should be covariant, contravariant or invariant. Depending on the variance, the applicable features of the type and the conformance rules to other generic types are changed.

Reference: On variance-based subtyping for parametric types

Definition-site variance

This solution lets the programmer decide in the definition of a generic class if the generic parameter should be covariant, contravariant or invariant. Depending on the variance, the formal generic can only appear at the argument, only appear as a result type or appear in both places. Also the conformance is adapted depending on the variance of the generic parameter.

This is the solution which is implemented in the CLR, although not supported by generics in C# which are novariant.

Reference: Article about generics in CLR

Note: There is also a proposal by Bernd Schoeller about variant and invariant generics which is a subset of this one and thus not explained in detail.

Wildcard generics

This mechanism extends the usage-site variance by adding a wildcard to the generic derivation. This wildcard denotes unspecified types and limits the use of features with generic parameters or result types over conformance to the wildcard types.

Since the mechanism is almost identical to the usage-site variance, it will not be looked at in more detail. Please refer to the reference article for more information.

Reference: Adding Wildcards to the Java Programming Language

Overview of dynamic solutions

These proposals do not prevent catcalls at compile-time but introduce means to handle catcalls at runtime.

Detachable types

This solution allows covariantly redefined features only to use detachable types. Through this mechanism, an object test is necessary before an argument can be used. This forces the programmer to test arguments for validity.

Reference: Article about attached types by Bertrand Meyer
Reference: ECMA Eiffel standard 2nd edition of June 2006

Recast

In the recast proposal, the programmer has to specify a transformation function when covariantly redefining a feature which can transform the old argument types to the new ones.

Reference: IssueCAT on ECMA wiki
Reference: Article about recast

Exceptions

Another way of handling catcalls at runtime is to raise exceptions. It can be required or not to provide a rescue clause which handles the case of the catcall.

Combinations

It is also possible to combine different proposals:

• Novariance for non-generic features and usage-site variance for generics .
• Forget / keep for non-generic features and definition-site variance for generics.
• DOG proposal for non-generic features and wildcard generics.
• ...

Results

The following table summarizes the support of the various solutions to the criteria described above which can be used to judge a catcall solution.

This results can be differently interpreted, so the colors may not be totally accurate. See the explanation at the end of the table for more information

General solutions

Solutions for non-generics

Solutions for generics

Dynamic solutions

Table explained

Syntax overhead 

Small if a keyword/mark is needed per class/feature declaration; Medium if a keyword/mark is neede per type declaration; Big if a clause is needed per type declaration.

Use of generics 

As it is now if assignments are possible if generic parameters conform; Limited is some restrictions in the use or the conformance between generics exist; Very limited a lot of restrictions in the use or the conformance between generics exist.

Agents 

Fully supported if all safe assignments are allowed; Limited if not all safe assignments are allowed; As it is now if unsafe assignments are still possible.

Comparator 

Supported if for a comparator all safe assignments are permitted (i.e. contravariant assignments); Not supported if only exact type or even (unsafe) subtypes can be assigned.

Support of IDE (Source changes) 

Not needed if everything still works the same; Possible if the compiler can suggest clauses or marks; Not possible if the programmer has to specify additional features/instructions.

Personal opinions

Personal view about catcall solution