[Python-3000] my take on "typeclasses"

[Phillip J. Eby]

A quick disclaimer first: I'm not necessarily supporting Talin's proposal, 
because I don't entirely understand it, and I think it's more ambitious in 
scope and more vague in implementation details than what I'm proposing.  So 
I think he's proposing a superset of what I propose, and thus I only 
support the subset of his proposal that overlaps my own.  ;)


At 12:45 AM 5/12/2006 +0200, Marcin 'Qrczak' Kowalczyk <qrczak at knm.org.pl> 
wrote:
>Talin <talin at acm.org> writes:
>
> > For any two predicates A & B, comparing them will produce one of four
> > possible outcomes:
> >
> >     1) A is a superset of B. In other words, any object that meets the
> > criteria for B also meets the criteria for A.
> >     2) B is a superset of A.
> >     3) Neither A nor B overlap. So an object that meets the criteria for
> > A can never meet the criteria for B and vice versa.
> >     4) There may or may not be some overlap between A and B.
>
>I'm afraid that most practical cases would yield 4.

Practical field experience with RuleDispatch begs to differ.  I'd suggest 
you read the Chambers & Chen papers on this, it clarifies quite well what 
is and isn't provable regarding criteria implication like this, for varying 
degrees of implementation complexity.

RuleDispatch does more than their implementation does, by adding 
implication support for simple inequalities, and there is a 
RuleDispatch-like system for Java that actually uses a theorem prover at 
compile time to do even more.

It's true in principle that you can always come up with some kind of 
criterion scenario that exceeds the limits of your current 
system.  However, in extensible systems like RuleDispatch and the Java one 
(JPred, I think?) you can always add new rules to the system for 
determining the precedence of rules.  The rarity with which this question 
comes up among RuleDispatch users suggests that it's not a common problem 
in practice.


>For predictably behaving libraries, rules of prioritizing specializers
>must be clearly defined. Otherwise there will be issues like "how do I
>teach Python that a matrix is not a number (even though it has arithmetic
>operators) and not a mapping (even though it has indexing), so Python
>doesn't try to apply specializations designed for numbers and mappings?",
>or "how do I teach Python that compressed streams are a subtype of
>file-like objects, so it chooses specializations of the former instead
>of reporting a conflict?".

By making the dispatch system itself accept rules, based on a simpler 
system.  See my sketch of such a system at:

     http://svn.python.org/projects/sandbox/trunk/Overload3K/

Although only 176 lines long (including docstrings and comments), it is 
sophisticated enough to allow definitions of new kinds of signature 
criteria, and rules for how they prioritize relative to one another.  It is 
limited only in that these rules can only use an object's *type* for 
criteria testing, but this limit is purely a side effect of the use of the 
classic "type-tuple cache" approach for the basic overloading 
implementation.  However, the framework defined in those 176 lines also 
allows other overloading implementations to be used, so the type limitation 
isn't an intrinsic one.

I think some future version of RuleDispatch will use this new framework to 
replace RuleDispatch's internal use of PyProtocols, and it would be awesome 
if some future version of Python with syntactic support for annotations and 
overloading could interoperate with it.



> >> When such concept is called to test the claim against an object,
> >> how does it determine whether the object is a function which takes
> >> an iterable and an int?
> >
> > By looking at the function's signature information.
>
>What if there is none (which is quite a common case)? The function
>is not applicable to this argument, the dispatch doesn't choose this
>specialization etc.? Then type signatures are no longer optional,
>functions constructed by generic wrappers rather than written by hand
>(e.g. partial applications) must provide some other means to specify
>the signature, and this is quite a radical shift towards a paradigm
>that I don't think Python would like.

For the language-supplied dispatch system that I propose, dispatch is only 
on argument *types*, so this introspect-the-signature thing you guys are 
talking about would not be available without user extensions.  I.e., a 
feature that allowed you to select an overload implementation by an 
argument's calling signature is definitely out of scope for my proposal.


>I claim that it's impossible to base sane details on this basis.
>You can't have type information which is at the same time:
>- flexible, so it can test arbitrary predicates
>- with a computable inclusion relation, so it can be used for dispatch
>- optional, so people can continue to write functions without type
>   annotations
>- predictable and explicit, so people can easily determine which
>   interfaces are supported by which types
>- implicit, based on duck typing, so capabilities are compared by
>   structure rather than by name
>etc.

My implementation sketch should suffice either as an existence proof that 
your claim is incorrect, or at the least provide you with a basis for 
clarifying your claim.

It is:

* flexible - it may be extended to support any kind of predicate that 
applies to argument types

* has a computable inclusion relation - as long as you implement the 
appropriate 'implies()' or 'type_matches()' methods

* optional - since clearly Python already works without it  :)

* predictable and explicit - since it is based entirely on declared overloads

* able to be implicit - since it allows membership in one overloadable 
function to be used as a dispatch criterion for inclusion in another  (and 
can easily be extended to support arbitrary combinations of inclusion, or 
even complex type signature tests like "argument X must be able to have an 
int added to it").

So unless I am misunderstanding your claim, it is incorrect.