develooper Front page | perl.perl6.language | Postings from July 2005

Inferring (Foo of Int).does(Foo of Any)

Thread Next
From:
Autrijus Tang
Date:
July 27, 2005 16:19
Subject:
Inferring (Foo of Int).does(Foo of Any)
Message ID:
20050727231952.GB32639@aut.dyndns.org
As Perl 6's aggregate types are generics (Role that takes type
parameters), the problem of type variancy naturally arises.

The basic premise is that:

    1.	    (Array of Item).does(Array of Int);	# false
    2.	    (Array of Int).does(Array of Item);	# also false!

Intuitively, while an (Array of Item) can store anything that an
(Array of Int) can store, it cannot promise to yield a Int as the
latter can.  Conversely, while (Array of Int) can always yield
something that does Item, it cannot promise to store any Item.
Hence neither can be the subtype of the other.

As another example, consider this:

    sub f (Foo @x) { ... }
    my Bar @y;

One can't expect f(@y) to work, unless both Bar.does(Foo) _and_
Foo.does(Bar).  To see the reason, consider Array's interface:

    # invariant generics
    role Array[of => ::t] {
	method FETCH (Int $idx) returns ::t { ... }
	method STORE (Int $idx, ::t $elm) { ... }
    }

Note that ::t occurs at both the return position, and at the parameter
position.  This means what when we fetch elements from an array of @foo,
it needs to be used in a context that expects a supertype of Foo.
On the other hand, when we store something into @foo, the expected
context is a subtype of Foo.  For @y to work in both positions, Bar
needs to meet both side of the demands.

I think it makes sense to hold both #1 and #2, instead of favoring
one side or the other.  If so, then the default Array type needs to be
something like (Array of Any|All), and do a &coerce:<as> whenever an
actual fetch happens.

However, this rigid invariancy does not need to apply to all generic
types.  For example, consider this:

    # covariant generics
    role Input[of => ::t] {
	method READ () returns ::t { ... }
    }

Clearly, we can have (Input of Int).does(Input of Item), since anything
that can read Int can be used in places that expects Item as inputs.

On the other hand, this:

    # contravariant generics
    role Output[of => ::t] {
	method WRITE (::t) { ... }
    }

means that (Output of Item).does(Output of Int), as a output channel for
Items can surely be used anywhere that wishes to writes out Ints.

As a final example:

    # nonvariant generics
    role Contrived[of => ::t] {
	method NOOP () { ... }
    }

Not only (Contrived of Int).does(Contrived of Item), the converse is
also true, as the type parameter is not actually used anywhere.

Hence, my proposal is that Perl 6's generics should infer its variancy,
based on the signature of its methods, and derive subtyping relationships
accordingly.

The other alternative is do as Java does, which is assume invariancy by
default, then force users to write variancy annotations, but I think
that is considerably less attractive.  There may be a case for inferring
by default, but overridable by the user; if so there needs to be a
syntax for that.

Thanks,
/Autrijus/


Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About