Interval types and usage-site variance

Revision as of 18:58, 5 July 2007 by Juliant (Talk | contribs) (Combining the mechanisms)

Research: This page describes research about Eiffel, not the actual language specification.

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:

  • LOWER..UPPER

Generic parameters can be marked to select the variance:

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

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 (LOWER) and if the upper bound (UPPER) 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 b: C..D conforms to the type a: A..B if C conforms to A and B conforms to D. 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 LIST [T] only conforms to LIST [T].
  • A generic conforms to a covariant generic if its generic parameter conforms to the generic parameter of the covariant generic. Thus LIST [U] conforms to LIST [+T].
  • A generic conforms to a contravariant generic if its generic parameter is a parent of the generic parameter of the contravariant generic. Thus LIST [T] conforms to LIST [-U].

Default behaviour

The default for a type declaration is that the interval contains the type up to NONE (note that it is assumed that NONE also conforms to expanded types. See the conclusion of interval types for more information.):

a: ANY  -- means ANY..NONE

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:

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

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

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

Cats and dogs

See the interval types example.

A simple generic algorithm

See the usage-site variance example.