Difference between revisions of "Comparison of catcall solutions"
(→Overview of general solutions) |
(adding Default and explicit variance as general solution) |
||
Line 93: | Line 93: | ||
Read-write types are a solution which can model interval types and usage-site variance. It splits a type into a ''read'' type and a ''write'' type. The read type defines the applicable features and the write type the signature to check for valid arguments. | Read-write types are a solution which can model interval types and usage-site variance. It splits a type into a ''read'' type and a ''write'' type. The read type defines the applicable features and the write type the signature to check for valid arguments. | ||
+ | |||
+ | === [[Default and explicit variance]] === | ||
+ | Default and explicit variance is inspired of usage-site variance and detachable proposition. | ||
+ | The proposition add no new keyword. | ||
== Overview of solutions for non-generics == | == Overview of solutions for non-generics == |
Revision as of 08:39, 8 May 2013
Contents
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]
toLIST [INTEGER]
where the featureput
changes signature fromANY
toINTEGER
. - 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]
toLIST [INTEGER]
only the features based on the formal change their signature while they don't change fromLIST [ANY]
toLINKED_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 forANY
is suitable. - If you want to pass an argument of type
STRING
to an agent, the agent either has to accept aSTRING
orANY
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
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.
Read-write types
Read-write types are a solution which can model interval types and usage-site variance. It splits a type into a read type and a write type. The read type defines the applicable features and the write type the signature to check for valid arguments.
Default and explicit variance
Default and explicit variance is inspired of usage-site variance and detachable proposition. The proposition add no new keyword.
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.