Difference between revisions of "Interval types"

Revision as of 18:45, 5 July 2007

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

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:

LOWER..UPPER

This specifies an interval of all types between the types LOWER and UPPER.

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 ANY..STRING can be attached to an object of dynamic type ANY or dynamic type STRING. It cannot be attached to an object of a type which lies outside this interval, for example INTEGER or PATH_NAME.

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.

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

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.

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

• A type b: C..D conforms to the type a: A..B if C conforms to A and B conforms to D.

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 f (g: G) of a class X [G] is only valid if G is monomorphic. Thus the type has to be instantitated with X [Y..Y]. So a call to f on a type X [Y..NONE] 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:

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

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.

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

Valid assignments:

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

Invalid assignments:

-- 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

Valid calls:

a_none.eat (cat_food)
a_a.eat (food)
a_d.eat (food)

Invalid calls:

a_none.eat (food)

A simple generic algorithm

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

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

Issues

Generic features

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

deferred class COMPONENT
end
 
class COMPOSITE
inherit COMPONENT
feature
  components: LIST [COMPONENT]
end

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

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

Expanded and Void

Look at the following code snippet:

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

It illustrates two problems in conjunction with NONE:

• The first is that NONE 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 Void is of type NONE. This raises the question how Void 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 Void and NONE can easily be solved by declaring that NONE inherits from all types regardless of reference or expanded status. To solve the problem of assigning Void to an interval type it can be defined that Void is of any (detached) reference type. You could for example say that Void 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.