Difference between revisions of "Definition-site variance"

Revision as of 10:05, 24 June 2007

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

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: class LIST [G] end
• To specify a covariant generic, we use a plus sign: class READ_LIST [+G] end
• To specify a contravariant generic, we use a minus sign: class WRITE_LIST [-G] end

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 LIST [T] only conforms to LIST [T].
• 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 READ_LIST [U] conforms to READ_LIST [T].
• 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 WRITE_LIST [U] conforms to WRITE_LIST [T].

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:

• TUPLE [T, U] conforms to TUPLE [T]
• TUPLE [U] does not conform to TUPLE [T]

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. LIST [G] needs to inherit from READ_LIST [+G]. That way you can assign a LIST [STRING] to a READ_LIST [STRING] and, through transitivity of conformance, to a READ_LIST [ANY].

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

Comparator

For the comparator example to work, the comparator class has to be declared as contravariant generic: class COMPARATOR [-G].

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

Agents

Again, to use definition-site variance you have to adapt the library design. The procedure class has to be defined as follows:

class PROCEDURE [+BASE_TYPE, -OPEN_ARGS -> TUPLE]
end

Calling agents

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

In contrast to 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

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

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 TUPLE parameters cannot be specified as covariant in the class definition of PROCEDURE. Since TUPLE 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:

class PROCEDURE [+BASE_TYPE, -OPEN_ARGS -> TUPLE[+]]
end

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.