Difference between revisions of "Comparison of catcall solutions"

m (Solutions for generics)
(Overview of general solutions)
Line 85: Line 85:
  
 
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.
 
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.
 +
 +
=== [[Interval types]]] ===
 +
 +
Interval types allow to define each type as an interval with a lower and upper type as boundary. This limits the dynamic type set and thus restricts the number of features which need to be checked for system-validity. In addition to this, it defines rules which handle the case of features with formal arguments.
 +
 
== Overview of solutions for non-generics ==
 
== Overview of solutions for non-generics ==
  

Revision as of 18:55, 5 July 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.

Interval types]

Interval types allow to define each type as an interval with a lower and upper type as boundary. This limits the dynamic type set and thus restricts the number of features which need to be checked for system-validity. In addition to this, it defines rules which handle the case of features with formal arguments.

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

Criteria Novariance Forget / keep Dynamic typeset algorithm
Syntax overhead No Big: forget/keep clauses per type No
Covariance on non-generic types Not allowed Allowed Allowed
Export status restrictions Not allowed Allowed Allowed
Use of generic types Very limited: Only invariant conformance Limited: Conformance restricted (keep all as default)
Limited: Use restricted (forget all as default)
As it is now
Agents Limited
Safe
Limited
Safe
As it is now
Comparator Not supported Not supported Not supported
Complexity of compiler check Small Medium: Check of feature call for all descendants; Conformance check on forget/keep clauses Big: Iterative abstract system execution
Complexity of runtime Small: As it is now Medium: Need to know cat features for object tests Small: As it is now
Whole-system analysis No Yes: use of forget all depends on system Yes
Dynamic class and type loading Yes No No
Backward compatibility Very limited Limited Full
Support of IDE (Source changes) Not needed Possible: Can propose forget/keep clauses Not needed

Solutions for non-generics

Criteria Restrict types DOG proposal
Syntax overhead Big: Restrict clause per type declaration Medium: cat on features and on type declarations
Covariance on non-generic types Allowed Allowed
Export status restrictions Allowed Allowed
Use of generic types Not addressed Not addressed
Agents Not addressed Not addressed
Comparator Not addressed Not addressed
Complexity of compiler check Medium: Check of feature call for all descendants; Conformance check on restrict clauses Small: Check of cat on conformance
Complexity of runtime not yet considered Small
Whole-system analysis Partial No
Dynamic class and type loading Limited Yes
Backward compatibility Very limited Very limited
Support of IDE (Source changes) Possible: Can propose restrict clauses Possible: Can propose cat marks

Solutions for generics

Criteria Usage-site variance Definition-site variance Wildcard generics
Syntax overhead Medium: Variance marks per generic type Small: Variance marks per generic class definition Medium: Variance marks per generic type
Covariance on non-generic types Not addressed Not addressed Not addressed
Export status restrictions Not addressed Not addressed Not addressed
Use of generic types Limited: Conformance is limited
Safe
Limited: Conformance is limited
Safe
Limited: Conformance is limited
Safe
Agents Fully supported
Safe
Fully supported: If tuples can be specified covariantly
Safe
Fully supported
Safe
Comparator Supported Supported Supported
Complexity of compiler check Small: Consider variance in conformance check Small: Consider variance in conformance check Small: Consider variance in conformance check
Complexity of runtime Small: Consider variance in object test Small: Consider variance in object test Small: Consider variance in object test
Whole-system analysis No No No
Dynamic class and type loading Yes Yes Yes
Backward compatibility Limited: Use of generics changed due to conformance Very limited: Libraries need redesign Limited: Use of generics changed due to conformance
Support of IDE (Source changes) Possible: Can propose variance marks Not possible: Libraries need redesign Possible: Can propose variance marks/wildcards

Dynamic solutions

Criteria Detachable types Recast Exceptions
Syntax overhead Small: Detachment marks Big: Recast clauses, recast features Medium: If rescue clause mandatory
No: If rescue clause not needed
Covariance on non-generic types Very limited: Only detached arguments, no expanded arguments Allowed Allowed
Export status restrictions Not addressed Not addressed Not addressed
Use of generics Very limited: Only detachable formal arguments Very limited: Recast clause for all features with formal generics As it is now
Agents As it is now As it is now As it is now
Comparator Not supported Not supported Not supported
Complexity of compiler check Small: As it is now Small: As it is now Small: As it is now
Complexity of runtime Small: As it is now Medium: Check for catcalls and do recast Medium: Check for catcalls and raise exception
Whole-system analysis No No No
Dynamic class and type loading Yes Yes Yes
Backward compatibility Very limited: All covariant and generic features become detached Very limited: All covariant and generic features need recast clause Limited: If rescue clause is mandatory
Full: If rescue clause not needed
Support of IDE (Source changes) Possible: Can propose detachment marks Not possible: Programmer must provide recast clause Not possible: If rescue clause mandatory
Not needed: If rescue clause not needed

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