Subject: Re: another fun one
From: Vassily Litvinov (vass@cs.washington.edu)
Date: Fri Apr 06 2001 - 21:52:36 PDT
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 : Fri Apr 06 2001 - 21:53:04 PDT