signature subtyping and role merging

1 view
Skip to first unread message

TSa

unread,
Oct 11, 2006, 12:10:37 PM10/11/06
to p6l
HaloO,

with my idea of deriving a type lattice from all role definitions
the problem of subtyping signatures arises. Please help me to think
this through. Consider

role Foo
{
sub blahh(Int, Int) {...}
}
role Bar
{
sub blahh(Str) {...}
}
role Baz does Foo does Bar # Foo|Bar lub
{
# sub blahh(Int&Str,Int?) {...}
}

The role Baz has to be the lub (least upper bound) of Foo and Bar.
That is the join of two nodes in the lattice. This means first of
all the sub blahh has to be present. And its signature has to be
in a subtype relation <: to :(Int,Int) and :(Str). Note that
Int <: Int&Str and Int|Str <: Int. The normal contravariant subtyping
rules for functions gives

+--------- :> ---+
| |
:(Int&Str,Int?) <: :(Int,Int)
| |
+--- :> -------+
and

+--------- :> ---+
| |
:(Int&Str,Int?) <: :(Str)

I hope you see the contravariance :)

The question mark shall indicate an optional parameter that
allows the subtype to be applicable in both call sites that
have one or two arguments.

The choice of glb for the first parameter makes the sub in Baz
require the implementor to use the supertype of Int and Str
which in turn allows the substitution of Int and Str arguments
which are subtypes---that is types with a larger interface.

Going the other way in the type lattice the meet Foo&Bar of the
two roles Foo and Bar is needed. But here the trick with the
optional parameter doesn't work and it is impossible to reconcile
the two signatures. This could simply mean to drop sub blahh from
the interface. But is there a better way? Perhaps introducing a
multi?

Apart from the arity problem the lub Int|Str works for the first
parameter:

+--------- <: ---+
| |
:(Int|Str,Int) :> :(Int,Int)
| |
+--- <: -------+

+---- <: ---+
| |
:(Int|Str) :> :(Str)


Regards, TSa.
--

Mark A Biggar

unread,
Oct 11, 2006, 1:37:56 PM10/11/06
to TSa, p6l
This is the "dog does bark" vs "tree does bark" problem. You can assume that the two methods "blahh" have naything semantically to do with each other at all. Unless ther is a specif annotation from the programmer creating the Role union that they are the same you must assume that they are different. Therefore your proposed signiture merge is nonsense in the general case. Even if the signature are the same the only case where you are justified in assuming that are the "same" method is if both composed Roles inherited the method from a common ancestor and even then you must solve the diamond inheritence problem.

--
Mark Biggar
ma...@biggar.org
mark.a...@comcast.net
mbi...@paypal.com

Jonathan Lang

unread,
Oct 11, 2006, 1:49:15 PM10/11/06
to TSa, p6l
On 10/11/06, TSa <Thomas....@barco.com> wrote:
> HaloO,
>
> with my idea of deriving a type lattice from all role definitions
> the problem of subtyping signatures arises. Please help me to think
> this through. Consider
>
> role Foo
> {
> sub blahh(Int, Int) {...}
> }
> role Bar
> {
> sub blahh(Str) {...}
> }
> role Baz does Foo does Bar # Foo|Bar lub
> {
> # sub blahh(Int&Str,Int?) {...}
> }

Please, no attempts to merge signatures. Instead, use multiple
dispatch (though technically this doesn't kick in until the role is
composed into a class). Thus:

role Foo
{
multi blahh(Int, Int) {...}
}
role Bar
{
multi blahh(Str) {...}


}
role Baz does Foo does Bar # Foo|Bar lub
{

# multi blahh(Int, Int) {...}
# multi blahh(Str) {...}
}

Remember that the name and the signature are used together to identify
the routine for dispatch and composition purposes.

Also, sub is an odd choice to use while illustrating role composition;
while subs _are_ allowed in roles AFAIK, they're generally not put
there. Methods and submethods are by far more common.

--
Jonathan "Dataweaver" Lang

TSa

unread,
Oct 23, 2006, 10:56:15 AM10/23/06
to p6l
HaloO,

Jonathan Lang wrote:
> Please, no attempts to merge signatures. Instead, use multiple
> dispatch

That avoids the problem before it occurs. But do you expect
every role to provide its methods as multi just in case?


> Also, sub is an odd choice to use while illustrating role composition;
> while subs _are_ allowed in roles AFAIK, they're generally not put
> there. Methods and submethods are by far more common.

The problem remains the same. After method lookup the arrow type of
the non-invocant parameters has to be a contra-variant supertype of
the two merged signatures. This signature is then a requirement to
the composed class that indirectly does both roles.


Regards, TSa.
--

Jonathan Lang

unread,
Oct 23, 2006, 12:05:43 PM10/23/06
to perl6language
TSa wrote:
> Jonathan Lang wrote:
> > Please, no attempts to merge signatures. Instead, use multiple
> > dispatch
>
> That avoids the problem before it occurs. But do you expect
> every role to provide its methods as multi just in case?

Conceded.

Bear in mind, though, that signatures include not only type
information, but also parameter names; and method calls are permitted
to pass an argument into a given parameter by means of its name
instead of its position, so the names cannot be disregarded. For
instance, consider the following pair of methods, supplied by
different roles:

method connect ( Terminal $from, Terminal $to ) { doit($from, $to) }
method connect ( Terminal $dest, Terminal $src ) { doit($src, $dest) }

There's no automated means that would allow you to reliably merge
those two signatures in a semantically appropriate way - not until
perl is smart enough to know that "from" and "src" have similar
connotations. When you have a conflict like this, you're better off
dropping the signatures altogether and leaving it up to the guy
writing the new implementation to figure out what to do with the
arguments that he gets.

--
Jonathan "Dataweaver" Lang

TSa

unread,
Oct 23, 2006, 12:36:38 PM10/23/06
to perl6language
HaloO,

Jonathan Lang wrote:
> Bear in mind, though, that signatures include not only type
> information, but also parameter names; and method calls are permitted
> to pass an argument into a given parameter by means of its name
> instead of its position, so the names cannot be disregarded. For
> instance, consider the following pair of methods, supplied by
> different roles:
>
> method connect ( Terminal $from, Terminal $to ) { doit($from, $to) }
> method connect ( Terminal $dest, Terminal $src ) { doit($src, $dest) }

Well, the type system would see these as a method that besides the
invocant has got two positional parameters of type Terminal and the
classes these things are composed into have to provide a method that
accepts these two. That's easy so far. But I see your point of the
argument names. So you can construct a role conflict and leave an
undefined method for the class. As long as users abide by the positional
interface they get what either role guarantees. When names have to be
available as well, then we get an undefined method that has to have two
positionals and two named parameters such that all four names appear
to satisfy all conceivable call sites for the two roles.


> There's no automated means that would allow you to reliably merge
> those two signatures in a semantically appropriate way - not until
> perl is smart enough to know that "from" and "src" have similar
> connotations. When you have a conflict like this, you're better off
> dropping the signatures altogether and leaving it up to the guy
> writing the new implementation to figure out what to do with the
> arguments that he gets.

I don't know how close leaving an undefined method as described above
to the class designer comes to automated merge. Note that at no point
I'm arguing that the body be merged. I'm seeing guarantees that the type
system tries to hold up in favour of the users of roles.


Regards, TSa.
--

Jonathan Lang

unread,
Oct 23, 2006, 2:05:30 PM10/23/06
to perl6language
TSa wrote:
> I don't know how close leaving an undefined method as described above
> to the class designer comes to automated merge. Note that at no point
> I'm arguing that the body be merged. I'm seeing guarantees that the type
> system tries to hold up in favour of the users of roles.

If you're not using "multi", then the signature is superfluous for
type-checking purposes. That is the purpose of not using "multi",
after all: to avoid the overhead involved in using the signature in
method identification. So either you use multi, in which case the
signatures exist in parallel; or you don't, in which case the
signature isn't important.

--
Jonathan "Dataweaver" Lang

TSa

unread,
Oct 24, 2006, 3:22:05 AM10/24/06
to perl6language
HaloO,

Jonathan Lang wrote:
> If you're not using "multi", then the signature is superfluous for
> type-checking purposes.

I think that signatures do matter for type-checking! It is
an error to provide too few or to many positional args or
args with an incompatible type.


Regards, TSa.
--

TSa

unread,
Oct 24, 2006, 11:54:53 AM10/24/06
to perl6language
HaloO,

TSa wrote:
> When names have to be available as well, then we get an undefined
> method that has to have two positionals and two named parameters such
> that all four names appear to satisfy all conceivable call sites for
> the two roles.

To get four names for two positional Parameters an 'is alias' parameter
trait is needed that can be given several times to produce an alias
that can be used as key in the named argument binding. Such a trait is
also very useful for backwards compatibility when parameter names are
changed. The signature merger would set alias traits as needed.

I don't know how the routine that is put behind the signature determines
in which context it was called to correctly swap the arguments for the
backend doit routine. Ideas?


Regards, TSa.
--

Jonathan Lang

unread,
Oct 24, 2006, 7:33:44 PM10/24/06
to perl6language

Mea culpa. I thought you were still talking about using an object's
methods as part of the process of deciding whether or not that object
satisfies the role requirements of some other routine's signature. Of
course signatures matter when it comes to deciding which arguments
that method will accept.

--
Jonathan "Dataweaver" Lang

Reply all
Reply to author
Forward
0 new messages