Subject: Re: another fun one
From: Craig Chambers (chambers@cs.washington.edu)
Date: Sat Apr 07 2001 - 12:42:39 PDT
Wow. Something is seriously wrong with the Cecil type system, if it's so damn
hard to get things to work, and so subtle and unexpected the ways things can go
wrong. If I understand you correctly, Vass, then the real error is in the type
of the x argument of the hash_keyed_set includes method, not the receiver at
all. The type error message didn't make this very clear to me.
I wonder if there's some way of rethinking inheritance/subtyping, and
parameterization, that would either make the error clearer or allow the code to
be written more normally.
Maybe the backquote sugar is to blame, for hiding the constraints that hold on
hash_keyed_set Value parameters that aren't true of plain collection T
parameters? If so, we'd have to rethink how we handle the backquote sugar,
without making things syntactically too verbose.
-- Craig
Vassily Litvinov wrote:
>
> On Fri, 6 Apr 2001, Craig Chambers wrote:
>
> > Can you explain why this does work?
> > ....
> >
> > collection.cecil:149: implementation type error
> > Kind: could not find legal instantiation of the callee
> > Sig: method includes(c@:collection[`T <= comparable[T]], x:T):bool
> > Recvs: -hash_keyed_set[A,B], *-
> > Callee: method includes(t@:hash_keyed_set[`Key, `Value <= comparable[Value]],
> > val:Value):bool
> > Instantiated signature:
> > signature includes(c@:collection[`T <= comparable[T]], x:T):bool
> > Instantiated receivers:
> > -hash_keyed_set[`#Key-2,`#Value-2], *-
> > Available constraints:
> > SUB `#Value-2 <= `#T-1
> > SUB `#T-1 <= comparable[`#T-1]
> > SUB `#Key-2 <= hashable[`#Key-2]
> > SUB `#Value-2 <= keyed_hashable[`#Key-2]
> > SUB `#Value-2 <= comparable[`#T-1]
> > Callee instantiation constraints - could not solve them:
> > includes(t@:hash_keyed_set[`Key, `Value <= comparable[Value]], val:Value):bool
> > SUBi `#Key-2 <= hashable[`#Key-2]
> > SUBi `#Value-2 <= keyed_hashable[`#Key-2]
> > SUB hash_keyed_set[`#Key-2,`#Value-2] <= hash_keyed_set[`#Key-2,`#Value-2]
> > SUB `#T-1 <= `#Value-2
> > SUB bool <= bool
>
> This is a classic one. I mean, the reason for the error is classic.
> (Craig, I didn't quite follow your line of reasoning - can you explain?)
>
> To explain the error, I'll give a simple example. Imagine you have the following:
>
> signature identity_includes(collection[`T], T):bool;
> implementation identity_includes(@:m_vector[`Q], :Q):bool { ... }
>
> Then, at some point, you happily send a message with the following
> argument types:
>
> ... identity_includes(:m_vector[int], :num) ...
>
> Is this send legal? Yes of course: m_vector[int] subtypes collection[num].
> But the implementation is going to have problems, because it expects the
> second argument to be of type int, not num. (Recall that m_vector[int]
> does not subtype m_vector[num].) Hence the error.
>
> Now, the critical reader will observe that the implementaaation of
> identity_includes on m_vector only sends an == to elements of m_vector and
> the second argument. Therefore both m_vector elements and the second
> argument can be of any types. In other words, we can re-write the
> implementation as follows:
>
> implementation identity_includes(@:m_vector[`Q], :any):bool { ... }
>
> and everything will work just fine.
>
> It turns out, however, that in real life you cannot always play this
> trick. Coming back to the above error on includes() for hash_keyed_set[],
> let's look at the callee. The second argument, in fact, must be
> keyed_hashable because message hash_key() is sent to it.
>
> So the following scenario is legal according to the signature, but will
> cause run-time message-not-understood error in the body of the
> implementation of includes():
>
> x is a hash_keyed_set[K,V] where V is keyed_hashable
> y is of type V1 where - V1 is a supertype of V, and
> - V1 is comparable
>
> then message send includes(x,y) is legal, as x is a subtype of collection[V1].
>
> I still tried to play that same trick as in the simple example, but in a
> more subtle way. Namely, the implementation of includes() on
> hash_keyed_set also dispatches on the second argument, and if that one is
> not keyed_hashable, returns false. I haven't been able to get typing
> right so far, but I'll come back to it later.
>
> This solution does have extra run-time cost, but it can be eliminated by
> introducing helper methods and invoking them directly if the receivers are
> known more precisely. That would be a bit inconvenient for the
> programmer, but can be avoided with static overloading (language-supported
> or compiler-implemented).
>
> And as a side thought: these rough experiences with ITC may hint that the
> way Cecil type system is set up (CTC+ITC) is not a perfect language design.
> ML_sub offers somewhat different ITC (more integrated with CTC). But on
> the other hand our type system appears to be more powerful, and maybe what
> we are trying to do is inherently more complex, so requires more
> sofistication to comply with the typechecker.
>
> Vass
_______________________________________________
Cecil mailing list
Cecil@cs.washington.edu
http://majordomo.cs.washington.edu/mailman/listinfo/cecil
This archive was generated by hypermail 2b25 : Sat Apr 07 2001 - 12:41:04 PDT