EiffelStudio: an EiffelSoftware project - User contributions [en]

Compiling EiffelStudio

2010-05-31T15:28:12Z

Juliant: Reverted edits by Jacksonsophia (Talk) to last version by Manus

[[Category:Compiler]]
[[Category:EiffelStudio]]

== Installing EiffelStudio ==

To compile EiffelStudio, you need an already working EiffelStudio compiler on your machine. The current source tree '''requires at least version 6.5''' of EiffelStudio. You can download it from http://dev.eiffel.com/Downloads. Read the [http://docs.eiffel.com/eiffelstudio/installation/index.html existing documentation] to install EiffelStudio.

'''Note:''' on Windows you will need the Microsoft C compiler to compile Eiffel Studio. How to install the free version of the Microsoft C compiler: [[Installing Microsoft C compiler]]. It is not possible to compile EiffelStudio with the free Borland compiler.

===Compilation methods===
Currently there are two compilation methods.
* You can compile EiffelStudio from scratch following the instructions in this document ('''This is the recommended approach''').
* You can use one of the [[Automatic Build Scripts]], and if you encounter any errors please report them to the [http://forums.eiffel.com EiffelStudio Development forum].

==Extracting source code==

===Checking out from SVN===
#Point the environment variables called '''EIFFEL_SRC''' and '''ISE_LIBRARY''' to the directory where you want to compile EiffelStudio. Usually we use the '''XXdev''' convention for this directory name - where XX is the version number of the currently developed version of the compiler.
#Make sure that '''ISE_EIFFEL''', '''ISE_PLATFORM''' and '''ISE_C_COMPILER''' (on Windows only) are properly defined.
#Perform the following checkout procedures:

'''DOS'''
<pre>
set SVNURL=https://svn.eiffel.com/eiffelstudio/trunk
svn co %SVNURL%/Src 65dev
svn co %SVNURL%/Delivery 65dev/Delivery
svn co %SVNURL%/Documentation 65dev/Documentation
svn co %SVNURL%/free_add_ons 65dev/free_add_ons
</pre>

'''Bash'''
<pre>
export SVNURL=https://svn.eiffel.com/eiffelstudio/trunk
svn co $SVNURL/Src 65dev
svn co $SVNURL/Delivery 65dev/Delivery
svn co $SVNURL/Documentation 65dev/Documentation
svn co $SVNURL/free_add_ons 65dev/free_add_ons
</pre>

To update the source files to the latest revision, perform the following steps:

'''Bash and DOS'''
<pre>
cd 65dev
svn up
svn up free_add_ons
svn up Delivery
svn up Documentation
</pre>

==Compiling C libraries==

===Compiling run-time on Windows===

'''DOS'''
<pre>cd %EIFFEL_SRC%/C
configure [win32|win64] [b|g|m|m6]</pre>

'''Bash'''
<pre>cd $EIFFEL_SRC/C
./configure.bat [win32|win64] [b|g|m|m6]</pre>

The first argument indicated whether you are compiling the run-time for 32 or 64 bits. The second one is to tell which C compiler will be used. For now only `b' (Borland), `g' (MinGW), `m' (Microsoft) and `m6' (for those forced to use Microsoft VC++ 6.0) are officially supported.

On Windows 32 bits to clean up all the generated files '''(including the library files needed by EiffelStudio)''' it suffices to do:

'''DOS'''
<pre>configure clean</pre>
'''Bash'''
<pre>./configure.bat clean</pre>

===Compiling run-time on Unix===

The command is simply:
<pre>cd $EIFFEL_SRC/C
./quick_configure</pre>
This requires that '''ISE_PLATFORM''' is properly defined. The `quick_configure' script will look for the file CONFIGS/$ISE_PLATFORM and use it to extract the platform specific information to compile the run-time. If not found then an error will be reported.

To clean up the generated files '''including the library files needed by EiffelStudio''':
<pre>make clobber</pre>

===Compiling C code from libraries===

Here is the list of commands to compile all required C libraries on Windows:

'''DOS'''
<pre>cd %EIFFEL_SRC%\library\net\Clib
finish_freezing -library
cd %EIFFEL_SRC%\library\vision2\Clib
finish_freezing -library
cd %EIFFEL_SRC%\library\wel\Clib
finish_freezing -library
cd %EIFFEL_SRC%\library\cURL\Clib
finish_freezing -library</pre>
'''Bash'''
<pre>cd $EIFFEL_SRC/library/net/Clib
finish_freezing -library
cd $EIFFEL_SRC/library/vision2/Clib
finish_freezing -library
cd $EIFFEL_SRC/library/wel/Clib
finish_freezing -library
cd %EIFFEL_SRC%/library/cURL/Clib
finish_freezing -library</pre>

On Unix it is slightly different:
<pre>cd $EIFFEL_SRC/library/net/Clib
finish_freezing -library
cd $EIFFEL_SRC/library/vision2/Clib
finish_freezing -library
cd $EIFFEL_SRC/library/vision2/implementation/gtk/Clib
finish_freezing -library
cd $EIFFEL_SRC/library/cURL/Clib
finish_freezing -library</pre>

Make sure that '''ISE_EIFFEL''' is set correctly to your current "EiffelStudio" installation!

===Compiling C code from C_library===

This is only required on Windows to read PNG file. On Unix, this is not required because it is included in GTK+2.4. So on Windows, simply do the following:

'''DOS'''
<pre>cd %EIFFEL_SRC%/C_library/zlib
finish_freezing -library
cd %EIFFEL_SRC%/C_library/libpng
finish_freezing -library</pre>
'''Bash'''
<pre>cd $EIFFEL_SRC/C_library/zlib
finish_freezing -library
cd $EIFFEL_SRC/C_library/libpng
finish_freezing -library</pre>

===Compiling C code from compiler===

This is only required on Windows as this C code is a tiny wrapper around the Microsoft C++ API to generate and to debug .NET code.

To compile it, you first need to install the Microsoft .NET SDK. You can download it from their website.

After installing it, you need to update your '''LIB''' and '''INCLUDE''' environment variable to include the path the lib and include directory of the .NET Framework SDK.

Once properly installed, you can do:

'''DOS'''
<pre>cd %EIFFEL_SRC%/framework/cli_writer/Clib
finish_freezing -library
cd %EIFFEL_SRC%/framework/cli_debugger/Clib
finish_freezing -library</pre>
'''Bash'''
<pre>cd $EIFFEL_SRC/framework/cli_writer/Clib
finish_freezing -library
cd $EIFFEL_SRC/framework/cli_debugger/Clib
finish_freezing -library</pre>

==Compiling EiffelStudio==

Now that we have taken care of the C code compilation we can compile the compiler. We assume that '''ec''' is in your path.

The configuration file of the compiler contains two active targets:
* '''batch''': for the command line compiler.
* '''bench''': for the graphical compiler, aka EiffelStudio.

Go to $EIFFEL_SRC/Eiffel/Ace and type the following command and replace ''target_name'' with either '''batch''' or '''bench'''.

<pre>ec -config ec.ecf -target target_name -c_compile</pre>

===Mac OS X specific===

Get a mac binary from [[EiffelOnMac|here]], then follow the instructions for unix.

==Launching the Compiler==

There are two ways of launching the compiler:
# Command line compiler: add the following arguments '''-config path_to_config_file.ecf'''. This will compile the project represented by `path_to_config_file.ecf'
# Graphical compiler (aka EiffelStudio): add the following argument '''-gui'''.

Downloads

2010-05-31T15:25:38Z

Juliant: Reverted edits by Jacksonsophia (Talk) to last version by Manus

[[Category:EiffelStudio]]
[[Category:Compiler]]
==EiffelStudio 6.x Pre-releases==
We provide versions of EiffelStudio for most popular platforms (Linux, Windows, Solaris, Irix, ...).

You can find the latest builds:
* from the download page of [http://sourceforge.net/project/showfiles.php?group_id=196408 the sourceforge area]
* as well as in [ftp://beta:beta57@ftp.eiffel.com the Eiffel Software beta area] (beware it also includes some nightly build which are untested).
* in [http://eiffelstudio.origo.ethz.ch/download the Origo download area] for the PorterPackage.

Details about new features and bug fixes in the builds are on the [[EiffelStudio_Releases| releases page]].

{{Note|Please be aware that the 6.x versions released through this site are intermediate builds on the road towards official EiffelStudio 6.x. If you are experiencing problems with this release, please use the [http://eiffelstudio.origo.ethz.ch/forum EiffelStudio developer forums] for discussions.}}

The convention used for filenames is the following:
Eiffel65_gpl_$BUILD-$ISE_PLATFORM.[tar.bz2|msi]
Where '''$BUILD''' is a build number, the higher number the more recent release it is, and where '''$ISE_PLATFORM''' is the name of your platform.

Mac OS X builds can be found [[EiffelOnMac|here]].

On Windows, you can use [[Installing_Microsoft_C_compiler|the latest Microsoft C compiler]], but EiffelStudio 6.1 needs [[Installing_Microsoft_C_compiler_6.1_and_older|an older compiler]].

==EiffelStudio 6.x==
You can download the official EiffelStudio 6.x release from [http://www.eiffel.com/downloads/eiffelstudio.html Eiffel Software]. The GPL release can also be downloaded from [http://sourceforge.net/project/showfiles.php?group_id=196408 http://sflogo.sourceforge.net/sflogo.php?group_id=196408.png].

==Doc Builder==
You can download the documentation generation tool for Windows 32-bit with .NET 1.1 installed by extracting the content of [http://download.origo.ethz.ch/eiffelstudio/174/doc_builder.zip doc_builder.zip] (or [http://download.origo.ethz.ch/eiffelstudio/174/doc_builder_64-bit.zip doc_builder_64-bit.zip] for the 64-bit version) onto your hard-drive. Once installed, you can launch the tool by launching the '''doc_builder.exe''' executable.

If you have both .NET 1.1 and .NET 2.0 (or greater), you need to force the loading of .NET 1.1. To do so, edit the file '''doc_builder.exe.config''' so that its content looks like:

<xml>
<configuration>
<startup>
<requiredRuntime version="v1.1.4322" safemode="true"/>
</startup>
<runtime>
<assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
<probing privatePath="Assemblies"/>
</assemblyBinding>
</runtime>
</configuration>
</xml>

CddBranch

2010-05-31T15:23:45Z

Juliant: Reverted edits by Jacksonsophia (Talk) to last version by Aleitner

[[Category:Testing]]
[[Category:EiffelDebugger]]
[[Category:CDD]]

== What is the CDD EiffelStudio? ==

[[Image:cdd_logo.png|center]]
<center>
[http://se.ethz.ch/people/leitner/cdd/video/ '''Play CDD Video''', click here]
</center>
CDD (short for Contract Driven Development) is a project developed at [http://se.ethz.ch ETH Zurich]. It adds advanced support for unit testing to EiffelStudio. With CDD EiffelStudio you can

* Write test cases
* Manage test cases (using tags)
* Run test cases
* View test outcomes
* '''Automatically extract test cases'''

If you have questions, feedback, or would like to report a bug please visit the [http://eiffelstudio.origo.ethz.ch/forum/20 CDD forum].

CDD EiffelStudio adds the following panel to regular EiffelStudio:

[[Image:cdd_panel.png|center]]

== Publications ==

Leitner, A., Ciupa, I., Oriol, M., Meyer, B., Fiva, A., "Contract Driven Development = Test Driven Development - Writing Test Cases", in Proceedings of ESEC/FSE'07: European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering 2007, (Dubrovnik, Croatia), September 2007 [http://se.ethz.ch/people/leitner/publications/cdd_leitner_esec_fse_2007.pdf pdf] [http://se.ethz.ch/people/leitner/publications/ESEC_FSE2007.bib.txt bibtex]

Leitner, A., Pretschner A., Mori S., Meyer B., Oriol M., "On the Effectiveness of Test Extraction without Overhead", under submission

== News ==
14.May 2008: Added patch for Windows and Linux that fixes a bug that can cause a crash during extraction.

10.April 2008: If installation exits with cryptic error codes, please have a look at the [[CDD Common Problems|Common Problems]] page.

08.April 2008: CDD EiffelStudio final 7 available
* Important bug fix: EiffelStudio no longer freezes when opening projects with many test cases

02.April 2008: CDD EiffelStudio Final 6 available
* Less mess: Redundant or duplicate test cases are no longer extracted
* Smoother upgrade: Cleaning a project will automatically clean the test suite
* Fixed bug in invarant checking
* Fixed bug that caused EiffelStudio to freeze in some situations
* Improved logging
* Installer ''might'' work with mingw on Windows now. (Not yet tested, reports welcome)

== Download CDD ==

The following packages contain the full EiffelStudio 6.1 plus the CDD extension. You do not need to have EiffelStudio installed already in order to install below packages. On Windows you do have to have either the Platform SDK or Visual C++ installed. Do not use EiffelStudio with the gcc/mingw or the .Net backend.

=== Linux ===
* Full Linux version: http://se.ethz.ch/people/leitner/cdd/Eiffel61_cdd_final_7.tar.bz2
* Full Linux version (for Debian stable): http://se.ethz.ch/people/leitner/cdd/Eiffel61_cdd_final_7_debian_stable.tar.bz2
* Installation instructions: http://docs.eiffel.com/eiffelstudio/installation/studio/060_linux.html
Notes:
* If you are '''upgrading''' from a previous version, make sure you delete the old version first (rm -rf)

Download the above file and install it just like you would install a EiffelStudio tar ball. Afterwards proceed to section "Using CDD". Make sure you set/update the environment variables PATH, ISE_EIFFEL, and ISE_PLATFORM according to the installation instructions.

=== Linux Patch ===
* Patch for CDD EiffelStudio Final 7: Download http://se.ethz.ch/people/leitner/cdd/ec and replace it with the '$ISE_EIFFEL/studio/spec/linux-x86/bin/ec' from Final 7. This patch fixes a crash that sometimes occurs during extraction of test cases. You may need to delete the precompile and EIFGENs of your project after applying the patch.

=== Windows ===

* Full Windows version (with installer): http://n.ethz.ch/~moris/download/Eiffel61_cdd_final_7-windows.msi
Notes:
* Installation is independent of installations of official EiffelStudio 6.1 (neither overwrites nor invalidates nor is influenced by those)
* If you are '''upgrading''' from a previous version, you first have to uninstall the old version then delete the existing precompilations (= delete EIFGENs in subdirectories of <INSTALL_DIRECTORY>/precomp/spec/windows/) and then install the new version.
* Which C compiler to install?
** Use the Microsoft C compiler either from Visual Studio or the Windows SDK:
*** Visual Studio (up to Visual Studio 2005, but no later, and only the non-express version)
*** Windows SDK (up to version 6.0, but no later)
** Do not use the gcc/mingw.
** Do not use the .NET compiler backend.

Have a look at http://dev.eiffel.com/Installing_Microsoft_C_compiler_6.1_and_older to learn how to install either Visual C++ or the Windows SDK for use with EiffelStudio.

==== Windows Patch ====

* Patch for CDD EiffelStudio Final 7: Download http://se.ethz.ch/people/leitner/cdd/ec.exe and replace it with the '$ISE_EIFFEL/studio/spec/windows/bin/ec.exe' from Final 7. This patch fixes a crash that sometimes occurs during extraction of test cases. You may need to delete the precompile and EIFGENs of your project after applying the patch.

== Documentation ==

=== Manually Written Test Cases ===
CDD Eiffelstudio allows you to create a new “empty” test case. These test cases are similar to jUnit test cases. A manually written test class must start with the word “TEST” and all test routines also have to start with the word “test”. It also has to inherit from class CDD_TEST_CASE.

=== Extracted Test Cases ===
CDD EiffelStudio automatically extracts test cases whenever you run your program and an exception is triggered. This feature is novel and not yet part of any other testing environment. You will be the first to try it out.

=== Test outcomes ===
A test case checks whether your program contains a particular bug. A test cases can fail indicating that the bug is present in your program, or pass indicating your program does not contain this bug. Sometimes test cases will be unresolved, in which case the testing framework was unable to find out whether the test case passed or failed. A test case can be unresolved for several reasons.

[[Image:cdd_buttons.png|center]]

=== Debug Test Case ===
Select a test case and press this button to run a test case in the debugger.

=== Enable/Disable Execution of Test Cases in Background ===
If enabled, all test cases are retested every time you press compile. If disabled no test cases are executed.

=== Enable/Disable automatic extraction of Test Cases ===
If enabled every time an exception is triggered a set of test cases that try to reproduce this exception is extracted. If disabled no test cases are extracted.

=== Clean up/Delete ===
You can use the “Clean Up/Delete” button in two different ways. By simply pressing it you will delete all unresolved test cases. By pick and dropping a test case to the “Clean up/Delete” button (right click on test case, move mouse to button and right click again) you can delete a test case. By the way, test cases are just regular classes. So you can use all existing tools that apply to classes in EiffelStudio too.

Update: To remove duplicate test cases (until the next cdd update), please use the command-line tool from the [http://clean-cdd.origo.ethz.ch/ clean-cdd project].

=== Create new manual test class ===
Press this button to create a empty test class. You can then edit the class to add manually written test cases. This is how a manually written test case can look like:

<eiffel>
class TEST_BANK_ACCOUNT
inherit CDD_TEST_CASE
feature
test_deposit
local
ba: BANK_ACCOUNT
do
create ba.make_with_balance (0)
ba.deposit (100)
check
money_depisited: ba.balance = 100
end
end
end
</eiffel>

Redefine routine `set_up' or `tear_down' if you want something to be executed before resp. after every test routine of a class.

[[Image:cdd_buttons_2.png|center]]

=== Search for tags ===
Enter keywords to search for paritcular test cases. Some tags are automatically set for you like the name of the test case. You can also easily add your own tags by adding an indexing item "tag" to your test class or routine:

<eiffel>
indexing
tag: "fixme"
class TEST_BANK_ACCOUNT
inherit CDD_TEST_CASE
feature
...
end
</eiffel>

Tags can be adde to all test routines and classes. Whether they are extracted or manually written does not matter.

=== Restrict execution of test cases ===

Once you have many test cases, you will run into situation where you don't want to execute all of them. The restrict button will help you to achieve this. As long as the "Restrict" button is pushed test cases that don't show up in the test case view will not be tested. Execution is restricted to those test cases that do show up.

=== Change test case view ===

Select one of several predefined test case views. For example you can group test cases by their outcome to quickly see only failing test cases.

== Further Documentation and Common Problems ==
Please visit [[Using CDD]] for further documentation or look at
[[CDD Common Problems|Common Problems]] if you run into problems.

== Related Publications ==

* Sunghun Kim, Shay Artzi, and Michael D. Ernst, "reCrash: Making Crash Reproducible" MIT Computer Science and Artificial Intelligence Laboratory technical report MIT-CSAIL-TR-2007-054, (Cambridge, MA), November 20, 2007. [http://recrash.googlecode.com/files/MIT-CSAIL-TR-2007-054.pdf (pdf)]

== Project Internal Stuff ==

[[CddBranchInternal]]

2010 News

2010-05-31T09:48:18Z

Juliant: fixed typo

[[Category:News]]
All the exciting news of the year 2010.

==May 26th==
EiffelStudio 6.6 release available

==March 24th==
Dr. Meyer is the recipient of the 2009 Harlan D. Mills award

Talk:Single-level call rule and generics

2007-07-15T17:16:04Z

Juliant:

Look very close to my suggestion, only that I had suggested to reuse the keyword 'invariant' instead of introducing a new keyword 'monomorphic', that not average developer will understand --[[User:Schoelle|Schoelle]] 14:02, 15 July 2007 (CEST)

'''--[[User:Juliant|Juliant]] 19:16, 15 July 2007 (CEST)''' This is a different problem. Your proposal about invariant generics is about ''conformance'' between generic parameters, i.e. conformance between <e>X [A]</e> and <e>X [B]</e>. What I'm trying to point out is the ''use'' of features on a formal generic parameter which are covariantly redefined. The possible solution for ''like Current'' features with the monomorphic keyword is about the instantation of the generic. A monomorphic generic can only be instantiated with a monomorphic type.

You can also look at it that way: With your ''invariant'' generic, you can use the generic as a feature argument. With a ''monomorph'' generic, you can call covariant features which have ''like Current'' in the argument.

Single-level call rule and generics

2007-07-14T18:58:07Z

Juliant: /* Monomorph formal generics */

[[Category:ECMA]]
[[Category:Catcall]]
== Problem ==

The single-level call rule says that every call has to be valid for all possible dynamic types of an entity. So for a formal generic <e>G</e> this means that the call has to be valid for all possible descendants of the constraint (or at least for every instantiation which happens in a system).

Let's look at an example using <e>NUMERIC</e>:

<e>
class X [G -> NUMERIC]

feature

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

Here, the call to <e>+</e> has to be valid for all possible descendants of <e>NUMERIC</e>. Since the signature of the feature is <e>like Current</e>, the call is never valid. This has to be the case as otherwise, the following code would produce a catcall:

<e>
x: X [NUMERIC]
x.f (1, 1.0)
</e>

The problem is that the formal generic <e>G</e> is always assumed to be of any type which satisfies the constraint, so normally the formal generic is polymorph.

As the above example show, the use of features on formal generic parameters which are covariantly redefined is severely limited. But as the purpose of <e>NUMERIC</e> is exactly to allow creation of generic algorithms over numeric types, this has to be addressed (Note that also <e>COMPARABLE</e> is a problem).

== Possible solutions ==

=== Monomorph formal generics ===

The first idea is to be able to mark a formal generic as monomorph:
<e>
class X [monomorph G -> NUMERIC]

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

The generic class can then only be instantiated with monomorphic types, i.e. using [[interval types]] <e>X [INTEGER..INTEGER]</e> or <e>X [REAL..REAL]</e>.

For the check we can now assume that <e>G</e> will be monomorphic. This helps a little bit further: For every feature argument which is <e>like Current</e> we can assume that the exact type will be given. But this works only for covariant features which have <e>like Current</e> arguments which are never redefined into something else. Take the following classes for an example:

<e>
class A
feature
f (a: like Current) do end
end

class B
inherit A
end

class C
inherit A redefine f
feature
f (a: D) do end
end

class D
inherit C
end
</e>

Now assume the following generic class:

<e>
class X [monomorph G -> A]
feature
f
local
g1, g2: G
do
g1.f (g2)
end
end
</e>

The call to <e>g1.f</e> is not valid since <e>G</e> could be of type <e>C</e>, and then the argument has to be of type <e>D</e>. So now, not even the <e>like Current</e> feature is callable with monomorphic generics. Basically it is the same as the declaration without ''monomorphic'' for the generic.

So this solution works only for the case of <e>like Current</e> features never change the signature. Only then it can be guaranteed for a monomorphic generic formal, that the signature will match the formal generic exactly. Other covariant features have still to be valid for all possible descendants.

For the case of <e>NUMERIC</e> and <e>COMPARABLE</e> the use of monomorphic formal arguments would work as they define only <e>like Current</e> features which are normally kept that way in subclasses. A more general mechanism would be nice but at the moment it is unclear how such a mechanism should look like.

=== Remodeling library ===

Another way to solve the problem of <e>NUMERIC</e> and <e>COMPARABLE</e> would be to change the library. As these classes have mostly <e>like Current</e> arguments and result types, they can be modeled via generics in the first place.

For example:

<e>
class NUMERIC [G -> NUMERIC [G]]
feature
infix "+" (other: G): G
end

class COMPARABLE [G -> COMPARABLE [G]]
feature
less_than (other: G): BOOLEAN
end
</e>

With this approach, the use of the general class <e>NUMERIC</e> and <e>COMPARABLE</e> will become more complicated, but since they appear in libraries most of the time it could be done.

Single-level call rule and generics

2007-07-14T18:32:06Z

Juliant: /* Monomorph formal generics */

[[Category:ECMA]]
[[Category:Catcall]]
== Problem ==

The single-level call rule says that every call has to be valid for all possible dynamic types of an entity. So for a formal generic <e>G</e> this means that the call has to be valid for all possible descendants of the constraint (or at least for every instantiation which happens in a system).

Let's look at an example using <e>NUMERIC</e>:

<e>
class X [G -> NUMERIC]

feature

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

Here, the call to <e>+</e> has to be valid for all possible descendants of <e>NUMERIC</e>. Since the signature of the feature is <e>like Current</e>, the call is never valid. This has to be the case as otherwise, the following code would produce a catcall:

<e>
x: X [NUMERIC]
x.f (1, 1.0)
</e>

The problem is that the formal generic <e>G</e> is always assumed to be of any type which satisfies the constraint, so normally the formal generic is polymorph.

As the above example show, the use of features on formal generic parameters which are covariantly redefined is severely limited. But as the purpose of <e>NUMERIC</e> is exactly to allow creation of generic algorithms over numeric types, this has to be addressed (Note that also <e>COMPARABLE</e> is a problem).

== Possible solutions ==

=== Monomorph formal generics ===

The first idea is to be able to mark a formal generic as monomorph:
<e>
class X [monomorph G -> NUMERIC]

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

The generic class can then only be instantiated with monomorphic types, i.e. using [[interval types]] <e>X [INTEGER..INTEGER]</e> or <e>X [REAL..REAL]</e>.

For the check we can now assume that <e>G</e> will be monomorphic. This helps a little bit further: For every feature argument which is <e>like Current</e> we can assume that the exact type will be given. But this works only for covariant features which have <e>like Current</e> arguments which are never redefined into something else. Take the following classes for an example:

<e>
class A
feature
f (a: like Current) do end
end

class B
inherit A
end

class C
inherit A redefine f
feature
f (a: D) do end
end

class D
inherit C
end
</e>

Now assume the following generic class:

<e>
class X [monomorph G -> A]
feature
f
local
g1, g2: G
do
g1.f (g2)
end
end
</e>

The call to <e>g1.f</e> is not valid since <e>G</e> could be of type <e>C</e>, and then the argument has to be of type <e>D</e>. So now, not even the <e>like Current</e> feature is callable with monomorphic generics. Basically it is the same as the declaration without ''monomorphic'' for the generic.

So this solution works only for the case of <e>like Current</e> features which are never redefined. Only then it can be guaranteed for a monomorphic generic formal, that the signature will match the formal generic exactly. Other covariant features have still to be valid for all possible descendants.

For the case of <e>NUMERIC</e> and <e>COMPARABLE</e> the use of monomorphic formal arguments would work as they define only <e>like Current</e> features which are normally kept that way in subclasses. A more general mechanism would be nice but at the moment it is unclear how such a mechanism should look like.

=== Remodeling library ===

Another way to solve the problem of <e>NUMERIC</e> and <e>COMPARABLE</e> would be to change the library. As these classes have mostly <e>like Current</e> arguments and result types, they can be modeled via generics in the first place.

For example:

<e>
class NUMERIC [G -> NUMERIC [G]]
feature
infix "+" (other: G): G
end

class COMPARABLE [G -> COMPARABLE [G]]
feature
less_than (other: G): BOOLEAN
end
</e>

With this approach, the use of the general class <e>NUMERIC</e> and <e>COMPARABLE</e> will become more complicated, but since they appear in libraries most of the time it could be done.

Single-level call rule and generics

2007-07-14T01:01:23Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
== Problem ==

The single-level call rule says that every call has to be valid for all possible dynamic types of an entity. So for a formal generic <e>G</e> this means that the call has to be valid for all possible descendants of the constraint (or at least for every instantiation which happens in a system).

Let's look at an example using <e>NUMERIC</e>:

<e>
class X [G -> NUMERIC]

feature

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

Here, the call to <e>+</e> has to be valid for all possible descendants of <e>NUMERIC</e>. Since the signature of the feature is <e>like Current</e>, the call is never valid. This has to be the case as otherwise, the following code would produce a catcall:

<e>
x: X [NUMERIC]
x.f (1, 1.0)
</e>

The problem is that the formal generic <e>G</e> is always assumed to be of any type which satisfies the constraint, so normally the formal generic is polymorph.

As the above example show, the use of features on formal generic parameters which are covariantly redefined is severely limited. But as the purpose of <e>NUMERIC</e> is exactly to allow creation of generic algorithms over numeric types, this has to be addressed (Note that also <e>COMPARABLE</e> is a problem).

== Possible solutions ==

=== Monomorph formal generics ===

The first idea is to be able to mark a formal generic as monomorph:
<e>
class X [monomorph G -> NUMERIC]

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

The generic class can then only be instantiated with monomorphic types, i.e. using [[interval types]] <e>X [INTEGER..INTEGER]</e> or <e>X [REAL..REAL]</e>.

For the check we can now assume that <e>G</e> will be monomorphic. This helps a little bit further: For every feature argument which is <e>like Current</e> we can assume that the exact type will be given. But this works only for covariant features which have <e>like Current</e> arguments which are never redefined into something else. Take the following classes for an example:

<e>
class A
feature
f (a: like Current) do end
end

class B
inherit A
end

class C
inherit A redefine f
feature
f (a: D) do end
end

class D
inherit C
end
</e>

Now assume the following generic class:

<e>
class X [monomorph G -> A]
feature
f
local
g1, g2: G
do
g1.f (g2)
end
end
</e>

The call to <e>g1.f</e> is not valid since <e>G</e> could be of type <e>C</e>, and then the argument has to be of type <e>D</e>. So now, not even the <e>like Current</e> feature is callable with monomorphic generics. Basically it is the same as the declaration without ''monomorphic'' for the generic.

So this solution works only for the case of <e>like Current</e> features which are never redefined. Only then it can be guaranteed for a monomorphic generic formal, that the signature will match the formal generic exactly. Other covariant features have still to be valid for all possible descendants.

For the case of <e>NUMERIC</e> and <e>COMPARABLE</e> the use of monomorphic formal arguments would work as they define only <e>like Current</e> features which are normally not redefined in subclasses. A more general mechanism would be nice but at the moment it is unclear how such a mechanism should look like.

=== Remodeling library ===

Another way to solve the problem of <e>NUMERIC</e> and <e>COMPARABLE</e> would be to change the library. As these classes have mostly <e>like Current</e> arguments and result types, they can be modeled via generics in the first place.

For example:

<e>
class NUMERIC [G -> NUMERIC [G]]
feature
infix "+" (other: G): G
end

class COMPARABLE [G -> COMPARABLE [G]]
feature
less_than (other: G): BOOLEAN
end
</e>

With this approach, the use of the general class <e>NUMERIC</e> and <e>COMPARABLE</e> will become more complicated, but since they appear in libraries most of the time it could be done.

Single-level call rule and generics

2007-07-14T01:00:48Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Problem ==

The single-level call rule says that every call has to be valid for all possible dynamic types of an entity. So for a formal generic <e>G</e> this means that the call has to be valid for all possible descendants of the constraint (or at least for every instantiation which happens in a system).

Let's look at an example using <e>NUMERIC</e>:

<e>
class X [G -> NUMERIC]

feature

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

Here, the call to <e>+</e> has to be valid for all possible descendants of <e>NUMERIC</e>. Since the signature of the feature is <e>like Current</e>, the call is never valid. This has to be the case as otherwise, the following code would produce a catcall:

<e>
x: X [NUMERIC]
x.f (1, 1.0)
</e>

The problem is that the formal generic <e>G</e> is always assumed to be of any type which satisfies the constraint, so normally the formal generic is polymorph.

As the above example show, the use of features on formal generic parameters which are covariantly redefined is severely limited. But as the purpose of <e>NUMERIC</e> is exactly to allow creation of generic algorithms over numeric types, this has to be addressed (Note that also <e>COMPARABLE</e> is a problem).

== Possible solutions ==

=== Monomorph formal generics ===

The first idea is to be able to mark a formal generic as monomorph:
<e>
class X [monomorph G -> NUMERIC]

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

The generic class can then only be instantiated with monomorphic types, i.e. using [[interval types]] <e>X [INTEGER..INTEGER]</e> or <e>X [REAL..REAL]</e>.

For the check we can now assume that <e>G</e> will be monomorphic. This helps a little bit further: For every feature argument which is <e>like Current</e> we can assume that the exact type will be given. But this works only for covariant features which have <e>like Current</e> arguments which are never redefined into something else. Take the following classes for an example:

<e>
class A
feature
f (a: like Current) do end
end

class B
inherit A
end

class C
inherit A redefine f
feature
f (a: D) do end
end

class D
inherit C
end
</e>

Now assume the following generic class:

<e>
class X [monomorph G -> A]
feature
f
local
g1, g2: G
do
g1.f (g2)
end
end
</e>

The call to <e>g1.f</e> is not valid since <e>G</e> could be of type <e>C</e>, and then the argument has to be of type <e>D</e>. So now, not even the <e>like Current</e> feature is callable with monomorphic generics. Basically it is the same as the declaration without ''monomorphic'' for the generic.

So this solution works only for the case of <e>like Current</e> features which are never redefined. Only then it can be guaranteed for a monomorphic generic formal, that the signature will match the formal generic exactly. Other covariant features have still to be valid for all possible descendants.

For the case of <e>NUMERIC</e> and <e>COMPARABLE</e> the use of monomorphic formal arguments would work as they define only <e>like Current</e> features which are normally not redefined in subclasses. A more general mechanism would be nice but at the moment it is unclear how such a mechanism should look like.

=== Remodeling library ===

Another way to solve the problem of <e>NUMERIC</e> and <e>COMPARABLE</e> would be to change the library. As these classes have mostly <e>like Current</e> arguments and result types, they can be modeled via generics in the first place.

For example:

<e>
class NUMERIC [G -> NUMERIC [G]]
feature
infix "+" (other: G): G
end

class COMPARABLE [G -> COMPARABLE [G]]
feature
less_than (other: G): BOOLEAN
end
</e>

With this approach, the use of the general class <e>NUMERIC</e> and <e>COMPARABLE</e> will become more complicated, but since they appear in libraries most of the time it could be done.

Single-level call rule and generics

2007-07-14T00:55:29Z

Juliant:

== Problem ==

The single-level call rule says that every call has to be valid for all possible dynamic types of an entity. So for a formal generic <e>g</e> this means that the call has to be valid for all possible descendants of the constraint (or at least for every instantiation which happens in a system).

Let's look at an example using <e>NUMERIC</e>:

<e>
class X [G -> NUMERIC]

feature

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

Here, the call to <e>+</e> has to be valid for all possible descendants of <e>NUMERIC</e>. Since the signature of the feature is <e>like Current</e>, the call is never valid. This has to be the case as otherwise, the following code would produce a catcall:

<e>
x: X [NUMERIC]
x.f (1, 1.0)
</e>

The problem is that the formal generic <e>G</e> is always assumed to be of any type which satisfies the constraint, so normally the formal generic is polymorph.

As the above example show, the use of features on formal generic parameters which are covariantly redefined is severely limited. But as the purpose of <e>NUMERIC</e> is exactly to allow creation of generic algorithms over numeric types, this has to be addressed (Note that also <e>COMPARABLE</e> is a problem).

== Possible solutions ==

=== Monomorph formal generics ===

The first idea is to be able to mark a formal generic as monomorph:
<e>
class X [monomorph G -> NUMERIC]

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

The generic class can then only be instantiated with monomorphic types, i.e. using [[interval types]] <e>X [INTEGER..INTEGER]</e> or <e>X [REAL..REAL]</e>.

For the check we can now assume that <e>G</e> will be monomorphic. This helps a little bit further: For every feature argument which is <e>like Current</e> we can assume that the exact type will be given. But this works only for covariant features which have <e>like Current</e> arguments which are never redefined into something else. Take the following classes for an example:

<e>
class A
feature
f (a: like Current) do end
end

class B
inherit A
end

class C
inherit A redefine f
feature
f (a: D) do end
end

class D
inherit C
end
</e>

Now assume the following generic class:

<e>
class X [monomorph G -> A]
feature
f
local
g1, g2: G
do
g1.f (g2)
end
end
</e>

The call to <e>g1.f</e> is not valid since <e>G</e> could be of type <e>C</e>, and then the argument has to be of type <e>D</e>. So now, not even the <e>like Current</e> feature is callable with monomorphic generics. Basically it is the same as the declaration without ''monomorphic'' for the generic.

So this solution works only for the case of <e>like Current</e> features which are never redefined. Only then it can be guaranteed for a monomorphic generic formal, that the signature will match the formal generic exactly. Other covariant features have still to be valid for all possible descendants.

For the case of <e>NUMERIC</e> and <e>COMPARABLE</e> the use of monomorphic formal arguments would work as they define only <e>like Current</e> features which are normally not redefined in subclasses. A more general mechanism would be nice but at the moment it is unclear how such a mechanism should look like.

=== Remodeling library ===

Another way to solve the problem of <e>NUMERIC</e> and <e>COMPARABLE</e> would be to change the library. As these classes have mostly <e>like Current</e> arguments and result types, they can be modeled via generics in the first place.

For example:

<e>
class NUMERIC [G -> NUMERIC [G]]
feature
infix "+" (other: G): G
end

class COMPARABLE [G -> COMPARABLE [G]]
feature
less_than (other: G): BOOLEAN
end
</e>

With this approach, the use of the general class <e>NUMERIC</e> and <e>COMPARABLE</e> will become more complicated, but since they appear in libraries most of the time it could be done.

Single-level call rule and generics

2007-07-14T00:51:34Z

Juliant:

== Problem ==

The single-level call rule says that every call has to be valid for all possible dynamic types of an entity. So for a formal generic <e>g</e> this means that the call has to be valid for all possible descendants of the constraint (or at least for every instantiation which happens in a system).

Let's look at an example using <e>NUMERIC</e>:

<e>
class X [G -> NUMERIC]

feature

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

Here, the call to <e>+</e> has to be valid for all possible descendants of <e>NUMERIC</e>. Since the signature of the feature is <e>like Current</e>, the call is never valid. This has to be the case as otherwise, the following code would produce a catcall:

<e>
x: X [NUMERIC]
x.f (1, 1.0)
</e>

The problem is that the formal generic <e>G</e> is always assumed to be of any type which satisfies the constraint, so normally the formal generic is polymorph.

As the above example show, the use of features on formal generic parameters which are covariantly redefined is severly limited. But as the purpose of <e>NUMERIC</e> is exactly to allow creation of generic algorithms over numeric types, this has to be addressed (Note that also <e>COMPARABLE</e> is a problem).

== Possible solutions ==

=== Monomorph formal generics ===

The first idea is to be able to mark a formal generic as monomorph:
<e>
class X [monomorph G -> NUMERIC]

f (g1, g2: G): G
do
Result := g1 + g2
end

end
</e>

The generic class can then only be instantiated with monomorphic types, i.e. using [[interval types]] <e>X [INTEGER..INTEGER]</e> or <e>X [REAL..REAL]</e>.

For the check we can now assume that <e>G</e> will be monomorphic. This helps a little bit furhter: For every feature argument which is <e>like Current</e> we can assume that the exact type will be given. But this works only for covariant features which have <e>like Current</e> arguments which are never redefined into something else. Take the following classes for an example:

<e>
class A
feature
f (a: like Current) do end
end

class B
inherit A
end

class C
inherit A redefine f
feature
f (a: D) do end
end

class D
inherit C
end
</e>

Now assume the following generic class:

<e>
class X [monomorph G -> A]
feature
f
local
g1, g2: G
do
g1.f (g2)
end
end
</e>

The call to <e>g1.f</e> is not valid since <e>G</e> could be of type <e>C</e>, and then the argument has to be of type <e>D</e>. So now, not even the <e>like Current</e> feature is callable with monomorphic generics. Basically it is the same as the declaration without ''monomorphic'' for the generic.

So this solution works only for the case of <e>like Current</e> features which are never redefined. Only then it can be guaranteed for a monomorphic generic formal, that the signature will match the formal generic exactly. Other covariant features have still to be valid for all possible descendants.

For the case of <e>NUMERIC</e> and <e>COMPARABLE</e> the use of monomorphic formal arguments would work as they define only <e>like Current</e> features which are normally not redefined in subclasses. A more general mechanism would be nice but at the moment it is unclear how such a mechanism should look like.

=== Remodeling library ===

Another way to solve the problem of <e>NUMERIC</e> and <e>COMPARABLE</e> would be to change the library. As these classes have mostly <e>like Current</e> arguments and result types, they can be modeled via generics in the first place.

For example:

<e>
class NUMERIC [G -> NUMERIC [G]]
feature
infix "+" (other: G): G
end

class COMPARABLE [G -> COMPARABLE [G]]
feature
less_than (other: G): BOOLEAN
end
</e>

With this approach, the use of the general class <e>NUMERIC</e> and <e>COMPARABLE</e> will become more complicated, but since they appear in libraries most of the time it could be done.

Talk:Interval types

2007-07-11T17:01:04Z

Juliant:

'''--[[User:Schoelle|Schoelle]] 12:33, 8 July 2007 (CEST)''': Could somebody illustrate how this solves the problem of convariant argument redefinition using 'like Current' or similar?

:'''--[[User:Manus|manus]] 18:14, 8 July 2007 (CEST)''': This case is just a typical case of implicit covariance. The rules are the same and therefore any feature involving `like Current' in its arguments will most likely be rejected in some cases unless the target is monomorphic. Dont' forget that it is mostly the case with `is_equal' and `copy' which are getting new signatures in the new ECMA standard. For COMPARABLE then it just mean that you won't be able to compare apple with oranges which is exactly what we are trying to avoid.

'''--[[User:Schoelle|Schoelle]] 15:30, 10 July 2007 (CEST)''' Thanks for the answer, this was enlighting. Second question: can anybody give examples from the practice that are different from A..A and A..NONE ? Something like A..B that really is needed and makes sense?

:'''--[[User:Seilerm|Seilerm]] 20:33, 10 July 2007 (CEST)''': I think this comes down to the very question where covariance on ordinary types is needed. If you want I can give a lot of examples for generics, probably because it is the main source where I personally use covariance. Besides that: I have seen code where one uses anchored types (i.e. the like keyword) to anchor argument types to the type of queries (mostly attributes). And then the query result type is redefined covariantly. This might be interesting if otherwise you would need a lot of generic parameters, but you only redefine a few times different query (attribute) types in your class hierarchy. That being said, I personally don't like this style of coding.

'''--[[User:Schoelle|Schoelle]] 12:13, 11 July 2007 (CEST)''' Ok, lets me see if I can correctly summarize, relating to my article [http://www.fams.de/text/type-safe-eiffel.html]. I am not doing this to advertise for my solution, but just because it is easier for me to understand something new by relating it to something that I have understood.

For ''Covariant arguments and anchored types'', we are (more or less) removing covariance from the language (the conformance rules have been made so restrictive that the BOAT/SKIPPER/CAT/CAT_SKIPPER example becomes illegal), as demanded in my article. '''(1)'''

For ''Genericity'', we are using rules similar to Wildcard types in Java, which disallows calls to features with arguments of a generic type (X[A..A] is X<A> in Java, X[A..NONE] is X<? extends A> in Java). '''(2)'''

I think that the approach of invariant arguments described in my paper is more elegant (I am probably just locked into own ideas), as the decision of using a generic parameter covariantly is made by the supplier and not the client, i.e. it becomes part of the library design. But if Java people can live with Wildcard types, so can we ... ;-) '''(3)'''

:'''--[[User:Juliant|Juliant]] 19:01, 11 July 2007 (CEST)'''
:for '''(1)''': Actually it's not the conformance rules that have been restricted, but the feature call rules. Per default you still have full conformance between normal types, but you mostly cannot call covariant features. In the end it is the same, restricting covariance as much as you probably won't use it anymore.
:for '''(2)''': Yes, they are very similar.
:for '''(3)''': The problem with the [[definition-site variance#Conclusion|invariant arguments]] you described is that they break the library for sure. Since one of the criterias for a catcall solution is backwards compatibility, this is not an option. If you would be starting from scratch, it may be a good option as the use of a generic is dictated by the library designer and it could be easier to use by the programmer.

Comparison of catcall solutions

2007-07-06T16:34:03Z

Juliant: /* Overview of general solutions */

[[Category:ECMA]]
[[Category:Catcall]]
== 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 [[Single level call rule implementation|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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> where the feature <e>put</e> changes signature from <e>ANY</e> to <e>INTEGER</e>.
* 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 <e>like Current</e>. 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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> only the features based on the formal change their signature while they don't change from <e>LIST [ANY]</e> to <e>LINKED_LIST [ANY]</e> 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 <e>STRING</e> or one for <e>ANY</e> is suitable.
* If you want to pass an argument of type <e>STRING</e> to an agent, the agent either has to accept a <e>STRING</e> or <e>ANY</e> 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 [http://dev.eiffel.com/Covariance_through_renaming 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: [http://dev.eiffel.com/Forget_/_Keep_Mechanism 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.

== 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueFLEX_CATCALL IssueFLEX_CATCALL on ECMA wiki] 
Reference: Discussion in ECMA mailinglist named ''Catcall removal: another proposal'', [[Restrict types mail|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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueDOG 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: [http://pag.csail.mit.edu/reading-group/variance-ECOOP02.pdf 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: [http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx Article about generics in CLR]

Note: There is also a [http://fams.de/text/type-safe-eiffel.html 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: [http://www.jot.fm/issues/issue_2004_12/article5 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: [http://se.ethz.ch/~meyer/publications/lncs/attached.pdf Article about ''attached types'' by Bertrand Meyer] 
Reference: [http://www.ecma-international.org/publications/standards/Ecma-367.htm 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueCAT IssueCAT on ECMA wiki] 
Reference: [http://www.inf.ethz.ch/~meyer/ongoing/covariance/recast.pdf 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 [[Comparison of catcall solutions#Table_explained|explanation at the end of the table]] for more information

=== General solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Novariance]]
! [[Forget / keep]]
! Dynamic typeset algorithm

|-

! Syntax overhead
| {{Green|No}}
| {{Red|Big}}: forget/keep clauses per type
| {{Green|No}}

|-

! Covariance on non-generic types
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| {{Red|Very limited}}: Only invariant conformance
| {{Orange|Limited}}: Conformance restricted (''keep all'' as default) {{Orange|Limited}}: Use restricted (''forget all'' as default)
| {{Green|As it is now}}

|-

! Agents
| {{Orange|Limited}} {{Green|Safe}}
| {{Orange|Limited}} {{Green|Safe}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on forget/keep clauses
| {{Red|Big}}: Iterative abstract system execution

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Need to know cat features for object tests
| {{Green|Small}}: As it is now

|-

! Whole-system analysis
| {{Green|No}}
| {{Red|Yes}}: use of ''forget all'' depends on system
| {{Red|Yes}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Red|No}}
| {{Red|No}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Orange|Limited}}
| {{Green|Full}}

|-

! Support of IDE (Source changes)
| {{Green|Not needed}}
| {{Orange|Possible}}: Can propose forget/keep clauses
| {{Green|Not needed}}

|}

=== Solutions for non-generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Restrict types]]
! [[DOG proposal]]

|-

! Syntax overhead
| {{Red|Big}}: Restrict clause per type declaration
| {{Orange|Medium}}: ''cat'' on features and on type declarations

|-

! Covariance on non-generic types
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| Not addressed
| Not addressed

|-

! Agents
| Not addressed
| Not addressed

|-

! Comparator
| Not addressed
| Not addressed

|-

! Complexity of compiler check
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on restrict clauses
| {{Green|Small}}: Check of ''cat'' on conformance

|-

! Complexity of runtime
| not yet considered
| {{Green|Small}}

|-

! Whole-system analysis
| {{Orange|Partial}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Orange|Limited}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Red|Very limited}}

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose restrict clauses
| {{Orange|Possible}}: Can propose ''cat'' marks

|}

=== Solutions for generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Usage-site variance]]
! [[Definition-site variance]]
! Wildcard generics

|-

! Syntax overhead
| {{Orange|Medium}}: Variance marks per generic type
| {{Green|Small}}: Variance marks per generic class definition
| {{Orange|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
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}

|-

! Agents
| {{Green|Fully supported}} {{Green|Safe}}
| {{Green|Fully supported}}: If tuples can be specified covariantly {{Green|Safe}}
| {{Green|Fully supported}} {{Green|Safe}}

|-

! Comparator
| {{Green|Supported}}
| {{Green|Supported}}
| {{Green|Supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check

|-

! Complexity of runtime
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Orange|Limited}}: Use of generics changed due to conformance
| {{Red|Very limited}}: Libraries need redesign
| {{Orange|Limited}}: Use of generics changed due to conformance

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose variance marks
| {{Red|Not possible}}: Libraries need redesign
| {{Orange|Possible}}: Can propose variance marks/wildcards

|}

=== Dynamic solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Detachable types]]
! Recast
! Exceptions

|-

! Syntax overhead
| {{Green|Small}}: Detachment marks
| {{Red|Big}}: Recast clauses, recast features
| {{Orange|Medium}}: If rescue clause mandatory {{Green|No}}: If rescue clause not needed

|-

! Covariance on non-generic types
| {{Red|Very limited}}: Only detached arguments, no expanded arguments
| {{Green|Allowed}}
| {{Green|Allowed}}
|-

! Export status restrictions
| Not addressed
| Not addressed
| Not addressed

|-

! Use of generics
| {{Red|Very limited}}: Only detachable formal arguments
| {{Red|Very limited}}: Recast clause for all features with formal generics
| {{Green|As it is now}}

|-

! Agents
| {{Red|As it is now}}
| {{Red|As it is now}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Check for catcalls and do recast
| {{Orange|Medium}}: Check for catcalls and raise exception

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}: All covariant and generic features become detached
| {{Red|Very limited}}: All covariant and generic features need recast clause
| {{Orange|Limited}}: If rescue clause is mandatory {{Green|Full}}: If rescue clause not needed

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose detachment marks
| {{Red|Not possible}}: Programmer must provide recast clause
| {{Red|Not possible}}: If rescue clause mandatory {{Green|Not needed}}: If rescue clause not needed

|}

=== Table explained ===

; Syntax overhead : {{Green|Small}} if a keyword/mark is needed per class/feature declaration; {{Orange|Medium}} if a keyword/mark is neede per type declaration; {{Red|Big}} if a clause is needed per type declaration.
; Use of generics : {{Green|As it is now}} if assignments are possible if generic parameters conform; {{Orange|Limited}} is some restrictions in the use or the conformance between generics exist; {{Red|Very limited}} a lot of restrictions in the use or the conformance between generics exist.
; Agents : {{Green|Fully supported}} if all safe assignments are allowed; {{Orange|Limited}} if not all safe assignments are allowed; {{Red|As it is now}} if unsafe assignments are still possible.
; Comparator : {{Green|Supported}} if for a comparator all safe assignments are permitted (i.e. contravariant assignments); {{Red|Not supported}} if only exact type or even (unsafe) subtypes can be assigned.
; Support of IDE (Source changes) : {{Green|Not needed}} if everything still works the same; {{Orange|Possible}} if the compiler can suggest clauses or marks; {{Red|Not possible}} if the programmer has to specify additional features/instructions.

== Personal opinions ==

[[Personal view about catcall solution]]

Read-write types

2007-07-06T16:31:21Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

The read-write proposal gives the programmer the possibility to specify per type declaration a ''read type'' and a ''write type''. The read type is used to specify applicable features and their return type (reading from the type). The write type is used to do the check on the feature signature for calling features (writing to the type).

This solution is a superset of two other solutions: [[interval types]] (without the generic rule) and [[usage-site variance]]. Thus it is the more general mechanism than these two as it solves normal and generic types in the same way and can express the same and more than the other two solutions.

It involves syntax overhead for complex problems which is due to the greater expressiveness. But with sensible default values it is as easy to use in the normal case as the other two solutions.

== Syntax ==

In order to express the read type and the write type, a type declaration is split into two parts. For the following discussion two keywords - '''read''' and '''write''' - are used.

If either the read or the write type is omitted, a default behaviour is assumed which will be shown later on. A type can be declared in the following way:

<e>
a: ANY -- Default semantics apply
b: read ANY write ANY
c: read LIST [read ANY write NONE] write NONE
d: read LIST [STRING] write NONE [STRING]
</e>

The syntax is very similar to the interval types, just replace '''write''' with '''..''' and omit the '''read''' keyword. Then the only difference is the generic parameters in the write type which don't appear in the interval definition, especially the generic parameters for class NONE are a special notation.

== Semantics ==

The meaning of a read-write type <e>read A write B</e> is the following: All features which are available are those of <e>A</e> and all calls have to be valid with the signature of the type <e>B</e>. If the write type is <e>NONE</e>, then the call has to be system-valid for all descendants of the read type. This is essentially the same as interval types.

The difference is, that the write type can be <e>NONE</e> but still has generic parameters. This is needed to distinguish the covariantly redefined features from the formal features and apply different settings for these feature groups.

If the read type has generic parameters, but the write type does not, then no features with formal arguments may be called. If the read type has generics and the write type has too, than the formal arguments for the signature are taken from the write type. This is the same as for covariantly redefined features where the signature is taken from the write type.

Some examples:

<e>
local
a: read ANY write NONE -- features from ANY, whole-system analysis (polymorphic)
b: read ANY write STRING -- features from ANY, signature from STRING
c: read STRING write STRING -- features from STRING, signature from STRING (monomorphic)
-- read-only list
d: read LIST [read ANY write NONE] write NONE
-- list with monomorphic STRING elements
e: read LIST [read STRING write STRING] write NONE [read STRING write STRING]
do
b.is_equal ({STRING})
-- b.to_upper -- feature 'to_upper' is not in ANY
c.is_equal ({STRING})
c.to_upper
d.item = {read ANY write NONE}
-- d.put -- no generics in write type, thus no features with formal arguments
e.item = {read STRING write STRING}
e.put ({read STRING write STRING})
end
</e>

=== Conformance rules ===

* A read-write type <e>a</e> conforms to a read-write type <e>b</e> if the read type of <e>a</e> conforms to the read type of <e>b</e> and the write type of <e>b</e> conforms to the write type of <e>a</e>.
* The same goes for the generics part, the generics of the read type of <e>a</e> have to conform to the generics of the read type of <e>a</e> and the generics of the write type of <e>b</e> have to conform to the generics of the write type of <e>a</e>

Some examples:

<e>
local
a: read ANY write NONE
b: read ANY write STRING
c: read STRING write STRING
d: read LIST [read ANY write NONE] write NONE -- read-only list
e: read LIST [read STRING write STRING] write NONE [read STRING write STRING]
f: read LINKED_LIST [read ANY write NONE] write LINKED_LIST [read ANY write NONE]
do
-- valid
a := b
a := c
b := c
d := e
d := f
end
</e>

=== Default behaviour ===

Although this solution has some syntax overhead, the default behaviour gets rid of most of it.

It is assumed here that <e>NONE</e> also conforms to expanded types. See the [[Interval_types#Conclusion|conclusion of interval types]] for more information.

The default for a normal type <e>X</e> is a polymorphic type:

<e>
a: X -- means 'read X write NONE'
</e>

The default for a generic type is a read-write type which is polymorphic in the base class and invariant in the generic parameter:

<e>
b: X [Y] -- means 'read X [Y] write NONE [Y]'
</e>

And if you write the ''read'' type but omit the ''write'' type, then the write type is always <e>NONE</e>. This is useful for generics as you can define a read-only type which is covariantly in the generic parameter:

<e>
c: read X -- means 'read X write NONE', (the same as just 'X')
d: read X [Y] -- means 'read X [Y] write NONE'
</e>

Thanks to these defaults, code which does not rely on generic conformance should work as before:

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- means 'read ANY write NONE'
list: LIST [ANY] -- means 'read LIST [read ANY write NONE] write NONE [read ANY write NONE]'
l_list: LINKED_LIST [ANY] -- means 'read LINKED_LIST [read ANY write NONE] write NONE [read ANY write NONE]'
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

If you want to assign generics with different parameters, you need to mark the target as read-only by specifying the type only as a ''read'' type, i.e. <e>read LIST [ANY]</e> if you want to assign any possible list.

== Comparison with other solutions ==

Interesting about this solution is that it two others can be mapped to it:

=== [[Interval types]] ===

For non-generic types, the read-write types are just like interval types:

<e>
a: ANY..NONE <=> read ANY write NONE
b: X..Y <=> read X write Y
</e>

The conformance rules and the default behaviour is the same.

=== [[Usage-site variance]] ===

The usage-site variance can also be expressed by read-write types:

<e>
-- invariant
a: LIST [ STRING] <=> read LIST [STRING] write NONE [STRING]
-- covariant
b: LIST [+STRING] <=> read LIST [STRING] write NONE
-- contravariant
c: LIST [-STRING] <=> read LIST [ANY] write NONE [STRING]
</e>

Note that due to the default behaviour of read-write types, the invariant generics can be expressed the same in read-write types and that covariant generics can be defined as <e>read LIST [STRING]</e>.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

For more examples, look at the examples section of [[interval types]] and [[usage-site variance]]. With the above mapping, all examples can easily be changed into read-write type examples.

=== A simple generic algorithm ===

It is easy to declare an algorithm over generics as long as only read-access is needed. Just declare input to the algorithm as read-only list.

<e>
class PERSON_PRINTER
feature
print_all (a_list: read LIST [PERSON])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a read-only list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT]
l_professors: LIST [PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT] conforms to read LIST [PERSON]
l_person_printer.print_all (l_students)
-- LIST [PROFESSPR] conforms to read LIST [PERSON]
l_person_printer.print_all (l_professor)
end
end
</e>

== Issues ==

=== Keywords ===

For this description, the keywords '''read''' and '''write''' were used. This can easily be changed. For example, to be more like the interval types the '''read''' keyword can be omitted and the '''write''' keyword replaced by two dots.

=== Syntax overhead ===

The read-write types can produce a considerable amount of syntax overhead. Thanks to the default behaviour and the shorthand for read-only types, the average situation requires only one keyword '''read''' from time to time. In general no annotation should be necessary at all.

== Conclusion ==

The read-write types are a powerful solution. It can handle non-generic and generic types in the same way but still allows to address features with formal arguments and other covariantly redefined features separately. Since both interval types and usage-site variance can be expressed through it, it has all the advantages of these and with sensible default values does not produce much syntax overhead in the general case.

Interval types and usage-site variance

2007-07-06T03:00:55Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This is a proposition to combine two mechanisms to prevent catcalls, the [[interval types]] for non-generics and the [[usage-site variance]] for generics.

The reason for this is that up to now all approaches failed to deliver an easy and concise solution to solve the problem of catcalls in general.

Interval types work well for non-generic types and the overhead for the type declaration is minimal with a sensitive default behaviour, but for generics it does not really work.

Usage-site variance is a promising solution for generics with just the small addition of a flag for the kind of variance needed on a generic derivation. And again, the default behaviour will allow most uses of a generic type as the programmer expects it to work.

== Syntax ==

Types can be specified as an interval:

* <e>LOWER..UPPER</e>

Generic parameters can be marked to select the variance:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

Each interval type describes the set of types which belong to the interval. A type belongs to the interval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it. All feature calls will be subject to whole-system validity and by restricting the dynamic type set to the types in the interval this check can be influenced.

For generics the applicable features depend on the variance mark used:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generic as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

The two mechanisms can also be combined. A generic parameter can be an interval type and can also have a variance modifier. The normal generic substitution applies to every formal generic by replacing the generic with the interval type. The variance marks are only used for conformance checks and don't affect the generic substitution.

=== Conformance rules ===

A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>. The conformance rules for generics differ depending on the variance mark:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

=== Default behaviour ===

The default for a type declaration is that the interval contains the type up to <e>NONE</e> (note that it is assumed that <e>NONE</e> also conforms to expanded types. See the [[Interval_types#Conclusion|conclusion of interval types]] for more information.):

<e>
a: ANY -- means ANY..NONE
</e>

This allows that in the default case all descendants of a type can be assigned.

The default for generic arguments is novariance. This allows that all features can be called on a generic without restrictions.

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- means ANY..NONE
list: LIST [ANY] -- means LIST [ANY..NONE] .. NONE
l_list: LINKED_LIST [ANY] -- means LINKED_LIST [ANY..NONE] .. NONE
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

What won't work as before is conformance of generics. The generic parameter of the target type will have to be marked as covariant, thus the features which have formal arguments cannot be called anymore.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Combining the mechanisms ===

<e>
local
dog: DOG -- means DOG..NONE
cat: CAT -- means CAT..NONE
animal: ANIMAL -- means ANIMAL..NONE
animal_list: LIST [ANIMAL] -- means LIST [ANIMAL..NONE] .. NONE
animal_dog_list: LIST [ANIMAL..DOG]
read_any_list: LIST [+ANY] -- means LIST [+ ANY..NONE] .. NONE
do
-- valid
dog.eat (food)
cat.eat (cat_food)
animal.eat (cat_food)

-- invalid
animal.eat (food) -- could be a CAT

-- valid
animal_list.put (dog)
animal_list.put (cat)
animal_list.eat (cat_food)
animal_dog_list.eat (food)
read_any_list := animal_list

-- invalid
read_any_list.put ("abc") -- contravariant list
animal_list.item.eat (food) -- could be a CAT

-- types
animal_list.item = {ANIMAL..NONE}
animal_dog_list.item = {ANIMAL..DOG}
read_any_list.item = {ANY..NONE}

animal_dog_list.put ({ANIMAL..DOG})
animal_list.put ({ANIMAL..NONE})
end
</e>

=== Cats and dogs ===

See the [[Interval_types#Cats_and_dogs|interval types]] example.

=== A simple generic algorithm ===

See the [[Usage-site_variance#A_simple_generic_algorithm|usage-site variance]] example.

Interval types

2007-07-06T03:00:09Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

With interval types, the programmer can restrict the conforming types for an entity. This way, the type set which needs to be checked for system validity of a feature call is restricted to a smaller set of types. In addition, certain rules for generic types will prohibit the unsafe use of generics.

== Syntax ==

At every location where a normal type is expected, an interval type can be specified by adding an upper bound for each type:

<e>
LOWER..UPPER
</e>

This specifies an interval of all types between the types <e>LOWER</e> and <e>UPPER</e>.

== Semantics ==

The intention of an interval type is to specify that an entity can only be attached to a type which lies inside the interval. Thus a type declared as <e>ANY..STRING</e> can be attached to an object of dynamic type <e>ANY</e> or dynamic type <e>STRING</e>. It cannot be attached to an object of a type which lies outside this interval, for example <e>INTEGER</e> or <e>PATH_NAME</e>.

Each interval type describes the set of types which belong to the interval. A type belongs to the interval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it.

<e>
a: A .. C <=> {A, B, C}
b: A .. B <=> {A, B}
c: A .. NONE <=> {A, B, C, ...}
</e>

=== Conformance rules ===

An interval type ''b'' conforms to an interval type ''a'' if it is a sub-interval of ''a''. So if ''a'' fully encloses the interval ''b'', ''b'' conforms to ''a''.

The conformance rules can also be explained by differently:

* An interval type ''b'' conforms to an interval type ''a'' if the set of types described by the interval of ''b'' is a subset of the set described by the interval of ''a''.

:<e>
a := b -- Is valid as {A, B} is a subset of {A, B, C}
</e>

* A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>.

Generic conformance is the same as it is now: A generic type ''b'' conforms to a generic type ''a'' if the base class of ''b'' conforms to ''a'' and all generic parameters conform as well.

=== Generic features ===

For features with formal arguments, another rule exists: A call on a feature which contains a formal argument is only valid if the generic substitution is monomorphic.

This means that a call on a feature <e>f (g: G)</e> of a class <e>X [G]</e> is only valid if <e>G</e> is monomorphic. Thus the type has to be instantiated with <e>X [Y..Y]</e>. So a call to <e>f</e> on a type <e>X [Y..NONE]</e> is not allowed.

=== Default behaviour ===

As a shorthand for interval definition, we define the following default behaviour which is different for ordinary types and for actual generic type parameters. Ordinary types are per default polymorphic and actual formal parameters monomorphic:

<e>
x: T <=> T .. NONE
y: A [T] <=> A [T .. T] .. NONE
</e>

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Cats and dogs ===

A feature call on a target ''t'' is only valid if it is valid for all polymorphic types which can possibly be assigned to ''t''. With interval types the set of conforming types can be restricted in order to be able to perform calls to features which are covariantly redefined in descendants by excluding such descendants from the dynamic type set.

<e>
a_none: ANIMAL <=> ANIMAL .. NONE
c_none: CAT <=> ANIMAL .. NONE
d_none: DOG <=> ANIMAL .. NONE
a_a: ANIMAL .. ANIMAL
c_c: CAT .. CAT
d_d: DOG .. DOG
a_c: ANIMAL .. CAT
a_d: ANIMAL .. DOG
</e>

Valid assignments:

<e>
a_none := c_none
a_none := d_none
a_none := a_a
a_none := c_c
a_none := d_d
c_none := c_c
d_none := d_d

a_c := a_a
a_c := c_c
a_d := a_a
a_d := d_d
</e>

Invalid assignments:

<e>
-- Invalid: a_a := a_none
-- Invalid: c_c := c_none
-- Invalid: d_d := d_none
-- Invalid: a_c := c_none
-- Invalid: a_d := d_none
</e>

Valid calls:

<e>
a_none.eat (cat_food)
a_a.eat (food)
a_d.eat (food)
</e>

Invalid calls:

<e>
a_none.eat (food)
</e>

=== A simple generic algorithm ===

It is easy to declare an algorithm which needs only read-access on a list:

<e>
class PERSON_PRINTER
feature
print_all (a_list: LIST [PERSON..NONE])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a covariant list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT] <=> LIST [STUDENT..STUDENT]
l_professors: LIST [PROFESSOR] <=> LIST [PROFESSOR..PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT..STUDENT] conforms to LIST [PERSON..NONE]
l_person_printer.print_all (l_students)
-- LIST [PROFESSOR..PROFESSOR] conforms to LIST [PERSON..NONE]
l_person_printer.print_all (l_professor)
end
end
</e>

== Issues ==

=== Generic features ===

The rule about calling features with formal parameters is too restrictive. Let's look at the following code:

<e>
deferred class COMPONENT
end

class COMPOSITE
inherit COMPONENT
feature
components: LIST [COMPONENT]
end
</e>

What should the type of feature <e>components</e> be? In order to be able to call <e>extend</e> on the list, it has to be monomorphic, thus <e>LIST [COMPONENT..COMPONENT]</e>. But since the argument type is now <e>COMPONENT..COMPONENT</e> we actually cannot add anything to the list as no descendant of <e>COMPONENT</e> is in the interval. Actually, since <e>COMPONENT</e> is deferred nothing can be added to the list at all.

But if we define the list as <e>LIST [COMPONENT..NONE]</e> - thus allowing descendants of <e>COMPONENT</e> in the list - then the rule about features with formal arguments disallows any calls to feature <e>extend</e> as the argument is not monomorphic anymore.

=== Expanded and Void ===

Look at the following code snippet:

<e>
local
any_none: ANY..NONE
any_string: ANY..STRING
do
-- invalid as NONE does not conform to INTEGER
any_none := 5
-- invalid as NONE is not in the interval ANY..STRING
any_string := Void
end
</e>

It illustrates two problems in conjunction with <e>NONE</e>:

* The first is that <e>NONE</e> does not conform to expanded types. This makes it impossible to declare a type interval which includes all types in the system, reference or expanded. This prevents the programmer to write code which works with reference types and expanded types, say a generic print algorithm.
* The second one is that <e>Void</e> is of type <e>NONE</e>. This raises the question how <e>Void</e> should be assigned to an interval type of references, or how such a type is initialized in the first place.

== Conclusion ==

The rule about features with formal parameters must be changed to make this solution usable as otherwise the use of generics is restricted too much.

The problem with <e>Void</e> and <e>NONE</e> can easily be solved by declaring that <e>NONE</e> inherits from all types regardless of reference or expanded status. To solve the problem of assigning <e>Void</e> to an interval type it can be defined that <e>Void</e> is of any (detached) reference type. You could for example say that <e>Void</e> always has the type of the lower bound of the target interval if this type is a (detached) reference type. That way it can be assigned to any interval of a reference type, even a monomorphic one, and it is still disallowed to assign it to expanded types.

Interval types and usage-site variance

2007-07-06T02:58:18Z

Juliant: /* Combining the mechanisms */

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This is a proposition to combine two mechanisms to prevent catcalls, the [[interval types]] for non-generics and the [[usage-site variance]] for generics.

The reason for this is that up to now all approaches failed to deliver an easy and concise solution to solve the problem of catcalls in general.

Interval types work well for non-generic types and the overhead for the type declaration is minimal with a sensitive default behaviour, but for generics it does not really work.

Usage-site variance is a promising solution for generics with just the small addition of a flag for the kind of variance needed on a generic derivation. And again, the default behaviour will allow most uses of a generic type as the programmer expects it to work.

== Syntax ==

Types can be specified as an interval:

* <e>LOWER..UPPER</e>

Generic parameters can be marked to select the variance:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it. All feature calls will be subject to whole-system validity and by restricting the dynamic type set to the types in the interval this check can be influenced.

For generics the applicable features depend on the variance mark used:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

The two mechanisms can also be combined. A generic parameter can be an interval type and can also have a variance modifier. The normal generic substituion applies to every formal generic by replacing the generic with the interval type. The variance marks are only used for conformance checks and don't affect the generic substitution.

=== Conformance rules ===

A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>. The conformance rules for generics differ depending on the variance mark:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

=== Default behaviour ===

The default for a type declaration is that the interval contains the type up to <e>NONE</e> (note that it is assumed that <e>NONE</e> also conforms to expanded types. See the [[Interval_types#Conclusion|conclusion of interval types]] for more information.):

<e>
a: ANY -- means ANY..NONE
</e>

This allows that in the default case all descendants of a type can be assigned.

The default for generic arguments is novariance. This allows that all features can be called on a generic without restrictions.

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- means ANY..NONE
list: LIST [ANY] -- means LIST [ANY..NONE] .. NONE
l_list: LINKED_LIST [ANY] -- means LINKED_LIST [ANY..NONE] .. NONE
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

What won't work as before is conformance of generics. The generic parameter of the target type will have to be marked as covariant, thus the features which have formal arguments cannot be called anymore.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Combining the mechanisms ===

<e>
local
dog: DOG -- means DOG..NONE
cat: CAT -- means CAT..NONE
animal: ANIMAL -- means ANIMAL..NONE
animal_list: LIST [ANIMAL] -- means LIST [ANIMAL..NONE] .. NONE
animal_dog_list: LIST [ANIMAL..DOG]
read_any_list: LIST [+ANY] -- means LIST [+ ANY..NONE] .. NONE
do
-- valid
dog.eat (food)
cat.eat (cat_food)
animal.eat (cat_food)

-- invalid
animal.eat (food) -- could be a CAT

-- valid
animal_list.put (dog)
animal_list.put (cat)
animal_list.eat (cat_food)
animal_dog_list.eat (food)
read_any_list := animal_list

-- invalid
read_any_list.put ("abc") -- contravariant list
animal_list.item.eat (food) -- could be a CAT

-- types
animal_list.item = {ANIMAL..NONE}
animal_dog_list.item = {ANIMAL..DOG}
read_any_list.item = {ANY..NONE}

animal_dog_list.put ({ANIMAL..DOG})
animal_list.put ({ANIMAL..NONE})
end
</e>

=== Cats and dogs ===

See the [[Interval_types#Cats_and_dogs|interval types]] example.

=== A simple generic algorithm ===

See the [[Usage-site_variance#A_simple_generic_algorithm|usage-site variance]] example.

Comparison of catcall solutions

2007-07-06T02:55:42Z

Juliant: /* Overview of general solutions */

[[Category:ECMA]]
[[Category:Catcall]]
== 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 [[Single level call rule implementation|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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> where the feature <e>put</e> changes signature from <e>ANY</e> to <e>INTEGER</e>.
* 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 <e>like Current</e>. 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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> only the features based on the formal change their signature while they don't change from <e>LIST [ANY]</e> to <e>LINKED_LIST [ANY]</e> 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 <e>STRING</e> or one for <e>ANY</e> is suitable.
* If you want to pass an argument of type <e>STRING</e> to an agent, the agent either has to accept a <e>STRING</e> or <e>ANY</e> 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 [http://dev.eiffel.com/Covariance_through_renaming 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: [http://dev.eiffel.com/Forget_/_Keep_Mechanism 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueFLEX_CATCALL IssueFLEX_CATCALL on ECMA wiki] 
Reference: Discussion in ECMA mailinglist named ''Catcall removal: another proposal'', [[Restrict types mail|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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueDOG 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: [http://pag.csail.mit.edu/reading-group/variance-ECOOP02.pdf 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: [http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx Article about generics in CLR]

Note: There is also a [http://fams.de/text/type-safe-eiffel.html 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: [http://www.jot.fm/issues/issue_2004_12/article5 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: [http://se.ethz.ch/~meyer/publications/lncs/attached.pdf Article about ''attached types'' by Bertrand Meyer] 
Reference: [http://www.ecma-international.org/publications/standards/Ecma-367.htm 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueCAT IssueCAT on ECMA wiki] 
Reference: [http://www.inf.ethz.ch/~meyer/ongoing/covariance/recast.pdf 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 [[Comparison of catcall solutions#Table_explained|explanation at the end of the table]] for more information

=== General solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Novariance]]
! [[Forget / keep]]
! Dynamic typeset algorithm

|-

! Syntax overhead
| {{Green|No}}
| {{Red|Big}}: forget/keep clauses per type
| {{Green|No}}

|-

! Covariance on non-generic types
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| {{Red|Very limited}}: Only invariant conformance
| {{Orange|Limited}}: Conformance restricted (''keep all'' as default) {{Orange|Limited}}: Use restricted (''forget all'' as default)
| {{Green|As it is now}}

|-

! Agents
| {{Orange|Limited}} {{Green|Safe}}
| {{Orange|Limited}} {{Green|Safe}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on forget/keep clauses
| {{Red|Big}}: Iterative abstract system execution

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Need to know cat features for object tests
| {{Green|Small}}: As it is now

|-

! Whole-system analysis
| {{Green|No}}
| {{Red|Yes}}: use of ''forget all'' depends on system
| {{Red|Yes}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Red|No}}
| {{Red|No}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Orange|Limited}}
| {{Green|Full}}

|-

! Support of IDE (Source changes)
| {{Green|Not needed}}
| {{Orange|Possible}}: Can propose forget/keep clauses
| {{Green|Not needed}}

|}

=== Solutions for non-generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Restrict types]]
! [[DOG proposal]]

|-

! Syntax overhead
| {{Red|Big}}: Restrict clause per type declaration
| {{Orange|Medium}}: ''cat'' on features and on type declarations

|-

! Covariance on non-generic types
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| Not addressed
| Not addressed

|-

! Agents
| Not addressed
| Not addressed

|-

! Comparator
| Not addressed
| Not addressed

|-

! Complexity of compiler check
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on restrict clauses
| {{Green|Small}}: Check of ''cat'' on conformance

|-

! Complexity of runtime
| not yet considered
| {{Green|Small}}

|-

! Whole-system analysis
| {{Orange|Partial}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Orange|Limited}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Red|Very limited}}

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose restrict clauses
| {{Orange|Possible}}: Can propose ''cat'' marks

|}

=== Solutions for generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Usage-site variance]]
! [[Definition-site variance]]
! Wildcard generics

|-

! Syntax overhead
| {{Orange|Medium}}: Variance marks per generic type
| {{Green|Small}}: Variance marks per generic class definition
| {{Orange|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
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}

|-

! Agents
| {{Green|Fully supported}} {{Green|Safe}}
| {{Green|Fully supported}}: If tuples can be specified covariantly {{Green|Safe}}
| {{Green|Fully supported}} {{Green|Safe}}

|-

! Comparator
| {{Green|Supported}}
| {{Green|Supported}}
| {{Green|Supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check

|-

! Complexity of runtime
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Orange|Limited}}: Use of generics changed due to conformance
| {{Red|Very limited}}: Libraries need redesign
| {{Orange|Limited}}: Use of generics changed due to conformance

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose variance marks
| {{Red|Not possible}}: Libraries need redesign
| {{Orange|Possible}}: Can propose variance marks/wildcards

|}

=== Dynamic solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Detachable types]]
! Recast
! Exceptions

|-

! Syntax overhead
| {{Green|Small}}: Detachment marks
| {{Red|Big}}: Recast clauses, recast features
| {{Orange|Medium}}: If rescue clause mandatory {{Green|No}}: If rescue clause not needed

|-

! Covariance on non-generic types
| {{Red|Very limited}}: Only detached arguments, no expanded arguments
| {{Green|Allowed}}
| {{Green|Allowed}}
|-

! Export status restrictions
| Not addressed
| Not addressed
| Not addressed

|-

! Use of generics
| {{Red|Very limited}}: Only detachable formal arguments
| {{Red|Very limited}}: Recast clause for all features with formal generics
| {{Green|As it is now}}

|-

! Agents
| {{Red|As it is now}}
| {{Red|As it is now}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Check for catcalls and do recast
| {{Orange|Medium}}: Check for catcalls and raise exception

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}: All covariant and generic features become detached
| {{Red|Very limited}}: All covariant and generic features need recast clause
| {{Orange|Limited}}: If rescue clause is mandatory {{Green|Full}}: If rescue clause not needed

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose detachment marks
| {{Red|Not possible}}: Programmer must provide recast clause
| {{Red|Not possible}}: If rescue clause mandatory {{Green|Not needed}}: If rescue clause not needed

|}

=== Table explained ===

; Syntax overhead : {{Green|Small}} if a keyword/mark is needed per class/feature declaration; {{Orange|Medium}} if a keyword/mark is neede per type declaration; {{Red|Big}} if a clause is needed per type declaration.
; Use of generics : {{Green|As it is now}} if assignments are possible if generic parameters conform; {{Orange|Limited}} is some restrictions in the use or the conformance between generics exist; {{Red|Very limited}} a lot of restrictions in the use or the conformance between generics exist.
; Agents : {{Green|Fully supported}} if all safe assignments are allowed; {{Orange|Limited}} if not all safe assignments are allowed; {{Red|As it is now}} if unsafe assignments are still possible.
; Comparator : {{Green|Supported}} if for a comparator all safe assignments are permitted (i.e. contravariant assignments); {{Red|Not supported}} if only exact type or even (unsafe) subtypes can be assigned.
; Support of IDE (Source changes) : {{Green|Not needed}} if everything still works the same; {{Orange|Possible}} if the compiler can suggest clauses or marks; {{Red|Not possible}} if the programmer has to specify additional features/instructions.

== Personal opinions ==

[[Personal view about catcall solution]]

Comparison of catcall solutions

2007-07-06T02:55:29Z

Juliant: /* Overview of general solutions */

[[Category:ECMA]]
[[Category:Catcall]]
== 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 [[Single level call rule implementation|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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> where the feature <e>put</e> changes signature from <e>ANY</e> to <e>INTEGER</e>.
* 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 <e>like Current</e>. 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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> only the features based on the formal change their signature while they don't change from <e>LIST [ANY]</e> to <e>LINKED_LIST [ANY]</e> 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 <e>STRING</e> or one for <e>ANY</e> is suitable.
* If you want to pass an argument of type <e>STRING</e> to an agent, the agent either has to accept a <e>STRING</e> or <e>ANY</e> 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 [http://dev.eiffel.com/Covariance_through_renaming 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: [http://dev.eiffel.com/Forget_/_Keep_Mechanism 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueFLEX_CATCALL IssueFLEX_CATCALL on ECMA wiki] 
Reference: Discussion in ECMA mailinglist named ''Catcall removal: another proposal'', [[Restrict types mail|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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueDOG 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: [http://pag.csail.mit.edu/reading-group/variance-ECOOP02.pdf 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: [http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx Article about generics in CLR]

Note: There is also a [http://fams.de/text/type-safe-eiffel.html 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: [http://www.jot.fm/issues/issue_2004_12/article5 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: [http://se.ethz.ch/~meyer/publications/lncs/attached.pdf Article about ''attached types'' by Bertrand Meyer] 
Reference: [http://www.ecma-international.org/publications/standards/Ecma-367.htm 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueCAT IssueCAT on ECMA wiki] 
Reference: [http://www.inf.ethz.ch/~meyer/ongoing/covariance/recast.pdf 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 [[Comparison of catcall solutions#Table_explained|explanation at the end of the table]] for more information

=== General solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Novariance]]
! [[Forget / keep]]
! Dynamic typeset algorithm

|-

! Syntax overhead
| {{Green|No}}
| {{Red|Big}}: forget/keep clauses per type
| {{Green|No}}

|-

! Covariance on non-generic types
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| {{Red|Very limited}}: Only invariant conformance
| {{Orange|Limited}}: Conformance restricted (''keep all'' as default) {{Orange|Limited}}: Use restricted (''forget all'' as default)
| {{Green|As it is now}}

|-

! Agents
| {{Orange|Limited}} {{Green|Safe}}
| {{Orange|Limited}} {{Green|Safe}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on forget/keep clauses
| {{Red|Big}}: Iterative abstract system execution

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Need to know cat features for object tests
| {{Green|Small}}: As it is now

|-

! Whole-system analysis
| {{Green|No}}
| {{Red|Yes}}: use of ''forget all'' depends on system
| {{Red|Yes}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Red|No}}
| {{Red|No}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Orange|Limited}}
| {{Green|Full}}

|-

! Support of IDE (Source changes)
| {{Green|Not needed}}
| {{Orange|Possible}}: Can propose forget/keep clauses
| {{Green|Not needed}}

|}

=== Solutions for non-generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Restrict types]]
! [[DOG proposal]]

|-

! Syntax overhead
| {{Red|Big}}: Restrict clause per type declaration
| {{Orange|Medium}}: ''cat'' on features and on type declarations

|-

! Covariance on non-generic types
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| Not addressed
| Not addressed

|-

! Agents
| Not addressed
| Not addressed

|-

! Comparator
| Not addressed
| Not addressed

|-

! Complexity of compiler check
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on restrict clauses
| {{Green|Small}}: Check of ''cat'' on conformance

|-

! Complexity of runtime
| not yet considered
| {{Green|Small}}

|-

! Whole-system analysis
| {{Orange|Partial}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Orange|Limited}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Red|Very limited}}

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose restrict clauses
| {{Orange|Possible}}: Can propose ''cat'' marks

|}

=== Solutions for generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Usage-site variance]]
! [[Definition-site variance]]
! Wildcard generics

|-

! Syntax overhead
| {{Orange|Medium}}: Variance marks per generic type
| {{Green|Small}}: Variance marks per generic class definition
| {{Orange|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
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}

|-

! Agents
| {{Green|Fully supported}} {{Green|Safe}}
| {{Green|Fully supported}}: If tuples can be specified covariantly {{Green|Safe}}
| {{Green|Fully supported}} {{Green|Safe}}

|-

! Comparator
| {{Green|Supported}}
| {{Green|Supported}}
| {{Green|Supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check

|-

! Complexity of runtime
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Orange|Limited}}: Use of generics changed due to conformance
| {{Red|Very limited}}: Libraries need redesign
| {{Orange|Limited}}: Use of generics changed due to conformance

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose variance marks
| {{Red|Not possible}}: Libraries need redesign
| {{Orange|Possible}}: Can propose variance marks/wildcards

|}

=== Dynamic solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Detachable types]]
! Recast
! Exceptions

|-

! Syntax overhead
| {{Green|Small}}: Detachment marks
| {{Red|Big}}: Recast clauses, recast features
| {{Orange|Medium}}: If rescue clause mandatory {{Green|No}}: If rescue clause not needed

|-

! Covariance on non-generic types
| {{Red|Very limited}}: Only detached arguments, no expanded arguments
| {{Green|Allowed}}
| {{Green|Allowed}}
|-

! Export status restrictions
| Not addressed
| Not addressed
| Not addressed

|-

! Use of generics
| {{Red|Very limited}}: Only detachable formal arguments
| {{Red|Very limited}}: Recast clause for all features with formal generics
| {{Green|As it is now}}

|-

! Agents
| {{Red|As it is now}}
| {{Red|As it is now}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Check for catcalls and do recast
| {{Orange|Medium}}: Check for catcalls and raise exception

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}: All covariant and generic features become detached
| {{Red|Very limited}}: All covariant and generic features need recast clause
| {{Orange|Limited}}: If rescue clause is mandatory {{Green|Full}}: If rescue clause not needed

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose detachment marks
| {{Red|Not possible}}: Programmer must provide recast clause
| {{Red|Not possible}}: If rescue clause mandatory {{Green|Not needed}}: If rescue clause not needed

|}

=== Table explained ===

; Syntax overhead : {{Green|Small}} if a keyword/mark is needed per class/feature declaration; {{Orange|Medium}} if a keyword/mark is neede per type declaration; {{Red|Big}} if a clause is needed per type declaration.
; Use of generics : {{Green|As it is now}} if assignments are possible if generic parameters conform; {{Orange|Limited}} is some restrictions in the use or the conformance between generics exist; {{Red|Very limited}} a lot of restrictions in the use or the conformance between generics exist.
; Agents : {{Green|Fully supported}} if all safe assignments are allowed; {{Orange|Limited}} if not all safe assignments are allowed; {{Red|As it is now}} if unsafe assignments are still possible.
; Comparator : {{Green|Supported}} if for a comparator all safe assignments are permitted (i.e. contravariant assignments); {{Red|Not supported}} if only exact type or even (unsafe) subtypes can be assigned.
; Support of IDE (Source changes) : {{Green|Not needed}} if everything still works the same; {{Orange|Possible}} if the compiler can suggest clauses or marks; {{Red|Not possible}} if the programmer has to specify additional features/instructions.

== Personal opinions ==

[[Personal view about catcall solution]]

Interval types and usage-site variance

2007-07-06T02:52:19Z

Juliant: /* Default behaviour */

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This is a proposition to combine two mechanisms to prevent catcalls, the [[interval types]] for non-generics and the [[usage-site variance]] for generics.

The reason for this is that up to now all approaches failed to deliver an easy and concise solution to solve the problem of catcalls in general.

Interval types work well for non-generic types and the overhead for the type declaration is minimal with a sensitive default behaviour, but for generics it does not really work.

Usage-site variance is a promising solution for generics with just the small addition of a flag for the kind of variance needed on a generic derivation. And again, the default behaviour will allow most uses of a generic type as the programmer expects it to work.

== Syntax ==

Types can be specified as an interval:

* <e>LOWER..UPPER</e>

Generic parameters can be marked to select the variance:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it. All feature calls will be subject to whole-system validity and by restricting the dynamic type set to the types in the interval this check can be influenced.

For generics the applicable features depend on the variance mark used:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

The two mechanisms can also be combined. A generic parameter can be an interval type and can also have a variance modifier. The normal generic substituion applies to every formal generic by replacing the generic with the interval type. The variance marks are only used for conformance checks and don't affect the generic substitution.

=== Conformance rules ===

A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>. The conformance rules for generics differ depending on the variance mark:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

=== Default behaviour ===

The default for a type declaration is that the interval contains the type up to <e>NONE</e> (note that it is assumed that <e>NONE</e> also conforms to expanded types. See the [[Interval_types#Conclusion|conclusion of interval types]] for more information.):

<e>
a: ANY -- means ANY..NONE
</e>

This allows that in the default case all descendants of a type can be assigned.

The default for generic arguments is novariance. This allows that all features can be called on a generic without restrictions.

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- means ANY..NONE
list: LIST [ANY] -- means LIST [ANY..NONE] .. NONE
l_list: LINKED_LIST [ANY] -- means LINKED_LIST [ANY..NONE] .. NONE
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

What won't work as before is conformance of generics. The generic parameter of the target type will have to be marked as covariant, thus the features which have formal arguments cannot be called anymore.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Combining the mechanisms ===

<e>
local
dog: DOG -- means DOG..NONE
cat: CAT -- means CAT..NONE
animal: ANIMAL -- means ANIMAL..NONE
animal_list: LIST [ANIMAL] -- means LIST [ANIMAL..NONE] .. NONE
animal_dog_list: LIST [ANIMAL..DOG]
read_any_list: LIST [+ANY] -- means LIST [+ ANY..NONE] .. NONE
do
-- valid
dog.eat (food)
cat.eat (cat_food)
animal.eat (cat_food)

-- invalid
animal.eat (food) -- could be a CAT

-- valid
animal_list.put (dog)
animal_list.put (cat)
animal_list.eat (cat_food)
animal_dog_list.eat (food)
read_any_list := animal_list

-- invalid
read_any_list.put ("abc")
animal_list.eat (food) -- could be a CAT

-- types
animal_list.item = {ANIMAL..NONE}
animal_dog_list.item = {ANIMAL..DOG}
read_any_list.item = {ANY..NONE}

animal_dog_list.put ({ANIMAL..DOG})
animal_list.put ({ANIMAL..NONE})
end
</e>

=== Cats and dogs ===

See the [[Interval_types#Cats_and_dogs|interval types]] example.

=== A simple generic algorithm ===

See the [[Usage-site_variance#A_simple_generic_algorithm|usage-site variance]] example.

Interval types

2007-07-06T02:45:12Z

Juliant: /* Conclusion */

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

With interval types, the programmer can restrict the conforming types for an entity. This way, the type set which needs to be checked for system validity of a feature call is restricted to a smaller set of types. In addition, certain rules for generic types will prohibit the unsafe use of generics.

== Syntax ==

At every location where a normal type is expected, an interval type can be specified by adding an upper bound for each type:

<e>
LOWER..UPPER
</e>

This specifies an interval of all types between the types <e>LOWER</e> and <e>UPPER</e>.

== Semantics ==

The intention of an interval type is to specify that an entity can only be attached to a type which lies inside the interval. Thus a type declared as <e>ANY..STRING</e> can be attached to an object of dynamic type <e>ANY</e> or dynamic type <e>STRING</e>. It cannot be attached to an object of a type which lies outside this interval, for example <e>INTEGER</e> or <e>PATH_NAME</e>.

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it.

<e>
a: A .. C <=> {A, B, C}
b: A .. B <=> {A, B}
c: A .. NONE <=> {A, B, C, ...}
</e>

=== Conformance rules ===

An interval type ''b'' conforms to an interval type ''a'' if it is a sub-interval of ''a''. So if ''a'' fully encloses the interval ''b'', ''b'' conforms to ''a''.

The conformance rules can also be explained by differently:

* An interval type ''b'' conforms to an interval type ''a'' if the set of types described by the interval of ''b'' is a subset of the set described by the interval of ''a''.

:<e>
a := b -- Is valid as {A, B} is a subset of {A, B, C}
</e>

* A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>.

Generic conformance is the same as it is now: A generic type ''b'' conforms to a generic type ''a'' if the base class of ''b'' conforms to ''a'' and all generic parameters conform as well.

=== Generic features ===

For features with formal arguments, another rule exists: A call on a feature wich contains a formal argument is only valid if the generic substitution is monomorphic.

This means that a call on a feature <e>f (g: G)</e> of a class <e>X [G]</e> is only valid if <e>G</e> is monomorphic. Thus the type has to be instantitated with <e>X [Y..Y]</e>. So a call to <e>f</e> on a type <e>X [Y..NONE]</e> is not allowed.

=== Default behaviour ===

As a shorthand for interval definition, we define the following default behaviour which is different for ordinary types and for actual generic type parameters. Ordinary types are per default polymorphic and actual formal parameters monomorphic:

<e>
x: T <=> T .. NONE
y: A [T] <=> A [T .. T] .. NONE
</e>

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Cats and dogs ===

A feature call on a target ''t'' is only valid if it is valid for all polymorphic types which can possibly be assigned to ''t''. With interval types the set of conforming types can be restriced in order to be able to perform calls to features which are covariantly redefined in descendands by excluding such descendants from the dynamic type set.

<e>
a_none: ANIMAL <=> ANIMAL .. NONE
c_none: CAT <=> ANIMAL .. NONE
d_none: DOG <=> ANIMAL .. NONE
a_a: ANIMAL .. ANIMAL
c_c: CAT .. CAT
d_d: DOG .. DOG
a_c: ANIMAL .. CAT
a_d: ANIMAL .. DOG
</e>

Valid assignments:

<e>
a_none := c_none
a_none := d_none
a_none := a_a
a_none := c_c
a_none := d_d
c_none := c_c
d_none := d_d

a_c := a_a
a_c := c_c
a_d := a_a
a_d := d_d
</e>

Invalid assignments:

<e>
-- Invalid: a_a := a_none
-- Invalid: c_c := c_none
-- Invalid: d_d := d_none
-- Invalid: a_c := c_none
-- Invalid: a_d := d_none
</e>

Valid calls:

<e>
a_none.eat (cat_food)
a_a.eat (food)
a_d.eat (food)
</e>

Invalid calls:

<e>
a_none.eat (food)
</e>

=== A simple generic algorithm ===

It is easy to declare an algorithm which needs only read-access on a list:

<e>
class PERSON_PRINTER
feature
print_all (a_list: LIST [PERSON..NONE])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a covariant list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT] <=> LIST [STUDENT..STUDENT]
l_professors: LIST [PROFESSOR] <=> LIST [PROFESSOR..PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT..STUDENT] conforms to LIST [PERSON..NONE]
l_person_printer.print_all (l_students)
-- LIST [PROFESSOR..PROFESSOR] conforms to LIST [PERSON..NONE]
l_person_printer.print_all (l_professor)
end
end
</e>

== Issues ==

=== Generic features ===

The rule about calling features with formal parameters is too restrictive. Let's look at the following code:

<e>
deferred class COMPONENT
end

class COMPOSITE
inherit COMPONENT
feature
components: LIST [COMPONENT]
end
</e>

What should the type of feature <e>components</e> be? In order to be able to call <e>extend</e> on the list, it has to be monomorphic, thus <e>LIST [COMPONENT..COMPONENT]</e>. But since the argument type is now <e>COMPONENT..COMPONENT</e> we actually cannot add anything to the list as no descendant of <e>COMPONENT</e> is in the interval. Actually, since <e>COMPONENT</e> is deferred nothing can be added to the list at all.

But if we define the list as <e>LIST [COMPONENT..NONE]</e> - thus allowing descendants of <e>COMPONENT</e> in the list - then the rule about features with formal arguments disallows any calls to feature <e>extend</e> as the argument is not monomorphic anymore.

=== Expanded and Void ===

Look at the following code snippet:

<e>
local
any_none: ANY..NONE
any_string: ANY..STRING
do
-- invalid as NONE does not conform to INTEGER
any_none := 5
-- invalid as NONE is not in the interval ANY..STRING
any_string := Void
end
</e>

It illustrates two problems in conjunction with <e>NONE</e>:

* The first is that <e>NONE</e> does not conform to expanded types. This makes it impossible to declare a type interval which includes all types in the system, reference or expanded. This prevents the programmer to write code which works with reference types and expanded types, say a generic print algorithm.
* The second one is that <e>Void</e> is of type <e>NONE</e>. This raises the question how <e>Void</e> should be assigned to an interval type of references, or how such a type is initialized in the first place.

== Conclusion ==

The rule about features with formal parameters must be changed to make this solution usable as otherwise the use of generics is restricted too much.

The problem with <e>Void</e> and <e>NONE</e> can easily be solved by declaring that <e>NONE</e> inherits from all types regardless of reference or expanded status. To solve the problem of assigning <e>Void</e> to an interval type it can be defined that <e>Void</e> is of any (detached) reference type. You could for example say that <e>Void</e> always has the type of the lower bound of the target interval if this type is a (detached) reference type. That way it can be assigned to any interval of a refernce type, even a monomorphic one, and it is still disallowed to assign it to expanded types.

Interval types and usage-site variance

2007-07-06T02:41:25Z

Juliant: /* Semantics */

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This is a proposition to combine two mechanisms to prevent catcalls, the [[interval types]] for non-generics and the [[usage-site variance]] for generics.

The reason for this is that up to now all approaches failed to deliver an easy and concise solution to solve the problem of catcalls in general.

Interval types work well for non-generic types and the overhead for the type declaration is minimal with a sensitive default behaviour, but for generics it does not really work.

Usage-site variance is a promising solution for generics with just the small addition of a flag for the kind of variance needed on a generic derivation. And again, the default behaviour will allow most uses of a generic type as the programmer expects it to work.

== Syntax ==

Types can be specified as an interval:

* <e>LOWER..UPPER</e>

Generic parameters can be marked to select the variance:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it. All feature calls will be subject to whole-system validity and by restricting the dynamic type set to the types in the interval this check can be influenced.

For generics the applicable features depend on the variance mark used:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

The two mechanisms can also be combined. A generic parameter can be an interval type and can also have a variance modifier. The normal generic substituion applies to every formal generic by replacing the generic with the interval type. The variance marks are only used for conformance checks and don't affect the generic substitution.

=== Conformance rules ===

A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>. The conformance rules for generics differ depending on the variance mark:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

=== Default behaviour ===

The default for a type declaration is that the interval contains the type up to <e>NONE</e> (note that it is assumed that <e>NONE</e> also conforms to expanded types):

<e>
a: ANY -- means ANY..NONE
</e>

This allows that in the default case all descendants of a type can be assigned.

The default for generic arguments is novariance. This allows that all features can be called on a generic without restrictions.

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- means ANY..NONE
list: LIST [ANY] -- means LIST [ANY..NONE] .. NONE
l_list: LINKED_LIST [ANY] -- means LINKED_LIST [ANY..NONE] .. NONE
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

What won't work as before is conformance of generics. The generic parameter of the target type will have to be marked as covariant, thus the features which have formal arguments cannot be called anymore.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Combining the mechanisms ===

<e>
local
dog: DOG -- means DOG..NONE
cat: CAT -- means CAT..NONE
animal: ANIMAL -- means ANIMAL..NONE
animal_list: LIST [ANIMAL] -- means LIST [ANIMAL..NONE] .. NONE
animal_dog_list: LIST [ANIMAL..DOG]
read_any_list: LIST [+ANY] -- means LIST [+ ANY..NONE] .. NONE
do
-- valid
dog.eat (food)
cat.eat (cat_food)
animal.eat (cat_food)

-- invalid
animal.eat (food) -- could be a CAT

-- valid
animal_list.put (dog)
animal_list.put (cat)
animal_list.eat (cat_food)
animal_dog_list.eat (food)
read_any_list := animal_list

-- invalid
read_any_list.put ("abc")
animal_list.eat (food) -- could be a CAT

-- types
animal_list.item = {ANIMAL..NONE}
animal_dog_list.item = {ANIMAL..DOG}
read_any_list.item = {ANY..NONE}

animal_dog_list.put ({ANIMAL..DOG})
animal_list.put ({ANIMAL..NONE})
end
</e>

=== Cats and dogs ===

See the [[Interval_types#Cats_and_dogs|interval types]] example.

=== A simple generic algorithm ===

See the [[Usage-site_variance#A_simple_generic_algorithm|usage-site variance]] example.

Interval types and usage-site variance

2007-07-06T02:31:02Z

Juliant: /* Default behaviour */

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This is a proposition to combine two mechanisms to prevent catcalls, the [[interval types]] for non-generics and the [[usage-site variance]] for generics.

The reason for this is that up to now all approaches failed to deliver an easy and concise solution to solve the problem of catcalls in general.

Interval types work well for non-generic types and the overhead for the type declaration is minimal with a sensitive default behaviour, but for generics it does not really work.

Usage-site variance is a promising solution for generics with just the small addition of a flag for the kind of variance needed on a generic derivation. And again, the default behaviour will allow most uses of a generic type as the programmer expects it to work.

== Syntax ==

Types can be specified as an interval:

* <e>LOWER..UPPER</e>

Generic parameters can be marked to select the variance:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it. All feature calls will be subject to whole-system validity and by restricting the dynamic type set to the types in the interval this check can be influenced.

For generics the applicable features depend on the variance mark used:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

=== Conformance rules ===

A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>. The conformance rules for generics differ depending on the variance mark:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

=== Default behaviour ===

The default for a type declaration is that the interval contains the type up to <e>NONE</e> (note that it is assumed that <e>NONE</e> also conforms to expanded types):

<e>
a: ANY -- means ANY..NONE
</e>

This allows that in the default case all descendants of a type can be assigned.

The default for generic arguments is novariance. This allows that all features can be called on a generic without restrictions.

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- means ANY..NONE
list: LIST [ANY] -- means LIST [ANY..NONE] .. NONE
l_list: LINKED_LIST [ANY] -- means LINKED_LIST [ANY..NONE] .. NONE
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

What won't work as before is conformance of generics. The generic parameter of the target type will have to be marked as covariant, thus the features which have formal arguments cannot be called anymore.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Combining the mechanisms ===

<e>
local
dog: DOG -- means DOG..NONE
cat: CAT -- means CAT..NONE
animal: ANIMAL -- means ANIMAL..NONE
animal_list: LIST [ANIMAL] -- means LIST [ANIMAL..NONE] .. NONE
animal_dog_list: LIST [ANIMAL..DOG]
read_any_list: LIST [+ANY] -- means LIST [+ ANY..NONE] .. NONE
do
-- valid
dog.eat (food)
cat.eat (cat_food)
animal.eat (cat_food)

-- invalid
animal.eat (food) -- could be a CAT

-- valid
animal_list.put (dog)
animal_list.put (cat)
animal_list.eat (cat_food)
animal_dog_list.eat (food)
read_any_list := animal_list

-- invalid
read_any_list.put ("abc")
animal_list.eat (food) -- could be a CAT

-- types
animal_list.item = {ANIMAL..NONE}
animal_dog_list.item = {ANIMAL..DOG}
read_any_list.item = {ANY..NONE}

animal_dog_list.put ({ANIMAL..DOG})
animal_list.put ({ANIMAL..NONE})
end
</e>

=== Cats and dogs ===

See the [[Interval_types#Cats_and_dogs|interval types]] example.

=== A simple generic algorithm ===

See the [[Usage-site_variance#A_simple_generic_algorithm|usage-site variance]] example.

Interval types and usage-site variance

2007-07-06T02:29:40Z

Juliant: /* Default behaviour */

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This is a proposition to combine two mechanisms to prevent catcalls, the [[interval types]] for non-generics and the [[usage-site variance]] for generics.

The reason for this is that up to now all approaches failed to deliver an easy and concise solution to solve the problem of catcalls in general.

Interval types work well for non-generic types and the overhead for the type declaration is minimal with a sensitive default behaviour, but for generics it does not really work.

Usage-site variance is a promising solution for generics with just the small addition of a flag for the kind of variance needed on a generic derivation. And again, the default behaviour will allow most uses of a generic type as the programmer expects it to work.

== Syntax ==

Types can be specified as an interval:

* <e>LOWER..UPPER</e>

Generic parameters can be marked to select the variance:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it. All feature calls will be subject to whole-system validity and by restricting the dynamic type set to the types in the interval this check can be influenced.

For generics the applicable features depend on the variance mark used:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

=== Conformance rules ===

A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>. The conformance rules for generics differ depending on the variance mark:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

=== Default behaviour ===

The default for a type declaration is that the interval contains the type up to <e>NONE</e> (note that it is assumed that <e>NONE</e> also conforms to expanded types):

<e>
a: ANY -- means ANY..NONE
</e>

This allows that in the default case all descendants of a type can be assigned.

The default for generic arguments is novariance. This allows that all features can be called on a generic without restrictions.

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- mean ANY..NONE
list: LIST [ANY] -- mean LIST [ANY..NONE] .. NONE
l_list: LINKED_LIST [ANY] -- means LINKED_LIST [ANY..NONE] .. NONE
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

What won't work as before is conformance of generics. The generic parameter of the target type will have to be marked as covariant, thus the features which have formal arguments cannot be called anymore.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Combining the mechanisms ===

<e>
local
dog: DOG -- means DOG..NONE
cat: CAT -- means CAT..NONE
animal: ANIMAL -- means ANIMAL..NONE
animal_list: LIST [ANIMAL] -- means LIST [ANIMAL..NONE] .. NONE
animal_dog_list: LIST [ANIMAL..DOG]
read_any_list: LIST [+ANY] -- means LIST [+ ANY..NONE] .. NONE
do
-- valid
dog.eat (food)
cat.eat (cat_food)
animal.eat (cat_food)

-- invalid
animal.eat (food) -- could be a CAT

-- valid
animal_list.put (dog)
animal_list.put (cat)
animal_list.eat (cat_food)
animal_dog_list.eat (food)
read_any_list := animal_list

-- invalid
read_any_list.put ("abc")
animal_list.eat (food) -- could be a CAT

-- types
animal_list.item = {ANIMAL..NONE}
animal_dog_list.item = {ANIMAL..DOG}
read_any_list.item = {ANY..NONE}

animal_dog_list.put ({ANIMAL..DOG})
animal_list.put ({ANIMAL..NONE})
end
</e>

=== Cats and dogs ===

See the [[Interval_types#Cats_and_dogs|interval types]] example.

=== A simple generic algorithm ===

See the [[Usage-site_variance#A_simple_generic_algorithm|usage-site variance]] example.

Interval types and usage-site variance

2007-07-06T02:27:37Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This is a proposition to combine two mechanisms to prevent catcalls, the [[interval types]] for non-generics and the [[usage-site variance]] for generics.

The reason for this is that up to now all approaches failed to deliver an easy and concise solution to solve the problem of catcalls in general.

Interval types work well for non-generic types and the overhead for the type declaration is minimal with a sensitive default behaviour, but for generics it does not really work.

Usage-site variance is a promising solution for generics with just the small addition of a flag for the kind of variance needed on a generic derivation. And again, the default behaviour will allow most uses of a generic type as the programmer expects it to work.

== Syntax ==

Types can be specified as an interval:

* <e>LOWER..UPPER</e>

Generic parameters can be marked to select the variance:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it. All feature calls will be subject to whole-system validity and by restricting the dynamic type set to the types in the interval this check can be influenced.

For generics the applicable features depend on the variance mark used:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

=== Conformance rules ===

A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>. The conformance rules for generics differ depending on the variance mark:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

=== Default behaviour ===

The default for a type declaration is that the interval contains the type up to <e>NONE</e> (note that it is assumed that <e>NONE</e> also conforms to expanded types):

<e>
a: ANY -- means ANY..NONE
</e>

This allows that in the default case all descendants of a type can be assigned.

The default for generic arguments is novariance. This allows that all features can be called on a generic without restrictions.

By choosing these defaults, most code which does not rely on covariant generic conformance should work as before:

<e>
local
any: ANY -- mean ANY..NONE
list: LIST [ANY] -- mean LIST [ANY..NONE] .. NONE
l_list: LINKED_LIST [ANY] -- means LINKED_LIST [ANY..NONE] .. NONE
do
any := "abc"
any := 8
list := l_list
list.put (any)
list.put ("abc")
any := list.item.out
end
</e>

The only things which don't work as before is conformance of generics and calls on covariantly redefined features. For the former the generic parameters of the target type have to be marked as covariant (using ''+'') and the latter will be subject to whole-system validity of feature calls.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Combining the mechanisms ===

<e>
local
dog: DOG -- means DOG..NONE
cat: CAT -- means CAT..NONE
animal: ANIMAL -- means ANIMAL..NONE
animal_list: LIST [ANIMAL] -- means LIST [ANIMAL..NONE] .. NONE
animal_dog_list: LIST [ANIMAL..DOG]
read_any_list: LIST [+ANY] -- means LIST [+ ANY..NONE] .. NONE
do
-- valid
dog.eat (food)
cat.eat (cat_food)
animal.eat (cat_food)

-- invalid
animal.eat (food) -- could be a CAT

-- valid
animal_list.put (dog)
animal_list.put (cat)
animal_list.eat (cat_food)
animal_dog_list.eat (food)
read_any_list := animal_list

-- invalid
read_any_list.put ("abc")
animal_list.eat (food) -- could be a CAT

-- types
animal_list.item = {ANIMAL..NONE}
animal_dog_list.item = {ANIMAL..DOG}
read_any_list.item = {ANY..NONE}

animal_dog_list.put ({ANIMAL..DOG})
animal_list.put ({ANIMAL..NONE})
end
</e>

=== Cats and dogs ===

See the [[Interval_types#Cats_and_dogs|interval types]] example.

=== A simple generic algorithm ===

See the [[Usage-site_variance#A_simple_generic_algorithm|usage-site variance]] example.

Interval types

2007-07-06T02:16:41Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

With interval types, the programmer can restrict the conforming types for an entity. This way, the type set which needs to be checked for system validity of a feature call is restricted to a smaller set of types. In addition, certain rules for generic types will prohibit the unsafe use of generics.

== Syntax ==

At every location where a normal type is expected, an interval type can be specified by adding an upper bound for each type:

<e>
LOWER..UPPER
</e>

This specifies an interval of all types between the types <e>LOWER</e> and <e>UPPER</e>.

== Semantics ==

The intention of an interval type is to specify that an entity can only be attached to a type which lies inside the interval. Thus a type declared as <e>ANY..STRING</e> can be attached to an object of dynamic type <e>ANY</e> or dynamic type <e>STRING</e>. It cannot be attached to an object of a type which lies outside this interval, for example <e>INTEGER</e> or <e>PATH_NAME</e>.

Each interval type describes the set of types which belong to the interval. A type belongs to the inverval if it conforms to the lower bound (<e>LOWER</e>) and if the upper bound (<e>UPPER</e>) conforms to it.

<e>
a: A .. C <=> {A, B, C}
b: A .. B <=> {A, B}
c: A .. NONE <=> {A, B, C, ...}
</e>

=== Conformance rules ===

An interval type ''b'' conforms to an interval type ''a'' if it is a sub-interval of ''a''. So if ''a'' fully encloses the interval ''b'', ''b'' conforms to ''a''.

The conformance rules can also be explained by differently:

* An interval type ''b'' conforms to an interval type ''a'' if the set of types described by the interval of ''b'' is a subset of the set described by the interval of ''a''.

:<e>
a := b -- Is valid as {A, B} is a subset of {A, B, C}
</e>

* A type <e>b: C..D</e> conforms to the type <e>a: A..B</e> if <e>C</e> conforms to <e>A</e> and <e>B</e> conforms to <e>D</e>.

Generic conformance is the same as it is now: A generic type ''b'' conforms to a generic type ''a'' if the base class of ''b'' conforms to ''a'' and all generic parameters conform as well.

=== Generic features ===

For features with formal arguments, another rule exists: A call on a feature wich contains a formal argument is only valid if the generic substitution is monomorphic.

This means that a call on a feature <e>f (g: G)</e> of a class <e>X [G]</e> is only valid if <e>G</e> is monomorphic. Thus the type has to be instantitated with <e>X [Y..Y]</e>. So a call to <e>f</e> on a type <e>X [Y..NONE]</e> is not allowed.

=== Default behaviour ===

As a shorthand for interval definition, we define the following default behaviour which is different for ordinary types and for actual generic type parameters. Ordinary types are per default polymorphic and actual formal parameters monomorphic:

<e>
x: T <=> T .. NONE
y: A [T] <=> A [T .. T] .. NONE
</e>

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Cats and dogs ===

A feature call on a target ''t'' is only valid if it is valid for all polymorphic types which can possibly be assigned to ''t''. With interval types the set of conforming types can be restriced in order to be able to perform calls to features which are covariantly redefined in descendands by excluding such descendants from the dynamic type set.

<e>
a_none: ANIMAL <=> ANIMAL .. NONE
c_none: CAT <=> ANIMAL .. NONE
d_none: DOG <=> ANIMAL .. NONE
a_a: ANIMAL .. ANIMAL
c_c: CAT .. CAT
d_d: DOG .. DOG
a_c: ANIMAL .. CAT
a_d: ANIMAL .. DOG
</e>

Valid assignments:

<e>
a_none := c_none
a_none := d_none
a_none := a_a
a_none := c_c
a_none := d_d
c_none := c_c
d_none := d_d

a_c := a_a
a_c := c_c
a_d := a_a
a_d := d_d
</e>

Invalid assignments:

<e>
-- Invalid: a_a := a_none
-- Invalid: c_c := c_none
-- Invalid: d_d := d_none
-- Invalid: a_c := c_none
-- Invalid: a_d := d_none
</e>

Valid calls:

<e>
a_none.eat (cat_food)
a_a.eat (food)
a_d.eat (food)
</e>

Invalid calls:

<e>
a_none.eat (food)
</e>

=== A simple generic algorithm ===

It is easy to declare an algorithm which needs only read-access on a list:

<e>
class PERSON_PRINTER
feature
print_all (a_list: LIST [PERSON..NONE])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a covariant list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT] <=> LIST [STUDENT..STUDENT]
l_professors: LIST [PROFESSOR] <=> LIST [PROFESSOR..PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT..STUDENT] conforms to LIST [PERSON..NONE]
l_person_printer.print_all (l_students)
-- LIST [PROFESSOR..PROFESSOR] conforms to LIST [PERSON..NONE]
l_person_printer.print_all (l_professor)
end
end
</e>

== Issues ==

=== Generic features ===

The rule about calling features with formal parameters is too restrictive. Let's look at the following code:

<e>
deferred class COMPONENT
end

class COMPOSITE
inherit COMPONENT
feature
components: LIST [COMPONENT]
end
</e>

What should the type of feature <e>components</e> be? In order to be able to call <e>extend</e> on the list, it has to be monomorphic, thus <e>LIST [COMPONENT..COMPONENT]</e>. But since the argument type is now <e>COMPONENT..COMPONENT</e> we actually cannot add anything to the list as no descendant of <e>COMPONENT</e> is in the interval. Actually, since <e>COMPONENT</e> is deferred nothing can be added to the list at all.

But if we define the list as <e>LIST [COMPONENT..NONE]</e> - thus allowing descendants of <e>COMPONENT</e> in the list - then the rule about features with formal arguments disallows any calls to feature <e>extend</e> as the argument is not monomorphic anymore.

=== Expanded and Void ===

Look at the following code snippet:

<e>
local
any_none: ANY..NONE
any_string: ANY..STRING
do
-- invalid as NONE does not conform to INTEGER
any_none := 5
-- invalid as NONE is not in the interval ANY..STRING
any_string := Void
end
</e>

It illustrates two problems in conjunction with <e>NONE</e>:

* The first is that <e>NONE</e> does not conform to expanded types. This makes it impossible to declare a type interval which includes all types in the system, reference or expanded. This prevents the programmer to write code which works with reference types and expanded types, say a generic print algorithm.
* The second one is that <e>Void</e> is of type <e>NONE</e>. This raises the question how <e>Void</e> should be assigned to an interval type of references, or how such a type is initialized in the first place.

== Conclusion ==

The rule about features with formal parameters must be changed to make this solution usable as otherwise the use of generics is restricted too much.

The problem with <e>Void</e> and <e>NONE</e> can easily be solved by declaring that <e>NONE</e> inherits from all types regardless of reference or expanded status. To solve the problem of assigning <e>Void</e> to an interval type it can be defined that <e>Void</e> is of any (detached) reference type. That way it can be assigned to any interval of a refernce type, even a monomorphic one, and it is still disallowed to assign it to expanded types.

Talk:Catcall checkpoints

2007-07-03T22:32:55Z

Juliant:

--[[User:Peter gummer|Peter gummer]] 10:54, 3 July 2007 (CEST) It is annoying that, in order to solve the catcall problem, we have to forbid polymorphic assignments like <e>list_of_any := list_of_string</e>. Yes, we don't want integers poked into <e>list_of_any</e> when it's attached to a list of strings; but usually when we perform such assignments it's so that we can use the list in a read-only fashion. I would prefer to allow such assignments, if and only if the entity on the left is declared '''read-only'''. ''Uh oh'', now I've gone and raised the old question, "C++ has ''const'' so why doesn't Eiffel?"

'''--[[User:Juliant|Juliant]] 00:32, 4 July 2007 (CEST)''':
The assignment has to be disallowed with ''default semantics''. A good solution will allow exactly what you say, an easy way to declare a read-only list. For example the [[usage-site variance]] would allow to declare a list as <e>LIST [+ANY]</e> to mark it read-only.

The last ECMA meeting proposed a new solution but we didn't get the validity rules yet, so we don't have a wiki-page for this at the moment. We will add this when we get them and then we can see how it works there.

Catcall checkpoints

2007-07-02T16:29:51Z

Juliant: /* Generic lists */

[[Category:Catcall]]
These examples should be considered for all catcall solutions:

== Generic lists ==

The default semantics of the catcall solution should work for generics like the following:

<e>
local
any_list: LIST [ANY]
string_list: LIST [STRING]
any_linked_list: LINKED_LIST [ANY]
do
-- Should be allowed with default semantics
any_list := any_linked_list
any_list.put ("abc")
any_linked_list.put (5)

-- Has to be forbidden with default semantics
any_list := string_list
end
</e>

== Faces of covariance ==

The following example shows the difference between generic covariance and non-generic covariance.

<e>
class A [G]
feature
f (t: T) do end
put (g: G) do end
end

class B [G]
inherit A [G] redefine f end
feature
f (u: U) do end
end

local
a_any: A [ANY]
a_string: A [STRING]
b_any: B [ANY]
b_string: B [STRING]
t: T
do
a_any := a_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- no catcall

a_any := b_any
a_any.put (5) -- no catcall
a_any.f (t) -- catcall for non-generic feature

a_any := b_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- catcall for non-generic feature
end
</e>

A safe and expressive solution should have a way to allow all valid cases and prohibit the invalid ones. This needs a way to address the generic and non-generic features indiviually.

== Contravariance ==

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- Should be allowed to sort the string list with an
-- ANY comparator
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

Solutions which pass this test are likely to be expressive for agents as well.

== Agents ==

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

=== Calling agents ===

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
-- The following calls are currently valid and should remain valid.
an_agent.call ([T])
an_agent.call ([U])

an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>
These basic cases mostly rely on the tuple conformance rules to work properly.

=== Assigning agents ===
To allow anything that is safe is more tricky. It requires the ability to model contravariance.
<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- This assignment is naturally allowed as they are the same type.
an_agent := agent_t

-- The following assignments are save but prohibited by the current implementation.
-- If they were allowed it would benefit event driven programming in Eiffel a lot.
-- As agents currently are modeled over the generic mechanism any solution which
-- solves the "comparator problem" is likely to pass here too.
an_agent := agent_empty
an_agent := agent_any

-- The following assignments are currently permitted. This is not the correct
-- behavior as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Catcall checkpoints

2007-07-02T16:28:13Z

Juliant: /* Lists */

[[Category:Catcall]]
These examples should be considered for all catcall solutions:

== Generic lists ==

The default semantics of the catcall solution should work for generics like the following:

<e>
local
any_list: LIST [ANY]
string_list: LIST [STRING]
any_linked_list: LINKED_LIST [ANY]
do
-- Should be allowed with default semantics
any_list := any_linked_list
any_list.put ("abc")
any_linked_list.put (5)
-- Has to be forbidden with default semantics
any_list := string_list
end
</e>

== Faces of covariance ==

The following example shows the difference between generic covariance and non-generic covariance.

<e>
class A [G]
feature
f (t: T) do end
put (g: G) do end
end

class B [G]
inherit A [G] redefine f end
feature
f (u: U) do end
end

local
a_any: A [ANY]
a_string: A [STRING]
b_any: B [ANY]
b_string: B [STRING]
t: T
do
a_any := a_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- no catcall

a_any := b_any
a_any.put (5) -- no catcall
a_any.f (t) -- catcall for non-generic feature

a_any := b_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- catcall for non-generic feature
end
</e>

A safe and expressive solution should have a way to allow all valid cases and prohibit the invalid ones. This needs a way to address the generic and non-generic features indiviually.

== Contravariance ==

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- Should be allowed to sort the string list with an
-- ANY comparator
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

Solutions which pass this test are likely to be expressive for agents as well.

== Agents ==

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

=== Calling agents ===

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
-- The following calls are currently valid and should remain valid.
an_agent.call ([T])
an_agent.call ([U])

an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>
These basic cases mostly rely on the tuple conformance rules to work properly.

=== Assigning agents ===
To allow anything that is safe is more tricky. It requires the ability to model contravariance.
<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- This assignment is naturally allowed as they are the same type.
an_agent := agent_t

-- The following assignments are save but prohibited by the current implementation.
-- If they were allowed it would benefit event driven programming in Eiffel a lot.
-- As agents currently are modeled over the generic mechanism any solution which
-- solves the "comparator problem" is likely to pass here too.
an_agent := agent_empty
an_agent := agent_any

-- The following assignments are currently permitted. This is not the correct
-- behavior as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Catcall checkpoints

2007-07-02T16:25:10Z

Juliant:

[[Category:Catcall]]
These examples should be considered for all catcall solutions:

== Lists ==

== Faces of covariance ==

The following example shows the difference between generic covariance and non-generic covariance.

<e>
class A [G]
feature
f (t: T) do end
put (g: G) do end
end

class B [G]
inherit A [G] redefine f end
feature
f (u: U) do end
end

local
a_any: A [ANY]
a_string: A [STRING]
b_any: B [ANY]
b_string: B [STRING]
t: T
do
a_any := a_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- no catcall

a_any := b_any
a_any.put (5) -- no catcall
a_any.f (t) -- catcall for non-generic feature

a_any := b_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- catcall for non-generic feature
end
</e>

A safe and expressive solution should have a way to allow all valid cases and prohibit the invalid ones. This needs a way to address the generic and non-generic features indiviually.

== Contravariance ==

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- Should be allowed to sort the string list with an
-- ANY comparator
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

Solutions which pass this test are likely to be expressive for agents as well.

== Agents ==

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

=== Calling agents ===

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
-- The following calls are currently valid and should remain valid.
an_agent.call ([T])
an_agent.call ([U])

an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>
These basic cases mostly rely on the tuple conformance rules to work properly.

=== Assigning agents ===
To allow anything that is safe is more tricky. It requires the ability to model contravariance.
<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- This assignment is naturally allowed as they are the same type.
an_agent := agent_t

-- The following assignments are save but prohibited by the current implementation.
-- If they were allowed it would benefit event driven programming in Eiffel a lot.
-- As agents currently are modeled over the generic mechanism any solution which
-- solves the "comparator problem" is likely to pass here too.
an_agent := agent_empty
an_agent := agent_any

-- The following assignments are currently permitted. This is not the correct
-- behavior as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Comparison of catcall solutions

2007-06-24T19:09:06Z

Juliant: /* Solutions for generics */

[[Category:ECMA]]
[[Category:Catcall]]
== 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 [[Single level call rule implementation|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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> where the feature <e>put</e> changes signature from <e>ANY</e> to <e>INTEGER</e>.
* 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 <e>like Current</e>. 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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> only the features based on the formal change their signature while they don't change from <e>LIST [ANY]</e> to <e>LINKED_LIST [ANY]</e> 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 <e>STRING</e> or one for <e>ANY</e> is suitable.
* If you want to pass an argument of type <e>STRING</e> to an agent, the agent either has to accept a <e>STRING</e> or <e>ANY</e> 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 [http://dev.eiffel.com/Covariance_through_renaming 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: [http://dev.eiffel.com/Forget_/_Keep_Mechanism 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueFLEX_CATCALL IssueFLEX_CATCALL on ECMA wiki] 
Reference: Discussion in ECMA mailinglist named ''Catcall removal: another proposal'', [[Restrict types mail|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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueDOG 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: [http://pag.csail.mit.edu/reading-group/variance-ECOOP02.pdf 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: [http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx Article about generics in CLR]

Note: There is also a [http://fams.de/text/type-safe-eiffel.html 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: [http://www.jot.fm/issues/issue_2004_12/article5 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: [http://se.ethz.ch/~meyer/publications/lncs/attached.pdf Article about ''attached types'' by Bertrand Meyer] 
Reference: [http://www.ecma-international.org/publications/standards/Ecma-367.htm 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueCAT IssueCAT on ECMA wiki] 
Reference: [http://www.inf.ethz.ch/~meyer/ongoing/covariance/recast.pdf 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 [[Comparison of catcall solutions#Table_explained|explanation at the end of the table]] for more information

=== General solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Novariance]]
! [[Forget / keep]]
! Dynamic typeset algorithm

|-

! Syntax overhead
| {{Green|No}}
| {{Red|Big}}: forget/keep clauses per type
| {{Green|No}}

|-

! Covariance on non-generic types
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| {{Red|Very limited}}: Only invariant conformance
| {{Orange|Limited}}: Conformance restricted (''keep all'' as default) {{Orange|Limited}}: Use restricted (''forget all'' as default)
| {{Green|As it is now}}

|-

! Agents
| {{Orange|Limited}} {{Green|Safe}}
| {{Orange|Limited}} {{Green|Safe}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on forget/keep clauses
| {{Red|Big}}: Iterative abstract system execution

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Need to know cat features for object tests
| {{Green|Small}}: As it is now

|-

! Whole-system analysis
| {{Green|No}}
| {{Red|Yes}}: use of ''forget all'' depends on system
| {{Red|Yes}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Red|No}}
| {{Red|No}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Orange|Limited}}
| {{Green|Full}}

|-

! Support of IDE (Source changes)
| {{Green|Not needed}}
| {{Orange|Possible}}: Can propose forget/keep clauses
| {{Green|Not needed}}

|}

=== Solutions for non-generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Restrict types]]
! [[DOG proposal]]

|-

! Syntax overhead
| {{Red|Big}}: Restrict clause per type declaration
| {{Orange|Medium}}: ''cat'' on features and on type declarations

|-

! Covariance on non-generic types
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| Not addressed
| Not addressed

|-

! Agents
| Not addressed
| Not addressed

|-

! Comparator
| Not addressed
| Not addressed

|-

! Complexity of compiler check
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on restrict clauses
| {{Green|Small}}: Check of ''cat'' on conformance

|-

! Complexity of runtime
| not yet considered
| {{Green|Small}}

|-

! Whole-system analysis
| {{Orange|Partial}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Orange|Limited}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Red|Very limited}}

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose restrict clauses
| {{Orange|Possible}}: Can propose ''cat'' marks

|}

=== Solutions for generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Usage-site variance]]
! [[Definition-site variance]]
! Wildcard generics

|-

! Syntax overhead
| {{Orange|Medium}}: Variance marks per generic type
| {{Green|Small}}: Variance marks per generic class definition
| {{Orange|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
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}

|-

! Agents
| {{Green|Fully supported}} {{Green|Safe}}
| {{Green|Fully supported}}: If tuples can be specified covariantly {{Green|Safe}}
| {{Green|Fully supported}} {{Green|Safe}}

|-

! Comparator
| {{Green|Supported}}
| {{Green|Supported}}
| {{Green|Supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check

|-

! Complexity of runtime
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Orange|Limited}}: Use of generics changed due to conformance
| {{Red|Very limited}}: Libraries need redesign
| {{Orange|Limited}}: Use of generics changed due to conformance

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose variance marks
| {{Red|Not possible}}: Libraries need redesign
| {{Orange|Possible}}: Can propose variance marks/wildcards

|}

=== Dynamic solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Detachable types]]
! Recast
! Exceptions

|-

! Syntax overhead
| {{Green|Small}}: Detachment marks
| {{Red|Big}}: Recast clauses, recast features
| {{Orange|Medium}}: If rescue clause mandatory {{Green|No}}: If rescue clause not needed

|-

! Covariance on non-generic types
| {{Red|Very limited}}: Only detached arguments, no expanded arguments
| {{Green|Allowed}}
| {{Green|Allowed}}
|-

! Export status restrictions
| Not addressed
| Not addressed
| Not addressed

|-

! Use of generics
| {{Red|Very limited}}: Only detachable formal arguments
| {{Red|Very limited}}: Recast clause for all features with formal generics
| {{Green|As it is now}}

|-

! Agents
| {{Red|As it is now}}
| {{Red|As it is now}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Check for catcalls and do recast
| {{Orange|Medium}}: Check for catcalls and raise exception

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}: All covariant and generic features become detached
| {{Red|Very limited}}: All covariant and generic features need recast clause
| {{Orange|Limited}}: If rescue clause is mandatory {{Green|Full}}: If rescue clause not needed

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose detachment marks
| {{Red|Not possible}}: Programmer must provide recast clause
| {{Red|Not possible}}: If rescue clause mandatory {{Green|Not needed}}: If rescue clause not needed

|}

=== Table explained ===

; Syntax overhead : {{Green|Small}} if a keyword/mark is needed per class/feature declaration; {{Orange|Medium}} if a keyword/mark is neede per type declaration; {{Red|Big}} if a clause is needed per type declaration.
; Use of generics : {{Green|As it is now}} if assignments are possible if generic parameters conform; {{Orange|Limited}} is some restrictions in the use or the conformance between generics exist; {{Red|Very limited}} a lot of restrictions in the use or the conformance between generics exist.
; Agents : {{Green|Fully supported}} if all safe assignments are allowed; {{Orange|Limited}} if not all safe assignments are allowed; {{Red|As it is now}} if unsafe assignments are still possible.
; Comparator : {{Green|Supported}} if for a comparator all safe assignments are permitted (i.e. contravariant assignments); {{Red|Not supported}} if only exact type or even (unsafe) subtypes can be assigned.
; Support of IDE (Source changes) : {{Green|Not needed}} if everything still works the same; {{Orange|Possible}} if the compiler can suggest clauses or marks; {{Red|Not possible}} if the programmer has to specify additional features/instructions.

== Personal opinions ==

[[Personal view about catcall solution]]

Comparison of catcall solutions

2007-06-24T19:08:48Z

Juliant: /* Solutions for generics */

[[Category:ECMA]]
[[Category:Catcall]]
== 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 [[Single level call rule implementation|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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> where the feature <e>put</e> changes signature from <e>ANY</e> to <e>INTEGER</e>.
* 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 <e>like Current</e>. 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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> only the features based on the formal change their signature while they don't change from <e>LIST [ANY]</e> to <e>LINKED_LIST [ANY]</e> 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 <e>STRING</e> or one for <e>ANY</e> is suitable.
* If you want to pass an argument of type <e>STRING</e> to an agent, the agent either has to accept a <e>STRING</e> or <e>ANY</e> 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 [http://dev.eiffel.com/Covariance_through_renaming 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: [http://dev.eiffel.com/Forget_/_Keep_Mechanism 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueFLEX_CATCALL IssueFLEX_CATCALL on ECMA wiki] 
Reference: Discussion in ECMA mailinglist named ''Catcall removal: another proposal'', [[Restrict types mail|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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueDOG 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: [http://pag.csail.mit.edu/reading-group/variance-ECOOP02.pdf 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: [http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx Article about generics in CLR]

Note: There is also a [http://fams.de/text/type-safe-eiffel.html 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: [http://www.jot.fm/issues/issue_2004_12/article5 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: [http://se.ethz.ch/~meyer/publications/lncs/attached.pdf Article about ''attached types'' by Bertrand Meyer] 
Reference: [http://www.ecma-international.org/publications/standards/Ecma-367.htm 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueCAT IssueCAT on ECMA wiki] 
Reference: [http://www.inf.ethz.ch/~meyer/ongoing/covariance/recast.pdf 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 [[Comparison of catcall solutions#Table_explained|explanation at the end of the table]] for more information

=== General solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Novariance]]
! [[Forget / keep]]
! Dynamic typeset algorithm

|-

! Syntax overhead
| {{Green|No}}
| {{Red|Big}}: forget/keep clauses per type
| {{Green|No}}

|-

! Covariance on non-generic types
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| {{Red|Very limited}}: Only invariant conformance
| {{Orange|Limited}}: Conformance restricted (''keep all'' as default) {{Orange|Limited}}: Use restricted (''forget all'' as default)
| {{Green|As it is now}}

|-

! Agents
| {{Orange|Limited}} {{Green|Safe}}
| {{Orange|Limited}} {{Green|Safe}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on forget/keep clauses
| {{Red|Big}}: Iterative abstract system execution

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Need to know cat features for object tests
| {{Green|Small}}: As it is now

|-

! Whole-system analysis
| {{Green|No}}
| {{Red|Yes}}: use of ''forget all'' depends on system
| {{Red|Yes}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Red|No}}
| {{Red|No}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Orange|Limited}}
| {{Green|Full}}

|-

! Support of IDE (Source changes)
| {{Green|Not needed}}
| {{Orange|Possible}}: Can propose forget/keep clauses
| {{Green|Not needed}}

|}

=== Solutions for non-generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Restrict types]]
! [[DOG proposal]]

|-

! Syntax overhead
| {{Red|Big}}: Restrict clause per type declaration
| {{Orange|Medium}}: ''cat'' on features and on type declarations

|-

! Covariance on non-generic types
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| Not addressed
| Not addressed

|-

! Agents
| Not addressed
| Not addressed

|-

! Comparator
| Not addressed
| Not addressed

|-

! Complexity of compiler check
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on restrict clauses
| {{Green|Small}}: Check of ''cat'' on conformance

|-

! Complexity of runtime
| not yet considered
| {{Green|Small}}

|-

! Whole-system analysis
| {{Orange|Partial}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Orange|Limited}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Red|Very limited}}

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose restrict clauses
| {{Orange|Possible}}: Can propose ''cat'' marks

|}

=== Solutions for generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Usage-site variance]]
! [[Definition-site variance]]
! Wildcard generics

|-

! Syntax overhead
| {{Orange|Medium}}: Variance marks per generic type
| {{Green|Small}}: Variance marks per generic class definition
| {{Orange|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
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}

|-

! Agents
| {{Green|Fully supported}} {{Green|Safe}}
| {{Orange|Fully supported}} {{Green|Safe}}: If tuples can be specified covariantly
| {{Green|Fully supported}} {{Green|Safe}}

|-

! Comparator
| {{Green|Supported}}
| {{Green|Supported}}
| {{Green|Supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check

|-

! Complexity of runtime
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Orange|Limited}}: Use of generics changed due to conformance
| {{Red|Very limited}}: Libraries need redesign
| {{Orange|Limited}}: Use of generics changed due to conformance

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose variance marks
| {{Red|Not possible}}: Libraries need redesign
| {{Orange|Possible}}: Can propose variance marks/wildcards

|}

=== Dynamic solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Detachable types]]
! Recast
! Exceptions

|-

! Syntax overhead
| {{Green|Small}}: Detachment marks
| {{Red|Big}}: Recast clauses, recast features
| {{Orange|Medium}}: If rescue clause mandatory {{Green|No}}: If rescue clause not needed

|-

! Covariance on non-generic types
| {{Red|Very limited}}: Only detached arguments, no expanded arguments
| {{Green|Allowed}}
| {{Green|Allowed}}
|-

! Export status restrictions
| Not addressed
| Not addressed
| Not addressed

|-

! Use of generics
| {{Red|Very limited}}: Only detachable formal arguments
| {{Red|Very limited}}: Recast clause for all features with formal generics
| {{Green|As it is now}}

|-

! Agents
| {{Red|As it is now}}
| {{Red|As it is now}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Check for catcalls and do recast
| {{Orange|Medium}}: Check for catcalls and raise exception

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}: All covariant and generic features become detached
| {{Red|Very limited}}: All covariant and generic features need recast clause
| {{Orange|Limited}}: If rescue clause is mandatory {{Green|Full}}: If rescue clause not needed

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose detachment marks
| {{Red|Not possible}}: Programmer must provide recast clause
| {{Red|Not possible}}: If rescue clause mandatory {{Green|Not needed}}: If rescue clause not needed

|}

=== Table explained ===

; Syntax overhead : {{Green|Small}} if a keyword/mark is needed per class/feature declaration; {{Orange|Medium}} if a keyword/mark is neede per type declaration; {{Red|Big}} if a clause is needed per type declaration.
; Use of generics : {{Green|As it is now}} if assignments are possible if generic parameters conform; {{Orange|Limited}} is some restrictions in the use or the conformance between generics exist; {{Red|Very limited}} a lot of restrictions in the use or the conformance between generics exist.
; Agents : {{Green|Fully supported}} if all safe assignments are allowed; {{Orange|Limited}} if not all safe assignments are allowed; {{Red|As it is now}} if unsafe assignments are still possible.
; Comparator : {{Green|Supported}} if for a comparator all safe assignments are permitted (i.e. contravariant assignments); {{Red|Not supported}} if only exact type or even (unsafe) subtypes can be assigned.
; Support of IDE (Source changes) : {{Green|Not needed}} if everything still works the same; {{Orange|Possible}} if the compiler can suggest clauses or marks; {{Red|Not possible}} if the programmer has to specify additional features/instructions.

== Personal opinions ==

[[Personal view about catcall solution]]

Usage-site variance

2007-06-24T19:08:03Z

Juliant: /* Vision 2 Example */ Thanks for the correction Peter

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

The usage-site variance allows the programmer to choose which kind of variance he wants to use when a generic derivation is declared. This allows to use every generic as novariant, covariant or contravariant in contrast to the [[definition-site variance]] where it is set in the class definition.

== Syntax ==

The syntax used here to specify the variance of a generic is simple and may be changed to something more verbose but also clearer:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

See the [[introduction to examples]] for information about the classes used.

=== Conformance rules ===

Depending on the variance of the generic, the conformance rules differ:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>. Note that <e>LINKED_LIST [T]</e> also conforms to <e>LIST [T]</e> as long as the generic parameter matches.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

For the conformance of tuples, we keep that a tuple with more elements conforms to a tuple with less elements as long as the common elements conform:

* <e>TUPLE [T, U]</e> conforms to <e>TUPLE [T]</e>
* <e>TUPLE [U, U]</e> conforms to <e>TUPLE [+T]</e>
* <e>TUPLE [T, U]</e> conforms to <e>TUPLE [-U]</e>

=== Applicable features ===

Depending on the variance of the generic, the applicable features differ:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== A simple generic algorithm ===

It is easy to declare an algorithm over generics as long as only read-access is needed. Just declare input to the algorithm as covariant list.

<e>
class PERSON_PRINTER
feature
print_all (a_list: LIST [+PERSON])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a covariant list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT]
l_professors: LIST [PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT] conforms to LIST [+PERSON]
l_person_printer.print_all (l_students)
-- LIST [PROFESSPR] conforms to LIST [+PERSON]
l_person_printer.print_all (l_professor)
end
end
</e>

=== Comparator ===

In the example of sorting a list with a comparator, contravariant generics can be used. Due to the use of <e>COMPARATOR [-G]</e> when sorting a <e>LIST [G]</e>, we allow to use a comparator which can sort more generally than just objects of type <e>G</e>. This allows to use a comparator for <e>ANY</e> objects to sort a list of strings.

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [-G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_string_comparator: COMPARATOR [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- COMPARATOR [STRING] conforms to COMPARATOR [-STRING]
l_string_sorter.sort (l_list, l_string_comparator)
-- COMPARATOR [ANY] conforms to COMPARATOR [-STRING]
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

=== Agents ===

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

==== Calling agents ====

<e>
local
an_agent: PROCEDURE [+ANY, -TUPLE [+T]]
-- An agent which takes an argument of type T.
do
-- The following calls are surely permitted (and also correct) since
-- the tuple generic inside the tuple is covariant and thus allows
-- the tuple of type U to be passed.
an_agent.call ([T])
an_agent.call ([U])

-- Due to the tuple conformance, the following calls are also
-- permitted. Note that they are both correct.
an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>

We see that this solution allows the full range of applicable arguments for calling agents.

==== Assigning agents ====

<e>
local
an_agent: PROCEDURE [+ANY, -TUPLE [+T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [+ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [+T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [+U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [+T, +T]]

-- This assignment is naturally allowed.
an_agent := agent_t

-- This assignment is allowed since the tuple is declared contravariant
-- and the empty tuple is an ancestor of TUPLE [+T]
an_agent := agent_empty

-- This assignment is allowed and correct. The reason is that TUPLE [+ANY]
-- is an ancestor of TUPLE [+T].
an_agent := agent_any

-- The following assignments are not permitted by the solution. This is the correct
-- behaviour as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

We see that this solution allows all possible agents to be assigned.

Since declaring an agent can be difficult (where did I need to put the "+" and the "-"?), an alternate [[Agent syntax|syntax for agents]] could be useful where the compiler can derive the correct type for an agent.

==== Vision 2 Example ====
A field which makes heavy use of agents and benefits a lot of them is ''event driven programming''. With the current agent mechanism the programmer is sometimes forced to use a hack to circumvent the type checker in order to gain flexibility.

The following code is taken from <e>EV_PND_MOTION_ACTION_SEQUENCE</e>. Here we gain the flexibility that an agent which listens to the event does not have to be a feature which takes all the data provided if the event occurs. Maybe the programmer is just interested in the fact that an actual event occurred and not in the data about it.
<e>
force_extend (action: PROCEDURE [ANY, TUPLE]) is
-- Extend without type checking. Not type save! Use on your own risk!
do
extend (agent wrapper (?, ?, ?, action))
end

wrapper (an_x, a_y: INTEGER; a_pick_and_dropable: EV_ABSTRACT_PICK_AND_DROPABLE;
action: PROCEDURE [ANY, TUPLE])
-- Use this to circumvent tuple type checking. (at your own risk!)
-- Calls `action' passing all other arguments.
do
action.call ([an_x, a_y, a_pick_and_dropable])
end
</e>

If this solution is built into Eiffel the designer of Vision2 would do a small change in <e>ACTION_SEQUENCE</e>. The changes makes sure that we can accept agents to features defined in descendants of <e>ANY</e> (therefore the <e>+ANY</e>) and that we accept agents which are not interested in all data but just (possibly) take parts of it (therefore <e>-EVENT_DATA</e>).
<e>
class
ACTION_SEQUENCE [EVENT_DATA -> TUPLE create default_create end]
inherit
ARRAYED_LIST [PROCEDURE [+ANY, -EVENT_DATA]]
-- old ARRAYED_LIST [PROCEDURE [ANY, EVENT_DATA]]
</e>

The wrapper code can be removed from <e>EV_PND_MOTION_ACTION_SEQUENCE</e> and we also change one line. This change empowers the system to accept descendants of <e>EV_ABSTRACT_PICK_AND_DROPABLE</e> as event data. The two integers do not need be marked covariantly as they are frozen and no descendants exist for them.
<e>
class
EV_PND_MOTION_ACTION_SEQUENCE

inherit
-- old EV_ACTION_SEQUENCE [TUPLE [x: INTEGER; y: INTEGER; pick_and_dropable: EV_ABSTRACT_PICK_AND_DROPABLE]]
EV_ACTION_SEQUENCE [TUPLE [x: INTEGER; y: INTEGER; pick_and_dropable: +EV_ABSTRACT_PICK_AND_DROPABLE]]
</e>
Now with this the actual signature of <e>{EV_PND_MOTION_ACTION_SEQUENCE}.extend</e> looks like this:
<e>
extend (v: PROCEDURE [ANY, -TUPLE [x: INTEGER_32; y: INTEGER_32; +pick_and_dropable: EV_ABSTRACT_PICK_AND_DROPABLE]]
</e>

For the sake of completeness the signature of <e>{EV_PND_MOTION_ACTION_SEQUENCE}.call</e>. Note again that the the field `pick_and_dropable' is covariant allowing to call the event with tuples containing descendants of <e>EV_ABSTRACT_PICK_AND_DROPABLE</e>.
<e>
call (event_data: TUPLE [x: INTEGER_32; y: INTEGER_32; pick_and_dropable: +EV_ABSTRACT_PICK_AND_DROPABLE])
</e>

== Conclusion ==

The usage-site variance is a mechanism which allows both expressive and type-safe generics. It can model agents and comparator types correctly.

Definition-site variance

2007-06-24T19:05:03Z

Juliant: /* Agents */

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

The defintion-site variance allows the programmer to choose which kind of variance he wants to use in the defintion of a generic class. Unlike the [[usage-site variance]], this fixes a specific class to the kind of variance which it supports.

== Syntax ==

The syntax used here to specify the variance of a generic is simple and may be changed to something more verbose but also clearer:

* To specify a novariant generic, the normal syntax can be used: <e>class LIST [G] end</e>
* To specify a covariant generic, we use a plus sign: <e>class READ_LIST [+G] end</e>
* To specify a contravariant generic, we use a minus sign: <e>class WRITE_LIST [-G] end</e>

== Semantics ==

See the [[introduction to examples]] for information about the classes used.

=== Conformance rules ===

Depending on the variance of the generic, the conformance rules differ:

* If a generic class is declared novariant, two generics conform if their base class conforms and the generic parameters match exactly. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* If a generic class is declared covariant, a generic conforms to another if its base class conforms and the generic parameter conforms to the other. Thus <e>READ_LIST [U]</e> conforms to <e>READ_LIST [T]</e>.
* If a generic class is declared contravariant, a generic conforms to another if its base class conforms and the generic parameter is an ancestor of the other. Thus <e>WRITE_LIST [U]</e> conforms to <e>WRITE_LIST [T]</e>.

Tuples are problematic in this solution as have to declare the generic tuple parameters as invariant. For the conformance of tuples, we keep that a tuple with more elements conforms to a tuple with less elements. The common elements have to match exactly due to their invariance:

* <e>TUPLE [T, U]</e> conforms to <e>TUPLE [T]</e>
* <e>TUPLE [U]</e> does not conform to <e>TUPLE [T]</e>

=== Applicable features ===

Depending on the variance of a generic, it can only occur in certain places:

* A novariant generic can be used as argument or result type.
* A covariant generic can only be used as a result type.
* A contravariant generic can only be used as an argument type.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== A simple generic algorithm ===

In order to use lists as read-only lists, the library design has to be adapted. <e>LIST [G]</e> needs to inherit from <e>READ_LIST [+G]</e>. That way you can assign a <e>LIST [STRING]</e> to a <e>READ_LIST [STRING]</e> and, through transitivity of conformance, to a <e>READ_LIST [ANY]</e>.

<e>
class PERSON_PRINTER
feature
print_all (a_list: READ_LIST [PERSON])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a covariant list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT]
l_professors: LIST [PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT] conforms to READ_LIST [PERSON]
l_person_printer.print_all (l_students)
-- LIST [PROFESSOR] conforms to READ_LIST [PERSON]
l_person_printer.print_all (l_professor)
end
end
</e>

=== Comparator ===

For the comparator example to work, the comparator class has to be declared as contravariant generic: <e>class COMPARATOR [-G]</e>.

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_string_comparator: COMPARATOR [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- COMPARATOR [STRING] conforms to COMPARATOR [STRING]
l_string_sorter.sort (l_list, l_string_comparator)
-- COMPARATOR [ANY] conforms to COMPARATOR [STRING]
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

=== Agents ===

Again, to use definition-site variance you have to adapt the library design. The procedure class has to be defined as follows:

<e>
class PROCEDURE [+BASE_TYPE, -OPEN_ARGS -> TUPLE]
end
</e>

==== Calling agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
-- The following calls are surely permitted as the generic
-- parameter in the tuple is novariant since it is not specified
-- further in the procedure class.
an_agent.call ([T])
an_agent.call ([T, ...])

-- Because the tuple is novariant, the following calls are
-- illegal although they would be safe.
an_agent.call ([U])
an_agent.call ([U, ...])
end
</e>

In contrast to [[usage-site variance#Agents|usage-site variance]] you cannot express that the generic parameters of the tuple are covariant. Because of that, the call with a subtype of the actual parameter is not permitted by the type system.

==== Assigning agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- This assignment is naturally allowed.
an_agent := agent_t

-- This assignment is allowed since the tuple is declared contravariant
-- and the empty tuple is an ancestor of TUPLE [T]
an_agent := agent_empty

-- This assignment is not allowed although it would be correct. The reason
-- is that TUPLE [ANY] is not an ancestor of TUPEL [T].
an_agent := agent_any

-- The following assignments are not permitted by the solution. This is the correct
-- behaviour as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Again, the fact that the generic tuple parameters are novariant causes that a safe assignment is prohibited.

==== Covariant tuples ====

The agent mechanism in definition-site variance is not as expressive as it can be because the generic <e>TUPLE</e> parameters cannot be specified as covariant in the class definition of <e>PROCEDURE</e>. Since <e>TUPLE</e> is a special case, you could think about allowing a special notation to denote totally covariant tuples. If this would be available, the mechanism would allow all possible assignments and calls for the agents.

A possible syntax to designate that the generic tuple arguments will be contravariant would be:

<e>
class PROCEDURE [+BASE_TYPE, -OPEN_ARGS -> TUPLE[+]]
end
</e>

== Conclusion ==

This solution requires that the libraries are designed in a way which separates reading and writing to generic datastructes. It allows full use of comparator objects but does not fully support agents.

On the plus side, the client of a library does not need to put variance markers as in the [[usage-site variance]] proposal which makes the use of the solution easier for the normal programmer.

Catcall checkpoints

2007-06-24T18:54:05Z

Juliant:

[[Category:Catcall]]
These examples should be considered for all catcall solutions:

== Faces of covariance ==

The following example shows the difference between generic covariance and non-generic covariance.

<e>
class A [G]
feature
f (t: T) do end
put (g: G) do end
end

class B [G]
inherit A [G] redefine f end
feature
f (u: U) do end
end

local
a_any: A [ANY]
a_string: A [STRING]
b_any: B [ANY]
b_string: B [STRING]
t: T
do
a_any := a_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- no catcall

a_any := b_any
a_any.put (5) -- no catcall
a_any.f (t) -- catcall for non-generic feature

a_any := b_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- catcall for non-generic feature
end
</e>

A safe and expressive solution should have a way to allow all valid cases and prohibit the invalid ones. This needs a way to address the generic and non-generic features indiviually.

== Contravariance ==

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- Should be allowed to sort the string list with an
-- ANY comparator
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

Solutions which pass this test are likely to be expressive for agents as well.

== Agents ==

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

=== Calling agents ===

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
-- The following calls are currently valid and should remain valid.
an_agent.call ([T])
an_agent.call ([U])

an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>
These basic cases mostly rely on the tuple conformance rules to work properly.

=== Assigning agents ===
To allow anything that is safe is more tricky. It requires the ability to model contravariance.
<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- This assignment is naturally allowed as they are the same type.
an_agent := agent_t

-- The following assignments are save but prohibited by the current implementation.
-- If they were allowed it would benefit event driven programming in Eiffel a lot.
-- As agents currently are modeled over the generic mechanism any solution which
-- solves the "comparator problem" is likely to pass here too.
an_agent := agent_empty
an_agent := agent_any

-- The following assignments are currently permitted. This is not the correct
-- behavior as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Catcall checkpoints

2007-06-24T18:52:35Z

Juliant: /* faces of covariance */

[[Category:Catcall]]
These examples should be considered for all catcall solutions:

== faces of covariance ==

The following example shows the difference between generic covariance and non-generic covariance.

<e>
class A [G]
feature
f (t: T) do end
put (g: G) do end
end

class B [G]
inherit A [G] redefine f end
feature
f (u: U) do end
end

local
a_any: A [ANY]
a_string: A [STRING]
b_any: B [ANY]
b_string: B [STRING]
t: T
do
a_any := a_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- no catcall

a_any := b_any
a_any.put (5) -- no catcall
a_any.f (t) -- catcall for non-generic feature

a_any := b_string
a_any.put (5) -- catcall for generic feature
a_any.f (t) -- catcall for non-generic feature
end
</e>

A safe and expressive solution should have a way to allow all valid cases and prohibit the invalid ones. This needs a way to address the generic and non-generic features indiviually.

== contravariance ==

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- Should be allowed to sort the string list with an
-- ANY comparator
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

Solutions which pass this test are likely to be expressive for agents as well.

== Agents ==

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

=== Calling agents ===

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
-- The following calls are currently valid and should remain valid.
an_agent.call ([T])
an_agent.call ([U])

an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>
These basic cases mostly rely on the tuple conformance rules to work properly.

=== Assigning agents ===
To allow anything that is safe is more tricky. It requires the ability to model contravariance.
<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- This assignment is naturally allowed as they are the same type.
an_agent := agent_t

-- The following assignments are save but prohibited by the current implementation.
-- If they were allowed it would benefit event driven programming in Eiffel a lot.
-- As agents currently are modeled over the generic mechanism any solution which
-- solves the "comparator problem" is likely to pass here too.
an_agent := agent_empty
an_agent := agent_any

-- The following assignments are currently permitted. This is not the correct
-- behavior as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Talk:Usage-site variance

2007-06-24T18:48:56Z

Juliant:

--[[User:Peter gummer|Peter gummer]] 20:11, 24 June 2007 (CEST) I think that pages such as this should be clearly marked as research. They could be misleading to someone new to Eiffel, who might stumble upon them and think that they describe the existing Eiffel compiler.

--[[User:Juliant|Juliant]] 20:48, 24 June 2007 (CEST) We added the ''Research'' template to make it clear.

Forget / keep

2007-06-24T18:45:44Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

The forget / keep mechanism enhances the type system. It allows to change types on the feature level by ''forgetting'' specific features (especially features which are covariantly redefined) so that these features can't be called anymore. It also allows to specifically ''keep'' certain features so that they are surely available which in turn changes the conformance rules to only allow types which have this feature with the exact same signature.

== Syntax ==

<e>
-- forget types

-- A type which forgets all covariantly redefined features, thus all
-- subtypes conform to this type.
a: ANIMAL forget all end

-- A type which only forgets the features `eat' and `sleep' but not other
-- covarianlty redefined features or features whose export status is
-- restricted. All subtypes which only redefine or restrict export status
-- of `eat' or `sleep' will conform to this type.
a: ANIMAL forget eat, sleep end

-- keep types

-- A type which keeps all features and looses conformance from subtypes which
-- covariantly redefine features or restrict export status.
b: ANIMAL keep all end

-- A type where all subtypes conform except those who covariantly redefine
-- feature `eat'.
b: ANIMAL keep eat end
</e>

== Semantics ==

The meaning of a ''forget'' clause is that the actual type which is used does not have the features listed in the forget clause. <e>forget all</e> is a bit misleading as it does not forget all features, but only features which are covariantly redefined or have the export status changed to be more restrictive later in the inheritance hierarchy. A better naming would be something along the lines of <e>forget covariance</e> but this does not address the export status change.

The meaning of a ''keep'' clause is the reverse. If a feature is listed in a ''keep'' clause it can be called on that type with the arguments listed in that type. This means in turn that all subclasses which change the signature of those features covariantly don't conform anymore as a call would not be safe anymore.

=== Default behavior ===

The mechanism has two possible default behaviors. If a type is declared without specifying which features to keep or to forget, it can either mean a type which keeps all features or a type which forgets all features. The default behavior has a big impact on the language:
* In the ''keep all'' case, all subclasses which have a covariantly redefined feature don't conform to the parent type anymore as it ''keeps'' this feature.
* In the ''forget all'' case, all subclasses conform to the parent per default, but all features which are covariantly redefined (even much later in the inheritance hierarchy) are not callable since they are ''forgotten''.

=== Conformance rules ===

Conformance is best explained on the feature level. A type <e>SUB</e> conforms to a type <e>PARENT</e> if all features which are available in <e>PARENT</e> are also available in <e>SUB</e>. You have to keep in mind that the type <e>PARENT</e> can forget certain features. Thus <e>SUB</e> only conforms to the type <e>PARENT forget x</e> if SUB also has a <e>forget x</e> clause. For the keep clause it is a little bit different: A type <e>SUB</e> only conforms to the type <e>PARENT keep x</e> if <e>SUB</e> does not restrict the export status of <e>x</e> or changes the arguments covariantly, thus it has the same interface regarding feature <e>x</e>.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Cats and Dogs ===

The examples are taken from the [http://dev.eiffel.com/Forget_/_Keep_Mechanism#Covariant_feature_redefinition reference article]

==== forget mechanism ====

The example regarding covariance on the feature level with the forget mechanism looks as follows:

<e>
local
a: ANIMAL -- means ANIMAL keep all
c: CAT
do
-- illegal assignment, ANIMAL and CAT don't conform
-- since CAT does not have the same signature for `eat'
a := c
a.eat (food)
end
</e>

<e>
local
a: ANIMAL forget all end
c: CAT
do
-- legal, CAT conforms to ANIMAL forget all
a := c

-- illegal, ANIMAL forget all doesn't have a feature eat
a.eat (food)
end
</e>

==== keep mechanism ====

The example regarding covariance on the feature level with the keep mechanism looks as follows:

<e>
local
a: ANIMAL -- means ANIMAL forget all
c: CAT
do
a := c
-- illegal call since the type ANIMAL does not have a feature `eat' anymore
a.eat (food)
end
</e>

<e>
local
a: ANIMAL keep all end
c: CAT
do
-- illegal, CAT does not conform to ANIMAL keep all
a := c

-- legal, ANIMAL keep all still has the feature `eat'
a.eat (food)
end
</e>

=== A Simple Generic Algorithm ===

<e>
deferred class PERSON_PRINTER
feature

print_attributes (a_list: LIST [PERSON] forget all)
-- Print all attributes of each person in the list.
deferred
end
end

deferred class EXAMPLE
feature
example
-- Shows example usage of PERSON_PRINTER.
local
l_students: LINKED_LIST [STUDENT]
l_professors: LINKED_LIST [PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
l_person_printer.print_attributes (l_students)
l_person_printer.print_attributes (l_professor)
end
end
</e>

By forgetting all covariantly redefined features the generics conform and we can reuse this algorithm for all implementations of <e>LIST</e> of descendants of <e>PERSON</e>.

=== Agents ===

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

==== Calling agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T] forget all]
-- An agent which takes an argument of type T.
do
-- The following calls are surely permitted (and also correct) since
-- the tuple generic inside the tuple has a 'forget all' clause and
-- thus allows the tuple of type U to be passed.
an_agent.call ([T])
an_agent.call ([U])

-- Due to the tuple conformance, the following calls are also
-- permitted. Note that they are both correct.
an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>

We see that this solution allows the full range of applicable arguments for calling agents.

==== Assigning agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T] forget all]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE [] forget all]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY] forget all]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T] forget all]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U] forget all]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T] forget all]

-- This assignment is naturally allowed.
an_agent := agent_t

-- Although it would be safe, the following assignments are not permitted by
-- the solution as it does not allow contravariance.
an_agent := agent_empty
an_agent := agent_any

-- The following assignments are not permitted by the solution. This is the correct
-- behaviour as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
-- The reason that they are not permitted is that the signature of 'call' changes
-- and thus don't conform anymore (with 'keep all' as default)
an_agent := agent_u
an_agent := agent_tt
end
</e>

Due to the lack of support for contravariance, not all safe assignments are possible with this solution.

Since declaring an agent can be difficult (there needs to be a "forget all" somewhere?), an alternate [[Agent syntax|syntax for agents]] could be useful where the compiler can derive the correct type for an agent.

== Issues ==

=== Whole-system analysis ===

Consider the following code fragment which shows an object test:

<e>
local
a: ANIMAL
do
if {x: ANIMAL forget all} a then
x.sleep
end
end
</e>

Now if the system is extended with a reference to the class CAT, the code becomes invalid as now <e>ANIMAL forget all</e> does not have a feature <e>sleep</e> anymore. This prevents loading of classes at runtime.

=== Object test ===

Consider the following code fragment which shows an object test:

<e>
local
a: ANIMAL forget all
c: CAT -- cat features 'eat' and 'sleep'
do
-- Valid
a := c
if {x: ANIMAL forget eat} a then
x.sleep
end
end
</e>

For this to work, the runtime must have information about the covariantly redefined features of each class. This adds a considerable amount of work to the object test as you need to check if all features which are covariantly redefined between the test type (<e>ANIMAL</e>) and the dynamic type (<e>CAT</e>) are listed in the forget clause.

== Conclusion ==

This proposal solves catcalls as a whole. This include catcalls which are introduced by covariant argument redefinition through formal arguments in generic classes.
It is not as expressive as other solutions (not fully applicable to agents, comparator example) and it is likely that it adds a lot of syntax to the code.

Agent syntax

2007-06-24T18:43:49Z

Juliant:

[[Category:ECMA]]
{{Research}}
==Agent syntax==

Idea: Use the '''like''' keyword followed by an agent signature definition to define agent types.

The good thing is that in Eiffel the "like" mechanism is already in place and well understood. In order to define an agent type something like
<e>
an_agent: like agent (a_x, a_y: INTEGER): BOOLEAN
</e>
would be very handy. Note that it is very similar to the definition of an inline agent. Of course the argument names could be omitted. But by allowing it we can even provide a named tuple as the argument signature for the call feature.
<e>
an_agent: like agent (INTEGER; INTEGER): BOOLEAN
</e>

The reason to introduce a syntax like this is to let the compiler handle the correct type of the agent. Depending if the type system is enhanced on a per-declaration syntax - like the [[restrict types]] or the [[usage-site variance]] propose - then the definition of an agent can be very cumbersome. By giving the programmer a shorthand he does not need to specify the exact agent type himself.

Comparison of catcall solutions

2007-06-24T18:42:35Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
== 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 [[Single level call rule implementation|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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> where the feature <e>put</e> changes signature from <e>ANY</e> to <e>INTEGER</e>.
* 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 <e>like Current</e>. 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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> only the features based on the formal change their signature while they don't change from <e>LIST [ANY]</e> to <e>LINKED_LIST [ANY]</e> 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 <e>STRING</e> or one for <e>ANY</e> is suitable.
* If you want to pass an argument of type <e>STRING</e> to an agent, the agent either has to accept a <e>STRING</e> or <e>ANY</e> 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 [http://dev.eiffel.com/Covariance_through_renaming 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: [http://dev.eiffel.com/Forget_/_Keep_Mechanism 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueFLEX_CATCALL IssueFLEX_CATCALL on ECMA wiki] 
Reference: Discussion in ECMA mailinglist named ''Catcall removal: another proposal'', [[Restrict types mail|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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueDOG 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: [http://pag.csail.mit.edu/reading-group/variance-ECOOP02.pdf 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: [http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx Article about generics in CLR]

Note: There is also a [http://fams.de/text/type-safe-eiffel.html 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: [http://www.jot.fm/issues/issue_2004_12/article5 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: [http://se.ethz.ch/~meyer/publications/lncs/attached.pdf Article about ''attached types'' by Bertrand Meyer] 
Reference: [http://www.ecma-international.org/publications/standards/Ecma-367.htm 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueCAT IssueCAT on ECMA wiki] 
Reference: [http://www.inf.ethz.ch/~meyer/ongoing/covariance/recast.pdf 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 [[Comparison of catcall solutions#Table_explained|explanation at the end of the table]] for more information

=== General solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Novariance]]
! [[Forget / keep]]
! Dynamic typeset algorithm

|-

! Syntax overhead
| {{Green|No}}
| {{Red|Big}}: forget/keep clauses per type
| {{Green|No}}

|-

! Covariance on non-generic types
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| {{Red|Very limited}}: Only invariant conformance
| {{Orange|Limited}}: Conformance restricted (''keep all'' as default) {{Orange|Limited}}: Use restricted (''forget all'' as default)
| {{Green|As it is now}}

|-

! Agents
| {{Orange|Limited}} {{Green|Safe}}
| {{Orange|Limited}} {{Green|Safe}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on forget/keep clauses
| {{Red|Big}}: Iterative abstract system execution

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Need to know cat features for object tests
| {{Green|Small}}: As it is now

|-

! Whole-system analysis
| {{Green|No}}
| {{Red|Yes}}: use of ''forget all'' depends on system
| {{Red|Yes}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Red|No}}
| {{Red|No}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Orange|Limited}}
| {{Green|Full}}

|-

! Support of IDE (Source changes)
| {{Green|Not needed}}
| {{Orange|Possible}}: Can propose forget/keep clauses
| {{Green|Not needed}}

|}

=== Solutions for non-generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Restrict types]]
! [[DOG proposal]]

|-

! Syntax overhead
| {{Red|Big}}: Restrict clause per type declaration
| {{Orange|Medium}}: ''cat'' on features and on type declarations

|-

! Covariance on non-generic types
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| Not addressed
| Not addressed

|-

! Agents
| Not addressed
| Not addressed

|-

! Comparator
| Not addressed
| Not addressed

|-

! Complexity of compiler check
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on restrict clauses
| {{Green|Small}}: Check of ''cat'' on conformance

|-

! Complexity of runtime
| not yet considered
| {{Green|Small}}

|-

! Whole-system analysis
| {{Orange|Partial}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Orange|Limited}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Red|Very limited}}

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose restrict clauses
| {{Orange|Possible}}: Can propose ''cat'' marks

|}

=== Solutions for generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Usage-site variance]]
! [[Definition-site variance]]
! Wildcard generics

|-

! Syntax overhead
| {{Orange|Medium}}: Variance marks per generic type
| {{Green|Small}}: Variance marks per generic class definition
| {{Orange|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
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}

|-

! Agents
| {{Green|Fully supported}} {{Green|Safe}}
| {{Orange|Almost fully supported}} {{Green|Safe}}
| {{Green|Fully supported}} {{Green|Safe}}

|-

! Comparator
| {{Green|Supported}}
| {{Green|Supported}}
| {{Green|Supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check

|-

! Complexity of runtime
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Orange|Limited}}: Use of generics changed due to conformance
| {{Red|Very limited}}: Libraries need redesign
| {{Orange|Limited}}: Use of generics changed due to conformance

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose variance marks
| {{Red|Not possible}}: Libraries need redesign
| {{Orange|Possible}}: Can propose variance marks/wildcards

|}

=== Dynamic solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Detachable types]]
! Recast
! Exceptions

|-

! Syntax overhead
| {{Green|Small}}: Detachment marks
| {{Red|Big}}: Recast clauses, recast features
| {{Orange|Medium}}: If rescue clause mandatory {{Green|No}}: If rescue clause not needed

|-

! Covariance on non-generic types
| {{Red|Very limited}}: Only detached arguments, no expanded arguments
| {{Green|Allowed}}
| {{Green|Allowed}}
|-

! Export status restrictions
| Not addressed
| Not addressed
| Not addressed

|-

! Use of generics
| {{Red|Very limited}}: Only detachable formal arguments
| {{Red|Very limited}}: Recast clause for all features with formal generics
| {{Green|As it is now}}

|-

! Agents
| {{Red|As it is now}}
| {{Red|As it is now}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Check for catcalls and do recast
| {{Orange|Medium}}: Check for catcalls and raise exception

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}: All covariant and generic features become detached
| {{Red|Very limited}}: All covariant and generic features need recast clause
| {{Orange|Limited}}: If rescue clause is mandatory {{Green|Full}}: If rescue clause not needed

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose detachment marks
| {{Red|Not possible}}: Programmer must provide recast clause
| {{Red|Not possible}}: If rescue clause mandatory {{Green|Not needed}}: If rescue clause not needed

|}

=== Table explained ===

; Syntax overhead : {{Green|Small}} if a keyword/mark is needed per class/feature declaration; {{Orange|Medium}} if a keyword/mark is neede per type declaration; {{Red|Big}} if a clause is needed per type declaration.
; Use of generics : {{Green|As it is now}} if assignments are possible if generic parameters conform; {{Orange|Limited}} is some restrictions in the use or the conformance between generics exist; {{Red|Very limited}} a lot of restrictions in the use or the conformance between generics exist.
; Agents : {{Green|Fully supported}} if all safe assignments are allowed; {{Orange|Limited}} if not all safe assignments are allowed; {{Red|As it is now}} if unsafe assignments are still possible.
; Comparator : {{Green|Supported}} if for a comparator all safe assignments are permitted (i.e. contravariant assignments); {{Red|Not supported}} if only exact type or even (unsafe) subtypes can be assigned.
; Support of IDE (Source changes) : {{Green|Not needed}} if everything still works the same; {{Orange|Possible}} if the compiler can suggest clauses or marks; {{Red|Not possible}} if the programmer has to specify additional features/instructions.

== Personal opinions ==

[[Personal view about catcall solution]]

Detachable types

2007-06-24T18:42:07Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

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.

This is specified in the [http://www.ecma-international.org/publications/standards/Ecma-367.htm ECMA Eiffel standard 2nd edition of June 2006].

== Syntax ==

No new syntax is necessary.

== Semantics ==

In this solution, it is only allowed to covariantly redefine arguments to detachable types. This ensures that an object test is done before the use of an argument. If now a catcall happens, the object test will fail. Since the argument is of detachable type, the programmer has to handle the case where Void is passed anyway and this also handles the catcall.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Cats and dogs ===

The definition of the CAT class changes as follows:
<e>
class CAT
inherit ANIMAL redefine eat end
feature
eat (food: ? CAT_FOOD)
do
if {cat_food: CAT_FOOD} food then
-- Use `cat_food'
else
-- either Void or an argument of type FOOD passed
end
end
end
</e>

== Issues ==

=== Weak covariance support ===

See [http://dev.eiffel.com/New_CAT_call article on dev.eiffel.com].

=== Generics ===

With the current conformance of generics, different generic derivations can be seen as if they covariantly redefined the features with formal generic parameters. For example feature <e>put</e> from the class <e>LIST</e> if you look at the signature of <e>LIST [ANY]</e> compared to <e>LIST [STRING]</e>. As with anchored types as parameters, you would also have to specify that all formal generic parameters need to be detached. This would mean that all classes which use generic parameters always have to use object tests to use the generic parameters, and Void-safety cannot be expressed on the type system level which would remove the main benefit of attached types in the context of generics.

=== Expanded types ===

The type rule specified by ECMA (VTCT, 8.11.8) defines that an expanded type cannot have an attachment mark since Void is not a valid value for it. Given that covariant feature redeclaration, especially anchored types for arguments, can only occur with detached types, this means that arguments cannot be covariantly redefined into expanded types.

The base classes like <e>INTEGER</e> which currently inherit from <e>NUMERIC</e> which only defines it's arguments as <e>like Current</e> would be invalid in their current form. Also if formal generic parameters need to be detached as explained above, generic derivations would not be allowed for expanded types if the formal generic occurs as a parameter of a feature. Especially <e>LIST [INTEGER]</e> would not be possible.

== Conclusion ==

The problems arise partially due to the fact that two concepts are mixed:
* Attachable/detachable types: A type <e>? T</e> can be attached to an object of type T or not attached at all (i.e. Void)
* Catcall arguments: In a catcall, the type of the argument can either be the expected type or the type of an ancestor version of the feature.

By using detachable types to solve catcalls, the notion of a detachable type is expanded to be able to hold types of all ancestors as well.

In addition to this, the problems with generics and expanded types show that this solution does severely limit the usefulness of covariance.

Definition-site variance

2007-06-24T18:41:53Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

The defintion-site variance allows the programmer to choose which kind of variance he wants to use in the defintion of a generic class. Unlike the [[usage-site variance]], this fixes a specific class to the kind of variance which it supports.

== Syntax ==

The syntax used here to specify the variance of a generic is simple and may be changed to something more verbose but also clearer:

* To specify a novariant generic, the normal syntax can be used: <e>class LIST [G] end</e>
* To specify a covariant generic, we use a plus sign: <e>class READ_LIST [+G] end</e>
* To specify a contravariant generic, we use a minus sign: <e>class WRITE_LIST [-G] end</e>

== Semantics ==

See the [[introduction to examples]] for information about the classes used.

=== Conformance rules ===

Depending on the variance of the generic, the conformance rules differ:

* If a generic class is declared novariant, two generics conform if their base class conforms and the generic parameters match exactly. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>.
* If a generic class is declared covariant, a generic conforms to another if its base class conforms and the generic parameter conforms to the other. Thus <e>READ_LIST [U]</e> conforms to <e>READ_LIST [T]</e>.
* If a generic class is declared contravariant, a generic conforms to another if its base class conforms and the generic parameter is an ancestor of the other. Thus <e>WRITE_LIST [U]</e> conforms to <e>WRITE_LIST [T]</e>.

Tuples are problematic in this solution as have to declare the generic tuple parameters as invariant. For the conformance of tuples, we keep that a tuple with more elements conforms to a tuple with less elements. The common elements have to match exactly due to their invariance:

* <e>TUPLE [T, U]</e> conforms to <e>TUPLE [T]</e>
* <e>TUPLE [U]</e> does not conform to <e>TUPLE [T]</e>

=== Applicable features ===

Depending on the variance of a generic, it can only occur in certain places:

* A novariant generic can be used as argument or result type.
* A covariant generic can only be used as a result type.
* A contravariant generic can only be used as an argument type.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== A simple generic algorithm ===

In order to use lists as read-only lists, the library design has to be adapted. <e>LIST [G]</e> needs to inherit from <e>READ_LIST [+G]</e>. That way you can assign a <e>LIST [STRING]</e> to a <e>READ_LIST [STRING]</e> and, through transitivity of conformance, to a <e>READ_LIST [ANY]</e>.

<e>
class PERSON_PRINTER
feature
print_all (a_list: READ_LIST [PERSON])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a covariant list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT]
l_professors: LIST [PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT] conforms to READ_LIST [PERSON]
l_person_printer.print_all (l_students)
-- LIST [PROFESSOR] conforms to READ_LIST [PERSON]
l_person_printer.print_all (l_professor)
end
end
</e>

=== Comparator ===

For the comparator example to work, the comparator class has to be declared as contravariant generic: <e>class COMPARATOR [-G]</e>.

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_string_comparator: COMPARATOR [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- COMPARATOR [STRING] conforms to COMPARATOR [STRING]
l_string_sorter.sort (l_list, l_string_comparator)
-- COMPARATOR [ANY] conforms to COMPARATOR [STRING]
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

=== Agents ===

Again, to use definition-site variance you have to adapt the library design. The procedure class has to be defined as follows:

<e>
class PROCEDURE [+BASE_TYPE, -OPEN_ARGS -> TUPLE]
end
</e>

==== Calling agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
-- The following calls are surely permitted as the generic
-- parameter in the tuple is novariant since it is not specified
-- further in the procedure class.
an_agent.call ([T])
an_agent.call ([T, ...])

-- Because the tuple is novariant, the following calls are
-- illegal although they would be safe.
an_agent.call ([U])
an_agent.call ([U, ...])
end
</e>

In contrast to [[usage-site variance#Agents|usage-site variance]] you cannot express that the generic parameters of the tuple are covariant. Because of that, the call with a subtype of the actual parameter is not permitted by the type system.

==== Assigning agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- This assignment is naturally allowed.
an_agent := agent_t

-- This assignment is allowed since the tuple is declared contravariant
-- and the empty tuple is an ancestor of TUPLE [T]
an_agent := agent_empty

-- This assignment is not allowed although it would be correct. The reason
-- is that TUPLE [ANY] is not an ancestor of TUPEL [T].
an_agent := agent_any

-- The following assignments are not permitted by the solution. This is the correct
-- behaviour as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Again, the fact that the generic tuple parameters are novariant causes that a safe assignment is prohibited.

== Conclusion ==

This solution requires that the libraries are designed in a way which separates reading and writing to generic datastructes. It allows full use of comparator objects but does not fully support agents.

On the plus side, the client of a library does not need to put variance markers as in the [[usage-site variance]] proposal which makes the use of the solution easier for the normal programmer.

DOG proposal

2007-06-24T18:41:41Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

This solution prevents catcalls by prohibiting polymorphic calls to features which are the source of potential catcalls.

== Syntax ==

A new keyword "cat" (subject to change) is introduced. It can be applied in front of features and type declarations.
<e>
feature
cat f (a: ANY)
-- Such a feature is called a cat-feature
local
l: cat DOG -- Such a type is called a cat-type
do
end
</e>
Features and types with the "cat" keyword will be referred to from now on as cat-features and cat-types.

== Semantics ==

In order to be able to redefine argument types of features covariantly and restrict the export status a feature has to be marked with the "cat" keyword. Such features can only be called on types which are declared with the "cat" keyword as well. The semantics of the "cat" keyword is that it is a monomorphic type. This is contrary to ordinary declarations which remain polymorphic. By allowing calls to "cat" features only on monomorphic types the compiler knows exactly which signature to check against. As the type cannot possibly change at runtime because of monomorphism of a cat-type the problem is avoided.

=== Conformance rules ===

The conformance stays the same but has one special case more: No type conforms to a cat-type except the same cat-type.
<e>
a: A
b: B
ca: cat A
cb: cat B
-- Conform and therefore valid
a := a
a := b
a := ca
a := cb
b := b
b := cb
ca := ca
cb := cb
-- Invalid (not all mentioned)
ca := a -- `a' could be attached to an object of type `B'
ca := b -- `ca' is monomorphic
</e>

== Examples ==

See the [[introduction to examples]] for information about the classes used but we give enhanced versions for some classes:
<e>
class ANIMAL
feature
cat eat (f: FOOD) do end
cat sleep do end
end
</e>
This is needed so that the (covariant) redefinition of the argument types of these features or the restriction of the export status is valid.

=== Cats and dogs ===

local
a: ANIMAL
ca: cat ANIMAL
c: CAT
cc: cat CAT
d: DOG
cd: cat DOG
f: FOOD
cf: CAT_FOOD
do
-- Invalid calls, both features are marked as cat.
a.eat (f)
a.sleep
c.eat (cf)
-- In order to be valid their target has to be of cat-type.
ca.eat (f)
ca.eat (cf)
ca.sleep
end

=== Generics ===

Generics are not that obvious and clear defined in the article. However there is always one save solution.

<e>
local
a: ANIMAL
ca: cat ANIMAL
la: LIST [ANIMAL]
lca: LIST [cat ANIMAL]
cla: cat LIST [ANIMAL]
clca: cat LIST [cat ANIMAL]
cllca: LINKED_LIST [cat ANIMAL]
do
-- Invalid:
lca := la -- ANIMAL is not cat: The list could contain polymorphic animals
lca := cla -- This is again because ANIMAL is not cat: Same reason as above.
clca := lca -- This time it is because we assign to a cat LIST.
clca := cla -- Here it is again because ANIMAL is not cat.
clca := llca -- LINKED_LIST is not of cat-type.
-- Invalid: Attachment to cat-type
ca := la.item (1) -- The result is not cat-type while the target of the assignment is.

-- Valid:
la := lca
la := cla
la := clca
lca := clca
cla := clca
lca := llca -- The list can still be used polymorphic
-- Valid: Attachement to non cat-type
a := la.item (1)
a := lca.item (1)
a := cla.item (1)
a := clca.item (1)
-- Valid: Attachement to cat-type
ca := lca.item (1)
ca := clca.item (1)
end
</e>

== Issues ==

=== Lacks support for generics ===

The solution is not suited to prohibit catcalls occurring in the context of generics.
If you assumes that each feature of a generic containing the formal as an argument is implicit ''cat'' you can only call them on cat lists:
<e>
feature
list: LIST [ANY]
local
ll: cat LINKED_LIST [DOG]
do
create ll
ll.extend (create {DOG})
end

not_so_nice
local
l: cat LIST [DOG]
ll: cat LINKED_LIST [DOG]
do
-- You cannot write algorithms which fill lists implementation independent.
-- INVALID: l := ll
l.extend (create {DOG})
end
</e>

This is because the base type of a generic has two kind of generic features: The ordinary ones like `is_equal' or other special features and then the ones who carry the formal as an argument. The difference is that a feature like `is_equal' changes its signature from LIST [A] to LINKED_LIST [A] but `put' does not.

=== Programmer needs foresight ===

This solution requires the programmer to think ahead. If a feature of a library is not marked as "cat" it becomes really difficult to change it later. This is not only because the owner of library is somebody else but also because it would invalidate probably a lot of existing code.

== Conclusion ==

This solution is targeted to ordinary types. However, it can easily be paired with another solution [[Comparison_of_catcall_solutions#Overview_of_solutions_for_generics|specific for generics]]. They might even look the same or use partly the same keywords and form a good solution in symbiosis.

Restrict types

2007-06-24T18:41:28Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==
This solution uses enhancements to the type system to ensure CAT call freeness. It tackles the problem on the type basis for each entity declaration (which includes variables and generic parameters). The programmer declares a set of types and depending on the type declaration of a target of a qualified call all problematic features regarding CAT are disabled.

A call on a target is only valid if it cannot become possibly invalid at run-time due to polymorphism and covariantly redefined features or changed export status.
This is achieved as the compiler checks that for all types which could be attached to a variable that all calls are valid.
To help the compiler the programmer '''restricts''' the set of possible types.

== Syntax and semantic==
There were various proposals for syntax. They all express sets of types. Some include set operations and simplified construction by using construct to describe intervals.
In the end it all comes down to the fact that the notion of a type in Eiffel is enhanced to a set of types.

The last proposal on the ECMA mailinglist is introduced here in a simplified, less formal manner:

<e>
a_type: TYPE restrict TYPE_SET
</e>

An actual type set for <e>TYPE_SET</e> can be constructed in many different ways. This proposal includes syntactic sugar to create sets out of given intervals and includes the set operations ''union'', ''intersection'' and ''subtraction''.
<e>
ANY .. NONE -- Fits all types
ANY > -- Means the same
> NONE -- Means the same
T > -- T and conforming types
> T -- Types to which T conforms to
T .. U -- Types conforming to T and to which U conforms
X .. Y -- Types conforming to X and to which Y conforms
{T .. U} + {X .. Y} -- Types that satisfy any of the preceding two conditions
{T .. U} - {X .. Y} -- Types that satisfy the first of those but not the second
{T .. U} * {X .. Y} -- Types that satisfy both
</e>

Once the compiler has a set of types it computes all features which are CAT free. This relies on the fact that all types are known at compile time.

A call on a target is only valid if it cannot become possibly invalid at run-time due to polymorphism and covariantly redefined features or changed export status.
This is achieved as the compiler checks that for all types which could be attached to a variable that all calls are valid.
To help the compiler the programmer '''restricts''' the set of possible types.

=== Conformance rules ===
The conformance rule for the new introduced entity ''type-set'' is given by the subset relation:

T restrict S conforms to T restrict S' only if S is a subset of S'

A few examples for some type sets help one to get started:
<e>
{ANIMAL} := {CAT} -- Does NOT conform. There is just an ANIMAL in the set!
</e>
<e>ANIMAL .. NONE</e> creates the set <e>{ANIMAL, CAT, DOG, ..., NONE}</e>

One can see now that the {CAT} is a subset of it and per definition the two sets conform:
<e>
{ANIMAL, CAT, DOG, ..., NONE} := {CAT}
</e>

=== Default behavior ===
An important decision to be made is what the default behavior is for:
<e>
a_type: TYPE
</e>
There are a couple of trade offs here. The possibilities are as follows:
* <e>TYPE .. TYPE -- monomorphic</e>
* <e>TYPE .. NONE -- polymorphic</e>
The choice made [[Restrict types mail|here]] is the second one: polymorphic
The article does not explain how exactly generic types are handled. Are generic parameters monomorphic? What are the conformance rules for generics?

== Examples ==
See the [[introduction to examples]] for information about the classes used.

=== Cats and dogs ===
Here is a list of valid and invalid assignments. A valid assignment in this context means that the right type conforms to the left type of the assignment.
<e>
local
zoo_member: ANIMAL -- Polymorph is default: The type set contains any descendant of ANIMAL.
animal: ANIMAL restrict ANIMAL
cat: CAT restrict CAT
dog: DOG restrict DOG
animal_not_hungry: ANIMAL restrict ANIMAL .. NONE -- One cannot call `eat' as it is covariantly redefined in CAT
animal_only_eating_cat_food: ANIMAL restrict ANIMAL .. CAT -- They can eat, but only cat food.

food: FOOD restrict FOOD
-- Food
cat_food: CAT_FOOD restrict CAT_FOOD
-- Cat food
do
animal := zoo_member -- Invalid! Default for ANIMAL is ANIMAL .. NONE, this is not a subset of {ANIMAL}
animal := cat -- Invalid! {CAT} is not a subset of {ANIMAL}
animal := dog -- Invalid! Rejected out of the same reason as the cat,
-- but to assign the dog would be save.
animal_not_hungry := cat -- Valid
animal_not_hungry := dog -- Valid
animal_only_eating_cat_food := cat -- Valid
animal_only_eating_cat_food := dog -- Invalid, but would be save for this example.
end
</e>

=== Generics ===
This mechanism partly describes the handling of generic types. The only major difference between the version presented here and the one in the wiki is that <e>la := lc</e> was moved to the invalid cases.

<e>
lc: LIST [CAT]; lo: LIST [OCTOPUS]
la: LIST [ANIMAL]
lac: LIST [ANIMAL restrict {CAT}]
laa: LIST [ANIMAL restrict] -- Monomorphic list

-- All OK.
lac := lc ; la := lo

-- INVALD: la := lc ; laa := la ; laa := lac ; laa := lc ; laa := lo ; lac := lo

</e>
<e>
-- OK
lac.item.eat (cf)

-- INVALID: lac.item.eat (f)
-- INVALID: la.item.eat (f)
-- INVALID: la.item.eat (cf) -- Becomes valid if OCTOPUS is removed from system
</e>

== Issues ==
=== Void and NONE ===
Note that the fact that ''Void'' is of type <e>NONE</e> does not fit into the conformance rules. 
If we check this code with the currently given rules it would be rejected:
<e>
a_t: T .. T
a_t := Void
</e>

<e>{NONE}</e> is no subset of <e>{T}</e>.

=== Lists ===
There are some interesting cases:
<e>
lla: LIST [LIST [ANIMAL]] restrict {LIST [LIST [ANIMAL]] .. LIST [LIST [CAT]]}
</e>
Now we apply the definition of the interval using the current conformance rules for types given by the ECMA standard.
<e>
T .. U -- Types conforming to T and to which U conforms
</e>
The following set is described by the interval above:
<e>
{LIST [LIST [ANIMAL]], LIST [LIST [CAT]]}
</e>
So we are allowed to assign a <e>LIST [LIST [CAT]]</e> to `l'. 
Now the result type of item is <e>LIST [ANIMAL]</e>:
<e>
lla.item (1) -- LIST [ANIMAL]
</e>
But then one could produce a CAT call like this:
<e>
lla.item (1).put (create {DOG})
</e>
Here the whole code:
<e>
local
lla: LIST [LIST [ANIMAL]] restrict {LIST [LIST [ANIMAL]] .. LIST [LIST [CAT]]}
llc: LIST [LIST [CAT]]
la: LIST [ANIMAL]
do
create llc...
lla := llc -- Type of `llc' is in type set of `lla'
la := lla.item (1) -- Dynamic type of la is LIST [CAT]
la.put (create {DOG}) -- Now there is an instance of DOG in LIST [CAT]
end
</e>
This is indeed bad because cats can have features which dogs do not have, calling them would lead to system failure.
We might try to fix this by changing the conformance for generics and the rule how intervals are generated.

== Conclusion ==
The solution in its current state solves CAT calls only for ordinary types. But it might be possible to enhance it to solve generic types as well.

Usage-site variance

2007-06-24T18:40:45Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

The usage-site variance allows the programmer to choose which kind of variance he wants to use when a generic derivation is declared. This allows to use every generic as novariant, covariant or contravariant in contrast to the [[definition-site variance]] where it is set in the class definition.

== Syntax ==

The syntax used here to specify the variance of a generic is simple and may be changed to something more verbose but also clearer:

* To specify a novariant generic, the normal syntax can be used: <e>LIST [ANY]</e>
* To specify a covariant generic, we use a plus sign: <e>LIST [+ANY]</e>
* To specify a contravariant generic, we use a minus sign: <e>LIST [-ANY]</e>

== Semantics ==

See the [[introduction to examples]] for information about the classes used.

=== Conformance rules ===

Depending on the variance of the generic, the conformance rules differ:

* A generic conforms to a novariant generic if it has the exact same generic parameter. Thus <e>LIST [T]</e> only conforms to <e>LIST [T]</e>. Note that <e>LINKED_LIST [T]</e> also conforms to <e>LIST [T]</e> as long as the generic parameter matches.
* A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus <e>LIST [U]</e> conforms to <e>LIST [+T]</e>.
* A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus <e>LIST [T]</e> conforms to <e>LIST [-U]</e>.

For the conformance of tuples, we keep that a tuple with more elements conforms to a tuple with less elements as long as the common elements conform:

* <e>TUPLE [T, U]</e> conforms to <e>TUPLE [T]</e>
* <e>TUPLE [U, U]</e> conforms to <e>TUPLE [+T]</e>
* <e>TUPLE [T, U]</e> conforms to <e>TUPLE [-U]</e>

=== Applicable features ===

Depending on the variance of the generic, the applicable features differ:

* On a novariant generic, all features can be used.
* On a covariant generic, only features which have the formal generic as a result type can be used. If the formal generic appears in an argument this feature is invalid.
* On a contravariant generic, only feature which have the formal generc as an argument type can be used. If the formal generic appears as a result type this feature is invalid.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== A simple generic algorithm ===

It is easy to declare an algorithm over generics as long as only read-access is needed. Just declare input to the algorithm as covariant list.

<e>
class PERSON_PRINTER
feature
print_all (a_list: LIST [+PERSON])
-- Print all attributes of each person in the list.
do
from
a_list.start
until
a_list.after
do
-- Reading is valid on a covariant list
a_list.item.print
end
end
end

class EXAMPLE
feature
make
local
l_students: LIST [STUDENT]
l_professors: LIST [PROFESSOR]
l_person_printer: PERSON_PRINTER
do
create l_person_printer
-- LIST [STUDENT] conforms to LIST [+PERSON]
l_person_printer.print_all (l_students)
-- LIST [PROFESSPR] conforms to LIST [+PERSON]
l_person_printer.print_all (l_professor)
end
end
</e>

=== Comparator ===

In the example of sorting a list with a comparator, contravariant generics can be used. Due to the use of <e>COMPARATOR [-G]</e> when sorting a <e>LIST [G]</e>, we allow to use a comparator which can sort more generally than just objects of type <e>G</e>. This allows to use a comparator for <e>ANY</e> objects to sort a list of strings.

<e>
class SORTER [G]
feature
sort (a_list: LIST [G]; a_comparator: COMPARATOR [-G])
do
-- Somewhere in the loop:
a_comparator.compare (l_string_1, l_string_2)
end
end

class EXAMPLE
feature
make
local
l_list: LIST [STRING]
l_string_sorter: SORTER [STRING]
l_string_comparator: COMPARATOR [STRING]
l_any_comparator: COMPARATOR [ANY]
do
-- COMPARATOR [STRING] conforms to COMPARATOR [-STRING]
l_string_sorter.sort (l_list, l_string_comparator)
-- COMPARATOR [ANY] conforms to COMPARATOR [-STRING]
l_string_sorter.sort (l_list, l_any_comparator)
end
end
</e>

=== Agents ===

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

==== Calling agents ====

<e>
local
an_agent: PROCEDURE [+ANY, -TUPLE [+T]]
-- An agent which takes an argument of type T.
do
-- The following calls are surely permitted (and also correct) since
-- the tuple generic inside the tuple is covariant and thus allows
-- the tuple of type U to be passed.
an_agent.call ([T])
an_agent.call ([U])

-- Due to the tuple conformance, the following calls are also
-- permitted. Note that they are both correct.
an_agent.call ([T, ...])
an_agent.call ([U, ...])
end
</e>

We see that this solution allows the full range of applicable arguments for calling agents.

==== Assigning agents ====

<e>
local
an_agent: PROCEDURE [+ANY, -TUPLE [+T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [+ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [+T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [+U]]
agent_tt := agent (t: T; t2: T) do end --> PROCEDURE [ANY, TUPLE [+T, +T]]

-- This assignment is naturally allowed.
an_agent := agent_t

-- This assignment is allowed since the tuple is declared contravariant
-- and the empty tuple is an ancestor of TUPLE [+T]
an_agent := agent_empty

-- This assignment is allowed and correct. The reason is that TUPLE [+ANY]
-- is an ancestor of TUPLE [+T].
an_agent := agent_any

-- The following assignments are not permitted by the solution. This is the correct
-- behaviour as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

We see that this solution allows all possible agents to be assigned.

Since declaring an agent can be difficult (where did I need to put the "+" and the "-"?), an alternate [[Agent syntax|syntax for agents]] could be useful where the compiler can derive the correct type for an agent.

==== Vision 2 Example ====
A field which makes heavy use of agents and benefits a lot of them is ''event driven programming''. With the current agent mechanism the programmer is sometimes forced to use a hack to circumvent the type checker in order to gain flexibility.

The following code is taken from <e>EV_PND_MOTION_ACTION_SEQUENCE</e>. Here we gain the flexibility that an agent which listens to the event does not have to be a feature which takes all the data provided if the event occurs. Maybe the programmer is just interested in the fact that an actual event occurred and not in the data about it.
<e>
force_extend (action: PROCEDURE [ANY, TUPLE]) is
-- Extend without type checking. Not type save! Use on your own risk!
do
extend (agent wrapper (?, ?, ?, action))
end

wrapper (an_x, a_y: INTEGER; a_pick_and_dropable: EV_ABSTRACT_PICK_AND_DROPABLE;
action: PROCEDURE [ANY, TUPLE])
-- Use this to circumvent tuple type checking. (at your own risk!)
-- Calls `action' passing all other arguments.
do
action.call ([an_x, a_y, a_pick_and_dropable])
end
</e>

If this solution is built into Eiffel the designer of Vision2 would do a small change in <e>ACTION_SEQUENCE</e>. The changes makes sure that we can accept agents to features defined in ancestors of <e>ANY</e> (therefore the <e>+ANY</e>) and that we accept agents which are not interested in all data but just (possibly) take parts of it (therefore <e>-EVENT_DATA</e>).
<e>
class
ACTION_SEQUENCE [EVENT_DATA -> TUPLE create default_create end]
inherit
ARRAYED_LIST [PROCEDURE [+ANY, -EVENT_DATA]]
-- old ARRAYED_LIST [PROCEDURE [ANY, EVENT_DATA]]
</e>

The wrapper code can be removed from <e>EV_PND_MOTION_ACTION_SEQUENCE</e> and we also change one line. This change empowers the system to accept descendants of <e>EV_ABSTRACT_PICK_AND_DROPABLE</e> as event data. The two integers do not need be marked covariantly as they are frozen and no descendants exist for them.
<e>
class
EV_PND_MOTION_ACTION_SEQUENCE

inherit
-- old EV_ACTION_SEQUENCE [TUPLE [x: INTEGER; y: INTEGER; pick_and_dropable: EV_ABSTRACT_PICK_AND_DROPABLE]]
EV_ACTION_SEQUENCE [TUPLE [x: INTEGER; y: INTEGER; pick_and_dropable: +EV_ABSTRACT_PICK_AND_DROPABLE]]
</e>
Now with this the actual signature of <e>{EV_PND_MOTION_ACTION_SEQUENCE}.extend</e> looks like this:
<e>
extend (v: PROCEDURE [ANY, -TUPLE [x: INTEGER_32; y: INTEGER_32; +pick_and_dropable: EV_ABSTRACT_PICK_AND_DROPABLE]]
</e>

For the sake of completeness the signature of <e>{EV_PND_MOTION_ACTION_SEQUENCE}.call</e>. Note again that the the field `pick_and_dropable' is covariant allowing to call the event with tuples containing descendants of <e>EV_ABSTRACT_PICK_AND_DROPABLE</e>.
<e>
call (event_data: TUPLE [x: INTEGER_32; y: INTEGER_32; pick_and_dropable: +EV_ABSTRACT_PICK_AND_DROPABLE])
</e>

== Conclusion ==

The usage-site variance is a mechanism which allows both expressive and type-safe generics. It can model agents and comparator types correctly.

Novariance

2007-06-24T18:40:20Z

Juliant:

[[Category:ECMA]]
[[Category:Catcall]]
{{Research}}
== Introduction ==

Novariance can be looked at for non-generics and generics:

* For non-generics, it just disallows covariant redeclaration of feature arguments. Since a covariant feature redeclaration is actually a strengthening of the precondition - strengthening of the type - the safest way is to disallow it. Also it is not really consistent in allowing strengthening of the precondition on the type system level but not on normal preconditions.

* For generics, you know from the beginning that for two different generic derivations of the same type, the generic arguments of features will differ. This is an inherent property of generics and you cannot disallow the change of type in the arguments. But again, since this is in general a strengthening of the precondition (from LIST [ANY] to LIST [STRING]) the direct solution is to disallow assignments between these types and thus removing conformance between generic derivations based on the conformance of the generic parameter. Conformance is only available on the base type if the generic parameters match exactly.

== Syntax ==

No new syntax is necessary.

== Semantics ==

The change in semantics as described above is:

* Covariant redefinition of feature arguments is not allowed.
* Generics only conform if the base types conform and the generic parameters are exactly the same.

== Examples ==

See the [[introduction to examples]] for information about the classes used.

=== Cat ===

To see how the ''CAT'' example can be modeled without covariance, see the article about [http://dev.eiffel.com/Covariance_through_renaming covariance through renaming].

=== Agents ===

For agents, we will look at an example with the type <e>T</e> and a subtype <e>U</e>. We will see an agent declaration and then check which arguments that are allowed:

==== Calling agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do

-- In the case of novariant generics, the only permitted call is
an_agent.call ([T])

-- None of the follwing calls is permitted, although it would be safe to
-- pass a tuple with more arguments or a tuple which consists of subtypes
-- of the required argument.
an_agent.call ([T, ...])
an_agent.call ([U])
an_agent.call ([U, ...])
end
</e>

The observations made are that it is not possible to pass an argument which has a different type than the exact required argument. This means that if you want to pass an argument of type <e>U</e> to an agent which requires an argument <e>T</e> you have to do an assignment to a variable of type <e>T</e> first and then pass this variable instead or use the adapt routine of the TYPE class, ie {T} [U].

==== Assigning agents ====

<e>
local
an_agent: PROCEDURE [ANY, TUPLE [T]]
-- An agent which takes an argument of type T.
do
agent_empty := agent () do end --> PROCEDURE [ANY, TUPLE []]
agent_any := agent (a: ANY) do end --> PROCEDURE [ANY, TUPLE [ANY]]
agent_t := agent (t: T) do end --> PROCEDURE [ANY, TUPLE [T]]
agent_u := agent (u: U) do end --> PROCEDURE [ANY, TUPLE [U]]
agent_tt := agent (t: T; t: T) do end --> PROCEDURE [ANY, TUPLE [T, T]]

-- The only legal assignment is an agent with the exact same generic parameters.
an_agent := agent_t

-- None of the follwing assignments is permitted, although it would be safe
-- to do so. The `empty_agent' would just discard the T argument passed, and the
-- `any_agent' also works if a T is passed.
an_agent := agent_empty
an_agent := agent_any

-- The following assignments are not permitted by the solution. This is the correct
-- behaviour as you could either create a catcall by passing a T argument to the
-- `agent_u' or pass the wrong number of arguments by passing a [T] tuple to the
-- `agent_tt'.
an_agent := agent_u
an_agent := agent_tt
end
</e>

Again, not all assignments which would be safe are allowed by the type system.

== Conclusion ==

In the non-generic case this solution limits the direct modeling ability as you cannot express covariant changes in the arguments. Since covariant redefinition is a precondition strengthening this can be justified on a mathematical basis, especially since covariant argument redefinition can be simulated through renaming.

In the generic case the possibilities are severely limited. It is not possible to use a list with a more general type even for reading (e.g. LIST [ANY]) without copying all elements over from a more specialized list (e.g. LIST [STRING]).

Template:Research

2007-06-24T18:40:01Z

Juliant:

'''Research:''' This page describes research about Eiffel, not the actual language specification.

Comparison of catcall solutions

2007-06-24T02:18:12Z

Juliant: /* General remarks */

[[Category:ECMA]]
[[Category:Catcall]]
== 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 statically 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 [[Single level call rule implementation|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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> where the feature <e>put</e> changes signature from <e>ANY</e> to <e>INTEGER</e>.
* 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 <e>like Current</e>. 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 <e>LIST [ANY]</e> to <e>LIST [INTEGER]</e> only the features based on the formal change their signature while they don't change from <e>LIST [ANY]</e> to <e>LINKED_LIST [ANY]</e> 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 <e>STRING</e> or one for <e>ANY</e> is suitable.
* If you want to pass an argument of type <e>STRING</e> to an agent, the agent either has to accept a <e>STRING</e> or <e>ANY</e> 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 [http://dev.eiffel.com/Covariance_through_renaming 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: [http://dev.eiffel.com/Forget_/_Keep_Mechanism 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueFLEX_CATCALL IssueFLEX_CATCALL on ECMA wiki] 
Reference: Discussion in ECMA mailinglist named ''Catcall removal: another proposal'', [[Restrict types mail|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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueDOG 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: [http://pag.csail.mit.edu/reading-group/variance-ECOOP02.pdf 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: [http://blogs.msdn.com/rmbyers/archive/2006/06/01/613690.aspx Article about generics in CLR]

Note: There is also a [http://fams.de/text/type-safe-eiffel.html 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: [http://www.jot.fm/issues/issue_2004_12/article5 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: [http://se.ethz.ch/~meyer/publications/lncs/attached.pdf Article about ''attached types'' by Bertrand Meyer] 
Reference: [http://www.ecma-international.org/publications/standards/Ecma-367.htm 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: [http://se.inf.ethz.ch/cgi-bin/ecma/index.cgi?IssueCAT IssueCAT on ECMA wiki] 
Reference: [http://www.inf.ethz.ch/~meyer/ongoing/covariance/recast.pdf 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 [[Comparison of catcall solutions#Table_explained|explanation at the end of the table]] for more information

=== General solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Novariance]]
! [[Forget / keep]]
! Dynamic typeset algorithm

|-

! Syntax overhead
| {{Green|No}}
| {{Red|Big}}: forget/keep clauses per type
| {{Green|No}}

|-

! Covariance on non-generic types
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Red|Not allowed}}
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| {{Red|Very limited}}: Only invariant conformance
| {{Orange|Limited}}: Conformance restricted (''keep all'' as default) {{Orange|Limited}}: Use restricted (''forget all'' as default)
| {{Green|As it is now}}

|-

! Agents
| {{Orange|Limited}} {{Green|Safe}}
| {{Orange|Limited}} {{Green|Safe}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on forget/keep clauses
| {{Red|Big}}: Iterative abstract system execution

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Need to know cat features for object tests
| {{Green|Small}}: As it is now

|-

! Whole-system analysis
| {{Green|No}}
| {{Red|Yes}}: use of ''forget all'' depends on system
| {{Red|Yes}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Red|No}}
| {{Red|No}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Orange|Limited}}
| {{Green|Full}}

|-

! Support of IDE (Source changes)
| {{Green|Not needed}}
| {{Orange|Possible}}: Can propose forget/keep clauses
| {{Green|Not needed}}

|}

=== Solutions for non-generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Restrict types]]
! [[DOG proposal]]

|-

! Syntax overhead
| {{Red|Big}}: Restrict clause per type declaration
| {{Orange|Medium}}: ''cat'' on features and on type declarations

|-

! Covariance on non-generic types
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Export status restrictions
| {{Green|Allowed}}
| {{Green|Allowed}}

|-

! Use of generic types
| Not addressed
| Not addressed

|-

! Agents
| Not addressed
| Not addressed

|-

! Comparator
| Not addressed
| Not addressed

|-

! Complexity of compiler check
| {{Orange|Medium}}: Check of feature call for all descendants; Conformance check on restrict clauses
| {{Green|Small}}: Check of ''cat'' on conformance

|-

! Complexity of runtime
| not yet considered
| {{Green|Small}}

|-

! Whole-system analysis
| {{Orange|Partial}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Orange|Limited}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}
| {{Red|Very limited}}

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose restrict clauses
| {{Orange|Possible}}: Can propose ''cat'' marks

|}

=== Solutions for generics ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Usage-site variance]]
! [[Definition-site variance]]
! Wildcard generics

|-

! Syntax overhead
| {{Orange|Medium}}: Variance marks per generic type
| {{Green|Small}}: Variance marks per generic class definition
| {{Orange|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
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}
| {{Orange|Limited}}: Conformance is limited {{Green|Safe}}

|-

! Agents
| {{Green|Fully supported}} {{Green|Safe}}
| {{Orange|Almost fully supported}} {{Green|Safe}}
| {{Green|Fully supported}} {{Green|Safe}}

|-

! Comparator
| {{Green|Supported}}
| {{Green|Supported}}
| {{Green|Supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check
| {{Green|Small}}: Consider variance in conformance check

|-

! Complexity of runtime
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test
| {{Green|Small}}: Consider variance in object test

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Orange|Limited}}: Use of generics changed due to conformance
| {{Red|Very limited}}: Libraries need redesign
| {{Orange|Limited}}: Use of generics changed due to conformance

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose variance marks
| {{Red|Not possible}}: Libraries need redesign
| {{Orange|Possible}}: Can propose variance marks/wildcards

|}

=== Dynamic solutions ===

{| border=1 cellpadding=2

|- style="visibility: hidden"
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |
| style="width:25%" |

|-

! Criteria
! [[Detachable types]]
! Recast
! Exceptions

|-

! Syntax overhead
| {{Green|Small}}: Detachment marks
| {{Red|Big}}: Recast clauses, recast features
| {{Orange|Medium}}: If rescue clause mandatory {{Green|No}}: If rescue clause not needed

|-

! Covariance on non-generic types
| {{Red|Very limited}}: Only detached arguments, no expanded arguments
| {{Green|Allowed}}
| {{Green|Allowed}}
|-

! Export status restrictions
| Not addressed
| Not addressed
| Not addressed

|-

! Use of generics
| {{Red|Very limited}}: Only detachable formal arguments
| {{Red|Very limited}}: Recast clause for all features with formal generics
| {{Green|As it is now}}

|-

! Agents
| {{Red|As it is now}}
| {{Red|As it is now}}
| {{Red|As it is now}}

|-

! Comparator
| {{Red|Not supported}}
| {{Red|Not supported}}
| {{Red|Not supported}}

|-

! Complexity of compiler check
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now
| {{Green|Small}}: As it is now

|-

! Complexity of runtime
| {{Green|Small}}: As it is now
| {{Orange|Medium}}: Check for catcalls and do recast
| {{Orange|Medium}}: Check for catcalls and raise exception

|-

! Whole-system analysis
| {{Green|No}}
| {{Green|No}}
| {{Green|No}}

|-

! Dynamic class and type loading
| {{Green|Yes}}
| {{Green|Yes}}
| {{Green|Yes}}

|-

! Backward compatibility
| {{Red|Very limited}}: All covariant and generic features become detached
| {{Red|Very limited}}: All covariant and generic features need recast clause
| {{Orange|Limited}}: If rescue clause is mandatory {{Green|Full}}: If rescue clause not needed

|-

! Support of IDE (Source changes)
| {{Orange|Possible}}: Can propose detachment marks
| {{Red|Not possible}}: Programmer must provide recast clause
| {{Red|Not possible}}: If rescue clause mandatory {{Green|Not needed}}: If rescue clause not needed

|}

=== Table explained ===

; Syntax overhead : {{Green|Small}} if a keyword/mark is needed per class/feature declaration; {{Orange|Medium}} if a keyword/mark is neede per type declaration; {{Red|Big}} if a clause is needed per type declaration.
; Use of generics : {{Green|As it is now}} if assignments are possible if generic parameters conform; {{Orange|Limited}} is some restrictions in the use or the conformance between generics exist; {{Red|Very limited}} a lot of restrictions in the use or the conformance between generics exist.
; Agents : {{Green|Fully supported}} if all safe assignments are allowed; {{Orange|Limited}} if not all safe assignments are allowed; {{Red|As it is now}} if unsafe assignments are still possible.
; Comparator : {{Green|Supported}} if for a comparator all safe assignments are permitted (i.e. contravariant assignments); {{Red|Not supported}} if only exact type or even (unsafe) subtypes can be assigned.
; Support of IDE (Source changes) : {{Green|Not needed}} if everything still works the same; {{Orange|Possible}} if the compiler can suggest clauses or marks; {{Red|Not possible}} if the programmer has to specify additional features/instructions.

== Personal opinions ==

[[Personal view about catcall solution]]

Catcall checkpoints

2007-06-24T01:59:41Z

Juliant: /* faces of covariance */

Catcall checkpoints

2007-06-24T01:59:08Z

Juliant: